Method and apparatus for encoding a plurality of pre-defined codes into a search key and for locating a longest matching pre-defined code

• US 20050157724A1
• Filed: 01/14/2005
• Published: 07/21/2005
• Est. Priority Date: 12/30/1999
• Status: Active Grant

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Delfin Y. Montuno, James Aweya
• Inventors: Aweya, James, Montuno, Delfin Y.
• Granted Patent: US 7,324,519 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method and apparatus for locating in a list of pre-defined codes, a longest code matching a given code. The method and apparatus involve producing a search mask encoding at least one portion of said given code and comparing the search mask to a search key having a Prefix Node Bit Array (PNBA) in which a bit is set active in at least one of a plurality of bit positions corresponding to possible bit combinations of bits in a bit string having a length equal to or less than the longest predefined code in the plurality of pre-defined codes and arranged by the lengths of possible bit combinations and by numeric values of the bit combinations, to identify a common active bit position in the search key and the search mask corresponding to one of the pre-defined codes having a length greater than all others of said pre-defined codes which correspond to common active bit positions.

Claims

1. A method of locating, in a list of pre-defined codes, a longest code matching a given code, the method comprising

a) producing a search mask encoding at least one portion of said given code;

and

b) comparing said search mask to a search key having a Prefix Node Bit Array (PNBA) in which a bit is set active in at least one of a plurality of bit positions corresponding to possible bit combinations of bits in a bit string having a length equal to or less than the longest predefined code in said plurality of said pre-defined codes and arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations, to identify a common active bit position in said search key and said search mask corresponding to one of said pre-defined codes having a length greater than all others of said pre-defined codes which correspond to common active bit positions.

2. The method claimed in claim 1 wherein producing comprises producing a Prefix Node Bit Array (PNBA) mask having bit positions corresponding to possible bit combinations in said given code and wherein said bit positions are arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations.

3. The method claimed in claim 2 wherein comparing comprises ANDing said PNBA mask with a search PNBA of said search key to produce a resultant PNBA.

4. The method claimed in claim 3 wherein comparing comprises determining a highest bit position in said resultant PNBA in which a bit is set.

5. The method claimed in claim 4 wherein comparing further comprises selecting as said longest code a pre-defined code corresponding to said highest bit position in said resultant PNBA.

6. A method of locating next hop information for a packet having a destination address comprising the method claimed in claim 4 in which the destination address is the given code and further comprising locating a position in a next hop array associating next hop information with active PNBA bit positions of the search PNBA, corresponding to said highest bit position in said resultant PNBA.

7. The method claimed in claim 1 wherein producing comprises producing a plurality of Prefix Node Bit Array (PNBA) masks having bit positions corresponding to possible bit sub-combinations in said given code and wherein said bit positions are arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations.

8. The method claimed in claim 7 wherein comparing comprises ANDing at least one of said PNBA masks with a search PNBA encoding possible bit sub-combinations of said pre-defined codes to produce at least one resultant PNBA.

9. The method claimed in claim 8 wherein comparing comprises determining a highest bit position in said at least one resultant PNBA in which a bit is set.

10. The method claimed in claim 9 wherein comparing further comprises selecting as said longest code a code having a sub-combination corresponding to said highest bit position in said at least one resultant PNBA.

11. A method of locating next hop information for a packet having a destination address the method comprising the method claimed in claim 10 in which the destination address is the given code and further comprising locating a position in a next hop array associating next hop information with active PNBA bit positions of the search PNBA, by determining a highest numbered bit position in said resultant PNBA and summing all of the active bits in the search PNBA in positions of the search PNBA less than a position with the same number as said highest numbered bit position in said resultant PNBA to produce a PNBA sum and adding said PNBA sum to a value representing a next hop pointer associated with said search PNBA to produce a next hop value identifying said position in said next hop array.

12. The method claimed in claim 9 wherein comparing further comprises determining whether or not any longer matching pre-defined code is encoded.

13. The method claimed in claim 12 wherein comparing comprises comparing said PNBA mask with at least one search PNBA associated with a search page.

14. The method claimed in claim 13 wherein comparing comprises determining a next search page to use to seek a longer matching pre-defined code.

15. The method claimed in claim 14 wherein determining a next search page comprises producing an External Subtree Root Bit Array (ESRBA) mask for each PNBA mask, wherein each ESRBA mask has 2^k bit position where k=the number of bits by which said given code is divided into sub prefixes and a bit position P of said each ESRBA mask is set active according to the following expression:

P=associated PNBA mask bit position−

2<sup>k−

1</sup>

16. The method claimed in claim 15 further comprising ANDing one of said ESRBA masks with an ESRBA associated with a said at least one of said PNBA masks to produce a resultant ESRBA.

17. The method claimed in claim 16 further comprising determining a set bit position in said resultant ESRBA in which a bit is set and summing all of the active bits in the search ESRBA in positions of the search ESRBA less than a position with the same number as said set bit position, to produce an ESRBA sum and adding said ESRBA sum to a value representing a next page pointer associated with said search ESRBA to produce a next page value identifying a next page to use to continue searching for a longer matching pre-defined code.

18. A method of locating next hop information for a packet having a destination address, the method comprising the method claimed in claim 17 in which the destination address is the given code and further comprising locating a position in a next hop array associating next hop information with active PNBA bit positions of the search PNBA and sorted according to corresponding to said active bit positions, corresponding to said highest bit position in said resultant PNBA.

19. The method claimed in claim 13 wherein comparing comprises determining a next PNBA to use to seek a longer matching pre-defined code.

20. The method claimed in claim 19 wherein determining a next PNBA comprises producing an External Subtree Root Bit Array (ESRBA) mask for each PNBA mask, wherein each ESRBA mask has 2^k bit position where k=the number of bits by which said given code is divided into sub prefixes and a bit position P of said each ESRBA mask is set active according to the following expression:

P=associated PNBA mask bit position−

2<sup>k−

1</sup>

21. The method claimed in claim 20 further comprising ANDing one of said ESRBAs with an ESRBA associated with a current PNBA to produce a resultant ESRBA.

22. The method claimed in claim 21 further comprising determining a set bit position in said resultant ESRBA in which a bit is set active and summing the bits of any previous search ESRBAs in the page to produce an ESRBA previous sum, summing the bits of a preset search ESRBA up to the same position as said set bit position, to produce a present ESRBA sum and adding the ESRBA previous sum to the ESRBA preset sum plus 1 to produce a PNBA-ESRBA indicator representing a next PNBA-ESRBA pair to use for searching.

23. The method claimed in claim 22 further comprising determining a next page with which said next PNBA-ESRBA pair is associated according to the relation:

$\mathrm{Next}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{page}=\mathrm{next}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{page}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pointer}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{in}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{current}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{page}+\left[\frac{r-u-1}{u}\right]$

where

r=said next PNBA-ESRBA indicator

u=the number of PNBA-ESRBA pairs associated with a page

when

r>

u.

24. A method of locating next hop information for a packet having a destination address, the method comprising the method claimed in claim 22 in which the destination address is the given code and further comprising locating a position in a next hop array associating next hop information with active PNBA bit positions of each search PNBA by summing all of the bits of all previous search PNBAs in a page to produce a PNBA previous sum, summing all of the bits of a present search PNBA associated with said page up to a position less than the position where the bit is set to produce a present PNBA sum and adding the PNBA previous sum with the PNBA preset sum plus a value representing a next hop pointer associated with the page associated with the preset PNBA to produce next hop array position value identifying a next hop array position in a next hop array at which said next hop information is stored.

25. An apparatus for locating, in a list of pre-defined codes, a longest code matching a given code, the apparatus comprising:

a) means for producing a search mask encoding at least one portion of said given code; and

b) means for comparing said search mask to a search key having a Prefix Node Bit Array (PNBA) in which a bit is set active in at least one of a plurality of bit positions corresponding to possible bit combinations of bits in a bit string having a length equal to or less than the longest predefined code in said plurality of said pre-defined codes and arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations, to identify a common active bit position in said search key and said search mask corresponding to one of said pre-defined codes having a length greater than all others of said pre-defined codes which correspond to common active bit positions.

26. A apparatus for locating, in a list of pre-defined codes, a longest code matching a given code, the apparatus comprising a processor circuit and memory in communication with the processor circuit, said memory being configured to direct the processor circuit to:

a) produce a search mask encoding at least one portion of said given code; and

b) compare said search mask to a search key having a Prefix Node Bit Array (PNBA) in which a bit is set active in at least one of a plurality of bit positions corresponding to possible bit combinations of bits in a bit string having a length equal to or less than the longest predefined code in said plurality of said pre-defined codes and arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations, to identify a common active bit position in said search key and said search mask corresponding to one of said pre-defined codes having a length greater than all others of said pre-defined codes which correspond to common active bit positions.

27. The apparatus claimed in claim 26 wherein said memory is configured to direct said processor circuit to produce a Prefix Node Bit Array (PNBA) mask having bit positions corresponding to possible bit combinations in said given code and wherein said bit positions are arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations.

28. The apparatus claimed in claim 27 wherein said memory is configured to direct said processor circuit to AND said PNBA mask with a search PNBA of said search key to produce a resultant PNBA.

29. The apparatus claimed in claim 28 wherein said memory is configured to direct said processor circuit to determine a highest bit position in said resultant PNBA in which a bit is set.

30. The apparatus claimed in claim 29 wherein said memory is configured to direct said processor circuit to select as said longest code a pre-defined code corresponding to said highest bit position in said resultant PNBA.

31. An apparatus for locating next hop information for a packet having a destination address, the apparatus comprising the apparatus claimed in claim 29 in which the destination address is the given code and wherein said memory is configured to direct said processor circuit to locate a position in a next hop array associating next hop information with active PNBA bit positions of the search PNBA, corresponding to said highest bit position in said resultant PNBA.

32. The apparatus claimed in claim 26 wherein said memory is configured to direct said processor circuit to produce a plurality of Prefix Node Bit Array (PNBA) masks having bit positions corresponding to possible bit sub-combinations in said given code and wherein said bit positions are arranged by the lengths of said possible bit combinations and by numeric values of said bit combinations.

33. The apparatus claimed in claim 32 wherein said memory is configured to direct said processor circuit to AND at least one of said PNBA masks with a search PNBA encoding possible bit sub-combinations of said pre-defined codes to produce at least one resultant PNBA.

34. The apparatus claimed in claim 33 wherein said memory is configured to direct said processor circuit to determine a highest bit position in said at least one resultant PNBA in which a bit is set.

35. The apparatus claimed in claim 34 wherein said memory is configured to direct said processor circuit to select as said longest code a code having a sub-combination corresponding to said highest bit position in said at least one resultant PNBA.

36. An apparatus for locating next hop information for a packet having a destination address, the apparatus comprising the apparatus claimed in claim 35 in which the destination address is the given code and wherein said memory is configured to direct said processor circuit to locate a position in a next hop array associating next hop information with active PNBA bit positions of the search PNBA, by determining a highest numbered bit position in said resultant PNBA and summing all of the active bits in the search PNBA in positions of the search PNBA less than a position with the same number as said highest numbered bit position in said resultant PNBA to produce a PNBA sum and adding said PNBA sum to a value representing a next hop pointer associated with said search PNBA to produce a next hop value identifying said position in said next hop array.

37. The apparatus claimed in claim 34 wherein said memory is configured to direct said processor circuit to determine whether or not any longer matching pre-defined code is encoded.

38. The apparatus claimed in claim 37 wherein said memory is configured to direct said processor circuit to compare said PNBA mask with at least one search PNBA associated with a search page.

39. The apparatus claimed in claim 38 wherein said memory is configured to direct said processor circuit to determine a next search page to use to seek a longer matching pre-defined code.

40. The apparatus claimed in claim 39 wherein said memory is configured to direct said processor circuit to determine a next search page by producing an External Subtree Root Bit Array (ESRBA) mask for each PNBA mask, wherein each ESRBA mask has 2^k bit position where k=the number of bits by which said given code is divided into sub prefixes and a bit position P of said each ESRBA mask is set active according to the following expression:

P=associated PNBA mask bit position−

2<sup>k−

1</sup>

41. The apparatus claimed in claim 40 wherein said memory is configured to direct said processor circuit to AND one of said ESRBA masks with an ESRBA associated with a said at least one of said PNBA masks to produce a resultant ESRBA.

42. The apparatus claimed in claim 41 wherein said memory is configured to direct said processor circuit to determine a set bit position in said resultant ESRBA in which a bit is set and summing all of the active bits in the search ESRBA in positions of the search ESRBA less than a position with the same number as said set bit position, to produce an ESRBA sum and add said ESRBA sum to a value representing a next page pointer associated with said search ESRBA to produce a next page value identifying a next page to use to continue searching for a longer matching pre-defined code.

43. An apparatus for locating next hop information for a packet having a destination address, the apparatus comprising the apparatus claimed in claim 42 in which the destination address is the given code and wherein said memory is configured to direct said processor circuit to locate a position in a next hop array associating next hop information with active PNBA bit positions of the search PNBA and sorted according to corresponding to said active bit positions, corresponding to said highest bit position in said resultant PNBA.

44. The apparatus claimed in claim 38 wherein said memory is configured to direct said processor circuit to determine a next PNBA to use to seek a longer matching pre-defined code.

45. The apparatus claimed in claim 44 wherein said memory is configured to direct said processor circuit to determine a next PNBA by producing an External Subtree Root Bit Array (ESRBA) mask for each PNBA mask, wherein each ESRBA mask has 2^k bit position where k=the number of bits by which said given code is divided into sub prefixes and a bit position P of said each ESRBA mask is set active according to the following expression:

P=associated PNBA mask bit position−

2<sup>k−

1</sup>

46. The apparatus claimed in claim 45 wherein said memory is configured to direct said processor circuit to AND one of said ESRBAs with an ESRBA associated with a current PNBA to produce a resultant ESRBA.

47. The apparatus claimed in claim 46 wherein said memory is configured to direct said processor circuit to determine a set bit position in said resultant ESRBA in which a bit is set active and sum the bits of any previous search ESRBAs in the page to produce an ESRBA previous sum, and to sum the bits of a preset search ESRBA up to the same position as said set bit position to produce a present ESRBA sum and to add the ESRBA previous sum to the ESRBA present sum plus 1 to produce a PNBA-ESRBA indicator representing a next PNBA-ESRBA pair to use for searching.

48. The apparatus claimed in claim 47 wherein said memory is configured to direct said processor circuit to determine a next page with which said next PNBA-ESRBA pair is associated according to the relation:

$\mathrm{Next}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{page}=\mathrm{next}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{page}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{pointer}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{in}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{current}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{page}+\left[\frac{r-u-1}{u}\right]$

where

r=said next PNBA-ESRBA indicator

u=the number of PNBA-ESRBA pairs associated with a page

when

r>

u.

49. An apparatus for locating next hop information for a packet having a destination address, the apparatus comprising the apparatus claimed in claim 47 in which the destination address is the given code and wherein said memory is configured to direct said processor circuit to locate a position in a next hop array associating next hop information with active PNBA bit positions of each search PNBA by summing all of the bits of all previous search PNBAs in a page to produce a PNBA previous sum, and by summing all of the bits of a present search PNBA associated with said page up to a position less than the position where the bit is set to produce a present PNBA sum and by adding the PNBA previous sum with the PNBA preset sum plus a value representing a next hop pointer associated with the page associated with the preset PNBA to produce next hop array position value identifying a next hop array position in a next hop array at which said next hop information is stored.