The transformation of the Internet into an important commercial infrastructure has significantly changed consumer expectations in terms of performance, security, and services. Internet Service Providers, while using a shared backbone infrastructure, would like to provide different services to different customers based on different service pricing or based on widely varying customer requirements. For providing this differentiated service, service providers need mechanisms for isolating traffic from different customers, for preventing unauthorized users from accessing specific parts of the network, and for providing customizable performance and bandwidth in accordance with customer expectations and pricing. In addition, service providers need mechanisms that allow routing decisions to be made not just based on destination addresses and the shortest path to it, but also based on contracts between service providers or between a service provider and a customer [14]. Consequently, routers (or packet forwarding engines in general) used in both enterprise and backbone environments should be able to provide network managers with the proper mechanisms that will allow the provisioning of these features.
Forwarding engines must be able to identify the context of packets and must be able to apply the necessary actions so as to satisfy the user requirements. Such actions may be, dropping of unauthorized packets, redirection of packets to proxy servers, special queueing and scheduling actions, or routing decisions based on a criteria other than the destination address. In the paper, we use interchangeably the terms packet filtering or packet classification to denote the mechanisms that support the above functions.
Specifically, the packet filtering mechanisms should parse
a large portion of the packet header, including information on the
transport protocols, before a forwarding decision is made
. The
parsing results in the incoming packet being classified using
a set of rules that have been defined by
network management software or real-time reservation
protocols such as RSVP.
Packet filtering functionality is required for example when a router is placed between an enterprise network and a core backbone network. The router must have the ability to block all unauthorized accesses that are initiated from the public network and are destined to the enterprise network. On the other hand, if accesses are initiated from a remote site of the enterprise network, they can be forwarded into the intra-net and this requires filtering ability. If this level of security is not enough, another policy requirement might be that authorized access attempts from the public network be forwarded to an application level proxy server that will authenticate the access. Clearly, filtering mechanisms are very useful at the edge of an enterprise network. In an edge network node, the router might need to identify the traffic that is initiated from specific customers, and either police it or shape it to meet a predefined contract. Indeed, these are the actions that are required by some of the differentiated services model proposals that are being considered for standardization by the IETF [10].
It is apparent that most filter rules apply to a whole range of addresses, port numbers, or protocols, and not just to single predefined hosts or applications. Aggregation, for instance of addresses, is not only required because customers are usually allocated blocks of addresses, but also because it is necessary to keep the network manageable. Therefore, the specification of the packet classification policies must support aggregations in their definitions. This means that packet classification algorithms must be be able to process rules that define combinations of ranges of values. If the algorithms can only handle exact values and do not support aggregation, preprocessing is required to translate the ranges to exact values. This is infeasible since ranges can grow exponentially with length of the packet field on which the ranges are defined.
Another trend worth noting is that even though packet filtering was thought of as a necessary tool only at the network access points, and mainly for firewall or security applications, it is becoming apparent that it is a valuable tool for performing traffic engineering and meeting the new requirements of the commercial Internet. Filtering policies that use the full information of the packet header can be defined for distributing the available system or network resources. The main consequence of these new uses is that all packet classification actions must be performed at wire-speed, i.e., the forwarding engines must have enough processing power to be able to process every arriving packet without queueing since without header processing it is not possible to differentiate packets to provide differentiated services.
The main contributions of this paper are algorithms that use multi-dimensional range matching that enable Gigabit routers to provide wire-speed packet filtering and classification in a traffic independent manner (i.e. we do not rely on traffic dependent caching or average case results to achieve fast execution times). To our knowledge, our proposed schemes are the first schemes that allow thousands of filter rules to be processed at speeds of millions of packets per second with range matches on 5 or more packet fields in a traffic independent manner. Specifically, we present three algorithms: The first algorithm takes advantage of bit-level parallelism which combined with very elementary bit-operations results in a scheme that supports a large number of filter rules. The second algorithm extends the performance of the first algorithm by making efficient use of both on-chip and off-chip memory. It provides a means for balancing the the time-space tradeoff in implementation, and allows it to be optimized for a particular system taking into account the available time for packet processing, the available memory, and the number of filter rules to be processed. Furthermore, the algorithm allows on-chip memory to be used efficiently and in a traffic independent manner for reducing worst-case execution time. This is unlike typical caching schemes which are heavily traffic dependent and only improve average case performance. The performance metric for all our schemes is worst-case execution time, simple operations to make it amenable to hardware implementation if necessary, and space requirements which are feasible with current memory technology and costs. Indeed, the implementation simplicity, scalability and performance of our filtering have been demonstrated in a prototype router, which can process 1K aggregate rules at a million packets per second []
Our third algorithm considers the special case of filter rules on two fields. This is motivated by important applications such look-ups for multicast traffic forwarding and policy-based routing. To elaborate on this example, when a forwarding engine supports a multicast protocol like PIM (sparse mode or dense mode) [13] or DVMRP [26], the forwarding decision has to be made on both the source address value and the multicast group value. Depending on the protocol, the forwarding engine may have a forwarding entry for a given group value irrespective of source addresses, and also have forwarding entries for a given group value and source subnet. Given the increasing importance of multicast forwarding in the Internet, it would be ideal if a simple algorithm could be used for making multicast forwarding decisions. Since the search for the source addresses may use the same forwarding information base as that used for unicast routing, the same type of CIDR (Classless Inter-Domain Routing) aggregations [15] are likely to be used. CIDR aggregations introduced the notion of prefix in the definition of routing entries. In other words an entry in the forwarding base is defined as a value and a mask. The mask defines the number of bits of the destination address of a packet that can be ignored when trying to match the destination address of the packet to the particular entry of the forwarding base.The bits that can be masked-out are always in the less significant portion of the address. Thus, the values in the forwarding engines can thought as prefixes. For the case of IPv4, prefixes can have a length between 1 and 32 bits. We present a linear space, O(prefix length) scheme which can be used to implement 2-dimensional lookups at rates of millions of packets per second for more than 128K entries in the forwarding table. Considering that multicast forwarding tables in the core backbone might include several hundreds of thousands of entries, even a solution that uses space with a moderate constant or time may not be feasible when the number of entries n is that high.