Controlling routing oscillations in adaptive routing protocols
Posted by Michael Gellman on November 20, 2006
I’ve been doing some work on ways to eliminate routing oscillations in an adaptive routing protocol. There’s a very good analysis using simulations in , but the current question I am investigating is whether there exists some analytical method for showing that the protocol will not oscillate, and, if so, how long does that take. One (very) well-developed field that has the potential to answer this question is that of Game Theory.
Price of Anarchy
One of the best introductions to this topic that I found was a research monograph of Tim Roughgarden’s Ph.D. Thesis Selfish Routing and the Price of Anarchy. The pace is good for setting the stage of how game theory, and specifically notions of Nash equilibrium, can be used to analyze networks. However, one of the assumptions that the analysis makes is that the routing system will tend to equilibrium — which is exactly what we are questioning. Thus, I continued my search into some more recent work.
Convergence to Wardrop Equilibrium
It is here that I came across the work of Simon Fischer, et al which uses notions going back to the 50’s in traffic networks to demonstrate convergence of on-line routing algorithms. At STOC 2006, they published a paper  analyzing an adaptive routing protocol, giving an upper bound on the number of rounds it takes to reach equilibrium "that is independent of the size and the structure of the network". It depends principally on a parameter of the latency function which they call its relative slope. They then extend this theoretical work with a set of simulations  to be presented at this year’s CoNEXT conference. Using bursty traffic on both artificial and real topologies, they show that an implementation of their protocol in a traffic engineering context can lead to good on-line performance without oscillations (for suitable parameters).
In a similar vein of analysis, Blum, et al show in  that no regret online routing algorithms approach a Nash equilibrium "at a rate that depends polynomially on the players’ regret bounds and the maximum slope of any latency function".
The question of whether adaptive routing protocols converge to an equilibrium or whether they oscillate ad infinitum is an important research question that is being addressed in different ways (e.g. experiments, simulation , and mathematical analysis [1-3]). One traditional argument against adaptive routing protocols (going back to ARPANet days ) is that they are unstable due to their selfish nature. This new body of evidence is gathering support for truly adaptive routing protocols which give good QoS to traffic in a completely distributed manner, all the while having good convergence properties.
-  – Fischer, S.; Räcke, H. & Vöcking, B. "Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods" Proc. 38th Ann. ACM. Symp. on Theory of Comput. (STOC), ACM, 2006, 653-662
-  – Fischer, S.; Kammenhuber, N. & Feldmann, A. "REPLEX — Dynamic Traffic Engineering Based on Wardrop Routing Policies" Proc. 2nd Conference on Future Networking Technologies (CoNext), 2006
-  – Blum, A.; Even-Dar, E. & Ligett, K. "Routing without regret: on convergence to nash equilibria of regret-minimizing algorithms in routing games" PODC ’06: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, ACM Press, 2006, 45-52
-  – Gao, R.; Dovrolis, C. & Zegura, E. "Avoiding Oscillations due to Intelligent Route Control Systems" IEEE Infocom, 2006
-  – McQuillan, J.; Richer, I. & Rosen, E. "The New Routing Algorithm for the ARPANET" Communications, IEEE Transactions on [legacy, pre – 1988], 1980, 28, 711-719
Please comment to this post if you know of other references that are of interest, or additional points about the references I selected!