Packet filter method and apparatus employing reduced memory

Abstract

A packet filter method and apparatus for a router employs an algorithm that decomposes a set of n filter rules of a k-dimensional space into sets of rule segments associated with non-overlapping intervals in each dimension. Such packet filter may be employed for layer four switching applications. Bit-parallel processing may be employed to compare each interval with corresponding fields of a packet received by the router. Bitmaps defined by the sets of rule segments, and so related to the corresponding filter rules are associated with the intervals. The interval bitmaps are combined to form a filter rule bitmap that identifies and associates one or more filter rules with the packet. For a case storing complete bitmaps for all intervals, the packet filter employs k*n2+O(n) bits of memory for each dimension, [log(2n)]+1 comparisons per dimension which may be performed in parallel, and [n/w] memory accesses for a pairwise combining operation, where w is a width of a bitmap used to identify the filter rule. Incremental memory read operations are employed to reduce memory space requirements of this packet filter case, allowing the packet-filter operation to be optimized in accordance with time complexity and memory space. Since a dominant contributing factor of execution time is off-chip memory accesses, availability of on-chip memory and the use of modified bitmap storage using interval bitmap pointers for incremental memory read operations significantly increases the number of filter rules that may be searched and applied within a given time constraint. For this algorithm employing incremental memory read operations, memory requirements may be reduced to O(n log n) bits while increasing the execution time by only a constant value, when log n≦w.

Dependencies are inferred from the claim text.