Bandwidth scheduling in overlay networks with linear capacity constraints

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


An increasing number of high-performance networks are built over the existing IP network infrastructure to provision dedicated channels for big data transfer. The links in these overlay networks correspond to underlying paths and may share lower-level link segments. We consider a model of overlay networks that incorporates correlated link capacities and linear capacity constraints (LCCs) to formulate such shared bottleneck components. The overlay links are typically shared by multiple users through advance reservations, resulting in varying bandwidth availability in future time. Therefore, efficient bandwidth scheduling algorithms are needed to improve the network resource utilization and also meet the user's transport requirements. We investigate two advance scheduling problems in overlay networks with LCCs: Fixed-Bandwidth Path and Varying-Bandwidth Path, with the objective to minimize the data transfer end time for a given data size. We prove that both problems are NP-complete and non-approximable, and propose heuristic algorithms using a gradual relaxation procedure on the maximum number of links from each LCC allowed for path computation. The performance superiority of these heuristics is verified by extensive simulation results in comparison with optimal and greedy strategies.

Original languageEnglish (US)
Title of host publicationINFOCOM 2017 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781509053360
StatePublished - Oct 2 2017
Event2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States
Duration: May 1 2017May 4 2017

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other2017 IEEE Conference on Computer Communications, INFOCOM 2017
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


  • Approximate algorithm
  • Bandwidth scheduling
  • Overlay networks


Dive into the research topics of 'Bandwidth scheduling in overlay networks with linear capacity constraints'. Together they form a unique fingerprint.

Cite this