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

compressing forwarding tables for datacenter scalability

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

wouldnotnecessarilyaddressthisproblem:whileitisoptimalfortheaverageentrywidth,itmayyieldaworstcasethatendsupwastingasigni cantnumberofbits.Therefore,foragivenforwardingtablewithdcolumns,ourgoalistosuggestasetofdpre xencodingsthatminimizesthemaximalencodedentrywidth.Thismakesitparticularlyhard,becauseeachentrywidthinvolvesallcolumns,andthemaximalonealsoinvolvesallrowentries.Therefore,anystrongsolutionmayneedtojointlylookatalltheelements.

D.RelatedWork

Theforwardingtablescalingproblemhasbeenthoroughlyanalyzedanddiscussedinnetworkingindustryforumsandstandardsorganizations,bothintheL2andtheL3layers(e.g.[1],[3]–[5],[7],[8]).Theseanalysesraisetheconcernthatthesteepgrowthrateofforwardingtableshasoutrunthesteadytechnologygrowthrateofmemorydensity.

Variouscreativemethodshavebeenproposedtomitigatethisscalingproblem.First,FIBaggregation[9]isanapproachthatreducesthesizeofaforwardingtablebyaggregatingtableentrieswiththesamevaluesofthenexthop eld.Forinstance,twopre xrulesthatdifferonlyontheirlastbitcanbecombinedtoasinglepre xwithashorterpre x.Likewise,apre xmaybeeliminatedduetoredundancyachievedbyashorterpre xwiththesamenexthop.Asimilarapproachispresentedin[10]–[13].Forinstance,in[11]anoptimalrepresentationisfoundbasedondynamicprogrammingwhereineachrulethevalueofthenexthopcanbeselectedamongashortlistofpossiblevalues.However,thisapproachassumesthattheroutingtablehasatreestructure,i.e.theruleshavetheformofpre xesinanaddress eld(usuallyIPaddress)andcannotbeappliedinthecaseofmoregeneral elds,suchasanexactMACaddresswithacorrespondingattribute.Inaddition,therehavebeenstudiesinotherrelated elds.Clearly,ininformationtheory,therearemanyresultsoncom-pressionandonlowerboundsbasedonentropy[6].Likewise,databaseimplementationsalsoattempttoscalesystemsbyintroducingcompressiontechniques[14]–[16].Inparticular,in[14]adictionary-basedsolutionthatsupportsdeleteandupdateoperationsissuggested.A eldvalueisinsertedintothedictionaryandencodedbasedonitslengthanditsnumberofoccurrences.Likewise,ablockofdataiscompressedonlyifitscompressionratioisbeyondathreshold.However,thesestudiesdonotconsidertheforwardingtablerestrictionsthatwementionabove,andinparticulartheboundedentrylength.Recently,[17]studiedhowtomaximizetheprobabilityofencodingrandomentrieswithina xed-widthmemory.

Oursolutioncanbeconsideredasatypeoftopologi-caltransformation.MostoftherelatedapproachessuggestTCAM-basedsolutionsandmainlydiscussrangeencod-ing[18]–[20].OursolutioncanbeappliedtoamoregeneralclassoftablesandisnotnecessarilybasedonTCAM.

Finally,asmentioned,anorthogonalandcomplementaryconsiderationistheimplementationoftheforwardingtableusinghashing,inordertoeasily ndtherowthatcorrespondstoagivenkey[21].

E.Contributions

Thispaperinvestigatesanoveltechniquefortheef cientrepresentationofforwardingtablesindatacenterswitches,withasupportforfastrandomaccessand xed-widthmemorywords.

Westartbystudyinganof ineencodingschemeforagivenstaticFIBtable.Weprovethatitispossibletoformulatetheencodingproblemasanoptimizationproblem,andthattherelaxedoptimizationproblemisconvex.Asaresult,weproposeanovelalgorithmthatachieves,foranygivenforwardingtablewithdcolumns,theoptimalworst-caseentrywidthwithinaguaranteedconstantadditivefactorofd 1,independentlyoftheirvaluesandofthenumberofrows.Next,wealsoprovethatthegeneraloptimizationproblemisNP-hard,aslongasthereareatleastd=7columns.Wedosobypresentingareductionfromthe3 SATdecisionproblem.Therefore,thereislittlehopeforapracticaloptimalalgorithm.

Inaddition,wealsoconsiderthespecialcaseofforwardingtableswithd=2columns,whichmayonlyconsistofthekeyandtheaction.We rstsuggesttightupperandlowerboundsontheoptimalencodingwidthofatwo-columntableinthegeneralcase.Wealsoshowasuf cientconditionfora xed-lengthencodingtobeoptimal.Moreover,wepresentanoptimalconditionalencodingofasecondcolumnwhentheencodingofonecolumnisgiven.Later,wealsointroduceabipartitegraphthatcanmodeltheforwardingtable,andpresentadditionalgraph-theoreticboundsonitsoptimalencodingwidth.Theseimprovedboundsrelyonthecombinatorialpropertiesofthegraph,suchasthesizeofitsedgecover.

Finally,wealsodiscussthelimitsofourof inemodel,byanalyzinghowourcompressedforwardingtablesmaybeabletohandleupdates.Weshowthatanadditionalbitpercolumnandanadditionalsmallmemorymaybesuf cienttocopewithtemporaryloadsofentryadditions,modi cationsordeletions.Weconcludebyevaluatingthesuggestedencodingtech-niquesonreal-lifeforwardingtablesaswellasonsynthetictables.Wedemonstratehowourintroducedtechniquesfareagainstalternativealgorithmssuchas xed-lengthandHuff-mancoding.Inparticular,wegetclosertothecompressionlowerbound,albeitatthecostofanincreasedcomplexity.

II.MODELANDPROBLEMFORMULATION

A.Terminology

Westartwiththeformalde nitionofterminologyusedinthispaper.Forabinarycodeword(string)x,let (x)denotethelengthinbitsofx.

De nition1(FIBTable).AFIBtableA=((a11,...,a1d),...,(ah1,...,ah

andd))isatwo-dimensionalmatrixofhrows(entries)dcolumns( elds).

GivenaFIBtableA,wedenotebySj(forj∈setofelementvaluesinthejthcolumn,i.e.Sj= [1,d])the

h

alsodenotebynthenumberofdistinctelementsiin=1{aithej}.Wejjthcolumn,i.e.nj=|Sj|.Letsj,1,...,sj,njdenotetheelementsofSj.

上一页第3页

你可能喜欢

热门文档

相关文档

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