ASORTEDPARTITIONINGAPPROACHTOFASTANDSCALABLEDYNAMICPACKET CLASSIFICATION BySorrachaiYingchareonthawornchai ATHESIS Submittedto MichiganStateUniversity inpartialfulfillmentoftherequirements forthedegreeof ComputerScience–MasterofScience 2019ABSTRACT ASORTEDPARTITIONINGAPPROACHTOFASTANDSCALABLEDYNAMICPACKET CLASSIFICATION BySorrachaiYingchareonthawornchai TheadventofSoftware-DefinedNetworking(SDN)leadstotwokeychallengesforpacketclassifi- cationonthedramaticallyincreaseddynamismanddimensionality.Althoughpacketclassification isawell-studiedproblem,noexistingsolutionsatisfiesthesenewrequirementswithoutsacrificing classificationspeed.Decisiontreemethods,suchasHyperCuts,andSmartSplitcan achievehigh-speedpacketclassification,butsupportneitherfastupdatesnorhighdimensionality. TheTupleSpaceSearch(TSS)algorithmusedinOpenvSwitchachievesfastupdatesandhigh dimensionalitybutnothigh-speedpacketclassification.Weproposeahybridapproach,Parti- tionSort,thatcombinesthebenefitsofbothTSSanddecisiontreesachievinghigh-speedpacket classification,fastupdatesandhighdimensionality.AkeytoPartitionSortisanovelnotionof rulesetsortabilitythatprovidestwokeybenefits.First,itresultsinfarfewerpartitionsthanTSS. Second,itallowstheuseofMulti-dimensionalIntervalTreestoachievelogarithmicclassification andupdatetimeforeachsortablerulesetpartition.Ourextensiveexperimentalresultsshowthat PartitionSortisanorderofmagnitudefasterthanTSSinclassifyingpacketswhileachievingcom- parableupdatetime.PartitionSortisafewordersofmagnitudefasterinconstructiontimethan SmartSplit,astate-of-the-artdecisiontreeclassifier,whileachievingacompetitiveclassification time.Finally,PartitionSortisscalabletoanarbitrarynumberoffieldsandrequiresonlylinear space.ACKNOWLEDGEMENTS IwouldliketoexpressmygreatappreciationtoDr.EricTorng,myresearchadvisor,forhispatient guidance,insightfulcritiquesofmyresearch.Inparticular,Iamgratefulforhisflexibiltyinthat IcancollaboratewithresearchersbothinsideandoutsideMichiganStateUniversityfordiverse projects.IwouldliketothankDr.AlexLiuforhissupportandguidancethroughthisproject.I appreciateDr.JamesDalyforhistimecollaboratingwithmeonexperimentalanalysis.Iwould liketothankJacobMarcus,aprofessorialassistant,formovingprojectstowardsopen-source community. Finally,IamgratefulforfinancialsupportfromthedepartmentofComputerScienceandEngi- neeringatMSU.ThisworkispartiallysupportedbytheNationalScienceFoundationunderGrant NumbersCNS-1318563,CNS-1524698,andCNS-1421407,andtheNationalNaturalScience FoundationofChinaunderGrantNumbers61472184and61321491,andtheJiangsuHigh-level InnovationandEntrepreneurship(Shuangchuang)Program. iiiTABLEOFCONTENTS LISTOFTABLES .......................................viiLISTOFFIGURES .......................................viiiKEYTOABBREVIATIONS ..................................xiCHAPTER1INTRODUCTION ...............................11.1BackgroundandMotivation ..............................1 1.2ProposedApproach:anOverview ..........................4 1.2.1SortableRulesetPartitioning .........................5 1.2.2Rank-IntervalTree(RIT) ...........................6 1.3HighlightsofResults .................................7 1.4RecentDevelopment .................................9 1.5FutureWork ......................................10 1.5.1BatchedProcessing ..............................10 1.5.2IntegrationwithOpenFlowswitches .....................10 CHAPTER2RELATEDWORK ...............................122.1OrthogonalPointEnclosureQuery ..........................12 2.2SoftwareBasedPacketClassification .........................12 2.3HardwareBasedPacketClassification ........................13 2.4BatchProcessing ...................................14 CHAPTER3PARTITIONSORT ...............................163.1Introduction ......................................16 3.1.1MotivationandProblemStatement ......................16 3.1.2LimitationsofPriorArt ............................18 3.1.3ProposedApproach ..............................18 3.1.4TechnicalChallengesandProposedSolution .................19 3.1.5SummaryofExperimentalResults ......................20 3.2RelatedWork .....................................20 3.3RulesetSortability ...................................22 3.3.1FieldOrderComparisonFunction ......................23 3.3.2UsefulnessforPacketClassification .....................24 3.4Multi-dimensionalIntervalTree(MITree) ......................25 3.5SortableRulesetPartitioning .........................27 3.6PartitionSort:PuttingitallTogether .........................30 3.6.1RuleUpdate(OnlineSortableRulesetPartitioning) .............30 3.6.2PacketClassification .............................31 3.7AnalysisofPartitionSort ...............................32 3.7.1GeneralCase .................................32 3.7.2NumberofTreesandGeometricProgression ................33 iv3.7.3SuccessfulSearchesandPriorityOptimization ................35 3.8RuleSplitting .....................................36 3.8.1Splitting ................................37 3.8.2DeterminingCore-Compatibility .......................38 3.8.3SplittingaRule ................................38 3.9ExperimentalResults .................................39 3.9.1ExperimentalMethods ............................39 3.9.1.1Rulesets ...............................39 3.9.1.2TupleSpaceSearch .........................40 3.9.1.3SmartSplit .............................40 3.9.1.4PartitionSort ............................40 3.9.1.5Caching ...............................40 3.9.1.6EvaluationMetrics .........................41 3.9.1.7MachineEnvironmentandCorrectnessTest ............42 3.9.2PartitionSortversusTSSwithoutcaching ..................42 3.9.2.1ClassificationTime .........................42 3.9.2.2UpdateTime ............................45 3.9.2.3ConstructionTime .........................45 3.9.2.4MemoryUsage ...........................45 3.9.3PartitionSortversusTSSwithCaching ....................47 3.9.4ComparisonwithSmartSplit .........................47 3.9.4.1ClassificationTime .........................48 3.9.4.2ConstructionTime .........................48 3.9.4.3MemoryUsage ...........................48 3.9.5ComparisonofPartitionAlgorithms .....................49 3.9.6ComparisonofSplitFactors .........................50 3.9.6.1ClassificationTime .........................51 3.9.6.2DrawbacksofSplitting .......................51 3.10Conclusions ......................................51 CHAPTER4RANK-INTERVALTREE ...........................534.1BackgroundandIntroduction .............................53 4.1.1NaiveMulti-dimensionalBinarySearchTree ................53 4.2Rank-IntervalTreeandStaticConstruction ......................54 4.2.1Rank-IntervalTreeDefinition .........................54 4.2.2RITProperties ................................57 4.2.3RITConstruction ...............................58 4.3DynamicRITs .....................................60 4.3.1Insertionin O(d+logn)time........................61 4.3.2Deletionin O(d+logn)time.........................67 CHAPTER5CONCLUSIONANDFUTUREWORK ...................755.1BatchedProcessing. ..................................75 5.2IntegrationwithOpenFlowswitches .........................80 vBIBLIOGRAPHY........................................83viLISTOFTABLES Table3.1:GrInd(G),online(O)andTSS(T)averagenumberofpartitions(tuples)and percentageofrulesinfivepartitionswithhighestpriorityrules ..........32 Table3.2:BoundsforPartitionSort(PS)Operations .....................32 viiLISTOFFIGURES Figure1.1:Sortablerulesetwith xy.............................5 Figure1.2:Examplesofsortablerulesetpartitioningwithfieldorder XY,YX,andXY....6 Figure1.3:ExampleillustratingneedforRIT.Inputinstanceconsistsof n/2+1unique intervalswheresmallestintervalinsortedorderhascardinality n/2.Thecor- respondingstandardbalancedbinarysearchtreehashighcardinalityinterval atdepthlog n/2+1whereasRIThashighcardinalityintervalatdepth1. NotetheactualRITreewouldhavespanningnodes(definedinSection4.2.1); weomitheretohighlightintuition. ........................7 Figure1.4:PartitionSortandPTSSclassificationtimesandupdatetimes. ..........9 Figure3.1:PartitionSortisuniquelycompetitivewithpriorartonbothclassificationtime andupdatetime.ItsclassificationtimeisalmostasfastasSmartSplitandits updatetimeissimilartoTupleSpaceSearch. ..................17 Figure3.2:Exampleoforderedrulesetwith xy.......................23 Figure3.3:Asortablerulesetwith7rulesand3fields,fieldorder f=XYZ ,andthe correspondingsimplebinarysearchtreewhereeachnodecontains dfields....26 Figure3.4:Wedepicttheuncompressed(left)andcompressed(right)MITreethatcor- respondtothesortablerulesetfromFigure3.3.Regularleftandrightchild pointersareblackanddonotcrossfieldboundaries.Nextfieldpointersare redandcrossfieldboundaries.InthecompressedMITree,nodeswithweight 1arelabeledbytheonematchingrule. ......................27 Figure3.5:ExampleexecutionofGrInd. ...........................28 Figure3.6:Averagenumberofremainingrules( ri)plottedinlogscalewithbase2and 1.38.Theaverageisacrossfrompartitionat iindexincludingthosewithzeros.34 Figure3.7:Plotof (Ti)forourACL,FW,andIPC64krulesets.Theworst-caseisthe maxmimumnumberofpartitionsoverallrulesetsofsize64k.Theaverage excludesmissingvalues. .............................36 Figure3.8:SplittingtherulesfromFigure3.2inYXorder. .................37 Figure3.9:ClassificationTimebyRulesetTypeandSize ...................43 viiiFigure3.10:Partitions/TuplesQueried.ACDFdistributionofnumberofpartitionsre- quiredtoclassifypacketswithpriorityoptimization(cf.Section3.6.2). .....43 Figure3.11:ClassificationTimeon64KRules .........................43 Figure3.12:UpdateTimevsTupleSpaceSearch ........................44 Figure3.13:ClassificationTimewithCachingbyRulesetSize ................46 Figure3.14:Cache-HitRatiobyRulesetSize .........................46 Figure3.15:ClassificationTimevsSmartSplit .........................47 Figure3.16:ConstructionTimeinlogarithmicscale. ......................48 Figure3.17:NumberofPartitionsforandOnlinePartitionSort ............49 Figure3.18:ClassificationTimeforandOnlinePartitionSort .............49 Figure3.19:ClassificationTimeforSplittingExperiments ..................50 Figure3.20:NumberofPartitionsforSplittingExperiments ..................50 Figure4.1:AnexampleofRITconstruction. .........................58 Figure4.2:Illustrationofleft/rightsiblings. ..........................61 Figure4.3:MergeOperation. .................................63 Figure4.4:Fixingcase2.1:Replace parent (v)withv....................64 Figure4.5:Case(2.2):If sphasarightsiblingandaspanningnodeparent. .........65 Figure4.6:Fixingcase(2.2b).Notethat q1.........................66 Figure4.7:RankRotationoperation. .............................68 Figure4.8:SplitMergeoperation. ..............................70 Figure4.9:Case(2.2):If sphasarightsibling. ........................71 Figure4.10:AlternaterepresentationofFigure4.9(b). ....................72 Figure4.11:Merge-zipoperatio n................................73 ixFigure5.1:Anexampleof1Dpacket-rulemerge .......................75 Figure5.2:Example2-DPartitionProjectionAlgorithm ...................77 xKEYTOABBREVIATIONS ACL AccessControlList FWFirewall GPUGraphicsProcessingUnit IPCInternetProtocolChains OPEQOrthogonalPointEnclosureQuery RITRank-IntervalTree SDNSoftware-DefinedNetworking TSSTupleSpaceSearch TCAM TernaryContentAddressableMemory VPPVectorPacketProcessor xiCHAPTER1 INTRODUCTION 1.1BackgroundandMotivation Packetclassificationisafundamentalbuildingblockfornetworkarchitecture.Apacketclassifier providesanabilitytodistinguishpacketsintoflowsforfurtheraction;suchanabilityisone ofthecoremechanismsofnetworkingservicesandapplicationssuchasnetworksecuritypolicy, networkmonitoring,routingprotocols,qualityofservicemeasurement,andsoon.Asaresult,if thepacketclassifierisnotfastenough,then(millionsof)incomingpacketsmustbeand delayed.Extendedpacketingmaydisruptandslowdowntheentirenetworkingsystem. Earlypacketclassificationresearchfocusedonstaticsettingwherepreprocessingispermitted andupdatesarerarelyrequired[1,2].Inthissetting,weareonlyconcernedwithpacketclassification speed.Inthepreprocessingstage,weconstructadatastructurethatrepresentsasetofrules {rj}whereeachruleofafixeddimension dcanberepresentedasacatesianproductofintervals [ai,bi]dfor id,0aibiandai,biZ0.Acommonsettingisthetaskofclassifiyingastandard IP5-tuple.Apacketclassifierextractsfromthepacketheaders5fields:sourceIP,destinationIP, sourceport,destinationport,andprotocol.(Wecanthinkofthevaluesof5fieldsasa5-tupleof non-negativeintegers q=(q1,q2,..., qdZd0ind=5dimensionalspaceasa querypoint .)Givenaquerypoint q,thepacketclassifierfindsamatchingrule rjsuchthat qiai,bi],for alli1,2,..., d}.Ifthereismorethanonematchingrule,thenwereturnthehighestpriority matchingrule. Manytechniqueshavebeenintroducedtoimprovepacketclassificationinstaticsetting.Given nrules,wecantriviallyscanrulesinsequentialorderofprioritytoclassifyapacketin O(dn)timeusingO(n)space.Earlyresearchfocusedongettingto O(logn)classificationtime,assumingno memoryrestriction[3–5].Thisnaturallymotivatesadecisiontree-basedapproachwhererulesare subdividedrecursivelybasedonsomeheuristics.Theadvantageisthatthetreeheightisusually 1muchshorterthan (n).However,thisapproachusuallynecesssitatesrulereplications,requiring non-trivialamountofextraspace O(nd)intheworstcase.Subsequentworkfocusedonminimizing memoryconsumptionusingvarioustechniques[6,7].Theseheuristicsareexperimentallyshown todrasticallyreducememoryconsumptionwithonlymoderateslowdowninclassificationtime. Morerecently,SAX-PAC[8]hasshownapartitioningalgorithmthatcanpartitionrulesintoa smallnumberofsetsofnon-intersectingrules.Thenon-intersectingrulesareasimplerinstanceof packetclassification.Thisreductionisgeneric,andmoreimportantly,doesnotincurextraspace. Software-DefinedNetworking(SDN)hasshiftedpacketclassificationresearchbyintroducing newtwouniquechallengestopacketclassification:dynamicityanddimensionality.SDNdefinesa newabstractiontoseparatethecontrolplaneandthedatalayerofthenetworkingstack.Abstraction meanstheuseofcommoninterfacesforheterogeneousnetworkdevicesofvendorsand architecturestocommunicatewiththecentralcontrollerandtoimplementthefunctionsdemanded bythecontroller.OneinstanceofSDNistheOpenFlowstandard[9,10].TheadventofSDNleads tonewchallenges,dynamicityanddimensionality,whichmakeruleupdatehavesimilarimportance topacketclassification.Specifically,beforeSDN,classificationruleswererelativelystaticwith infrequentupdates.WithSDN,rulesarefrequentlyinserted,modifiedordeletedbythecontroller tomeetanapplications’requirementssuchasestablishinganewnetworkpaththatsatisfiesagiven qualityofservice.Thus,updatetimeinadditiontoclassificationtimemustbeminimized.For example,OpenvSwitch[11]usesPTSSforitspacketclassifiereventhoughPTSShasrelatively slowclassificationduetoPTSSsupportingfastupdate.TheimportanceoffastupdateinOpenFlow ishighlightedbyK etal. ’swork[12];theyshowthatindeployedOpenFlowswitchesthat useternarycontentaddressablememory(TCAM),thedataplanemightlagbehindthecontrol planebyasmuchas400msandruleupdatesmayhappenoutoforder.Thisisanobvioussecurity risk.Furthermore,currentsoftwareOpenvSwitchimplementationscanhandleupto 42,000rule updates/s[12],whichrequirestheclassifier’sworstupdatetimetobelessthan10 µs,evenforlarge rulesets.Thisrulesoutanyclassifierthathasevenmillisecondupdatetime. Fornon-trivialdimensions d=(logn),noexistingsolutionscanhandledynamicityand 2fastclassificationatthesametime.Fromthetheorycommunity, prioralgorithmsonpacket classification(alsoknownasrectangle-stabbingquery)anditspriorityvariantareessentially linearinclassificationtime .Kaplanetal. [13]presentedadynamicdatastructureforpacketclassificationthatusespoly- logarithmicqueryandupdatetimewhileusing O(npolylog )space.Afshani etal. [14]showed thatrectangle-stabbingquerycannotbedimensionallyscalablewithlinearspace;itrequires (logn(logn/logd)d−2+k)timetoprocessaquery.Fromthenetworkcommunity, priorpacket classificationalgorithmscannotsatisfyboththedynamicityandscalabilityrequirements .Decision treemethods,suchasHiCuts[3]andHyperCuts[4]arenotscalablewiththenumberoffields danddonotsupportfastupdate.Inadecisiontree,eachbranchorsplitpointpartitionsthepacketspace withthegoaltofindasplitwheretherulesaredividedevenly.However,perfectsplitsarehardto findandanyrulethatcrossesthesplitsmustbecopiedintoallpartitionsitintersects.Thisleadsto updatesastheinsertionordeletionofasinglerule,ataminimum,requiresaddingor deletingallcopiesoftherules.Furthermore,thismayleadtosplitscompromis- ingclassificationspeed.Rulereplicationalsoleadtonon-linearmemoryusage.TupleSpaceSearch (TSS)[15],anoldpacketclassificationalgorithm,hasbeenadoptedinOpenvSwitch[11]because itsupportsfastupdatesanditsperformanceisrelativelyinsensitivetothenumberofdimensions d.Foreachrule,TSScreatesa d-tuplewhereeachvaluerepresentsthenumberofbitsusedinthe correspondingfield.TSSworksbycreatingahashtableforeach d-tuple.Unfortunately,whileTSS hasanupdatecomplexityof O(d),itsclassificationtimeismuchslowerthanotherexistingpacket classificationmethodsbecausethenumberofhashtablesistoolarge. CurrentpracticesforSDNpacketclassificationrelyoncaching,atechniquethatimprovespacket classificationspeed.Cacheisafastmemorywithlimitedcapacity(typicallySRAM)locatednear processingunitwithordersofmagnitudefasterthanthemainmemorystorage(typically,DRAM). Wecanimplementasimplestandardcachebymemorizingthesignatureofthepacketquerysothat wecanreturnthecorrectflowofthefuturepacketthathavethesamesignature.Theeness ofcachingdependsheavilyonlocalityofthereference,orpatternsofflows.Thelookuptimecan 3significantlyreduceifmajorityofthepacketclassificationresultsarefoundinthecache. Wearguethatitisnottorelyoncachinginthelongrun.Inotherwords,weshouldtreat localityofreferenceasabonusforpacketclassifierwheneverhashighlocality.Otherwise, thepacketclassifierperformancewillgobacktothefulllook-upmodeintheworstcase.Locality ofreferenceismorechallengingtopreservewhentherearemanyflows.UnlikeIPlookup,packet classificationcachesizemustscalewiththenumberofflows(i.e.,numberofrules)tomaintain highlocality[1,16].Morecomplexnetworkapplicationsalsocontributetoavarietyofflows, andhencelesslocalityforthecachetoexploit.One(expensive)solutionistousemorehardware tomaintainhighlocality;thisisclearlynotsustainableinthelongrunbecauseofthecost. Ourgoalistodevelopandynamicpacketclassifierthatworkswellevenwithhigh dimensionality.Morespecifically,apacketclassifiermustprovidehigh-speedpacketclassification andfast-rule-updateatthesametime.Inotherwords,thepacketclassifiercannotassume constructionandpreprocessing.Atthesametime,thepacketclassifiermustscalewellwithhigh dimensionalityanddoesnotrelyoncache.Finally,wemustuseonlylinearspacewithrespectto thenumberofrules. 1.2ProposedApproach:anOverview Akeyelementofourapproachistoapartitionanarbitraryrulesetinto sortable rulesets. Partitioningtosortablerulesets,whichcanbestoredinbinarysearchtreesandthusprovideboth fastclassificationandfastupdate,separatesourapproachfrompreviouspartitioningstrategiesthat partitiontodecisiontrees,whichdonotsupportfastupdate,ornon-overlappingrulesets,whichdo nothaveanaturaldatastructurethatguaranteesfastclassificationorupdate. Theintuitionisthatsortingone-dimensionalrulesissimplesincetheyareonlyintervalsinone dimension.Thebasicideaisthatwechooseafieldorder(permutation) fandthencomparetwo rulesbycomparingtheirprojectionsinthefields( i.e.,dimensions)sequentially.Forexample,in Figure1.1,ifwechoosefieldorder XY,then R1XYR4becauseR1’sprojectioninfield X,which is[1,3],issmallerthan R4’sprojectioninfield X,whichis [5,7];butifwechoosefieldorder YX,4 Figure1.1:Sortablerulesetwith xythenR4XYR1becauseR4’sprojectioninfield Y,whichis [1,3],issmallerthan R1’sprojection infield Y,whichis [5,7].Asanotherexample, R4XYR2becausealthoughthefirstfield Xcannotseparatethemapartastheirprojectionsinfield Xareboth [5,7],field Ycanseparatethemapartas R4’sprojectioninfield X,whichis [1,3],issmallerthan R2’sprojectioninfield X,whichis [5,7].1.2.1SortableRulesetPartitioning Givenanarbitraryruleset,wepartitionitintoacollectionofsortablerulesets.Notethefield ordersforeachpartitionmight.Wenotemanypreviouspacketprocessingapproachessuch as[6]andSmartSplit[7]havealsopartitionedrulesetstotryanddealwiththereplication ofrulesthatisinherentinthepopulardecisiontreedatastructuresusedbymanypacketprocessing solutions.Whiletheirpartitioninghasreducedrulereplication,themainbenefithasbeentoreduce thememoryexplosionthatoccurswithoutpartitioning.Becausethefinaldatastructureisadecision tree,theresultingpartitionsstilldonotsupportfastupdateasthereisstillrulereplication(even ifreduced);theirsolutionsarenotappropriatefordynamicSDNsecuritypolicies.Alternatively, SAX-PAC[8]partitionsrulesetsintononoverlappingrulesets.Unfortunately,thereisnonaturaldata structureforstoringnonoverlappingrulesetssothatpacketclassificationcanbeperformedquickly. Inessence,SAX-PACcanguaranteefastclassificationforonlytwodimensionalrulesbecausethey havenottargetedanappropriatedatastructuretoperformfastclassification.Becausewepartition 5rXYYX XYFigure1.2:Examplesofsortablerulesetpartitioningwithfieldorder XY,YX,andXY.tosortablerulesets,weovercomethelimitationsofpriorartinthatwecanclassifypacketsand updaterulesintheresultingdatastructurein O(logn)timeusingbinarysearchtrees.Anexample ofsortablepartitioningcanbeseeninFigure1.2.Ourgoalinpartitioningistominimizethe numberofresultingpartitionsbecausewemustsearcheachpartitionintheworstcase.Wecan viewpartitioningfrombothanonlineandanperspective.Intheonlineperspective,wehave anexistingpartitioningoftherulesandmustaddorremovearulefromtheexistingpartitions.In theperspective,wehaveasetofrulesthatmustbepartitionedasweseefit.The problemisimportantevenforSDNasthesystemmayperiodicallyrepartitiontherulesettoimprove performance. 1.2.2Rank-IntervalTree(RIT) Next,wedescribeandatastructurethatpotentiallysupports O(d+logn)ruleinsertion,rule deletion,andpacketsearch.Becausecomparingtworulesrequires O(d)time,astandardbalanced binarysearchtreewouldonlyguarantee O(dlogn)timeratherthan O(d+logn)time.Thereare treesthatsupporttheseoperationsin O(d+logn)time[17–20].Ourcontributionisthatwepropose anewtreebalancingtechniqueforRITthatyieldsthesameoptimalrunningtime. WeproposeacandidatedatastructurecalledRank-IntervalTreeRITwherenodesarestandard 6binarysearchtreenodesaugmentedwitha“nextfield”pointer.RITworkswiththeuniqueintervals ineachfield.Forexample,considerfield f1andthecorresponding nintervalsoftherulesinsorted order.Supposethefirst n/2intervalsareidenticalandtheremaining n/2intervalsareunique.Then thisrulesethas n/2+1uniqueintervalsinfield f1;thefirstintervalhascardinality n/2andthe remainingn/2intervalshavecardinality1.ThisexampleisdepictedinFigure1.3. HowshouldRITstoretheseuniqueintervals?Thekeyobservationisthatitmusttakeinto accountbothcardinalityandbalancing.Ifthecardinalityofanodeisyhigh,itmust behighinthetree.ConsiderourrunningexampleinFigure1.3;ifitonlybalancesandignores cardinality,thefirstintervalwithcardinality n/2willbeatdepthlog n/2+1;ifthispatternrepeats inlaterfields,thisproducesatreewithdepth (dlogn).Iftherearenohighcardinalitynodes,then itshouldbeastandardbalancedbinarysearchtree,butweachievethisbycombiningnodesand focusingjustoncardinality. in/4+ 1 111n/21i1in/2+ 1 i1n/211in/2 + 1 i21Corresponding Standard Balanced BST Corresponding RITree i1c(i1) = n/2i2c(i2) = 1 In/2 + 1 c(in) = 1 . . . Input Instance of n/2 + 1 unique intervals laid out in sorted order: in/4+ 1 Figure1.3:ExampleillustratingneedforRIT.Inputinstanceconsistsof n/2+1uniqueintervals wheresmallestintervalinsortedorderhascardinality n/2.Thecorrespondingstandardbalanced binarysearchtreehashighcardinalityintervalatdepthlog n/2+1whereasRIThashigh cardinalityintervalatdepth1.NotetheactualRITreewouldhavespanningnodes(definedin Section4.2.1);weomitheretohighlightintuition. 1.3HighlightsofResults WecomparePartitionSorttoTSSbecauseitthebestcombinationofclassificationtime andupdatetimeandthusisusedbyOpenvSwitch[11].WealsocomparewithSmartSplitasa 7state-of-the-arttraditionalpacketclassifierthatignoresupdate. ExperimentalSetup: WegeneraterulesetsusingClassBench[21]whichmimicsthreeruleset types:accesscontrollists(ACL),firewalls(FW),andIPChains(IPC).Wegeneratedrulesetswith 1k,2k,4k,...,64krules;hereweshowresultsusingthe1k,4k,16kand64krulesetstoimprove readability.Foreachsizeandseed,wegenerated20rulesetsandreporttheaverage classificationtimeandruleupdatetime. Metrics: Wecomparedthesealgorithmsusingfourmetrics:classificationtime,updatetime, space,andconstructiontime.Westudiedthescalabilityofthealgorithmsonthesemetricswith respecttothenumberofrules nandthenumberoffields d.Summary: OurresultsshowthatPartitionSortisuniquelycompetitivewithbothTSSinupdate timeandSmartSplitinclassificationtime.Inparticular,PartitionSortperformsupdatesin0.65 µsonaveragewhichiscomparabletothatofTSSwhileSmartSplitrequires100sofsecondsto reconstructsomeclassifiers.Atthesametime,PartitionSortclassifiespacketsin0.29 µsonaverage whichiscomparabletothatofSmartSplitwhileTSSrequiresanorderofmagnitudemoretime. WeshowbelowacomparisonofPartitionSortandTSSfocusingonclassificationtimeandupdatetime versusthenumberofrules. NumberofColors: WefirstcomparethenumberofcolorsrequiredbyPartitionSortandPTSS asthishelpsdeterminethenumberofpartitionssearchedandlargelyexplainswhyPartitionSort outperformsPTSS. PartitionSortusesanorderofmagnitudefewercolorsthanPTSS. ForACL, FW,andIPCrulesetswith32krules,thenumberofcolorsusedbyPartitionSortandPTSSareon average16.3vs.241.4,22.3vs99.2,and9.5vs.170.9,respectively.ThissuggestsPartitionSort willclassifyrulesanorderofmagnitudefasterthanPTSS. ClassificationTime Ourexperimentalresultsshowthat,onaverage,PartitionSortclassifies packets7.2timesfasterthanTSSforalltypesandsizesofrulesets. Thatis,foreachofthe420 rulesets,wecomputedtheratioofTSSclassificationtimedividedbyPartitionSortclassification timeandthenaveragedthese420ratios.Whenrestrictedtothe60size64krulesets,PartitionSort 8classifiespackets6.7timesfasterthanTSSwithamaximumratioof20.1andaminimumratio of2.6.Figure1.4(a)showstheaverageclassificationtimesforbothPartitionSortandTSSacross allrulesettypesandsizes. BesidesbeingmuchfasterthanTSS,PartitionSortisalsomuchmore consistentthanTSS. UpdateTime OurexperimentalresultsshowthatPartitionSortachievesveryfastupdatetimes withanaverageupdatetimeof0.65 µsandamaximumupdatetimeof2.1 µs.Onaverage, PartitionSort’supdatetimeisonly1.7timeslargerthanTSS’supdatetime.Figure1.4(b)showsthe averageupdatetimesacrossallrulesettypesandsizesforbothPartitionSortandTSS.Thisresult isconsistentwiththefactthatTSSisoptimizedforfastupdate. Figure1.4:PartitionSortandPTSSclassificationtimesandupdatetimes. 1.4RecentDevelopment AfterPartitionSort,thereareafewmorepacketclassificationalgorithmsthatfocusonupdate time.TupleMerge[22]isanewpartitioning-basedpacketclassifierthatimprovesTSSbymerging compatibletuplesinTSSinalessrestrictivewaythanthatinTSS.Thisapproachreducesa 9significantnumberoftuples,andsoimprovestheoverallclassificationandupdatespeed.In comparisontoPartitionSort,TupleMergemayhavemorepartitionsthanthatinPartitionSort,but eachpartitionisrepresentedasahashtable,whichisfasterthanabinarysearchtree.Therefore, itispossibletohavemorehashtables,andstillresultinslightlyfasteroverallclassificationtime. CutSplit[23]isanewdecision-treepacketclassifierthatimprovespreviousdecisiontreetechniques byexplotingthecuttingandsplittingtechniquesadaptively.ThekeydevelopmentisthatCutSplit managestodynamizedecisiontreesthatareknowntobehardtohandleruledynamicity.Being unawareofourwork,Yangetal[24]proposeanimprovedversionofaggregatedbitvectorscheme wheretheyreplacebitvectorsandmakethebitwise‘AND’operationofBloomfilterswiththegoal toimprovebothclassification,andupdatespeed.However,thereisnocomparisonwithPartitionSort andTupleMergeintheirwork. 1.5FutureWork Therearetwomaindirectionsforfuturework.Firstdirectionistoextendouralgorithmto workwithbatchedprocessing.Secondistointegrateourframeworkintoopen-sourceOpenFlow switches. 1.5.1BatchedProcessing Givenabatchofpackets,wecanclassifythemusingthebasicideaofmergesort.Namelywedo roundsofsortingpacketsandthenmergingthemwithsortedrule.Withbatchedprocessing,we canachievepacketclassificationusingamortizedO(1)timeperpacketifweusealineartime sortingalgorithmsuchasradixsort.Thealgorithmisfullycompatiblewithoursorted-partitioning approachwhichsupportsbothsingle-queryandbatchedqueryclassification. 1.5.2IntegrationwithOpenFlowswitches WewillintegrateourideasintotwoopensourceOpenFlowswitches:LagopusandOpenvSwitch. Wehavealreadydoneapreliminaryintegrationof1and2withLagopus.However,OpenvSwitchis 10morewidelyused.Forthisproject,weproposetointegrateallofourkeyideasintoOpenvSwitch. TherearetwokeychallengesthatwemustovercometosuccessfullyintegrateourideasintoOpen vSwitch.First,wemustgeneralizePartitionSorttohandleruleswitharbitrarybitmasks.Second, wemustdevelopcachingschemesforPartitionSortsimilartothemegaflowcachingschemethat OpenvSwitchcurrentlyuseswithitsTupleSpaceSearchpacketclassifier. 11CHAPTER2 RELATEDWORK Fromthetheorycommunity,priorworkismostlyonOrthogonalPointEnclosureQuery.Fromthe networkingcommunity,priorworkfallsintotwomaincategories:softwarebasedandhardware based.2.1OrthogonalPointEnclosureQuery Fromcomputationalgeometry,wedonothaveanyknownresultsthatgiveusdynamic d-scalablealgorithmsforanyOPEQvariants.WedoknowthatOPEQwith d=1,whichisalsoknownasthe intervalstabbingqueryproblem,canbesolvedin O(logn)timeusinglinearspaceinthedynamic setting.Forreportingandcountingvariants,thereareseveralwaystoachievethisresult[25,26]. Forthepriorityvariant,optimal O(logn)dynamicsolutionshavebeengivenin[27,28].Wecan extend d-dimensionalsolutionsto (d+1)-dimensionalsolutionsusingsegmenttreesatacostof amultiplicativefactorof O(logn)inbothspaceandtime[29].Ifwerestrictboxestobedisjoint ornested,Kaplan etal. [30]eliminatethemultiplicativefactorof O(logn)forqueries;however, spaceandupdatesstillrequirethemultiplicativefactorof O(logn).Finally,thegeneraltechnique forhandlingthedynamicsettingistostartwithagoodsolutionforthestaticcaseandthenuse generaltransformationtechniqueswithadditionalcostofspaceortime[31–33]. 2.2SoftwareBasedPacketClassification Mostpriorsoftwarebasedpacketclassificationalgorithmsarebasedondecisiontrees;they inhowtoconstructthetree.RepresentativeonesareHiCuts[3],HyperCuts[4],andHyperSplit[5]. Thesemethodsgenerallyproduce O(logn)classificationtimesatthepotentialcostofsuperlinear spaceduetorulereplication.HiCutsandHyperCutspartitionpacketspacewithmultiplecutsat eachtreenodewiththegoaltoreducetreeheight;however,thismayleadtogreaterrulereplication. HyperSplitsplitspacketspacewithjustonecutateachtreenodeleadingtolessrulereplicationat 12thepotentialcostofgreatertreeheight.However,HyperSplitstillfromrulereplicationand thusrequiressuperlinearspace.Tomitigatetheofrulereplicationindecisiontreemethods, [6]andSmartSplit[7]usemultipledecisiontrees.Theycategorizerulesbywhetherthey are“small”or“large”ineachfieldandlabelrulesasconflictingiftheirvectorsofsmallandlargeare notidentical.Fortherewouldbe2 dpossibledecisiontreeswhereeachtreeisaHyperCuts tree.ForSmartSplit,thereareonly4possibledecisiontreesastheyspecializetotraditional5-field classificationandonlyapplythiscategorizationtothesourceanddestinationIPfields.SmartSplit analyzestheresultingrulesandthenchoosesbetweenHyperSplitandHyperCuts.Although andSmartSplitreducerulereplicationandthuslimitthesuper-linearmemoryusage,theydonot eliminatereplicationandthusruleupdatesarestillproblematic;furthermore,theydonotscale elyto d>5.Kogan etal. proposedSAX-PAC[8]wheretheypartitionarulesetintosetsof non-intersectingrules,whichmeansthateachpartitionisessentiallyaPLOSinstance,andPLOS isnotknowntobe d-scalable.Suchpartitioncriteriaaretoorelaxedresultinginpartitionsthat donotguaranteefastclassificationorupdate.Becausedecisiontreemethodsdonotsupportfast updates,OpenvSwitch[11]usesTupleSpaceSearch(TSS)[15]forpacketclassification.TSS achievesfastupdatesbecauseitcanquicklyidentifywhichtuplecorrespondstoagivenrule.Each partitionisthenimplementedusingahashtableonthetuplemeaningruleinsertionanddeletion takes O(d)expectedtime;thetimeis O(d)ratherthan O(1)becauseallrelevantfieldsmustbe extractedandhashed.Thelimitationisthatthedefinitionoftuplesistoostrictresultingintoomany partitions.Sometechniqueshavebeenproposedtoimproveperformancesuchasperforminga searchonspecificfieldsin O(logn)timetoidentifyeligibletuples[15].However,thesetechniques complicateruleupdate,andOpenvSwitchhasnotimplementedtheseoptimizations. 2.3HardwareBasedPacketClassification MostprevalenthardwarebasedpacketclassificationsolutionsarebasedonTernaryContent AddressableMemory(TCAM).ATCAMchiptakesasinputasearchkeyandthenuseshardware circuitstocomparetheinputsearchkeywithallofitsoccupiedentriesinparallel.Itthenusesa 13priorityencodertoidentifytheindex(orcontentsifdesired)ofthefirstmatchingentry.Thisalltakes placeinconstanttime( i.e.,afewclockcycles).TheCAMisternarybecauseeachentryconsists ofanarrayof0’s,1’s,or*’s( don’t-care values).Apacketheader( i.e.,asearchkey)matchesa TCAMentryiftheircorresponding0’sand1’smatch.TCAMhasseverallimitations.First,TCAM chipshavelimitedcapacity.ThelargestavailableTCAMchiphasacapacityof72megabits(Mb), while2Mband1Mbchipsarethemostpopular.Second,TCAMchipsconsumealargeamountof power duetotheirparallelsearching.ThepowerconsumedbyaTCAMchipisabout1.85Watts permegabit(Mb)[34],whichisroughly30timeslargerthanacomparablysizedSRAMchip[35]. TheseproblemsareexacerbatedwhenweconsiderOpenFlowpacketclassificationwithmorefields andwiderfieldssuchasIPv6IPaddresses.Asaresult,whileTCAMisusedinsomeOpenFlow implementations,TCAMisnotascalablesolutionthattrulymeetsthedemandsofOpenFlow packetclassification.K etal. alsoshowhowthedataplanecanlagbehindthecontrolplane byupto400msinsomeTCAMimplementationsofOpenFlow[12].AlthoughTCAMspacecanbe minimizedusingvariousTCAMoptimizationalgorithms[36–59],onceoptimized,itisextremely (oftenintermsofminutesorhours)toperformupdatesaseachupdatetypicallycause thewholeTCAMtabletoberecomputedfromscratch.Recently,GPU[60,61]andFPGA[62,63] basedpacketclassificationsolutionshavebeenproposed.Thesealgorithmsarenotsuitablefor OpenFlowpacketclassificationbecausetheyareveryforupdating. 2.4BatchProcessing Batchprocessinghasbecomecommonplaceinlower-levelbuildingblocksofnetworkingstack. Netmap[64]isaframeworkforfastpacketI/O,availableinLinux,FreeBSD.Netmapreduces overheadfromprocessingonepacketatatime.Thesavinggainedbyalargebatchcomesfrom removingper-packetdynamicmemoryallocations,systemcalloverheads,amortizedoverlarge batches.Intel’sDPDKisanopen-sourceprojectthataimsforachievinghighI/Operformance,and highpacketprocessingrates.ThekeyadvantageofDPDKisthatitisauserspaceapplicationthat interactsdirectlytothenetworkhardwarewithoutpassingthroughLinuxkernelnetworkingstacks. 14Inadditiontothelow-levelnetworkingstack,batchprocessingtechniqueisbroughttohigh-level networkingfunctionality.VectorPacketProcessor(VPP)[65]architectureprovideslayer2and3 networkingfunctionalitiesbasedonlow-levelbuildingblocksuchasDPDK.Theuniquefeaturefor VPPisthatVPPextendsthebatchingfromlow-levelbuildingblocktohigh-levelpacketprocessing functions.Thenetworkfunctioncanberepresentedasatree.Insteadofprocessingonepacketata time,VPPprocessabatchofatmost256packetsatoncebeforemovingonthenextnode. Wenowturnattentiontobatchinginpacketclassification.Givenabatchofpackets,wecan processallpacketsthebatchinparallel,andthuswecanachievesignificantperformancespeedup. Acommonmassively-parallelprocessorisGraphicsProcessingUnit(GPU).PacketShader[66] exploitsparallelismfromGPUtospeedupthesoftware-routerbyintroducinghigh-performance packetI/OengineattheoperatingsystemlevelandpacketbatchestoGPU.However, theyshowspeedupoverlinearsearchclassifier.TheydidnotshowifGPUcanactuallyspeed upovermoreadvancedpacketclassifier.Recently,[67]designanewGPU-basedalgorithmthat featuresimprovedmemoryaccesspatterntoreducelatencytohipmemory.Furthermore,they showedsignificantspeedupoverthreetypesofpacketclassifiers:linearsearch,Bloom-filter,and TupleSpacesearchclassifier. Onemajordrawbackforbatchedprocessingishighlatency.[66],and[67]reportedlatencyin rangebetween200microsecondsto1000microsecondsdependingonpacketsizeandclassification algorithms.ThishighlatencywasbecauseGPUrequireslargebatchestomaximizethroughput. Toobtainlargebatch,weneedtowaitforpackettoqueueuptothedesiredbatchsize.Moreover, withGPUwemustdealwithpacketsfromhostCPUtoGPU,thisrequirescareful implementationofGPUusingknowntechniquessuchaslatencyhiding. 15CHAPTER3 PARTITIONSORT 3.1Introduction 3.1.1MotivationandProblemStatement Software-DefinedNetworking(SDN)definesanewabstractiontoseparatethecontrolplaneand thedatalayerofthenetworkingstack.Abstractionmeanstheuseofcommoninterfacesforhetero- geneousnetworkdevicesofvendorsandarchitecturestocommunicatewiththecentral controllerandtoimplementthefunctionsdemandedbythecontroller.OneinstanceofSDNisthe OpenFlowstandard[9,10]. ThecorepacketprocessingfunctionsinSDNare(1)packetclassificationand(2)ruleupdate whichinteractthroughasharedrulelistdatastructureTheadventofSDNleadstonewchal- lenges,dynamismanddimensionality,whichmakeruleupdatehavesimilarimportancetopacket classification.InSDN,rulesarefrequentlyinserted,modifiedordeletedbythecontrollertomeetanapplica- tions’requirementssuchasestablishinganewnetworkpathwithagivenqualityofservice.Thus, updatetimeinadditiontoclassificationtimemustbeminimized.Forexample,OpenvSwitch[11] usesPriorityTupleSpaceSearch(PTSS)foritspacketclassifiereventhoughPTSShasrelatively slowclassificationduetoPTSSsupportingfastupdate.TheimportanceoffastupdateinOpenFlow ishighlightedbyK etal. ’swork[12];theyshowthatindeployedOpenFlowswitchesthatuse ternarycontentaddressablememory(TCAM),thedataplanemightlagbehindthecontrolplane byasmuchas400msandruleupdatesmayhappenoutoforder.Thisisanobvioussecurityrisk. Dimensionalscalabilityhasbecomeanimportantfactorascomplicatedfunctionalityrequires muchmoreflexibilityoffieldinpacketprocessing.Intraditionalpacketclassification,thenumber offieldsis5withrelativelyfewupdaterequests.InSDNspace,thenumberoffieldstendtogrow largertosupportsophisticatedfunctionalityofnetworkingapplications.InOpenFlow,forexample, 161 Classification Time Update Time 2 1 2 3 100 SmartSplitPartitionSortTuple Space Search Figure3.1:PartitionSortisuniquelycompetitivewithpriorartonbothclassificationtimeand updatetime.ItsclassificationtimeisalmostasfastasSmartSplitanditsupdatetimeissimilarto TupleSpaceSearch. thenumberofheaderfieldsupportis45.Recently, P4hasbeenintroducedtosupportprogramming protocolindependentpacketprocessing[10].Hence,anypacketclassifiermustadapttoarbitrary numberoffields. Thedynamicpacketclassificationproblemisdefinedasfollows.Apacketfield fisavari- ablewhosedomain,denoted D(f),isasetofnonnegativeintegers.Aruleover dpacketfields f1,f2,···,fdcanberepresentedas (s1f1s2f2··· sdfddecisionwhereeach siisanintervalindomain D(fi).Forexample,prefix192.168.*.*denotestherange[192.168.0.0, 192.168.255.255].Apacket p=(p1,p2,···,pd)satisfiestheaboveruleifandonlyifthecon- dition(p1s1p2s2···( pdsd)holds.Atable Rconsistsofasequenceof nrules r1,r2,···,rn.Givenapacket p,thepacketclassificationproblemistofindthefirstrulein r1,r2,···,rnthat pmatches. Inaddition,dynamicpacketclassificationmustsupportfast-update intermsofinsertionanddeletionofruleswithoutsignificantlyslowingdownclassificationspeed. 173.1.2LimitationsofPriorArt Oneofthefundamentalchallengesinpacketclassificationistosimultaneouslyachievehigh-speed classificationandfastupdate.MostexistingmethodssuchasSmartSplit[7]havefocusedon minimizingclassificationtimewhilesacrificingupdatetimeandmemoryfootprintwhilesome methodslikeTupleSpaceSearch(TSS)[15]havesacrificedclassificationtimetoachievefast updates.Thenetresultisthatthehigh-speedclassificationmethodsarenotcompetitiveonupdate timewhereasthefastupdatemethodsarenotcompetitiveonclassificationtimeasshowninFigure 3.1.SmartSplit[7]isthestate-of-the-artdecisiontreemethodasitbuildsuponthepreviousbest methodsHyperCuts[4],[6],andHyperSplit[5].SmartSplitachieveshigh-speedclas- sificationbyleveragingthelogarithmicsearchtimesofbalancedsearchtrees.Unfortunately,no decisiontreemethodincludingSmartSplitafasterupdatemethodotherthanreconstructing thetreebecauseanupdateoftenrequirestoomanymodificationstothesearchtree.SmartSplit thefastestconstructiontimeforanydecisiontreemethodbyanalyzingtherulesinquestion andthenconstructingHyperCutsorHyperSplittreesbasedonitsanalysis.ThisbringsSmartSplit’s constructiontimedowntoafewminuteswhichisseveralordersofmagnitudelargerthanstandard OpenFlow’srequirementswhereupdatesshouldbecompletedinmicroseconds[12]. TSS[15]usedinOpenvSwitch[11]isthestate-of-the-artfastupdatemethod.TSSachieves fastupdatesbypartitioninganOpenFlowrulesetintosmallerrulesetsbasedoneasilycomputed rulecharacteristicssothatrulescanbequicklyinsertedanddeletedfromhashtables;however, TSShaslowclassificationspeedbecausethenumberofpartitionsislargeandeachpartitionmust besearchedforeverypacket. 3.1.3ProposedApproach Ourproposedapproach,PartitionSort,introducestheconceptof rulesetsortability thatallows PartitionSorttounifythebenefitsofhigh-speeddecisiontreeclassifiersandthefast-updateTSS classifiertoachieveanewclassificationschemethatisuniquelycompetitivewithbothhigh-speed 18classificationmethodsonclassificationtimeandfastupdatemethodsonupdatetimeasshownin Figure3.1.PartitionSortpartitionsarulesetintoasmallnumberofsortablerulesets.Westoreeach sortablerulesetinamulti-keybinarysearchtreeleadingto O(d+logn)classificationandupdate timepersortablerulesetwhere dandnarethenumberoffieldsandrules,respectively.Thememory requirementislinearinthenumberofrules. PartitionSortisahybridapproachthatleveragesthebestofdecisiontreesandTSS.Similar toTSS,PartitionSortpartitionstheinitialrulesetintosmallerrulesetsthatsupporthigh-speed classificationandfastupdates.Similartodecisiontreemethods,PartitionSortachieveshigh-speed classificationforeachpartitionbyusingbalancedsearchtrees. 3.1.4TechnicalChallengesandProposedSolution WefacefourkeytechnicalchallengesindesigningourPartitionSortapproach.Thefirstis definingrulesetsortabilityformulti-dimensionalrules .Itischallengingtosortmulti-dimensionalrulesina waythathelpspacketclassification.Weaddressthischallengebydescribinganecessaryrequirement thatanyusefulorderedrulesetmustsatisfyandthenintroduceourfieldordercomparisonfunction thatprogressivelycomparesmulti-dimensionalrulesonefieldatatime. Thesecondtechnicalchallengeis designingandatastructureforsortablerulesets thatsupportshigh-speedclassificationandfastupdateusingonlylinearspace.Weshowthatournotion ofrulesetsortabilitycanbetranslatedintoamultikeysetdatastructureandhenceitispossibleto have O(d+logn)search/insert/deletetimeusingamulti-keybalancedbinarysearchtree.Wealso proposeapathcompressionoptimizationtospeedupclassificationtime. Thethirdtechnicalchallengeis elypartitioninganon-sortablerulesetintoasfew sortablerulesetsaspossible .Weaddressthischallengebyareductiontoanewgraphcoloring problemwithgeometricconstraint.Then,wedevelopafastsortablerulesetpartitioning algorithmthatrunsinmilliseconds. Thefourthchallengeis designinganeonlinepartitioningalgorithm .Thisisparticularly challengingbecausewemustnotonlyachievefastupdatesbutalsopreservefastclassificationtime 19inthefaceofmultipleupdates.Weuseanrulesetpartitioningalgorithmasasubroutineto designafastonlinerulesetpartitioningalgorithmthatstillachievesfastclassificationtime. 3.1.5SummaryofExperimentalResults WeconductextensivecomparisonsbetweenPartitionSortandothermethods,inparticularTSSand SmartSplit.OurresultsshowthatPartitionSortisuniquelycompetitivewithbothTSSinupdate timeandSmartSplitinclassificationtime.Morespecifically,PartitionSortperformsupdatesin 0.65µsonaveragewhichiscomparabletothatofTSSwhileSmartSplitrequires100sofseconds toreconstructaclassifier.Atthesametime,PartitionSortclassifiespacketsin0.29 µsonaverage whichiscomparabletoSmartSplitwhileTSSrequiresanorderofmagnitudemoretime.With caching,PartitionSortclassifiespacketsroughly1.84timesfasterthanTSS. Therestofthepaperisorganizedasfollows.WefirstdescriberelatedworkinSection3.2.We thendefinerulesetsortabilityinSection3.3.WethendescribeanMulti-dimensionalIntervalTree inSection3.4,anpartitioningschemeinSection3.5andthefullPartitionSortalgorithmin Section3.6.WeprovidetheoreticalanalysisofPartitionSortinbothworst-caseandaveragecase inSection3.7.WethendescribeanoptimizationbasedonRule-Splittingtogroupincompatible rulesinthesamepartitioninSection3.8.WethengiveourexperimentalresultsinSection3.9and concludethepaperinSection3.10. 3.2RelatedWork Fromcomputationalgeometrypointofview,packetclassificationproblemisessentiallya priorityOrthogonalPointEnclosureQuery(OPEQ)problemwherewepreprocessasetof nd-dimensionalaxis-parallelboxessothatwecanreportthehighestpriorityboxthatcontainsaquery point.Aspecialcasewhere d=1,alsoknownasthepriorityintervalstabbingqueryproblem, canbesolvedin (logn)timeusinglinearmemoryindynamicsetting[27,28].Wecanextend d-dimensionalsolutionsto (d+1)-dimensionalsolutionusingsegmenttreesatacostofmultiplicative factorof O(logn)inbothspaceandtime[29].Unfortunately,usinglinearspace,anydatastructure requires (logn(logn/logd)d−2+k)timetoprocessaquery[14].ItisunclearifthePointLocation 20problemwhichisessentiallyanOPEQproblemwithnon-intersectingboxescanbesolvedinsub- polylogarithmictime.ThebestknownresultisduetoRahul’sresult[68]forthestaticversionwhere queriescanbeprocessedin O(logd−3/2n)time.Inpacketclassification,however,rulesetsdonot exhibitworst-caseinstances[2,69].Inparticular,ifwerestrictthestructureofrulesetsgivenby ClassBench[21],weshowthatitispossibletoachieve O(dlogn+log2n)classificationtimeusing linearmemory. Wedividepreviousworkonpacketclassificationintofourcategories:decisiontreemethods, partitioningmethods,hybridmethodsthatusebothdecisiontreesandpartitioning,andTCAM- basedmethods.Decision-treemethodssuchasSmartSplit[7],HiCuts[3],HyperCuts[4],and HyperSplit[5]recursivelypartitionthepacketspaceintoseveralregionsuntilthenumberofrules withineachregionfallsbelowapredefinedthreshold.Thesemethodsleveragethelogarithmicsearch timeofdecisiontreestoachievefastsoftware-basedpacketclassification.Theirkeydrawbackis thatwhenpartitioning,eachruleintheoriginalrulelistiscopiedintoanewsublistforeachregion thatintersectsit.Itispossiblethatrulesmaybereplicatedintomanyregionsleadingtohigh memoryconsumptionaswellasslowandcomplicatedupdatessinceeachcopymustbeinsertedor deleted.Incontrast,thedecisiontreesinPartitionSorthavenorulereplication.Thus,PartitionSort useslinearspaceandsupportsfastupdates. PartitioningmethodssuchasTupleSpaceSearch[15]andSAX-PAC[8]workbypartitioning theoriginalrulesetintoacollectionofsmallerrulesetsthatareeacheasiertomanage.TSSpartitions rulesbasedontupleswhicharethepatternsofprefixlengthsofeachfieldinagivenrule.The specificityofTSSpartitioningisbothastrengthandweakness.Itisgoodbecausetheresulting partitioncanbesearchedusingahashfunctionleadingto O(d)classificationtimeperpartition andO(d)ruleupdatetime.Itisbadbecauseitproducesalargenumberofpartitionsthatneed tobesearched,resultinginslowclassificationtime.PartitionSortovercomesthisissuebyusing arelaxedpartitioningconstraintthatresultsinfarfewerpartitions.Incontrast,SAX-PACusesa moregeneralpartitioningschemethanPartitionSort;specifically,rulesfitwithinapartitionaslong astheyarenon-intersecting.Everysortablerulesetisnon-intersecting,butnotviceversa.The 21drawbackwithSAX-PACisthatthereisnoknownfastclassificationmethodfornon-intersecting rulesetsunlessthenumberoffieldsisjusttwo.Incontrast,PartitionSortachieveshigh-speedand fast-updateclassificationonsortablerulesetsforanynumberoffields. AfewhybridmethodscombiningpartitioninganddecisiontreessuchasIndependentSet[70], [6]andSmartSplit[7]havebeenproposedtoreducerulereplicationandmanagethesuper- linearspacerequirementsofdecisiontreemethods.IndependentSetdevelopsaweakerpartitioning schemethatalsoeliminatesrulereplication.Specifically,theyuseonlyonefieldtopartitionrules requiringthatrulesarenon-overlappinginthatfield.Incontrast,PartitionSortusesmultiplefields topartitionrules.IndependentSet’sone-fieldpartitioningschemecreatesmanymorepartitions leadingtosignificantlyslowerclassificationtime.Ontheotherhand,andSmartSplit usepartitioningschemesbasedonobservablerulecharacteristics,buttheydonoteliminaterule replicationwhichmeansruleupdatingisstillcomplex.Specifically,andSmartSplitinitially placerulesintothesamepartitioniftheyaresmallorlargeinthesamefields.Theythenproduce eitheraHyperCutsorHyperSplittreeforeachpartition.Whereasbothmethodssignificantlyreduce rulereplicationandthesuper-linearspacerequirementsofdecisiontrees,neithereliminatesrule replication;thusbothstillfrompoorruleupdateperformance. Finally,therearemanyhardware-basedTCAMapproachesforpacketclassification[38–42,45, 71,72].TCAMcanbeusedwhentheclassifiersaresmall,butTCAMsizesareextremelysmall andTCAMconsumeslotsofpower.ItisnotclearthatTCAM-basedclassifierscanscaletohandle thedemandsofOpenFlowpacketclassification.Furthermore,theconstructiontimesofthemost compressiveTCAM-basedapproaches,whicharerequiredtodealwiththelimitedsizes,aretoo largetobeusedinthedynamicOpenFlowenvironment. 3.3RulesetSortability Wemustovercometwomainchallengesindefiningsortablerulesets.Thefirstisthatwemust defineanorderingfunction thatallowsustoorderruleswhichare d-dimensionalhypercubes. Considerthetwoboxes r1andr4inFigure3.2;onemightarguethat r1r4sincer1’sprojection 22intheXdimensionissmallerthan r4’sprojectionintheXdimension;however,onecouldalso arguethat r4r1becauser4’sprojectionintheYdimensionissmallerthan r1’sprojectioninthe Ydimension.Thesecondisthat mustbeusefulforpacketclassificationpurposes.Specifically, supposedefinesatotalorderingonrules r1throughrnandwearetryingtoclassifypacket p.If wecomparepacket ptorule rianddeterminethat p>ri,thenpacket pcanonlymatchsomerule amongrules ri+1throughrn.Thatis,packet pmustnotbeabletomatchanyofrules r1throughri. Figure3.2:Exampleoforderedrulesetwith xy3.3.1FieldOrderComparisonFunction Weproposethefollowing fieldordercomparisonfunction forsortingrules.Theintuitioncomes fromthefactthatsortingone-dimensionalrulesisstraightforward.Thebasicideaisthatwechoose afieldorder(permutation) fandthencomparetworulesbycomparingtheirprojectionsinthe currentfielduntilwecanresolvethecomparison.Continuingtheexamplefromabove,ifwechoose fieldorder XY,then r1XYr4because[1,3],r1’sprojectioninfield X,issmallerthan [5,7],r4’sprojectioninfield X.Amoreinterestingexampleisthat r4XYr2becausetheirprojectionsin fieldXareboth [5,7]whichforcesustoresolvetheirorderingusingtheirprojectionsinfield Y.Wenowformallydefineourfieldordercomparisonfunction.Wefirstdefinesomenotation givenafieldorder f.Let fidenotethe ithfieldof f.Foranyrule r,let fi(r)denotetheprojection ofrinfi,andlet fi(r)denotetheprojectionof rintothefirst ifieldsof f.23Wenowdefinehowtocomparetwointervalsusing f.Foranytwointervals i1=[min(i1),max(i1)]andi2=[min(i2),max(i2)],wesaythat i1f1(t),then s>ft.Otherwise, f1(s)=f1(t).Iffcontainsonlyonefield,then s=ft.Otherwise,therelationshipbetween sandtisdetermined byf=f\f1.Thatis,weeliminatethefirstfieldandrecursivelycompare sandtstartingwith fieldf2whichis f1.Tosimplifynotation,weoftenusethefieldorder ftodenoteitsassociatedfieldordercomparison functionf.Forexample,consideragaintherectanglesinFigure3.2and f=XY.Wehave r1XYr2sinceX(r1)max(f1(r)),then p>fr.If fcontainsonlyonefield,then pmatches r.Otherwise,therelationship between pandrisdeterminedby f=f\f1.Lemma3.3.1. Let nd-dimensionalrules r1through rnbetotallyorderedbyfieldorder f,andlet pbea d-dimensionalpacket.Forany 2in,if p>fri,then p>frjfor 1jfriastheothercaseisidenticalbysym- metry.Consideranypacket pandrules riandrjwherep>friandri>frj.ApplyingDefinitions 1and3,wecanprovethattransitivityholdsand p>frj.3.4Multi-dimensionalIntervalTree(MITree) WedescribeandatastructurecalledMulti-dimensionalIntervalTree(MITree)for representingasortablerulesetgivenfieldorder f.Inparticular,weshowthatMITreesachieve O(d+logn)timeforsearch,insertion,anddeletion;werefertothisas O(d+logn)dynamictime .Anobvious(andnaive)approachistostoreanentireruleforeachnodeandconstructabalanced binarysearchtreebecausetherulesaretotallyorderedbyfieldorder f.Therunningtimeisclearly O(dlogn)becausetheheightofabalancedtreeis O(logn)andeachcomparisonrequires O(d)time.Theproblemisthisrunningtimeisnotscalabletohigherdimensions.Figure3.3showsan examplesortablerulesetwithitscorrespondingnaivebinarysearchtree. Wecanspeedupthenaiveapproachbyafactorof dbyusingonefieldatatimewithaclever balancingheuristic.Weshowthisintwosteps.First,weshow O(d+logn)dynamictimefora specialcasewhereallintervalsarepoints.Weextendthissolutiontothegeneralcaseofsortable rulesets. Thespecialcasewhereallintervalsarepointsisexactlyamulti-keydictionaryproblem.A multi-keydictionaryisadynamicsetofobjectsthathavecomparisonsbasedonalexicalorder ofkeys.Oneexampleofamulti-keydictionaryisadatabasetableof nrowsand dcolumns.25XYZ r1[0,2][0,6][1,2] r2[3,4][0,1][1,2] r3[3,4][2,3][3,5] r4[3,4][4,5][3,6] r5[5,6][0,5][1,2] r6[5,6][0,5][4,6] r7[5,6][0,5][7,9] r4r2r1r3r6r5r7Figure3.3:Asortablerulesetwith7rulesand3fields,fieldorder f=XYZ ,andthe correspondingsimplebinarysearchtreewhereeachnodecontains dfields.Thereexistsamulti-keybinarysearchtreesupporting O(d+logn)dynamictimeforthemulti-key dictionaryproblem[73,74]. Inthegeneralcaseofsortablerulesets,weshowthatthe O(d+logn)resultisattainable.First, allkeysarecomparedinlexicalorderbecause,bydefinitionofsortablerulesets,fieldorder fisessentiallyapermutationofthenaturalorder [1..d].Furthermore,itisimmediatebythedefinition ofsortablerulesetsthatiftworulesareidenticalin [f(1),f(2),..., f(i−1)]thenat f(i),they eitheroverlapfullyorhavenointersection.ThispropertyallowsustoconstructanMITreethat behavesasiftheintervalisonlyapoint.Hence,wecanusethesamebalancingheuristictoachieve O(d+logn)dynamictime.Thesearchprocedureisidenticaltopointkeysexceptthatweneed additionalcheckingforintervalsforeachintervaltreenode. TheseresultsyieldthefollowingTheorem. Theorem3.4.1. Givenasortableruleset,Multi-dimensionalIntervalTree(MITree)supports searches,insertion,anddeletionin O(d+logn)timeusingonlylinearspace. Weperformoneadditionalpathcompressionoptimization.Weremoveduplicateintervalsfor eachfieldintheMulti-dimensionalIntervalTreesothateachuniqueintervalissharedbymultiple rules.Eachnode vthusrepresentsaparticularintervalinagivenfield.Each vthushasathirdchild containingtherulesthatmatchon v.Figure3.4showsanMITreefortherulesetinFigure3.3.Let c(v)bethenumberofrulesthatmatchnode v.Weobservethat cdecreasesfromearlierfieldsto 26laterfields.Thusif c(v)=1,thenthereisonlyonerule rthatcanmatch.Inthiscase,westorethe remainingfieldsof rwithvasshowninFigure3.4.Fortherestofthispaper,weuseMITreeto refertoacompressedMITree. [0,2][3,4][5,6][0,1][2,3][4,5][0,5][0,6][1,2][3,5][3,6][1,2]r3r4r2[1,2][4,6][7,9]r6r5r7r133131111XYZ[0,2][3,4][5,6][0,1][2,3][4,5][0,5][1,2][4,6][7,9]r6r5r733r13r3r2r4XYZFigure3.4:Wedepicttheuncompressed(left)andcompressed(right)MITreethatcorrespondto thesortablerulesetfromFigure3.3.Regularleftandrightchildpointersareblackanddonot crossfieldboundaries.Nextfieldpointersareredandcrossfieldboundaries.Inthecompressed MITree,nodeswithweight1arelabeledbytheonematchingrule. 3.5SortableRulesetPartitioning Rulesetsarenotnecessarilysortable,sowemustpartitionrulesetsintoasetofsortablerulesets. Becausetheclassificationtimedependsonthenumberofsortablerulesetsafterpartitioning,our goalistodevelopsortablerulesetpartitioningalgorithmsthatminimizethenumberof sortablerulesets.Hereweconsidertheproblemwhereallrulesareknown apriori .Westart byobservingthattherulesetpartitioningproblemisessentiallyacoloringofanintersection graph(tobedefinedshortly)bythe d!possiblefieldordersforsortablerulesets. Formally,thebasicapproachistopartitionruleset Rintoorderedrulesets (Ri,f(i))for 1iwhere1iRi=R,RiRj=,andeachsubset Riissortableunderfieldorder f(i).Thereisnorelationbetweenfieldorders f(i)andf(j);theymaybethesameor LetRconsistof n,possiblyoverlapping, d-dimensionalrules v1throughvn.Foreachofthe d!fieldorders f(i)for1 id!,wedefinethecorrespondingintervalgraph Gi=(V,Ei)whereV=Rand(vj,vkEiifvjf(i)vkfor1 jpr(Tj).Tomaintainthissortedorder,PartitionSortusesthe followingdatastructures.First,alookuptable M:Ridentifyingwhichtableeachruleisin. Second,foreachtree T,PartitionSortmaintainsaheap H(T)oftheprioritiesofeveryrulein T.3.6.1RuleUpdate(OnlineSortableRulesetPartitioning) Givenanexistingsetofrules,wenowdescribehowPartitionSortperformsruleupdates(insertions ordeletions).Westartwiththesimpleroperationofdeletingarule r.Using M,weidentifywhich tableTrisin.Wethendelete rfromT,remove pr(r)fromH(T),andresort Tifnecessary, typicallyusinginsertionsortsince Tisotherwisesorted.Ifnorulesremainin T,wedelete TfromMandfrom T.Wenowconsiderthemorecomplexoperationofinsertingarule r.Wefacetwokeychallenges: choosingatree Titoreceive randchoosingafieldorderfor Ti.Weconsidertrees Tiinpriorityorderstartingwiththehighestprioritytree.Whenweconsider Ti,wefirstseeif Ticanreceive rwithoutmodifying f(Ti).Ifso,weinsert rintoTi.However,beforecommittingtothis updatedtree,if |Tiforsomesmallthresholdsuchas 10,werunGrInd(cf.Section3.5) 30ontherulesin Ti(nowincluding r)touseanewfieldorderifGrIndprovidesonepartitionwith afieldorder.Thisreconstructionof TiwillnottakelongbecauseGrIndisfastand issmall.Ifso,weupdatethefieldorderandusethenewtree Ti.Ifwecannotinsert rintoTi,wereject Tiasincompatibleandmoveontothenext Ti.Ifnoexistingtree Tiwillwork,wecreateanew treeTifor rwithanemptyheap H(Ti).Inallcases,wecleanupbyinserting pr(r)intoH(Ti)andresort Tifnecessary. 3.6.2PacketClassification WenowdescribepacketclassificationinthepresenceofmultipleMITrees.Wekeeptrackof hp,thepriorityofthehighestprioritymatchingruleseensofar.Initially hp=0todenotenomatching rulehasbeenfound.Wesequentiallysearch Tifor1 itforpacket p.Beforesearching Ti,wefirstcompare pr(Ti)tohp.If pr(Ti)1.33Weshowthe rivaluesforour64kACL,FW,andIPCrulesetsinFigure3.6.Fromthisfigure, weseethattheIPC,ACL,andFW rivaluesare (2,1),(2,65),and (2,108)geometricprogressions, respectively,andallthe rivaluesare (1.38,1)geometricprogressions. 01020304050 Index Number of Remaining Rules12481632641282565121024204840968192163843276865536ACL FWIPCLog2Log1.38Figure3.6:Averagenumberofremainingrules( ri)plottedinlogscalewithbase2and1.38.The averageisacrossfrompartitionat iindexincludingthosewithzeros. Assumingweworkwithrulesetswherethe riaregeometricprogressions,wegetthefollowing boundonthenumberoftrees. Lemma3.7.1. Ifriisa ( )geometricprogressionthen b=O(logn).Proof. Thevalueof iwhereriisatmostlog ngiventhat rin/iuntilthen.Theremaining numberoftreesisatworst ,sotheresultfollows. Thisleadstothefollowingclassificationtimeresult. Theorem3.7.2. Ifriisa ( )geometricprogressionthenthetotalnumberofcomparisonsrequired byPartitionSortforqueriesandinsertionsisatmost O(dlogn+log2n).Proof. ThisfollowsdirectlyfromTheorem3.7.1andLemma3.7.1.Specifically,fromTheorem 3.7.1,wegetthatthenumberofcomparisonsis O(db+blog˜ n).FromLemma3.7.1,wegetthat b=O(logn).Combiningthetwoandobservingthat˜ nn,theresultfollows. 34Lookingatthedatamoreclosely,allthe rivaluesdropveryquicklyuntillessthanroughly600 orlessthan1%oftherulesremain.Then,the rivaluestapermoreslowlybutstillatasteady rate.Theremaybeotheroptionstohandlethelast1%orsoofrules.Forexample,assuggested byKogan etal. ,wecoulduseaTCAMclassifierifoneisavailable[8].Anotheroptionistousea standarddecisiontreesuchasaSmartSplittree.Finally,inSection3.8,weproposearule-spliting optimizationthatallowsustofurtherreducethenumberofsortablerulesetsrequired. 3.7.3SuccessfulSearchesandPriorityOptimization Sofar,wehaveassumedthatsearchesmustexploreall Ti.However,forsuccessfulsearches, thepriorityoptimizationdescribedinSection3.6.2allowsustoskipsome Tioncethecorrectrule isfound.Wenowanalyzehowmanytreesneedtobesearchedforsuccessfulsearchesassuming thateachruleisequallylikelytobethecorrectmatchingrule. Consideranyrule rintheruleset.Recallthattreesareorderedbytheirmaximumpriorityfirst. Wedefine j=(r)tobethesmallestpossibleindex jsuchthat pr(r)>pr(Tj);thismeansthat ifristhematchingrule,wewouldnotneedtosearchtree T(r)oranylaterrulesinceallthese ruleshavelowerprioritythan r.Fortree Ti,wedefine (Ti)=rTi((r)−1)/| Ti|;thatis, (Ti)representstheaveragenumberoftreesthatneedtobesearchedwhen Ticontainsthematching rule.Weplot (Ti)inFigure3.7alongwiththebestpossiblevaluesfor Tiwhichis iandtheworst possiblevaluewhichis |T| .Aswecanseefromthisplot,the |Ti|isroughlyboundedby2 i+1forsmall iandthisimprovesforlarger i.Addtothisthefactthatthevastmajorityofourrulesare containedinthefirstfivetrees(seeTable3.1),thenonaverageonlyarelativelysmallnumberof treesaresearchedforanysuccessfulsearch. Wenowcombinethepropertiesofthegeometricprogressionandthepriorityoptimizationto obtainthefollowingaveragecaseboundonsuccessfulsearches. Lemma3.7.2. Ifasequenceofremainingrules riisa ( )geometricprogressionand (Ticiforsomeconstant c,thentheaveragecasecostofasuccessfulsearchis O(d+logn).35010203040 01020304050 Partition Index by Max Priority Number Partition Search Worst−case 2i+1 BoundWith Priority i BoundFigure3.7:Plotof (Ti)forourACL,FW,andIPC64krulesets.Theworst-caseisthemaxmimum numberofpartitionsoverallrulesetsofsize64k.Theaverageexcludesmissingvalues. Proof. Wefirstobservethatthegeometricprogressionofremainingrulescanbeviewedasa sequenceofnumberofrulesintreeswherethesizeofeachsuccessivetreedecreasesbyafactor of1 /.Second,foralltherulesintree Ti,(Ti)istheaveragenumberoftreesthatneedstobe searchedandissimplysomeconstant ctimestheindex i;thisaverageassumesthateachruleis equallylikelytobehit.Puttingthesetwoobservationstogether,wegetthattheaveragenumberof treessearchedis c(1−1/)|T| i=11/i−1whichisaconstantin cand.Thesearchcostinanytree isO(d+logn),sotheresultfollows. 3.8RuleSplitting Weproposearulesplittingoptimizationwherewespeedupclassificationtimebycreating fewertrees.Specifically,wesplitsomeoftherulesintomultiplepiecesthataremorecompatible witheachother.Theresultisanewsemanticallyequivalentrulelistthatcanberepresentedusing fewertrees.Sincethenumberoftreesismoreimportantthanthenumberofrules,thiswillusually reducethesearchtimerequired. Forexample,considertherulesinFigure3.2.InYXorder,only r1,r3,and r4arecompatible. 36r1r2r3r4r573153517911XYr5r2Figure3.8:SplittingtherulesfromFigure3.2inYXorder. Ifwecut r2atY=5and r5atY=3asshowninFigure3.8,thenalloftherulesarecompatible. Theresultingtreewouldcontain7rules. RulesplittingissimilartotherulereplicationthatoccursinHyperCutsandotherdecisiontrees wherearuleisreplicatedintomultiplebranches.PartitionSorthasanadvantagethatitcanadjust thenumberoftreesandwhichrulesareassociatedwiththeminordertocontroltheamountof splittingthatoccurs.OthermethodslikeHyperCutsmustdosplittingbecausealloftherulesare placedinthesametree.Thesemethodstendtohaveveryhighmemorycostsastheyareforcedto resolveessentialruleincompatibilities.SomemethodssuchasandSmartSplitdosome separationtocontrolreplication,buttheircontrolislessrefined.Weacontinuumof betweenthenumberoftrees,theirheight,andtheamountofmemoryrequired(viareplicationor splitting).3.8.1Splitting WenowdescribehowPartitionSortbuildsatreethatincludessplitrules.First,weselectacoreset ofrules CandtheirfieldorderusingGrInd.Thisformsthebasisforourtree.Otherruleswillbe selected,split,andaddedtothislist. Fromtheremainingrules,weselectthecore-compatiblerules:therulesthatdonotrequire splittinganyrulein C.Wethencomputehowmucheachoftheseruleswouldneedtobesplitin 37ordertoaddthemtotherulelist.Wethensortthembythenumberofsplitsrequired.Wethentake rulesuntilthenumberofsplitsrequiredpassessomethresholdandrejecttheremainingrules.We thensplitthenewrulelistcontainingthecoresetandtheacceptedrules. UsingtherulesinFigure3.2,ourcoresetofrulesis r1,r3,and r4inYXorder.Weconsider addingrules r2andr5.Bothrulesarecore-compatibleandeachonlyneedstobesplitintotworules tobeacceptable.Aslongasourlimitisatleast7rules,wesplitrules r2andr5asshowninFigure 3.8andplacealloftherulesintoasingletree. Ifourcoresetwasinstead r2,r3andr4thenr1wouldnotbecore-compatible.Thatisbecause thiswouldrequiresplitting r2,whichisnotallowedbyourmethod. 3.8.2DeterminingCore-Compatibility Wemustbeabletodetermineifrule riscore-compatiblewithacoresetofrules, Cgivenfieldorder f.Wedothisbycomparing rtoeach riC.Firstconsiderfield f0.If r[f0]isdisjointfrom ri[f0],thentherulesarecompatible.Otherwise,if low(r[f0])>low(ri[fo])orhigh(r[f0])I(v).Inthefirstandthirdcase,we gototheleftorrightchild,respectively.Inthesecondcasewhere qI(v),weproceedtothe thirdpointerwhichpointstoanembeddedRITthatcontainsalltherealintervalsspannedby I(v).Forarealnode,thesecondcasemeanswehavefoundamatchandweeitherreturnthematching boxorusethethirdpointertoproceedtothenextfield.Toillustrate,considerFigure4.1 (e).The spanningnodesaredenotedasrednodes.Eachspanningnode’sthirdpointer,denotedwithared arrow,pointstoanotherRIT. 564.2.2RITProperties RITssatisfytwoinvariants.Thefirstinvariant IV1isthatanyroot-to-leafpathhasmonotonically increasingrankwithatmosttwonodes(spanningorrealnodes)ofthesamerank.Thesecond invariant IV2isthattwoconsecutivenodes vandparent (v)havethesamerankifandonlyif parent 2(v)isadirectspanningnodeof v,parent (v).WenowprovethekeypropertyofRITs. Lemma4.2.2. Thedepthofanyrank knodeinaRITisatmost 2k+1.Proof. Byinvariant IV1,ifwefollowanypathin Tfromtherootnode rtoanynode vofrank k,theranksofthenodesonthepatharemonotonicallyincreasingandweencounteratmosttwo nodesofrank kfor1 kk.Thereisatmostonerank0nodeinanyRIT.Thus,thetotallength ofthepathisatmost2 k+1.Thisleadstothefollowingtheorem. Theorem4.2.1. Considera d-dimensionalkeys Jandquerypoint q.Let TbeanRITfor J.The worstcasesearchtimeforquery qinTis2log n+3dwhichis (d+logn).Proof. WeassumewithoutlossofgeneralitythatwereachtheRITforfield dduringoursearchfor q.Let vibethefinalnodevisitedinfield fiandki=rank (vi)for1 id.Let T(n,d)denotethetotalnumberofnodesvisitedin Tgivenwehave ntotalboxesremainingand dtotalfields includingthecurrentfieldremaning.Then T(n,d)isthequantitywewishtocompute. Wecanboundthenumberofelementsofnodeofrank kbyn/2k−1usingProposition4.2.2. WethenapplyLemma4.2.2 dtimestogetthefollowinginequalities. T(n,d2k1+1+T(n/2k1−1,d−1);k1lognT(n/2k1−1,d−12k2+1+T(n/2k1+k2−2,d−2);k2log(n/2k1−1)T(n/2k1+k2−2,d−22k3+1+T(n/2k1+k2+k3−3,d−3);k3log(n/2k1+k2−2)...T(n/2d−1iki−d+1,12kd+1;kdlog(n/2d−1iki−d+1)57Substitutingeachtermintothefirstequationyields T(n,d2(diki)+d.Theresultfollowsfrom kdlog(n/2d−1iki−d+1)=logn−log(2d−1i=1ki−d+1)=logn−(d−1i=1ki−d+1)whichimplies dikilogn+d.4.2.3RITConstruction WedescribehowtoconstructaRITandshowthattheconstructionmethodmaintainstheinvariants. Weworkwiththesetofrealintervals Idefinedabove.Wefirstdescribehowweconvert Iintoa setofrealintervalsandspanningintervals.Westartfrom k=logn.Wefindtheleftmostpairof k-adjacentintervals iaandibtoformaspanninginterval,replacingalltheenclosedintervalsby thisspanninginterval I(a,b).Wedefine span (I(a,b))tobethesetofintervalsreplacedbyspanning interval I(a,b);forlatervaluesof k,span (I(a,b))mayincludeaspanninginterval I(c,d).Inthis case,I(c,dspan (I(a,b)),butintervalswithin span (I(c,d))arenotin span (I(a,b)).Bythe definitionofrankandthedefinitionof c(i)foraspanninginterval,thenewspanninginterval I(a,b)hasarank k−1sincewecombinetwonodesofrank k.Wecontinueuntilthereareno k-adjacentintervalsremaining.Wethendecrement kandrepeattheprocessuntil k=0.[4] [4] [4] [1] [6] [4] [6][4] [4] [5] [5] [1] [6 ] [5] [6] [5] [6] [4] [3][1] [6] [4] [6] [5] [5] [5] [6] [5][5] [5] [4] [4][5] [6] [5]Rank interval tree (a)(b)(c)(d)(e)[4] [3] [1] [6] [4] [6][5] [5] [4] [4][5] [6] [5] [0]01344445555666Third pointer Left/right child pointers Figure4.1:AnexampleofRITconstruction. WenowconvertthissetofintervalsintoaRIT T.Wecreateanodeforeachinterval:areal 58nodeforrealintervalsandaspanningnodeforspanningintervals.Byourconstruction,wedonot haveany k-adjacentintervalsforany k0.Weformabinarysearchtreebyinsertingthenodes intothetreeinorderofrankstartingwiththelowestranknode.Ifallnodesarerealnodes,weare done.Foranyspanningnodes v,werecursivelyapplythesameoperationformaRIT T(span (v))forthenodesin span (v)andwehavethethirdpointerof vpointtotherootof T(span (v)).The thirdpointerofallrealnodes vpointstotherootnodeofaRITcreatedforthe nboxeswhose currentfieldin fmatches I(v)usingthenextfieldin f.WeillustratetheconstructionofaRITinFigure4.1.Westartwiththetenuniqueandsorted intervalsdepictedinFigure4.1(a)whereaninterval [k]hasrank k.Intervalsinblackarereal intervals;intervalsinredarespanningintervals.Weusenodeandintervalinterchangeably.We startwiththelowestrank6,butthereareno6-adjacentintervals.Forrank5,therearetwopairs of5-adjacentintervalsasdenotedintheredrectangles.Figure4.1(b)showsthetworesulting spanningintervalsofrank4andintervalsreplacedbythespanningintervals.Thereisonepairof 4-adjacentintervalswhichisdenotedbytheredrectangleinFigure4.1(b).Figure4.1(c)shows theresultingspanningintervalofrank3andthetwointervalsreplacedbythespanningintervals. Wethenfindtherearenomore k-adjacentintervalsforanyvalueof k,sowecreateafinalspanning intervalofrank0asdepictedinFigure4.1(d).Finally,infigure4.1(e),weshowtheresulting RITwhererealnodesaredenotedinblack,spanningnodesaredenotedinred,thethirdpointerof spanningnodesaredenotedwithredarrows,andthenumberinsideeachnodeisitsrank. Weshowthatafterconstructionthetreehasinvariants. Lemma4.2.3. TheRITsatisfiestheinvariants IV1andIV2afterstaticconstruction. Proof. First,inaRIT T,ifnode pistheparentofnode vandpointsto vusingthethirdpointer, thenrank (v)I(v),weproceedtotherightchildof vandrecurse.If b=I(v)andvisarealnode,we incrementc(v)andfollowthethirdpointertothenextfieldandrecurse.Wenotetheremustbe somenextfieldsinceweassumethatinsertionispossiblewhichmeansthatatsomefield i,bwillhaveauniqueinterval.If b=I(v)andvisaspanningnode,wefollowthethirdpointerto therootofthe v’ssubtreeandrepeattheprocessrecursively.Ifanullchildisfound,whichmust happeneventually,wecreateanewrealnode vwithc(v)=1,andwecreatesingletonnodetrees inthesubsequentfieldswhichdonotrequirepathrepairsince c(v)=1.Thiscompletesthesimple insertionphasewhichclearlyrunsin O(d+logn)timegiventhisisessentiallyidenticaltosearch. 61Wenowproceedtopathrepair.Wefocusonaspecificfield i.Let bdenotefi(b),TbetheRIT thatwesearchedinfield iwheninserting b,andlet vbethenodethatwasmodifiedin Tbythe insertionof v.Notethat viseitheranewnodewith c(v)=1or visanexistingnodewherewe incrementedc(v)byone.Weuse c(v)todenotetheoldvalueof c(v)includingdenoting c(v)tobe 0if visanewnode.Lettheroot-to-leafpath Pbethepathfrom r,therootof T,to v.Aftersimple insertion,thefollowingistrue:invariants IV1andIV2holdeverywherein Texceptforapossible violationbetween vandparent (v)sincec(v)increasedby1or vwascreatedwith c(v)=1which meansrank (v)mayhavechangedbyexactly1. Inpathrepair,thiswillbeoursteadystate.Specifically,invariants IV1andIV2willhold everywherein Texceptforapossibleviolationbetweenaspecifiednode vandparent (v)dueto rank (v)possiblydecreasingby1.Wewillrepairthepotentialviolationbetween vandp(v)insuch awaythatinvariants IV1andIV2willstillholdeverywherein Texceptforapossibleviolation betweenanewnode vandparent (v)wherevissomenodeabove vonP.Notethat vmaynot haveoriginallybeenon P.Therearesomecaseswherenopathrepairisneeded.First,if logc(v=logc(v,no repairisneededasnode v’srankhasnotchanged.Thisalsoimpliesthattherankofanyspanning nodeson Phavenotchangedastheycanonlychangerankifsomenodeon Pchangesrank. Thus,wearedone.Asecondcasewherenopathrepairisneededisif logc(v>logc(vbutlogc(vlogc(v.Weaddresscase(1)usingthefollowingmergeoperationdepictedinFigure4.3.Weformanew spanningnode vwithrank k−1bymerging vandparent (v).Thisnewspanningnode vtakesthe placeof parent (v)onPwherewesettheleftchildpointerof vtopointtotherootofsubtree A.Wenotethereisasymmetriccasewhere vistherightchildof parent (v),andasymmetricmerge 62operationhandlesthatcase. k +1 k k A B C v v k +1 k k-1 A C B k v has no left or right sibling New spanning node v’ Figure4.3:MergeOperation. Lemma4.3.1. Iftheonlyviolationof IV1andIV2occursatnode vwhere vhasnoleftorright siblingand rank (v)=rank (parent (v)),wecaneliminatethisviolationmerging vandparent (v).Afterthemergeandreplacing parent (v)withthenewspanningnode v,theonlypossibleviolation ofIV1andIV2inTcanoccurbetween vandparent (v).Proof. Ifweassumethat IV1andIV2holdfor Tbefore rank (v)decreasesby1from k+1to k,thenitfollowsimmediatelythat IV1andIV2holdforthesubtreerootedat v.Furthermore,theonly possibleviolationof IV1andIV2occursbetween vandparent (v)sincerank (v)=k−1whereas rank (parent (v))=kandvhasreplaced parent (v).Weaddresscase(2)asfollows. Lemma4.3.2. Iftheonlyviolationof IV1andIV2occursatnode vwhere vhasaleftorsibling andlogc(v>logc(v,wecanfixtheviolationbetween vandparent (v)andadvancethe nextpointoftheviolation qstepswhere q1doingO(q)work. Proof. ThesituationmustlooklikethatofFigure4.2orthesymmetricvariantwhere wisthe childof spratherthan wandvmustbe worw.Webreakcase(2)intoseveralcases.Thesimplest isif visw.Wefixthisbyasimplerotationmaking wthechildof spandwtheleftchildof w63andrBtherightchildof w.Thisbringsustothesymmetriccaseof v=w.Wehaveadvancedthe pointofviolationby1stepdoingconstantwork,sothiscaseiscomplete. k +1 k A C B k+1 k k +1 k A B C k+1 Parent(v) has no left sibling v v Parent(v) replaced by v w’ Figure4.4:Fixingcase2.1:Replace parent (v)withvWenowconsiderthecasewhere v=w.Webreakthiscaseintotwosubcases.Incase(2.1), parent (v)hasnoleftorrightsibling.Wethenfixtheviolationusingthefollowingstepsasdepicted inFigure4.4.Wereplace parent (v)withvandperformappropriatepointerrewiring.Namely,we setv’sleftchildtobe parent (v)’sleftchild,andwesettherightchildof wtobe root (C).Note thatsince wwas v’srightsibling,itdidnothavearightchildbefore.Furthermore,inthiscase,we actuallyendthepathrepairas vhastaken parent (v)’splaceon Pwiththesamerankas parent (v),soIV1andIV2mustholdthroughout T.Wehaveeliminatedallviolationsdoingonlyconstant work,sothiscaseiscomplete. Incase(2.2), parent (v)hasaleftorrightsibling.Withoutlossofgenerality,wemayassume thatthesituationisasdepictedinFigure4.5(a)or(b).Ifnot,wesimplyperformonerotation between sp=parent (v)andsp’ssiblingtomake spthedirectchildofitsspanningnode.Wenote therearethesymmetriccaseswhere sphasaleftsiblingandaspanningnodeparent. IftheconfigurationisthatdepictedinFigure4.5(a),wereplace spwithvbreakingapart vandw.Wethenmake ythenewrightchildof v,merge yandv,andmake sp2theresultingspanning node.Notethatbecause wwas v’srightsibling, I(w)liesbetween I(v)andI(y)whichmeans thatI(sp2)isbythesechanges.Wethendosomepointermanipulation.Specifically,we 64k +1 k C B k+1 k v k k-1 k +1 k C B k+1 k v k k-1 (a) (b) sp sp2 w’ w’ y y sp2 sp Figure4.5:Case(2.2):If sphasarightsiblingandaspanningnodeparent. make root (C)therightchildof wandwemake wtheleftchildof y.Theonlypossibleissueisif root (C)hasrank k+1inwhichcase root (C)andwviolatetheinvariants.Inthiscase,wemerge root (C)withw,andthenwemergethenewspanningnode vthathasrank kwithy.Finallywe rotatethissecondnewspanningnodethathasrank k−1with vtomakethisnewspanningnode thedirectchildof sp2.Thisreturnsustocase(2)wherethisnewspanningnodeisthenew vandsp2isthenew parent (v).Notethatif root (c)hasrankstrictlygreaterthan k+1,noadditional workwouldberequiredandtree Twouldnowsatisfyinvariants IV1andIV2.Inthiscase,wehave advancedthepointofviolationbyatleastonestepwhiledoingconstantwork. ThefinalcasewemustdealwithisiftheconfigurationisthatdepictedinFigure4.5(b).This isthemostinvolvedcase.Similartocase(2.2a),weagainreplace spwithvbreakingapart vandw.Wethenmake ythenewrightchildof v,merge yandv,andmake sp2theresultingspanning node.However,unlikecase(2.2a), I(w)issmallerthan I(v)whichmeansthat I(sp2)nolonger containsI(w).Weneedtofindaplacetoreinsert wintoTthatlies“totheleft”of sp2.Weillustratehowwefindtheplacetoreinsert winFigure4.6.Weworkourwayup Pstarting withsp2whichhasrank k−1untilwefindanode xthatdoesnothavearightsibling.Notethatwe musteventuallyfindsuchanodeas root (T)hasnorightsibling.Foreachnode wthatweencounter duringthissearchthatdoeshavearightsibling,weassumewithoutlossofgeneralitythat w’sparentisthespanningnodeformedbymerging wandw’srightsibling.Thecrucialobservationis 65k +1 k C0 B k+1 k v k k-1 k-1 . . . C k-q x does not have a right sibling k+1 A1 k+2 L R . . . A k +1 k C0 B k+1 v k k-1 k-1 . . . C k-q A k+1 A1 k+2 L R . . . w’ x w’ vp Update min Find first node z of rank k+1 of right spine of T(x’) Possibly merge up toward root x’ z z vp x Figure4.6:Fixingcase(2.2b).Notethat q1.thatif whasarightsibling,then w’sleftchildpointermustbenull.Weupdatemin (I(w))tobe min(I(v)).Whenwefindthis x,itcouldbethecasethat xhasaleftsiblingor xisnotaspanning node.Lettherankof xbek−qwhereq1.Regardlessofwhichcaseappliesfor x,thecrucialobservationisthattheleftchildpointerof xnolongerneedstobenull.If x’sleftchildpointerisnull,wesimplyset wtobetheleftchildof xandwearedone.Tree Thasnoviolationsofanyinvariant.If x’sleftchildpointerisnotnull,let xdenotetheleftchildof x.Wethenfindtheplacetoinsert wbysearchingintherightspineof thesubtreerootedat x.Weproceeduntilwefindanode zwithrankgreaterthan k+1orwefind theendoftherightspineof T(x),whichevercomesfirst.Let vpbetheparentof zorthelastnode ontherightspineof x;note xcouldbe vp.Wethenreset vp’spointertopointto winsteadof z.Ifwefoundanode z,wethensettheleftchildpointerof wtopointto zasshowninFigure4.6. Finally,if vphasrank k+1,wethenhaveaninvariantviolationbetween wandvp.However, thecrucialobservationisthatallthenodesontherightspineof T(x)havenoleftorrightsiblings bydefinitionoftherightspinesincewenevertraverseathirdpointer.Weresolvetheinvariant between wandvpbymerging wandvp.Thismayleadtoanotherinvariantviolationbetweenthe resultingspanningnode vandtheparentof vp.Becauseofourcrucialobservation,wecanresolve 66thisandanyfutureviolationsbyrepeatedlymergingthenodesuntilweeventuallymergewith x.Ifxistheleftsiblingof x,thenwehavereturnedtocase(2)wherethisnewnodethatreplaces xisvandisinviolationwithitsparent xwhichisalsoitsrightsibling.Thecrucialobservationis thatwehaveadvancedthepointofviolationatleast qlevelswhiledoing O(q)work.Insummary, wehaveshownthatwecanhandleallsubcaseswithincase(2)whereweadvanceatleast qsteps towards root (T)whiledoingatmost O(q)work. Theorem4.3.1. Insertinga d-dimensionalkey bintoaRITmaintaining IV1andIV2canbedone inO(d+logn)time.Proof. Weobservethesimpleinsertionphasetakesatmost O(d+logn)timeresultinginatmost oneviolationperRITperfield.Ifthenodeisatrank kintree Tinfield i,thenLemmas 4.3.1and4.3.2implythatthepathrepairphasetakesatmost O(k)workfortree T.Giventhisis proportionaltothesearchtimeintree T,thisimpliesthetotalpathrepairtimeis O(d+logn)andtheresultfollows. 4.3.2Deletionin O(d+logn)timeBeforewestart,wefirstintroducearankrotationoperationthatwewillneedforsomecasesduring pathrepair.Rankrotationisabasicleftorrighttreerotationpossiblyfollowedbytwomerges. ConsiderFigure4.7(anditssymmetriccounterpart).Assumethatsubtrees A,B,and CsatisfyIV1andIV2andtheirrootshaveranks k,kandk+1,respectively.Weperformbasictreerotation fornode vandv.Let rbbearootnodeofsubtree B.If rank (rb)>k,wearedonesincesubtree rootedat vafterrotationsatisfies IV1andIV2.Otherwise, rank (rb)=k.Inthiscase,wemerge rbandvtoobtainanewspanningnode spofrank k−1thatreplaces v.Next,weperformanother mergebetween spandvtoobtainanothernewspanningnode spofrank k−2thatreplaces v.Thesubtreerootedat vspnowsatisfies IV1andIV2.Thenetresultisthatwefixtheviolation between vanditsleftchildwherethenewnodeinthepositionof vmayhavearankthatis1or2 smaller. 67k B k B A A C C v v k-1 v’ k-1 v’ A k-2 sp’ B’ Merge if rank( rb)= k Rotate Figure4.7:RankRotationoperation. Weassumethatwearedeletingakey b.Weseparatedeletionintotwophases:simpledeletion andpathrepair.Inthesimpledeletionphase,wefirstsearchfor bintheRIT.Ifweareprocessing fieldi,whenwecometonode v,wecompare bwithI(v)(weagaindrop fi).If bI(v),weproceedtotherightchildof vandrecurse.If b=I(v)andvisarealnode,wemaintainapointerto c(v)andfollowthethirdpointertothenext fieldandrecurse.If b=I(v)andvisaspanningnode,wefollowthethirdpointertotherootofthe v’ssubtreeandrepeattheprocessrecursively.Ifanullchildisfound,thismeansthesearchfailed andnodeletionoccurs.Ifbox bisfound,wethendecrement c(v)ineachfinalnodeforeachfield andproceedtopathrepairineachtree.Notethatinatleastthe dthfield, c(v)mustbe0.If c(v)=0,wemustdelete vfromthetreecompletely,butwedelaythisdeletiontothepathrepairstage.This completesthesimpledeletionphasewhichclearlyrunsin O(d+logn)timegiventhisisessentially identicaltosearch. Wenowproceedtopathrepair.Wefocusonaspecificfield i.Let bdenotefi(b),Tbethe RITthatwesearchedinfield iwhendeleting b,andlet vbethenodethatwasmodifiedin Tbythedeletionof v.Weuse c(v)todenotetheoldvalueof c(v).Lettheroot-to-leafpath Pbethe pathfrom r,therootof T,to v.Aftersimpledeletion,thefollowingistrue:invariants IV1andIV2holdeverywherein Texceptforthefollowingpossibleviolations.Case(1):if vhasnoleftorright sibling,wemayhaveaviolationbetween vandeitherorbothofitsbinarysearchtreechildrensince c(v)decreasedby1.Case(2):if vhasaleftorrightsibling,wemayhaveaviolationbetween vanditssiblingandtheirspanningnodeparentif rank (v)nolongermatchestherankofitssibling.We alsonotethatif c(v)=0,wedoneedtodeletenode vcompletely.Inthiscase,wecanonlyhave 68thesecondtypeofviolationasanodewith c(v)=1willhavenochildrenotherthanaleftorright sibling.Aswithinsertion,therearesomecaseswherenopathrepairisneeded.First,if logc(v=logc(v,norepairisneededasnode v’srankhasnotchanged.Thisalsoimpliesthattherankof anyspanningnodeson Phavenotchangedastheycanonlychangerankifsomenodeon Pchanges rank.Thus,wearedone.Asecondcasewherenopathrepairisneededisif logc(vlogc(child (vforbothpossiblechildrenof v.Inthiscase, vhaschangedrank, butitsnewrankisstillstrictlylargerthantherankofitspossiblytwochildren,so IV1andIV2holdforallof T.Thiscasecanonlyoccurif vhasnoleftorrightsibling. Wenowdealwithourtwopossibleinvariantviolations.Wefirstdealwithcase(1)whichturns outtobeaveryeasycase. Lemma4.3.3. Iftheonlyviolationof IV1andIV2occursatnode vwhere vhasnoleftorright siblingand rank (v)=rank (child (v)),wecaneliminatethisviolationbymerging vandchild (v).Afterthemerge,therewillbenoviolationsof IV1andIV2inT.Proof. First,weobserveagainthatthiscasecannotoccurif c(v)=0as vmusthavebeenasingleton nodebeforethedeletionandasingletonnodecannothaveachildthatisnotaleftorrightsibling. Withoutlossofgenerality,weassumethatthechildwithequalrankisitsleftchild lc.Whenwe merge lcandvtoform v,wereplace vwithv.Wemake vpointto vandlcisstilltheleftchild ofv.Wemaketheoldrightchildof v,ifitexists,therightchildof v.Since vwillhavetherank thatvusedtohave,wehaveeliminatedallpossibleinvariantviolations. Wenowdealwiththesecondcasewherewehaveasinglenode vwhoserankhaschangedand vhasasibling. Lemma4.3.4. Iftheonlyviolationof IV1andIV2occursatnode vwhere vhasaleftorsibling andlogc(vk+1or Bisempty,thenwesplitcase(2)intotwosubcasessimilartowhatwe didwithinsertions.Thefirstsubcase(2.1)isthat sphasnoleftorrightsibling.Inthiscase,we splitthemergebetween vandwasillustratedinFigure4.8.Thatis,wepromote wtoreplace spandwemake vtheleftchildof w.Intheprocess,wenowmake rA,therootofsubtree A,theleft childof vandrC,therootofsubtree C,therightchildof w.Thisintermediatestateisillustratedin themiddleofFigure4.8. k k+1 k A B C v v k k+1 A C B k k-1 k k k k k+2 k+2 w sp w k-1, k, k+1 k-1, k y x ? Figure4.8:SplitMergeoperation. Wecouldhaveviolationsbetween rAandvandrCandw.Weaddresstheseasfollowswith theresultillustratedintherightmosttreeofFigure4.8whereweonlyfocusonthenode xwhich ultimatelyreplaces wandthenode ywhichultimatelyreplaces v.Westartwiththerelationship between wandrCandtheresultingnode x.If rank (rC)=k,wemerge rCandwtoformanew spanningnode xwithrank k−1.Otherwise,thereisnoviolationbetween wandrCandxisjust wwithrank k−1.Thus,node xhasrank k−1or k.Wenowconsider rAandvandtheresultingnode y.If rank (rAk+2,thereisnoviolation andyisjust vwithrank k+1.If rank (rA)=k+1,wemerge rAandvtomakearank kspanning70nodey.Thelastpossibilityisthat rank (rA)=k.Inthiscase,weneedtoperformarankrotation operationbetween rAandv.Thisresultsinnode yhavingrank kork−1.Consideringallthe possibilities,node yhasrank k−1,k,or k+1.Wenowconsiderthepossibilitiesbetweennode yandnode x.Wemayneedtomerge yandxiftheysharethesamerankresultinginarootnodewithrank k−2or k−1.Wemayhaveto performarankrotationbetween yandxresultinginarootnodewithrank k−2or k−1.Finally, wemaynotneedtodoanythingresultinginarootnodewithrank k−1or k.Thus,therootnode willhaverank k,k−1,or k−2.Iftherootnodehasrank k−1or k,wearedoneasweinitiallyassumedthat sphadnoleftor rightsiblingandwehavenotdecreasedtherankofthissubtree.Thus,noinvariantsareviolated andthiscaseiscomplete.Iftherootnodehasrank k−2,wereturntothecaseofinsertionpath repairaswehaveactuallydecreasedtherankofthisnode,andweleverageourinsertionpathrepair resultstocompletethiscase.Thus,subcase(2.1)iscomplete. k+1k+2 C B k+1 k v k k-1 (a) (b) sp k+1k+2 C B k+1 k v k k-1 sp sp2 sp2 w w Figure4.9:Case(2.2):If sphasarightsibling. Wenowconsidersubcase(2.2)where sphasaleftorrightsibling.Similartoinsertion,we considertwosubcasesillustratedbyFigure4.9.Theotherpossibilitiesaresymmetrictothesecases andsothesameanalysisappliestothem.Forsubcase(2.2a),depictedinFigure4.9(a),wereplace spwithwandmovesubtree Ctobetherightchildof v.Weconsiderthestructureofsubtree C.Let 71Chained merges sp sp2 B C D k+1 k+2 k+1 k k-1 x has no right sibling x . . . Figure4.10:AlternaterepresentationofFigure4.9(b). rCbetherootofsubtree C.If rank (rC)>k+2or rCdoesnotexist,thenwenowhavemovedthe invariantviolationuponeleveltonode w.Thiscompletesthiscaseaswehavedone O(1)work. Ifrank (rC)=k+2,wemerge rCandvtomakeanewspanningnode vwithrank k+1to replacev,andthis vcanmergewith wtocreateanewspanningnode xwithrank ktoreplace w.Thiscompletesthiscaseas Tnowsatisfies IV1andIV2.Otherwise, rank (rC)=k+1.Let rLandrRbetherootsoftheleftandrightsubtreesof rC.Wefirstrotate rCwithv.Thismeans rListherightchildof vandapossibleviolation.Wenow merge rCandwtomakeanode vwithrank ktoreplace w.If rank (rL)>k+2,wehaveno violationbetween rLandvandthiscaseiscompleteas Thasnoviolationsof IV1orIV2.Otherwise rank (rL)=k+2,sowemerge rLandvtomakeanewnode zwithrank k+1thatisaleftchild ofrC.Thisreturnsustooneoftheinsertionpathrepairviolationsas zhasthesamerankasits parentrC.Weleverageourinsertionpathrepairresultstocompletethiscase.Thussubcase(2.2a) iscomplete. Nowweconsidersubcase(2.2b)depictedinFigure4.9(b).Thissituationismorecomplicated andissimilartothecomplicatedcasefrominsertion.Westartagainbyreplacing spwithw.If rank (rC)=k+1,thenwemerge rCandwtocreateanewspanningnode vwithrank kthatreplacesw.Thisnowcreatesasituationthatisidenticaltotheinsertioncase(2.2b)fromLemma 4.3.2aswemustinsert vbackinto Tandwemustfindaplacetoperformthisinsertion.Weleverage ourinsertionpathrepairresultstocompletethiscase. Wenowconsiderthecasewhere rank (rC)>k+1.Inthiscase, wdoesnothaverank 72 . . . k+2 L1 L0 R vl L D De-chaining Zone k-1 k k+1 k+2 C B . . . k-q Right spine of T(lx) vj lx Figure4.11:Merge-zipoperation tomaintainthemergebetween spanditsrightsibling.Thus,thisleadstosplittingnotonly spbutalsosp2andpotentiallymorespanningnodes.WeillustratethisrippleinFigure4.10. Wedealwiththiscaseasfollows.WeconvertthechainedmergesinFigure4.10intoabinary searchtree.Thatis,westartfromnode vandwemoveuppath Puntilwefindanode xwithrank k−qthathasnorightsibling;thisissimilartothecaseforinsertion.Alongthispath,webasically replaceeachspanningnodeencounteredwithitsrightsiblingchild.Theresultanttreeisillustrated intheDe-chaniningZoneinFigure4.11.Wenotethattherearenogapsinrankfrom k+2upto k−q−1whichistherightsiblingchildof x.Wenowconsidernode xwhichmayhavealeftsiblingoraleftchild.Thekeypointisthatthe leftchildpointerneednotbenullsince xdoesnothavearightsibling.Weconsidertherightspine ofthesubtreerootedat lx,theleftchildof x.ThisrightspineisalsodepictedinFigure4.11.We notethat rank (lxk−qsinceitmightbealeftsiblingof x.WenowbasicallymergetherightspinewiththeDe-chainingZone.Theremaybegapsinrank intherightspine,buttherearenogapsinrankintheDe-chainingzone. Weprogressupthetwochainsusingpointersasfollows.FortheDe-chainingzone,westart withvjpointingto v,theminimumnodeintheDe-chainingzone.Notethat vjhasanullleftchild pointer.Fortherightspine,weset vltopointtothenodethathasthelargestrankatmost rank (vj).Thus,rank (vlrank (vj)max(r),wereset tomin (r)modeandresetourcurrentrule rtobethenextrule.Wecontinueinthisfashionuntil eitherallpacketsorallrulesarefinished.Whenwemovetothenextsortableruleset,wecontinue inthisfashionexceptwithafewsmallchanges.First,weinitializetheresultarraytobethearray thatcarriesoverfromthepreviousruleset.Wenoteafewpositivefeaturesofthismergeprocess. First,thetotalnumberofcomparisonsisatmost m+2npertreeandthus mT+2nwhereTisthe numberofpartitions.Thiscanbeseenwherewechargeeachcomparisonto pifpissmallerthan theendpointof ritiscomparedtoorto riftheendpointof rissmallerthan p.Eachpacket pischargedatmostonceperpartitionandeachendpointof rischargedatmostonce,sotheresult follows.Second,itfollowsthattheresultingnumberofcomparisonsis O(1)perpacketperpartition aslongasweensurethat m=(n).Finally,similartomergesortandsequentialsearch,thecaching behaviorofthemergeisgoodaspacketsandrulesareaccessedsequentially. Multi-dimensionalBatchPacketProcessing. Wewillinvestigatehowtobatchprocesspackets inthemulti-dimensionalcase.Wefirstnotethatasimpleextensionoftheone-dimensionalalgorithm willnotwork,evenwhenextendingto d=2.Forexample,considerthreepoints P4,P6,and P7andbox R5fromFigure5.2.In XYorder, P6