Abstract

Data-intensive Grid applications require huge data transferring between multiple geographically separated computing nodes where computing tasks are executed. For a future WDM network to efficiently support this type of emerging applications, neither the traditional approaches to establishing lightpaths between given source destination pairs are sufficient, nor are those existing application level approaches that consider computing resources but ignore the optical layer connectivity. Instead, lightpath establishment has to be considered jointly with task scheduling to achieve best performance. In this paper, we study the optimization problems of jointly scheduling both computing resources and network resources. We first present the formulation of two optimization problems with the objectives being the minimization of the completion time of a job and minimization of the resource usage/cost to satisfy a job with a deadline. When the objective is to minimize the completion time, we devise an optimal algorithm for a special type of applications. Furthermore, we propose efficient heuristics to deal with general applications with either optimization objective and demonstrate their good performances in simulation.

© 2009 IEEE

PDF Article

References

  • View by:
  • |
  • |

  1. H. El-Rewini, T. G. Lewis, H. H. Ali, Task Scheduling in Parallel and Distributed Systems (Prentice-Hall, 1994).
  2. D. Simeonidou, "Dynamic optical-network architectures and technologies for existing and emerging grid services," J. Lightw. Technol. 23, 3347-3357 (2005).
  3. M. De Leenheer, "A view on enabling-consumer oriented grids through optical burst switching," IEEE Commun. Mag. 44, 124-131 (2006).
  4. G. Zervas, "A fully functional application-aware optical burst switched network test-bed," OFC/NFOEC AnaheimCA (2007) OWC2.
  5. Y. Wang, "Joint scheduling for optical grid applications," J. Opt. Netw. 6, 304-318 (2007).
  6. H. Zang, J. P. Jue, B. Mukherjee, "A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks," SPIE Opt. Netw. Mag. 1, (2000).
  7. R. Dutta, G. Rouskas, "Survey of virtual topology design algorithms for wavelength routed networks," SPIE Opt. Netw. Mag. 1, 73-89 (2000).
  8. J. Kuri, "Routing and wavelength assignment of scheduled lightpath demands," IEEE J. Sel. Areas Commun. 21, 1231-1240 (2003).
  9. B. Wang, "On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks," Broadband Networks 13-22 (2005).
  10. O. Sinnen, L. A. Sousa, "Communication contention in task scheduling," IEEE Trans. Parallel Distrib. Syst. 16, 503-515 (2005).
  11. M. Labb, R. Seguin, P. Soriano, C. Wynants, “Network synthesis with non-simultaneous multicommodity flow requirements: bounds and heuristics,” S.M.G., Univerist Libre de Bruxelles, Tech. Report 99/26 (1999).
  12. S. H. Bokhari, A Shortest Tree Algorithm for Optimal Assignment Across Space and Time in a Distributed Processor System SE-7, 583-589 (1981).
  13. H. Thomas, Introduction to Algorithms (The MIT Press, 2001).
  14. J. D. Ullman, "NP-complete scheduling problems," J. Comput. Syst. Sci. 10, 384-393 (1975).
  15. T. L. Adam, K. M. Chandy, J. R. Dickson, "A comparison of list schedules for parallel processing systems," Commun. ACM 17, 685-689 (1974).
  16. O. Sinnen, L. Sousa, "List scheduling: Extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures," Parallel Comput. 30, 81-101 (2004).
  17. X. Liu, "Approaches to support various types of traffic in WDM networks," OFC/NFOEC AnaheimCA (2007) OThQ4.

2007 (1)

2006 (1)

M. De Leenheer, "A view on enabling-consumer oriented grids through optical burst switching," IEEE Commun. Mag. 44, 124-131 (2006).

2005 (3)

D. Simeonidou, "Dynamic optical-network architectures and technologies for existing and emerging grid services," J. Lightw. Technol. 23, 3347-3357 (2005).

B. Wang, "On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks," Broadband Networks 13-22 (2005).

O. Sinnen, L. A. Sousa, "Communication contention in task scheduling," IEEE Trans. Parallel Distrib. Syst. 16, 503-515 (2005).

2004 (1)

O. Sinnen, L. Sousa, "List scheduling: Extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures," Parallel Comput. 30, 81-101 (2004).

2003 (1)

J. Kuri, "Routing and wavelength assignment of scheduled lightpath demands," IEEE J. Sel. Areas Commun. 21, 1231-1240 (2003).

2000 (2)

H. Zang, J. P. Jue, B. Mukherjee, "A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks," SPIE Opt. Netw. Mag. 1, (2000).

R. Dutta, G. Rouskas, "Survey of virtual topology design algorithms for wavelength routed networks," SPIE Opt. Netw. Mag. 1, 73-89 (2000).

1981 (1)

S. H. Bokhari, A Shortest Tree Algorithm for Optimal Assignment Across Space and Time in a Distributed Processor System SE-7, 583-589 (1981).

1975 (1)

J. D. Ullman, "NP-complete scheduling problems," J. Comput. Syst. Sci. 10, 384-393 (1975).

1974 (1)

T. L. Adam, K. M. Chandy, J. R. Dickson, "A comparison of list schedules for parallel processing systems," Commun. ACM 17, 685-689 (1974).

A Shortest Tree Algorithm for Optimal Assignment Across Space and Time in a Distributed Processor System (1)

S. H. Bokhari, A Shortest Tree Algorithm for Optimal Assignment Across Space and Time in a Distributed Processor System SE-7, 583-589 (1981).

Broadband Networks (1)

B. Wang, "On service provisioning under a scheduled traffic model in reconfigurable WDM optical networks," Broadband Networks 13-22 (2005).

Commun. ACM (1)

T. L. Adam, K. M. Chandy, J. R. Dickson, "A comparison of list schedules for parallel processing systems," Commun. ACM 17, 685-689 (1974).

IEEE J. Sel. Areas Commun. (1)

J. Kuri, "Routing and wavelength assignment of scheduled lightpath demands," IEEE J. Sel. Areas Commun. 21, 1231-1240 (2003).

IEEE Commun. Mag. (1)

M. De Leenheer, "A view on enabling-consumer oriented grids through optical burst switching," IEEE Commun. Mag. 44, 124-131 (2006).

IEEE Trans. Parallel Distrib. Syst. (1)

O. Sinnen, L. A. Sousa, "Communication contention in task scheduling," IEEE Trans. Parallel Distrib. Syst. 16, 503-515 (2005).

J. Comput. Syst. Sci. (1)

J. D. Ullman, "NP-complete scheduling problems," J. Comput. Syst. Sci. 10, 384-393 (1975).

J. Lightw. Technol. (1)

D. Simeonidou, "Dynamic optical-network architectures and technologies for existing and emerging grid services," J. Lightw. Technol. 23, 3347-3357 (2005).

J. Opt. Netw. (1)

Parallel Comput. (1)

O. Sinnen, L. Sousa, "List scheduling: Extension for contention awareness and evaluation of node priorities for heterogeneous cluster architectures," Parallel Comput. 30, 81-101 (2004).

SPIE Opt. Netw. Mag. (1)

R. Dutta, G. Rouskas, "Survey of virtual topology design algorithms for wavelength routed networks," SPIE Opt. Netw. Mag. 1, 73-89 (2000).

SPIE Opt. Netw. Mag. (1)

H. Zang, J. P. Jue, B. Mukherjee, "A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks," SPIE Opt. Netw. Mag. 1, (2000).

Other (5)

M. Labb, R. Seguin, P. Soriano, C. Wynants, “Network synthesis with non-simultaneous multicommodity flow requirements: bounds and heuristics,” S.M.G., Univerist Libre de Bruxelles, Tech. Report 99/26 (1999).

H. Thomas, Introduction to Algorithms (The MIT Press, 2001).

X. Liu, "Approaches to support various types of traffic in WDM networks," OFC/NFOEC AnaheimCA (2007) OThQ4.

H. El-Rewini, T. G. Lewis, H. H. Ali, Task Scheduling in Parallel and Distributed Systems (Prentice-Hall, 1994).

G. Zervas, "A fully functional application-aware optical burst switched network test-bed," OFC/NFOEC AnaheimCA (2007) OWC2.

Cited By

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