| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
WDM Optical Interconnects with Recirculating Buffering and Limited Range Wavelength Conversion
May 2006 (vol. 17 no. 5)
pp. 466-480
Abstract—All-optical communication, in particular, wavelength-division-multiplexing (WDM) technique, has been proposed as a promising candidate to meet the ever-increasing demands on bandwidth from emerging bandwidth-intensive computing/networking applications. However, with current technology, the cost of optical communication, especially the cost of optical buffering and wavelength conversion, remains a major concern for such applications. In this paper, we study WDM optical interconnects that utilize low cost recirculating buffering and limited range wavelength conversion. We first consider the packet scheduling problem in this type of interconnect, and formalize the problem of maximizing throughput and minimizing packet delay as a matching problem in a bipartite graph. We give an optimal parallel algorithm for this problem that runs in O(Bk^2) time, compared to O((N+B)^3k^3) time if directly applied to existing matching algorithms for general bipartite graphs, where N is the number of input/output fibers of the interconnect, B is the number of fiber delay lines, and k is the number of wavelengths. We also consider efficient switching fabric designs for this type of interconnect. We distinguish between the switching fabric connecting the input fibers to the output fibers and the switching fabric connecting the input fibers to the delay lines and show that by adopting the idea of concentration, the cost of the latter can be reduced significantly in terms of the number of crosspoints.
[1] 466 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 et al., “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] 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.[6] 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.[7] R. Ramaswami and K.N. Sivarajan, Optical Networks: A Practical Perspective. Morgan Kaufmann, 1998.[8] L. Xu, H.G. Perros, and G. Rouskas, “Techniques for Optical Packet Switching and Optical Burst Switching,” IEEE Comm. Magazine, pp. 136-142, 2001.[9] R. Ramaswami and G. Sasaki, “Multiwavelength Optical Networks with Limited Wavelength Conversion,” IEEE/ACM Trans. Networking, vol. 6, pp. 744-754, 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, 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] S.L. Danielsen et al., “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, 1998.[13] S. Nakamura and G.M. Masson, “Lower Bounds on Crosspoint in Concentrators,” IEEE Trans. Computers, pp. 1173-1178, 1982.[14] A. YavuzOruc and H.M. Huang, “Crosspoint Complexity of Sparse Crossbar Concentrators,” IEEE Trans. Information Theory, pp. 1466-1471, 1996.[15] N. McKeown, “The iSLIP Scheduling Algorithm Input-Queued Switch,” IEEE/ACM Trans. Networking, vol. 7, pp. 188-201, 1999.[16] M. Karpinski and W. Rytter, Fast Parallel Algorithms for Graph Matching Problems. Oxford Univ. Press, 1998.[17] V. Eramo, M. Listanti, and M. DiDonato, “Performance Evaluation of a Bufferless Optical Packet Switch with Limited-Range Wavelength Converters,” IEEE Photonics Technology Letters, vol. 16, no. 2, pp. 644-646, 2004.[18] Z. Zhang and Y. Yang, “Scheduling in Buffered WDM Packet Switching Networks with Arbitrary Wavelength Conversion Capability,” Proc. IEEE INFOCOM Conf., 2004.[19] W.J. Goralski, Optical Networking and WDM, first ed. McGraw-Hill, 2001.[20] 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.[21] 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., vol. 5, pp. 2575-2579, 2003.[22] E.L. Lawler, Combinatorial Optimization: Networks and Matroids. Holt, Rinehart, and Winston, 1976.[23] W. LipskiJr and F.P. Preparata, “Algorithms for Maximum Matchings in Bipartite Graphs,” Naval Research Logistics Quarterly, vol. 14, pp. 313-316, 1981.[24] D.K. Hunter and I. Andronovic, “Approaches to Optical Internet Packet Switching,” IEEE Comm. Magazine, vol. 38, no. 9, pp. 116-122, 2000.[25] C. Develder, M. Pickavet, and P. Demeester, “Assessment of Packet Loss for an Optical Packet Router with Recirculating Buffer,” Proc. Conf. Optical Network Design and Modeling, pp. 247-261, 2002.[26] Z. Zhang and Y. Yang, “A New Switching Fabric Design for WDM Packet Switching Networks with Wavelength Conversion and Recirculating Buffering,” Proc. IEEE Int'l Conf. Comm., 2004.[27] 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.[28] D.B. West, Introduction to Graph Theory. Prentice-Hall, 1996.
Index Terms:
Wavelength-division-multiplexing (WDM), optical interconnects, optical packet switching, recirculating buffers, limited range wavelength conversion, concentrators, parallel algorithms, scheduling, matching, bipartite graphs.
Citation:
Zhenghao Zhang, Yuanyuan Yang, "WDM Optical Interconnects with Recirculating Buffering and Limited Range Wavelength Conversion," IEEE Transactions on Parallel and Distributed Systems, vol. 17, no. 5, pp. 466-480, May 2006, doi:10.1109/TPDS.2006.67
Usage of this product signifies your acceptance of the
Terms of Use.
|
|
|
|
|
|
|
|
