A general approach for all-to-all routing in multihop WDM optical networks

ABSTRACT

WDM optical networks provide unprecedented high speed and reliability for message transfer among the nodes. All-to-all routing is a fundamental routing problem in such networks and has been well studied on single hop WDM networks. However, the number of wavelengths to realize all-to-all routing on the single hop model typically is very large. One way to reduce the number of wavelengths is to use k-hop routing, in which each routing path consists of k segments and each segment is assigned a different wavelength, where k usually is a small constant. Because of the complexity of design and analysis for such a routing problem, only few papers discussed and proposed all-to-all routing by k ≥ 2 hops. However, the proposed algorithms are usually exceeding complicated even for ring topologies. Often, an ad hoc approach is employed to deal with each individual topology.In this paper we propose a generic method for all-to-all routing in multi-hop WDM networks, which aims to minimize the number of wavelengths. We illustrate the approach for several optical networks of commonly used topology, including lines, rings, tori, meshes, and complete binary trees. For each case an upper bound on the number of wavelengths is obtained. The results show that this approach produces clear routing paths, requires less wavelengths, and can easily incorporate load balancing. For simple topologies such as lines and rings, this approach easily produces the same bounds on the number of wavelengths that were hard-obtained previously. Moreover, this general approach provides a unified routing algorithm for any d-dimensional torus, which seems impossible to obtain by the previous approach.

REFERENCES

• 1: Alok Aggarwal , Amotz Bar-Noy , Don Coppersmith , Rajiv Ramaswami , Baruch Schieber , Madhu Sudan, Efficient routing in optical networks, Journal of the ACM (JACM), v.43 n.6, p.973-1001, Nov. 1996 [doi>10.1145/235809.235812]
• 2: [2] B. Beauquier, "All-to-all communication for some wavelength-routed all-optical networks," Networks, vol. 33, pp. 179-187, 1999.
• 3: [3] B. Beauquier, J.-L. Bermond, L. Gargano, P. Hell, S. Perennes, and U. Vaccaro, "Graph problems arising from wavelength-routing in all-optical networks," in Proc. 2nd Workshop of Optical and Computer Science (IPPS'97), Apr. 1997.
• 4: Bruno Beauquier , Stéphane Pérennes , David Tóth, All-to-all routing and coloring in weighted trees of rings, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.185-190, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305639]
• 5: Jean-Claude Bermond , Luisa Gargano , Stephane Perennes , Adele A. Rescigno , Ugo Vaccaro, Efficient Collective Communication in Optical Networks, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.574-585, July 08-12, 1996
• 6: Jean-Claude Bermond , Luisa Gargano , Stephan Perennes , Adele A. Rescigno , Ugo Vaccaro, Efficient collective communication in optical networks, Theoretical Computer Science, v.233 n.1-2, p.165-189, Feb. 28 2000 [doi>10.1016/S0304-3975(98)00018-8]
• 7: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 8: [8] I. Caragiannis, C. Kaklamanis, and P. Persiano, "Wavelength routing in all-optical tree networks: A survey," Bull. Eur. Assoc. Theoretical Comput. Sci., vol. 76, pp. 104-112, 2002.
• 9: Francesc Comellas , Margarida Mitjana , Lata Narayanan , Jaroslav Opatrny, Optical Routing of Uniform Instances in Tori, Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, p.285-294, September 01, 2000
• 10: Jack J. Dongarra , David W. Walker, Software libraries for linear algebra computations on high performance computers, SIAM Review, v.37 n.2, p.151-180, June 1995 [doi>10.1137/1037042]
• 11: Danny Dolev , Joe Halpern , Barbara Simons , Ray Strong, A new look at fault tolerant network routing, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.526-535, December 1984 [doi>10.1145/800057.808723]
• 12: Pierre Fraigniaud , Emmanuel Lazard, Methods and problems of communication in usual networks, Discrete Applied Mathematics, v.53 n.1-3, p.79-133, Sept. 14, 1994
• 13: G. C. Fox, Solving problems on concurrent processors, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 14: Luisa Gargano , Pavol Hell , Stephane Perennes, Colouring Paths in Directed Symmetric Trees with Applications to WDM Routing, Proceedings of the 24th International Colloquium on Automata, Languages and Programming, p.505-515, July 07-11, 1997
• 15: [15] L. Gargano and U. Vaccaro, I. A. Althofer, Ed., "Routing in all-optical networks: Algorithmic and graph-theoretic problems," in Numbers, Information and Complexity. Boston, MA: Kluwer, 2000, pp. 555-578.
• 16: [16] P. E. Green, Fiber-Optic Communication Networks. Englewood Clilffs, NJ: Prentice Hall, 1992.
• 17: Qian-Ping Gu , Shietung Peng, Multihop All-to-All Broadcast on WDM Optical Networks, IEEE Transactions on Parallel and Distributed Systems, v.14 n.5, p.477-486, May 2003 [doi>10.1109/TPDS.2003.1199065]
• 18: [18] S. M. Hedetniemi, S. T. Hedetniemi, and A. Liestman, "A survey of gossiping and broadcasting in communication networks," Networks, vol. 18, pp. 129-134, 1988.
• 19: [19] J. Hromkovic, R. Klasing, B. Monien, and R. Peine, D. Du and F. Hsu, Eds., "Dissemination of information in interconnection networks (broadcasting and gossiping)," in Combinatorial Network Theory. Boston, MA: Kluwer, 1995, pp. 125-212.
• 20: [20] W. Liang and X. Shen, "All-to-All routing in multihop WDM optical networks," [Online]. Available: http://cs.anu.edu.au/~Weifa.Liang/papers/ton_2.pdf
• 21: Alastair D. McAulay, Optical computer architectures: the application of optical concepts to next generation computers, John Wiley & Sons, Inc., New York, NY, 1991
• 22: [22] B. Mukherjee, "WDM-based local lightwave networks, Part I: Single-hop systems," IEEE Network Mag., vol. 31, pp. 78-88, 1993.
• 23: [23] B. Mukherjee, "WDM-based local lightwave networks, Part II: Multi-hop systems," IEEE Network Mag., vol. 6, pp. 12-27, 1992.
• 24: L. Narayanan , J. Opatrny , D. Sotteau, All-to-all optical routing in optimal chordal rings of degree four, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.695-703, January 17-19, 1999, Baltimore, Maryland, United States
• 25: Jaroslav Opatrny, Uniform Multi-hop All-to-All Optical Routings in Rings, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.237-246, April 10-14, 2000
• 26: [26] R. Ramaswami, "Multi-wavelength lightwave networks for computer communication," IEEE Commun. Mag., vol. 31, pp. 78-88, 1993.
• 27: Heiko Schröder , Ondrej Sýkora , Imrich Vrto, Optical All-to-All Communication for Some Product Graphs, Proceedings of the 24th Seminar on Current Trends in Theory and Practice of Informatics: Theory and Practice of Informatics, p.555-562, November 22-29, 1997
• 28: Ronald J. Vetter , David H. C. Du, Distributed computing with high-speed optical networks, Computer, v.26 n.2, p.8-18, February 1993 [doi>10.1109/2.191977]
• 29: Gordon Wilfong , Peter Winkler, Ring routing and wavelength translation, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.333-341, January 25-27, 1998, San Francisco, California, United States
• 30: Xijun Zhang , Chunming Qiao, On scheduling all-to-all personalized connections and cost-effective designs in WDM rings, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.435-445, June 1999 [doi>10.1109/90.779215]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
      C.2.5 Local and Wide-Area Networks
          Subjects: High-speed (e.g., FDDI, fiber channel, ATM)

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Design

Keywords:
WDM routing, all-to-all routing, gossiping, multihop routing algorithms, network design, optical networks, robust routing protocol