Harks, T: Multicommodity Routing Problems

One of the main goals of this thesis was to understand the consequences of selfish behavior and limited knowledge about future information on the performance of routing strategies. We identified three practical applications for the considered models arising in road traffic networks and in the Internet. First, we studied online routing strategies within the framework Online-MCRP that modeled the interactions of service providers in an inter-domain resource market. In such a market, network capacity is traded in order to deploy Internet traffic with Quality of Service requirements. We showed that a greedy online algorithm, which corresponds to a natural cost minimization strategy of a service provider, leads to a routing pattern that is not too inefficient. In particular, we showed that for polynomial price functions in Cd, the competitive ratio of this greedy online algorithm can be bounded by a constant factor (depending on d) for arbitrary networks and commodity sequences. Even though the provable bounds are quite large, these bounds show that the proposed inter-domain market may not lead to arbitrary inefficient resource allocations. In practice, however, there are many more additional requirements to consider. For instance, routings have to respect capacities, which we only incorporated implicitly using steep load dependent price functions. With capacities, however, one can easily construct examples in which any online algorithm does not even produce a feasible solution. Further requirements in practice include path length restrictions and survivability issues. Another important point is that in practice, routings are only valid until a given time, after which they disappear. This has effects on the cost for future routings. It is also an open issue whether the competitiveness bound in Theorem 3.9 and Theorem 3.24 are tight, and whether there exists a competitive online algorithm for the unsplittable variant of the OnlineMCRP. Finally, we simplified the