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

compressing forwarding tables for datacenter scalability

ROTTENSTREICHetal.:COMPRESSINGFORWARDINGTABLESFORDATACENTERSCALABILITY

compressing forwarding tables for datacenter scalability

139

TABLEI

ANEXAMPLEOFAFORWARDINGTABLEWITHd=3COLUMNSANDITSENCODEDREPRESENTATION.I(A)SHOWSTHEORIGINALTABLEWITHOUTENCODING.THEENTRYSELECTIONMECHANISMISNOTPRESENTED.I(B)ILLUSTRATESTHECORRESPONDINGENCODEDFORWARDINGTABLEWITH

AMAXIMALENCODEDENTRYWIDTHOFP=5BITS.(SPACESAREPRESENTEDJUSTFORSIMPLICITYANDDONOTEXISTINPRACTICE.)I(C)

DESCRIBESTHEd=3DICTIONARIESREPRESENTINGTHEPREFIX

ENCODINGSOFTHEdCOLUMNS.

(A)TheoriginalforwardingtableMACAddressVLANTargetPort00:1b:2b:c3:4d:90Vlan10Te12/100:00:aa:6c:b1:10Vlan10Gi11/800:00:aa:65:ce:e4Vlan10Te12/100:00:aa:65:ce:e4Vlan200Gi11/2400:13:72:a2:a2:0eVlan200Gi11/2400:21:9b:37:7e:14Vlan10Te12/100:13:72:a2:a2:0eVlan200Gi11/8

Fig.1.Anillustrationofanaccesstotheencodedforwardingtable.First,

thepacketlookupkeyishashedtoobtainanentryindexi∈[1,h].Then,asingleencodedentryof(atmost)Pbitsisretrieved.Finally,dpipelinedaccessestoddictionariesareperformedbasedonthedbinarycodewords(ofdifferentlengths)composingthisencodedentry.

(B)Encoding1100000010010001111101111110010110

(C)Theencodingdictionaries

D1(MACAddress)

00-00:00:aa:6c:b1:1001-00:00:aa:65:ce:e410-00:13:72:a2:a2:0e110-00:1b:2b:c3:4d:90111-00:21:9b:37:7e:14

D2(VLAN)0-Vlan101-Vlan200

D3(TargetPort)0-Te12/110-Gi11/811-Gi11/24

wouldliketokeeptwokeypropertiesthatarespeci ctoforwardingtables:

(i)Theabilitytoaccesseachrowentrydirectlyregardlessofitsrowindex,and

(ii)Theabilitytostoreeachrowentryina xed-widthmemoryword.

Suchcriteriapreventormakelessattractivetraditionalen-codingtechniques.Forinstance,iftheentriesarecompressedusingaLempel-ZivWelch(LZW)techniqueandsequentiallystoredinthememory,itisthendif culttocalculatethememoryaddressofaspeci centry,andtoaccessitdirectlybasedonitsentryindex.

C.OverviewoftheSuggestedSolution

AsillustratedinFigure1,wesuggestanovelcompressiontechniqueforforwardingtablesthatsupportsrandomaccesses.Weproposetoencodeeachoftheforwarding-tablecolumnsseparately,usingadedicatedvariable-lengthbinarypre xencoding,i.e.anencodinginwhichanycodewordisnotapre xofanyothercodeword.Weremindthatapre xofastringb1b2...bn,isastringoftheformb1b2...bmwherem≤n.Therefore,eachrowentryinad-columntableisrepresentedbytheconcatenationofdcodewordsrepresentingthecontentofeachofitsd elds.Accordingly,itswidthequalsthesumofthedcorrespondingcodewordlengths.Foreachrowentryweallocatea xedmemorysizeP.Inaddition,eachcolumnjisassociatedtoadictionaryDj,whichisstoredseparatelyinthememory.ThisdictionaryDjmapseachbinarycodewordintoitsrepresented eldvalueincolumnj.Figure1illustratesanaccesstotheencodedforwardingtable.Ateachpacketarrival,we rsthashthepacketlookupkeytoobtainanentryindexi∈[1,h].Then,weaccesstheencodedtabletoretrievethePbitsrepresentingtheencodingofitsithentry.Last,welookupeachoftheddictionariesinapipelinedmanner.Thisway,wesequentiallyobtainthecorrespondingvaluesofthed eldsintheithentryafterdpipelinedlookups.

Notethatthecombinationofthebounded-widthentrypropertyandthepre xpropertyofindividual eldsyieldsourtwodesiredpropertiesspeci edabove.

Example1.TableIpresentsanexampleofaforwardingtableandapossibleencodingofthattable.Thereareh=7entriesinthetable,eachwithd=3 elds:MACAddress,VLANandTargetPort.

First,TableI(A)presentstheoriginaltablewithoutencod-ing.

Next,TableI(B)illustratesapossibleencodingoftheforwardingtable(thepresentedspacesintheencodedtablearejustshowntodistinguishbetweenthedifferent elds,anddonotexistinpractice).Forinstance,thetwopossiblevaluesintheVLAN eldareencodedbyasimple xed-lengthsingle-bitencoding.Inaddition,variable-lengthencodingsareusedtoencodethethreedistinctvaluesintheTargetPort eld,aswellasthe vedistinctvaluesoftheMACAddress eld.Withthesed=3encodings,theobtainedmaximalwidthofanencodedentryisP=5bits.Thus,inordertosupporttherandom-accessrequirement,wekeepP=5bitsinthememoryforeachencodedentry,evenifitmayactuallybeshorter.Forinstance,thethirdentryonlyneeds4bits,andthereforewastes1bit.

Finally,TableI(C)illustratestheencodingsusedbythed=3dictionariesrepresentingthed=3columns.ThenumberofentriesineachdictionaryequalsthenumberofdistinctvaluesinthecorrespondingcolumninI(A).

Thisexampleillustrateshowpre xencodingenablesustosimplyconcatenatethecodewordswithoutaneedforanyadditionalseparating ags.

Inaddition,italsoshowshowthememorysizeisdirectlydeterminedbytheworst-caseentrywidth,i.e.themaximumnumberofconcatenatedbitsperentry.ThisisonereasonforexamplewhyencodingeachcolumnusingHuffmancoding[6]

上一页第2页

你可能喜欢

热门文档

相关文档

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