^ Top

NANOG Meeting Presentation Abstract

Identifying Problematic Inter-domain Routing Issues
Meeting: NANOG24
Date / Time: 2002-02-12 9:30am - 10:00am
Room: Grand Ballroom
Presenters: Speakers:
Olaf Maennel, Saarland University, Saarbruecken, Germa.
Anja Feldmann, Saarland University, Saarbruecken, Germany.
Abstract: Even today, with the widespread usage and critical importance of the Internet, basic routing protocols such as BGP are poorly understood. The important gaps in our understanding include: what causes BGP instability; what is the influence of policy changes on BGP instability; the impact of multi-homing with its blackholes in the routing hierarchy; BGP convergence rate; and the interaction of EBGP, IBGP, and other intra-domain routing protocols.



These are just a few of the questions. To be able to solve problems and/or answer the questions above, we first need to characterize the routing tables and routing updates and determine how their variability relates to the structure of the Internet. In this talk we first discuss the public domain tool \"character,\" which identifies and categorizes BGP routing updates in the context of related updates, and we then present some preliminary analysis results.



Character consists of two parts (implemented as Perl modules): a low-level module, \"FileFinder.pm,\" which provides an intermediate layer between raw BGP data collected via tools such as mrtd, gated, etc.; and the analysis module \"Check.pm,\" which includes functions for the identification and characterization of routing updates. Check provides a extensible and flexible interface for categorizing and analyzing BGP routing updates.



Character\'s input data includes two BGP tables and all BGP updates in between. The two table dumps are used as reference points and for identifying missing updates. (We realize that table dumps aren\'t perfect. But the analysis of many such tables and updates allows us to identify characteristics rather then spurious artifacts.)



Character\'s main data structure is organized by prefix and contains each update:prefix plus attributes. This data structure allows character to identify whether a specific update is a new one (in the considered time frame) or if it has been processed before (using Craig Labovitz\'s terminology is it an AA-DIFF, an AA-DUP, an AW-DIFF or a WA-DIFF); if the attributes of the update have changed and in which way, e.g., at which AS the AS-path has changed and where it is rejoining in the old way.



Besides keeping per-prefix information, character also computes per-AS information, such as the percentage of currently seen updates (near in time) which came through an AS. In addition, it calculates the percentage of total routes through each AS vs. the maximal number of prefixes associated with the AS.



One of the more interesting questions is whether a prefix is flapping. Character keeps track of the overall number of flapping prefixes as well as the number of flapping prefixes originated by the last AS on the AS-path. Besides flapping, character also allows us to study re-convergence. Here re-convergence means: a failure somewhere results in a withdrawl of a route, an alternative route is announced, and after the repair of the failure, the original best route is reannounced, resulting in a flap with two different updates in between.



An old suspicion is that a significant portion of routing table updates is the result of BGP session resets. Each reset causes the two participating peers to exchange their full routing table and redistribute the learned information to their peers. Therefore the effects of routing table resets are visible even if the responsible peers are many AS-hops away. To identify these session resets character keeps track of how many updates are being processed by the router each time a new update arrives. From this character can compute the total number of updates per time period and the number of prefixes with updates per time period. In addition, character computes the same information for every AS: total number of updates (number of prefixes with updates) per time period involving this AS. If a rate exceeds some predefined rate, this update is marked as part of a peak (a possible session reset).



We applied character on BGP table data from RIPE\'s \"rrc00\" peering point during Christmas 2001, and found that less than half of the updates during a period of a day are really \"new\" or \"unique\" ones - all other updates have been seen before (with exactly the same attributes). What has changed between the last update and this one?



Using Craig Labovitz\'s terminology, over 60% of the updates can be categorized as AA-DIFF, 15% AA-DUP (most of them correlate with session resets), 11% AW-DIFF, and 7% WA-DIFF. There are only a few withdraws - most of the updates are route replacements. With regards to attribute changes, we find that 22.0% involve only changes in the AS on the AS-path but no change in the AS-path length; in 14.5% the AS-path is getting longer (not due to policy changes); in 13.8% the Community field has changed; and in 12.9% the AS-path is getting shorter. Other updates involve policy changes, in which the AS-path is getting longer because of a community change, or the other way around.



Most of the time the AS-path changes somehow. Therefore we next investigate whether it reestablishes its connectivity according to the old path. We find that it is the originating AS in 41%, a transit AS in 53% and that the originating AS has changed in roughly 6% of the cases.



With regards to route flapping, we find that even in times of route flap dampening nearly half of all updates are still flapping prefixes (one third of the updates are flapping from time to time - and 14% of all seen prefixes are ONLY flapping prefixes; all flaps have a mean around 51 minutes between flaps). If a prefix is flapping, in over 50% percent of the cases all other prefixes announced by the last AS in the AS-path are flapping as well.



We observed classical re-convergence, but less than 14% of the routes that flap with two updates in-between fall into this category. We note that during certain time periods a single AS is responsible for almost all of the updates, and more than one third of all updates are due to session resets. Indeed session resets cause large peaks (with over 2000 updates per second!) which have to be processed by the router\'s processor.



The described functions answer some questions about what is happening - but they don\'t answer questions about how to avoid these problems in the future. Therefore our next step will be to put together all necessary tools needed to construct a testbed with realistic routing tables and updates. With its help we expect to answer some of the questions related to Internet scalability.
Files: youtubeIdentifying Problematic Inter-domain Routing Issues
pptOlaf Maennel Presentation(PPT)
Sponsors: None.

Back to NANOG24 agenda.

NANOG24 Abstracts

  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • Panel: Updates From the NAPs
    Moderators:
    Mike Hughes, LINX; Panelists:
    Paul VixiePAIX; .
    Lane PattersonEquinix; .
    Tom BechlyMAE Services; .
    Akio SugenoNYIIX/LAIIX/6IIX; .
    Avi FreedmanMetroIX; .
    Jeff MeltzerMetroIX; .
    Tony HaeuserSBC NAPs (AADS, PacBell); .
    Matthew BrooksNOTA; .
    Albert CrewsBellsouth MIX; .
  • UWho
    Moderators:
    Andrew NewtonVeriSign; .
    Leslie DaigleVeriSign; .
  • UWho
    Moderators:
    Andrew NewtonVeriSign; .
    Leslie DaigleVeriSign; .

 
^ Back to Top