research-article

A novel approach for all-to-all routing in all-optical hypersquare torus network

Authors:

Lixin ZhangAuthors Info & Claims

CF '16: Proceedings of the ACM International Conference on Computing Frontiers

Pages 250 - 258

https://doi.org/10.1145/2903150.2903173

Published: 16 May 2016 Publication History

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.

References

[1]

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.

[2]

B. Mukherjee, "WDM-based local lightwave networks. II. Multihop systems," Network, IEEE, vol. 6, no. 4, pp. 20--32, July 1992.

Digital Library

[3]

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.

Digital Library

[4]

L. Gargano and U. Vaccaro, Routing in All-Optical Networks: Algorithmic and Graph-Theoretic Problems. Springer US, 2000.

[5]

B. Beauquier, "All-to-all communication for some wavelength-routed all-optical networks," Networks, vol. 33, no. 3, pp. 179--187, 1998.

[6]

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.

Digital Library

[7]

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.

[8]

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.

Digital Library

[9]

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.

Digital Library

[10]

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.

[11]

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.

[12]

D. Zhou and S. Subramaniam, "Survivability in optical networks," IEEE network, vol. 14, no. 6, pp. 16--23, 2000.

Digital Library

[13]

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.

Digital Library

[14]

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.

Digital Library

[15]

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.

Digital Library

[16]

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.

[17]

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.

Digital Library

[18]

G. Ellinas and K. Bala, Wavelength Assignment Algorithms for WDM Ring Architectures. Springer US, 2001.

[19]

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.

Digital Library

[20]

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.

Digital Library

[21]

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.

[22]

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.

Digital Library

[23]

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.

Digital Library

[24]

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.

Digital Library

[25]

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.

Digital Library

Cited By

Manoharan KSabrigiriraj M(2022)Wavelength Allotment for All-to-All Broadcast in WDM Optical Bidirectional ring with 3-Length ExtensionWSEAS TRANSACTIONS ON COMPUTERS10.37394/23205.2022.21.1921(139-157)Online publication date: 9-May-2022
https://doi.org/10.37394/23205.2022.21.19
Manoharan KSabrigiriraj M(2022)All-to-all Broadcast in Optical WDM Ring with 2-length Extension and 3-length ExtensionWSEAS TRANSACTIONS ON COMMUNICATIONS10.37394/23204.2022.21.1921(135-154)Online publication date: 20-May-2022
https://doi.org/10.37394/23204.2022.21.19
Manoharan KSabrigiriraj M(2022)All-to-All Broadcast in WDM Linear Array with 3-length ExtensionWSEAS TRANSACTIONS ON CIRCUITS AND SYSTEMS10.37394/23201.2022.21.921(74-93)Online publication date: 6-May-2022
https://doi.org/10.37394/23201.2022.21.9
Show More Cited By

A novel approach for all-to-all routing in all-optical hypersquare torus network
1. Networks
  1. Network properties
    1. Network structure
      1. Network topology types
        Ring networks
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis

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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '16: Proceedings of the ACM International Conference on Computing Frontiers

May 2016

487 pages

ISBN:9781450341288

DOI:10.1145/2903150

General Chairs:
Gianluca Palermo
Politecnico di Milano, IT
,
John Feo
Pacific Northwest National Laboratory and Northwest Institute for Advanced Computing
,
Program Chairs:
Antonino Tumeo
Pacific Northwest National Laboratory, USA
,
Hubertus Franke
New York University and IBM Research, USA

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Micron Foundation: Micron Technology Foundation, Inc.
ACM: Association for Computing Machinery
Politecnico di Milano: Politecnico di Milano
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing
IBM: IBM

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 May 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China

Conference

CF'16

Sponsor:

Micron Foundation
ACM
Politecnico di Milano
SIGMICRO
IBM

CF'16: Computing Frontiers Conference

May 16 - 19, 2016

Como, Italy

Acceptance Rates

CF '16 Paper Acceptance Rate 30 of 94 submissions, 32%;

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
94
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Manoharan KSabrigiriraj M(2022)Wavelength Allotment for All-to-All Broadcast in WDM Optical Bidirectional ring with 3-Length ExtensionWSEAS TRANSACTIONS ON COMPUTERS10.37394/23205.2022.21.1921(139-157)Online publication date: 9-May-2022
https://doi.org/10.37394/23205.2022.21.19
Manoharan KSabrigiriraj M(2022)All-to-all Broadcast in Optical WDM Ring with 2-length Extension and 3-length ExtensionWSEAS TRANSACTIONS ON COMMUNICATIONS10.37394/23204.2022.21.1921(135-154)Online publication date: 20-May-2022
https://doi.org/10.37394/23204.2022.21.19
Manoharan KSabrigiriraj M(2022)All-to-All Broadcast in WDM Linear Array with 3-length ExtensionWSEAS TRANSACTIONS ON CIRCUITS AND SYSTEMS10.37394/23201.2022.21.921(74-93)Online publication date: 6-May-2022
https://doi.org/10.37394/23201.2022.21.9
Lo YFu HZhang YWong W(2020) The undirected optical indices of complete -ary trees Discrete Applied Mathematics10.1016/j.dam.2020.05.006285(173-181)Online publication date: Oct-2020
https://doi.org/10.1016/j.dam.2020.05.006
Sabrigiriraj MManoharan K(2019)Wavelength allocation for all-to-all broadcast in bidirectional optical WDM modified ringOptik10.1016/j.ijleo.2018.10.129179(545-556)Online publication date: Feb-2019
https://doi.org/10.1016/j.ijleo.2018.10.129
Sabrigiriraj MManoharan K(2019)Wavelength Allotment for All-to-All Broadcast in WDM Optical Modified Linear Array for Reliable CommunicationMobile Networks and Applications10.1007/s11036-017-0908-824:2(350-356)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s11036-017-0908-8

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents