资源描述:
《Approximate Caches for Packet Classification》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、ApproximateCachesforPacketClassificationFrancisChang,Wu-changFengKangLiSystemsSoftwareLaboratoryDepartmentofComputerScienceOGISchoolofScienceandEngineeringatOHSUUniversityofGeorgiaBeaverton,Oregon,USAAthens,Georgia,USA{francis,wuchang}@cse.ogi.edukangli@acm
2、.orgAbstract—Manynetworkdevicessuchasroutersandclassificationcachesrequirethestorageoffullpacketheaders.firewallsemploycachestotakeadvantageoftemporallocalityofUnfortunately,duetotheincreasingsizeofpacketheaderspacketheadersinordertospeeduppacketprocessingd
3、ecisions.(theeventualdeploymentofIPv6[19]),storingfullheaderTraditionally,cachedesignstradeofftimeandspacewiththeinformationcanbeprohibitivegiventhecostofthehigh-goalofbalancingtheoverallcostandperformanceofthedevice.speedmemorythatwouldbeusedimplementsucha
4、cache.Inthispaper,weexamineanotheraxisofthedesignspacethatToaddressthisproblem,thispaperexaminesathirdaxisforhasnotbeenpreviouslyconsidered:accuracy.Inparticular,wedesigningpacketclassificationcaches:accuracy.Inquantifythebenefitsofrelaxingtheaccuracyofthec
5、acheontheparticular,weseektoanswerthefollowingquestion:costandperformanceofpacketclassificationcaches.OurcacheWhatarethequantifiablebenefitsthatrelaxingthedesignisbasedonthepopularBloomfilterdatastructure.Thisaccuracyofacachehasonthesizeandperformanceofpack
6、etpaperprovidesamodelforoptimizingBloomfiltersforthisclassificationcaches?purpose,aswellasextensionstothedatastructuretosupportgracefulaging,boundedmisclassificationrates,andmultipleWhiletherearemanywaysofexploringthisaxis,thisbinarypredicates.Giventhis,wes
7、howthatsuchcachescanpaperexaminesoneapproachfordoingsothroughtheuseofaprovidenearlyanorderofmagnitudecostsavingsattheexpensemodifiedBloomFilter.Inthisapproach,classifiedpacketsofmisclassifyingonebillionthofpacketsforIPv6-basedcaches.satisfyingabinarypredica
8、teareinsertedintothefilterthatcachesthedecision.SubsequentpacketsthenquerythefilterKeywords—Bloomfilter;packetclassification;caches;toquicklytestmembershipbeforebeingprocessedfurther.probabilisticalgor