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

compressing forwarding tables for datacenter scalability

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

CompressingForwardingTablesfor

DatacenterScalability

OriRottenstreich,MaratRadan,YuvalCassuto,IsaacKeslassy,CarmiArad,TalMizrahi,YoramRevah,andAvinatanHassidim

Abstract—Withtheriseofdatacentervirtualization,thenum-berofentriesintheforwardingtablesofdatacenterswitchesisexpectedtoscalefromseveralthousandstoseveralmillions.Unfortunately,suchforwardingtablesizeswouldnot ton-chipmemoryusingcurrentimplementations.

Inthispaper,weinvestigatethecompressibilityofforwardingtables.We rstintroduceanovelforwardingtablearchitecturewithseparateencodingineachcolumn.Itisdesignedtokeepsupportingfastrandomaccessesand xed-widthmemorywords.Then,weshowthatalthough ndingtheoptimalencodingisNP-hard,wecansuggestanencodingwhosememoryrequirementperrowentryisguaranteedtobewithinasmalladditiveconstantoftheoptimum.Next,weanalyzethecommoncaseoftwo-columnforwardingtables,andshowthatsuchtablescanbepresentedasbipartitegraphs.Wededucegraph-theoreticalboundsontheencodingsize.Wealsointroduceanalgorithmforoptimalconditionalencodingofthesecondcolumngivenanencodingofthe rstone.Inaddition,weexplainhowourarchitecturecanhandletableupdates.Last,weevaluateoursuggestedencodingtechniquesonsyntheticforwardingtablesaswellasonreal-lifetables.

IndexTerms—DatacenterVirtualization,Layer-2Datacenter,ForwardingInformationBase,Compression.

I.INTRODUCTION

A.Background

MACaddressperthread,andconsideringthejointincreaseofthenumbersof(a)threadspercore,(b)coresperprocessor(socket),(c)socketsperserver,and(d)serversperdatacenter,itisclearthattheproductofallthesenumbersisexpectedtodramaticallyincreaseinthecomingyears[1]–[3].Inadditiontothisexpectedstronggrowthinthenumberofentriesperforwardingtable,wecanalsoexpectamoderategrowthinthenumberofattributesperentry,suchasthequality-of-serviceandsecurityattributes,aswellasinthesizeoftheseattributes.Allinall,weneedtobeabletohandledramaticallylargerforwardingtables.

Unfortunately,forwardingtablesmustbeaccessedonaper-packetbasis.Therefore,theyareperformancesensitive.Becauseofthehighdatacenterrates,theyareoftenimple-mentedinhardwareusingon-chipmemory.Thismakesscalingforwardingtableschallenging,becauseon-chipmemoryistoosmalltoholdmillionsofforwarding-tableentriesinrawform[4],[5].

Thegoalofthispaperistostudythecompressibilityofforwardingtables,providingbothananalyticalframeworkandexperimentalinsighttowardtheeffectivecompressionofsuchtables.

B.CompressingForwardingTables

Forwardingtables,alsoreferredtoasForwardingInforma-tionBases(FIBs),consistofseveralentries,whichassociatealookupkeytoitscorrespondingforwardinginformation.Forinstance,thelookupkeycanbea(destinationMACaddress,VLAN)pair,andtheforwardinginformationcanincludetheswitchtargetport,thequality-of-serviceattributes,thesecurityattributes,andadditionalinformationusedforvariousmodi cationsthatneedtobeappliedtothepacket.Forwardingtablesaretypicallyarrangedastwo-dimensionaltables.Eachrowentryinaforwardingtablecorrespondstoadifferentlookupkey,andcontainsseveralcolumns,withthelookupkeyandforwardinginformation.Forwardingtablescanthenbeaccessedusingahashingmechanism.Uponeachincomingpacket,thepacketlookupkeyishashedintoone(orseveral)ofthehashtableentries.Ifthisentryindeedcontainsthelookupkey,thentheforwardingtablereturnstheassociatedforwardinginformation.

Forwardingtablesaretypicallyredundant,becausetheir elds(columns)canhaveahighlynon-uniformvaluedis-tribution,andbecausethevaluesindifferent eldscanbecorrelated.Therefore,weareinterestedinstudyingwhetherthesepropertiescanbeusedtocompressthem.However,we

T

HERAPIDgrowthofforwardingtablesinnetworkswitchesraisesseriousconcernsinthenetworkingindus-try.Layer2(L2)networksarenolongerconstrainedtosmalllocalareanetworks.Onthecontrary,theyarenowusedindatacenternetworks,whichwillsoonhaveaneedformillionsofhostsinasingleL2domain,whilecurrentL2domainsareonlyrestrictedtoseveralthousands[1].Asaresult,currentforwardingtablescannothandlesuchdatacenternetworks.Themaindriverofthisexpecteddramaticgrowthrateisthedeploymentofhostvirtualizationindatacenternet-works.Whereastraditionalserverswouldonlyuseoneortwoglobally-uniqueMACaddressesperserver,contemporaryserversusetensofMACaddresses,correspondingtotheirtensofvirtualmachines(thesegeneratedMACaddressesarenotnecessarilygloballyuniqueanymore).Assumingone

ManuscriptreceivedJanuary15,2013;revisedJuly1,2013.

O.Rottenstreich,M.Radan,Y.CassutoandI.KeslassyarewiththeTechnion,Israel(e-mails:{or@tx,radan@tx,ycassuto@ee,isaac@ee}.technion.ac.il).

C.Arad,T.MizrahiandY.RevaharewithMarvellIsrael(e-mails:{carmi,talmi,yoramr}@marvell.com).T.MizrahiisalsowiththeTechnion.

A.Hassidimiswiththedepartmentofcomputerscience,Bar-IlanUniver-sity,Israel(e-mail:avinatan@cs.biu.ac.il).

DigitalObjectIdenti er10.1109/JSAC.2014.140113.

c2014IEEE0733-8716/14/$31.00

第1页

你可能喜欢

热门文档

相关文档

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