Telecommunication Laboratories

In next generation networks (NGNs), packet classification is important in fulfill-ing the requirements of multimedia services. Using pre-defined filters, the incoming pack-ets can be categorized that determines to which forwarding class a packet belongs. Packet classification is essentially a problem of multidimensional range matching. The tuple space search is a well-known solution based on multiple hash accesses for various filter length combinations. The tuple-based algorithm, a tuple pruning search, performs well in the practical environment; however, the worst-case speed is not guaranteed. An-other scheme, a rectangle search, could pro-vide good time complexity, but it suffers from the memory-explosion problem. In this work, we explore the relative property of filters and reorganize the filters through filter projection. The proposed scheme could improve the lookup speed of tuple pruning without any extra storage. We evaluate the proposed scheme with both real world and synthetic filter databases. The experimental results show that the proposed scheme increases the lookup speed by a factor of two