×

Traffic engineering of management flows by link augmentations on confluent trees. (English) Zbl 1153.68315

Summary: 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. In particular, we design fully polynomial-time approximate schemes for different variants of this problem on trees. We use these algorithms as the basis for designing efficient heuristics for alleviating congestion in general \((non-tree)\) service provider network topologies.

MSC:

68M10 Network design and communication in computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Applegate, D., Cohen, E.: Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs. In: ACM SIGCOMM, 2003
[2] Bejerano, Y., Rastogi, R.: Robust monitoring of link delays and faults in IP networks. In: IEEE INFOCOM, 2003
[3] Bienkowski, M., Korzeniowski, M., Räcke, H.: A practical algorithm for constructing oblivious routing schemes. In: 15th Annual ACM Symp. on Parallel Algorithms and Architectures (SPAA), pp. 24–33 (2003)
[4] Breitbart, Y., Chan, C.Y., Garofalakis, M., Rastogi, R., Silberschatz, A.: Efficiently monitoring bandwidth and latency in ip networks. In: IEEE INFOCOM, 2001
[5] Chen, J., Rajaraman, R., Sundaram, R.: Meet and merge: approximation algorithms for confluent flow. In: Symp. on Theory of Computing (STOC), pp. 373–382 (2003) · Zbl 1192.90220
[6] Chen, J., Kleinberg, R., Lovasz, L., Rajaraman, R., Sundaram, R., Vetta, A.: (Almost) tight bounds and existence theorems for confluent flows. In: Symp. on Theory of Computing (STOC), pp. 529–538 (2004) · Zbl 1192.90022
[7] Ford, L., Fulkerson, D.: Flows in Network. Princeton University Press, Princeton (1962) · Zbl 0106.34802
[8] Fortz, B., Thorup, M.: Optimizing OSPF/IS-IS weights in a changing world. IEEE J. Sel. Areas Commun. 20(4), 756–767 (2002) · doi:10.1109/JSAC.2002.1003042
[9] Fortz, B., Rexford, J., Thorup, M.: Internet traffic engineering by optimizing OSPF weights. In: IEEE INFOCOM, pp. 118–124 (2000)
[10] Fortz, B., Rexford, J., Thorup, M.: Traffic engineering with traditional IP routing protocols. IEEE Commun. Mag. 40(10), 118–124 (2002) · doi:10.1109/MCOM.2002.1039866
[11] Frank, A.: Connectivity augmentation problems in network design. In: Mathematical Programming: State of the Art, pp. 34–63 (1994)
[12] Iyer, S., Bhattacharrya, S., Taft, N., Diot, C.: An approach to alleviate link overload as observed on an IP backbone. In: IEEE INFOCOM, 2003
[13] Jamin, S., Jin, C., Jin, Y., Raz, D., Shavitt, Y., Zhang, L.: On the placement of Internet instrumentation. In: IEEE INFOCOM, 2000
[14] Kleinberg, J.: Approximation algorithms for disjoint paths problems. Ph.D. Thesis, MIT (1996) · Zbl 0877.68102
[15] Kumar, A., Rastogi, R., Siberschatz, A., Yener, B.: Algorithms for provisioning virtual private networks in the hose model. In: ACM SIGCOMM, pp. 135–148 (2001)
[16] Li, L., Thottan, M., Yao, B., Paul, S.: Distributed network monitoring with bounded link utilization in ip networks. In: IEEE INFOCOM, 2003
[17] Lorenz, D., Orda, A., Raz, D., Shavit, Y.: How good can IP routing be? In: DIMACS Technical Report: 2001-17 (2001)
[18] Wang, J., Nahrsdedt, K.: Hop-by-hop routing algorithms for premimum-class traffic in diffserv networks. In: IEEE INFOCOM, 2002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.