Techniques for efficient memory management for longest prefix match problems

• US 6,725,326 B1
• Filed: 08/15/2000
• Issued: 04/20/2004
• Est. Priority Date: 08/15/2000
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Patra, Abhijit, Sharma, Samar, Panigrahy, Rina
• Primary Examiner(s): Ellis, Kevin L.
• Assistant Examiner(s): Ho, Thang H
• Application Number:
  US09/639,387
• Time in Patent Office: 1,344 Days
• Field of Search: 711/108, 713/160, 365/49
• US Class Current: 711/108
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: H04L 45/7453 using hashing
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

Techniques for efficient memory management that enable rapid longest prefix match lookups in memory. In general, the present invention is efficacious wherever maintenance of a good distribution of holes in a sorted list is required. This technique relies on a proactive hole management methodology to preserve a good distribution of holes in each memory region in such a way that one does not have to search for holes in order to insert or store a new entry into the list. In particular, all holes in a given region are kept in one or more contiguous sub-region. Keeping the holes contiguous requires a hole move every time there is a delete operation. The amortized cost of these operations is justified by the resulting simplification in later insert (store) and delete operations. For example, during an insert the new entry is placed at the end of the contiguous sub-region of used entries in the region. During a delete, when a hole is created in the middle of a contiguous sub-region of used entries, the last used entry is moved into the hole, thus keeping the holes contiguous. Such an organization of holes and movement of used entries within a region is permissible within the longest prefix match type of lookup table, because all entries within a region, by definition, have an IP prefix of equal length.

Claims

1. A method of memory management comprising the steps of:

dividing a memory into a plurality of contiguous regions ordered from the lowest to the highest, each said region composed of a plurality of entries, wherein each said entry is either a used entry or a hole;

iteratively;

equalizing a first designated region to maintain all used entries in a first contiguous sub-region adjoining a second contiguous sub-region containing all holes;

when commanded

inserting a value in one of said entries in a second designated region, said second designated region being any one of said plurality of contiguous regions, wherein said inserting further comprises;

if said second designated region lacks a hole, expanding said second designated region by moving one of said holes from an adjoining region; and

writing said value in a hole in said second designated region; and

deleting a used entry by converting said used entry into a hole.

2. The method of claim 1, wherein said second designated region contains two said second sub-regions, each said second sub-region containing only holes and adjoining said first sub-region.

3. The method of claim 1, wherein said memory comprises a content addressable memory (CAM).

4. The method of claim 1, wherein said memory comprises a ternary content addressable memory (TCAM).

5. The method of claim 1, wherein said equalizing further comprises:

moving one of said used entries from an end of said first contiguous sub-region to a hole created by said deleting within said first contiguous sub-region;

or

adjusting the boundaries of said region to maintain a relatively equal distribution of holes in said region with respect to at least one adjoining region.

6. The method of claim 1, wherein said first designated region is the contiguous region having the most holes.

7. The method of claim 1, wherein said equalizing further comprises:

computing the difference in number of said holes between each said contiguous region i and the next adjoining region ((i

     1) modulo (the number of said plurality of contiguous regions)); and

designating said first designated region based on having the most said difference.

8. The method of claim 1, wherein said equalizing further comprises:

further dividing said plurality of contiguous regions into a lower group and an upper group, wherein said first group consists of all contiguous regions from said lowest region up to and including said second designated region and said second group consists of all other regions;

computing an average number of holes in said lower group and said upper group respectively;

determining if said average number of holes in said lower group is larger than said average number of holes in said upper group, the result of said determining forming a first Boolean;

next determining if the number of holes in said second designated region is larger than the number of holes in the next higher region;

wherein said next higher region is said lowest region when said second designated region is said highest region, the result of said next determining forming a second Boolean;

if said first Boolean is logically equal to said second Boolean, equalizing said second designated region; and

incrementing said second designated region to point to said next higher contiguous region.

9. A computer system for memory management, comprising computer instructions for:

dividing a memory into a plurality of contiguous regions ordered from the lowest to the highest, each said region composed of a plurality of entries, wherein each said entry is either a used entry or a hole;

iteratively;

equalizing a first designated region to maintain all used entries in a first contiguous sub-region adjoining a second contiguous sub-region containing all holes;

when commanded

inserting a value in one of said entries in a second designated region, said second designated region being any one of said plurality of contiguous regions, wherein said inserting further comprises;

if said second designated region lacks a hole, expanding said second designated region by moving one of said holes from an adjoining region; and

writing said value in a hole in said second designated region; and

deleting a used entry by converting said used entry into a hole.

10. The computer system of claim 9, wherein said second designated region contains two said second sub-regions, each said second sub-region containing only holes and adjoining said first sub-region.

11. The computer system of claim 9, wherein said memory comprises a content addressable memory (CAM).

12. The computer system of claim 9, wherein said memory comprises a ternary content addressable memory (TCAM).

13. The computer system of claim 9, wherein said equalizing further comprises:

moving one of said used entries from an end of said first contiguous sub-region to a hole created by said deleting within said first contiguous sub-region;

or

adjusting the boundaries of said region to maintain a relatively equal distribution of holes in said region with respect to at least one adjoining region.

14. The computer system of claim 9, wherein said first designated region is the contiguous region having the most holes.

15. The computer system of claim 9, wherein said equalizing further comprises:

computing the difference in number of said holes between each said contiguous region i and the next adjoining region ((i

     1) modulo (the number of said plurality of contiguous regions)); and

designating said first designated region based on having the most said difference.

16. The computer system of claim 9, wherein said equalizing further comprises:

further dividing said plurality of contiguous regions into a lower group and an upper group, wherein said first group consists of all contiguous regions from said lowest region up to and including said second designated region and said second group consists of all other regions;

computing an average number of holes in said lower group and said upper group respectively;

determining if said average number of holes in said lower group is larger than said average number of holes in said upper group, the result of said determining forming a first Boolcan;

next determining if the number of holes in said second designated region is larger than the number of holes in the next higher region;

wherein said next higher region is said lowest region when said second designated region is said highest region, the result of said next determining forming a second Boolean;

if said first Boolean is logically equal to said second Boolean, equalizing said second designated region; and

incrementing said second designated region to point to said next higher contiguous region.

17. A computer system comprising a processor, a memory, and a network interface, said processor configured to perform the steps of:

dividing a memory into a plurality of contiguous regions ordered from the lowest to the highest, each said region composed of a plurality of entries, wherein each said entry is either a used entry or a hole;

iteratively;

equalizing a first designated region to maintain all used entries in a first contiguous sub-region adjoining a second contiguous sub-region containing all holes;

when commanded

inserting a value in one of said entries in a second designated region, said second designated region being any one of said plurality of contiguous regions, wherein said inserting further comprises;

if said second designated region lacks a hole, expanding said second designated region by moving one of said holes from an adjoining region; and

writing said value in a hole in said second designated region; and

deleting a used entry by converting said used entry into a hole.

18. The computer system of claim 17, wherein said second designated region contains two said second sub-regions, each said second sub-region containing only holes and adjoining said first sub-region.

19. The computer system of claim 17, wherein said memory comprises a content addressable memory (CAM).

20. The computer system of claim 17, wherein said memory comprises a ternary content addressable memory (TCAM).

21. The computer system of claim 17, wherein said equalizing further comprises:

moving one of said used entries from an end of said first contiguous sub-region to a hole created by said deleting within said first contiguous sub-region;

or

adjusting the boundaries of said region to maintain a relatively equal distribution of holes in said region with respect to at least one adjoining region.

22. The computer system of claim 17, wherein said first designated region is the contiguous region having the most holes.

23. The computer system of claim 17, wherein said equalizing further comprises:

computing the difference in number of said holes between each said contiguous region i and the next adjoining region ((i

     1) modulo (the number of said plurality of contiguous regions)); and

designating said first designated region based on having the most said difference.

24. The computer system of claim 17, wherein said equalizing further comprises:

further dividing said plurality of contiguous regions into a lower group and an upper group, wherein said first group consists of all contiguous regions from said lowest region up to and including said second designated region and said second group consists of all other regions;

computing an average number of holes in said lower group and said upper group respectively;

determining if said average number of holes in said lower group is larger than said average number of holes in said upper group, the result of said determining forming a first Boolean;

next determining if the number of holes in said second designated region is larger than the number of holes in the next higher region;

wherein said next higher region is said lowest region when said second designated region is said highest region, the result of said next determining forming a second Boolean;

if said first Boolean is logically equal to said second Boolean, equalizing said second designated region; and

incrementing said second designated region to point to said next higher contiguous region.

25. A computer-readable storage medium, comprising computer instructions for:

dividing a memory into a plurality of contiguous regions ordered from the lowest to the highest, each said region composed of a plurality of entries, wherein each said entry is either a used entry or a hole;

iteratively;

equalizing a first designated region to maintain all used entries in a first contiguous sub-region adjoining a second contiguous sub-region containing all holes;

when commanded

inserting a value in one of said entries in a second designated region, said second designated region being any one of said plurality of contiguous regions, wherein said inserting further comprises;

if said second designated region lacks a hole, expanding said second designated region by moving one of said holes from an adjoining region; and

writing said value in a hole in said second designated region; and

deleting a used entry by converting said used entry into a hole.

26. The computer-readable storage medium of claim 25, wherein said second designated region contains two said second sub-regions, each said second sub-region containing only holes and adjoining said first sub-region.

27. The computer-readable storage medium of claim 25, wherein said memory comprises a content addressable memory (CAM).

28. The computer-readable storage medium of claim 25, wherein said memory comprises a ternary content addressable memory (TCAM).

29. The computer-readable storage medium of claim 25, wherein said equalizing further comprises:

moving one of said used entries from an end of said first contiguous sub-region to a hole created by said deleting within said first contiguous sub-region;

or

adjusting the boundaries of said region to maintain a relatively equal distribution of holes in said region with respect to at least one adjoining region.

30. The computer-readable storage medium of claim 25, wherein said first designated region is the contiguous region having the most holes.

31. The computer-readable storage medium of claim 25, wherein said equalizing further comprises:

computing the difference in number of said holes between each said contiguous region i and the next adjoining region ((i

     1) modulo (the number of said plurality of contiguous regions)); and

designating said first designated region based on having the most said difference.

32. The computer-readable storage medium of claim 25, wherein said equalizing further comprises:

further dividing said plurality of contiguous regions into a lower group and an upper group, wherein said first group consists of all contiguous regions from said lowest region up to and including said second designated region and said second group consists of all other regions;

computing an average number of holes in said lower group and said upper group respectively;

determining if said average number of holes in said lower group is larger than said average number of holes in said upper group, the result of said determining forming a first Boolean;

next determining if the number of holes in said second designated region is larger than the number of holes in the next higher region;

wherein said next higher region is said lowest region when said second designated region is said highest region, the result of said next determining forming a second Boolean;

if said first Boolean is logically equal to said second Boolean, equalizing said second designated region; and

incrementing said second designated region to point to said next higher contiguous region.

33. A computer data signal embodied in a carrier wave, comprising computer instructions for:

dividing a memory into a plurality of contiguous regions ordered from the lowest to the highest, each said region composed of a plurality of entries, wherein each said entry is either a used entry or a hole;

iteratively;

equalizing a first designated region to maintain all used entries in a first contiguous sub-region adjoining a second contiguous sub-region containing all holes;

when commanded

inserting a value in one of said entries in a second designated region, said second designated region being any one of said plurality of contiguous regions, wherein said inserting further comprises;

if said second designated region lacks a hole, expanding said second designated region by moving one of said holes from an adjoining region; and

writing said value in a hole in said second designated region; and

deleting a used entry by converting said used entry into a hole.

34. The computer data signal of claim 33, wherein said second designated region contains two said second sub-regions, each said second sub-region containing only holes and adjoining said first sub-region.

35. The computer data signal of claim 33, wherein said memory comprises a content addressable memory (CAM).

36. The computer data signal of claim 33, wherein said memory comprises a ternary content addressable memory (TCAM).

37. The computer data signal of claim 33, wherein said equalizing further comprises:

moving one of said used entries from an end of said first contiguous sub-region to a hole created by said deleting within said first contiguous sub-region;

or

adjusting the boundaries of said region to maintain a relatively equal distribution of holes in said region with respect to at least one adjoining region.

38. The computer data signal of claim 33, wherein said first designated region is the contiguous region having the most holes.

39. The computer data signal of claim 33, wherein said equalizing further comprises:

computing the difference in number of said holes between each said contiguous region i and the next adjoining region ((i

     1) modulo (the number of said plurality of contiguous regions)); and

designating said first designated region based on having the most said difference.

40. The computer data signal of claim 33, wherein said equalizing further comprises:

further dividing said plurality of contiguous regions into a lower group and an upper group, wherein said first group consists of all contiguous regions from said lowest region up to and including said second designated region and said second group consists of all other regions;

computing an average number of holes in said lower group and said upper group respectively;

determining if said average number of holes in said lower group is larger than said average number of holes in said upper group, the result of said determining forming a first Boolean;

next determining if the number of holes in said second designated region is larger than the number of holes in the next higher region;

wherein said next higher region is said lowest region when said second designated region is said highest region, the result of said next determining forming a second Boolean;

if said first Boolean is logically equal to said second Boolean, equalizing said second designated region; and

incrementing said second designated region to point to said next higher contiguous region.