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

compressing forwarding tables for datacenter scalability

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

whentheavailablerunningtimeisverylimitedwhiletheseconddirectionrequiresalongerrunningtime.

(i)We rstcountforeachoftheelementsinthe rstcolumn,thenumberofdistinctentriesinwhichitappears.Asdiscussedearlier,duplicatedentrieshavenoin uenceontheobtainedencodingwidth.Basedonthesenumbersofdistinctappearances,wecancalculateacorrespondingdistribution.Wecanthenencodethis rstcolumnbyaHuffmancoding[24]basedonthisdistribution.Giventhisencodingofthe rstcolumn,wecan ndanencodingschemeforthewholetablebyencodingthesecondcolumnbytheoptimalconditionalencodinggiventheencodingofthe rstcolumn.Anotheroptionforanencodingschemeisobtainedsimilarlybyconsideringthetwocolumnsinareverseorder.ByLemma5andTheorem6,itisguaranteedthatbothoptionsperformatleastaswellasanencodingschemecomposedofthetwoHuffmancodingsforeachofthetwocolumns.Finally,wecanencodethegiventwo-columnFIBtablesbythebestofthetwooptions,i.e.theonethatyieldsasmallerencodingwidth.

(ii)We ndtheencodingschemeobtainedbythealgorithmforgeneralFIBtablespresentedinSectionIII-B.Then,weconsider(independently)asthegiven(constrained)encoding,eachofthetwoencodingsforthetwocolumnscomposingthesolution.Foreachofthem,we ndtheoptimalconditionalencodingoftheothercolumn.Again,byLemma5andTheorem6,itisguaranteedthatbothoptionsperformatleastaswellastheoriginalsolutiongivenbythealgorithm.V.LOWERBOUNDSONTHEOPTIMALENCODINGWIDTH

OFTWO-COLUMNFIBTABLESWewouldlikenowtosuggestadditionallowerboundsontheoptimalencodingwidthofagiventwo-columnFIBtableAasde nedabove.WecancalculatethisboundwithoutsolvingtherelaxedFIBencodingproblem.

LetagainGA=<L+R,E>=<S1+S2,E>with|S|S=n=2W.We rstrecallanadditionalde nitionfrom1|=graph2|theory.

De nition5(EdgeCover).ForanundirectedgraphG=<V, E>,asetofedgesS EiscalledanedgecoverofGif(x,yat)least∈S{x,y}=V,i.e.eachoftheverticesinVisincidentononeoftheedgesinS.

Clearly,GAdoesnotincludeanyisolatedvertices,i.e.anyvertexisconnectedtoatleastonevertexandthevalueitrepresentsappearsinatleastoneoftherowsofA.Therefore,anedgecoveralwaysexists.ForagraphG,wedenotebyρ(G)theedgecoveringnumberofG,i.e.theminimalnumberofedgesinanedgecoverofG.We rstshowasimplepropertyofρ(GA).

Lemma7.Theedgecoveringnumberρ(G)≤2·(n 1).

A)ofG≤ρ(GAsatis esnAProof.Considertheedgesinaminimaledgecoverinanarbi-traryorder.The rstedgecoverstwovertices.Anyadditionaledgeaddsoneortwoverticestothesetofverticescoveredbypreviousedgesintheedgecover.Sincethereare2nverticesinGAthenclearlyn≤ρ(GA)≤2n 1.Toshowthat

ρ(GA)≤2n 2,weshowthattheremustbetwoindependentedgesinGA,i.e.edgesthatdonotshareanyvertex.Consideranedge(s1,i,s2,j)fori,j∈[1,n].IfalltheotheredgesinEshareatleastonevertexwith{(s1,i,s2,k)|k∈[1,n]} thisedge,wemusthavethatE={(s)1,,k,s(s2,j)|k∈[1,n]}.Then,forinstancetheedges(s1,i,s2,k1,k,s2,j)fork=i,jareindependent.Finally,thetwoindependentedgescancon-tributetwocoveredverticestotheedgecoverandnecessarilyρ(GA)≤2n 2=2·(n 1).

Letα=ρ(GA)/n.ThenexttheoremsuggestsalowerboundontheoptimalencodingwidthofAbasedonthevalueofρ(GA).

Theorem8.TheoptimalencodingwidthofAsatis es

OPT(A)≥2·(W+α 1)

α.(20)

Proof.ForGA=<S1+S2,E>,letS EbeanedgecoverofGAofsizeρ(GA)=α·n.LetCtableencodingschemeofAA=(σ.Wewill1,σshow2)beanarbitraryFIBthat

(x,ymax)∈S (σ1(x))+ (σ2(y))≥2·(W+α 1)

α.(21)Thus,sinceS Ethennecessarily

(C2·(W

(x,y)∈E

(σ1(x))+ (σ2(y))≥+α 1)

A)=max α.

(22)Todoso,weconsiderthesubsetoftherowsofArepresentedbytheedge((d11

ρ(GcoverS.LetD=

A),dρ|D|1,d=2),...,(dρ(G1

2(GA)))representtheserows,s.t.A)=α·S1= ρi=1(Gn.ByDe nition5oftheedgecover,

A){di appear1}andSatleast2=ρoncei=1(GA){di

inthe2},i.e.allthe

elementsofS1 rstcolumnoftherowsofDaswellasalltheelementsofSLetX2inthesecond.D(CA)denotethetotalsumofcodewordlengthsoftheelementsinDusingtheencodingCAX D(CA)= =(σ(G1,σ2),s.t.

ρi=1A) (σ1(di1))+ (σ2(di

2)).

BymanipulatingKraft’sinequality,wecanhavethatthetotalsumofcodewordlengthsofthendistinctelementsineachcolumnisatleastn·W.Ofcourse,theotherα·n n=(α 1)·nelementsineachcolumnareencodedinatleastonebiteach.Thus,ρ(X GA)

D(CA)=

(σ1(di1))

+

(σ2(di

2))i=1

ρ(GA)

ρ(GA)

=

(σ

1(di1))

+

(σ2(di2))

i=1

i=1

≥n·W+(α 1)·n+n·W+(α 1)·n=2n·W+2(α 1)·n.

(23)

Werecallthatthetotalnumberofrowsisα·nandisatleastonerowinDthatisencodedinatleast thusX(CthereDα·n

A)

上一页第9页

你可能喜欢

热门文档

相关文档

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