Linear recursive networks and their applications in topological design and data routing

ABSTRACT

We present a new class of interconnection topologies called the Linear Recursive Networks. It is shown that each member of this fairly large class of network topologies possesses a recursively-decomposable structure. The path and connectivity properties of the entire class of networks are analyzed and found to have useful features. It is also demonstrated that Point-To-Point or Broadcasting/Gathering operations can be performed efficiently on all Linear Recursive Networks. The preliminary results suggest that the Linear Recursive Networks potentially have many applications.

REFERENCES

• 1: B. W. Arden and H. Lee, "Analysis of Chordal Ring Network," IEEE Trans. on Computers, C-30, 1981, 291-295.
• 2: R. C. Backhouse and B. A. Carre, "Regular Algebra Applied to Path-Finding Problems," J. Inst. Math. Applic., 15, 1975, i61-186.
• 3: V. E. Benes, Mathematical Theory of Connecting Networks and Telephone Trajfic, Academic Press, Orlando, FL., 1965.
• 4: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 5: R. R. Boorstyn and H. Frank, "Large Scale Network Topological Optimization," IEEE Trans. Communications, COM-26, Jan. i977, 29-47.
• 6: John Carroll , Darrell Long, Theory of finite automata with an introduction to formal languages, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 7: Wushow Chou, Computer communications. Vol. II: systems and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1985
• 8: Narsingh Deo, Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation), Prentice-Hall, Inc., Upper Saddle River, NJ, 1974
• 9: R. A. Finkel and M. H. Solomon, "The Lens Interconnection Strategy," IEEE Trans. Computers, C-30, 1981.
• 10: M. D. Gaudreau, "Recursive Formula for the Calculation of Point-to-Point Congestion," IEEE Trans. Communications, COMM-28, March 1980, 313-316.
• 11: M. Gerla and L. Kleinrock, "On the Topological Design of Distributed Computer Networks," IEEE Trans. Communications, COM-25, Jan. 1977.
• 12: A. Ghafoor, "A Class of Fault-Tolerant Multiprocessor Networks," IEEE Trans. Reliability, R,-38, April 1989, 5-15.
• 13: J. N. Hagstrom, "Using the Decomposition Tree of a Network in Reliability Evaluation," IEEE Trans. Reliability, R-32, April 1983, 71-78.
• 14: F. Harary, Graph Theory, Addison-Wesley Pub. Co., Reading, Mass., 1969.
• 15: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 16: W. J. Hsu, Fibonacci Cubes-A New Interconnection Technology, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.3-12, January 1993 [doi>10.1109/71.205649]
• 17: W.-J. Hsu and M. J. Chung, "Generalized Fibonacci C, ubes", accepted, to appear in Proc. Int'l Conference on Parallel Processing, 1993.
• 18: S. P. Jain and K. Gopal, "On Network Augmentation,'' IEEE Trans. Reliability, R-35, Dec. 1986, 541-543.
• 19: J. Kim, et al., "Reliability Evaluation of the Hypercube," IEEE Trans. Reliability, R-38, April 1989, 121-129.
• 20: Jenshiuh Liu, Graph embedding and data communication in a large family of network topologies, Michigan State University, East Lansing, MI, 1992
• 21: G. Memmi and Y. Raillard, "Some Results About the (d, k) Graph Problem", iEEE Trans. Computers, C-3 l, 1982, 784-791.
• 22: H. Nakazawa, "Baysian Decomposition Method for Computing the reliability of an Oriented Network," IEEE Trans. Reliability, R-25, April 1976, 77-80.
• 23: Suresh Rai , Dharma P. Agrawal, Distributed Computing Network Reliability, IEEE Computer Society Press, Los Alamitos, CA, 1990
• 24: Sanjay Ranka , Sartaj Sahni, Hypercube algorithms: with applications to image processing and pattern recognition, Springer-Verlag New York, Inc., New York, NY, 1990
• 25: A. M. Rushdi, "On Reliability Evaluation by Network Decomposition," IEEE Trans. Reliability, R- 33, Dec. 1984, 379-384.
• 26: A. Satyanarayana and M. K. Chang, "Network Reliability and the Factoring Theorem," Networks, 13, 1983, 107-120.
• 27: Roshan Lal Sharma, Network Topology Optimization, John Wiley & Sons, Inc., New York, NY, 1990

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Distributed networks

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems; Trees

General Terms:
Design, Languages, Theory, Verification