| [home] - [up] |
Abstract: In this lecture, we will survey results on the price of anarchy and the price of stability that have recently been established in a series of papers on selfish routing in multicommodity flow networks. We will give simplified proofs for some of these results, and strengthen others. Many results hold in the more general context of congestion games, which provide the framework in which we describe this work. If time permits, we will also address related aspects such as the complexity of finding a pure-strategy Nash equilibrium and the concept of "Nashification."
Colloquium - 16:00
Abstract: Telecommunication network design problems usually consist in installing hardware at the nodes and capacities on the links of a network, such that given communication demands can be satisfied. To this end, many mathematical models and algorithms have been developed and successfully applied to real-world networks.
However, most of the existing models ignore the layered structure of practical telecommunication networks, where different layers use different technologies and routing protocols (e.g., IP, MPLS, ATM, SDH, or WDM). A multi-layer routing is nested, i.e., the links of a routing path in one layer may actually be paths in another layer. As these interdependencies between different layers make multi-layer network planning difficult, a common approach in practice is the subsequent planning of one layer after the other. In the Matheon project B3, we aim at developing models and algorithms for an *integrated* planning of several network layers.
In this talk, our approach to multi-layer network design problems will be presented. After an introduction to the practical planning problem, our integer programming models for hardware and routing in a multi-layer network will be described. Eventually, a sketch of the planned algorithmic approach will be given and discussed.