A Value-based Framework for Internet Peering Agreements

A Value-based Framework for Internet Peering Agreements

FlowRoute: Inferring Forwarding Table Updates Using Passive Flow-level Measurements Amogh Dhamdhere (CAIDA/UCSD) [email protected] with Lee Breslau, Nick Duffield, Cheng Ee, Alexandre Gerber, Carsten Lund and Shubho Sen (AT&T Labs-Research) Motivation Routing protocol performance during routing events can affect end-to-end performance Transient loops and packet losses may occur during routing reconvergence Network operators need to monitor routing protocol performance Do routers respond as expected? Update their forwarding tables in a timely manner? Update their forwarding tables to the expected state? 01/25/20

IMC 2010, Melbourne Australia 2 Monitoring Routing Events Control plane monitors (e.g., OSPFmon, BGPmon) Monitor the control plane cannot measure when a router implemented a change in its forwarding table Active probing Can only monitor paths that are probed Spatial and temporal resolution limited by placement of probes and probing frequency 01/25/20 IMC 2010, Melbourne Australia 3

FlowRoute A data-plane monitoring tool to work in conjunction with control plane monitors Infer forwarding table updates using flow-level measurements Works offline, for after-the-fact forensics and analysis No additional overhead on routers Uses flow-level measurements (e.g., Netflow) that are already collected 01/25/20 IMC 2010, Melbourne Australia 4 Basic Method T1: f1

N1 R T2: f2 N2 Single packet flows f1 and f2 towards D f1 seen at N1: R is previous hop at time T1 N1 is Rs next hop towards D at T1 f2 seen at N2: R is previous hop at time T2 N2 is Rs next hop towards D at T2 Rs next hop towards D changed in [t1,t2] 01/25/20

IMC 2010, Melbourne Australia 5 Routing Flow Records o i Rp Rn R R sees flow towards destination D from tf to tl Netflow: (R, i, o, tf, tl, D)

Map outgoing interface Duplicate first o to next hop router packet timestamp Map incoming Subtract link interface i to propagation previous hop delays router (Rp, tf-, tl- ,D,R) 01/25/20 (R, tf, tf, D, Rn) One flow record at R produces two routing flow

records, giving the routing state of R and R p IMC 2010, Melbourne Australia 6 Inferring Forwarding Table Updates Collect netflow records from all routers Convert to Routing Flow Records (RFRs) for offline processing (R, T1, T2, N1, D) (R, T3, T4, N2, D) T2 < T3 N1 T1

01/25/20 N2 T2 T3 T4 R changed next hop towards D in the time window [t2,t3] range of range of forwarding table update IMC 2010, Melbourne Australia 7 Inferring Forwarding Table Updates Collect netflow records from all routers

Convert to Routing Flow Records (RFRs) for offline processing (R, T1, T2, N1, D) (R, T3, T4, N2, D) T2 > T3 N2 N1 T1 01/25/20 T3 T2

T4 Routing flow records overlap could be due to Equal Cost Multi-Path (ECMP) IMC 2010, Melbourne Australia 8 ECMP [T1,T2]: f1 N1 R [T3, T4]: f2 01/25/20

D N2 Router R can forward flows destined to D to either N1 or N2 RFRs generated at N1 and N2 can overlap inconsistency Non-overlapping RFRs can appear as a routing change for every flow IMC 2010, Melbourne Australia 9 Filtering ECMP Observation: In 99% of next hop changes due to ECMP, a router routes fewer than 20 flows

towards one next hop, before routing a flow towards an equal-cost next hop Filtering heuristic: Declare routing change only if >20 flows were routed to the old next hop before a flow is routed to new next hop Conservative: May miss routing changes before 20 flows are forwarded to the old next hop 01/25/20 IMC 2010, Melbourne Australia 10 Sampling Both packet and flow sampling in high-speed networks Sampling does not affect correctness of inferred ranges Sampling affects the width of ranges; more sampling lower temporal resolution More discussion in the paper

01/25/20 IMC 2010, Melbourne Australia 11 Timely Forwarding Table Updates Forwarding table update ranges OSPF event range of cluster All ranges overlap with OSPF event cluster 01/25/20 IMC 2010, Melbourne Australia 12

Delayed Forwarding Table Updates Forwarding table updates consistent with OSPF events Forwarding table updates delayed w.r.t OSPF events Such behavior is not detectable using a control plane monitor alone! 01/25/20 IMC 2010, Melbourne Australia 13 Delayed Forwarding Table Updates

Used FlowRoute on a 2-month dataset 2666 OSPF event clusters 97010 time ranges consistent with OSPF event clusters 117 ranges that showed delayed forwarding table updates Two routers showed delayed updates 14 times in the 2-month dataset Subsequently retired from the network 01/25/20 IMC 2010, Melbourne Australia 14 Loops Delayed forwarding table updates can cause transient loops Example in the paper of how this can happen

392 instances of 1-hop loops during 2-month dataset Mostly short-lived (sub-second) A few loops lasted 10s of seconds Long-lived loops were due to delayed updates by one or more routers 01/25/20 IMC 2010, Melbourne Australia 15 Summary FlowRoute: A data plane monitor to work in conjunction with control plane monitors for forensics and analysis of forwarding table updates Used to study forwarding table updates in a tier-1 ISP network Found cases of delayed forwarding table updates due to buggy routers

Also found transient loops during routing convergence and spikes in link utilization 01/25/20 IMC 2010, Melbourne Australia 16 Thanks! [email protected] www.caida.org/~amogh 01/25/20 IMC 2010, Melbourne Australia 17 Practical Issues What should be the destination? Can be either destination IP address, prefix, or MPLS tunnel

endpoint Need to observe sufficient flow volume We choose MPLS tunnel endpoint Sampling Both packet and flow sampling occur in high-speed networks Sampling does not affect correctness of inferred ranges Affects the width of the ranges; more sampling lower temporal resolution 01/25/20 IMC 2010, Melbourne Australia 18 Existing Approaches Control plane monitors (e.g., OSPFmon, BGPmon) Monitor the control plane, cannot measure when a router implemented a change in its forwarding table

Collect and process router logs Large volume of data, transporting and processing is hard Limited by polling frequency, e.g., 5 minutes with SNMP Active probing Spatial and temporal resolution limited by placement of probes and probing frequency 01/25/20 IMC 2010, Melbourne Australia 19 Delayed Forwarding Table Updates Used FlowRoute on a 2-month dataset -- 2666 OSPF event clusters 97010 time ranges consistent with OSPF event clusters 58 clusters, 117 ranges that showed delayed forwarding table updates Two routers showed delayed updates 14 times in

the 2-month dataset Subsequently retired from the network 01/25/20 IMC 2010, Melbourne Australia 20

Recently Viewed Presentations

  • 27 - Faculty Site Listing

    27 - Faculty Site Listing

    The stored toxin is retained in the metamorphosed monarch butterfly. ... Figure 27-6 Camouflage by resembling specific objects. Leafy sea dragon. Living rock cacti. Citrus swallowtail larva. ... Wing pattern looks like a jumping spider. The jerky motions mimic the...
  • James Madison High School

    James Madison High School

    Agriscience Magnet ProgramDirector - Doak Stewart. The AMP is available to NEISD high school students with an interest in studying agriculture science. The AMP employs a performance-based enrollment process that evaluates students on interest, academic progress, school attendance, and discipline...
  • New Join Employee Induction Contents Introduction About ABIS

    New Join Employee Induction Contents Introduction About ABIS

    Induction refers to the process of introducing a new comer to his employer/ company and work environment. An induction session, conducted on day one for a new joiner, usually through PowerPoint presentation and videos sessions lasts a few hours or...
  • 10.4 Adding, Subtracting, and Multiplying Radical Expressions 1.

    10.4 Adding, Subtracting, and Multiplying Radical Expressions 1.

    3. Simplify radical expressions that contain mixed operations. Simplify. 1) 2) 3) Adding Radical Expressions Like radicals: Radical expressions with identical radicands and indices (roots). Adding Like Radicals Add or subtract the coefficients and leave the radical parts the same.
  • When responding to an argumentative / persuasive on-demand

    When responding to an argumentative / persuasive on-demand

    Some may believe that parents who allow their children to play with toy guns are just asking for future trouble; however, encouraging kids to role play with pretend guns can help them understand roles of good and evil, the importance...
  • DGP - Sentence 1

    DGP - Sentence 1

    Sentence. the fore men worked hard too finish the job there boss gived them a large bogus. Word Bank: capital letter (1) semicolon (1) period (1) Discuss and Compare. Compare your answers to your neighbor's answers to see if you...
  • High Potential Opportunity Sustainable Aquaculture Developing and deploying

    High Potential Opportunity Sustainable Aquaculture Developing and deploying

    University of Plymouth. Sparsholt College. Recognised worldwide for expertise in providing education in aquaculture and fisheries studies. 6,500 students and one of the leading providers of university level courses for the land and environment . ... with the town of...
  • Improving Location Accuracy - Corvelle

    Improving Location Accuracy - Corvelle

    Improving Location Accuracy 101100110101 Update on migrating to NAD 83 and to a newer survey grid version Yogi Schulz