Packet filter method and apparatus employing reduced memory

• US 6,289,013 B1
• Filed: 09/02/1998
• Issued: 09/11/2001
• Est. Priority Date: 02/09/1998
• Status: Expired due to Term

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Stiliadis, Dimitrios, Lakshman, T. V.
• Primary Examiner(s): NGO, RICKY QUOC
• Application Number:
  US09/145,433
• Time in Patent Office: 1,105 Days
• Field of Search: 370/252, 370/389, 370/400, 370/401, 370/411, 370/412, 713/153, 713/154, 713/201, 713/200
• US Class Current: 370/389
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

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*n²+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.

Claims

1. Apparatus for associating a multi-dimensional filter rule with a packet having two or more fields corresponding to two or more dimensions, the multi-dimensional filter rule to be applied to the packet by a router in a communications network, the apparatus comprising:

a storage medium storing a plurality of intervals for each dimension, each interval having a corresponding interval vector; and

a classification processor comprising

i) a comparator adapted to compare each field of the packet with the plurality of intervals to identify an interval in each dimension based on the value of a corresponding field of the packet;

ii) a memory access module adapted to generate an interval vector for each interval identified by the comparator, wherein at least one interval vector is formed from a stored interval vector and a stored difference vector associated with the corresponding interval; and

iii) a logic operator adapted to combine the generated interval vectors to generate a filter-rule vector,

wherein the classification processor identifies the multi-dimensional filter rule based on the filter-rule vector and associates the multi-dimensional filter rule with the packet.

2. The invention as recited in claim 1, further comprising a pre-processor comprising:

a first processing module adapted to project each multi-dimensional filter rule onto each dimension to define a filter rule segment in the dimension, the first processing module decomposing each filter-rule segment into one or more non-overlapping intervals associated with one or more multi-dimensional filter rules; and

a second processing module adapted to generate an interval vector for each non-overlapping interval, the second processing module storing either the interval vector or a difference vector for each interval vector.

3. The invention as recited in claim 2, wherein each interval vector identifies a presence or absence of each multi-dimensional filter rule in the corresponding non-overlapping interval.

4. The invention as recited in claim 2, wherein each difference vector is generated by the second processing module based on a difference between the corresponding interval vector and an interval vector corresponding to a different non-overlapping interval.

5. The invention as recited in claim 4, wherein each interval vector comprises a bitmap, the bitmap having bits in one-to-one correspondence with each multi-dimensional filter-rule in the dimension, and the step g) further comprises the step of setting each bit indicating a presence or absence of the multi-dimensional filter-rule.

6. The invention as recited in claim 5, wherein the logic operator combines the interval vectors as an intersection of the bitmaps for each dimension.

7. The invention as recited in claim 1, wherein each interval vector identifies a presence or absence of each multi-dimensional filter rule in the corresponding interval.

8. The invention as recited in claim 4, wherein each interval vector comprises a bitmap, the bitmap having bits in one-to-one correspondence with each multi-dimensional filter-rule in the dimension, and the step g) further comprises the step of setting each bit indicating a presence or absence of the multi-dimensional filter-rule.

9. The invention as recited in claim 8, wherein the logic operator combines the interval vectors as an intersection of the bitmaps for each dimension.

10. The invention as recited in claim 8, wherein the logic operator is an AND operator.

11. The method as recited in claim 8, wherein each bit position of the bitmap is associated with a priority of the corresponding multi-dimensional filter-rule.

12. A method of associating a multi-dimensional filter rule with a packet having two or more fields corresponding to two or more dimensions, the multi-dimensional filter rule to be applied to the packet by a router in a communications network, the method comprising the steps of:

a) identifying an interval in each dimension based on the value of a corresponding field of the packet;

b) generating an interval vector for each interval identified in step a), wherein at least one interval vector is formed from a stored interval vector and a stored difference vector associated with the corresponding interval;

c) logically combining the interval vectors generated in step b) to generate a filter-rule vector;

d) identifying the multi-dimensional filter rule based on the filter-rule vector; and

e) associating the multi-dimensional filter rule with the packet.

13. The method as recited in claim 12, wherein, for each multi-dimensional filter rule, the method further comprises the steps of:

f) projecting each multi-dimensional filter rule onto each dimension to define a filter-rule segment in the dimension;

g) decomposing each filter-rule segment into one or more non-overlapping intervals, wherein each non-overlapping interval is associated with one or more multi-dimensional filter-rules;

h) generating one of the interval vectors for each non-overlapping interval; and

i) storing either the interval vector or a difference vector for each interval vector.

14. The method as recited in claim 13, wherein each interval vector identifies each multi-dimensional filter-rule associated with the corresponding non-overlapping interval.

15. The method as recited in claim 13, wherein the step i) comprises the step of generating each difference vector based on a difference between the corresponding interval vector and an interval vector corresponding to a different non-overlapping interval.

16. The method as recited in claim 15, wherein the step i) comprises the step of generating each difference vector based on a difference between the corresponding interval vector and the interval vector corresponding to the previous non-overlapping interval.

17. The method as recited in claim 15, wherein the step i) comprises the step of generating each difference vector based on a cumulative difference between the corresponding interval vector and a stored interval vector corresponding to a different non-overlapping interval.

18. The method as recited in claim 13, wherein each interval vector comprises a bitmap, the bitmap having bits in one-to-one correspondence with each multi-dimensional filter-rule in the dimension, and the step h) further comprises the step of setting each bit indicating a presence or absence of the multi-dimensional filter rule in the non-overlapping interval.

19. The method as recited in claim 18, wherein the step c) comprises the step of intersecting the bitmaps for each interval.

20. The method as recited in claim 18, wherein each bit position of the bitmap is associated with a priority level of the corresponding multi-dimensional filter rule.

21. The method as recited in claim 12, wherein each interval vector identifies each multi-dimensional filter rule associated with the corresponding interval.

22. The method as recited in claim 21, wherein, for each interval vector, a priority level is defined for each multi-dimensional filter rule.

23. The method as recited in claim 12, wherein, for each interval vector, a priority level is defined for each multi-dimensional filter rule associated with the interval vector.

24. The method as recited in claim 23, wherein step d) comprises the step of identifying the multi-dimensional filter rule having the highest priority level in the filter-rule vector.

25. A method of associating multi-dimensional filter rules with at least one non-overlapping intervals in each dimension of the multi-dimensional filter-rule, each dimension of the multi-dimensional filter rule corresponding to a field of a packet, comprising the steps of:

a) projecting each multi-dimensional filter rule onto each dimension to define a filter-rule segment in the dimension;

b) decomposing each filter-rule segment into one or more non-overlapping intervals, wherein each non-overlapping interval is associated with one or more multi-dimensional filter-rules;

c) generating an interval vector for each non-overlapping interval; and

d) storing either the interval vector or a difference vector for each interval vector.

26. The method as recited in claim 25, wherein each interval vector identifies each multi-dimensional filter-rule associated with the corresponding non-overlapping interval.

27. The method as recited in claim 26, wherein the step c) further comprises the step of generating each difference vector based on a difference between the corresponding interval vector and an interval vector corresponding to a different non-overlapping interval.

28. The method as recited in claim 26, wherein each interval vector comprises a bitmap, the bitmap having bits in one-to-one correspondence with each multi-dimensional filter-rule in the dimension, and the step h) further comprises the step of setting each bit indicating a presence or absence of the multi-dimensional filter rule in the non-overlapping interval.

29. The method as recited in claim 26, wherein, for each interval vector, a priority level is defined for each multi-dimensional filter rule associated with the interval vector.