Optimal packet scheduling in output-buffered optical switches with limited-range wavelength conversion

ABSTRACT

All-optical packet switching is a promising candidate for future high-speed switching. However, due to the absence of optical Ran-dom Access Memory, the traditional Virtual Output Queue (VOQ) based input-queued switches are difficult to implement in optical domain. In this paper we consider output-buffered optical packet switches. We focus on packet scheduling in an output-buffered optical packet switch with limited-range wavelength conversion, aiming at maximizing throughput and minimizing average queuing delay simultaneously. We show that it can be converted to a minimum cost maximum network flow problem. To cope with the high complexity of general network flow algorithms, we further present a new algorithm that can determine an optimal scheduling in O (min {W²,BW}) time, where W is the number of wave-length channels in each fiber and B is the length of the output buffer. We also conduct simulations to test the performance of the proposed scheduling algorithm under different traffic models.

REFERENCES

• 1: L. Xu, H.G. Perros and G. Rouskas, "Techniques for optical packet switching and optical burst switching," IEEE Communications Magazine, pp. 136--142, Jan. 2001.
• 2: T. Tripathi and K. N. Sivarajan, "Computing approximate blocking probabilities in wavelength routed all-optical networks with limited-range wavelength conversion," IEEE Journal of Selected Areas in Comm., vol. 18, pp. 2123--2129, 2000.
• 3: X. Qin and Y. Yang, "Nonblocking WDM switching networks with full and limited wavelength conversion," IEEE Trans. Communications, vol. 50, no. 12, pp. 2032--2041, 2002.
• 4: Yuanyuan Yang , Jianchao Wang, Designing WDM Optical Interconnects with Full Connectivity by Using Limited Wavelength Conversion, IEEE Transactions on Computers, v.53 n.12, p.1547-1556, December 2004 [doi>10.1109/TC.2004.113]
• 5: S. Daniesen, C. Joergensen, B. Mikkelsen and K. Stubkjaer, "Analysis of a WDM packet switch with improved performance under bursty traffic conditions due to tunable wavelength converters," Journal of Lightwave Technology, vol. 16, pp. 729--735, May 1998.
• 6: H. Yang and S. J. B. Yoo, "All-optical variable buffering strategies and switch fabric architectures for future all-optical data routers," Journal of Lightwave Technology, vol. 23, pp. 3321--3330, Oct. 2005.
• 7: W. D. Zhong and R. S. Tucker, "A new wavelength-routed photonic packet buffer combining traveling delay lines with delay-line loops," Journal of Lightwave Technology, vol. 19, No. 8, Aug. 2001.
• 8: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 9: L. Li, S. D. Scott and J. S. Deogun, "A novel fiber delay line buffering architecture for optical packet switching," Proc. GLOBECOM 2003, vol. 5, pp. 2809--2813, 2003.
• 10: P. C. Ku, P. Palinginis, T. Li, F. Sedgwick, S. Chang, H. Wang, C. Chang-Hasnain and S.L. Chuang, "Variable optical buffer using slow light in semiconductor nanostructures," Proceedings of the IEEE, vol. 91, pp. 1884--1897, Nov. 2003.
• 11: L. Wosinska, J. Haralson, L. Thylen, J. Oberg and B. Hessmo,"Benefit of implementing novel optical buffers in an asynchronous photonic packet switch," Eur. Conf. Optical Communications (ECOC), Stockholm, Sweden, 2004.
• 12: R. S. Tucker, P.-C Ku and C. J. Chang-Hasnain, "Fundamental limitations of slow-light optical buffers," Optical Fiber Communication Conference, 2005. Technical Digest. OFC/NFOEC, vol. 3, Mar. 2005.
• 13: Zhenghao Zhang , Yuanyuan Yang, Optimal Scheduling Algorithms in WDM Optical Interconnects with Limited Range Wavelength Conversion Capability, IEEE Transactions on Parallel and Distributed Systems, v.15 n.11, p.1012-1026, November 2004 [doi>10.1109/TPDS.2004.68]
• 14: Zhenghao Zhang , Yuanyuan Yang, Optimal Scheduling in Buffered WDM Interconnects with Limited Range Wavelength Conversion Capability, IEEE Transactions on Computers, v.55 n.1, p.71-82, January 2006 [doi>10.1109/TC.2006.14]
• 15: S. Danielsen, B. Mikkelsen, C. Joergensen, T. Durhuus, and K. Stubkjaer, "WDM packet switch architecture and analysis of the influence of tuneable wavelength converters on the performance," Journal of Lightwave Technology, vol. 15, pp. 219--227, Feb. 1997.
• 16: Nick McKeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking (TON), v.7 n.2, p.188-201, April 1999 [doi>10.1109/90.769767]
• 17: A. Bianco, M. Franceschinis, S. Ghisolfi, A. M. Hill, E. Leonardi, F. Neri and R. Webb, "Frame-based matching algorithms for input-queued switches," High Performance Switching and Routing, 2002. Merging Optical and IP Technologies. Workshop on, pp. 69--76, 2002.
• 18: P. Pappu, J. Parwatikar, J. Turner and K. Wong, "Distributed queueing in scalable high performance routers," INFOCOM 2003, vol. 3, pp. 1633--1642, Apr. 2003.
• 19: T. Hou and A. Wong, "Queueing analysis for ATM switching of mixed continuous-bit-rate and bursty traffic," Proc. INFOCOM'90, pp. 660--667.
• 20: Mark W. Garrett , Walter Willinger, Analysis, modeling and generation of self-similar VBR video traffic, Proceedings of the conference on Communications architectures, protocols and applications, p.269-280, August 31-September 02, 1994, London, United Kingdom

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Packet-switching networks

General Terms:
Algorithms, Design

Keywords:
WDM optical switches, minimum cost maximum flow, output-queued (OQ), packet scheduling, wavelength conversion