Review - Delayed Internet Routing Convergence

Review of Delayed Internet Routing Convergence
by Ivan Hernández

The paper describes the excessive delay in inter-domain routing
failover, mainly provoked by not good BGP implementations. The authors
analyzed BGP's performance and behavior based on the data collected
in a two year study using actual Internet infrastructure in which they
were able to interact with five ISPs. The experimental methodology is
very complete and they were able to collect large amounts of data. The
experimental results show the performance (in term of configuration
message) and latency of the routers in failover and route repair; the
results also show the impact of the failover latency on end hosts.

One interesting part of the paper is when the authors present a BGP
convergence model. Of course, it is a simplified model, nevertheless
it is very useful to do the analysis and find out what are the
reasons that provoke the excessive delay in BGP failover. Using the
model, the authors present several observations and consequences on
BGP failover performances, the main result here is the upperbound on
the number of computational states explored during BGP convergence,
this is O(n!), with n the number of ASes. Next, the authors improve
the performance of the BGP in failover using a timer, MinRouteAdver,
used to form rounds. Timer forces a node to process all (n-1)
announcements from its neighbors before it can send out a new update;
thus, in each round, will only be announced longer paths that in the
previous round. The timer provides a global synchronization that gets
rid of (k-1)-length paths before the nodes announce k-length paths.

The authors highlight that the BGP's specification requires ASPath
loop, nevertheless the spec does not define where the detection should
take place. The authors observe that if the detection take place in
the sender and receiver, BGP's failover performance would
improve. Finally they do simulations of the original BGP, timer-BGP,
and timer-BGP with loop detection. The best performance is achieved by
the last version.

I liked this paper, it is well written all ideas are clearly
explained. In the paper we can see the impact of bad implementations
and implementations that interpret protocol specifications in
different ways. The authors collected an impressive amount of data
for 2 years, and it was show in only six figures in the paper!
Received on Wed Oct 11 2006 - 19:14:36 EDT