Scalable Packet ClassificationFlorin BaboescuDept. of Computer Science and EngineeringUniversity of California, San Diego9500 Gilman DriveLa Jolla, CA [email protected] VargheseDept. of Computer Science and EngineeringUniversity of California, San Diego9500 Gilman DriveLa Jolla, CA [email protected] classification is important for applications such asfirewalls, intrusion detection, and differentiated services. Ex-isting algorithms for packet classification reported in the lit-erature scale poorly in either time or space as filter databasesgrow in size. Hardware solutions such as TCAMs do notscale to large classifiers. However, even for large classifiers(say 100,000 rules), any packet is likely to match a few (say10) rules. Our paper seeks to exploit this observation toproduce a scalable packet classification scheme called Ag-gregated Bit Vector (ABV). Our paper takes the bit vectorsearch algorithm (BV) described in [11] (which takes lin-ear time) and adds two new ideas, recursive aggregation ofbit maps and filter rearrangement, to create ABV (whichcan take logarithmic time for many databases). We showthat ABV outperforms BV by an order of magnitude usingsimulations on both industrial firewall databases and syn-thetically generated databases.1. INTRODUCTIONEvery Internet router today can forward entering Internetmessages (packets) based on the destination address. The32 bit IP destination address is looked up in a table whichthen determines the output link on which the packet is sent.However, for a competitive advantage, many routers todaychoose to do additional processing for a specific subset ofpackets. Such additional processing includes providing dif-ferentiated output scheduling (e.g., Voice over IP packetsare routed to a high priority queue), taking security-relatedactions (e.g., dropping packets sent from a certain subnet),load balancing (e.g., routing packets to different servers) anddoing traffic measurement (e.g., measuring traffic betweensubnet pairs).Although the details of the additional processing can varygreatly, a common requirement of all the functions above isthat routers be able to classify packets based on packet head-ers into equivalence classes called flows. A flow is definedby a rule — for example the set of packets whose sourcePermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for pro£t or commercial advantage and that copiesbear this notice and the full citation on the £rst page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior speci£cpermission and/or a fee.SIGCOMM’01, August 27-31, 2001, San Diego, California, USA..Copyright 2001 ACM 1-58113-411-8/01/0008 ...$5.00.address starts with prefix bits S, whose destination addressis D, and which are sent to the server port for web traffic.Associated with each flow is an action which defines the ad-ditional processing — example actions include sending to aspecific queue, dropping the packet, making a copy, etc.Thus packet classification routers have a database of rules,one for each flow type that the router wants to process differ-ently. The rules are explicitly ordered by a network manager(or protocol) that creates the rule database. Thus when apacket arrives at a router, the router must find a rule thatmatches the packet headers; if more than one match is found,the first matching rule is applied.Scalable Packet Classification: This paper is about theproblem of performing scalable packet classification for routersat wire speeds even as rule databases increase in size. For-warding at wire speeds requires forwarding minimum sizedpackets in the time it takes to arrive on a link; this is cru-cial because otherwise one might drop important traffic be-fore the router has a chance to know it is important [11].With Internet usage doubling every 6 months, backbonelink speeds have increased from OC-48 to OC-192 (2.4 to10 Gigabits/second), and speeds up to OC-768 (40 Giga-bits/second) are projected. Even link speeds at the networkedge have increased from Ethernet (10 Mbit/sec) to GigabitEthernet.Further, rule databases are increasing in size. The ini-tial usage of packet classification for security and firewallsgenerally resulted in fairly small databases (e.g., the largestdatabase in a large number of Cisco rule sets studied by [9] isaround 1700). This makes sense because such rules are oftenentered by managers. However, in the very popular Differ-entiated Services [1] proposal, the idea is to have routers atthe edge of the backbone classify packets into a few distinctclasses that are marked by bits in the TOS field of the IPheader. Backbone routers then only look at the TOS field.If, as seems likely, the DiffServ proposal reaches fruition, therule sets for edge routers can grow very large.Similarly, rulesets for edge routers that do load balanc-ing [2] can grow very large. Such rulesets can potentially beinstalled at routers by a protocol; alternately, a router thathandles several thousand subscribers may need to handle say10 rules per subscriber that are manually entered. It maybe that such customer aggregation is the most importantreason for creating large classifiers. Thus, we believe ruledatabases of up to 100,000 rules are of practical interest.1992. PREVIOUS WORKPrevious work in packet classification [11, 15, 9, 16, 10]has shown that the problem is inherently hard. Most prac-tical solutions use linear time [11] to search through allrules sequentially, or use a linear amount of parallelism (e.g.,Ternary-CAMs [4]). Ternary CAMs are Content Address-able Memories that allow wildcard bits. While Ternary-CAMs are very common, such CAMs have smaller densitythan standard memories, dissipate more power, and requiremultiple entries to handle rules that specify ranges. ThusCAM solutions are still expensive for very large rule setsof say 100,000 rules, and are not practical for PC-basedrouters [12]. Solutions based on caching [17] do not appearto work well in practice because of poor hit rates and smallflow durations [14].Another practical solution is provided by a seminal paperthat we refer to as the Lucent bit vector scheme [11]. Theidea is to first search for rules that match each relevant fieldF of the packet header, and to represent the result of thesearch as a