Complexity analysis and algorithm design for advance bandwidth scheduling in dedicated networks

Yunyue Lin, Qishi Wu

Research output: Contribution to journalArticlepeer-review

52 Scopus citations


An increasing number of high-performance networks provision dedicated channels through circuit switching or MPLS/GMPLS techniques to support large data transfer. The link bandwidths in such networks are typically shared by multiple users through advance reservation, resulting in varying bandwidth availability in future time. Developing efficient scheduling algorithms for advance bandwidth reservation has become a critical task to improve the utilization of network resources and meet the transport requirements of application users. We consider an exhaustive combination of different path and bandwidth constraints and formulate four types of advance bandwidth scheduling problems, with the same objective to minimize the data transfer end time for a given transfer request with a prespecified data size: 1) fixed path with fixed bandwidth (FPFB); 2) fixed path with variable bandwidth (FPVB); 3) variable path with fixed bandwidth (VPFB); and 4) variable path with variable bandwidth (VPVB). For VPFB and VPVB, we further consider two subcases where the path switching delay is negligible or nonnegligible. We propose an optimal algorithm for each of these scheduling problems except for FPVB and VPVB with nonnegligible path switching delay, which are proven to be NP-complete and nonapproximable, and then tackled by heuristics. The performance superiority of these heuristics is verified by extensive experimental results in a large set of simulated networks in comparison to optimal and greedy strategies.

Original languageEnglish (US)
Article number6170906
Pages (from-to)14-27
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number1
StatePublished - 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


  • Bandwidth scheduling
  • dedicated networks
  • nonapproximable


Dive into the research topics of 'Complexity analysis and algorithm design for advance bandwidth scheduling in dedicated networks'. Together they form a unique fingerprint.

Cite this