| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Optimal Scheduling in Buffered WDM Interconnects with Limited Range Wavelength Conversion Capability
January 2006 (vol. 55 no. 1)
pp. 71-82
All optical networking is a promising candidate for supporting high-speed communications because of the huge bandwidth of optics. In this paper, we study optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability. We formalize the problem of maximizing network throughput and minimizing total delay as a problem of finding an optimal matching in a weighted bipartite graph. We then give a simple algorithm, called the Scan and Swap Algorithm, that finds the optimal matching in O(kB) time, where k is the number of wavelengths per fiber and B is the buffer length, as compared to directly adopting other existing algorithms that need at least O(k^{2} N^{2}+k^{2}BN) time, where N is the number of input fibers.
[1] 71 B. Mukherjee, “WDM Optical Communication Networks: Progress and Challenges,” IEEE J. Selected Areas in Comm., vol. 18, no. 10, pp. 1810-1824, Oct. 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, June 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 Tuneable Wavelength Converters,” J. Lightwave Technology, vol. 16, no. 5, pp. 729-735, May 1998.[5] T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms. The MIT Press, 1990.[6] 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, Oct. 2000.[7] G. Shen, S.K Bose, T.H. Cheng, C. Lu, and T.Y. Chai, “Performance Study on a WDM Packet Switch with Limited-Range Wavelength Converters,” IEEE Comm. Letters, vol. 5, no. 10, pp. 432-434, Oct. 2001.[8] L. Xu, H.G. Perros, and G. Rouskas, “Techniques for Optical Packet Switching and Optical Burst Switching,” IEEE Comm. Magazine, pp. 136-142, Jan. 2001.[9] R. Ramaswami and G. Sasaki, “Multiwavelength Optical Networks with Limited Wavelength Conversion,” IEEE/ACM Trans. Networking, vol. 6, pp. 744-754, Dec. 1998.[10] 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, Dec. 2002.[11] 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, Dec. 2000.[12] Z. Zhang and Y. Yang, “Optimal Scheduling in WDM Optical Interconnects with Arbitrary Wavelength Conversion Capability,” IEEE Trans. Parallel and Distributed Systems, vol. 15, no. 11, pp. 1012-1026, Nov. 2004.[13] S.L. Danielsen, B. Mikkelsen, C. Joergensen, T. Durhuus, and K.E. Stubkjaer, “WDM Packet Switch Architectures and Analysis of the Influence of Tunable Wavelength Converters on the Performance,” J. Lightwave Technology, vol. 15, no. 2, pp. 219-227, Feb. 1998.[14] N. McKeown, P. Varaiya, and J. Warland, “Scheduling Cells in an Input-Queued Switch,” IEEE Electronic Letters, pp. 2174-2175, Dec. 1993.[15] N. McKeown, “The iSLIP Scheduling Algorithm Input-Queued Switch,” IEEE/ACM Trans. Networking, vol. 7, pp. 188-201, Apr. 1999.[16] 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, Mar. 2003.[17] X. Masip-Bruin, S. Sanchez-Lopez, J. Sole-Pareta, J. Domingo-Pascual, and D. Colle, “Routing and Wavelength Assignment under Inaccurate Routing Information in Networks with Sparse and Limited Wavelength Conversion,” Proc. IEEE 2003 Global Telecomm. Conf. (IEEE GLOBECOM '03), vol. 5, pp. 2575-2579, Dec. 2003.[18] R. Ramaswami and K.N. Sivarajan, Optical Networks: A Practical Perspective, first ed. Academic Press, 2001.[19] E.L. Lawler, Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976.[20] D.B. West, Introduction to Graph Theory. Prentice Hall, 1996.[21] 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, Dec. 1973.[22] F. Glover, “Maximum Matching in Convex Bipartite Graph,” Naval Research Logistics Quarterly, vol. 14, pp. 313-316, 1967.[23] W. Lipski Jr. and F.P. Preparata, “Algorithms for Maximum Matchings in Bipartite Graphs,” Naval Research Logistics Quarterly, vol. 14, pp. 313-316, 1981.
Index Terms:
Index Terms- Wavelength-division-multiplexing (WDM), packet scheduling, wavelength conversion, limited range wavelength conversion, optical packet switching, optical interconnects, optical switching networks, optical buffering, packet loss probability.
Citation:
Zhenghao Zhang, Yuanyuan Yang, "Optimal Scheduling in Buffered WDM Interconnects with Limited Range Wavelength Conversion Capability," IEEE Transactions on Computers, vol. 55, no. 1, pp. 71-82, Jan. 2006, doi:10.1109/TC.2006.14
