Editorial Cuvillier

Publicaciones, tesis doctorales, capacitaciónes para acceder a una cátedra de universidad & prospectos.
Su editorial internacional especializado en ciencias y economia

Editorial Cuvillier

De En Es
Multicommodity Routing Problems

Impresion
EUR 19,00 EUR 18,05

E-Book
EUR 13,30

Multicommodity Routing Problems (Tienda española)

Selfish Behavior and Online Aspects

Tobias Harks (Autor)

Previo

Indice, Datei (31 KB)
Lectura de prueba, Datei (95 KB)

ISBN-10 (Impresion) 3867273596
ISBN-13 (Impresion) 9783867273596
ISBN-13 (E-Book) 9783736923591
Idioma Inglés
Numero de paginas 132
Edicion 1
Volumen 0
Lugar de publicacion Göttingen
Lugar de la disertacion Berlin
Fecha de publicacion 06.09.2007
Clasificacion simple Tesis doctoral
Area Matemática
Palabras claves Mehrgueterflussprobleme, Online Optimierung, Algorithmische Spieltheorie.
Descripcion

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