Networks: Some Analysis …Jean Walrandwww.eecs.berkeley.edu/~wlrWalrand 2OutlinePerformance Evaluation? How well does TCP work?? Simple Model and Fixed Point ModelDistributed Optimization? User and Network Optimization? Stability of closed loop systemSome basic models? Classical queuing resultsWalrand 3Performance EvaluationObjective:? Understand behavior of TCP (AIMD)Motivation:? Compare with other protocols: Compatibility? Understand limitations/how to improveSimple Model:? Express throughput as function of loss rateFixed Point Model:? Calculate throughputWalrand 4Performance EvaluationSimple ModelWalrand 5Performance EvaluationSimple Model (cont)-101234560 0.2 0.4 0.6 0.8 1 1.2LRT (packets)Walrand 6Performance EvaluationFixed PointKey Ideas:? Sources adjust rate based on observed losses? Losses depend on rate of sourceRate(Losses):? Instantaneous rate x(t): AIMD? Controlled by “Poisson Losses” (?)? Analysis => E(x(t)) = R(?)Losses(Rate):? Router queue fed by arrivals? Loss rate = increasing in queue length? Analysis => ? = L(R)Walrand 7Performance Evaluation Fixed Point (cont)Summary:???Walrand 8Performance Evaluation Fixed Point (cont)Analysis:dW(t) ? dt/T – [W(t)/2]dN(t)E[dW(t)] ? dt/T – E[W(t)dN(t)]/2? dt/T – E[W(t)]E[dN(t)|W(s), s < t]/2? dt/T – E[W(t)]?(t)dt/2; ?(t) = f(qm(t – d)); qm(t) = E(q(t))dx(t) ? W(t)/T – Cdtdqm(t)/dt = axm(t) + (1 – a)qm(t)dqm(t)/dt ? axm(t) + (1 – a)qm(t)dxm(t) ? Wm(t)/T - CdtNumerical integration=> Wm(t)…Walrand 9Stability of Systems Lyapunov Function: DeterministicNonlinear system:dx(t)/dt = f(x(t))Want to show that x(t) ? x*Show that there is some function V(x(t)) such that? dV(x(t))/dt < - aV(x(t)) whenever x(t) ? x*? For all ? > 0, there is ? > 0 s.t. ||x – x*|| < ? if V(x) < ? …. V(x) > 0 for x ? x*; V(x*) = 0Then x(t) ? x*.Note that dV(x(t))/dt = ? V(x(t))dx(t)/dt = ? V(x(t)) f(x(t))Walrand 10Stability of Systems Lyapunov Function: StochasticStochastic system:P[x(n+1) = j|x(n) = i] = P(i,j); i,j in {0, 1, …}Assume irreducibleWant to show that {x(n)} is positive recurrent, i.e., that the fraction of time in any state is positive.Assume there is some V(x) such that? E[V(x(n+1)) – V(x(n))|x(n) = x] < - a < 0 whenever x is not in some finite set A? E[V(x(n+1)) – V(x(n))|x(n) = x] < ??for all xThen {x(n)} is PR. Indeed: V must increase a positive fraction of the time, so x must spend a positive fraction of the time in A.Walrand 11Control Theory Stability of Linear SystemsLinear system: [x(t) is n-dimensional]x’(t) = Ax(t) [Here, x’(t) = dx(t)/dt]When does x(t) remain stable for every x(0)?Example: x’(t) = ax(t) => x(t) = exp{at}x(0) => stable if a < 0With n > 1, x(t) = exp{At}x(0) => stable if eigenvalues of A have < 0 real part[In general, exp{At} = ? Fk(t)exp{?kt} where the Fkare polynomial matrices.]Walrand 12Duality Theory Nonlinear OptimizationConsider: A := min{f(x) | g(x) ? 0}Fix p ? 0. Then h(p) := min{f(x) + pg(x)} ? AIndeed: h(p) ? min{f(x) + pg(x) | g(x) ? 0} ? AUnder suitable conditions, max{h(p), p ? 0} = AExtends to multiple inequality constraintsExample: f(x) = - log(x1) – 2log(x2)g(x) = 3x1+ x2– 3Then h(p) = min{3px1– log(x1)} + min{px2– 2log(x2)} – 3p= 3log(p) – 3p + 3 + log(3/4)max{h(p), p ? 0} = log(3/4)Also, to find A, by KT, set d(f(x) + pg(x))/dxj= 0 => f(x) + pg(x) = h(p)then p should maximize h(p)Note the decompositionWalrand 13Duality Theory Nonlinear OptimizationPrimal: A := min{f(x) | g(x) ? 0}Dual: B = max{h(p), p ? 0} with h(p) := min{f(x) + p’g(x)}Theorem: under suitable conditions, A = BEquivalently:Primal: A := max{f(x) | g(x) ? 0}Dual: B = min{h(p), p ? 0} with h(p) := max{f(x) - p’g(x)}Theorem: under suitable conditions, A = BWalrand 14Primal/Dual Nonlinear OptimizationPrimal: max U1(x1) + U2(x2) + U3(x3)s.t. x1+ x2? 1, x1+ x3? 1Dual: minimize B1(p1+ p2) + B2(p1) +B3(p2) + p1+ p2s.t. p1? 0, p2? 0where Bj(a) = max|xjUj(xj) – axjNetwork optimization: Choose pricesUser optimization: Choose rateSocial optimization: Coupled problemProtocol: Modified TCP solves user’s problem with suitablecost for marked ACKs set by network.Walrand 15Basic Models Classical Queuing Models: M/M/1In next dt seconds, arrival w.p. ?dt, departure w.p. ?dtJustified with exponential arrivals and service timesQueue length x(t) is Markov: Given x(t), past and future are independentQuestions of interest: ? Fraction of time that x(t) = n: converges to ?(n) [ergodicity]? Probability that x(t) = n: converges to ?(n) [asymptotic stationarity]? Probability that an arrival finds n in queue: ?(n) [PASTA]? Calculating ?(n): balance equations? Departure process from stationary queue: Poisson [time-reversibility]? Delay through stationary queue: Exponential? Extension to network: Jackson??Walrand 16Basic Models Classical Queuing Models: Loss NetworksPoisson arrivals, exponential holding times, parallel serviceCan calculate P(number of busy servers = n)Insensitivity result: P(number of busy servers = n) remains the same if the distribution of the holding times is not exponentialExtends to networksn??Walrand 17Basic Models Classical Queuing Models: Large DeviationsIf average rate is less than service rate, it is unlikely that the queue builds up muchIn fact, P(queue > x) ? K exp{- a(c)x} for x largeThe minimum value of c so that a(c) > b is the effective bandwidth of A, say EB(A)Fact: If A1 and A2 are independent, thenEB(A1 + A2) = EB(A1) + EB(A2)Extension to
View Full Document
Unlocking...