Abstract

Batch scheduling accommodates a group of tasks with the start/end time constraints to maximize the revenue from scheduling tasks over a number of servers, which has been extensively studied in the context of job–machine scheduling. In optical networks, batch scheduling refers to the process of scheduling a group of data units (i.e., the jobs) competing for the same set of wavelength channels (i.e., the machines). Classical job–machine scheduling studies have considered both the case of a pure-loss system, and the case with waiting rooms (i.e., buffers), which are generally in the form of random access memory (RAM). In optical networks, the buffering is achieved by feeding the optical signal into a fixed length of fiber, namely, a fiber delay line (FDL), since optical RAM is not yet available. The unique feature of the discrete and predefined buffering time in fact instantiates a new type of problem, namely, job–machine scheduling with discrete-time buffers. In this work, we comprehensively study batch scheduling in optical networks. We show that batch scheduling with and without FDLs corresponds to two different instances of the job–machine scheduling problem. While proving their NP-completeness, we mathematically model both cases using integer linear programming formulations to provide an optimal scheduling. Given the timeliness request for on-line batch scheduling and the dramatic problem size in optical networks, we also propose polynomial-time heuristic algorithms, which are shown to be near optimal in our simulations.

© 2013 OSA

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. E. M. Arkin and E. B. Silverberg, “Scheduling jobs with fixed start and end times,” Discrete Appl. Math., vol. 18, no. 1, pp. 1–8, 1987.
    [CrossRef]
  2. W. Nawijn, “Minimum loss scheduling problems,” Eur. J. Oper. Res., vol. 56, no. 3, pp. 364–369, 1992.
    [CrossRef]
  3. V. Gabrel, “Scheduling jobs within time windows on identical parallel machines: New model and algorithms,” Eur. J. Oper. Res., vol. 83, pp. 321–329, 1995.
    [CrossRef]
  4. T. Cheng and C. Sin, “A state-of-the-art review of parallel-machine scheduling research,” Eur. J. Oper. Res., vol. 47, pp. 271–292, 1990.
    [CrossRef]
  5. K. I. Bouzina and H. Emmons, “Interval scheduling on identical machines,” J. Global Optim., vol. 9, pp. 379–393, 1996.
    [CrossRef]
  6. A. Agnetis, D. Pacciarelli, and F. Rossi, “Batch scheduling in a two-machine flow shop with limited buffer,” Discrete Appl. Math., vol. 72, no. 3, pp. 243–260, 1997.
    [CrossRef]
  7. Y. Wang and X. Cao, “Distributive waveband assignment in multi-granular optical networks,” in IEEE IPDPS, Apr. 2010, pp. 1–9.
  8. S. Charcranoon, T. El-Bawab, H. Cankaya, and J.-D. Shin, “Group-scheduling for optical burst switched (OBS) networks,” in Proc. IEEE GLOBECOM, 2003, pp. 2745–2749.
  9. M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
    [CrossRef]
  10. X. Cao, Y. Wang, and A. Zelikovsky, “Batch scheduling algorithms using interval graphs in optical burst switching networks,” in Proc. IEEE GLOBECOM, 2009, pp. 1–5.
  11. A. Kaheel and H. Alnuweiri, “Batch scheduling algorithms: A class of wavelength schedulers in optical burst switching networks,” in Proc. IEEE ICC, 2005, pp. 1713–1719.
  12. F. Farahmand and J. Jue, “Look-ahead window contention resolution in optical burst switched networks,” in Workshop on High Performance Switching and Routing (HPSR), Sept. 2003, pp. 147–151.
  13. B. Mukherjee, Optical WDM Networks. Springer, 2006.
  14. R. Ramaswami, K. Sivarajan, and G. Sasaki, Optical Networks: A Practical Perspective, 3rd ed.Morgan Kaufmann, San Francisco, CA, 2009.
  15. L. Li, S. D. Scott, and J. S. Deogun, “A novel fiber delay line buffering architecture for optical packet switching,” in Proc. IEEE GLOBECOM, 2003, vol. 5, pp. 2809–2813.
  16. D. Hunter, M. Chia, and I. Andonovic, “Buffering in optical packet switches,” J. Lightwave Technol., vol. 16, no. 2, pp. 2081–2094, 1998.
    [CrossRef]
  17. M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, “Routers with very small buffers,” in Proc. IEEE INFOCOM, 2006, pp. 1–11.
  18. F. Gavril, “Algorithms for maximum k-coloring and k-covering of transitive graphs,” Comput. Chem. Eng., vol. 17, pp. 465–470, 1997.
  19. Y. Chen, C. Qiao, and X. Yu, “Optical burst switching: A new area in optical networking research,” IEEE Network, vol. 18, no. 1, pp. 16–23, May–June2004.
    [CrossRef]
  20. Y. Xiong, M. Vandenhoute, and H. Cankaya, “Control architecture in optical burst-switched WDM networks,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1838–1851, 2000.
    [CrossRef]

2005

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

2004

Y. Chen, C. Qiao, and X. Yu, “Optical burst switching: A new area in optical networking research,” IEEE Network, vol. 18, no. 1, pp. 16–23, May–June2004.
[CrossRef]

2000

Y. Xiong, M. Vandenhoute, and H. Cankaya, “Control architecture in optical burst-switched WDM networks,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1838–1851, 2000.
[CrossRef]

1998

1997

F. Gavril, “Algorithms for maximum k-coloring and k-covering of transitive graphs,” Comput. Chem. Eng., vol. 17, pp. 465–470, 1997.

A. Agnetis, D. Pacciarelli, and F. Rossi, “Batch scheduling in a two-machine flow shop with limited buffer,” Discrete Appl. Math., vol. 72, no. 3, pp. 243–260, 1997.
[CrossRef]

1996

K. I. Bouzina and H. Emmons, “Interval scheduling on identical machines,” J. Global Optim., vol. 9, pp. 379–393, 1996.
[CrossRef]

1995

V. Gabrel, “Scheduling jobs within time windows on identical parallel machines: New model and algorithms,” Eur. J. Oper. Res., vol. 83, pp. 321–329, 1995.
[CrossRef]

1992

W. Nawijn, “Minimum loss scheduling problems,” Eur. J. Oper. Res., vol. 56, no. 3, pp. 364–369, 1992.
[CrossRef]

1990

T. Cheng and C. Sin, “A state-of-the-art review of parallel-machine scheduling research,” Eur. J. Oper. Res., vol. 47, pp. 271–292, 1990.
[CrossRef]

1987

E. M. Arkin and E. B. Silverberg, “Scheduling jobs with fixed start and end times,” Discrete Appl. Math., vol. 18, no. 1, pp. 1–8, 1987.
[CrossRef]

Agnetis, A.

A. Agnetis, D. Pacciarelli, and F. Rossi, “Batch scheduling in a two-machine flow shop with limited buffer,” Discrete Appl. Math., vol. 72, no. 3, pp. 243–260, 1997.
[CrossRef]

Alnuweiri, H.

A. Kaheel and H. Alnuweiri, “Batch scheduling algorithms: A class of wavelength schedulers in optical burst switching networks,” in Proc. IEEE ICC, 2005, pp. 1713–1719.

Andonovic, I.

Arkin, E. M.

E. M. Arkin and E. B. Silverberg, “Scheduling jobs with fixed start and end times,” Discrete Appl. Math., vol. 18, no. 1, pp. 1–8, 1987.
[CrossRef]

Bouzina, K. I.

K. I. Bouzina and H. Emmons, “Interval scheduling on identical machines,” J. Global Optim., vol. 9, pp. 379–393, 1996.
[CrossRef]

Cankaya, H.

Y. Xiong, M. Vandenhoute, and H. Cankaya, “Control architecture in optical burst-switched WDM networks,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1838–1851, 2000.
[CrossRef]

S. Charcranoon, T. El-Bawab, H. Cankaya, and J.-D. Shin, “Group-scheduling for optical burst switched (OBS) networks,” in Proc. IEEE GLOBECOM, 2003, pp. 2745–2749.

Cao, X.

Y. Wang and X. Cao, “Distributive waveband assignment in multi-granular optical networks,” in IEEE IPDPS, Apr. 2010, pp. 1–9.

X. Cao, Y. Wang, and A. Zelikovsky, “Batch scheduling algorithms using interval graphs in optical burst switching networks,” in Proc. IEEE GLOBECOM, 2009, pp. 1–5.

Charcranoon, S.

S. Charcranoon, T. El-Bawab, H. Cankaya, and J.-D. Shin, “Group-scheduling for optical burst switched (OBS) networks,” in Proc. IEEE GLOBECOM, 2003, pp. 2745–2749.

Chen, Y.

Y. Chen, C. Qiao, and X. Yu, “Optical burst switching: A new area in optical networking research,” IEEE Network, vol. 18, no. 1, pp. 16–23, May–June2004.
[CrossRef]

Cheng, T.

T. Cheng and C. Sin, “A state-of-the-art review of parallel-machine scheduling research,” Eur. J. Oper. Res., vol. 47, pp. 271–292, 1990.
[CrossRef]

Chia, M.

Chua, K. C.

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

Deogun, J. S.

L. Li, S. D. Scott, and J. S. Deogun, “A novel fiber delay line buffering architecture for optical packet switching,” in Proc. IEEE GLOBECOM, 2003, vol. 5, pp. 2809–2813.

El-Bawab, T.

S. Charcranoon, T. El-Bawab, H. Cankaya, and J.-D. Shin, “Group-scheduling for optical burst switched (OBS) networks,” in Proc. IEEE GLOBECOM, 2003, pp. 2745–2749.

Emmons, H.

K. I. Bouzina and H. Emmons, “Interval scheduling on identical machines,” J. Global Optim., vol. 9, pp. 379–393, 1996.
[CrossRef]

Enachescu, M.

M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, “Routers with very small buffers,” in Proc. IEEE INFOCOM, 2006, pp. 1–11.

Farahmand, F.

F. Farahmand and J. Jue, “Look-ahead window contention resolution in optical burst switched networks,” in Workshop on High Performance Switching and Routing (HPSR), Sept. 2003, pp. 147–151.

Gabrel, V.

V. Gabrel, “Scheduling jobs within time windows on identical parallel machines: New model and algorithms,” Eur. J. Oper. Res., vol. 83, pp. 321–329, 1995.
[CrossRef]

Ganjali, Y.

M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, “Routers with very small buffers,” in Proc. IEEE INFOCOM, 2006, pp. 1–11.

Gavril, F.

F. Gavril, “Algorithms for maximum k-coloring and k-covering of transitive graphs,” Comput. Chem. Eng., vol. 17, pp. 465–470, 1997.

Goel, A.

M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, “Routers with very small buffers,” in Proc. IEEE INFOCOM, 2006, pp. 1–11.

Hunter, D.

Jue, J.

F. Farahmand and J. Jue, “Look-ahead window contention resolution in optical burst switched networks,” in Workshop on High Performance Switching and Routing (HPSR), Sept. 2003, pp. 147–151.

Kaheel, A.

A. Kaheel and H. Alnuweiri, “Batch scheduling algorithms: A class of wavelength schedulers in optical burst switching networks,” in Proc. IEEE ICC, 2005, pp. 1713–1719.

Kong, P. Y.

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

Li, L.

L. Li, S. D. Scott, and J. S. Deogun, “A novel fiber delay line buffering architecture for optical packet switching,” in Proc. IEEE GLOBECOM, 2003, vol. 5, pp. 2809–2813.

McKeown, N.

M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, “Routers with very small buffers,” in Proc. IEEE INFOCOM, 2006, pp. 1–11.

Mohan, G.

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

Motani, M.

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

Mukherjee, B.

B. Mukherjee, Optical WDM Networks. Springer, 2006.

Nawijn, W.

W. Nawijn, “Minimum loss scheduling problems,” Eur. J. Oper. Res., vol. 56, no. 3, pp. 364–369, 1992.
[CrossRef]

Pacciarelli, D.

A. Agnetis, D. Pacciarelli, and F. Rossi, “Batch scheduling in a two-machine flow shop with limited buffer,” Discrete Appl. Math., vol. 72, no. 3, pp. 243–260, 1997.
[CrossRef]

Phung, M. H.

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

Qiao, C.

Y. Chen, C. Qiao, and X. Yu, “Optical burst switching: A new area in optical networking research,” IEEE Network, vol. 18, no. 1, pp. 16–23, May–June2004.
[CrossRef]

Ramaswami, R.

R. Ramaswami, K. Sivarajan, and G. Sasaki, Optical Networks: A Practical Perspective, 3rd ed.Morgan Kaufmann, San Francisco, CA, 2009.

Rossi, F.

A. Agnetis, D. Pacciarelli, and F. Rossi, “Batch scheduling in a two-machine flow shop with limited buffer,” Discrete Appl. Math., vol. 72, no. 3, pp. 243–260, 1997.
[CrossRef]

Roughgarden, T.

M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, “Routers with very small buffers,” in Proc. IEEE INFOCOM, 2006, pp. 1–11.

Sasaki, G.

R. Ramaswami, K. Sivarajan, and G. Sasaki, Optical Networks: A Practical Perspective, 3rd ed.Morgan Kaufmann, San Francisco, CA, 2009.

Scott, S. D.

L. Li, S. D. Scott, and J. S. Deogun, “A novel fiber delay line buffering architecture for optical packet switching,” in Proc. IEEE GLOBECOM, 2003, vol. 5, pp. 2809–2813.

Shin, J.-D.

S. Charcranoon, T. El-Bawab, H. Cankaya, and J.-D. Shin, “Group-scheduling for optical burst switched (OBS) networks,” in Proc. IEEE GLOBECOM, 2003, pp. 2745–2749.

Silverberg, E. B.

E. M. Arkin and E. B. Silverberg, “Scheduling jobs with fixed start and end times,” Discrete Appl. Math., vol. 18, no. 1, pp. 1–8, 1987.
[CrossRef]

Sin, C.

T. Cheng and C. Sin, “A state-of-the-art review of parallel-machine scheduling research,” Eur. J. Oper. Res., vol. 47, pp. 271–292, 1990.
[CrossRef]

Sivarajan, K.

R. Ramaswami, K. Sivarajan, and G. Sasaki, Optical Networks: A Practical Perspective, 3rd ed.Morgan Kaufmann, San Francisco, CA, 2009.

Vandenhoute, M.

Y. Xiong, M. Vandenhoute, and H. Cankaya, “Control architecture in optical burst-switched WDM networks,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1838–1851, 2000.
[CrossRef]

Wang, Y.

Y. Wang and X. Cao, “Distributive waveband assignment in multi-granular optical networks,” in IEEE IPDPS, Apr. 2010, pp. 1–9.

X. Cao, Y. Wang, and A. Zelikovsky, “Batch scheduling algorithms using interval graphs in optical burst switching networks,” in Proc. IEEE GLOBECOM, 2009, pp. 1–5.

Wong, T. C.

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

Xiong, Y.

Y. Xiong, M. Vandenhoute, and H. Cankaya, “Control architecture in optical burst-switched WDM networks,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1838–1851, 2000.
[CrossRef]

Yu, X.

Y. Chen, C. Qiao, and X. Yu, “Optical burst switching: A new area in optical networking research,” IEEE Network, vol. 18, no. 1, pp. 16–23, May–June2004.
[CrossRef]

Zelikovsky, A.

X. Cao, Y. Wang, and A. Zelikovsky, “Batch scheduling algorithms using interval graphs in optical burst switching networks,” in Proc. IEEE GLOBECOM, 2009, pp. 1–5.

Comput. Chem. Eng.

F. Gavril, “Algorithms for maximum k-coloring and k-covering of transitive graphs,” Comput. Chem. Eng., vol. 17, pp. 465–470, 1997.

Comput. Netw.

M. H. Phung, K. C. Chua, G. Mohan, M. Motani, T. C. Wong, and P. Y. Kong, “On ordered scheduling for optical burst switching,” Comput. Netw., vol. 48, no. 6, pp. 891–909, 2005.
[CrossRef]

Discrete Appl. Math.

A. Agnetis, D. Pacciarelli, and F. Rossi, “Batch scheduling in a two-machine flow shop with limited buffer,” Discrete Appl. Math., vol. 72, no. 3, pp. 243–260, 1997.
[CrossRef]

E. M. Arkin and E. B. Silverberg, “Scheduling jobs with fixed start and end times,” Discrete Appl. Math., vol. 18, no. 1, pp. 1–8, 1987.
[CrossRef]

Eur. J. Oper. Res.

W. Nawijn, “Minimum loss scheduling problems,” Eur. J. Oper. Res., vol. 56, no. 3, pp. 364–369, 1992.
[CrossRef]

V. Gabrel, “Scheduling jobs within time windows on identical parallel machines: New model and algorithms,” Eur. J. Oper. Res., vol. 83, pp. 321–329, 1995.
[CrossRef]

T. Cheng and C. Sin, “A state-of-the-art review of parallel-machine scheduling research,” Eur. J. Oper. Res., vol. 47, pp. 271–292, 1990.
[CrossRef]

IEEE J. Sel. Areas Commun.

Y. Xiong, M. Vandenhoute, and H. Cankaya, “Control architecture in optical burst-switched WDM networks,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1838–1851, 2000.
[CrossRef]

IEEE Network

Y. Chen, C. Qiao, and X. Yu, “Optical burst switching: A new area in optical networking research,” IEEE Network, vol. 18, no. 1, pp. 16–23, May–June2004.
[CrossRef]

J. Global Optim.

K. I. Bouzina and H. Emmons, “Interval scheduling on identical machines,” J. Global Optim., vol. 9, pp. 379–393, 1996.
[CrossRef]

J. Lightwave Technol.

Other

Y. Wang and X. Cao, “Distributive waveband assignment in multi-granular optical networks,” in IEEE IPDPS, Apr. 2010, pp. 1–9.

S. Charcranoon, T. El-Bawab, H. Cankaya, and J.-D. Shin, “Group-scheduling for optical burst switched (OBS) networks,” in Proc. IEEE GLOBECOM, 2003, pp. 2745–2749.

X. Cao, Y. Wang, and A. Zelikovsky, “Batch scheduling algorithms using interval graphs in optical burst switching networks,” in Proc. IEEE GLOBECOM, 2009, pp. 1–5.

A. Kaheel and H. Alnuweiri, “Batch scheduling algorithms: A class of wavelength schedulers in optical burst switching networks,” in Proc. IEEE ICC, 2005, pp. 1713–1719.

F. Farahmand and J. Jue, “Look-ahead window contention resolution in optical burst switched networks,” in Workshop on High Performance Switching and Routing (HPSR), Sept. 2003, pp. 147–151.

B. Mukherjee, Optical WDM Networks. Springer, 2006.

R. Ramaswami, K. Sivarajan, and G. Sasaki, Optical Networks: A Practical Perspective, 3rd ed.Morgan Kaufmann, San Francisco, CA, 2009.

L. Li, S. D. Scott, and J. S. Deogun, “A novel fiber delay line buffering architecture for optical packet switching,” in Proc. IEEE GLOBECOM, 2003, vol. 5, pp. 2809–2813.

M. Enachescu, Y. Ganjali, A. Goel, N. McKeown, and T. Roughgarden, “Routers with very small buffers,” in Proc. IEEE INFOCOM, 2006, pp. 1–11.

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.


Figures (10)

Fig. 1
Fig. 1

(Color online) Feed-forward FDLs.

Fig. 2
Fig. 2

(Color online) A schematic optical router employing FDLs.

Fig. 3
Fig. 3

(Color online) An example of OBS batch scheduling.

Fig. 4
Fig. 4

(Color online) An example of batch scheduling with FDLs.

Fig. 5
Fig. 5

(Color online) Time intervals for batch scheduling.

Fig. 6
Fig. 6

(Color online) Blocking probability versus load.

Fig. 7
Fig. 7

(Color online) Throughput versus load.

Fig. 8
Fig. 8

(Color online) Delay versus load for the control packet.

Fig. 9
Fig. 9

(Color online) Delay versus load for the data unit.

Fig. 10
Fig. 10

(Color online) Blocking probability versus B W .

Tables (3)

Tables Icon

Table I Variations of Job–Machine Scheduling

Tables Icon

Algorithm 1 Section-Based Batch Scheduling (SBS)

Tables Icon

Table II Simulation Parameters

Equations (20)

Equations on this page are rendered with MathJax. Learn more.

maximize i , k C i k .
maximize i , k C i k * L i .
k [ 1 , K ] C i k 1 .
m [ 0 , M ] F D L i m 1 .
m [ 0 , M ] F D L i m = k [ 1 , K ] C i k .
If ( D i A j ) × ( D j A i ) > 0 , then , F D L i m + F D L j m 2 , m > 0 , i , j 1 , i j .
2 > ( F D L i m + F D L j m ) .
If ( D i A j ) × ( D j A i ) > 0 , then , C i k + C j k 2 , k , i , j > 0 , i j ,
A i = A i + m ( t [ m ] × F D L i m ) ,
D i = D i + m ( t [ m ] × F D L i m ) ,
A j = A j + m ( t [ m ] × F D L j m ) ,
D j = D j + m ( t [ m ] × F D L j m ) .
If C i k + C j k > 1 , then , D i A j 0 or D j A i 0 , k , i , j .
0 C i k + C j k 2 f < 2 ,
D i A j + ( 1 f ) × P or D j A i + ( 1 f ) × P .
f = u + v ,
D i A j + ( 2 f u ) × P ,
D j A i + ( 2 f v ) × P .
If ( D i A j ) × ( D j A i ) > 0 , then , C i k + C j k 2 , k , i , j 1 , i j .
2 > ( C i k + C j k ) .