DEFT: Distributed Exponentially-weighted Flow Splitting

Dahai Xu, Mung Chiang, Jennifer L. Rexford

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

54 Scopus citations

Abstract

Network operators control the flow of traffic through their networks by adapting the configuration of the underlying routing protocols. For example, they tune the integer link weights that interior gateway protocols like OSPF and IS-IS use to compute shortest paths. The resulting optimization problem - to find the best link weights for a given topology and traffic matrix-is computationally intractable even for the simplest objective functions, forcing the use of local-search techniques. The optimization problem is difficult in part because these protocols split traffic evenly along shortest paths, with no ability to adjust the splitting percentages or direct traffic on other paths. In this paper, we propose an extension to these protocols, called Distributed Exponentially-weighted Flow SpliTting (DEFT), where the routers can direct traffic on non-shortest paths, with an exponential penalty on longer paths. DEFT leads not only to an easier-to-solve optimization problem, but also to weight settings that provably perform no worse than OSPF and IS-IS. Furthermore, in our optimization problem, both link weights and flows of traffic are integrated as optimization variables into the formulation and jointly solved by a twostage iterative method. Our novel formulation leads to a much more efficient way to identify good link weights than the local-search heuristics used for OSPF and IS-IS today. DEFT retains the simplicity of having routers compute paths based on configurable link weights, while approaching the performance of more complex routing protocols that can split traffic arbitrarily over any paths.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE INFOCOM 2007
Subtitle of host publication26th IEEE International Conference on Computer Communications
Pages71-79
Number of pages9
DOIs
StatePublished - 2007
EventIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications - Anchorage, AK, United States
Duration: May 6 2007May 12 2007

Publication series

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

Other

OtherIEEE INFOCOM 2007: 26th IEEE International Conference on Computer Communications
Country/TerritoryUnited States
CityAnchorage, AK
Period5/6/075/12/07

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering

Keywords

  • Interior gateway protocol
  • Mathematical programming
  • Network optimization
  • OSPF
  • Routing
  • Traffic engineering

Fingerprint

Dive into the research topics of 'DEFT: Distributed Exponentially-weighted Flow Splitting'. Together they form a unique fingerprint.

Cite this