Reliable adaptive multipath provisioning with bandwidth and differential delay constraints

Weiyi Zhang, Jian Tang, Chonggang Wang, Shanaka De Soysa

Research output: Chapter in Book/Entry/PoemConference contribution

49 Scopus citations

Abstract

Robustness and reliability are critical issues in network management. To provide resiliency, a popular protection scheme against network failures is the simultaneous routing along multiple disjoint paths. Most previous protection and restoration schemes were designed for all-or-nothing protection and thus, an overkill for data traffic. In this work, we study the Reliable Adaptive Multipath Provisioning (RAMP) problem with reliability and differential delay constraints. We aim to route the connections in a manner such that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple (not necessary disjoint) paths, allowing the whole network to carry sufficient traffic even when link/node failure occurs. The flexibility enabled by a multipath scheme has the tradeoff of differential delay among the diversely routed paths. This requires increased memory in the destination node in order to buffer the traffic until the data arrives on all the paths. Increased buffer size will raise the network element cost and could cause buffer overflow and data corruption. Therefore, differential delay between the multiple paths should be bounded by containing the delay of a path in a range. We first prove that RAMP is an NP-hard problem. Then we present a pseudo-polynomial time solution to solve a special case of RAMP, representing edge delays as integers. Next, an (1 + ε)-approximation algorithm is proposed to solve the optimization version of the RAMP problem. An efficient heuristic is also provided for the RAMP problem. We also present numerical results confirming the advantage of our schemes as the first solution for the RAMP problem.

Original languageEnglish (US)
Title of host publication2010 Proceedings IEEE INFOCOM
DOIs
StatePublished - 2010
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

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

Other

OtherIEEE INFOCOM 2010
Country/TerritoryUnited States
CitySan Diego, CA
Period3/14/103/19/10

Keywords

  • Differential delay
  • Multi-path routing
  • Polynomial time approximation
  • Quality of service
  • Restricted maximum flow

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Reliable adaptive multipath provisioning with bandwidth and differential delay constraints'. Together they form a unique fingerprint.

Cite this