Ordered lookup with bypass matching for scalable per-flow classification in layer 4 routers

In order to provide different service treatments to individual or aggregate d hows, layer 4 routers in Integrated Services networks need to classify pa ckets into different queues. The classification module of layer 4 routers m ust be fast enough to support gigabit links at a rate of millions of packet s per second. In this work, we present a new software method OLBM to lookup multiple fields of a packet, in a dynamically pre-defined order, against t he classification database. This algorithm also uses a technique called byp ass matching and can classify packets at a rate of well over one million pa ckets per second while scaling to support more than 300k flows. Complexity analysis and experiment measurements are also presented in this study. (C) 2001 Elsevier Science B.V. All rights reserved.