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

compressing forwarding tables for datacenter scalability

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

compressing forwarding tables for datacenter scalability

2014

Fig.4.EffectivenessoftheencodingalgorithmonsyntheticFIBtableswithdare=selected2columnsaccordingandWto=the8,ZipfasadistributionfunctionofthewithZipftheparameter.givenparameter.ElementsByTheorem3,theoptimalencodingwidthisatleastW+2=10andatmost2W=16.Sinced=2,oursuggestedconvexschemetakesatmostd xed-length 1=1encodingbitmorehasthanathe xedtheoreticalwidthof2lowerW=bound.16bits,Inwhilecomparison,theHuffmantheencodingsometimesachievesagreater

compressing forwarding tables for datacenter scalability

width.

(a)Effectivenessoftheencodingalgorithmasafunctionofthenumberofcolumnswith2W=32distinctelementsper

compressing forwarding tables for datacenter scalability

column.

(b)Effectivenessoftheencodingalgorithmasafunctionofthenumberofdistinctelementspercolumnwithd=10columns.

Fig.5.Analysisoftheencodingalgorithmasafunctionoftableparameters.

cankeepanadditionalcopyofthetablethatwillbeaccessedinsuchcases.

VII.EXPERIMENTALRESULTS

Wenowturntoconductingexperimentstoexaminethedis-tributionoftheoptimalencodingwidthandtheperformanceofoursuggestedencodingalgorithmfromSectionIII-B.Intheexperiments,werelyonbothsyntheticandreal-lifeFIBtables.

A.EffectivenessonSyntheticFIBtables

We rstevaluateoursuggestedschemeonsynthetictwo-columnFIBtables.Inour rstexperiments,eachtablehas1000entrieswith2W=256(forW=8)distinctelements

compressing forwarding tables for datacenter scalability

in

Fig.6.EffectivenessofthenumberofentriesontheencodingwidthinsyntheticFIBtableswithd=4columnsandatmost2WWs==2,8=256(for3)distinctareconsidered.

elementsineachcolumn.TwovaluesoftheZipfparametereachofthed=2columns.Togeneratethetable,we rstmakesurethateachelementappearsatleastonceineachcolumnbyaddinganentrycontainingitwithanadditionalrandomelementintheothercolumn.ThisadditionalrandomelementisselectedaccordingtoaZipfdistributionofparameters.Then,weaddadditionalentrieswithd=2randomelementsselectedaccordingtothesamedistribution.Intuitively,aZipfdistributionwithalowerparametersisclosertotheuniformdistribution.

First,inFig.4,wecompareoursuggestedscheme(fromSectionIII-B),denoted“convex”,withthe xed-lengthandHuffmanencodingschemes.Theresultsarebasedontheaverageof10simulations.Wepresentthelowerboundgivenbythefractionalsolutionoftherelaxedoptimizationproblem(SectionIII-B).Wealsoshowoursuggestedscheme,whichtakestheceilingofthefractionalsolutionoftherelaxedproblem,unlessitexceeds2W,inwhichcaseitsimplyuses xed-lengthencoding.AssuggestedbyTheorem1,ourschemeisalwayswithind 1=1bitofthefractional-optimumlowerbound.Forinstance,foraZipfparameters=4,thewidthsfortheHuffman, xed-length,andoursuggestedencodingsarerespectively17.6,2W=16,and12.1,whilethelowerboundis11.2.Moregenerally,thelowertheZipfparameter,thecloserthelowerboundisto2W.Next,inFig.5,weplottheencodingef ciencyasafunctionofthenumberofcolumns(a)andofthenumberofelementsappearingineachcolumn(b).Inbothplotswetakeh=1000entriesandaZipfparameters=2.InFig.5(a)thenumberofelementsis32,i.e.W=5,andinFig.5(b)thenumberofcolumnsisd=10.Wecanseethatin(a),Huffmanbecomesbetterfortheworst-caseentrywidth.Intuitively,itisbecausetheratioofthestandarddeviationofthesumoftheencodings

ofdcolumnstotheexpectedsumdecreaseswithdas√1.Wewanttostressthatthepresentedencodingschemed

suggestsatradeoffbetweenmemoryrequirementsandrunningtime.Whileourschemeperformsbetterandobtainsanim-provedencodingwidth,itisalsomuchslowertorunthanthesimplerschemes.Asmentionedintheimplementationsection,itisdesignedforof ineorbackgrounduse.Forinstance,inFig.5(a),anunoptimizedimplementationofourschemeonabasicInteli5corerespectivelytook0.82secondsand23.1secondsforthetwo-columnandten-columntables,whiletheHuffmannschemeranintherespectively-negligibletimesof7and11milliseconds.

上一页第11页

你可能喜欢

热门文档

相关文档

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