资源描述：
《mit-science-lectures-lect11b_mit》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、MIT18.996:TopicinTCS:InternetResearchProblemsSpring2002Lecture11April24,2002Lecturer:MarceloTorresScribe:BenLeong11.1OpenLoopCongestionControlFromPowerpointslides.11.1.1ErlangLossModelAssumethatwehavekchannelsandthatcallsarriveatanarrivalrateλandeachcalldepartsatarateµ=1.WecanthenconstructaMar
2、kovmodelfortheprocessasshowninFigure11.1.llll012k123kFigure11.1.ErlangLossModelThebalanceequationsforthemodelareasfollows:λΠ0=Π1λΠ1=Π2...λΠk−1=ΠkkΠi=1i=1Thesolutiontothesebalanceequationsyields:λkΠ=k!kkλii=1i!Hence,wewillacceptuptonconnectionswhere(λn)kk!<ρk(λn)ii=1i!11-1MIT18.996Lecture11
3、—April24,2002Spring2002Suppose(λn)→ρ∗>1,thenkk11P[X=k]=1−ρ∗ρ∗k11Πk≈1−<ρρ∗ρ∗Wecanobtainnbysolvingkkk1−<ρλnλnThemaindifferencebetweencircuitswitchingandpacketswitchingisthattheformerhasfixedcapacitychannelsandafinitenumberofchannels.11.1.2SmallBufferModelnInthesmallbuffermodel,wehav
4、ensourcesXi,1≤i≤n.Lossoccurswheni=1Xi(t)>C.WeassumethatXi(t)areindependentidenticallydistributedrandomvariablesandwewanttofindnsuchthatnP[Xi(t)>C]<ρi=1n2AlthoughweoftenapplytheCentralLimitTheorem:i=1Xi∼N(nµ,nσ)whenwewishntoapproximateP[i=1Xi>µX¯+cn],thisapproximationdoesnotworkwellwhenweare
5、work-inginthetailregion.HenceweusetheChernoffBound.AssumethatM(s)=logE(esX)exists.ThenforanyrandomvariableY,xsXP[Y≥0]=P[e≥1]sX≤E[e](∀s≥0)nsXP[X≥0]≤E[ei]ii=1=E[esXi]n1nlogP[Xi≥0]≤Mx(s)ni=1ns(X−C)logP[X≥0]=logE[ei]ii=1≤nMx(s)−sCTherefore,toobtainn,weletnMx(s)−sC≤ρ,andfindswhichminimizestheR
6、HSof:logρ+sCn≤Mx(s)11-2MIT18.996Lecture11—April24,2002Spring200211.1.3LargeBufferModelInthismodel,theinputisgivenbyA=A(t):t≥0.Supposeψ(s)exists,where1sA(t)ψ(s)=limlogE[e]t→∞tandthesystemservesworkatrateM.Theorem11.1(Glynn&Whitt-1994).Wheres∗istherootofψ(s)=sM,1∗logP[W>x]→−sλAgoodapproximation
7、isgivenby:−s∗xP[W>x]≈CeWherethereareksources,eachwiththecumulativemomentgeneratingfunctionsψi(s),nψ(s)=nkψk(s)k=1Tokeepthelossprobabilitylessthane−δx,weletψ(s)−δM≤0nψ(s)k⇒nk≤Mδk=111-3
