Abstract

We consider the scheduling problem in a new slotted optical network called TWIN. The TWIN architecture possesses interesting properties, which may offer solutions for next-generation optical networks. Besides, TWIN has the ability to support quality of service (QoS) by controlling two important parameters: queueing delay and delay variance. However, to the best of our knowledge, the existing scheduling algorithms in TWIN focused mainly on maximizing the throughput and ignored the consideration of QoS. We formulate the scheduling problem into an integer linear programming problem and propose a heuristic--virtual topology-based dynamic scheduling (VTBDS) algorithm to solve it fast and efficiently. Besides, we derive an analytical model for TWIN and investigate the performance of VTBDS in it. By means of simulations, we demonstrate that our model approximates the TWIN network very well, and VTBDS incurs smaller queueing delay and delay variance, which are advantageous for guaranteeing better QoS.

© 2007 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Chiu and E. Modiano, ''Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,'' J. Lightwave Technol. 18, 2-12 (2000).
    [CrossRef]
  2. S. Yao, S. Dixit, and B. Mukherjee, ''Advances in photonic packet switchings: an overview,'' IEEE Commun. Mag. 84-94 (2000).
  3. C. Qiao and M. Yoo, ''Optical burst switching (OBS)--a new paradigm for an optical Internet,'' J. High Speed Networks 8, 69-84 (1999).
  4. I. Widjaja, I. Saniee, R. Giles, and D. Mitra, ''Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network,'' IEEE Commun. Mag. 41, S30-S365 (2003).
  5. C. Nuzman and I. Widjaja, ''Time-domain wavelength interleaved networking with wavelength reuse,'' in Proceedings of IEEE INFOCOM (IEEE, 2006).
  6. K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).
  7. L. Zhang, ''Virtual clock: a new traffic control algorithm for packet switching networks,'' in Proceedings of ACM SIGCOMM (1990).
  8. A. K. Parekh and R. G. Gallager, ''A generalized processor sharing approach to flow control: the single node case,'' in Proceedings of IEEE INFOCOM (IEEE, 1992).
  9. J. C. R. Bennett and H. Zhang, ''WF2Q: worst-case fair weighted fair queueing,'' in Proceedings of IEEE INFOCOM (IEEE, 1996).
  10. N. McKeown, ''The iSLIP scheduling algorithm for input-queued switches,'' IEEE/ACM Trans. Netw. 7, 188-201 (1999).
  11. W. Wang, L. Dong, and W. Wolf, ''iSKIP: a fair and efficient scheduling algorithm for input-queued crossbar switches,'' in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (IEEE, 2002).
  12. K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).
  13. Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).
  14. D.-J. Xue, Y. Qin, and C. K. Siew, ''A slotted dynamic traffic scheduling algorithm in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2005).
  15. J. von Neumann, ''A certain zero-sum two-person game equivalent to the optimal assignment problem,'' Contrib. Theory Games 2, 147-151 (1946).
  16. B. Li and Y. Qin, ''Traffic scheduling in a photonic packet switching system with QoS guarantee,'' J. Lightwave Technol. 16, 2281-2295 (1998).
  17. L. Kleinrock, Queueing Systems, Volume I: Theory (Wiley, 1976), pp. 189-191.

2006 (1)

C. Nuzman and I. Widjaja, ''Time-domain wavelength interleaved networking with wavelength reuse,'' in Proceedings of IEEE INFOCOM (IEEE, 2006).

2005 (1)

D.-J. Xue, Y. Qin, and C. K. Siew, ''A slotted dynamic traffic scheduling algorithm in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2005).

2004 (1)

Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).

2003 (3)

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).

I. Widjaja, I. Saniee, R. Giles, and D. Mitra, ''Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network,'' IEEE Commun. Mag. 41, S30-S365 (2003).

2002 (1)

W. Wang, L. Dong, and W. Wolf, ''iSKIP: a fair and efficient scheduling algorithm for input-queued crossbar switches,'' in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (IEEE, 2002).

2000 (2)

A. Chiu and E. Modiano, ''Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,'' J. Lightwave Technol. 18, 2-12 (2000).
[CrossRef]

S. Yao, S. Dixit, and B. Mukherjee, ''Advances in photonic packet switchings: an overview,'' IEEE Commun. Mag. 84-94 (2000).

1999 (2)

C. Qiao and M. Yoo, ''Optical burst switching (OBS)--a new paradigm for an optical Internet,'' J. High Speed Networks 8, 69-84 (1999).

N. McKeown, ''The iSLIP scheduling algorithm for input-queued switches,'' IEEE/ACM Trans. Netw. 7, 188-201 (1999).

1998 (1)

1996 (1)

J. C. R. Bennett and H. Zhang, ''WF2Q: worst-case fair weighted fair queueing,'' in Proceedings of IEEE INFOCOM (IEEE, 1996).

1992 (1)

A. K. Parekh and R. G. Gallager, ''A generalized processor sharing approach to flow control: the single node case,'' in Proceedings of IEEE INFOCOM (IEEE, 1992).

1990 (1)

L. Zhang, ''Virtual clock: a new traffic control algorithm for packet switching networks,'' in Proceedings of ACM SIGCOMM (1990).

1976 (1)

L. Kleinrock, Queueing Systems, Volume I: Theory (Wiley, 1976), pp. 189-191.

1946 (1)

J. von Neumann, ''A certain zero-sum two-person game equivalent to the optimal assignment problem,'' Contrib. Theory Games 2, 147-151 (1946).

Bambos, N.

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).

Bennett, J. C. R.

J. C. R. Bennett and H. Zhang, ''WF2Q: worst-case fair weighted fair queueing,'' in Proceedings of IEEE INFOCOM (IEEE, 1996).

Chiu, A.

Dixit, S.

S. Yao, S. Dixit, and B. Mukherjee, ''Advances in photonic packet switchings: an overview,'' IEEE Commun. Mag. 84-94 (2000).

Dong, L.

W. Wang, L. Dong, and W. Wolf, ''iSKIP: a fair and efficient scheduling algorithm for input-queued crossbar switches,'' in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (IEEE, 2002).

Gallager, R. G.

A. K. Parekh and R. G. Gallager, ''A generalized processor sharing approach to flow control: the single node case,'' in Proceedings of IEEE INFOCOM (IEEE, 1992).

Giles, R.

I. Widjaja, I. Saniee, R. Giles, and D. Mitra, ''Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network,'' IEEE Commun. Mag. 41, S30-S365 (2003).

Kleinrock, L.

L. Kleinrock, Queueing Systems, Volume I: Theory (Wiley, 1976), pp. 189-191.

Kumaran, K.

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).

Li, B.

McKeown, N.

N. McKeown, ''The iSLIP scheduling algorithm for input-queued switches,'' IEEE/ACM Trans. Netw. 7, 188-201 (1999).

Mitra, D.

I. Widjaja, I. Saniee, R. Giles, and D. Mitra, ''Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network,'' IEEE Commun. Mag. 41, S30-S365 (2003).

Modiano, E.

Mukherjee, B.

S. Yao, S. Dixit, and B. Mukherjee, ''Advances in photonic packet switchings: an overview,'' IEEE Commun. Mag. 84-94 (2000).

Nuzman, C.

C. Nuzman and I. Widjaja, ''Time-domain wavelength interleaved networking with wavelength reuse,'' in Proceedings of IEEE INFOCOM (IEEE, 2006).

Parekh, A. K.

A. K. Parekh and R. G. Gallager, ''A generalized processor sharing approach to flow control: the single node case,'' in Proceedings of IEEE INFOCOM (IEEE, 1992).

Qiao, C.

C. Qiao and M. Yoo, ''Optical burst switching (OBS)--a new paradigm for an optical Internet,'' J. High Speed Networks 8, 69-84 (1999).

Qin, Y.

D.-J. Xue, Y. Qin, and C. K. Siew, ''A slotted dynamic traffic scheduling algorithm in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2005).

Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).

B. Li and Y. Qin, ''Traffic scheduling in a photonic packet switching system with QoS guarantee,'' J. Lightwave Technol. 16, 2281-2295 (1998).

Ross, K.

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).

Saniee, I.

Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).

I. Widjaja, I. Saniee, R. Giles, and D. Mitra, ''Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network,'' IEEE Commun. Mag. 41, S30-S365 (2003).

Siew, C. K.

D.-J. Xue, Y. Qin, and C. K. Siew, ''A slotted dynamic traffic scheduling algorithm in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2005).

Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).

von Neumann, J.

J. von Neumann, ''A certain zero-sum two-person game equivalent to the optimal assignment problem,'' Contrib. Theory Games 2, 147-151 (1946).

Wang, W.

W. Wang, L. Dong, and W. Wolf, ''iSKIP: a fair and efficient scheduling algorithm for input-queued crossbar switches,'' in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (IEEE, 2002).

Widjaja, I.

C. Nuzman and I. Widjaja, ''Time-domain wavelength interleaved networking with wavelength reuse,'' in Proceedings of IEEE INFOCOM (IEEE, 2006).

Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).

I. Widjaja, I. Saniee, R. Giles, and D. Mitra, ''Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network,'' IEEE Commun. Mag. 41, S30-S365 (2003).

Wolf, W.

W. Wang, L. Dong, and W. Wolf, ''iSKIP: a fair and efficient scheduling algorithm for input-queued crossbar switches,'' in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (IEEE, 2002).

Xue, D.-J.

D.-J. Xue, Y. Qin, and C. K. Siew, ''A slotted dynamic traffic scheduling algorithm in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2005).

Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).

Yao, S.

S. Yao, S. Dixit, and B. Mukherjee, ''Advances in photonic packet switchings: an overview,'' IEEE Commun. Mag. 84-94 (2000).

Yoo, M.

C. Qiao and M. Yoo, ''Optical burst switching (OBS)--a new paradigm for an optical Internet,'' J. High Speed Networks 8, 69-84 (1999).

Zhang, H.

J. C. R. Bennett and H. Zhang, ''WF2Q: worst-case fair weighted fair queueing,'' in Proceedings of IEEE INFOCOM (IEEE, 1996).

Zhang, L.

L. Zhang, ''Virtual clock: a new traffic control algorithm for packet switching networks,'' in Proceedings of ACM SIGCOMM (1990).

Contrib. Theory Games (1)

J. von Neumann, ''A certain zero-sum two-person game equivalent to the optimal assignment problem,'' Contrib. Theory Games 2, 147-151 (1946).

IEEE Commun. Mag. (2)

S. Yao, S. Dixit, and B. Mukherjee, ''Advances in photonic packet switchings: an overview,'' IEEE Commun. Mag. 84-94 (2000).

I. Widjaja, I. Saniee, R. Giles, and D. Mitra, ''Light core and intelligent edge for a flexible, thin-layered and cost-effective optical transport network,'' IEEE Commun. Mag. 41, S30-S365 (2003).

IEEE J. Sel. Areas Commun. (1)

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Scheduling bursts in time-domain wavelength interleaved networks,'' IEEE J. Sel. Areas Commun. 21, 1441-1451 (2003).

IEEE/ACM Trans. Netw. (1)

N. McKeown, ''The iSLIP scheduling algorithm for input-queued switches,'' IEEE/ACM Trans. Netw. 7, 188-201 (1999).

J. High Speed Networks (1)

C. Qiao and M. Yoo, ''Optical burst switching (OBS)--a new paradigm for an optical Internet,'' J. High Speed Networks 8, 69-84 (1999).

J. Lightwave Technol. (2)

Other (9)

L. Kleinrock, Queueing Systems, Volume I: Theory (Wiley, 1976), pp. 189-191.

W. Wang, L. Dong, and W. Wolf, ''iSKIP: a fair and efficient scheduling algorithm for input-queued crossbar switches,'' in Proceedings of IEEE Global Telecommunications Conference (GLOBECOM) (IEEE, 2002).

K. Ross, N. Bambos, K. Kumaran, I. Saniee, and I. Widjaja, ''Dynamic scheduling of optical data bursts in time-domain wavelength interleaved networks,'' in Proceedings of IEEE Symposium on Hot Interconnects (HOTI 2003) (IEEE, 2003).

Y. Qin, D.-J. Xue, C. K. Siew, I. Saniee, and I. Widjaja, ''A topology based dynamic traffic scheduling in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2004).

D.-J. Xue, Y. Qin, and C. K. Siew, ''A slotted dynamic traffic scheduling algorithm in time-domain wavelength interleaved networks,'' in Proceedings of IEEE International Conference on Networks (ICON) (IEEE, 2005).

C. Nuzman and I. Widjaja, ''Time-domain wavelength interleaved networking with wavelength reuse,'' in Proceedings of IEEE INFOCOM (IEEE, 2006).

L. Zhang, ''Virtual clock: a new traffic control algorithm for packet switching networks,'' in Proceedings of ACM SIGCOMM (1990).

A. K. Parekh and R. G. Gallager, ''A generalized processor sharing approach to flow control: the single node case,'' in Proceedings of IEEE INFOCOM (IEEE, 1992).

J. C. R. Bennett and H. Zhang, ''WF2Q: worst-case fair weighted fair queueing,'' in Proceedings of IEEE INFOCOM (IEEE, 1996).

Cited By

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

Alert me when this article is cited.