EE 122: Network Performance, EvaluationOverviewMotivationsOutlineTiming DiagramsDefinitionsSending One PacketSending one Packet: ExamplesQueueingQueueing ExampleSwitching: Store and ForwardStore and Forward: Multiple Packet ExampleSwitching: Cut-ThroughSlide 14ThroughputExample: Windows Based Flow ControlThroughput: FluctuationsDelayDelay: Illustration 1Delay: Illustration 2Little’s TheoremSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Evaluation TechniquesAnalysisSimulationFluid Flow SystemEvaluation: Putting Everything TogetherEE 122: Network Performance, EvaluationSeptember 7, 20042OverviewMotivationsTiming diagramsMetricsEvaluation techniques3MotivationsUnderstanding network behaviorImproving protocolsVerifying correctness of implementationDetecting faultsMonitor service level agreementsChoosing providersBilling4OutlineMotivationsTiming diagramsMetricsEvaluation techniques5Timing DiagramsSending one packetQueueingSwitching-Store and forward-Cut-throughFluid view6DefinitionsLink bandwidth (capacity): maximum rate (in bps) at which the sender can send data along the link Propagation delay: time it takes the signal to travel from source to destinationPacket transmission time: time it takes the sender to transmit all bits of the packetQueuing delay: time the packet need to wait before being transmitted because the queue was not empty when it arrivedProcessing Time: time it takes a router/switch to process the packet header, manage memory, etc7Sending One PacketR bits per second (bps)T secondsP bitsBandwidth: R bpsPropagation delay: T sectimeTransmission time = P/RTPropagation delay =T = Length/speed_of_light1/speed = 3.3 usec in free space 4 usec in copper 5 usec in fiber8Sending one Packet: ExamplesP = 1 KbyteR = 1 Gbps100 Km, fiber => T = 500 usec P/R = 8 usecTP/RtimetimeTP/RP = 1 KbyteR = 100 Mbps1 Km, fiber => T = 5 usec P/R = 80 usecT >> P/RT << P/R9QueueingThe queue has Q bits when packet arrives packet has to wait for the queue to drain before being transmittedP bitstimeP/RTQ bitsQueueing delay = Q/RCapacity = R bpsPropagation delay = T sec10Queueing ExampleP = 1 Kbit; R = 1 Mbps P/R = 1 msPacket arrivalTime (ms)TimeDelay for packet that arrives at time t, d(t) = Q(t)/R + P/RDelay for packet that arrives at time t, d(t) = Q(t)/R + P/R# bits in queue: Q(t)1 KbP bits Q bits00.517 7.50.5 Kb1.5 Kb2 Kbpacket 1, d(0) = 1mspacket 2, d(0.5) = 1.5mspacket 3, d(1) = 2ms11Switching: Store and ForwardA packet is stored (enqueued) before being forwarded (sent)SenderReceiver10 Mbps5 Mbps 100 Mbps 10 Mbpstime12Store and Forward: Multiple Packet ExampleSenderReceiver10 Mbps5 Mbps 100 Mbps 10 Mbpstime13Switching: Cut-ThroughA packet starts being forwarded (sent) as soon as its header is receivedSenderReceiverR1 = 10 MbpsR2 = 10 MbpstimeHeaderWhat happens if R2 > R1 ?14OutlineMotivationsTiming diagramsMetrics•Throughput•Delay Evaluation techniques15ThroughputThroughput of a connection or link = total number of bits successfully transmitted during some period [t, t + T) divided by TLink utilization = throughput of the link / link rateBit rate units: 1Kbps = 103bps, 1Mbps = 106bps, 1 Gbps = 109bps [For memory: 1 Kbyte = 210 bytes = 1024 bytes]-Some rates are expressed in packets per second (pps) relevant for routers/switches where the bottleneck is the header processing16Example: Windows Based Flow ControlConnection: -Send W bits (window size)-Wait for ACKs-RepeatAssume the round-trip-time is RTT secondsThroughput = W/RTT bpsNumerical example:-W = 64 Kbytes-RTT = 200 ms-Throughput = W/T = 2.6 MbpstimeSourceDestinationRTTRTTRTT17Throughput: FluctuationsThroughput may vary over timemaxminmeanThroughputTime18DelayDelay (Latency) of bit (packet, file) from A to B-The time required for bit (packet, file) to go from A to BJitter-Variability in delayRound-Trip Time (RTT)-Two-way delay from sender to receiver and backBandwidth-Delay product-Product of bandwidth and delay “storage” capacity of network19Delay: Illustration 1at point 2at point 1Latest bit seenby time tDelaySender Receiver1 2time20Delay: Illustration 2Sender Receiver1 221Packet arrival times at 1Packet arrival times at 2Delaytime21Little’s TheoremAssume a system (e.g., a queue) at which packets arrive at rate a(t)Let d(i) be the delay of packet i , i.e., time packet i spends in the systemWhat is the average number of packets in the system? systema(t) – arrival rated(i) = delay of packet iIntuition:-Assume arrival rate is a = 1 packet per second and the delay of each packet is s = 5 seconds-What is the average number of packets in the system?22Little’s TheoremLatest bit seenby time tSender Receiver1 2timex(t)d(i) = delay of packet ix(t) = number of packets in transit (in the system) at time t TWhat is the system occupancy, i.e., average number of packets in transit between 1 and 2 ?23Little’s TheoremLatest bit seenby time tSender Receiver1 2timex(t)TAverage occupancy = S/Td(i) = delay of packet ix(t) = number of packets in transit (in the system) at time t S= area24Little’s TheoremLatest bit seenby time tSender Receiver1 2timex(t)S(N)Pd(N-1)S(N-1)TS = S(1) + S(2) + … + S(N) = P*(d(1) + d(2) + … + d(N))d(i) = delay of packet ix(t) = number of packets in transit (in the system) at time t S= area25Average occupancyAverage arrival timeAverage delayLittle’s TheoremLatest bit seenby time tSender Receiver1 2timex(t)S(N)Pd(N-1)S(N-1)TS/T = (P*(d(1) + d(2) + … + d(N)))/T = ((P*N)/T) * ((d(1) + d(2) + … + d(N))/N)d(i) = delay of packet ix(t) = number of packets in transit (in the system) at time t S= area26Little’s TheoremLatest bit seenby time tSender Receiver1 2timex(t)S(N)Average occupancy = (average arrival rate) x (average delay)S= areaa(i)d(N-1)S(N-1)Td(i) = delay of packet ix(t) = number of packets in transit (in the system) at time t27OutlineMotivationsTiming diagramsMetricsEvaluation techniques28Evaluation TechniquesMeasurements-gather data from a real network-e.g., ping www.berkeley.edu-realistic, specificSimulations: run a program that pretends to be a real network-e.g., NS network simulator, Nachos OS simulatorModels, analysis-write some equations from which we can derive conclusions-general, may not be realisticUsually
View Full Document