1、Internet Routing Instability,Craig Labovitz G. Robert Malan Farnam Jahanian,Presenters:Supranamaya RanjanMohammed Ahamed,Appeared: SIGCOMM 97,Internet Structure,Many small ISPs at lowest level,Small number of big ISPs at core,The Core of the Internet,Verio,UUNet,Sprint,rice.edu,Routing done using BG
2、P at core,Inter-domain routing could be RIP/OSPF etc,BGP Overview,Verio,UUNet,Sprint,128.42.x.x 196.29.x.x,128.42.x.x,100.100.x.x,196.29.x.x,92.92.x.x,100.100.x.x 196.29.x.x,92.92.x.x,BGP Overview (contd.),Similar to Distance Vector routing,Path Vector protocol,Loop detection done using AS_PATH fiel
3、d,Peering session (TCP),R1,R2,Exchange full routing table at start,Updates sent incrementally,Key Point,The volume of BGP messages exchanged is abnormally high,Most messages are redundant / unnecessary and do notcorrespond to and topology or policy changes,Consequence: Instability,Normal data packet
4、s handled by dedicated hardware,BGP packet processing consumes CPU time,Severe CPU processing overhead takes the router offline,Route Flap Storm:,C,B,A,Router A temporarily fails,When A becomes alive B & Csend full routing tables,B & C failcascading effect,How do we avoid /lessen the impact of these
5、 problems?,Route Dampening,Router does not accept frequent route updates to a destination,Might signal that network has erratic connectivity,Increment counter for destination when route changes,Counter exceeds threshold stop accepting updates,Problem:,Future legitimate announcements are accepted onl
6、yafter a delay,Decrement counter with time,Prefix Aggregation/Super-netting,Core router advertises a less specific network prefix,Reduces size of routing tables exchanged,Problems:,- Internet addresses largely non-hierarchically assigned,Prefix aggregation is not effective because:,- 25% of prefixes
7、 multi-homed,- Multi-homed prefixes should be exposed at the core,- Domain renumbering not done when changing ISPs,Route Servers,O(N) peering sessions per Router,1 peering session per router,Route Server,In-spite of all these measures the BGP message overhead is unexpectedly high,Evaluation Methodol
8、ogy,Data from Route Server at M.A.E west (D.C) peering point,Peering point for more than 60 major ISPs,Time series analysis of message exchange events,Nine month log,Observation: Lots of redundant updates,Duplicate route with-drawls,Number of With-drawls,Unique,ISP,A,23276,4344,F,86417,12435,I,24790
9、23,14112,Ratio,5,7,175,One Reason:- Stateless BGP- No state of previous with-drawls maintained,Observation: Instability Proportional to Activity,After removing duplicate messages:,Time of day,Evidence from Fine Grained Structure,Conjecture:BGP packets are competing with data packets during high band
10、width activity.,Frequency (1/hour),7 days,24 hours,Power spectral density,Observation: Instability & size uncorrelated,ISPs serving more network prefixes may not contribute more to instability,Observation: Instability distributed over routes,75% median,20% to 90% of routes change 10 times or less,No
11、 single route contributes significantly to instability,10,# of announcements per prefix+AS,Cumulative proportion,Observation: Synchronized updates,Inter-arrival times of updates shows periodicity,30 s and 1 minute patterns,Some routers collect and send Updates once every 30 s,Routers get synchronize
12、d,Possible reasons:,Border router- Internal router: interaction misconfigured?,End-to-end Perspective,Chinoy: “Dynamics of Internet routing information” (SIGCOMM 93),Measurements on NSFNET showed:- Processing and forwarding latency of BDP updateis 3 orders of magnitude more than the latency incurred
13、 in forwarding data packets- Will lead to packet drops during the intervening period,Paxson: “End-to-End routing behavior in the internet” (SIGCOMM 96),Routing loops introduce loops into other routers routing tablesAn end-to-end route changes every 1.5 hours on an average,End-to-End perspective (Pax
14、son),Pathologytype,Probabilityin 1995,Probabilityin 1996,Long-lived Routing loops,Short-lived Routing loops,Outage30s,Total,same,same,0.96%,2.2%,3.4%,1.5%,Summary and Conclusions,Redundant routing information flows in core,Instability distributed across autonomous systems,Possible reasons for instab
15、ility:,Stateless BGP updatesMisconfigured routersSynchronizationClocks driving the links not synchronized (link “flaps”),Follow-up work & impact,Migration from stateless to stateful BGP decreased duplicate withdrawals by an order of magnitude,“Origins of Internet Routing Instability”-1999,But Duplicate Announcements (AADup) doubled,Reason: Non-transitive attribute filtering not implemented,- BGP specification: “never propagate non-transitive attributes”,- ASPATH is transitive attribute,- MED (Multi Exit Discriminator) is NOT transitive,Propagating MEDs Causes Oscillations,
