Review: Delayed Internet Routing Convergence

Review: Delayed Internet Routing Convergence

Reviewer: Di Niu

This paper examines delayed Internet routing convergence. Through a
two-year experimental study, it breaks the widely held belief that
the Internet supports rapid rerouting in face of link or router
failures. It further shows that during these periods of delayed
routing convergence, end-to-end internet paths will experience
intermittent loss of connectivity, as well as increased packet loss
and latency. Simplified theoretical models are used to provide an
explanation for the rationales behind the observations. The is a
complete and foundational work on the latency of Internet routing
convergence, as it provides both strong experimental studies and
good theoretical explanations to back up the measurement results.

To solve the slow convergence problem of DV routing algorithm, the
inter-domain routing protocol in the Internet called BGP uses the
path vector approach, which includes the entire path to the
destination. And it was incorrectly believed that the path vector
approach can provide BGP with much better convergence properties.
This paper is primarily an effort to break such a wrong idea about
BGP. It demonstrates that the Internet does not support effective
inter-domain failover and that most of the delay in path restoral
stems solely from the unexpected interaction of configurable routing
protocol timers and specific router vendor protocol implementation
decisions during the process of delayed BGP convergence. Moreover,
the path vector exponentially exacerbates the number of possible
routing table oscillations, though it solves the count-to-infinity
problem. Additionally, Internet path failover can adversely affect
the end-to-end perfomance. Specifically, mesaured packet loss grows
by a factor of 30 and latency by a factor of four during path restoral.

Theoretical analysis are used to back up these observations. The
theoretical upper bound on the number of computational states
explored during BGP convergence is Ο(n!), where n is the number of
autonomous systems in the Internet. And the lower bound on BGP
convergence is Ω((n-3)*30) seconds. If minor changes to current
vendor BGP implementations are deployed, the lower bound on inter-
domain convergence time complexity will be reduced to Ω(30) seconds.
Furthermore, in Sec. 6, implications from these theoretical results
are provided to give an explanation for the measurement results in
Sec. 4.

The paper is not without weaknesses. Generally speaking, the paper
covers the whole spectrum of its theme, delayed Internet routing
convergence. The authors conducted a two-year measurement study which
appears very strong. However, its theoretical analysis adopts an
oversimplified model and thus provided results that are not so
valuable. It appears that the authors found through measurement that
routing convergence latency is a problem in the Internet. Later they
deliberately tried to back up there findings with theories.
Unfortunately, the analysis which constitutes the second part of the
paper appears not professional at all. Although the paper is strong
in its idea and its first part, a more theoretically inclined
researcher may find its second part far-fetched. In this sense, the
highlight of this paper is just the presentation of measurement results.
Received on Wed Oct 11 2006 - 22:21:35 EDT