Controlling routing oscillations in adaptive routing protocols

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 [4], 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 [1] 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 [2] 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).

No-regret Routing

In a similar vein of analysis, Blum, et al show in [3] 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".

Closing Thoughts

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 [4], and mathematical analysis [1-3]). One traditional argument against adaptive routing protocols (going back to ARPANet days [5]) 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.

References

• [1] – 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
• [2] – Fischer, S.; Kammenhuber, N. & Feldmann, A. "REPLEX — Dynamic Traffic Engineering Based on Wardrop Routing Policies" Proc. 2nd Conference on Future Networking Technologies (CoNext), 2006
• [3] – 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
• [4] – Gao, R.; Dovrolis, C. & Zegura, E. "Avoiding Oscillations due to Intelligent Route Control Systems" IEEE Infocom, 2006
• [5] – 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!

Advertisement

Packet Reordering

I’ve been doing some literature surveys recently on the topic of measuring Packet Reordering, and, for what should be a simple thing to quantify, it has a surprisingly large body of research. In this post, I’ll talk about packet reordering, why it’s important to consider, and approaches to quantify it.

What is Packet Reordering?

When a sender generates a traffic stream (this could be anything, from TCP traffic, to real-time Voice or Video) it generates an in-order sequence of data packets. Due to any number of causes which we discuss below, there may be a chance that the ordering of the packets received at the destination is different from that which the sender generated. This phenomenon we refer to as reordering.

In their IMW 2002 paper [1], Jaiswal, et al cite 3 main causes for packets being received in a different order than they were generated by the source:

• Retransmission. In this case a sender infers that a packet has been lost and retransmits the packet. The retransmitted packet will have a sequence number that is smaller than previously observed packets at the measurement point and hece will be deemed “out-of-sequence.”
• Network duplication. In this case, a non-sender-retransmitted copy of a packet is observed. This can occur when the measurement point is within a routing loop (and hence the same packet is observed more than once), or if the network itself creates a duplicate copy of the packet
• In network-reordering. In this case, the network inverts the order of two packet in a connection (for example, because of parallelism within a router or a route change

In the full version of their paper, delivered at INFOCOMM 2003 [2], Jaiswal, et al present the results of a large measurement study into the extent of reordering in the Internet. Their work has a number of methodological contributions for the classifying TCP packets observed in the network backbone. From their study, they found that many of the out-of-order packets observed in the network were due to retransmissions, and only a small fraction of packets (on the order of 1%, on average) were re-ordered by the network.

Why is it a problem?

Bennett, et al [3] enumerate five negative consequences of reordering on TCP traffic:

1. Reordering causes unnecessary retransmissions
2. Reordering makes it difficult or impossible to grow TCP’s congestion window
3. Reordering can cause actual packet losses to be obscured, so that TCP retransmits lost packets later than it normally would
4. Reordering may cause the round-trip estimator to poorly estimate the round-trip time
5. Reordering may reduce the efficiency of the receiving TCP

How can we measure it?

A straight-forward method for measuring the number of out-of-order packets in the network is to consider any packet that has a sequence number that is smaller than that of a previously observed packet in that connection [1]. This is also known as the Type-P-Reordered metric in [4].

This approach has the advantage that it is simple to compute, and it results in a single metric. However, this simplicity results in subtle problems that have been highlighted by various researchers. One particular drawback to is that a single out-of-order packet with high sequence number will classify many subsequent packets as reordered, skewing the results. This has caused some researchers to call for a more sophisticated metric to take into account the degree of reordering.

One approach proposed by Piratla et al in [5] is known as reorder density, which, instead of a single value for desequencing, results in a histogram of reordering, whereby the degree to which a packet arrived reordered is taken into account. They compare their method with many other proposed reordering metrics in [6].

Conclusion

I hope this has given you an overview of what Packet Reordering is, why it is harmful to network flows, and some of the ways that it can be measured.

For further references on this topic, a great resource has been created here by Dr. Piratla.

References

• [1] – Jaiswal, S.; Iannaccone, G.; Diot, C.; Kurose, J. & Towsley, D. “Measurement and classification of out-of-sequence packets in a tier-1 IP backbone” IMW ’02: Proceedings of the 2nd ACM SIGCOMM Workshop on Internet measurment, ACM Press, 2002, 113-114
• [2] – Jaiswal, S.; Iannaccone, G.; Diot, C.; Kurose, J. & Towsley, D. “Measurement and classification of out-of-sequence packets in a tier-1 IP backbone” INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications Societies. IEEE, 2003, 2, 1199-1209
• [3] – Bennett, J. C. R.; Partridge, C. & Shectman, N. “Packet reordering is not pathological network behavior” IEEE/ACM Trans. Netw., IEEE Press, 1999, 7, 789-798
• [4] – Morton, A.; Ciavattone, L.; Ramachandran, G.; Shalunov, S. & Perser, J. “Packet Reordering Metric for IPPM” 2006
• [5] – Piratla, N. M.; Jayasumana, A. P. & Bare, A. A. “Reorder Density (RD): A Formal, Comprehensive Metric for Packet Reordering.” Proc. IFIP Networking Conference, 2005, 78-89
• [6] – Piratla, N. M.; Jayasumana, A. P. & Bare, A. “A Comparative Analysis of Packet Reordering Metrics” COMSWARE, 2006