Traffic Engineering of Management Flows by Link Augmentations on Confluent Trees

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 to avoid congestion resulting in loss of critical data (e.g. billing records, network alarms etc.) is essential for the smooth functioning of these networks. 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 providers POPs (points of prescence). These collection of paths, thus, form 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 bypass the traffic off 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. The traffic engineering problem described above also has applications to alleviating congestion resulting from focused overloads in VoIP networks and for dealing with congesting resulting from flash crowds in the world wide web. 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 of alleviating congestion in general non-tree service provider network topologies.