Competitive Packet Routing

 

With modern communication systems a lot of challenges rise. Consider the Internet, which is a huge network of servers and wires. An amazing amount of data is transported through this network in every second and each packet of data is allowed to freely choose a path through this network. Such a complex scenario leads to a lot of questions:

  1. What is a good protocol to send informations through the Internet? Which rules could speed up the total performance of the network?

  2. How long does it take to send a packet from location A to location B?

  3. What is the benefit of a central authority compared to selfish users in the network? What would it cost to install such an authority? Can we decrease the total travel time without regulating the participants too much?

For dealing with this questions we combine concepts of game theory and network optimization.
Game theory deals with systems in which selfish and rational agents interact with each other. While in network optimization there is the so called packet routing problem which asks for central solution that coordinates all agents in such a network. We represent the internet as a graph, servers become nodes and the wires between them become arcs. Selfish players (representing the packets) want to traverse a network as fast as possible but the capacities of some arcs are too small to handle all players simultaneously. So some of the data has to wait until it can pass this bottleneck.To analyze this kind of conflict we search for equilibria that arise from the selfish decisions of the players. We try to prove the existence of these equilibria. In case of existence, we compare the performance of such states with those that would result if a central authority optimized the paths of all participants. Due to this we can give bounds or guarantees on how bad a lack of coordination can be. Therefore we are able to classify different networks and mechanisms by their performance.

In a primary work we analyzed the impact of a priority list of all players on games, where each player owns a single packet [1]. We derived several new bounds on the price of anarchy and stability for global and local priority policies. We also considered the question of the complexity of computing an optimal priority list. It turns out that even for very restricted cases, i.e. for routing on a tree, the computation of an optimal priority list is APX-hard.

This project is contributed by Tobias Harks, Britta Peis, Daniel Schmand, Laura Vargas Koch and Björn Tauer.

We extended the model to Oligopolistic Routing Games, a version where each player is allowed to control an arbitrary number of packets.

This project is contributed by Britta Peis, Björn Tauer, Veerle Timmermanns and Laura Vargas Koch.

Beside this arc-based protocols can be examined:

This project is contributed by Robert Scheffler, Martin Strehler and Laura Vargas Koch.

Furthermore, the first-in-first-out protocol and a randomized protocol can be studied. This is a project of Björn Tauer and Laura Vargas Koch, which is currently in the reviewing process.