Zhuang Wang
Ke Liu
Long Li
Mingyu Chen
ABSTRACT
Wavelength division multiplexing (WDM) optical networks are becoming more attractive due to their unprecedented high bandwidth provisions and reliability over data transmission among nodes. Therefore, it is not uncommon for enterprises to build a datacenter with over thousands of nodes using WDM optical networks. To reach the high speed over optical links, all-optical, i.e., single hop, networks are desirable as there is no overhead on conversions to and from the electronic form compared to multi-hop networks. However, given the number of nodes required, few previous works suggested a topology, e.g., torus, to support all-to-all routing with the minimum number of wavelengths over all-optical networks. In this paper, we address this challenge from a different angle. Specifically, it is possible to build different torus topologies by altering the number of nodes in every dimension, but we first show that the minimum number of wavelengths to satisfy the all-to-all routing over torus is N/3, and prove that the necessary and sufficient condition to achieve it is the sides of all dimensions are 3; thus the resultant topology is an n-dimensional hypersquare torus network; then we develop a wavelength assignment to achieve the all-to-all routing over the corresponding n-dimensional hypersquare torus; finally, we consider the fail-over problem in our proposed topology and derive the minimum number of backup wavelengths to mitigate the affected lightpaths thus maintain the gossiping.
- I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: an approach to high bandwidth optical wan's," Communications, IEEE Transactions on, vol. 40, no. 7, pp. 1171--1182, Jul 1992.Google Scholar
Cross Ref
- B. Mukherjee, "WDM-based local lightwave networks. II. Multihop systems," Network, IEEE, vol. 6, no. 4, pp. 20--32, July 1992. Google ScholarDigital Library
- J.-C. Bermond, L. Gargano, S. Perennes, A. A. Rescigno, and U. Vaccaro, "Efficient collective communication in optical networks," Theoretical Computer Science, vol. 233, no. 1--2, pp. 165--189, 2000. Google ScholarDigital Library
- L. Gargano and U. Vaccaro, Routing in All-Optical Networks: Algorithmic and Graph-Theoretic Problems. Springer US, 2000.Google Scholar
- B. Beauquier, "All-to-all communication for some wavelength-routed all-optical networks," Networks, vol. 33, no. 3, pp. 179--187, 1998.Google ScholarCross Ref
- M. C. Heydemann, J. C. Meyer, and D. Sotteau, "On forwarding indices of networks," Discrete Applied Mathematics, vol. 23, no. 89, pp. 103--123, 1989. Google ScholarDigital Library
- M. A. Marsan, A. Bianco, E. Leonardi, and F. Neri, "A comparison of regular topologies for all-optical networks," in INFOCOM'93. Proceedings. Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies. Networking: Foundation for the Future, IEEE. IEEE, 1993, pp. 36--47.Google Scholar
- L. N. Bhuyan and D. P. Agrawal, "Generalized hypercubeand hyperbus structures for a computer network," IEEE Trans Comput, vol. 33, no. 4, pp. 323--333, 1984. Google ScholarDigital Library
- K. Day and A. E. Al-Ayyoub, "Fault diameter of k-ary n-cube networks," IEEE Transactions on Parallel and Distributed Systems, vol. 8, no. 9, pp. 903--907, 1997. Google ScholarDigital Library
- H. Choi, S. Subramaniam, and H.-A. Choi, "On double-link failure recovery in wdm optical networks," in INFOCOM 2002. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE, vol. 2. IEEE, 2002, pp. 808--816.Google ScholarCross Ref
- B. T. Doshi, S. Dravida, P. Harshavardhana, O. Hauser, and Y. Wang, "Optical network design and restoration," Bell Labs Technical Journal, vol. 4, no. 1, pp. 58--84, 1999.Google ScholarCross Ref
- D. Zhou and S. Subramaniam, "Survivability in optical networks," IEEE network, vol. 14, no. 6, pp. 16--23, 2000. Google ScholarDigital Library
- R. Ramaswami and G. Sasaki, "Multiwavelength optical networks with limited wavelength conversion," IEEE/ACM Transactions on Networking (TON), vol. 6, no. 6, pp. 744--754, 1998. Google ScholarDigital Library
- D. Banerjee and B. Mukherjee, "A practical approach for routing and wavelength assignment in large wavelength-routed optical networks," Selected Areas in Communications, IEEE Journal on, vol. 14, no. 5, pp. 903--908, 1996. Google ScholarDigital Library
- A. E. Ozdaglar and D. P. Bertsekas, "Routing and wavelength assignment in optical networks," IEEE/ACM Transactions on Networking (TON), vol. 11, no. 2, pp. 259--272, 2003. Google ScholarDigital Library
- K. Christodoulopoulos, K. Manousakis, and E. Varvarigos, "Comparison of routing and wavelength assignment algorithms in WDM networks," in Global Telecommunications Conference, 2008. IEEE GLOBECOM 2008. IEEE, Conference Proceedings, pp. 1--6.Google Scholar
- H. Schröder, O. Sýkora, and I. Vrt'O, "Optical all-to-all communication for some product graphs (extended abstract)," Lecture Notes in Computer Science, pp. 555--562, 1997. Google ScholarDigital Library
- G. Ellinas and K. Bala, Wavelength Assignment Algorithms for WDM Ring Architectures. Springer US, 2001.Google ScholarCross Ref
- B. Beauquier, S. Pérennes, and D. Tóth, "All-to-all routing and coloring in weighted trees of rings," in Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, ser. SPAA '99. New York, NY, USA: ACM, 1999, pp. 185--190. Google ScholarDigital Library
- S. Pascu and A. El-Amawy, "On conflict-free all-to-all broadcast in one-hop optical networks of arbitrary topologies," Networking, IEEE/ACM Transactions on, vol. 17, no. 5, pp. 1619--1630, Oct 2009. Google ScholarDigital Library
- L. Narayanan, J. Opatrny, and D. Sotteau, "All-to-all optical routing in chordal rings of degree four," Algorithmica, vol. 31, no. 2, pp. 155--178, 2001.Google ScholarCross Ref
- Q. P. Gu and S. Peng, "Multihop All-to-All Broadcast on WDM Optical Networks," IEEE Transactions on Parallel and Distributed Systems, vol. 14, no. 5, pp. 477--486, 2003. Google ScholarDigital Library
- J. Opatrny, "Uniform multi-hop all-to-all optical routings in rings," Lecture Notes in Computer Science, vol. 297, no. 1, pp. 385--397, 2000. Google ScholarDigital Library
- W. Liang and X. Shen, "A general approach for all-to-all routing in multihop WDM optical networks," Networking IEEE/ACM Transactions on, vol. 14, no. 4, pp. 914--923, 2006. Google ScholarDigital Library
- L. Sun, F. Zhang, and J. Qian, "Multi-hop all-to-all optical routings in cartesian product networks." Information Processing Letters, vol. 107, no. 6, pp. 252--256, 2008. Google ScholarDigital Library
- A novel approach for all-to-all routing in all-optical hypersquare torus network
Recommendations
A general approach for all-to-all routing in multihop WDM optical networks
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 ...
Fixed-alternate routing and wavelength conversion in wavelength-routed optical networks
Consider an optical network which employs wavelength-routing crossconnects that enable the establishment of wavelength-division-multiplexed (WDM) connections between node pairs. In such a network, when there is no wavelength conversion, a connection is ...
Routing and wavelength assignment for hypercube in array-based WDM optical networks
Hypercube is one of the most versatile and efficient communication patterns shared by a large number of computational problems. As the number of edges in hypercube grows logarithmically with the size of networks, the complexity of network topologies can ...
Comments