OSA's Digital Library

Journal of Lightwave Technology

Journal of Lightwave Technology


  • Vol. 29, Iss. 9 — May. 1, 2011
  • pp: 1227–1238

Optimal Packet Scheduling in WDM Optical Switches With Output Buffer and Limited Wavelength Conversion

Lin Liu and Yuanyuan Yang

Journal of Lightwave Technology, Vol. 29, Issue 9, pp. 1227-1238 (2011)

View Full Text Article

Acrobat PDF (740 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

  • Export Citation/Save Click for help


All-optical packet switching is a promising candidate for future high-speed switching. However, due to the absence of optical random access memory, the traditional Virtual Output Queue (VOQ) based input-queued switches are difficult to implement in the 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 this problem can be converted to a minimum cost maximum network flow problem. To cope with the high complexity of general network flow algorithms, we present an algorithm that can efficiently find an optimal schedule in $O(\min\{NW,BW\})$ time, where $N$ is the switch size, $W$ is the number of wavelength channels per fiber and $B$ is the length of the longest FDL at the output of the switch. The complexity of the new algorithm asymptotically matches the lower bound of the scheduling problem. We also conduct extensive simulations to test the performance of the proposed scheduling algorithm under different traffic models.

© 2011 IEEE

Lin Liu and Yuanyuan Yang, "Optimal Packet Scheduling in WDM Optical Switches With Output Buffer and Limited Wavelength Conversion," J. Lightwave Technol. 29, 1227-1238 (2011)

Sort:  Year  |  Journal  |  Reset


  1. D. Staessens, D. Colle, U. Lievens, M. Pickavet, P. Demeester, W. Colitti, A. Nowe, K. Steenhaut, R. Romeral, "Enabling high availability over multiple optical networks," IEEE Commun. Mag. 120-126 (2008).
  2. Z. Zhang, Y. Yang, "Performance analysis of optical packet switches enhanced with electronic buffering," Proc. 23th IEEE Int. Parallel Distrib. Process. Symp. (2009).
  3. H. Ngo, D. Pan, Y. Yang, "Optical switching networks with minimum number of limited range wavelength converters," IEEE/ACM Trans. Netw. 15, 969-979 (2007).
  4. L. Liu, Z. Zhang, Y. Yang, "Packet scheduling in a low latency optical packet switch," Proc. IEEE Int. Conf. High Performance Switching and Routing (2010) pp. 146-151.
  5. I. Iliadis, C. Minkenberg, "Performance of a speculative transmission scheme for scheduling-latency reduction," IEEE/ACM Trans. Netw. 16, 182-195 (2008).
  6. S. Shimizu, Y. Arakawa, N. Yamanaka, "Wavelength assignment scheme for WDM networks with limited-range wavelength converters," J. Opt. Netw. 5, 410-421 (2006).
  7. T. Tripathi, K. N. Sivarajan, "Computing approximate blocking probabilities in wavelength routed all-optical networks with limited-range wavelength conversion," IEEE J. Sel. Areas Commun. 18, 2123-2129 (2000).
  8. X. Qin, Y. Yang, "Nonblocking WDM switching networks with full and limited wavelength conversion," IEEE Trans. Commun. 50, 2032-2041 (2002).
  9. Y. Yang, J. Wang, "Designing WDM optical interconnects with full connectivity by using limited wavelength conversion," IEEE Trans. Comput. 53, 1547-1556 (2004).
  10. H. Yang, S. J. B. Yoo, "All-optical variable buffering strategies and switch fabric architectures for future all-optical data routers," J. Lightw. Technol. 23, 3321-3330 (2005).
  11. W. D. Zhong, R. S. Tucker, "A new wavelength-routed photonic packet buffer combining traveling delay lines with delay-line loops," J. Lightw. Technol. 19, (2001).
  12. R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).
  13. R. S. Tucker, P.-C. Ku, C. J. Chang-Hasnain, "Slow-light optical buffers: Capabilities and fundamental limitations," J. Lightw. Technol. 23, 4046-4066 (2005).
  14. Z. Zhang, Y. Yang, "Optimal scheduling in WDM optical interconnects with arbitrary wavelength conversion capability," IEEE Trans. Parallel Distrib. Syst. 15, 1012-1026 (2004).
  15. Z. Zhang, Y. Yang, "Optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability," IEEE Trans. Comput. 55, 71-82 (2006).
  16. T. Hou, A. Wong, "Queueing analysis for ATM switching of mixed continuous-bit-rate and bursty traffic," Proc. IEEE INFOCOM pp. 660-667.
  17. Y. Okawachi, M. S. Bigelow, J. E. Sharping, Z. Zhu, A. Schweinsberg, D. J. Gauthier, R. W. Boyd, A. L. Gaeta, "Tunable all-optical delays via Brillouin slow light in an optical fiber," Phys. Rev. Lett. 94, (2005) Art. ID 153902.
  18. R. M. Camacho, C. J. Broadbent, I. Ali-Khan, J. C. Howell, "All-optical delay of images using slow light," Phys. Rev. Lett. 98, (2007) Art. ID 043902.
  19. A. D. Sarwate, V. Anantharam, "Exact emulation of a priority queue with a switch and delay lines," Queueing Syst.: Theory Appl. 53, 115-125 (2006).
  20. H.-C. Chiu, C.-S. Chang, J. Cheng, D.-S. Lee, "Using a single switch with $O(M)$ inputs/outputs for the construction of an optical priority queue with $O(M_3)$ buffer," Proc. IEEE INFOCOM (2007) pp. 2501-2505.
  21. C.-S. Chang, Y.-T. Chen, D.-S. Lee, "Constructions of optical FIFO queues," IEEE/ACM Trans. Netw. 14, 2838-2843 (2006).
  22. M. Karol, M. Hluchyj, S. Morgan, "Input versus output queueing on a space-division packet switch," IEEE Trans. Commun. 35, 1347-1356 (1987).
  23. A. Detti, G. Parca, V. Carrozzo, S. Betti, "Optical packet network with limited-range wavelength conversion: A novel formalization of the optimal scheduling problem," J. Lightw. Technol. 27, 5607-5618 (2009).
  24. V. Eramo, M. Listanti, A. Germoni, "Cost evaluation of optical packet switches equipped with limited-range and full-range converters for contention resolution," J. Lightw. Technol. 26, 390-407 (2008).
  25. N. Kitsuwan, R. Rojas-Cessa, M. Matsuura, E. Oki, "Performance of optical packet switches based on parametric wavelength converters," IEEE/OSA Opt. Commun. Netw. 2, 558-569 (2010).
  26. B.-C. Lin, C.-T. Lea, D. Tsang, J. Xu, "Reducing wavelength conversion range in space/wavelength switches," IEEE Photon. Technol. Lett. 20, 1458-1460 (2008).

Cited By

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited