Title: Network Sensitivity to Intradomain Routing Changes

Abstract:

In a large transit IP network, hosts outside the network originate and
consume most of the traffic. This implies that the network performance and
robustness is determined by both intradomain and interdomain routing.
Despite the architecture separation between these two classes of routing
protocols in the Internet, intradomain protocols do influence the
path-selection process in the Border Gateway Protocol (BGP). When there
are multiple (equally good) BGP routes available for a given destination,
BGP selects the route associated with the closest egress point based upon
intradomain path costs. Under such hot-potato routing, BGP-level routes to
destinations that connect to the network in multiple points (such as
multi-homed customers and destinations learned from peers) may change
because of intradomain routing changes.

This talk looks at the unforeseen implications of the interaction between
intra and interdomain routing. First, I present the results of our
analysis of the influence of intradomain routing changes on BGP routing in
a large tier-1 ISP network.  We found that intradomain routing changes
trigger a significant number of BGP updates.  For example, we have
measured some instances in which more than half of a router's BGP table
changed because of a single intradomain routing event.  In addition, we
discovered that BGP routing changes triggered by intradomain events can
take more than a minute to converge, which may lead to transient
forwarding instabilities.  We call these abrupt swings of external routes
"hot-potato disruptions". Applications such as voice, streaming, and
gaming are particularly sensitive delays and losses caused by these
disruptions.

As a result, there is a need for guidelines and tools to assist in the
design of networks that minimize hot-potato disruptions. However,
developing these tools is challenging due to the complex and subtle nature
of the interactions between exterior and interior routing. We address
these challenges using an analytic model of hot-potato routing that
incorporates metrics to evaluate network sensitivity to hot-potato
disruptions.  After describing this model, I demonstrate its utility by
analyzing the sensitivity of a large tier-1 ISP network.

More info on this work can be found at:

Renata Teixeira is a Ph.D. student at the University of California, San
Diego in the Department of Computer Science and Engineering. She received
her B.Sc. in Computer Science and M.Sc. in Electrical Engineering from
Universidade Federal do Rio de Janeiro, Brazil in 1997 and 1999,
respectively. Her research interests are in measurement and analysis of
routing protocols, and in management of large IP networks.