The Critical Network Flow Problem: Migratability and Survivability

Ruozhou Yu, Guoliang Xue, Xiang Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


In this paper, we propose a new network abstraction, termed critical network flow, which models the bandwidth requirement of modern Internet applications and services. A critical network flow defines a conventional flow in a network with explicit requirement on its aggregate bandwidth, or the flow value as commonly termed. Unlike common bandwidth-guaranteed connections whose bandwidth is only guaranteed during normal operations, a critical network flow demands strictly enforced bandwidth guarantee during various transient network states, such as network reconfiguration or network failures. Such a demand is called the bandwidth criticality of a critical network flow, which is characterized both by its flow value and capability to satisfy bandwidth guarantee in the transient states.We study algorithmic solutions to the accommodation of critical network flows with different bandwidth criticalities, including the basic case with no transient network state considered, the case with network reconfiguration, and the case with survivability against link failures. We present a polynomial-time optimal algorithm for each case. For the survivable case, we further present a faster heuristic algorithm. We have conducted extensive experiments to evaluate our model and validate our algorithms.

Original languageEnglish (US)
Pages (from-to)3545-3558
Number of pages14
JournalIEEE/ACM Transactions on Networking
Issue number6
StatePublished - Dec 2017


  • Critical network flow
  • bandwidth guarantee
  • flow migration
  • survivability.
  • traffic engineering

ASJC Scopus subject areas

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


Dive into the research topics of 'The Critical Network Flow Problem: Migratability and Survivability'. Together they form a unique fingerprint.

Cite this