Delayed Internet Routing Convergence April 23, 2009

Three Important Things:

• There is common acceptance that the internet in its current form is robust and efficient in adjusting routes in the face of link failures. Such occurrences are fairly common in such a huge infrastructure, and the authors recognized that it would be valuable to evaluate this accepted belief. By evaluating BGP convergence they came to the conclusion that inter-domain failover has significant delay, and that the path vector approach is incorrectly believed to provide improved convergence properties over distance vector routing. The claim is that the delay stems from ambiguity in the BGP protocol, and varying implementations across different router vendors.
• The paper was focused on experimental trails conducted over a long period of time, lending strength to the obtained results. The authors emphasize several points about designing and executing their experiments in order to produce quality, meaningful, relevant results.  Faults were injected into the actual internet backbone as opposed to a simulation environment. Latency effects were measured at the router level by routing ISP routing tables, this allowed the examination of several events: route repair, route failure, repair and failover, failurea and failover. End-to-end measurements were performed to determine the application level impact, the results proved that even moderate routing table flux caused packet loss, increased packet latency, and out-order-delivery.
• In addition to the hard data, the authors provide theoretical lower and upper bounds. The exploration of these bounds resulted in several insights about delayed convergence. For example, a lack of minimum route advertisement interval timer in some implementations influences the order in which link updates are processed, which impacts the rate of convergence. There are numerous implementation variations across vendors that contribute to the performance bounds.

Glaring Problem:
A major concern that I had with this work is that it only focues on BGP, and that it didn’t really discuss the parallels between inter-domain and intra-domain results. It would have been useful to see how the obtained results pertained to other routing protocols, if at all.

Future Work:
Following this thorough treatment of BGP convergence analysis, it would be useful to follow up on the root causes of delayed convergence and try to design new protocols, or at least new features in future routers that could help alieviate the strain on the internet backbone.  These topics were mentioned in the paper, but not at length. Such research would be crucial to the continued viability of the internet from a QoS perspective.

An Experimental Study of Delayed Internet Routing Convergence April 23, 2009

This paper presents the results of a very comprehensive study of routing convergence behavior on the internet. By monitoring the internet in many different places while injecting routing faults at various points in the network, they were able to measure in great detail the effects of such faults on both the routing tables themselves and their effect on end users.

They present a few important conclusions. The first is that the amount of time it takes for new routes to stabilize after a fault is actually much longer than previously thought. In addition to this insight, they have discovered that this delay will increase linearly in the best case and exponentially in the worst case with the number of additional autonomous systems on the internet. This presents a significant challenge to the designers of internet routers, especially if the growth rate increases more exponentially than linearly.

Their second conclusion is that much of this large failover time is due to differences in how vendors implement the BGP specification. If more loop detection was done by the sender instead of just at the receiver, the number of total updates could be reduced dramatically. However, this adds complexity to routers which are likely already quite expensive and complicated to design.

A third conclusion they arrive at is that different classes of update traffic have different behavior with regards to the amount of time and number of messages necessary to reach routing convergence. The loss of a route causes messages which are monotonically increasing while the addition of a route causes messages which are strictly increasing. While this may not seem like a significant difference, it actually has a profound effect on the convergence time, since it can take a long time for a faulted route to disappear from the system as routers bounce messages back and forth slowly increasing their distance to the faulted route until eventually they all realize that it is no longer present. This is in contrast to an added route, which either creates a shorter path which is propagated, or doesn’t, and doesn’t generate any new routes.

A weakness of this paper is that their bounds on the convergence rate of routes are fairly loose. While it is valuable to know that it is at least linear, the upper bound is quite high and does not necessarily describe the behavior accurately. However, since the growth rate is at least linear, future research needs to focus on ways to either improve BGP or supplant it with something more intelligent, which is less susceptible to implementation dependencies and superfluous messages during routing convergence.

An Experimental Study of Delayed Internet Routing Convergence April 23, 2009

Major Contributions

1. This paper presents the results of a two year study on the convergence of the BGP routing protocol and provides recommendations to reduce convergence time and overhead mainly caused by BGP routers with different implementations due to the ambiguity of BGP specs. RouteView data collection probe was used to log and timestamp all BGP updates from BGP routers of vaious ISPs. Results show that failover delay is independent of network load, congestion, locality and more dependent on topology.

2. A fault injection server was used to inject BGP faults to upstream ISPs and measure the latency to random websites. The failure injection measurement results were taken for BGP events Tup, Tdown, Tshort, and Tlong and measured how long it takes for all the route tables to converge following an event. Tup is a previously unavailable route is now available. Tdown is the opposite of Tup. Tshort is a long ASPath is now replaced by a shorter ASPath. Tlong is the opposite of Tshort. From the distribution of convergence latencies following Tlong, Tdown, Tshort, and Tup faults,  the authors find that Tlong and Tdown form one equivalence class, and Tshort and Tup formed another equivalence class. Tlong and Tdown took almost three times the amount of time to converge compared to Tshort and Tup events. Analysis showed that Tlong and Tdown took longer because it is monotonically incrasing compared to strictly increasing for Tshort and Tup events. The results also show that RTT latency to random websites increased by a factor of four following a failover event and packet loss increased by a factor of 30.

3. The paper provides vendor specific recommendations to reduce convergence lower bound to 30 seconds by analyzing changes to MinRouteAdver using simulation data. The recommendation is to implement both sender and receive side ASPath loop detection, and do not apply MinRouteAdver to Tdown withdrawals.

The most glaring problem is not answering the question of how often these rare long convergence delays occur and whether BGP can still scale without much modification given some constraints on topology.

With routers getting faster, further research considerations with implementing additions or modifications to BGP to improve convergence times using synchronization, diffusing updates, and having additional state information may be feasible. Further research can also consider a complete overhaul or replacement of BGP.

An Experimental Study of Delayed Internet Routing Convergence April 23, 2009

The paper takes a critical and look at BGP route convergence in the face of failover/updates. It provides empirical measurements of real Internet latencies and packet losses for a period of over 2 years as well as theoretical analysis for worst and best case complexity of the route convergence process.

The paper brings to light the fact that most of the failovers measured during the 2 year period took an average of 3 minutes to converge. This observation provides hard statistical evidence that there are considerable BGP inefficiencies. Moreover, this duration length is considerably higher as compared to telephone network failovers. The underlying point here being that the network infrastructure supporting the Internet should be as efficient at resolving failures as the telephone network, especially given the increasing reliance on the Internet for business purposes.

The paper also analyzes the BGP protocol from a theoretical perspective. Given a completely connected graph model for the Internet and certain message ordering and processing constraints, the authors show that unbounded delay BGP messages can result in Ο((n-1)!) states. This is of course the upper bound, but it provides insight into how the network topology and BGP router processing details can affect route convergence. Additionally, the authors point out that a lower bound also exists for router states (or rounds as termed in the paper). If the BGP routers adhere to the minimum route advertisement delay and process messages of route length in increasing order (among other constraints), the lower bound is Ω(n).

Lastly, as a result of the analysis on the lower bound for rounds/states, the authors provide implementation suggestions and optimizations to reduce the lower bound to Ω(1). The minor changes to BGP implementations include performing sender and receiver loop detection and using peerwise MinRouteAdvert times. These suggestions allow routers to converge in one round. The paper provides simulation results that explore the unbounded, MinRouteAdvert, and modified (as per suggestions) MinRouyteAdvert implementations of BGP. These results validate the theoretical implications made by the authors.

The paper is a solid presentation of simulation, theoretical analysis, and real world observation/experimentation results. The only criticism is that the authors make the comparison between the public switched telephone network and the Internet. This isn’t necessarily a fair comparison as the telephone networks were designed with a dedicated single purpose, presumably using the same underlying technology throughout. The Internet serves considerably larger topologies, provides numerous varying uses, and runs on a myriad of technologies. Providing faster failure convergence is a great endeavor, but comparing against the telephone network may be too ambitious.

I think the path for further research would be to implement some of the suggestions and perform a long term test of the efficacy of the modified MinRouteAdvert protocol.

An Experimental Study of Delayed Internet Routing Convergence April 19, 2009

Convergence time of routing information and packet loss and delay due to inter-domain route changes, longer than expected.

Paper carries out experiments and analyses data collected to determine the average time taken before inter-domain routing information reaches steady state after there has been a change in the topology of an Autonomous System (AS). Data was collected by injecting routing faults into five major ISPs over a period of two years. In one of its experiments the paper observes that  20% of nodes require more than 3 minutes to converge for a Tdown or Tlong update.

Factors convergence time depends on.

The paper makes mention of some interesting factors convergence time depends (and does not depend) on. It provides experimental proofs and reasoning to support its claims. Some of them are:

i) Order in which route-change announcements are processed at a node

ii) Number of interconnections between AS (number of BGP peers). A complete graph would have larger number of computational states to be explored during convergence.

iii) Upstream provider transit property.

iv) If loop detection is done at only the receiver or both the sender and the receiver.

v) Largely independent of network load and congestion.

vi) Independent of geographical location of the node.

T-long and T-down have longer convergence times and why.

In the experimental data gathered by the paper it can be noted that convergence time and latencies are larger when the topology change involved a route going down. This might have resulted in a node becoming inaccessible or a longer route having to be taken. The paper analyses the sequence of events that occur when a route disappears and the how this results in T-down and T-long requiring longer convergence times as compared to T-short and T-up. In the case of T-down, a node keeps failing over to a longer secondary path before it exhausts all of them and realizes that the destination node is no longer available.

Problems/Oversights.

A couple of assumptions the paper makes in its experimental methods might not accurately model internet. Some of them are:

- It monitors the routing tables of only 25 ISPs. This might or might not correctly reflect packet forwarding and updating times over internet. More ISPs would mean more locations from which updates might reach a node.

- It models BGP messages to be processed in a single linear queue. This only models the case where there exist high congestion and long delays over the internet.

Future Work

The new system can be modeled which imbibes in itself factors claimed by the paper to reduce convergence times. These could involve, among others, sender and receiver end loop detection, re-ordering of announcements received to reduce convergence times, etc. This new system could be analyzed to obtain a quantitative measure of the enhancement that can be achieved at adding some amount of complexity to the internet protocol.