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

compressing forwarding tables for datacenter scalability

ROTTENSTREICHetal.:COMPRESSINGFORWARDINGTABLESFORDATACENTERSCALABILITY143

Property2.LetAbeaFIBtableofdcolumnssuchthatthesetofdistinctelementsinthejthcolumnisS≤2WThen,

jwith|Sj|=njj.OPT(A)≤

dWj.

(9)

j=1

D.NP-HARDNESS

Weconcludethesectionbyconsideringthecomplexityof ndinganoptimalencodingschemeofagivenFIBtable.First,foratablewithasinglecolumn(d=1)anoptimalsolutionisgivenbythe xed-lengthencoding.Ifthereareninthe xed-lengthencodingallcodewords1=|S1|distinctelements,havelengthof log2n1 bits.Clearly,thisencodingisoptimalsinceKraft’sinequalitycannotbesatis edifallelementsareencodedinatmost( lognowshowthatthe2nabove1 -1)bits.

WeencodingproblemisNP-hardfortableswithatleastsevencolumns.

Theorem2.GivenaFIBtableAwithd≥7columns, ndinganoptimalencodingschemeofAisNP-hard.

ProofOutline.Forspacereasons,weprovideaproofoutline,andpresentthefullproofin[23].Weshowareductionfromthe3 SATdecisionproblemto ndinganoptimalencodingofatablewith7columns.

LetY=Y1∧Y2∧...∧YmbeaCNFformula.LetnbethenumberofvariablesinY.Fornisoftheformofn=2k

1

simplicity,weassumethat

forapositiveintegerk.Weshowthattheformula3

Yissatis ableiffacarefullyconstructedtableT(Y)withsevencolumnshasencodingwidthofatmost3k+6bits.T(Y)hastwokindsofentries.Entriesthatarenotin uencedbyY,andmadditionalentriesthatrepresentthemclausesofY.Aclauseissatis edifthewidthofthecorrespondingencodedentryisatmost3k+6bits.Usingthistable,wepresentthereductionfromanyinstanceof3 SAT,beforeconcluding.

Determiningthehardnessoftheprobleminthecaseofd∈[2,6]isleftasanopenquestion.WeconjecturethattheproblemisNP-hardford≥2.

Conjecture1.Foralld≥2, ndinganoptimalencodingschemeoftableswithdcolumnsisNP-hard.E.RetrievingtheForwardingInformation

AsmentionedinSectionI,intheproposedsolutiontherepresentationofanyencodedentryofdcolumns,issimplytheconcatenationofthedcorrespondingcodewordswithoutanyadditionalseparating ags.Wewouldliketoshow rstthattherepresentationsoftwodistinctoriginalentriesyieldtwodifferentconcatenations.Wewouldalsoliketosuggestanef cientwaytodetecttheboundariesofthedifferentcodewordscomposingsuchaconcatenation.

Property3.Letσ1,...,σdbedpre xencodingsofdsetsS1,...,Sd.Letx=(x j∈[11,...,x,d])xd),y=(y1,...,yd)betwoentriessatisfying(j,yj∈Sj.Letσ(x)=σ1(x1)·σ2(x2)...σd(xd)andσ(y)=σ1(y1)·σ2(y2)...σtwostringobtainedbyconcatenatingthedcodewordsd(yd)betheinthe

encodingsofx,y.Ifσ(x)=σ(y)thennecessarilyx=y,i.e.

( j∈[1,d])xi=yi.Inparticularthereisasingleelementz1∈S1whoseencodingσ1(z1)isapre xofσ(x)=σ(y).Proof.Theproofisbyinductionond.First,ford=1ifσ(x)=σ(y)wehaveσ1(x1)=σ(x)=σ(y)=σ1(y1).SinceσFor1isanencoding,wehavethatnecessarilyx1=y1.d≥2,assumethatσ(x)=σ(y),i.e.σ1(x1)·σ2(xbetween2)...σthed(xd)=σtwofollowing1(y1)·σcases.

2(y2)...σd(yd)anddistinguish(i)Ifx1=y1thennecessarilyσ1(x1)=σ1(y1).WecanthendeducethatσBytheinductionhypothesis2(x2)...σwehaved(xd)=σinthis2(ycase2)...σalsod(ythatd).(x2,...,xd)=(y2,...,yd)andsincexconcludethat(x1=y1wecan1,...,xd)=(y1,...,y(xd).

(ii)Ifx1=y1thennecessarilyσ11)=σ1(y1).Fromtheequalityσmust1(xhave1)·σthat2(x2)...σ (σd(x))d)=σ= (σ1(y1)·σ2(y2)...σd(yd)weσ1(x11(y1))andthateither1(x1)isapre xofσ1(y1)(if (σ1(x1))< (σ)isapre xofσσ1(y1)))orσ1(y1acontradiction1(x1)(if (since1(xσ1))> (σpre x1(yencoding.1))).Bothcasesleadto1isaFinally,sincecase(ii)leadstoacontradiction,theonlyelementz1∈S1whoseencodingσ1(z1)isapre xofσ(x)=σ(y)mustbez1=x1=y1.

Followingthelastpartoftheproperty,wecannowsuggesthowtodetecttheboundariesofthedifferentcodewordscomposinganencodedentry.Todoso,wekeepforeachofthedencodings,adictionarywithasortedlistofthepossiblecodewords(andtheirmatchingelements).Then,weperforminapipelinedmannerdaccessestothedictionaries.Ineachaccess,weperformabinarysearchto ndthesinglecodewordinthecurrentencodingwhichisapre xoftheconcatenatedstringrepresentingtheencodedentry.Bythelastproperty,thereisexactlyonesuchcodeword.Next,wecontinuetothenextdictionaryafteromittingthepre xoftheconcatenatedstring.Anyadditionalmemorybesidesthebasicrepresentationofthedictionariesisnotrequired.

IV.TWO-COLUMNFIBTABLES

Indatacenters,apopularclassofFIBtablesaresimpleL2MACtablesthatcontaintwocolumns.The rstdescribestheTargetPort,whilethesecondcanbeviewedasanaggrega-tionofcolumnsrepresentingacollectionofotherattributes.Indeed,weseeinreal-lifetabletracesthattheseadditionalattributesarehardlyeverused.Thustheiraggregationhasarelativelysmallsetofpossiblevalues.

Therefore,fromnowon,weconsiderthespecialcaseoftwo-columnFIBtables,i.e.FIBtablesthatsatisfyd=2.Wewouldliketofundamentallystudythiscasetoobtainsomeintuitionontheproblem.Weshowthatinthiscase,inorderto nditsoptimalencodingscheme,aFIBtableAcanbesimplyrepresentedasabipartitegraph.Wealsosuggestananalysisoftheoptimalencodingwidthofsuchtwo-columnFIBtables.

Forthesakeofsimplicity,weassume,unlessmentionedotherwise,thatthenumberofdistinctelementsineachofthed=2columnsofAisthesame,andthatitisapoweroftwo,i.e.|S1|=|S2|=n=2W.

上一页第6页

你可能喜欢

热门文档

相关文档

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