Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

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, eg., for a replication policy adopted from evolutionary game theory.

REFERENCES

• 1: M. Beckmann, C. B. McGuire, and C. B. Winsten. Studies in the Economics and Transportation. Yale University Press, 1956.
• 2: Richard Ernest Bellman and Kenneth L. Cooke. Differential-Difference Equiations, volume 6 of Mathematics in Science and Engineering. Academic Press, 1963.
• 3: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and distributed computation: numerical methods, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 4: William E. Boyce , Richard C. Diprima, Elementary Differential Equations With Mathematica, John Wiley & Sons, Inc., New York, NY, 1997
• 5: Jianhua Cao and Christian Nyberg. An approximate analysis of load balancing using stale state information for servers in parallel. In Proc. 2nd IASTED Int. Conf. on Communications Internet and Information Technology, November 2003.
• 6: Michael Dahlin, Interpreting Stale Load Information, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1033-1047, October 2000 [doi>10.1109/71.888643]
• 7: Rodney D. Driver. Existence and stability of solutions of a delay-differential system. Arch. Rational Mech. Anal., 10:401--426, 1962.
• 8: Simon Fischer and Berthold Vöcking. On the evolution of selfish routing. In Proc. 12th Ann. European Symp. on Algorithms (ESA), Lecture Notes in Comput. Sci. 3221, pages 323--334. Springer-Verlag, September 2004.
• 9: Alain B. Haurie and Patrice Marcotte. On the relationship between Nash-Cournot and Wardrop equilibria. Networks, 15:295--308, 1985.
• 10: A. Khanna , J. Zinky, The revised ARPANET routing metric, Symposium proceedings on Communications architectures & protocols, p.45-56, September 25-27, 1989, Austin, Texas, United States
• 11: James F. Kurose , Keith W. Ross, Computer Networking: A Top-Down Approach Featuring the Internet, Pearson Benjamin Cummings, 2004
• 12: Michael Mitzenmacher, How useful is old information (extended abstract)?, Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing, p.83-91, August 21-24, 1997, Santa Barbara, California, United States [doi>10.1145/259380.259426]
• 13: Jennifer Rexford. Hand of Optimization in Telecommunications, chapter Route optimization in IP networks. Kluwer Academic Publishers, 2005.
• 14: Tim Roughgarden, How unfair is optimal routing?, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.203-204, January 06-08, 2002, San Francisco, California
• 15: Tim Roughgarden , Éva Tardos, How bad is selfish routing?, Journal of the ACM (JACM), v.49 n.2, p.236-259, March 2002 [doi>10.1145/506147.506153]
• 16: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 17: John Glen Wardrop. Some theoretical aspects of road traffic research. In Proc. of the Institute of Civil Engineers, Pt. II, pages 325--378, 1952.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.m Miscellaneous

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
(evolutionary) game theory, adaptive routing, stale information