Summary: Delayed Internet Routing Covnergence

The paper discusses the impact and the rate at which inter-domain repair
and failure information propagates through the Internet. Especially the
paper focuses on BGP and measures the impact of Internet path changes on
end-to-end network performance. The motivation here is to develop Internet
infrastructure that ensures minimal packet loss even during the periods of
delayed convergence.

BGP is an incremental protocol that sends update information upon the
changes in the network topology or routing policy. BGP announcements and
withdrawals to communicate the changes to the other AS. Faults were
injected using fault injection server and router views are probed using
another server. Various simulations were conducted on the 5 real AS, that
are well distributed over the Internet, to study the latency of four
injected events: Tup, Tdown, Tshort, and Tlong. The routing measurements
indicate that both Tdown and Tlong converged more slowly than Tup and
Tshort. They also show that delay in inter-domain path fail overs averaged
three minutes during the period of two years.

The paper brings out several key observations that lead to delayed
convergence of BGP protocol:
1)BGP bouncing problem leads to exploration of ever increasing ASPath
lengths and generation of large numbers of update massages during
convergence. This merely illustrates how adoption of path vector policy in
BGP exacerbates the bouncing problem.
2)Unlike traditional DV algorithms, BGP convergence is monotonically
increasing and it has n! Possible paths in a network n nodes.
3)The theoretical upper bound on the number of states in BGP is O(n!).
However, the communication complexity of the number of
messages(announcements and withdrawals) is much larger than n!.
4)Lower bound of the BGP requires n-3 rounds of MinRouteAdver timer in a
complete graph of n nodes.
5)The paper suggests using modified MinRouteAdver that will ensure BGP
converges within the thirty second round. Though communication complexity
remains the same, modified MinRouteAdver timer exhibits improved state
complexity thus leading to better convergence.
6)BGP allows the administrator of an autonomous system to specify
arbitrarily complex policies. The paper demonstrates that observed
convergence delays stems from the these vendor specific router
implementation decisions and ambiguity in BGP specification.

The analysis of measurement results over the two years show that Internet
path fail over has significant impact on the end to end performance.
measured packet loss grows by a factor of 30 and latency by a factor of
four during path rest oral.

However, I thought the practical impact of having large oscillations was
not clear in this paper. They could have measured impact on some sample
applications to understand the impact in a better way. Though this paper
claims that BGP has theoretical lower and upper bounds, it seems like
these bounds are not applicable in practice.
Received on Thu Oct 12 2006 - 09:30:57 EDT