Performance AnalysisPerformance Analysis TCP delay modeling With applications to HTTP Introduction to queueing theory With a probability refresher TCP throughput analysis (revisited)Delay modelingQ: How long does it taketo receive an objectfrom a Web serverafter sending arequest?Ignoring congestion,delay is influenced by: TCP connectionestablishment data transmission delay slow startNotation, assumptions: Assume one link between clientand server of rate R S: MSS (bits) O: object size (bits) no retransmissions (no loss, nocorruption)Window size: First assume: fixed congestionwindow, W segments Then dynamic window,modeling slow startFixed congestion window (1)First case:WS/R > RTT + S/R: ACK for firstsegment in window returnsbefore window’s worth of datasentdelay = 2RTT + O/RFixed congestion window (2)Second case: WS/R < RTT + S/R:wait for ACK aftersending window’sworth of data sentdelay = 2RTT + O/R+ (K-1)[S/R + RTT - WS/R]TCP Delay Modeling: Slow Start (1)Now suppose window grows according to slowstartWill show that the delay for one object is:RSRSRTTPRORTTLatencyP)12(2 !!"#$%&'+++=where P is the number of times TCP idles at server:}1,{min !=KQP- where Q is the number of times the server idles if the object were of infinite size.- and K is the number of windows that cover the object.TCP Delay Modeling: Slow Start (2)RTTinitiate TCPconnectionrequestobjectfirst window= S/Rsecond window= 2S/Rthird window= 4S/Rfourth window= 8S/Rcompletetransmissionobjectdeliveredtime atclienttime atserverDelay components:• 2 RTT for connectionestab and request• O/R to transmit object• time server idles due toslow startServer idles: P = min{K-1,Q} timesExample:• O/S = 15 segments• K = 4 windows• Q = 2• P = min{K-1,Q} = 2Server idles P=2 timesTCP Delay Modeling (3)RSRSRTTPRTTRORSRTTRSRTTROidleTimeRTTROPkPkPpp)12(][2]2[22delay111!!+++=!+++=++=!==""RTTinitiate TCPconnectionrequestobjectfirst window= S/Rsecond window= 2S/Rthird window= 4S/Rfourth window= 8S/Rcompletetransmissionobjectdeliveredtime atclienttime atserverTCP Delay Modeling (4)!!"##$+=+%=%&=%+++=%+++=&&)1(log)}1(log:{min}12:{min}/222:{min}222:{min22110110SOSOkkSOkSOkOSSSkKkkkLLCalculation of Q, number of idles for infinite-size object,is similar.Recall K = number of windows that cover objectHow do we calculate K ?HTTP Modeling Assume Web page consists of: 1 base HTML page (of size O bits) M images (each of size O bits) Non-persistent HTTP: M+1 TCP connections in series Response time = (M+1)O/R + (M+1)2RTT + sum of idle times Persistent HTTP: 2 RTT to request and receive base HTML file 1 RTT to request and receive M images Response time = (M+1)O/R + 3RTT + sum of idle times Non-persistent HTTP with X parallel connections Suppose M/X integer. 1 TCP connection for base file M/X sets of parallel connections for images. Response time = (M+1)O/R + (M/X + 1)2RTT + sum of idle timesHTTP Response time (in seconds)RTT = 100 msec, O = 5 Kbytes, M=10 and X=5For low bandwidth, connection & response time dominated bytransmission time.Persistent connections only give minor improvement over parallel connections.HTTP Response time (in seconds)RTT =1 sec, O = 5 Kbytes, M=10 and X=5For larger RTT, response time dominated by TCP establishment & slow start delays. Persistent connections now give important improvement: particularly in high delay·bandwidth networks.Queueing Theory Intro Recall router model Want to model Q(t) under real-world,probabilistic A(t) and D(t) Start with a probability refresherµA(t), λD(t)Model of FIFO router queueQ(t)A Quick Probability Refresher A random variable, X, can take on a number ofdifferent possible values Example: the number of students who came to officehours is a random variable with values 1,2,3,… Each time we observe (or sample) the randomvariable, it may take on a different value A random variable takes on each of these valueswith a specified probability Example: X = {0, 1, 2, 3, 4} P[X=0] = .1, P[X=1] = .2, P[X=2] = .4, P[X=3] = .1, P[X=4]= .2 The sum of the probabilities of all values equals 1 Σall values P[X=value] = 1A Quick Probability Refresher Example Suppose we throw two dice and the random variable, X, isthe sum of the two dice Possible values of X are {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} P[X=2] = P[X=12] = 1/36 P[X=3] = P[X=11] = 2/36 P[X=4] = P[X=10] = 3/36 P[X=5] = P[X=9] = 4/36 P[X=6] = P[X=8] = 5/36 P[X=7] = 6/36Note:12Σi=2P[X=i] = 1A Quick Probability Refresher A probability distribution function matcheseach possible value of a random variablewith its associated probabilityA Quick Probability Refresher The cumulative distribution function ofa random variable, X, is defined by CDF: P[X ≤ x] = Σall y=x P[x=y]A Quick Probability Refresher Expected Value Can be thought of a “long term average” ofobserving the random variable a large number oftimes Example: dice E[X] = 2*1/36 + 3*2/36 + 4*3/36 + 5*4/36 +6*5/36 + 7*6/36 + 8*5/36 + 9*4/36 + 10*3/36 +11*2/36 + 12*1/36E[X] = x =ΣAll possible values of xValue * P[X = value]A Quick Probability Refresher Average vs. Expected Value Short term average Suppose a random variable X is sampled N times Let ni = # of X = i was observed Average of samples = (n0*0 + n1*1 + n2*2 + n3*3 + …)/N = n0/N*0 + n1/N*1 + n2/N*2 + n3/N*3 + … As N → ∞, the ratio ni/N becomes pi Thus, E[X] = limN→∞ [n0/N*0 + n1/N*1 + n2/N*2 + n3/N*3 + …] = p0*0 + p1*1 + p2*2 + p3*3 + … = Σ∞i=0 i * piA Quick Probability Refresher Continuous Random Variables In many cases, a random variable takes a value drawnfrom a continuous interval Ex: processing time for a packet may be any real value [0, ∞) The distribution of possible values a continuous randomvariable can take is given by a probability density function,F(x) P(a ≤ x ≤ b) = ⌠ab F(x)dx = Σbi=a P(x = i) E[x] = ⌠-∞∞ xF(x)dx = Σ i * P(x = i)Basic Queueing Theory Elementary notions Things arrive at a queue according to some probabilitydistribution Things leave a queue according to a second probabilitydistribution Averaged over time Things arriving and things leaving must be equal Or the queue length will grow without bound Convenient to express probability distributions as averageratesLittle’s Law Goal Estimate relevant
View Full Document
Unlocking...