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

compressing forwarding tables for datacenter scalability

ROTTENSTREICHetal.:COMPRESSINGFORWARDINGTABLESFORDATACENTERSCALABILITY141

Forexample,inTableI,therearen3=3valuesinthethirdcolumn,andS3={Te12/1,Gi11/8,Gi11/24}.

De nition2(Pre xEncoding).ForasetofelementsS,anencodingσisaninjectivemappingσ:S→B,whereBisasetofbinarycodewordsofsize|B|=|S|.Anencodingiscalledapre xencodingifnobinarycodewordinBisapre x(start)ofanyotherbinarycodewordinB.

De nition3(FIBEncodingScheme).AnencodingschemeCAofaFIBTableAisanorderedsetofdpre xencodingsCA=(σ1,...,σd).Thatis,eachσjencodescolumnj,andisconstrainedtobeapre xencoding.

De nition4(FIBEncodingWidth).LetCA=(σ1,...,σd)beaFIBencodingschemeoftheFIBtableA.Theencodingwidth (CA)ofCAisde nedasthemaximalsumofthelengthsofthedcodewordsrepresentingthedelementsinarowofA,i.e.

d (σj(ai(1) (CA)=maxj)).

i∈[1,h]

j=1

Therefore,wecannowformallypresenttheproblemof

ndinganoptimalFIBtableencodingschemefortableA=

1hh

((a11,...,ad),...,(a1,...,ad))asthefollowingoptimizationproblem.

mins.t.

P

d j=1

(σj(aij))≤P2 (σj(a))≤1

i∈[1,h] j∈[1,d] a∈Sj

a∈Sj

(4a)(4b)(4c)(4d)

a∈Sj

(σj(a))≥0 j∈[1,d], (σj(a))∈Z j∈[1,d],

Example2.LetAbetheFIBtablefromExample1withh=7,d=3,alsodescribedinTableI.I(A).Likewise,letCA=(σ1,σ2,σ3)betheFIBencodingschemeofA.Then,asshowninTableI.I(C),σ3(Te12/1)=0,σ3(Gi11/8)=10,

=11.AsdescribedinTable)=σ3(Gi11/24) I.I(B), (CA di

=max5,5,4,5,5,5,5=maxi∈[1,h]j=1 (σj(aj))

5.

Let’scomparethisschemewitha xed-lengthencodingofeachcolumn.Sincethenumberofdistinctelementsinthed=3columnsofAaren1=5,n2=2andn3=3,ifIAa xed-lengthencodingofAthentheelementsinthejthcolumn d

areencodedin log2nj bits,and (IA)=j=1 log2nj =3+1+2=6.

B.OptimalFIBTableEncodingScheme

ForeachFIBtableA,wedenotebyOPT(A)theoptimalencodingwidthofA,i.e.thesmallestpossibleencodingwidthofanyencodingschemeofAsuchthat

OPT(A)=

CA=(σ1,...,σd)

min

(CA).

(2)

Ourgoalisto ndanencodingschemeCAthatminimizestheencodingwidth (CA),andthereforereachesthisminimum.

III.GENERALFIBTABLES

A.OptimizationProblem

We rstwanttorewritetheproblemof ndingtheoptimalencodingschemeforanyFIBtableAasanoptimizationproblem.

First,itiswellknownthatthesetofcodewordlengthsinapre xencodingexistsiffitsatis esKraft’sinequality[6].Property1(Kraft’sinequality).Thereexistsapre xen-codingσoftheelementsinasetSwithcodewordlengths{ (σ(a))|a∈S}iff

2 (σ(a))≤1.(3)

a∈S

Inthisoptimizationproblem,wetrytominimizethemax-imalencodingwidthofarow(denotedherebyP)while

havingfoursetsofconstraints.The rstset(4a)representsthelimitationonthetotalwidthofeachrow.Thesecondsetofconstraints(4b)requiresthateachoftheencodingsσ1,...,σdshouldsatisfyKraft’sinequality.Thelasttwosets(4c,4d)illustratethefactthatthecodewordlengthofanyelementshouldbeanon-negativeinteger(theconstraints(4b)and(4c)togetherguaranteethatifthenumberofdistinctelementsinacolumnisatleasttwo,thecodewordlengthsarepositive).Foranoptimalsolutiontothisoptimizationproblem,theequalityP=OPT(A)issatis ed.

Theoptimizationproblemcanbealsodescribedasbeingdependentonlyonthecodewordlengths.Todoso,wereplace(forj∈[1,d],a∈Sj)thevalueof (σj(a))byacorrespondingvariable.Inaddition,itiseasytoderivethesetsofcodewordsgiventheirlengths.Todoso,wecan ndforanencodingσi(fori∈[1,d]),thecodewordsoftheelementsofSiinanincreasingorderoftheirrequiredlengths.Foreachelementx∈Si,weallocateanarbitrarycodewordσi(x)intherequiredlengthsuchthatnoneofthepreviouslyallocatedcodewords(forthisencoding)isapre xofthecurrentcodeword.ItiseasytoverifythatKraft’sinequalityguaranteesthatsuchallocationisalwayspossible.

WealsodenotebytherelaxedFIBencodingproblemtheproblemachievedbyomittingthefourthsetofconstraints(4d).Inthisrelaxedproblem,thecodewordlengthsarenotnecessarilyintegers.

B.ApproximationoftheOptimalEncoding

Wenowdescribehowtoobtainaconcreteef cientencodingschemeforanygivenforwardingtablewithanarbitrarynumberofcolumns.We ndforeachtableAofdcolumns,asolutiontotheFIBencodingproblemthatisguaranteedtobewithina xedadditiveapproximationoftheoptimalencodingwidthOPT(A).Morespeci cally,we ndanen-codingschemeCAwithencodingwidth (CA)thatsatis es (CA)≤OPT(A)+(d 1),i.e.itsencodingwidthislargerthantheoptimalencodingwidth(inbits)byatmostthenumberofcolumnsinAminusone.Weemphasizethatthisboundontheadditiveerrorof(d 1)dependsneitheronthenumberofdistinctelementsnj≤2Wj(forj∈[1,d])ineachofthecolumns,noronthenumberofrowshinA.

上一页第4页

你可能喜欢

热门文档

相关文档

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