EECS 122 Introduction to Computer Networks Transport Analysis Computer Science Division Department of Electrical Engineering and Computer Sciences University of California Berkeley Berkeley CA 94720 1776 Katz Stoica F04 Outline Exponential averaging and its applications Retransmission timeout RTO computation Little s Theorem revisited Katz Stoica F04 2 Exponential Averaging Let X1 X2 XN be a series of measurements Then average value Ai after the i th measurement is computed as Ai Ai 1 1 Xi where is a constant between 0 and 1 Note that assuming A0 0 Ai 1 X1 1 X2 1 XN What is the role of What does control Katz Stoica F04 3 Exponential Averaging Example X constant A converges to X X A 1 2 3 4 5 6 7 8 9 10 iteration Katz Stoica F04 4 Exponential Averaging Example Maintaining queue size in RED Katz Stoica F04 5 Exponential Averaging Example RTT estimation in TCP Measure RTT for each packet ACK pair Compute average of RTT as EstRTT x EstRTT 1 x RTT is 0 9 or 0 8 Katz Stoica F04 6 Moving Window Average Let X1 X2 XN be a series of measurements Then average value Ai after the i th measurement is computed as Ai Xi 1 Xi 2 Xi w W where W is the window size How do exponential averaging and moving window averaging compare Katz Stoica F04 7 Outline Exponential averaging and its applications Retransmission timeout RTO computation Little s Theorem revisited Katz Stoica F04 8 Retransmission Timeout RTO Computation The Problem Timeout RTT RTT Timeout Timeout too long inefficiency Timeout too short duplicate packets Katz Stoica F04 9 RTO Computation Original Algorithm Measure RTT for each packet ACK pair then perform 1 EstRTT x EstRTT 1 x RTT where is 0 9 or 0 8 2 RTO 2 x EstRTT Katz Stoica F04 10 RTO Computation Jacobson Karels Algorithm Measure RTT for each packet ACK pair then perform 1 Err RTT EstRTT 2 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 Katz Stoica F04 11 RTO Computation Karn Partridge Algorithm Add 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 Katz Stoica F04 12 Outline Exponential averaging and its applications Retransmission timeout RTO computation Little s Theorem revisited Katz Stoica F04 13 Little s Theorem Assume 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 system What is the average number of packets in the system d i delay of packet i a t arrival rate system Intuition 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 Katz Stoica F04 14 Little s Theorem 1 Latest bit seen by time t d i delay of packet i x t number of packets in transit in the system at time t 2 Sender Receiver x t time T What is the system occupancy i e average number of packets in transit between 1 and 2 Katz Stoica F04 15 Little s Theorem 1 Latest bit seen by time t d i delay of packet i x t number of packets in transit in the system at time t Sender 2 Receiver x t S area time T Average occupancy S T Katz Stoica F04 16 Little s Theorem 1 Latest bit seen by time t d i delay of packet i x t number of packets in transit in the system at time t 2 Sender Receiver S N S N 1 P d N 1 x t S area time T S S 1 S 2 S N P d 1 d 2 d N Katz Stoica F04 17 Little s Theorem 1 Latest bit seen by time t d i delay of packet i x t number of packets in transit in the system at time t 2 Sender Receiver S N P S N 1 d N 1 x t S area time T Average S T P d 1 d 2 d N T occupancy P N T d 1 d 2 d N N Average arrival time Average delay Katz Stoica F04 18 Little s Theorem 1 Latest bit seen by time t d i delay of packet i x t number of packets in transit in the system at time t 2 Sender Receiver S N a i S N 1 d N 1 x t S area time T Average occupancy average arrival rate x average delay Katz Stoica F04 19
View Full Document
Unlocking...