552: Computer Networks

552: Computer Networks

Measurement Lecture 8, Computer Networks (198:552) Why measure networks? Application QoS Throughput Delay Loss Jitter Availability

Congestion/overload Long-term demands SLO violations ISP ISP ISP Application QoS Problematic ISPs

Problematic CDNs Measurements for ISP Network Operators Example (1): Excess Traffic Two large flows of traffic New egress point for first flow

Multi-homed customer Example (2): DoS Attack Install packet filter Web server back to life Web server at its knees Example (3): Link Failure Routing change alleviates congestion

Link failure New route overloads a link Measurements for ISP network operators Control

Route and schedule traffic Filter traffic Provision additional capacity Diagnose root cause Determine how to route traffic

Detect link or path-level problems Measure incoming traffic demands Measure forwarding updates! Measure How do ISPs measure today? Periodic link statistics

SNMP counters Example: port1: 500 packets transmitted, 13 dropped Periodic flow statistics NetFlow, sFlow, IPFIX Example: src:, dst:, inport: 4, count: 45 Active end-to-end probes Ping: 64 bytes from icmp_seq=0 ttl=55 time=6.575 ms Traceroute: more to come

User complaints! Customer phone calls, NANOG posts Diagnosis & Traffic engineering Control plane issues New routes Link failures Network upgrades! Data plane issues

Lot of neat algorithms & measurement systems Quality of input data matters! Scope to do a lot more DoS attack Flash crowds Poor demand prediction, in general Decision plane issues Poor provisioning

Lack of peering Challenge: Measurement data reduction A network cant capture every packet with timestamps Too much data! Filter to restrict to data of interest Ex: by source, by app, by (physical) port, Sample to thin the data stream for exact computations Systematic, random, stratified

Consistently sample same/distinct packet at each hop Aggregate (ex: by flow) to summarize data over many packets One problem: too many flows Sketches: aggregation that approximates with limited memory Challenge: Joining traffic with forwarding Where is DoS traffic entering the network? How do I know which traffic is DoS traffic?

Are there other links that are affected? Should you reroute other traffic that is affected? Install packet filter Web server back to life Web server at its knees

End-to-End Measurements Why end-to-end measurements? Endpoints could directly measure what matters to users ISPs may not be willing to share data Proprietary design, net neutrality, Data shared improperly may violate user privacy! Indirect view: cant say for sure why something happens Hard to corroborate with ground truth

Possible to use multiple endpoints and span ISP boundaries! Metrics and tools Reachability: ping & its variants Path: traceroute & its variants Available bandwidth: speedtest, iperf, pathrate, Delays and loss rate: a selection of the above tools Traceroute 1. 2.

3. 4. 5. 6. Launch a probe packet towards DST, with a TTL of 1 Each router hop decrements the TTL of the packet by 1 When TTL hits 0, router returns ICMP TTL Exceeded SRC host receives this ICMP, displays a traceroute hop Repeat from step 1, with TTL incremented by 1, until DST host receives probe returns ICMP Dest Unreach

Traceroute: Example output (1/2) [552]$ traceroute google.com traceroute to google.com (, 64 hops max, 52 byte packets 1 fios_quantum_gateway ( 1.628 ms 1.537 ms 1.506 ms 2 lo0-100.nwrknj-vfttp-354.verizon-gni.net ( 2.093 ms 2.486 ms 1.835 ms 3 b3354.nwrknj-lcr-21.verizon-gni.net ( 4.962 ms 2.935 ms 3.985 ms 4 *** 5 0.et-10-1-5.gw7.ewr6.alter.net ( 3.864 ms 0.et-11-1-0.gw7.ewr6.alter.net ( 3.503 ms 0.et-10-1-5.gw7.ewr6.alter.net ( 3.581 ms

6 ( 3.949 ms 4.222 ms 4.669 ms 7 *** 8 ( 9.154 ms ( 7.080 ms ( 10.782 ms 9 lga34s14-in-f14.1e100.net ( 4.097 ms ( 5.462 ms ( 9.410 ms Traceroute: Example output (2/2) [552]$ traceroute rutgers.edu

traceroute to rutgers.edu (, 64 hops max, 52 byte packets 1 fios_quantum_gateway ( 1.536 ms 1.083 ms 1.098 ms 2 lo0-100.nwrknj-vfttp-354.verizon-gni.net ( 2.343 ms 1.932 ms 1.948 ms 3 b3354.nwrknj-lcr-21.verizon-gni.net ( 3.124 ms b3354.nwrknj-lcr-22.verizon-gni.net ( 4.026 ms 2.766 ms 4 *** 5 *** 6 0.ae1.gw1.phil.alter.net ( 6.599 ms 0.ae6.gw1.phil.alter.net ( 5.401 ms 5.670 ms 7 rutgers-gw.customer.alter.net ( 5.061 ms 6.937 ms 6.205 ms 8 ( 5.321 ms 5.475 ms 10.577 ms

9 ( 6.500 ms 7.154 ms 7.254 ms 10 ( 6.808 ms 6.799 ms 6.612 ms 11 ( 8.201 ms 7.956 ms 8.180 ms ... 64 * * * Some problems with traceroute Control traffic (ICMP) and data traffic may see different behavior Router CPU versus forwarding table Probes load-balanced differently

A different packet observes each hop Route changes while packet in transit Not all routers may respond to ICMP messages Hidden routers Anonymous routers Improper processing One-way measurement End-to-End Routing

Behavior in the Internet LBNL Technical Report (1996) Vern Paxson Methodology Traceroute between NPDs distributed worldwide (add pic) Exponential sampling/PASTA property Why? What might happen otherwise? D1: unidirectional traceroutes

D2: paired traceroutes Confidence intervals for probability that an event occurred Measurements sample half of the Internet by AS weight Pathologies in Internet routing Forwarding loops! Persistent and temporary Circuitous routing Routing transients Recovery times are bimodal

Route fluttering Partitioned network Temporary outages, some > 30 seconds Too many hops Pathologies correlated with operator change and congestion Summary of pathologies Routing stability Why does routing stability matter?

Prevalence: how frequently do you see a route? PASTA ensures that samples see true stable behavior Persistence: how long does a given route persist over time? Challenging to measure! Example: R1, R2, R1, but samples miss the intermediate R2 Routing prevalence Routing persistence

Routing asymmetry 49% of D2 measurements saw asymmetric paths! visiting a different city each way around 30% with a different AS! Trend worsening over time A summary No guarantees on where your traffic might end up A black-hole! Somewhere unintended (US eastLondon goes through Israel)

Routes are dominated by single winner but can be quite flappy Implications on what performance apps might expect What measurement tools provide Asymmetry makes a lot of things complex Diagnosis: Assumptions about where problems lie Flow state in the core: cant assume youll see return traffic Limitations of the study Representativeness:

Routes within an AS may not have similar characteristics! Sample a really small subset of actual Internet paths Methodology: PASTA doesnt hold when the network is down Hard to extrapolate trends in Internet evolution with just 2 points E2E measurements: Fundamentally hard to corroborate with ground truth Reverse Traceroute

Usenix NSDI 2010 Ethan Katz-Bassett, Harsha V. Madhyastha, Vijay Kumar Adhikari, Colin Scott, Justine Sherry, Peter van Wesep, Thomas Anderson, and Arvind Krishnamurthy Can we find the reverse path? Routes arent always symmetric! What are reverse routes useful for? Main techniques Distributed set of vantage points issuing forward traceroutes

Create an atlas of nodes and paths to the source Incrementally stitch reverse path until you hit an atlas node IP record route: grab first (few) router IP address(es) on return path Recursively reverse traceroute from there! Timestamp option: verify whether a router is on reverse path Source spoofing: sample reverse path without forward path Use prior mapping of vantage points closest to the destination

When all else fails, assume symmetric routing How accurate is reverse traceroute? Ground truth: actual traceroutes from D to S Overlap in hops of reverse and (ground truth) traceroute Close to 87% in the median Why are there differences between the two? Reverse paths used undiscovered peering links

(E2E) Measurement research challenges Ground truth Explaining empirical observations Aliasing, router identification, AS identification, Representativeness Measuring without bias PASTA Coordinating distributed vantage points Probing overheads

Detailed knowhow of the Internet and its quirks! Ex: IP timestamp marked only when router sees itself on top How will the conclusions evolve over time?

Recently Viewed Presentations

  • 1 Samuel 16:7 The Lord does not see

    1 Samuel 16:7 The Lord does not see

    Four men (Dave Miller, Jeff Miller, Eric Lyons, Kyle Butt) Speak around the country & globe (100+ places annually) Publications. Monthly Journals: Reason & Revelation . and . Discovery. Books for adults & kids + Tracts for adults & kids....
  • Présentation PowerPoint

    Présentation PowerPoint

    Guide me, O thou great Jehovah, pilgrim through this barren land. I am weak, but thou art mighty; hold me with thy powerful hand. Bread of heaven, bread of heaven, feed me till I want no more; feed me till...
  • John Basl's 'Technology and Ethics' - Woodwind Web Design

    John Basl's 'Technology and Ethics' - Woodwind Web Design

    SEP, retrieved 8-26-2014: "The method of reflective equilibrium consists in working back and forth among our considered judgments (some say our "intuitions") about particular instances or cases, the principles or rules that we believe govern them, and the theoretical considerations...
  • Neutrale TU Graz-Standardpräsentation 4:3

    Neutrale TU Graz-Standardpräsentation 4:3

    [Nicholas Chammas, Eddie Pantrige: Building a Scalable Record Linkage System, Spark+AI. Summit 2018] 706.520 Data Integration and Large-Scale Analysis -05 Entity Linking and DeduplicationMatthias Boehm, Graz University of Technology, WS 2019/20 ... [Xu Chu, Ihab F. Ilyas, ParaschosKoutris ...
  • UOW 2016 template

    UOW 2016 template

    UOW mandatory internship requirement - students must spend 20 days in a legal workplace (organised by or pre-approved by Law School) under supervision of practising lawyer. Set objectives, reflective journal. Firms, Legal Aid ALS, CLC's (IARC, RACS), barristers, Judges, Magistrates,...
  • Open Automation Software

    Open Automation Software

    OAS Recipe . Provides data transfer from databases such as . MS SQL Server, Access, Oracle, ... ENTERPRISE DATA AUTOMATIONTransport and transform data between sources, log data to open formats at unmatched speeds, or even aggregate data from disparate sources.
  • mcdonough-dolmaya.ca


    Julie McDonough Dolmaya University of Ottawa ... Létourneau & Ruel (1994) Bélanger-Campeau commission briefs Robinson (1998), Khouri (1994) and Brisset (1988) ECP or PCF articles —All excluded from my delimited catalogue.
  • Bridging the Gap between Pupil Level and District Level ...

    Bridging the Gap between Pupil Level and District Level ...

    Fife Peer Learning Project Peter Tymms (Durham, Fife & Dundee) Outline Why Peer Learning The Fife Peer Learning Project Why Scotland Confluence of Fife, Dundee and PIPS Peer Learning Overall plan Design Decisions at Authority Level Issues Peer Learning Meta-analyses...