EE 122: Network Performance, Queueing Theory, EvaluationOverviewMotivationsOutlineDefinitionsSending One PacketSending one Packet: ExamplesQueueingQueueing ExampleRouter: Store and ForwardStore and Forward: Multiple Packet ExampleCut-ThroughThroughputDelayBandwidth-Delay ProductDelay: Illustration 1Delay: Illustration 2Slide 18Little’s TheoremAnswerSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26ProblemWhat do You Know?What I Assume?Queueing SystemM / M / 1 QueuePoisson Arrival Process and Exponential DistributionPASTA Principle 1/2PASTA Principle 2/2M/M/1 QueueSlide 36Slide 37Slide 38Slide 39Slide 40Evaluation TechniquesEvaluation: Putting Everything TogetherKatz. Stoica F04EE 122: Network Performance, Queueing Theory, EvaluationComputer Science DivisionDepartment of Electrical Engineering and Computer ScienceUniversity of California, Berkeley,Berkeley, CA 94720-1776 September 7, 20042Katz. Stoica F04OverviewMotivationsTiming diagramsQueueing TheoryEvaluation Techniques3Katz. Stoica F04MotivationsUnderstanding network behaviorImproving protocolsVerifying correctness of implementationDetecting faultsMonitor service level agreementsChoosing providersBilling4Katz. Stoica F04OutlineMotivationsTiming diagramsQueueing TheoryEvaluation techniques5Katz. Stoica F04DefinitionsLink 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, etc6Katz. Stoica F04Sending 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 nsec in free space 4 nsec in copper 5 nsec in fiber7Katz. Stoica F04Sending 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/R8Katz. Stoica F04QueueingThe 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 sec9Katz. Stoica F04Queueing ExampleP = 1 Kbit; R = 1 Mbps P/R = 1 msPacket arrivalTime (ms)Delay 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/RP bits Q bits00.517 7.5Time# bits in queue: Q(t)1 Kb0.5 Kb1.5 Kb2 Kbpacket 1, d(0) = 1mspacket 2, d(0.5) = 1.5mspacket 3, d(1) = 2ms10Katz. Stoica F04Router: Store and ForwardA packet is stored (enqueued) before being forwarded (sent)SenderReceiver10 Mbps5 Mbps 100 Mbps 10 Mbpstime11Katz. Stoica F04Store and Forward: Multiple Packet ExampleSenderReceiver10 Mbps5 Mbps 100 Mbps 10 Mbpstime12Katz. Stoica F04Cut-ThroughA packet starts being forwarded (sent) as soon as its header is receivedSenderReceiverR1 = 10 MbpsR2 = 10 MbpstimeHeaderWhat happens if R2 > R1 ?13Katz. Stoica F04ThroughputThroughput 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, 1Gbps = 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 processing14Katz. Stoica F04DelayDelay (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 network15Katz. Stoica F04Bandwidth-Delay Product Window-based flow control: -Send W bits (window size)-Wait for ACKs (i.e., make sure packets reached destination) -RepeatThroughput = W/RTT W = Throughput x RTTNumerical example:-W = 64 Kbytes-RTT = 200 ms-Throughput = W/T = 2.6 MbpstimeSourceDestinationRTTRTTRTTW16Katz. Stoica F04Delay: Illustration 1at point 2at point 1Latest bit seenby time tDelaySender Receiver1 2time17Katz. Stoica F04Delay: Illustration 2Sender Receiver1 221Packet arrival times at 1Packet arrival times at 2Delaytime18Katz. Stoica F04OverviewMotivationsTiming diagramsQueueing TheoryLittle Theorem-M/M/1 QueueEvaluation Techniques19Katz. Stoica F04Little’s TheoremAssume a system at which packets arrive at rate λ(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? systemλ(t) – arrival rated(i) = delay of packet iIntuition:-Assume arrival rate is λ = 1 packet per second and the delay of each packet is d = 5 seconds-What is the average number of packets N in the system?20Katz. Stoica F04AnswerAnswer: N = λ x d = 5 01 2 3 4 5 6 7 8 169 10 11 12 13 14 15timepackets21Katz. Stoica F04Little’s TheoremLatest bit seenby time tSender Receiver1 2timeB(t)d(i) = delay of packet iB(t) = number of bits 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 ?d(i)22Katz. Stoica F04Little’s TheoremLatest bit seenby time tSender Receiver1 2timeB(t)TAverage occupancy = A/Td(i) = delay of packet iB(t) = number of bits in transit (in the system) at time t A= aread(i)23Katz. Stoica F04Little’s TheoremLatest bit seenby time tSender Receiver1 2timeB(t)A(m)Pd(m-1)A(m-1)TA = A(1) + A(2) + … + A(m) = P*(d(1) + d(2) + … + d(m))d(i) = delay of packet ix(t) = number of packets in transit (in the system) at time t A= area24Katz. Stoica F04Average occupancyArrival rateAverage delayLittle’s TheoremLatest bit seenby time tSender Receiver1 2timeB(t)A(m)Pd(m-1)A(m-1)TA/T = (P*(d(1) + d(2) + … + d(m)))/T = ((P*m)/T) * ((d(1) + d(2) + … + d(m))/m)d(i) = delay of packet iB(t) = number of bits in transit (in the system) at time t A= area25Katz. Stoica F04Little’s TheoremLatest bit seenby time tSender Receiver1
View Full Document
Unlocking...