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

Yunyue Lin, Qishi Wu

Research output: Contribution to journalArticlepeer-review

46 Scopus citations

Abstract

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
Volume21
Issue number1
DOIs
StatePublished - Feb 20 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Bandwidth scheduling
  • dedicated networks
  • nonapproximable

Fingerprint 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