Abstract

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

PDF Article

References

  • View by:
  • |
  • |

  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).

2010 (1)

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).

2009 (1)

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).

2008 (4)

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).

I. Iliadis, C. Minkenberg, "Performance of a speculative transmission scheme for scheduling-latency reduction," IEEE/ACM Trans. Netw. 16, 182-195 (2008).

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).

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).

2007 (2)

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).

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.

2006 (4)

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).

C.-S. Chang, Y.-T. Chen, D.-S. Lee, "Constructions of optical FIFO queues," IEEE/ACM Trans. Netw. 14, 2838-2843 (2006).

Z. Zhang, Y. Yang, "Optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability," IEEE Trans. Comput. 55, 71-82 (2006).

S. Shimizu, Y. Arakawa, N. Yamanaka, "Wavelength assignment scheme for WDM networks with limited-range wavelength converters," J. Opt. Netw. 5, 410-421 (2006).

2005 (3)

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.

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).

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).

2004 (2)

Z. Zhang, Y. Yang, "Optimal scheduling in WDM optical interconnects with arbitrary wavelength conversion capability," IEEE Trans. Parallel Distrib. Syst. 15, 1012-1026 (2004).

Y. Yang, J. Wang, "Designing WDM optical interconnects with full connectivity by using limited wavelength conversion," IEEE Trans. Comput. 53, 1547-1556 (2004).

2002 (1)

X. Qin, Y. Yang, "Nonblocking WDM switching networks with full and limited wavelength conversion," IEEE Trans. Commun. 50, 2032-2041 (2002).

2001 (1)

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).

2000 (1)

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).

1987 (1)

M. Karol, M. Hluchyj, S. Morgan, "Input versus output queueing on a space-division packet switch," IEEE Trans. Commun. 35, 1347-1356 (1987).

IEEE Trans. Comput. (1)

Z. Zhang, Y. Yang, "Optimal scheduling in buffered WDM interconnects with limited range wavelength conversion capability," IEEE Trans. Comput. 55, 71-82 (2006).

IEEE Trans. Parallel Distrib. Syst. (1)

Z. Zhang, Y. Yang, "Optimal scheduling in WDM optical interconnects with arbitrary wavelength conversion capability," IEEE Trans. Parallel Distrib. Syst. 15, 1012-1026 (2004).

IEEE Commun. Mag. (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).

IEEE J. Sel. Areas Commun. (1)

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).

IEEE Photon. Technol. Lett. (1)

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).

IEEE Trans. Commun. (1)

M. Karol, M. Hluchyj, S. Morgan, "Input versus output queueing on a space-division packet switch," IEEE Trans. Commun. 35, 1347-1356 (1987).

IEEE Trans. Commun. (1)

X. Qin, Y. Yang, "Nonblocking WDM switching networks with full and limited wavelength conversion," IEEE Trans. Commun. 50, 2032-2041 (2002).

IEEE Trans. Comput. (1)

Y. Yang, J. Wang, "Designing WDM optical interconnects with full connectivity by using limited wavelength conversion," IEEE Trans. Comput. 53, 1547-1556 (2004).

IEEE/ACM Trans. Netw. (1)

I. Iliadis, C. Minkenberg, "Performance of a speculative transmission scheme for scheduling-latency reduction," IEEE/ACM Trans. Netw. 16, 182-195 (2008).

IEEE/ACM Trans. Netw. (1)

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).

IEEE/ACM Trans. Netw. (1)

C.-S. Chang, Y.-T. Chen, D.-S. Lee, "Constructions of optical FIFO queues," IEEE/ACM Trans. Netw. 14, 2838-2843 (2006).

IEEE/OSA Opt. Commun. Netw. (1)

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).

J. Lightw. Technol. (5)

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).

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).

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).

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).

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).

J. Opt. Netw. (1)

Phys. Rev. Lett. (1)

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.

Phys. Rev. Lett. (1)

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.

Queueing Syst.: Theory Appl. (1)

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).

Other (5)

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.

T. Hou, A. Wong, "Queueing analysis for ATM switching of mixed continuous-bit-rate and bursty traffic," Proc. IEEE INFOCOM pp. 660-667.

R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).

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.

Z. Zhang, Y. Yang, "Performance analysis of optical packet switches enhanced with electronic buffering," Proc. 23th IEEE Int. Parallel Distrib. Process. Symp. (2009).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.