ModelsMotivationTimingOne PacketIllustrationExamplesQueuingQueuing ExampleStore and ForwardS&F - MultipleCut-ThroughA Fluid ViewMetricsThroughputDefinitionsConnectionLinkFluctuationsMeasurementsDelayDefinitionsIllustration 1Illustration 2Little’s ResultMeasurements 1Measurements 2Evaluation TechniquesAnalysisSimulationMeasurementsModels Motivation Timing Diagrams Metrics Evaluation TechniquesTOC – ModelsMotivation Understanding Network Behavior Improving Protocols Verifying Correctness of Implementation Detecting Faults Choosing Provider Feasibility of Applications Monitoring Service Level Agreements BillingTOC – Models – MotivationTiming Sending one packet Illustration Examples Queuing Queuing example Store and forward S&F:Multiple packets Cut-Through Fluid ViewTOC – Models – TimingOne PacketP bitsR bpsT secondsP/R = Transmission timeT = Propagation time = L/speed = L(km)x(time/km)TP/RTimeTime/km = 3.3µs in free space4 µs in copper5 µs in fiberTime/km = 3.3µs in free space4 µs in copper5 µs in fiberTOC – Models – Timing – One PacketIllustrationTransmission LineTransmitter Æ ReceiverSignal ÆOne bitEach bit takes 1/R seconds to be transmittedThe bits take T seconds to propagateTOC – Models – Timing – IllustrationExamplesP = 1KByteR = 1Gbps100km, fiberT = 500µsP/R = 8µsT >> P/RTP/RP = 1KByteR = 100Mbps1km, fiberT = 5µsP/R = 80µsTP/RT << P/RTOC – Models – Timing – ExamplesQueuing Link:R bpsT secondsP bitsQQ/RTQ/R = queuing delay(load-dependent)P/RTimeTOC – Models – Timing – QueuingQueuing Example Link:P bitsR bpsQ1ms1-kbit packets; R = 1MbpsTimeT(t) = Q/R + P/R for a packet that arrives at t1msTime tLet Tn = Q/R +P/R for packet nT1 = 1msT2 = 1.5msT3 = 2msT4 = 1msT5 = 1.5msT6 = 1msTOC – Models – Timing – Queuing ExampleStore and Forward System:10Mbps 5Mbps 100Mbps 10MbpsTOC – Models – Timing – Store and ForwardS&F - Multiple System:10Mbps 5Mbps 100Mbps 10MbpsTOC – Models – Timing – S&F MultipleCut-Through System:R1 = 10Mbps R2 = 10MbpsHeaderStart forwarding assoon as the header is receivedNote: What if R2 > R1?TOC – Models – Timing – Cut-ThroughA Fluid ViewRate R System:A(t); rate a(t)X(t)D(t); rate d(t)# bits in [0, t] # bits in [0, t]a(t)d(t)X(t)TOC – Models – Timing – Fluid ViewMetrics Throughput DelayTOC – Models –MetricsThroughput Definitions Example 1: Connection Example 2: Link Fluctuations MeasurementsTOC – Models – Metrics – ThroughputDefinitions Roughly: throughput = bit rate (e.g., 120Kbits/second) More precisely: Throughput of a connection or of a link: total number of bits during some period [t, t + T] divided by T Bandwidth* of a link = link rate = bit rate of the transmitter*Note: misnomer, but common usage Utilization of a link = throughput of the link / link rate Bit rate units: 1Kbps = 103bps, 1Mbps = 106bps, 1Gbps = 109bps[For memory: 1Kbytes = 210bytes = 1,024 bytes; 1MBytes = 220bytes] Some rates are expressed in packet per second (pps)Æ relevant when the bottleneck is the header processingTOC – Models – Metrics – Throughput – DefinitionsConnection Connection: Send W bits (window size) Wait for ACKs Repeat Assume that the round-trip time is RTT seconds Throughput = W/RTT bps Numerical Example: W = 64KBytes = 512 kbits = 512x1,024 = 524,288 bits RTT = 200ms Throughput = W/T = 2.6MbpsRTTKRTTKTimeSourceDestinationTOC – Models – Metrics – Throughput – ConnectionLink 1Mbps link sends 1,000-bit packetsRate every µs10.5MbpsRate every40 msUtilization= 50%Time tTOC – Models – Metrics – Throughput –LinkFluctuations Rate varies over timeThroughput over last T secondsminmeanmaxTime tTOC – Models – Metrics – Throughput – FluctuationsMeasurements TCP: Keep track of number of bytes receivedLet R(t) = number of bits in [0, t]Throughput over last T seconds = [R(t) – R(t – T)]/T Link: Device has counter with number of bytes received; calculate as aboveTOC – Models – Metrics – Throughput – MeasurementsDelay Definitions Illustration 1 Illustration 2 Little’s Result Measurements: Example 1 Measurements: Example 2TOC – Models – Metrics – DelayDefinitions Delay/Latency of bit (packet, file) from A to B The time required for bit (packet, file) to go from A to B Jitter: Variability in delay Round-Trip Time (RTT) Two-way delay from sender to receiver and back Bandwidth-Delay Product Product of bw and delay, indicates “storage” capacity of networkTOC – Models – Metrics – Delay – DefinitionsIllustration 1S21DLatest bit seen by time tat point 1 at point 2Delay of bit nnTOC – Models – Metrics – Delay – Illustration 1Illustration 2S D1212Packet arrival times at 1Packet arrival times at 220 msMax delay = 100 msMin delay = 40 msJitter = 60 msMax delay = 100 msMin delay = 40 msJitter = 60 msTOC – Models – Metrics – Delay – Illustration 2S D12Little’s ResultNS = areaT(N)T(N - 1)X(t)S = T(1) + … + T(N)= integral of X(t)TT(1) + … + T(N)NNT1X(t)dt =TS=.TÆ Average occupancy = (average delay)x(average arrival rate)TOC – Models – Metrics – Delay – Little’s ResultMeasurements 1 A Good EpochTOC – Models – Metrics – Delay – Measurements 1Measurements 2 A Worse EpochTOC – Models – Metrics – Delay – Measurements 2Evaluation Techniques Models + Analysis Models + Simulations MeasurementsTOC – Models – EvaluationAnalysis Example: M/M/1 QueueArrivals are Poisson with rate λService times are exponentially distributed with mean 1/µAverage delay per packet T = 1/(µ – λ) = (1/µ)/(1 – ρ) where ρ = λ/µ = utilizationFor instance, 1/µ = 1ms and ρ = 80% => Q = 5msµλTOC – Models – Evaluation –AnalysisSimulation Model of traffic Model of routers, links, …. Simulation: Time Driven: X(n) = state at time nεX(n+1) = f(X(n), event at time nε) Event Driven: Y(n) = state after event nE(n) = n-th eventT(n) = time when event n occurs[Y(n+1), T(n+1)] = g(Y(n), T(n), E(n)] Key Step: Output analysis (estimates, confidence intervals….)TOC – Models – Evaluation – SimulationMeasurements Design Experiment Representative? Output AnalysisTOC – Models – Evaluation –
View Full Document