Cookies help us deliver our services. By using our services, you agree to our use of cookies.

Cuvillier Verlag

Publications, Dissertations, Habilitations & Brochures.
International Specialist Publishing House for Science and Economy

Cuvillier Verlag

De En Es
Multicommodity Routing Problems

Hard Copy
EUR 19.00 EUR 18.05

EUR 13.30

Multicommodity Routing Problems (English shop)

Selfish Behavior and Online Aspects

Tobias Harks (Author)


Table of Contents, Datei (31 KB)
Extract, Datei (95 KB)

ISBN-13 (Printausgabe) 3867273596
ISBN-13 (Hard Copy) 9783867273596
ISBN-13 (eBook) 9783736923591
Language English
Page Number 132
Edition 1
Volume 0
Publication Place Göttingen
Place of Dissertation Berlin
Publication Date 2007-09-06
General Categorization Dissertation
Departments Mathematics
Keywords Multicommodity Flow, Online Optimization, Algorithmic Game Theory.

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).