Affiliations: Center for Telecommunications Research, 530 W. 120th Street, Room 801, Columbia University, New York, NY 10027, USA, Tel.: (908) 957-7174, Fax: (908) 957-7500, E-mail: zhang@mrspock.mt.att.com
Note: [] This work was part of the Optical Network Technology Consortium (ONTC) under ARPA contract MDA 972-92-H-0010. The ONTC members include Bell Communications Research, Columbia University, NOIthern TelecomlBNR, Hughes, Rockwell Science Center, United Technologies Research Center and Lawrence Livermore National Laboratories.
Note: [] Correspondence author. The work was done while the author was at Columbia University. His new working address is: AT&T Bell Labs., 200 Laurel Ave., Room 3E-317, Middletown, NJ 07748, USA.
Abstract: In this paper, we present three logarithmically scalable routing algorithms for very large optical networks. The algorithms are based on a hierarchical approach. Each algorithm requires a different amount of information to be stored at each node, and results in a different efficiency. The network capacity provided by each algorithm is compared with that provided by the global shortest path algorithm (which is not scalable). It is found that the network capacities of the three algorithms are almost the same as that of the global shortest path algorithm. For fixed routing algorithms, we use an approximate analysis, appeared in the literature, from which the blocking probability at a fixed network load can iterately be obtained (we use call blocking probability as our quality objective and compare network capacity by observing the difference in the offered load which produces the same blocking probability). The approximate analysis is validated through simulation and is found to be very accurate. Scalable, quasi-dynamic routing algorithms are also studied. Numerical results show that, when the node-capacity is equal to the capacity of a single wavelength and the bandwidth required per call is large (greater than 24% of the link capacity), the capacity provided by the quasi-dynamic routing algorithm is very close to that of an infinite capacity centralized switch (lowest possible call blocking caused exclusively by congestion on the finite capacity user input/output links, never by the switch fabric itself). In all the examples considered, the improvement of the quasi-dynamic routing algorithm over the fixed routing algorithm is significant.
