Abstract

We consider an optical slotted ring network. We distinguish two quality-of-service packet models. In the first, each subpacket of a same packet can be routed independently, and in the second, each subpacket has to be routed in consecutive slots (no jitter). We evaluate performances in terms of jitter and delay of routed packets. First, we study the algorithmic complexity of minimizing delay in the second model and show it is NP incomplete. Then, we propose distributed and online algorithms for the two models. Finally, we compare these algorithms using an OMnet++ simulator.

© 2006 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
    [CrossRef]
  2. International Telecommunications Union, 'Convergence between internet and optical networks,' ITU News Mag. , October 2003, www.itu.int/itunews.
  3. N. Chandhok, A. Durresi, R. Jagannathan, and R. Jain, 'IP over optical networks: summary of issues,' www.cs.wustl.edu/rjain/ietf/issues.htm (2000).
  4. D. Barth, J. Cohen, P. Fragopoulou, and G. Hébuterne, 'Wavelengths assignment on a ring all-optical metropolitan area network,' presented at the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, Rome, Italy, 21 September 2002.
  5. A. Bianco, M. Bonsignori, E. Leonardi, and F. Neri, 'Variable-size packets in slotted WDM ring networks' presented at the 6th IFIP Working Conference on Design and Modelling, Torino, Italy, 4-6 February 2002.
  6. A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.
  7. X. Yu, Y. Chen, and C. Qiao, 'A study of traffic statistics of assembled burst traffic in optical burst switched networks,' www.cse.buffalo.edu/ qiao/wobs/ obs/papers/Yulowbaropti02.pdf 2003.
  8. S. Yao, B. Mukherjee, S. J. Ben Yoo, and S. Dixit, 'All-optical packet-switched networks: a study of contention-resolution schemes in irregular mesh network with variable packet size,' Proc. SPIE 4233, 235-246 (2000).
  9. Yao, S. J. Ben Yoo, and B. Mukerjee, 'A comparison study between slotted and unslotted all-optical packet-switched network with priority-based routing,' networks.cs.ucdavis.edu/ syao/ofc01.pdf (2002).
  10. P. Brucker, Scheduling Algorithms (Springer-Verlag, 2001).
  11. M. Pinedo, Scheduling: Theory, Algorithms, and System (Prentice-Hall, 2002).
  12. H. Amet, J. Cohen, F. Deppner, M.-C. Portmann, and S. Rousseau, 'Un probleme d'ordonnancement de messages: Partie 1 modélisations; partie 2 approches de résolution,' presented at the 6th Congress of the French Society of Operations Research and Decision-Making Analysis, Tours, France, 14-16 February 2005.
  13. M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).
  14. European project of the 5th PCRD. Data and voice integration over DWDM (david).
  15. D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau, 'A comparison of splittable and non-splittable packet models in an optical ring network,' Res. Rep.2005/83 (Universite Versailles, Saint Quentin, 2005), http://wwwex.prism.uvsq.fr/rapports/bin/abstract.php?id=316&lang=fr.

2000 (2)

B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
[CrossRef]

S. Yao, B. Mukherjee, S. J. Ben Yoo, and S. Dixit, 'All-optical packet-switched networks: a study of contention-resolution schemes in irregular mesh network with variable packet size,' Proc. SPIE 4233, 235-246 (2000).

Amet, H.

H. Amet, J. Cohen, F. Deppner, M.-C. Portmann, and S. Rousseau, 'Un probleme d'ordonnancement de messages: Partie 1 modélisations; partie 2 approches de résolution,' presented at the 6th Congress of the French Society of Operations Research and Decision-Making Analysis, Tours, France, 14-16 February 2005.

Bala, K.

B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
[CrossRef]

Barth, D.

D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau, 'A comparison of splittable and non-splittable packet models in an optical ring network,' Res. Rep.2005/83 (Universite Versailles, Saint Quentin, 2005), http://wwwex.prism.uvsq.fr/rapports/bin/abstract.php?id=316&lang=fr.

D. Barth, J. Cohen, P. Fragopoulou, and G. Hébuterne, 'Wavelengths assignment on a ring all-optical metropolitan area network,' presented at the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, Rome, Italy, 21 September 2002.

Bayvel, P.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

Ben Yoo, S. J.

S. Yao, B. Mukherjee, S. J. Ben Yoo, and S. Dixit, 'All-optical packet-switched networks: a study of contention-resolution schemes in irregular mesh network with variable packet size,' Proc. SPIE 4233, 235-246 (2000).

Yao, S. J. Ben Yoo, and B. Mukerjee, 'A comparison study between slotted and unslotted all-optical packet-switched network with priority-based routing,' networks.cs.ucdavis.edu/ syao/ofc01.pdf (2002).

Bianco, A.

A. Bianco, M. Bonsignori, E. Leonardi, and F. Neri, 'Variable-size packets in slotted WDM ring networks' presented at the 6th IFIP Working Conference on Design and Modelling, Torino, Italy, 4-6 February 2002.

Bonsignori, M.

A. Bianco, M. Bonsignori, E. Leonardi, and F. Neri, 'Variable-size packets in slotted WDM ring networks' presented at the 6th IFIP Working Conference on Design and Modelling, Torino, Italy, 4-6 February 2002.

Breuer, D.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

Brucker, P.

P. Brucker, Scheduling Algorithms (Springer-Verlag, 2001).

Chandhok, N.

N. Chandhok, A. Durresi, R. Jagannathan, and R. Jain, 'IP over optical networks: summary of issues,' www.cs.wustl.edu/rjain/ietf/issues.htm (2000).

Chen, Y.

X. Yu, Y. Chen, and C. Qiao, 'A study of traffic statistics of assembled burst traffic in optical burst switched networks,' www.cse.buffalo.edu/ qiao/wobs/ obs/papers/Yulowbaropti02.pdf 2003.

Cohen, J.

H. Amet, J. Cohen, F. Deppner, M.-C. Portmann, and S. Rousseau, 'Un probleme d'ordonnancement de messages: Partie 1 modélisations; partie 2 approches de résolution,' presented at the 6th Congress of the French Society of Operations Research and Decision-Making Analysis, Tours, France, 14-16 February 2005.

D. Barth, J. Cohen, P. Fragopoulou, and G. Hébuterne, 'Wavelengths assignment on a ring all-optical metropolitan area network,' presented at the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, Rome, Italy, 21 September 2002.

D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau, 'A comparison of splittable and non-splittable packet models in an optical ring network,' Res. Rep.2005/83 (Universite Versailles, Saint Quentin, 2005), http://wwwex.prism.uvsq.fr/rapports/bin/abstract.php?id=316&lang=fr.

de Miguel, I.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

Deppner, F.

H. Amet, J. Cohen, F. Deppner, M.-C. Portmann, and S. Rousseau, 'Un probleme d'ordonnancement de messages: Partie 1 modélisations; partie 2 approches de résolution,' presented at the 6th Congress of the French Society of Operations Research and Decision-Making Analysis, Tours, France, 14-16 February 2005.

Dixit, S.

S. Yao, B. Mukherjee, S. J. Ben Yoo, and S. Dixit, 'All-optical packet-switched networks: a study of contention-resolution schemes in irregular mesh network with variable packet size,' Proc. SPIE 4233, 235-246 (2000).

Dser, M.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

Durresi, A.

N. Chandhok, A. Durresi, R. Jagannathan, and R. Jain, 'IP over optical networks: summary of issues,' www.cs.wustl.edu/rjain/ietf/issues.htm (2000).

Fragopoulou, P.

D. Barth, J. Cohen, P. Fragopoulou, and G. Hébuterne, 'Wavelengths assignment on a ring all-optical metropolitan area network,' presented at the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, Rome, Italy, 21 September 2002.

Garey, M.

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).

Gastal, L.

D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau, 'A comparison of splittable and non-splittable packet models in an optical ring network,' Res. Rep.2005/83 (Universite Versailles, Saint Quentin, 2005), http://wwwex.prism.uvsq.fr/rapports/bin/abstract.php?id=316&lang=fr.

Gladisch, A.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

Hanik, N.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

Hébuterne, G.

D. Barth, J. Cohen, P. Fragopoulou, and G. Hébuterne, 'Wavelengths assignment on a ring all-optical metropolitan area network,' presented at the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, Rome, Italy, 21 September 2002.

Jagannathan, R.

N. Chandhok, A. Durresi, R. Jagannathan, and R. Jain, 'IP over optical networks: summary of issues,' www.cs.wustl.edu/rjain/ietf/issues.htm (2000).

Jain, R.

N. Chandhok, A. Durresi, R. Jagannathan, and R. Jain, 'IP over optical networks: summary of issues,' www.cs.wustl.edu/rjain/ietf/issues.htm (2000).

Johnson, D.

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).

Leonardi, E.

A. Bianco, M. Bonsignori, E. Leonardi, and F. Neri, 'Variable-size packets in slotted WDM ring networks' presented at the 6th IFIP Working Conference on Design and Modelling, Torino, Italy, 4-6 February 2002.

Mautor, T.

D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau, 'A comparison of splittable and non-splittable packet models in an optical ring network,' Res. Rep.2005/83 (Universite Versailles, Saint Quentin, 2005), http://wwwex.prism.uvsq.fr/rapports/bin/abstract.php?id=316&lang=fr.

Mukerjee, B.

Yao, S. J. Ben Yoo, and B. Mukerjee, 'A comparison study between slotted and unslotted all-optical packet-switched network with priority-based routing,' networks.cs.ucdavis.edu/ syao/ofc01.pdf (2002).

Mukherjee, B.

S. Yao, B. Mukherjee, S. J. Ben Yoo, and S. Dixit, 'All-optical packet-switched networks: a study of contention-resolution schemes in irregular mesh network with variable packet size,' Proc. SPIE 4233, 235-246 (2000).

Neri, F.

A. Bianco, M. Bonsignori, E. Leonardi, and F. Neri, 'Variable-size packets in slotted WDM ring networks' presented at the 6th IFIP Working Conference on Design and Modelling, Torino, Italy, 4-6 February 2002.

Pendarakis, D.

B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
[CrossRef]

Pinedo, M.

M. Pinedo, Scheduling: Theory, Algorithms, and System (Prentice-Hall, 2002).

Portmann, M.-C.

H. Amet, J. Cohen, F. Deppner, M.-C. Portmann, and S. Rousseau, 'Un probleme d'ordonnancement de messages: Partie 1 modélisations; partie 2 approches de résolution,' presented at the 6th Congress of the French Society of Operations Research and Decision-Making Analysis, Tours, France, 14-16 February 2005.

Qiao, C.

X. Yu, Y. Chen, and C. Qiao, 'A study of traffic statistics of assembled burst traffic in optical burst switched networks,' www.cse.buffalo.edu/ qiao/wobs/ obs/papers/Yulowbaropti02.pdf 2003.

Rajagopalan, B.

B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
[CrossRef]

Ramamoorthy, R. S.

B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
[CrossRef]

Rousseau, S.

H. Amet, J. Cohen, F. Deppner, M.-C. Portmann, and S. Rousseau, 'Un probleme d'ordonnancement de messages: Partie 1 modélisations; partie 2 approches de résolution,' presented at the 6th Congress of the French Society of Operations Research and Decision-Making Analysis, Tours, France, 14-16 February 2005.

D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau, 'A comparison of splittable and non-splittable packet models in an optical ring network,' Res. Rep.2005/83 (Universite Versailles, Saint Quentin, 2005), http://wwwex.prism.uvsq.fr/rapports/bin/abstract.php?id=316&lang=fr.

Saha, D.

B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
[CrossRef]

Spencer, J.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

Yao,

Yao, S. J. Ben Yoo, and B. Mukerjee, 'A comparison study between slotted and unslotted all-optical packet-switched network with priority-based routing,' networks.cs.ucdavis.edu/ syao/ofc01.pdf (2002).

Yao, S.

S. Yao, B. Mukherjee, S. J. Ben Yoo, and S. Dixit, 'All-optical packet-switched networks: a study of contention-resolution schemes in irregular mesh network with variable packet size,' Proc. SPIE 4233, 235-246 (2000).

Yu, X.

X. Yu, Y. Chen, and C. Qiao, 'A study of traffic statistics of assembled burst traffic in optical burst switched networks,' www.cse.buffalo.edu/ qiao/wobs/ obs/papers/Yulowbaropti02.pdf 2003.

Zapata, A.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

IEEE Commun. Mag. (1)

B. Rajagopalan, D. Pendarakis, D. Saha, R. S. Ramamoorthy, and K. Bala, 'IP over optical network: architectural aspects,' IEEE Commun. Mag. 38(9), 94-102 (2000).
[CrossRef]

ITU News Mag. (1)

International Telecommunications Union, 'Convergence between internet and optical networks,' ITU News Mag. , October 2003, www.itu.int/itunews.

Proc. SPIE (1)

S. Yao, B. Mukherjee, S. J. Ben Yoo, and S. Dixit, 'All-optical packet-switched networks: a study of contention-resolution schemes in irregular mesh network with variable packet size,' Proc. SPIE 4233, 235-246 (2000).

Other (12)

Yao, S. J. Ben Yoo, and B. Mukerjee, 'A comparison study between slotted and unslotted all-optical packet-switched network with priority-based routing,' networks.cs.ucdavis.edu/ syao/ofc01.pdf (2002).

P. Brucker, Scheduling Algorithms (Springer-Verlag, 2001).

M. Pinedo, Scheduling: Theory, Algorithms, and System (Prentice-Hall, 2002).

H. Amet, J. Cohen, F. Deppner, M.-C. Portmann, and S. Rousseau, 'Un probleme d'ordonnancement de messages: Partie 1 modélisations; partie 2 approches de résolution,' presented at the 6th Congress of the French Society of Operations Research and Decision-Making Analysis, Tours, France, 14-16 February 2005.

M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).

European project of the 5th PCRD. Data and voice integration over DWDM (david).

D. Barth, J. Cohen, L. Gastal, T. Mautor, and S. Rousseau, 'A comparison of splittable and non-splittable packet models in an optical ring network,' Res. Rep.2005/83 (Universite Versailles, Saint Quentin, 2005), http://wwwex.prism.uvsq.fr/rapports/bin/abstract.php?id=316&lang=fr.

N. Chandhok, A. Durresi, R. Jagannathan, and R. Jain, 'IP over optical networks: summary of issues,' www.cs.wustl.edu/rjain/ietf/issues.htm (2000).

D. Barth, J. Cohen, P. Fragopoulou, and G. Hébuterne, 'Wavelengths assignment on a ring all-optical metropolitan area network,' presented at the 3rd Workshop on Approximation and Randomization Algorithms in Communication Networks, Rome, Italy, 21 September 2002.

A. Bianco, M. Bonsignori, E. Leonardi, and F. Neri, 'Variable-size packets in slotted WDM ring networks' presented at the 6th IFIP Working Conference on Design and Modelling, Torino, Italy, 4-6 February 2002.

A. Zapata, J. Spencer, I. de Miguel, M. Dser, P. Bayvel, D. Breuer, N. Hanik, and A. Gladisch, 'Investigation of future optical metro ring networks based on 100-gigabit ethernet,' presented at ITG-Fachtagung 'Photonische Netze,' Leipzig, Germany, 5-6 May 2003.

X. Yu, Y. Chen, and C. Qiao, 'A study of traffic statistics of assembled burst traffic in optical burst switched networks,' www.cse.buffalo.edu/ qiao/wobs/ obs/papers/Yulowbaropti02.pdf 2003.

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.