Multicommodity Routing Problems

Selfish Behavior and Online Aspects

Vorschau

Inhaltsverzeichnis, Datei (31 KB)
Leseprobe, Datei (95 KB)

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 competition within the market by assuming fixed continuous and nondecreasing price functions defining the price for a unit resource. In practice, resource providers determine prices depending on the current market situation and their position with respect to the network topology. If the provider domain’s link is a bottleneck, the demand would become somewhat inelastic leading to a monopolistic situation. For a fully connected network (i.e. perfectcompetition in the network), the demand is at a minimum when the offered price is above the current market price and at maximum when below. The infrastructure of the Internet today is more related to an oligopolistic market where the network is not fully connected (i.e. domains are at most connected to 3 to 5 neighboring domains).