Treffer: Internet routing and related topology issues

In most domains of the Internet network, the traffic demands are routed on a single-path defined as the shortest one according to a set of administrative weights. Most of the time, the values set by the administrator (or the default ones) are such that there are many paths of the same length between the extremities of some demands. However, if the shortest paths are not unique, it might become difficult for an Internet domain administrator to predict and control the traffic flows in the network. Moreover, the sequence order of packets can be changed when many paths are used leading to some end-to-end delays. It is hence an important issue to ensure that each shortest path is unique according to a given set of administrative weights. We show that it is possible to determine a set of small integer weights (smaller than 6 times the radius of the network) such that all links are used and every demand is routed on a unique shortest path. Above and beyond this uniqueness requirement, network administrators wishing to exploit the available resources would like to control the whole routing pattern. The problem they face consists of determining a set of weights enforcing a given routing policy. We formulate this problem using linear programs, and we show how integer weights can be computed by heuristics with guaranteed worst-case performances. Some conditions on the given routing, necessary for the existence of a solution, are derived. Both necessary and sufficient conditions are also provided, together with some other useful properties, in the case of particular graphs such as cycles and cacti.