DOC PREVIEW
USC CSCI 551 - 14_paxson99b-6up

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1 Computer Communications - CSCI 551 Copyright © William C. ChengCS551End-to-End InternetPacket Dynamics[Paxson99b]Bill Chenghttp://merlot.usc.edu/cs551-f12Why do people want to know?How do you measure Internet performance?2End-to-end Packet Dynamics Computer Communications - CSCI 551 Copyright © William C. ChengAre ISPs willing to tell you?What kinds of packet dynamics are observed in the network?Does there exist a typical Internet path?active measurementsMeasure Internet traffic3Key Ideas Computer Communications - CSCI 551 Copyright © William C. ChengN2 pathslots of details out of TCPpathologies (out-of-order, duplication, corruption)Evaluate dynamicsbandwidthlossdelayFocused on a small number of pathsrouters designed to handle TCP as common casePrevious studies4Methodology Computer Communications - CSCI 551 Copyright © William C. ChengUsed unrealistic traffic (pings etc.)Examined nearly 1000 pathsPaxson’s studyUsed TCP trafficcongestion-adaptive (both good and bad)used statistically valid sampling to reduce biasWas extraordinarily carefullooked at the wire to get most confidenceadjusted for TCP implementation idiosyncrasiesSignificant (non-trivial)occurrence (10-30%connections)Different packets sentalong different routesReordering: packets arrive at receiver in a different orderthan they were sent5Pathologies: Reordering Computer Communications - CSCI 551 Copyright © William C. ChengEvidence:Strongly-site dependentMost egregious instancescorrelated with route flutterRouter forwarding lulls (i.e., stops forwarding as ifit has gone to sleep)Other curious effectsWhich assume packet loss upon receiving dup-ACKsyes, about 20ms waits would have detected mostreordering eventsOn TCP fast retransmit and recovery6Impact of Reordering Computer Communications - CSCI 551 Copyright © William C. ChengBut packets may actually have been reorderedCan we avoid this by:Waiting before sending ACKReducing the dup-ACK thresholdbottom line: current techniques workBut, these require server and client side changepossibly, to 2Link layer retransmissionsmaybe notPacket duplication7Other Pathologies Computer Communications - CSCI 551 Copyright © William C. ChengHappens, but very infrequentlyAbout 1 in 5000 (2x10-4)Packet corruptionIs TCP 16-bit checksum enough to protect against this?Found one out of 300K ACKs corrupted, so maybe notBottleneck BW: max possible rateHow do you compute the bottleneck path bandwidth?8Bottleneck Bandwidth Estimation Computer Communications - CSCI 551 Copyright © William C. ChengAvailable bandwidth: reasonable shareSend two packets, each size S, closely spaced Packet pairAt bottleneck, the packets are separated by a time TIf inference done at sender, can be error-prone because ofWhere to measure? Sender (RTT) or receiver (OTT)?Bottleneck bandwidth Qb = S/TACK compressionbandwidth asymmetry, which causes noise in reversepathClock granularity (fix: measure multiple packets)9Packet Pair Problems and Fixes Computer Communications - CSCI 551 Copyright © William C. ChengRoute changes (fix: measure several, take mode)Out of order delivery (fix: filter out)Multi-channel links, route spraying (fix: measurefor multiple packets)If two modes widely separated in trace-> route changeCompute estimates from bunches of packets each sentclosely spaced to the next (also known as packet trains)10Fix? Packet-bunch Modes Computer Communications - CSCI 551 Copyright © William C. ChengGet modes from the distribution of estimatesIf two modes for different bunch sizes-> multi-channel linksBunches also eliminate clock granularity problemsmuch higher on some links, ex. US to EuropeFairly high rates (3% or 5%)11Packet Loss Computer Communications - CSCI 551 Copyright © William C. ChengBut many connections are loss-free (30- 66%)define queued andunqueued pktsqueued := packet iqueued behind i-1at bottleneck linkshort-time-scale:packet a to b (stream)12Is Loss Predictive? Computer Communications - CSCI 551 Copyright © William C. Chengelse unqueued (sufficentspacing that no self-queueing)queued packets have muchhigher loss rateszero/non-zero ispredictive (data not inpaper)long-time scale: hoursor daysallows trafficengineeringactual loss rate is notpredictiveData loss acrossconnections well-modeledby exponentialData vs ACK lossNot so for ACKsLoss are not independentBurstsBurst sizes are heavy-tailed13Loss Patterns Computer Communications - CSCI 551 Copyright © William C. ChengP[pkt i lost | pkt i-1was lost]Conditional lossdefinitiondrop-tail routersWhylosses are not i.i.dImplications14Burst Loss Computer Communications - CSCI 551 Copyright © William C. Chengconditinal loss ratesare much higher15Overall Loss Characteristics Computer Communications - CSCI 551 Copyright © William C. ChengIn measuring, must becareful to account fortcpdump lossesACK loss is the correctdeterminant of networkconditionsDoubling of average lossin one yearLoss rates don’t havepredictive powerBut whether a connectionsuffers loss or not can beused for prediction Dual network states(quiescent vs. busy)Existence ofDiurnal variationsGeographical diversityin loss patternsNo typical loss rateCorrect RTOimplementationAvoiding unnecessaryretransmissionsSACKA flight of ACKs queuedbehind cross trafficalthough mostconnectionsexperienced oneACK compressionHappens quite infrequentlydurations are small andnumber of such eventsis smallPacket pair techniques canaccount for this by rejectingoutliersMuch more infrequentthan ACK compressionData timingcompression16Delays Computer Communications - CSCI 551 Copyright © William C. ChengPossibly due tospecific routersACK and data timing compression should not happenMeasured by variations inone-way transit timesQueueing time scales17Delays Computer Communications - CSCI 551 Copyright © William C. ChengShow wide variability, sowe cannot design for aparticular regimeApproximated by variationsin delay experienced due toown loadingAvailable bandwidthAgain, shows wide variabilityMost between 0.1 - 1 secDo you think this study is valid today?18Questions? Computer Communications - CSCI 551 Copyright © William C. ChengWhat has happened since 1995?Dialup->broadbandBetter connectivityHigher backbone


View Full Document

USC CSCI 551 - 14_paxson99b-6up

Download 14_paxson99b-6up
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view 14_paxson99b-6up and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 14_paxson99b-6up 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?