| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capability
November 2004 (vol. 15 no. 11)
pp. 1012-1026
Abstract—Optical communication is a promising candidate for many emerging networking and parallel/distributed computing applications because of its huge bandwidth. Wavelength Division Multiplexing (WDM) is a technique that can better utilize the optical bandwidth by dividing the bandwidth of a fiber into multiple wavelength channels. In this paper, we study optimal scheduling algorithms to resolve output contentions in bufferless time slotted WDM optical interconnects with wavelength conversion ability. We consider the general case of limited range wavelength conversion with arbitrary conversion capability, as limited range wavelength conversion is easier to implement and more cost effective than full range wavelength conversion, and it also includes full range wavelength conversion as a special case. We first consider the conversion scheme in which each wavelength can be converted to multiple wavelengths in an interval of wavelengths and the intervals for different wavelengths are "ordered.” We show that the problem of maximizing network throughput can be formalized as finding a maximum matching in a bipartite graph. We then give an optimal scheduling algorithm called the First Available Algorithm that runs in O(k) time, where k is the number of wavelengths per fiber. We also study the case where the connection requests have different priorities. We formalize the problem as finding an optimal matching in a weighted bipartite graph and give a scheduling algorithm called the Downwards Expanding Algorithm that runs in O(kD+Nk\log(Nk)) time where N is the number of input fibers of the interconnect and D is the conversion degree. Finally, we consider the circular symmetrical wavelength conversion scheme and give optimal scheduling algorithms for nonprioritized scheduling in O(Dk) time and prioritized scheduling in O(k^2+Nk\log(Nk)) time.
[1] 1012 B. Mukherjee, “WDM Optical Communication Networks: Progress and Challenges,” IEEE J. Selected Areas in Comm., vol. 18, no. 10, pp. 1810-1824, 2000.[2] D.K. Hunter, M.C. Chia, and I. Andonovic, “Buffering in Optical Packet Switches,” J. Lightwave Technology, vol. 16 no. 12, pp. 2081-2094, 1998.[3] M. Kovacevic and A. Acampora, “Benefits of Wavelength Translation in All-Optical Clear-Channel Networks,” IEEE J. Selected Areas in Comm., vol. 14, no. 5, pp. 868-880, 1996.[4] S.L. Danielsen, C. Joergensen, B. Mikkelsen, and K.E. Stubkjaer, “Analysis of a WDM Packet Switch with Improved Performance under Bursty Traffic Conditions Due to Tunable Wavelength Converters,” J. Lightwave Technology, vol. 16, no. 5, pp. 729-735, 1998.[5] N. McKeown, P. Varaiya, and J. Warland, “Scheduling Cells in an Input-Queued Switch,” IEEE Electronics Letters, pp. 2174-2175, 1993.[6] N. McKeown, “The iSLIP Scheduling Algorithm Input-Queued Switch,” IEEE/ACM Trans. Networking, vol. 7, pp. 188-201, 1999.[7] H.J. Chao, C.H. Lam, and E. Oki, Broadband Packet Switching Technologies, first ed. Wiley-Interscience, 2001.[8] W.J. Goralski, Optical Networking and WDM, first ed. McGraw-Hill, 2001.[9] R. Ramaswami and K.N. Sivarajan, Optical Networks: A Practical Perspective, first ed. Academic Press, 2001.[10] T. Tripathi and K.N. Sivarajan, “Computing Approximate Blocking Probabilities in Wavelength Routed All-Optical Networks with Limited-Range Wavelength Conversion,” IEEE J. Selected Areas in Comm., vol. 18, pp. 2123-2129, 2000.[11] L. Xu, H.G. Perros, and G. Rouskas, “Techniques for Optical Packet Switching and Optical Burst Switching,” IEEE Comm. Magazine, pp. 136-142, 2001.[12] R. Ramaswami and G. Sasaki, “Multiwavelength Optical Networks with Limited Wavelength Conversion,” IEEE/ACM Trans. Networking, vol. 6, pp. 744-754, 1998.[13] X. Qin and Y. Yang, “Nonblocking WDM Switching Networks with Full and Limited Wavelength Conversion,” IEEE Trans. Comm., vol. 50, no. 12, pp. 2032-2041, 2002.[14] Y. Yang, J. Wang, and C. Qiao, “Nonblocking WDM Multicast Switching Networks,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 12, pp. 1274-1287, 2000.[15] M.S. Borella and B. Mukherjee, “Efficient Scheduling of Nonuniform Packet Traffic in a WDM/TDM Local Lightwave Network with Arbitrary Transceiver Tuning Latencies,” IEEE J. Selected Areas in Comm., vol. 14, no. 5, pp. 923-934, 1996.[16] G.N. Rouskas and V. Sivaraman, “Packet Scheduling in Broadcast WDM Networks with Arbitrary Transceiver Tuning Latencies,” IEEE/ACM Trans. Networking, vol. 14, no. 3, pp. 359-370, 1997.[17] Z. Zhang and Y. Yang, “Distributed Scheduling Algorithms for Wavelength Convertible WDM Optical Interconnects,” Proc. 17th IEEE Int'l Parallel and Distributed Processing Symp., 2003.[18] E.L. Lawler, Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.[19] J. Hopcroft and R. Karp, “An $n^{{5}\over{2}}$ Algorithm for Maximum Matchings in Bipartite Graph,” SIAM J. Computing, vol. 2, no. 4, pp. 225-231, 1973.[20] F. Glover, “Maximum Matching in Convex Bipartite Graph,” Naval Research Logistics Quarterly, vol. 14, pp. 313-316, 1967.[21] W. Lipski Jr. and F.P. Preparata, “Algorithms for Maximum Matchings in Bipartite Graphs,” Naval Research Logistics Quarterly, vol. 14, pp. 313-316, 1981.[22] E.L. Lawler, Introduction to Graph Theory. Holt, Rinehart and Winston, 1976.[23] G. Shen et al., “Performance Study on a WDM Packet Switch with Limited-Range Wavelength Converters,” IEEE Comm. Letters, vol. 5, no. 10, pp. 432-434, 2001.[24] H. Qin, S. Zhang, and Z Liu, “Dynamic Routing and Wavelength Assignment for Limited-Range Wavelength Conversion,” IEEE Comm. Letters, vol. 5, no. 3, pp. 136-138, 2003.[25] X. Masip-Bruin et al., “Routing and Wavelength Assignment under Inaccurate Routing Information in Networks with Sparse and Limited Wavelength Conversion,” Proc. IEEE GLOBECOM Conf. '03, vol. 5, pp. 2575-2579, 2003.
Index Terms:
Wavelength-division-multiplexing (WDM), optical interconnects, scheduling, wavelength conversion, limited range wavelength conversion, bipartite graphs, bipartite matching, matroid.
Citation:
Zhenghao Zhang, Yuanyuan Yang, "Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capability," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 11, pp. 1012-1026, Nov. 2004, doi:10.1109/TPDS.2004.68
