Traffic engineering of management flows by link augmentations on confluent trees

Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Joseph Naor, Baruch Schieber

Research output: Contribution to conferencePaperpeer-review


Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Lately there has been a tremendous increase in management traffic due to the growing complexity and size of the data networks and the services provisioned on them. Traffic engineering for management flows is essential for the smooth functioning of these networks to avoid congestion, which can result in loss of critical data such as billing records, network alarms, etc. As is the case with most intra-domain routing protocols, the management flows in many of these networks are routed on shortest paths connecting the NOC with the service provider's POPs (points of presence). This collection of paths thus forms a "confluent" tree rooted at the gateway router connected to the NOC. The links close to the gateway router may form a bottleneck in this tree resulting in congestion. Typically this congestion is alleviated by adding layer two tunnels (virtual links) that offload the traffic from some links of this tree by routing it directly to the gateway router. The traffic engineering problem is then to minimize the number of virtual links needed for alleviating congestion. In this paper we formulate a traffic engineering problem motivated by the above mentioned applications. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which the underlying network is a tree, we design efficient algorithms. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general (non-tree) service provider network topologies.

Original languageEnglish (US)
Number of pages10
StatePublished - 2005
Externally publishedYes
EventSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures - Las Vegas, NV, United States
Duration: Jul 18 2005Jul 20 2005


ConferenceSeventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures
Country/TerritoryUnited States
CityLas Vegas, NV

All Science Journal Classification (ASJC) codes

  • General Engineering


  • Approximation Algorithms
  • Network Management
  • Traffic Engineering


Dive into the research topics of 'Traffic engineering of management flows by link augmentations on confluent trees'. Together they form a unique fingerprint.

Cite this