Measurement-based Admission ControlPapers coveredSlide 6Equivalent Token Bucket FilterThe admission control algorithmThe admission control algorithm (ctd…)Measurement-based connection admission control (Gibbens et.al)The Basic ModelThe Basic Model (ctd…)The basic model (ctd…)Slide 30A Framework for Robust Measurement-Based Admission ControlImpulsive load modelImpulsive Load Model (ctd…)Slide 41Slide 42Slide 43Slide 44Slide 46Slide 47The Continuous Load ModelMemoryless MBACSlide 52Slide 54Slide 55Slide 56Slide 60MBAC with Estimation MemorySlide 63Slide 64Slide 65Slide 66Robust MBACSlide 68Slide 69Slide 70Slide 71Robust MBACSlide 73Slide 74Measurement-based Admission ControlCS 8803NTM Network MeasurementsParag ShahPapers covered•Sugih Jamin, Peter B. Danzig, Scott Shenker, Lixia Zhang, "A Measurement-based Connection Admission Control Algorithm for Integrated Services Networks", IEEE/ACM Transactions on Networking, 5(1):56-70. February 1997.•R.J. Gibbens and F.P.Kelly, "Measurement-based connection admission control". In International Teletraffic Congress Proceedings, June 1997.•Matthias Grossglauser, David N. C. Tse, "A Framework for Robust Measurement-based Admission Control", IEEE/ACM Transactions on Networking, 7(3):293-309, June 1999.MBAC in Integrated Services Packet Networks(Jamin et. Al)•Admission control algorithm done under CSZ scheduling algorithm•Multiple levels of predictive service with per-delay bounds that are order of magnitude different from each other•Approximate worst-case parameters with measured quantities (Equivalent Token Bucket Filter)•Gauranteed services use WFQ and Predictive services use Priority queueingEquivalent Token Bucket Filter: aggregate bandwidth utilization for flows of class j: experienced packet queueing delay for class jDescribe existing aggregate traffic of each predictiveclass with an equivalent token bucket filter with parametersdetermined from traffic measurement.The admission control algorithmFor a new predictive flow α:1. Deny if sum of current and requested rates exceeds targeted link utilization levels2. Deny of new flow violates delay bounds at same or lower priority levels:The admission control algorithm (ctd…)For a new guaranteed service flow:1. Deny of bandwidth check fails2. Deny when delay bounds are violatedMeasurement-based connection admission control (Gibbens et.al)•Performance of MBAC depends upon statistical interactions between several timescales (packet, burst, connection admission, connection holding time)•Buffer overflow happens when:•Extreme measurement errors allow too many sources •Extreme behaviour by admitted sources•They are analyzed at the following timescales: •Admission decision and holding times•Timescales comparable to busy period before overflowThe Basic Modelas the load produced by a connection of class j at time t.No. of connections at class jPeak rate of class jMean rate of class jResource capacityrate of load lost at a resource of capacity CThe Basic Model (ctd…)Let connections of class j arrive in a Poisson stream of rate Let holding times of accepted connections be independent and exponentially distributed with parameterLetand let be a subset of Suppose a connection arriving at time t is accepted ifand is rejected otherwise.Back-off period: Period between the rejection of a connectionand the time when the first connection then in progress endsLet according as at time t the system is in a backoff or notis then a Markov Chain with off-diagonal transition rates:The basic model (ctd…)is a vector with a 1 in the jth component zeros otherwiseacceptance probabilityThe proportion of load lost is where the expectation is taken over the state n of the Markov chain.t : timescale associated with admission decisions and holding timesτ : shorter time period, typically time before a packet buffer overflowA Framework for Robust Measurement-Based Admission Control•Assuming that the measured parameters are the real ones, can grossly compromise the target performance of the system.•There exists a critical timescale over which the impact of admission decision persists.Impulsive load model•Bufferless single link with capacity c•Bandwidth fluctuations are identical stationary and independent of each other (mean = µ, variance = σ)•Normalized capacity n – (c/µ): Steady-state overflow probability•Infinite burst of flows arrive at time 0•After time 0, no more flows are accepted and the flows stay forever in the system•Permits study of impact of performance errors on on the number of flows and on overflow probabilityImpulsive Load Model (ctd…)The number of admissible flows in the system is the largestinteger m such that: bandwidth of the ith flow at time tFor large n,If mean and variance are known a priori, then the no. offlows m* to accept should satisfyWhere Q(.) is the ccdf of a N(0,1) Gaussian RVImpulsive Load Model (ctd…)Actual Steady-state Overflow probability:For reasonably large cIf mean and variance are not known a priori, and if it uses Estimation from initial bandwidth of flows in certaintyEquivalence, by Central Limit Theorem,Impulsive Load Model (ctd…)We want an approximation of average overflow probabilityIn steady state and for large t and compare it to the targetTo find an approximation of the distribution for Mo:We compare the estimated and actual means:Can be interpreted as the scaled aggregateBandwidth fluctuation at time 0 around the meanThe estimated standard deviation:is GaussianDeviation is of the order ofDistribution of Mo can be approximated by a linearization of The relationship around a nominal operating point, which is the operating point under perfect knowledgeFurther, is the order of the estimation error around m* (perfect knowledge) Further,Letbe the random number of flows admitted under MBACwhere capacity is nµ.. Then the sequence of random variablesconverges to a distribution to a random variableRandomness is due to both randomness in the number of flowsAdmitted, as well as randomness in the bandwidth demands of those flows.The aggregate load at time t can be approximated byIs the approximation for the scaled aggregate Bandwidth fluctuation at time tFurther,For large n, the overflow probability at time tExponentially distributed holding time for which a flowStays in the systemAssumption: [Worst Case] There are always flows waiting to enter the system(admitted)The auto-correlation function of the flow:The Continuous
View Full Document