Disjoint Routing in Telecommunication Networks

Participants: Ewgenij Gawrilow,
Olaf Jahn,
Rolf H. Möhring,
Martin Oellrich,
Andreas S. Schulz
Supported by: Deutsche Telekom AG, Darmstadt

Project description:

Traditionally, in telecommunication, the operation and management of the network infrastructure on the one hand and the provision of network services on the other hand have been organized as an integrated process. The liberalization of the German telecommunications market makes possible the decoupling of both tasks. This goes along with competition among the providers of network services who lease the required transportation capacity from the carrier of the physical transmission network (for example Deutsche Telekom). That is, a provider tells Deutsche Telekom which links he needs between his service nodes. These so-called network platforms, consisting of the service provider's nodes and the links connecting them, can, for instance, be data service networks, or backbone networks for mobile services, or ATM networks. The service providers try to enhance the quality and reliability of their services by dedicated management. However, to ensure the success of their survivability planning, links which seem to be independent in the network platform must not share the same equipment on the physical level.

[network with demands]

Network platform with demands

[dependent edges]
Origin of edge dependences
In traditional routing, however, each demand connection of a network platform is individually routed in the transmission network. In this setting it may happen that some nodes or edges in the transmission network are used several times. Consequently, a node or edge failure in the transmission network may give rise to two or more failures of demand connections. In this project, we have developed an efficient algorithm for the Disjoint Routing Problem. Hence, if a node or edge failure in the transmission network occurs, at most one demand connection of a network platform is affected. Moreover, we also consider the case of so-called dependent edges. Two edges of the network are said to be dependent when it is forbidden to use them simultaneously in an embedding. The notion of dependent edges naturally generalizes the concept of path disjointness. In practice, two or more edges become dependent when they model physical trunks that share a common duct. Any damage to that duct will inevitably disrupt all the trunks in it, so this information is coded as the edge dependences.
From the graph-theoretical point of view, we deal with the Maximum Disjoint Paths Problem (in both the edge- and the node-disjoint variants) which is known for its inherent difficulty. Nevertheless, our algorithm does not only work extremely well for the real-world examples that we got from Deutsche Telekom. It also finds an embedding of a network platform into the transmission network with minimum total cost. Costs are associated with each edge of the transmission network and reflect maintenance costs. The total cost of an embedding is found as the sum of all used edge costs. The two figures depict a network platform together with the available transmission network and an optimal realization of the demand connections as pairwise node-disjoint paths in the transmission network. [embedded demands]
Optimal realization as pairwise node-disjoint paths

Our exact optimization algorithm and the various subroutines for finding "good" primal and dual bounds as well as the graphical viewer/demand editor have been implemented in C and C++. Providing input data for this software is easy as we use a simple ASCII-based file format. Naturally, the programs can be adapted to get their data also from other sources (like pipes, sockets, memory blocks, or a data base).

Find out more about how our algorithm works.

A German-language poster about this this project is available as PDF (0.2 MB), Postscript (0.8 MB), or gzipped Postscript (0.2 MB).