University:
Massachusetts Institute of Technology
Course:
18.996 | Topics in Theoretical Computer Science: Internet Research Problems
Academic year:

2023
Views:

136

Pages:

3
Author:

Leland Mcdonald

MIT 18.996: Topic in TCS: Internet Research Problems Lecture 11 11.1 Open Loop Congestion Control From Powerpoint slides. 11.1.1 Erlang Loss Model Assume that we have k channels and that calls arrive at an arrival rate λ and each call departs at a rate µ = 1. We can then construct a Markov model for the process as shown in Figure 11.1. λ 0 λ λ 1 1 λ 2 k 2 3 Figure 11.1. Erlang Loss Model The balance equations for the model are as follows: λΠ0 = Π1 λΠ1 = Π2 .. . λΠk−1 = Πk k Πi = 1 i=1 The solution to these balance equations yields: Πk = λk kk! λi i=1 i! Hence, we will accept up to n connections where (λn)k k! k (λn)i i=1 i! 11-1 < ρ k Suppose (λn) k → ρ∗ > 1, then k 1 P [X = k] = 1− ∗ ρ k 1 1 Πk ≈ < ρ 1− ∗ ρ∗ ρ We can obtain n by solving 1 ρ∗ k k k 1− < ρ λn λn The main difference between circuit switching and packet switching is that the former has fixed capacity channels and a finite number of channels. 11.1.2 Small Buffer Model In the small buffer model, we have n sources Xi , 1 ≤ i ≤ n. Loss occurs when ni=1 Xi (t) > C. We assume that Xi (t) are independent identically distributed random variables and we want to find n such that n P[ Xi (t) > C] < ρ i=1 n 2 Although we often n apply the Central Limit Theorem: i=1 Xi ∼ N(nµ, nσ ) when we wish to approximate P [ i=1 Xi > µX̄ +cn ], this approximation does not work well when we are working in the tail region. Hence we use the Chernoff Bound. Assume that Mx (s) = log E(esX ) exists. Then for any random variable Y , P [Y ≥ 0] = P [esX ≥ 1] ≤ E[esX ] (∀ s ≥ 0) n Xi ≥ 0] ≤ E[es Xi ] P[ i=1 = E[esXi ]n n 1 log P [ Xi ≥ 0] ≤ Mx (s) n i=1 n Xi ≥ 0] = log E[es( Xi −C) ] log P [ i=1 ≤ nMx (s) − sC Therefore, to obtain n, we let nMx (s) − sC ≤ ρ , and find s which minimizes the RHS of: n≤ log ρ + sC Mx (s) 11-2 11.1.3 Large Buffer Model In this model, the input is given by A = A(t) : t ≥ 0. Suppose ψ(s) exists, where 1 log E[esA(t) ] t→∞ t ψ(s) = lim and the system serves work at rate M. Theorem 11.1 (Glynn & Whitt - 1994). Where s∗ is the root of ψ(s) = sM , 1 log P [W > x] → −s∗ λ A good approximation is given by: P [W > x] ≈ Ce−s ∗x Where there are k sources, each with the cumulative moment generating functions ψ i (s), ψ(s) = n nk ψk (s) k=1 To keep the loss probability less than e −δx , we let ψ(s) − δM ≤ 0 n ψk (s) ≤ M nk ⇒ δ k=1 11-3

18.996 Lecture 11 Notes

Related Documents

Recommended Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock