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

compressing forwarding tables for datacenter scalability

144IEEEJOURNALONSELECTEDAREASINCOMMUNICATIONS,VOL.32,NO.1,JANUARY

compressing forwarding tables for datacenter scalability

2014

compressing forwarding tables for datacenter scalability

(a)(b)

Fig.2.Atwo-columnforwardingtablewithh=6entriesandn=2W=4(forW=2)distinctelementsineachcolumnwith(a)thetable,and(b)itscorrespondingbipartitegraph.Thenumberofedgesinthegraphequalsthenumberofdistinctentriesintheforwardingtable.

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

1hh

ofA=((a1wecanpresent1,a2),...,(a1,a2)),

itsFIBencodingwidthbasedonGAas (CA)=max(x,y)∈E (σ1(x))+ (σ2(y)).FromtheconstructionofGA,wecanclearlyseethatthelastequationiscompatiblewithDe nition4.

TherepresentationofaFIBtableasabipartitegraphcanhelpustofurtherunderstandtheFIBencodingwidthbasedontoolsfromgraphtheory.Thenexttheoremrelatestheexistenceofanindependentsetofaspeci csizeinthebipartitegraphGAtothevalueofOPT(A).

Theorem4.LetAbeatwo-columnFIBtablewith|S1|=|S2|=n=2WandletGA=<L+R,E>beitscorrespond-ingbipartitegraph.If theredoesnotexistanindependentsetofverticesU=U1U2inGA,sothatU1 L=S1,U2 L=S2and|U1|=|U2|=n2+1,thentheoptimalencodingwidthofAnecessarilysatis esOPT(A)=2W.Namely,theoptimalencodingwidthisachievedbythe xed-lengthencodinganditcannotbeimprovedbyanyvariable-lengthencoding.

Proof.LetCA=(σ1,σ2)beanarbitraryFIBtableencodingschemeofA.Asmentionedearlier,byProperty2,OPT(A)≤2W.Wewouldliketoshowalsothat (CA)≥2WandthereforeOPT(A)≥2W.ByKraft’sinequality,thereare(atleast)n2+1elementsinS1whosecodewordlengthsinσ1areatleastWbits.LetU1denotethesetoftheircorrespondingverticesinL.Likewise,letU2 RdenotethesimilarsetofverticesrepresentingtheelementsinS2withcodewordlengthsofatleastWinσ2.Wethenhavethat|U1|,|U2|≥n2+1.If (CA)<2W,then( i∈[1,h]),i

(σ1(a1))+ (σ2(ai2))≤2W 1.Since( x∈U1,y∈U2), (σ1(x))+ (σ2(y))≥W+W=2W,thennecessarily, ( x∈U1,y∈U2),(x,y)∈/E.ThusU=U1U2isanindependentsetinGA.Since|U1|,|U2|≥n2+1,wehaveacontradiction,andcandeducethatindeed (CA)≥2WandOPT(A)=2W.

B.OptimalConditionalEncodingoftheSecondColumnWenowconsidertheconditionalproblemof ndinganoptimaltwo-columnencodinggiventhattheencodingofthe rstcolumnisknown.

Formally,givenatwo-columnFIBtableAandaknown

¯1,wewanttopre xencodingofoneofitscolumnsσ1:=σ

ndapre xencodingσ2ofthesecondcolumnsuchthattheencodingwidth (CA)oftheFIBencodingschemeCA=(σ1:=σ¯1,σ2)isminimized.WedenotetheFIBencodingwidthofsuchschemebyOPT(A|σ1:=σ¯1),i.e.

¯1)=OPT(A|σ1:=σ

CA=(σ1:=¯σ1,σ2)

A.TheOptimalEncodingWidthofaTwo-ColumnFIBTableThenexttheoremsuggestsalowerboundandanup-perboundontheoptimalencodingwidthofA=

1hh

((a11,a2),...,(a1,a2))forW≥2.Theorem3.LetAbeatwo-columnFIBtablewith|S1|=|S2|=n=2WforW≥2.Then,theoptimalencodingwidthofAsatis es

W+2≤OPT(A)≤2W.

(10)

ProofOutline.In[23],wepresentthefullproofandalsoprovethetightnessoftheseboundsbyexposing,foreachofthem,aFIBtablethatachievesthebound.

TheupperboundofW+W=2WcanbesimplyachievedusingProperty2,basedona xed-lengthencoding.Toshowthelowerbound,weconsidertwooptionsforthecodewordlengthsoftheelementsinS1.IfallofthemequalWbits,atleastoneofthemsharesanentrywithanelementinS2encodedwithtwoormorebits.Likewise,ifthecodewordlengthsarenot xed,wehaveanelementinS1withacodewordlengthofatleastW+1thatsharesanentrywithanotherarbitraryelementinS2encodedinatleastasinglebit.Bothcasesthensuf cetoconclude.

1hh

Anytwo-columnFIBtableA=((a11,a2),...,(a1,a2))canberepresentedbyacorrespondingbipartitegraphGAasfollows.Thetwodisjointsetsarethesetsofdistinctelementsineachofthetwocolumns.Thus,ifanelementappearsinbothofthetwocolumns,itisrepresentedbytwodifferentverticesineachofthetwodisjointsets.EdgesconnectelementsinthetwosetsiftheyappearatleastonceonthesamerowoftheFIBtable.Formally,wede nethegraphGA=<L+R,E>suchthatL=S1,R=S2andE={(x,y)|( i∈

i

[1,h]),(ai1,a2)=(x,y)}.Therefore,duplicatedrowshavenoin uenceontheconstructionofthebipartitegraph,andthegraphdoesnotcontainparalleledges.ItisalsoeasytoseetheindependenceintheorderoftherowsoftheFIBtable.

Example3.Figure2(a)presentsanexampleofatwo-columnforwardingtablewithh=6entriesandn=2W=4(forW=2)distinctelementsinbothcolumns.ThecorrespondingbipartitegraphappearsinFigure2(b).Theverticesontheleftsideofthegraphrepresentthen=4distinctelementsinthe rstcolumn,whiletheverticesontherightsiderepresentthendistinctelementsinthesecondcolumn.Thenumberofedgesinthegraphequalsthenumberofdistinctentriesintheforwardingtable.

min

(CA).

(11)

Wewouldliketosuggestanalgorithmto ndsuchanoptimalconditionalencoding.LetAbeatwo-columnFIBtablewithtwosetsofdistinctelementsineachofthecolumnsS1,S2andanencodingofthe rstcolumnσ1:=σ¯1.Fory∈S2,

σ1(x))wedenotebyφσ¯1(y)themaximalcodewordlength (¯

ofanelementx∈S1thatsharesarowwithyinA.

σ1(x))|x∈S1,(x,y)∈E}.φσ¯1(y)=max{ (¯

(12)

上一页第7页

你可能喜欢

热门文档

相关文档

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