Optical interconnection using ShuffleNet multihop networks in multi-connected ring topologies

ABSTRACT

In many applications, such as metropolitan area, campus, and local area networks, multicomputer interconnection networks, and the interconnection of cabinets, shelves, and boards, optical interconnection is increasingly favored over electrical. Recently, ShuffleNet multihop lightwave networks were proposed as a way to tap the vast bandwidth potential of optical fiber for multiuser packet communications. We consider the use of ShuffleNet multihop networks for optical interconnection, and study their implementation in ring topologies with each node connected to several other nodes of the ring (i.e., multi-connected ring topologies). To minimize fiber cabling congestion, the design procedure uses a new representation of the ShuffleNet connectivity graph and a generalization of Gray code patterns. As an example, only six fibers (without wavelength-division multiplexing) are required to interconnect 24 Network Interface Units (NIUs), providing a total network throughput of 1.47 Gb/s for an optical transmission rate of 100 Mb/s. The design also provides for easy, modular growth of multi-connected rings.

REFERENCES

• 1: Special Issue on Fiber Optics for Local Communications, IEEE J. Select. Areas Commun., vol. SAC-3, no. 6, Nov. 1985.
• 2: S.Y. Sub, S. W. Granlund, and S. S. Hegde, "Fiber- Optic Local Area Network Topology," IEEE Commun. Mag., vol. 24, no. 8, Aug. 1986.
• 3: Laxmi N. Bhuyan, Interconnection networks for parallel and distributed processing, Computer, v.20 n.6, p.9-12, June 1987 [doi>10.1109/MC.1987.1663585]
• 4: Daniel A. Reed , Dirk C. Grunwald, The performance of multicomputer interconnection networks, Computer, v.20 n.6, p.63-73, June 1987 [doi>10.1109/MC.1987.1663593]
• 5: L. Green, "Optical Interconnects: Upcoming LAN Technology," Proc. 12th Conf. Local Computer Networks, pp. 137-139, Oct. 1987.
• 6: A. S. Acampora, "A Muttichannel Multihop Local Lightwave Network," GLOBECOM'87 Conf. Rec., pp. 1459-1467, Nov. 1987.
• 7: M. G. Hluchyj and M. J. Karol, "ShuffleNet: An Application of Generalized Perfect Shuffles to Multihop Lightwave Networks," Proc. INFOCOM'88,
• 8: A. S. Acampora, M. J. Karol, and M. G. Hluchyj, "Terabit Lightwave Networks: The Multihop Approach," AT~T Tech. Journal, Nov./Dec. 1987.
• 9: H. S. Stone, "Parallel Processing with the Perfect Shuffle," IEEE Trans. Comput., vol. C-20, no. 2, pp. 153-161, Feb. 1971.
• 10: J. H. Patel, "Performance of Processor-Memory In terconnections for Multiprocessors," {EEE Trans. Comp~t., vol. C-30, no. 10, pp. 771-780, Oct. 1981.
• 11: Special Issue on Token-Ring Local Area Networks, IEEE Network Mag., vol. 1, no. 1, Jan. 1987.
• 12: J.H. Saltzer, K. T. Pogran, and D. D. Clark, "Why a Ring?" Computer Networks 7, pp. 223-231, North- Holland Publishing Company, New York, NY, 1983.
• 13: A. S. Tanenbaum, Computer networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 14: C S Raghavendra , J S Silvester, A survey of multi-connected loop topologies for local computer networks, Computer Networks and ISDN Systems, v.11 n.1, p.29-42, Jan. 1986 [doi>10.1016/0169-7552(86)90027-9]
• 15: J.A. Silvester and C. S. Raghavendra, "Analysis and Simulation of a Class of Double Loop Network Architectures," Proc. INFOCOM'$4, pp. 30-35, Apr. 1984.
• 16: C. S. Raghavendra, M. Gerla, and D. S. Parker, "Multi*Connected Loop Topologies for Loop Computer Networks," Proc. INFOCOM'8~, pp. 184- 190, Mar. 1982.
• 17: A. Khurshid and D. M. Rouse, "Photonic Switching in Ring-Based Optic Networks," submitted to IEEE J. Select. Areas Commun..
• 18: K. Y. Eng, "A Multi-Fiber Ring Architecture for Distributed Lightwave Networks," ?roc. ICC88, June 1988.
• 19: F. E. Ross, "FDDI- a Tutorial," iEEE Uommun. Mag., vol. 24, no. 5, May 1986.
• 20: W.-K. Chen, Applied Graph Theory- Graph and Electrical Networks, North-Holland Publishing Company, New York, NY, 1976.
• 21: M. Eisenberg and N. Mehravari, "On the Performance of the Multichannel Multihop Lightwave Network under Non-uniform Traffic," to appear in IEEE J. Select. Areas Commun., Aug. 1988.
• 22: M. J. Karol and S. Shaikh, "A Simple Adaptive Routing Scheme for ShuffleNet Multihop Lightwave Networks," submitted to GLOBECOM'88 (Nov. 1988).
• 23: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 24: J.G. Proakis, Digital Communications, McGraw-Hill Book Company, New York, NY, 1983.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Token rings

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.3 Interconnections (subsystems)
          Subjects: Fiber optics

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

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

General Terms:
Algorithms, Design