Selfish vs. Greedy: Network routing with limited control

Teacher

Patrizio Angelini, Universitaet Tuebingen (p.angelini at gmail.com)

Abstract

In most of the real-world networks it is not possible to perform a centralized control over the traffic and to impose globally-optimal routing strategies to the network entities. Thus, each of such entities selects routes for its traffic with the sole aim of minimizing its own costs, rather than the global social costs. In this sense, most of the existing routing schemes are to be regarded as selfish. Typical settings in which selfish routing appears include packet routing in computer networks and vehicle traffic in road networks.

In general, the lack of cooperation among network entities with conflicting interests results in a degradation of the network performance with respect to a centralized routing scheme aiming at minimizing the global costs. In order to estimate this degradation, selfish routing has been studied in the general framework of game theory. In this setting, the price of anarchy is the ratio between the social cost of a Nash equilibrium and the one of a globally-optimal routing.

In this series of lectures we introduce basic concepts of game theory, useful to study selfish routing in this framework, and we revise some of the main results in this area. In particular, to estimate the worst possible loss in network performance due to selfish behavior, we present some upper bounds on the price of anarchy. Then, we discuss the computational complexity of the problem of computing the price of anarchy of a given network. Finally, we study how to design networks in which the price of anarchy is reasonably low.

Then, we move our attention to specific types of networks in which, together with a lack of a centralized control, one has to face the additional problem that the routing entities cannot have a complete knowledge of the whole network structure when selecting routes. This is the case, in particular, for wireless sensor networks, due to the limited computation capabilities of the sensors.

In these networks, the delivery of the packets is controlled by a geographic routing scheme, which is characterized by the fact that sensors take their routing choices only based on geographic coordinates, and not on the usual network protocols addresses. Among these schemes, the simplest and most used one is the so-called greedy routing. Here, each sensor sends its packet to any of its neighbors that is closer than itself to the destination.

Greedy routing is simple, as it only requires each sensor to know and transmit its own coordinates, and to perform few basic computations. However, the necessity of installing GPS antennae on the sensors makes it not effective in terms of energy consumption. Further, the routing may get stuck at a vertex that is closer to the destination than all of its neighbors, but that is not connected to it due to the presence of geographic obstacles.

To avoid these two drawbacks, Rao et al.~[MobiCom ’03] proposed a scheme in which the routing is based on fictitious virtual coordinates, rather than on the real ones. In order for this scheme to be useful, one has to assign virtual coordinates so that the greedy routing is guaranteed to succeed. A set of coordinates with this property determines a greedy embedding of the network.

Greedy embeddings have been first defined and studied in a setting in which the virtual coordinates to be determined belong to the standard 2-dimensional Euclidean space. However, since these virtual coordinates are totally independent from the original geographic location of the sensors, one can consider coordinates belonging to any possible metric space. In fact, greedy embeddings have been studied in the 2-d and 3-d Euclidean space, in the hyperbolic space, and in some other spaces that are based on suitably defined metrics.

In the second part of the course we consider the main results in the research area of computing greedy embeddings of networks, mainly focusing on the original Euclidean space. In particular, we provide algorithms to construct greedy embeddings of different types of networks, and examples of networks that do not admit such embeddings. Further, we consider the problem of constructing succinct embeddings, that is, ones in which the virtual coordinates can be described by means a logarithmic number of bits, an important property to make greedy embeddings useful in practice.

Program

Lecture 1
– Introduction to network routing
– Elements of game theory
– Model and first examples for selfish routing
– Computing the price of anarchy

Lecture 2}
– Upper bounds for the price of anarchy
– Inapproximability results for computing the price of anarchy
– Coping with selfish routing

Lecture 3
– Geometric and greedy routing in wireless sensor networks
– Definition and basic geometric properties of Euclidean greedy embeddings

Lecture 4
– Euclidean greedy embeddings of trees: characterizations and area requirements
– Algorithms for Euclidean greedy embeddings of maximal and triconnected planar graphs

Lecture 5
– Planar Euclidean greedy embeddings
– Greedy embeddings in non-Euclidean metric spaces
– Succinct greedy embeddings

Primary Material

Software resources

Credits 3

Length 5 lectures

November 6-7-8-9-10, 2017; 14:30 -16:00;  Sala riunioni Sezione di Informatica e Automazione