Shvetank: Delayed Internet Routing Convergence

CSC220906AU16
-------------------------------------------------------------------------------------------------------------------
Motivation: This paper examines the latency in internet path failure.
failover and repair due o the convergence properties of internet domain
routing. It suggests some specific changes to BGP implementations but is
afraid that it would be at the expense of a more complex protocol and
increased router overhead.

Key Points:

1) An important observation made is that the delay in inter-domain path
failovers averaged three minutes during the two years of study and some
percentage of failovers triggered routing table oscillations lasting
upto fifteen minutes. Moreover, internet path failover has significant
impact on performance as measured packet loss grows by a factor of 30
and latency by a factor of four during path restoral.

2) The methodology adopted for evaluation is injection of faults
consisting of BGP update messages including route transitions.

3) The routing events {route repair, route repair and failover} and
{route failure,route failure and failover} seemed to form an equivalent
class with respect to convergence latency and number of update messages
they trigger.

4) The delays obtained show no correlation between convergence latency
and geographic or network distance. Instead, analysis shows that these
variations directly relate to a number of topological factors including
the length and number of possible paths between an AS ad a given
destination.

5) Moderate levels of routing table oscillations led to increased packet
loss, latency and out of order packets. These performance problems arise
as routers drop packets for which they do not have a valid next hop or
queue packets while awaiting the completion of forwarding table
cache updates.

6) Its observed that the most significant difference between the
convergence behavior of traditional DV algorithms and BGP is that DVs
are strictly increasing whereas BGP is monotonically increasing. BGP
convergence has been studied to provide an upper and lower bound on
convergence time.

7) In the absence of a fixed timer such as MinRouteAdver, the order in
which announcements are processed at a node influences the rate of
convergence for a path-vector algorithm. The primary effect of
MinRouteAdver timer is to impose a monotonically increasing path metric
for successive iterations, thus imposing a global state synchronization
reducing the computational and communication complexity of BGP convergence.

These delay results of BGP convergence time suggest a strong need to
reevaluate the applications and protocols including the emerging QoS and
VoIP standards that assume a stable underlying intern-domain forwarding
infrastructure and fast IP path restoral.
Received on Thu Oct 12 2006 - 11:10:56 EDT