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

compressing forwarding tables for datacenter scalability

150IEEEJOURNALONSELECTEDAREASINCOMMUNICATIONS,VOL.32,NO.1,JANUARY2014

TABLEII

DEALINGWITHRULEUPDATES.ENCODINGISBASEDONTHEFIRSTHALFOFTHEENTRIESINEACHFILE.ADDITIONALENTRIESARECONSIDERED

ASNEWINSERTEDENTRIES.

numbernumberraw xed-improvedlonguncodedofofdatalengthwidthentriesentries eldsentrieswidthwidthUnitedStates32790311513530China1290329118132China2

2

428

29

5

5

3

TheresultsaresummarizedinTableII.Ingeneral,onlyasmallportionofthenewentriescouldnotbeencodedwithinthepredeterminedwidth.Forinstance,inthetablefromUnitedStatesanencodingwidthof13bitswasobtainedintheencodingofthe rst1395entries,improvingthewidthof15bitsrequiredfortheencodingofthe lewiththe xed-lengthencoding.Whiletryingtoinsertthelast1395entriesofthesecondhalfofthe leasnewentries,1342ofthem(96.2%)couldbeencodedsuccessfullywithin13bitsbasedonthepreviouslyselectedencodingscheme.Only53entriesobtainedwidthslargerthan13.Inaddition,noneofthesenewentriescontainednewelementssuchthattheirencodingwasnotde nedintheschemeforthe rstentries.Likewise,inChina1,weencountered13entrieswithover owamong452insertedentries(only2.88%).Onlytwoofthenewentriescontainedelementsthatdidnotappearinthe rsthalfofentries.

C.ExtrapolatedTables

Wewanttoextrapolatethebehaviorsoftheseschemesfromreal-lifelimiteddatasetstothelargerexpecteddatasetstobeencounteredinfuturedatacenternetworkarchitectures.Theapproachwetakehereinistoamplifytheavailabledatasetsbyscalingoutthenumberofcolumnsinthetable,soastomodelatablewithascaled-outnumberofattributes.

WeextendtheChina1tablebyduplicatingandappendingtheportcolumnseveraltimes.Ineachnewcolumn,wepermutetheappearancesoftheelementsuniformlyatrandom.Themotivationistomodeladditionalforwardingattributesthatwouldfollowadistributionthatissimilartoanexistingone.Rearrangingtherowlocationsoftheduplicateelementsaddsrandomnesstotheextended le.AsseeninFig.8,foreachadditionalcolumnthe xedencodingincreasesbyaconstant,asexpectedsincethenumberofuniqueelementsineachcolumndoesnotvary.TheHuffmanandconvexencodingsincreaseataslowerpace,therebyincreasingtheencodingeffectivenessasthenumberofcolumnsgrows.Ofcourse,sincethistableisextendedsynthetically,weurgecautioninover-interpretingtheresults.

VIII.CONCLUSION

Inthispaper,wesawhowdatacentervirtualizationiscausingadramaticriseinthenumberofentriesinforwardingtables,suchthatitbecomesimpossibletoimplementfor-wardingtablesincurrentmemorysizeswithoutanycompres-sionalgorithm.Wetheninvestigatedthecompressibilityofforwardingtables,byintroducinganovelforwardingtablearchitecturewithseparateencodingineachcolumn.

compressing forwarding tables for datacenter scalability

Our

Fig.8.Effectivenessoftheencodingalgorithmontheextendedtable(basedontheChina1table),asafunctionofthenumberofcolumns.

architecturesupportsfastrandomaccessesand xed-widthmemorywords.Wealsolaterexplainedhowourarchitecturecanhandletableupdates.

Later,wesuggestedanencodingwhoseper-entrymem-oryrequirementisguaranteedtobewithinasmalladditiveconstantoftheoptimum.Finally,weevaluatedthisnewschemeagainstthe xed-widthandHuffmanschemes,usingbothsyntheticandreal-lifeforwardingtablesfromdifferentswitches,switchvendors,andnetworkcountrylocations.Asfuturework,weplantocheckhowusingadditionalhardwaresuchasCAMandTCAMcanhelpinfurthercompressingtheforwardingtables.

IX.ACKNOWLEDGMENT

WewouldliketothankYishayMansourandHaimKaplanfortheirhelpfulparticipationandsuggestions.

ThisworkwaspartlysupportedbytheAndrewViterbigrad-uatefellowship,bytheGoogleEuropeanDoctoralfellowship,byaEuropeanCommissionMarieCurieCIGgrant,bytheIntelICRI-CICenter,bytheIsraelScienceFoundationgrantNo.1241/12,bytheGerman-IsraeliFoundationforScienti cResearchandDevelopment,bytheJapanTechnionSocietyandGreenberg(Ottawa)ResearchFunds,andbytheIsraelMinistryofScienceandTechnology.

REFERENCES

[1]I.Gashinsky,“Datacenterscalabilitypanel,”inNorthAmericanNetwork

OperatorsGroup,NANOG52,2011.

[2]R.N.Mysoreetal.,“Portland:ascalablefault-tolerantlayer2data

centernetworkfabric,”inSIGCOMM,2009.

[3]T.Nartenetal.,“ProblemstatementforARMD,”IETF,draft-ietf-armd-problem-statement,workinprogress,2012.

[4]G.Hankins,“Pushingthelimits,aperspectiveonrouterarchitecture

challenges,”inNorthAmericanNetworkOperatorsGroup,NANOG53,2011.

[5]D.Meyer,L.Zhang,andK.Fall,“ReportfromtheIABworkshopon

routingandaddressing,”IETF,RFC4984,2007.

[6]T.M.CoverandJ.A.Thomas,Elementsofinformationtheory(2.ed.).

Wiley,2006.

[7]T.Narten,“Onthescalabilityofinternetrouting,”IETF,draft-narten-radir-problem-statement,workinprogress,2010.

[8]P.Francis,X.Xu,H.Ballani,D.Jen,R.Raszuk,andL.Zhang,“FIB

suppressionwithvirtualaggregation,”IETF,draft-ietf-grow-va,workinprogress,2011.

[9]X.Zhao,Y.Liu,L.Wang,andB.Zhang,“Ontheaggregatabilityof

routerforwardingtables,”inINFOCOM,2010.

[10]R.Draves,C.King,V.Srinivasan,andB.Zill,“Constructingoptimal

IProutingtables,”inINFOCOM,1999.

[11]Q.Li,D.Wang,M.Xu,andJ.Yang,“Onthescalabilityofrouter

forwardingtables:Nexthop-selectableFIBaggregation,”inInfocomMini-Conference,2011.

上一页第13页

你可能喜欢

热门文档

相关文档

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