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

compressing forwarding tables for datacenter scalability

ROTTENSTREICHetal.:COMPRESSINGFORWARDINGTABLESFORDATACENTERSCALABILITY

compressing forwarding tables for datacenter scalability

149

(a)United

compressing forwarding tables for datacenter scalability

States

(b)China

compressing forwarding tables for datacenter scalability

1

(c)China2

Fig.7.Totalmemorysizeofencodedreal-lifetablesincludingthedictionarysize.Allforwardingtableswerecollectedinenterprisenetworks,intheUnitedStatesaswellasinChina.

Weperformanadditionalsimulationtoexaminehowthenumberofentriesin uencetheencodingwidth.Wecompareagainoursuggestedschemewiththe xed-lengthencodingintablesofhentriesforh∈{100,500,1000,2000,5000,10000}andd=4columns.Allentriesareselectedrandomlyamong2W=256(forW=8)possibleelementsineachcolumn,accordingtoZipfdistribu-tionparameterss=2,3.Here,sinceweconsideralsotableswithrelativelysmallnumberofentries,wedonotforceallelementstoappearatleastonceineachcolumn.Accordingly,the xed-lengthencodingyieldsanencodingwidthsmallerthand·W=32.Theresultsarebasedontheaverageof10simulations.

Fig.6depictstheresults.Asexpected,theencodingwidthofourschemeincreaseswhenthenumberofentriesgrows

sincetheadditionalentriesresultinmoreconstraintsonthewidth.Forallexaminednumberofentriestheimprovementofourschemeisnotnegligible.Forinstance,ifh=500ands=3theobtainedwidthis12.8incomparisonwith14.5forthe xed-lengthencoding(animprovementof11.7%).Likewise,ifh=2000thewidthis14.5insteadof17.0(14.9%improvement).Theimprovementisevenlargerforthecaseofh=10000entriesandequals20.0%.Further,weexpecttoobserveanimprovementfortableswithrelativelylargenumberofentriesaslongasthedistributionoftheirelementsislessclosetotheuniformdistribution.Ofcourse,within nitenumberofentries,allpossibleentriesappearandwecannotimprovethe xed-lengthencoding.B.Real-LifeFIBtables

Wealsoconductexperimentsonthreetypicalreal-lifeenterprise-networktables.Thetablesarecollectedfromthreedifferentswitchesofthreedifferentswitchvendors,eachswitchusingadifferentnumberofcolumns.Alltableswerecollectedinenterprisenetworks,the rstintheUnitedStateswith2790entriesandtheotherinChinawith903and428entries.

Wewould rstliketoevaluatethevariousencodingschemes.Foreachtable,wepresentthesizeoftheoriginalrawtablewithoutcompression.Wecompareittothetotalsizeofthecompressedtable,includingthedictionaryforthreecompressionalgorithms:the xed-lengthencoding,theHuffmanencodingandoursuggestedencoding.TheresultsarepresentedinFig.7.

Forinstance,inthesecondreal-lifetable(China1),pre-sentedinFig.7(b),weconsiderthe903entriesoftwocolumnsrepresentingtheVLANandtheTarget-Port elds.Withoutencoding,eachentryisallocated29bitsperentryandthustherawdatawithoutencodingrequires903·29=26187bits.Usingthethreeencodings,thesizeofthedictionariesisalmost xedandequalsapproximately2900bits.Anentrywidthof11and14bitsisachievedinthe xed-lengthencodingandintheHuffmanencoding,respectively,whileintheproposedencodingweachieveanentrywidthofonly8bits.Thisleadstoanimprovementof20.7%,34.9%,and61.3%inthetotalmemorysize(includingthedictionary)comparedtothe xed-length,HuffmanandRawsolutions,respectively.

Wewouldalsoliketoexaminetheef ciencyoftheen-codingschemewhiledealingwithforwardingtableupdates.Toillustrateupdatesweperformthefollowingexperiment.Foreachofthethreereal-lifetables,weconsiderthe rsthalfofentries(e.g.1395outof2790inthetablefromUnitedStates).Wethen ndforeachofthem,oursuggestedencodingscheme.Next,weconsidertheentriesinthesecondhalfoftheoriginaltableasnewinsertedentries.Weexaminetheabilitytoencodethenewentrieswithinthedeterminedencodingwidth.Anotherobstacleisthatthesenewentriesmightincludenewelementsthatarenotencodedintheencodingschemefoundforthe rsthalfofentries.Ourhighinterestininsertionsofnewelementsisexplainedbythefactthat,asmentionedinSectionVI,changesinexistingentriescanbealsosupportedbyinsertionsofnewentries.

上一页第12页

你可能喜欢

热门文档

相关文档

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