DIMACS TR: 2004-24

Network Augmentation for Confluent Flow in Data Networks



Authors: Randeep Bhatia, Nicole Immorlica, Tracy Kimbrel, Vahab S. Mirrokni, Joseph (Seffi) Naor and Baruch Schieber

ABSTRACT
Service providers rely on the management systems housed in their Network Operations Centers (NOCs) to remotely operate, monitor and provision their data networks. Due to the growing complexity and size of the data networks and the services provisioned on them, there has been a tremendous increase in management traffic. Traffic engineering for management traffic to avoid congestion resulting in packet losses and retransmissions is essential for the smooth functioning of these networks.

In this paper we study the traffic engineering of networks that use hop-by-hop routing (as is the case with most inter-domain and intra-domain routing protocols) for carrying management traffic. In such networks the set of routing paths connecting the NOC with the service provider's POPs (points of presence) form a tree rooted at the gateway router connected to the NOC. Given the management traffic need for each individual network node, we are interested in the minimal topological changes (link and/or link weight modi cations) to ensure low-congestion routing of the management traffic. We show that the general versions of this problem are hard to solve. However, for some simpler cases in which new (physical or virtual) links provide a direct bypass for connecting network nodes to the NOC and the underlying network is a tree, we present efficient algorithms. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general non-tree service provider network topologies.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-24.ps.gz

DIMACS Home Page