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.
Compressing Video for TaskStream Currently, TaskStream allows users to upload videos up to 100 megabytes in size. Therefore, in order to upload a video...
PPMexe: PPM for Compressing Software Milenko Drini?? and Darko Kirovski? c ? Computer Science Department, UCLA, Los Angeles, USA ? Microsoft Research, ...
Face Fixer Compressing Polygon MeshesFace Fixer Compressing Polygon Meshes隐藏>> UNC Technical Report TR-00-04 Face Fixer: Compressing Polygon Meshes with ...
Compressing Hexahedral Volume Meshes Martin Isenburg? University of North Carolina at Chapel Hill Pierre Alliez? INRIA Sophia-Antipolis Abstract Unstructured ...
Compressing Mixed-State Sources by Sending Classical Information_专业资料。We consider visible compression for discrete memoryless sources of mixed quantum ...
Managing Gigabytes Compressing and Indexing Documents and Images_专业资料。As today’s information explosion generates greater and greater volumes of raw data...
Compressing File Collections with a TSP-Based Approach Dimitre Trendafilov Nasir Memon Torsten Suel Department of Computer and Information Science Technical ...
Compressing cube-connected cycles and butterfly networks We consider the simulation of large cube-connected cycles (CCC) and large butterfly networks (BFN)...
The objectives for compressing DEMs are obtain...更多>>Abstract. Wavelet decomposition is a well-known technique to compress image data. Here, we have ...
Re-Store: A System for Compressing, Browsing, and Searching Large Documents (Extended Abstract of Invited Presentation) Alistair Moffat Raymond Wan ...
热门文档