URL: http://www.cs.rutgers.edu/dataman/552dir/papers/lab99.pdf Entry Date: 2003-05-14 Abstract: This paper examines the network routing messages exchanged between core Internet backbone routers. Internet routing instability, or the rapid fluctuation of network reachability information, is an important problem currently facing the Internet engineering community. High levels of network instability can lead to packet loss, increased network latency and time to convergence. At the extreme, high levels of routing instability have led to the loss of internal connectivity in wide-area, national networks. In an earlier study of inter-domain routing, we described widespread, significant pathological behaviors in the routing information exchanged between backbone service providers at the major U.S. public Internet exchange points. These pathologies included several orders of magnitude more routing updates in the Internet core than anticipated, large numbers of duplicate routing messages, and unexpected frequency components between routing instability events. The work described in this paper extends our earlier analysis by identifying the origins of several of these observed pathological Internet routing behaviors. We show that as a result of specific router vendor software changes suggested by our earlier analysis, the volume of Internet routing updates has decreased by an order of magnitude. We also describe additional router software changes that can decrease the volume of routing updates exchanged in the Internet core by an additional 30 percent or more. We conclude with a discussion of trends in the evolution of Internet architecture and policy that may lead to a rise in Internet routing instability. Datasets: BGP updates collected over 28 months (Mar 96 to Jun 98) at 5 U.S. exchange points: AADS, Mae-East, Mae-West, PacBell, and Sprint Results: Quoting and paraphrasing from paper:

• The volume of inter-domain routing updates has decreased by an order of magnitude since April 1997. For the first time since the end of the NSFNet, the number of BGP announcements has surpassed the number of withdrawals.
  • most of decrease in redundant withdrawals caused by stateless BGP implementations
• The majority of BGP messages consists of redundant, pathological announcements.
• The number of BGP announcements per day almost doubled over the 28 months, while the routing table did not grow in proportion.
• Fluctuation in prefix reachability information accounted for over 40% of all non-WWDup updates (updates other than redundant withdrawals).
• An average of 10-15% of BGP updates were AADiff (implicit withdrawal with different path attributes); these represent policy changes or pathological behavior.
  • on average, only 20-30% of all AADiffs involve AS path changes
  • oscillation in the community, aggregator, next hop, and origin attributes accounted for a combined total of 10% of all AADiffs
  • oscillations in MED constituted the single largest category of AADiffs, averaging between 25% and 40% in the last 11 months of the study; 90% of these oscillations caused by just two ISPs that dynamically computed MED values of eBGP routes from IGP metrics
• After January 1998, AADup (implicit withdrawal with same path attributes) was the single largest category of BGP updates and accounted for 30-40% of the updates seen each day.
  • may have two causes related to BGP software implementations: (1) non-transitive attribute filtering, and (2) interaction between MinRouteAdvert timer and stateless BGP
• Only a small percentage of the total number of BGP updates generated each day is due to persistent oscillations, that is, a sustained (usually on the order of several hours or more), high frequency oscillation in prefix reachability or path attributes.
• Instability is not disproportionately dominated by prefixes of specific lengths.
• We experimentally confirmed a number of the origins of pathological routing behavior postulated in our earlier work.
  • redundant withdrawals caused by stateless BGP
  • periodicity in update arrivals caused by unjittered timers

References: This is a followup to the paper "Internet Routing Instability" by the same authors.