文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 文学研究 > compressing forwarding tables for datacenter scalability
侵权投诉

compressing forwarding tables for datacenter scalability

142IEEEJOURNALONSELECTEDAREASINCOMMUNICATIONS,VOL.32,NO.1,JANUARY2014

Toobtainsuchanencoding,weconsidertherelaxedFIBen-codingproblemde nedabove,inwhichthecodewordlengthsarenotnecessarilyintegers.Weshowthatthisoptimizationproblemisconvex,andthusitssolutioncanbefoundbyoneofseveralknownalgorithmsforsuchproblems.Wethenbuildasasolutiontotheoriginaloptimizationproblem,anencodingwithcodewordlengthsachievedbytakingtheceilingofeachofthecodewordlengthsinthesolutionoftherelaxedproblem.Weshowthatthesenewcodewordlengthsleadtoanencodingthatsatis estheadditiveapproximationTheorem1.Let

fromabove.

(¯σ[1,d])bethecodewordj(slengthsj,1)),..., (¯

σ(s ofanoptimaljj,nj))(forj∈solutiontotherelaxedFIBencodingproblem.Further,letC))A=(σ= (¯1,...,σσd)beanencodingschemesatisfying (σforallj∈[1,d],i∈[1,nj(sj,ij(sj,i)) j].Thenwehave:

(i)TherelaxedFIBencodingproblemisconvex.

(ii)Theencodingwidth (CA)oftheencodingschemeCsatis es

A (CA)≤OPT(A)+(d 1).

(5)

Proof.We rstexaminetheconvexityoftherelaxedproblem.

Clearly,itssimpleobjectivefunctionisconvex.Wewouldliketoshowthateachoftheinequalityconstraintfunctions(asafunctionofthecodewordlengths)isconvexaswell.Simply,constraintsinthe rstandthethirdsetsofinequalitycon-straints(4a,4c)areconvexduetotheirlinearity.Inaddition,wewouldnowliketoexaminetheconvexityofthesecondsetofconstraints(4b)representingKraft’sinequality.Todoso,wede nedfunctionsfthedpre xencodings.The1,...,ffunctiondfortheconstraintsoneachoffofcodewordlengthsj(forj∈[1,d])receivesasaparametertheset oftheelementsinSj.as Thefunctionfσ

(σj (j(sj,1)),...,j(a))= n (σj(sj,nj))isde neda∈Si=1j

j2 2 (σj(sj,i)).Weconsidertwoarbitraryencoding

schemes(¯σ1,...,¯σd),( σ1 ,..., σwordlengths (¯σ(sd)withcode-)),..., (¯σ(s

( σ jj,1jj,nj)),j(s∈j,1)),..., ( σ[1,d],respectively.j(sj,nj))fortheelementsinSforjWewouldliketoshowthatjfj(α·σ¯+β·σ )≤α·fandα,β∈[0,1]withαj(¯σ)+β·f+β=1.Here,j( σ)forallj∈[1,d]whenperforminglinearoperationsonthesetofcodewordlengths,werefertoanewsetofcodewordlengths,sothateachofitscodewordlengthsisobtainedbyperformingthelinearoperationsonthecorrespondinglengthintheoriginalset.Basedontheconvexityofthefunctiong(x)=2 x,wehavefj(α·¯σ

+β·σ )= nj

2

α· (¯σj(sj,i))+β· ( σj(s

j,i))

i=1 nj≤

α·2 (¯σ

j(sj,i))

+β·2

( σj(sj,i))

i=1

nj

=α·

2

(¯σj(sj,i))

+β nj

·

2 (

σj(sj,i))i=1

i=1

=α·fj(¯σ)+β·fj( σ).

(6)

Basedontheseproperties,wecan nallydeducethatthere-laxedFIBencodingproblemisconvex.Withthisobservation,

anoptimalsolution,i.e.ageneralizedencoding(withnon-necessarilyintegercodewordlengths)canbefoundbyusingoneoftheseveralknown(polynomialtime)algorithmsforsuchconvexproblems(e.g.theellipsoidalgorithm[22]).Letusdenoteby

(¯σ j(sj,1)),..., (¯σj(sj,nj))thecodewordlengthsofanoptimalsolutiontotheproblem.LetOPT(A)=max r relaxedi∈[1,h]dj=1 (¯

σj(ai

j))bethemaximalencodingwidthofarowinthisoptimalsolutionoftherelaxedproblem.Again,OPTr(A)isnotnecessarilyinteger.Clearly,sincethesetofconstraintsintherelaxedprob-lemisasubsetoftheconstraintsintheFIBencodingproblem,theinequalityOPTr(A)≤OPT(A)holds.Further,sinceOPT(A)isaninteger,wehavethat OPTisalowerboundforOPTr(A) ≤OPT(A),i.e. OPTr(A) (A).Clearly,since (σj(sj,i))= (¯σj(sj,i)) ≥ (¯σj(sj,i)),allthedconstraintsrepresentingKraft’sinequality,satis edbythesolutionoftherelaxedproblem,arealsosatis edbythesetofcodewordlengthsinCA=(σ1,...,σd).

WenowshowthattheencodingwidthoftheencodingschemeCAiswithinaguaranteedadditiveapproximationoftheoptimalencodingwidthofA,OPT(A).Directlyfromthede nitionofCA,wecanhavethat (C A)=imax

d∈[1,h] (σi

d j(aj))=imax

∈[1,h]

(¯σj(ai

j))j=1

j=1

< d i

imax∈[1,h]

(¯σj(aj))+1j=1= dimax

∈[1,h]

(¯σj(aij))

+d=OPTr(A)+d

j=1

≤OPT(A)+d.

(7)

Finally,since (CA)aswellasOPT(A)arebothinte-gers,wecandeducefromthe(strong)inequality (COPT(A)+dthat (CA)<A)≤OPT(A)+(d 1).C.UpperBoundontheOptimalEncoding

WenowpresentasimpleupperboundontheoptimalencodingofanyFIBtablewithanarbitrarynumberdofcolumns.

Considera xed-lengthencodingschemeIAthatencodeseachcolumnjusinga xed-lengthencoding(asseeninExample2).Thenineachcolumnj,itusescodewordsofsizeWj= log2nj ,sinceitneedsatleastnthenj>2Wj 1codewordstorepresenttotalwidthofeachjdifferentvalues.Asaconse-quence,therowinalso xed,andwehave

(I dA)=

Wj=

d log2nj .

(8)

j=1

j=1

The xed-lengthencodingyieldsanupperboundonthe

optimalencodingwidthoftheFIBtable.

上一页第5页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email