Presented by Riccardo Crepaldi and Mirko MontanariCS 525 - Spring 2008Internet Routing InstabilityCraig Labovitz, G. Robert Malan, Farnam JahanianPublished in ACM SIGCOMM 1997CS 525 - Spring 2008The structure of the Internet9 large ISPs, tier one 4000-6000 tier two providers Large public exchange points are considered the “core” of the Internet.Backbone service providers must maintain a complete map, or default-free routing table.CS 525 - Spring 2008The (future?) of the Internet“Almost all of the many predictions now being made about 1996 hinge on the Internet's continuing exponential growth. But I predict the Internet, which only just recently got this section here in InfoWorld, will soon go spectacularly supernova and in 1996 catastrophically collapse. Here's why there soon will be only World Wide Web ghost pages.MoneyDigital MoneyMeasurementMonopoliesSecurityCompatibilityCapacityPrivacyVideoPornographyBob MetcalfeCS 525 - Spring 2008Border Gateway ProtocolVerioUUNet Sprint 128.42.x.x196.29.x.x128.42.x.x100.100.x.x196.29.x.x92.92.x.x100.100.x.x196.29.x.x92.92.x.xBGP connects Autonomous systemPath Vector ProtocolExchange full routing table at startUpdates are sent incrementally:AnnouncementsWithdraws (Implicit and Explicit)The ASPATH mechanism allows a router to detect and prevent routing loops.CS 525 - Spring 2008Updates in BGPWADiff – Route is explicitly withdrawn (unreachable) and replaced with an alternative route to the same destinationAADiff – Route is implicitly withdrawn and replaced by an alternative route (unreachable or better path found)WADup – Route is explicitly withdrawn and then re-announced as reachable (link or router failure, or pathological oscillation)AADup – Route is implicitly withdrawn and replaced with a duplicate of the original route WWDup – Repeated transmission of BGP withdrawals for a prefix that is currently unreachableCS 525 - Spring 2008Routing InstabilityForwarding InstabilityWADiff, AADiff, WAdupmay reflect legitimate topological changes and affects the paths on which data will be forwardedRouting Policy FluctuationAADupreflects changes in routing policy information that do no affect forwarding pathsRedundancyWADup, AADup, WWDupupdates are redundant BGP information that do not reflect routing nor forwarding instabilityCS 525 - Spring 2008Routing InstabilityForwarding InstabilityWADiff, AADiff, WAdupmay reflect legitimate topological changes and affects the paths on which data will be forwardedRouting Policy FluctuationAADupreflects changes in routing policy information that do no affect forwarding pathsRedundancyWADup, AADup, WWDupupdates are redundant BGP information that do not reflect routing nor forwarding instabilityDesirable and NecessaryPathologicalCS 525 - Spring 2008MethodologyBGP routing messages logged for 9 months with five major US exchanges pointsM.A.E. east is representativeCS 525 - Spring 2008Origins of the InstabilityRouter configuration errorsTransient physical and data link problemsSoftware bugsCS 525 - Spring 2008Effects of InstabilityPoorer end-to-end network performanceDegradation of overall efficiency of the Internet infrastructureIncreased packet lossDelays in time for network convergenceResource overhead (CPU, memory, etc.)CS 525 - Spring 2008BGP ImprovementsRoute Aggregation (Supernetting):Combines a number of smaller IP prefixes into a single, less specific route announcementReduces overall number of networks visible Fails in multi-homingRoute dampening algorithms“Hold-down” updates that exceed certain parametersCan introduce artificial connectivity problemsCS 525 - Spring 2008Main ObservationsThe number of BGP updates exchanged per day in the Internet core is one or more orders of magnitude larger than expectedRouting information is dominated by pathological, or redundant updates, which may not reflect changes in routing policy or topologyInstability and redundant updates exhibit a specific periodicity of 30 and 60 secondsInstability and redundant updates show a surprising correlation to network usage and exhibit corresponding daily and weekly cyclic trendsCS 525 - Spring 2008Main ObservationsInstability is not dominated by a small set of autonomous systems or routesInstability and redundant updates exhibit both strong high and low frequency components.Much of the high frequency instability is pathologicalDiscounting the contribution of redundant updates, the majority (over 80%) of Internet routes exhibits a high degree of stabilityThis work has led to specific architectural and protocol changes in commercial Internet routers through the collaboration with vendorsCS 525 - Spring 2008CS 525 - Spring 2008CS 525 - Spring 2008Poor ImplementationsManufacturing companies are responsible for inefficiencies...CS 525 - Spring 2008Forwarding Instability Density?Duplicate messages removed~30000 samplesThresold: 345 updates per 10 minsInstability over thresholdInstability below thresholdData MissingCS 525 - Spring 2008Forwarding Instability Density?Duplicate messages removed~30000 samplesThresold: 345 updates per 10 minsISP infrastructure upgrade?Instability over thresholdInstability below thresholdData MissingCS 525 - Spring 2008Forwarding Instability Density?Duplicate messages removed~30000 samplesThresold: 345 updates per 10 mins10:00 AM - Backbone Maintenance? ISP infrastructure upgrade?Instability over thresholdInstability below thresholdData MissingCS 525 - Spring 2008Forwarding Instability Density?Duplicate messages removed~30000 samplesThresold: 345 updates per 10 mins10:00 AM - Backbone Maintenance? ISP infrastructure upgrade?Summer Vacation - Business Pattern?Instability over thresholdInstability below thresholdData MissingCS 525 - Spring 2008A representative Week“bell-shaped curve of raw updates that peaks during the afternoon”Saturday Spikes: “we have no immediate explanation for this occurence”CS 525 - Spring 2008Data ValidationFFT and MEM Spectral Estimation Correspond Routing instability corresponds closely to trends in Internet bandwidth usage and packet loss 7Days24 HoursCS 525 - Spring 2008Let’s go in DetailEach line is a single day80-100% of the daily instability is contributed by Prefix + AS pairs announced less than 50 times.20-90% of AADiff events are contributed by routes that changed 10 times or lessWADiff climbs fasterCS 525 - Spring
View Full Document
Unlocking...