EECS 122: Introduction to Computer Networks Transport AnalysisOutlineExponential AveragingExponential Averaging: ExampleSlide 5Slide 6Moving Window AverageSlide 8Retransmission Timeout (RTO) Computation: The ProblemRTO Computation: Original AlgorithmRTO Computation: Jacobson/Karels AlgorithmRTO Computation: Karn/Partridge AlgorithmSlide 13Little’s TheoremSlide 15Slide 16Slide 17Slide 18Slide 19Katz, Stoica F04EECS 122: Introduction to Computer Networks Transport AnalysisComputer Science DivisionDepartment of Electrical Engineering and Computer SciencesUniversity of California, BerkeleyBerkeley, CA 94720-17762Katz, Stoica F04OutlineExponential averaging and its applicationsRetransmission timeout (RTO) computationLittle’s Theorem (revisited)3Katz, Stoica F04Exponential AveragingLet X1, X2, …, XN be a series of measurementsThen average value Ai after the i-th measurement is computed as Ai = Ai-1 + (1 - ) Xi where is a constant between 0 and 1Note that (assuming A0 = 0): Ai = (1 - ) X1 + (1 - ) X2 + (1 - ) XN What is the role of ? What does control?4Katz, Stoica F04Exponential Averaging: ExampleX constant; A converges to XA1 23 4 5 6 7 8 9 10…Xiteration5Katz, Stoica F04Exponential Averaging: ExampleMaintaining queue size in RED6Katz, Stoica F04Exponential Averaging: ExampleRTT estimation in TCPMeasure RTT for each packet/ACK pairCompute average of RTT as-EstRTT = x EstRTT + (1 - ) x RTT is 0.9 (or 0.8)7Katz, Stoica F04Moving Window AverageLet X1, X2, …, XN be a series of measurementsThen average value Ai after the i-th measurement is computed as Ai = (Xi-1 + Xi-2 + … + Xi-w)/W where W is the window sizeHow do exponential averaging and moving window averaging compare?8Katz, Stoica F04OutlineExponential averaging and its applications Retransmission timeout (RTO) computationLittle’s Theorem (revisited)9Katz, Stoica F04Retransmission Timeout (RTO) Computation: The ProblemTimeout too long inefficiencyTimeout too short duplicate packets RTTTimeoutTimeoutRTT10Katz, Stoica F04RTO Computation: Original AlgorithmMeasure RTT for each packet/ACK pair, then perform1. EstRTT = x EstRTT + (1 - ) x RTT, where is 0.9 (or 0.8) 2. RTO = 2 x EstRTT11Katz, Stoica F04RTO Computation: Jacobson/Karels AlgorithmMeasure RTT for each packet/ACK pair, then perform1. Err = RTT - EstRTT2. EstRTT = EstRTT + (1 – ) x Err (Note: equivalent to EstRTT = x EstRTT + (1 - ) x RTT)3. DevRTT = x DevRTT + x |Err|4. RTO = EstRTT + 4 DevRTT where = 0.9 and = 1/8 •DevRTT represents the mean of the deviation (like standard deviation) of the RTT•Why do we need DevRTT?12Katz, Stoica F04RTO Computation: Karn/Partridge AlgorithmAdd the following two considerations to Jacobson/Karels algorithm-EstRTT is updated only when an ACK is received before the timeout expires. Why?-If a packet timeouts, double EstRTT. Why?13Katz, Stoica F04OutlineExponential averaging and its applicationsRetransmission timeout (RTO) computationLittle’s Theorem (revisited)14Katz, Stoica F04Little’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?15Katz, Stoica F04Little’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 ?16Katz, Stoica F04Little’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= area17Katz, Stoica F04Little’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= area18Katz, Stoica F04Average 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= area19Katz, Stoica F04Little’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
View Full Document
Unlocking...