Algorithms for fast packet classification

The rapid growth of the Internet brings with it great challenges and complex issues in deploying high-speed networks. The number of users, the volume of traffic and the types of services to be provided are continually increasing. Services like QoS and security guarantees are in more demand. They require a finer discrimination of packets based on fields other than the destination that we call packet classification.; A classifier consists of a set of rules for classifying packets based on several header fields. Because core routers can have fairly large (e.g. 2,000 rules) classifiers and must use limited SRAM to meet OC −768 speeds, they can not use the best existing classification algorithms (RFC, HiCuts, BV). Thus the general belief is that hardware solutions like CAMs are needed, despite the amount of board area and power they consume.; In this thesis, we propose algorithmic solutions for packet classification as an alternative to CAMs.; A first contribution of this dissertation takes a bit vector search algorithm described in [24] and adds two new ideas: recursive aggregation of bit maps and filter rearrangement to create ABV, a scheme which may take logarithmic time for many databases.; A second contribution addresses the problem of packet classification in core routers that are used by Tier-1 ISPs. We start by snaking a new contribution in characterizing the features of core router databases. We notice that any packet can be matched by at most a small number of rules in the databases even if we consider only two fields for classification . Using this observation we create a new algorithm Extended Grid of Trie with Path Compression (EGT-PC) which has better performance results than the state of the art algorithm for multi dimensional packet classification HiCuts [19, 20].; Another contribution concentrates on the problem of efficient rule management in a classifier: detecting conflicts between the rules as well as allowing incremental updates at a speed that may be on a order of magnitude of the speed of the classification process. We provide a solution which slightly increases the time of a search but allows fast updates and fast conflict detection between rules.