Articles in journals and conference proceedings

• Simon Fischer, Nils Kammenhuber, and Anja Feldmann: REPLEX — Dynamic Traffic Engineering Based on Wardrop Routing Policies. In: Proc. 2nd Conference on Future Networking Technologies (CoNext), Lisboa, Portugal, December 2006. (To appear)
   (371 kB),  (1.3 MB),  (369 bytes)
• Simon Fischer, Harald Räcke, and Berthold Vöcking: Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods. In: Proc. 38th Ann. ACM. Symp. on Theory of Comput. (STOC), pages 653–662, Seattle, WA, USA, May 2006. ACM. DOI: 10.1145/1132516.1132608
   (170 kB),  (361 kB), [abstract] (2.6 kB),  (414 bytes)
  > show abstract

  Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods

  Simon Fischer, Harald Räcke, Berthold Vöcking

  Abstract. We study rerouting policies in a dynamic round-based variant of a well known game theoretic traffic model due to Wardrop. Previous analyses (mostly in the context of selfish routing) based on Wardrop's model focus mostly on the static analysis of equilibria. In this paper, we ask the question whether the population of agents responsible for routing the traffic can jointly compute or better learn a Wardrop equilibrium efficiently. The rerouting policies that we study are of the following kind. In each round, each agent samples an alternative routing path and compares the latency on this path with its current latency. If the agent observes that it can improve its latency then it switches with some probability depending on the possible improvement to the better path.

  We can show various positive results based on a rerouting policy using an adaptive sampling rule that implicitly amplifies paths that carry a large amount of traffic in the Wardrop equilibrium. For general asymmetric games, we show that a simple replication protocol in which agents adopt strategies of more successful agents reaches a certain kind of bicriteria equilibrium within a time bound that is independent of the size and the structure of the network but only depends on a parameter of the latency functions, that we call the relative slope. For symmetric games, this result has an intuitive interpretation: Replication approximately satisfies almost everyone very quickly.

  In order to achieve convergence to a Wardrop equilibrium besides replication one also needs an exploration component discovering possibly unused strategies. We present a sampling based replication-exploration protocol and analyze its convergence time for symmetric games. For example, if the latency functions are defined by positive polynomials in coefficient representation, the convergence time is polynomial in the representation length of the latency functions. To the best of our knowledge, all previous results on the speed of convergence towards Wardrop equilibria, even when restricted to linear latency functions, were pseudopolynomial.

  In addition to the upper bounds on the speed of convergence, we can also present a lower bound demonstrating the necessity of adaptive sampling by showing that static sampling methods result in a slowdown that is exponential in the size of the network. A further lower bound illustrates that the relative slope is, in fact, the relevant parameter that determines the speed of convergence.

  < hide abstract
• Patrick Briest, Piotr Krysta, and Berthold Vöcking: Approximation Techniques for Utilitarian Mechanims Design. In: Proc. 37th Ann. ACM. Symp. on Theory of Comput. (STOC), 2005.
   (179 kB),  (276 bytes)
• Nils Kammenhuber and Lukas Kencl: Efficient Statistics Gathering from Tree-Search Methods in Packet Processing Systems. In: Proceedings of IEEE ICC, 2005.
   (151 kB),  (278 bytes)
• Simon Fischer and Berthold Vöcking: On the Structure and Complexity of Worst-Case Equilibria. In: Proc. 1st Workshop on Internet and Network Economics (WINE), number 3828 of Lecture Notes in Comput. Sci. pages 151–160, Hong Kong, China, December 2005. Springer-Verlag.
   (128 kB), [abstract] (871 bytes),  (480 bytes)
  > show abstract

  On the Structure and Complexity of Worst-Case Equilibria

  Simon Fischer and Berthold Vöcking

  We study an intensively studied resource allocation game introduced by Koutsoupias and Papadimitriou where $n$ weighted jobs are allocated to $m$ identical machines. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash equilibrium for this game w.r.t. the expected maximum load over all machines. The known algorithms for approximating the so-called "price of anarchy" rely on this conjecture. We present a counter-example to the conjecture showing that fully mixed equilibria cannot be used to approximate the price of anarchy within reasonable factors. In addition, we present an algorithm that constructs so-called concentrated equilibria that approximate the worst-case Nash equilibrium within constant factors.

  < hide abstract
• Simon Fischer and Berthold Vöcking: Adaptive Routing with Stale Information. In: Marcos Kawazoe Aguilera and James Aspnes (editors): Proc. 24th Ann. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing (PODC), pages 276–283, Las Vegas, NV, July 2005. ACM.
   (145 kB),  (335 kB), [abstract] (2.2 kB),  (409 bytes)
  > show abstract

  Adaptive Routing with Stale Information

  Simon Fischer and Berthold Vöcking

  We investigate adaptive routing policies for large networks in which agents reroute traffic based on old information. It is a well known and practically relevant problem that old information can lead to undesirable oscillation effects resulting in poor performance. We investigate how adaptive routing policies should be designed such that these effects can be avoided.

  The network is represented by a general graph with latency functions on the edges. Traffic is managed by a large number of agents each of which is responsible for a negligible amount of traffic. Initially the agents' routing paths are chosen in an arbitrary fashion. From time to time each agent revises her routing strategy by sampling another path and switching with positive probability to this path if it promises smaller latencies. As the information on which the agent bases her decision might be stale, however, this does not necessarily lead to an improvement. The points of time at which agents revise their strategy are generated by a Poisson distribution. Stale information is modelled in form of a bulletin board that is updated periodically and lists the latencies on all edges.

  We analyze such a distributed routing process in the so-called fluid limit, that is, we use differential equations describing the fractions of traffic on different paths over time. In our model, we can show the following effects. Simple routing policies that always switch to the better alternative lead to oscillation, regardless at which frequency the bulletin board is updated. Oscillation effects can be avoided, however, when using smooth adaption policies that do not always switch to better alternatives but only with a probability depending on the advantage in the latency. In fact, such policies have dynamics that converge to a fixed point corresponding to a Nash equilibrium for the underlying routing game, provided the update periods are not too large.

  In addition, we also analyze the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e.g., for a replication policy adopted from evolutionary game theory.

  < hide abstract
• Simon Fischer and Berthold Vöcking: On the Evolution of Selfish Routing. In: Susanne Albers and Tomasz Radzik (editors): Proc. 12th Ann. European Symp. on Algorithms (ESA), LNCS 3221, pages 323–334, Bergen, Norway, September 2004. Springer-Verlag.
   (135 kB),  (329 kB), [abstract] (1.1 kB),  (407 bytes)
  > show abstract

  On the Evolution of Selfish Routing

  Simon Fischer and Berthold Vöcking

  We introduce a model to study the temporal behaviour of selfish agents in networks. So far, most of the analysis of selfish routing is concerned with static properties of equilibria which is one of the most fundamental paradigms in classical Game Theory. By adopting a generalised approach of Evolutionary Game Theory we extend the model of selfish routing to study the dynamical behaviour of agents.

  For symmetric games corresponding to singlecommodity flow, we show that the game converges to a Nash equilibrium in a restricted strategy space. In particular we prove that the time for the agents to reach an $\epsilon$-approximate equilibrium is polynomial in $\epsilon$ and only logarithmic in the ratio between maximal and optimal latency. In addition, we present an almost matching lower bound in the same parameters.

  Furthermore, we extend the model to asymmetric games corresponding to multicommodity flow. Here we also prove convergence to restricted Nash equilibria, and we derive upper bounds for the convergence time that are linear instead of logarithmic.

  < hide abstract
• Rene Beier, Artur Czumaj, Piotr Krysta, and Berthold Vöcking: Computing Equilibria for Congestion Games with (Im)perfect Information. In: Proc. 14th Symposium on Discrete Algorithms (SODA), pages 746–755, 2004.
   (178 kB),  (315 bytes)
• Jörg Wallerich, Holger Dreger, Anja Feldmann, Balachander Krishnamurthy, and Walter Willinger: A methodology for studying persistency aspects of Internet flows. In: ACM SIGCOMM Computer Communication Review, 2004.
   (5.3 MB), [ps.gz] (1.7 MB),  (314 bytes)
• Anja Feldmann, Nils Kammenhuber, Olaf Maennel, Bruce Maggs, Roberto De Prisco, and Ravi Sundaram: A Methodology for Estimating Interdomain Web Traffic Demand. In: Proceedings of ACM Internet Measurement Conference, 2004.
   (912 kB),  (354 bytes)
• Amit Agarwal, Tarun Agarwal, Sumit Chopra, Anja Feldmann, Nils Kammenhuber, Piotr Krysta, and Berthold Vöcking: An Experimental Study of k-Splittable Scheduling for DNS-Based Traffic Allocation. In: Proceedings of EURO-PAR 2003, 2003.
   (139 kB),  (384 bytes)

Technical reports and non-refereed articles

• Simon Fischer and Berthold Vöcking: Evolutionary Game Theory with Applications to Adaptive Routing. In: Proc. European Conference on Complex Systems (ECCS), Paris, France, November 2005. (to appear)
   (111 kB), [abstract] (936 bytes),  (325 bytes)
  > show abstract

  Evolutionary Game Theory with Applications to Adaptive Routing

  Simon Fischer and Berthold Vöcking

  One of the most important problems in large communication networks like the Internet is the problem of routing traffic through the network. Current Internet technology based on the TCP protocol does not route traffic adaptively to the injection rates but uses fixed end-to-end routes and adjusts only the injection rates in order to avoid congestion. A more flexible approach uses load-adaptive rerouting policies that reconsider their routing strategies from time to time depending on the current network traffic. In this manuscript, we survey recent results from [FV04] and [FV05] about the application of methods from evolutionary game theory to such an adaptive traffic management.

  Key words: Evolutionary game theory, Wardrop model, adaptive routing, stale information, analysis and dynamics of complex networks

  < hide abstract
• Simon Fischer and Berthold Vöcking: Adaptive Routing with Stale Information. Technical report, AIB-2005-06, RWTH Aachen University, 2005.
   (264 kB),  (564 kB), [abstract] (2.2 kB),  (231 bytes)
  > show abstract

  Adaptive Routing with Stale Information

  Simon Fischer and Berthold Vöcking

  We investigate adaptive routing policies for large networks in which agents reroute traffic based on old information. It is a well known and practically relevant problem that old information can lead to undesirable oscillation effects resulting in poor performance. We investigate how adaptive routing policies should be designed such that these effects can be avoided.

  In our theoretical model, the network is represented by a general graph with latency functions on the edges. Traffic is managed by a large number of agents each of which is responsible for a negligible amount of traffic. Initially the agents' routing paths are chosen in an arbitrary fashion. From time to time each agent revises her routing strategy by sampling another path and switching with positive probability to this path if it promises smaller latencies. As the information on which the agent bases her decision might be stale, however, this does not necessarily lead to an improvement. The points of time at which agents revise their strategy are generated by a Poisson distribution. Stale information is modelled in form of a bulletin board that is updated periodically and lists the latencies on all edges.

  We analyze such a distributed routing process in the so-called fluid limit, that is, we use differential equations describing the fractions of traffic on different paths over time. In our model, we can show the following effects. Simple routing policies that always switch to the better alternative lead to oscillation, regardless at which frequency the bulletin board is updated. Oscillation effects can be avoided, however, when using smooth adaption policies that do not always switch to better alternatives but only with a probability depending on the advantage in the latency. In fact, such policies have dynamics that converge to a fixed point corresponding to a Nash equilibrium for the underlying routing game, provided the update periods are not too large.

  In addition, we also analyze the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e.g., for a replication policy adopted from evolutionary game theory.

  < hide abstract
• Nils Kammenhuber and Lukas Kencl: Efficient Statistics Gathering from Tree-Search Methods in Packet Processing Systems. Technical report, IRC-TR-04-034, Intel Research, 2004.
   (269 bytes)

Theses

• Christian Vollmert: Design and Implementation of a Web Workload Generator for the SSFNet Simulator. Bachelor's Thesis, Technische Universität München, 2004.
   (232 bytes)
• Manuela Mark: Über die Anwendung der evolutionären Spieltheorie auf Selfish Routing. Master's Thesis, Universität Dortmund, 2004.
   (200 bytes)
• Thomas Krämer: IP Traffic Engineering — OSPF vs. MPLS. Master's Thesis, Universität des Saarlandes, 2003.
   (219 bytes)
• Susanne Horst: A Simulation-Based Comparison of an Abstract Transmission Protocol and TCP. Master's Thesis, Universität des Saarlandes, 2003.
   (247 bytes)
• Hagen Böhm: Analysis of OSPFv2–BGP4 Interactions Using the SSFNet Simulator. Master's Thesis, Universität des Saarlandes, 2003.
   (237 bytes)

Other publications

• Anja Feldmann, Nils Kammenhuber, Olaf Maennel, Bruce Maggs, and Ravi Sundaram: A methodology for estimating interdomain Web traffic demand. Poster at ACM SIGCOMM Conference, 2003.
   (320 bytes)