Method and apparatus for routing information packets associated to addresses represented through numerical strings

• US 6,731,643 B1
• Filed: 12/16/1999
• Issued: 05/04/2004
• Est. Priority Date: 12/30/1998
• Status: Expired due to Term

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Perissinotto, Cristian, Cucchi, Silvio
• Primary Examiner(s): Vanderpuye, Kenneth
• Assistant Examiner(s): Phunkulh, Bob A.
• Application Number:
  US09/464,392
• Time in Patent Office: 1,601 Days
• Field of Search: 370/389, 370/392, 370/400, 370/401, 370/411, 370/395.1, 370/395.3, 370/395.31, 370/395.32, 709/238, 709/239, 709/240, 709/241, 709/242, 711/202, 711/203, 711/204, 711/205, 711/206, 711/207, 711/211, 711/216
• US Class Current: 370/401
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing

Abstract

A method for routing information packets associated with addresses represented by numerical strings, in routing apparatuses for telecommunication networks, wherein the routing apparatus receives information packets at their input and routes the packets on a plurality of outputs. The method builds a first set of numerical strings with variable length, and contains the strings in an address table. The method then compares a first address, incoming at the input and associated to an information packet, with said first set of numerical strings according to a longest prefix match criterion and using a binary search for performing the comparison. The comparison further includes building a second set of numerical strings contained in a sorted extended address table wherein the table is derived from the first set of numerical strings and the second set of numerical strings is derived from the first set of numerical strings using a building-by-intervals method which operates on the intervals defined by the numerical strings belonging to said first set of numerical strings.

Claims

1. A method for routing information packets associated with addresses represented by numerical strings through routing apparatuses in a telecommunication network, wherein the routing apparatuses receive at their input information packets and route said packets on a plurality of outputs, said numerical strings by identifiable by at least part of a prefix, said method comprising:

building a first set of numerical strings with variable length and contained in an address table, said address table being sorted and associated to a set of references to the outputs, said set of references being inserted in a mapping table;

comparing a first address, incoming at the input and associated to an information packet, with said first set of numerical strings according to a longest prefix match criterion using a binary search method for performing the comparison, and utilizing the resulting reference to address the information packet to the corresponding output, wherein said comparing includes;

providing for building a second set of numerical strings, contained in a sorted extended address table, said sorted extended table being derived from the first set of numerical strings; and

wherein said second set of numerical strings is derived from the first set of numerical strings using a building-by-intervals method, operating on the intervals defined by the numerical strings belonging to said first set of numerical strings.

2. The method according to claim 1, said method further including:

associating to the second set of numerical strings a complete match mapping table and a set of partial match mapping tables containing at least the references contained in the mapping table;

in case said binary search converges towards the string in k-th position in the sorted extended address table, comparing a resulting string with the first address;

if the resulting string matches with the first address, providing the reference present in k-th position in the complete match mapping table;

if the resulting string does not match with the first address, providing the reference present in k-th position in one of the partial match mapping tables.

3. The method according to claim 2, wherein said building-by-intervals method of the second set of strings comprises:

taking in account each spring belonging to the first set of numerical strings and evaluate its length;

if said length is equal to a maximum length, introducing the string in the second set of numerical strings;

if the length of the string belonging to the first set of numerical strings is shorter than the maximum length, introducing at least an extreme lower string and an extreme upper string of maximum length in the second set of numerical strings, which strings express the interval defined by the string belonging to the first set of numerical strings.

4. The method according to claim 3, wherein said building-by-intervals method of the second set of strings, should the length of the string belonging to the first set of numerical strings be shorter than the maximum length, will also introduce an external lower string and an external upper string of maximum length, in the second set of numerical strings, said external lower string being adjacent to and preceding the extreme lower string, whereas said external upper string is adjacent to and subsequent to the extreme upper string.

5. The method according to claim 3, wherein the set of partial match mapping tables consists of a unique partial match mapping table.

6. The method according to claim 5, wherein:

if the resulting string matches with the first address at the input, providing the reference present in k-th position in the complete match mapping table;

if the resulting string does not match with the first address at the input but has a partial match, providing the reference present in k-th position in one of the partial match mapping table;

if the resulting has a null match with the first address, directly providing a “

no match”

information.

7. The method according to claim 3, wherein said method further comprises:

building a set of mapping tables sorted by increasing length through the set of partial match mapping tables and the complete match mapping table;

calculating, if the resulting string through the binary search is in k-th position, a common length of the common prefix between the address at the input and the resulting string;

returning the reference present in k-th position in the j-th mapping table sorted by crescent length.

8. The method according to claim 7, wherein the number of said mapping tables sorted by increasing length is equal to the maximum length of the strings belonging to the first set of numerical strings.

9. The method according to claim 7, wherein the number of said mapping tables sorted by increasing length is equal to a number of different lengths that may be taken by the strings belonging to the first set of numerical strings.

10. The method according to claim 3, wherein the set of partial match mapping tables consists of a maximum match mapping table and an external match mapping table and that, moreover, they are associated to a prefix length table.

11. The method according to claim 10, wherein said maximum match mapping table contains in k-th position the reference to the longest prefix usable for the corresponding numerical string in the extended address table, whereas the length of said prefix is stored in k-th position of the prefix length table, whereas the external match mapping table contains for each string in k-th position of the extended address table the reference to the first more external interval with respect to the interval referred to by the reference contained in k-th position of the maximum match mapping table.

12. The method according to claim 3, wherein a cancellation step is provided for one or more numerical strings from the first set of numerical strings, said cancellation step being followed by the sole modification of the references contained in the set of the partial match mapping tables and in the complete match mapping table.

13. The method according to claim 3, wherein an enabling or disabling step is provided for one or more numerical strings from the first set of numerical strings, said enabling or disabling step being followed by the sole modification of the references contained in the set of partial match mapping tables and in the complete match mapping table.

14. A routing apparatus, utilized in telecommunication networks, receiving at its input information packets, associated with addresses represented by numerical strings and routing said packets on a plurality of outputs, said routing apparatus comprising:

a mapping unit configured to build a first set of numerical strings with variable length, said strings being contained in an address table, said address table being sorted and associated to a set of references to the outputs, said set of references being inserted in a mapping table;

a comparison unit configured to comparing a first address, incoming at the input and associated to an information packet, with said first set of numerical strings according to a longest prefix match criterion using a binary search method for performing the comparison, and utilizing the resulting reference to address the information packet to the corresponding output, wherein said comparing unit further includes;

a build mechanism configured to build a second set of numerical strings, contained in a sorted extended address table, said sorted extended table being derived from the first set of numerical strings; and

wherein said second set of numerical strings is derived from the first set of numerical strings using a building-by-intervals unit, said building by intervals unit operating on the intervals defined by the numerical strings belonging to said first set of numerical strings.

15. The routing apparatus according to claim 14, said apparatus further including:

an associating unit for associating to the second set of numerical strings a complete match mapping table and a set of partial match mapping tables containing at least the references contained in the mapping table;

wherein in case said binary search converges towards the string in k-th position in the sorted extended address table, comparing a resulting string with the first address;

if the resulting string matches with the first address, providing the reference present in k-th position in the complete match mapping table;

if the resulting string does not match with the first address, providing the reference present in k-th position in one of the partial match mapping tables.

16. The routing apparatus according to claim 15, wherein said building-by-intervals unit of the second set of strings comprises:

an accounting unit for taking in account each string belonging to the first set of numerical strings and evaluate its length, wherein

if said length is equal to a maximum length, introducing the string in the second set of numerical strings;

if the length of the string belonging to the first set of numerical strings is shorter than the maximum length, introducing at least an extreme lower string and an extreme upper string of maximum length in the second set of numerical strings, which strings express the interval defined by the string belonging to the first set of numerical strings.

17. The routing apparatus according to claim 16, wherein said building-by-intervals unit of the second set of strings, should the length of the string belonging to the first set of numerical strings be shorter than the maximum length, will also introduce an external lower string and an external upper string of maximum length, in the second set of numerical strings, said external lower string being adjacent to and preceding the extreme lower string, whereas said external upper string is adjacent to and subsequent to the extreme upper string.

18. The routing apparatus according to claim 16, wherein the set of partial match mapping tables consists of a unique partial match mapping table.

19. The routing apparatus according to claim 18, wherein said building by interval unit further comprises a matching unit configure to perform the following steps:

if the resulting string matches with the first address at the input, providing the reference present in k-th position in the complete match mapping table;

if the resulting string does not match with the first address at the input but has a partial match, providing the reference present in k-th position in one of the partial match mapping tables;

if the resulting has a null match with the first address, directly providing a “

no match”

information.

20. The routing apparatus according to claim 16, wherein said apparatus further comprises:

a building unit configured to build a set of mapping tables sorted by increasing length through the set of partial match mapping tables and the complete match mapping table;

a calculation unit configured to calculate, if the resulting string through the binary search is in k-th position, a common length of the common prefix between the address at the input and the resulting string;

a reference returning unit configured to return the reference present in k-th position in the j-th mapping table sorted by crescent length.

21. The routing apparatus according to claim 20, wherein the number of said mapping tables sorted by increasing length is equal to the maximum length of the strings belonging to the first set of numerical strings.

22. The routing apparatus according to claim 20, wherein the number of said mapping tables sorted by increasing length is equal to a number of different lengths that may be taken by the strings belonging to the first set of numerical strings.

23. The routing apparatus according to claim 16, wherein the set of partial match mapping tables consists of a maximum match mapping table and an external match mapping table and the maximum match mapping table and external match mapping table are associated to a prefix length table.

24. The routing apparatus according to claim 23, wherein said maximum match mapping table contains in k-th position the reference to the longest prefix usable for the corresponding numerical string in the extended address table, whereas the length of said prefix is stored in k-th position of the prefix length table, whereas the external match mapping table contains for each string in k-th position of the extended address table the reference to the first more external interval with respect to the interval referred to by the reference contained in k-th position of the maximum match mapping table.

25. The routing apparatus according to claim 14, wherein a cancellation unit is provided for one or more numerical strings from the first set of numerical strings, said cancellation unit configured to modify the references contained in the set of the partial match mapping tables and in the complete match mapping table.

26. The routing apparatus according to claim 14, wherein an enabling or disabling unit is configured to provide one or more numerical strings from the first set of numerical strings, said enabling or disabling unit further configures to modify the references contained in the set of partial match mapping tables and in the complete match mapping table.

27. A computer program product for enabling a computer to route information packets associated with addresses represented by numerical strings through a routing apparatus, said computer program product comprising:

software instructions for enabling the computer to perform predetermined operations, and

a computer readable medium bearing the software instructions;

the predetermined operations including the steps of;

building a first set of numerical strings with variable length and contained in an address table, said address table being sorted and associated to a set of references to outputs, said set of references being inserted in a mapping table;

comparing a first address, incoming at an input and associated to an information packet with said first set of numerical strings according to a longest prefix match criterion using a binary search method for performing the comparison, and utilizing the resulting reference to address the information packet to the corresponding output, wherein said comparing includes;

providing for building a second set of numerical strings, contained in a sorted extended address table, said sorted extended table being derived from the first set of numerical strings; and

wherein said second set of numerical strings is derived from the first set of numerical strings using a building-by-intervals method, operating on the intervals defined by the numerical strings belonging to said first set of numerical strings.

28. The computer program product according to claim 27, further including instructions for:

associating to the second set of numerical strings a complete match mapping table and a set of partial match mapping tables containing at least the references contained in the mapping table;

in case said binary search converges towards the string in k-th position in the sorted extended address table, comparing a resulting string with the first address;

if the resulting string matches with the first address, providing the reference present in k-th position in the complete match mapping table;

if the resulting string does not match with the first address, providing the reference present in k-th position in one of the partial match mapping tables.

29. The computer program product according to claim 28, wherein said building-by-intervals method of the second set of strings comprises:

taking in account each string belonging to the first set of numerical strings and evaluate its length;

if said length is equal to a maximum length, introducing the string in the second set of numerical strings;

if the length of the string belonging to the first set of numerical strings is shorter than the maximum length, introducing at least an extreme lower string and an extreme upper string of maximum length in the second set of numerical strings, which strings express the interval defined by the string belonging to the first set of numerical strings.

30. The computer program product according to claim 29, wherein said building-by-intervals method of the second set of strings, should the length of the string belonging to the first set of numerical strings be shorter than the maximum length, will also introduce an external lower string and an external upper string of maximum length, in the second set of numerical strings, said external lower string being adjacent to and preceding the extreme lower string, whereas said external upper string is adjacent to and subsequent to the extreme upper string.

31. The computer program product according to claim 29, wherein the set of partial match mapping tables consists of a unique partial match mapping table.

32. The computer program product according to claim 29, wherein:

if the resulting string matches with the first address at the input, providing the reference present in k-th position in the complete match mapping table;

if the resulting string does not match with the first address at the input but has a partial match, providing the reference present in k-th position in one of the partial match mapping table;

if the resulting has a null match with the first address, directly providing a “

no match”

information.

33. The computer program product according to claim 29, wherein said the computer program product further includes instructions for:

building a set of mapping tables sorted by increasing length through the set of partial match mapping tables and the complete match mapping table;

calculating, if the resulting string through the binary search is in k-th position, a common length of the common prefix between the address at the input and the resulting string;

returning the reference present in k-th position in the j-th mapping table sorted by crescent length.

34. The computer program product according to claim 33, wherein the number of said mapping tables sorted by increasing length is equal to the maximum length of the strings belonging to the first set of numerical strings.

35. The computer program product according to claim 33, wherein the number of said mapping tables sorted by increasing length is equal to a number of different lengths that may be taken by the strings belonging to the first set of numerical strings.

36. The computer program product according to claim 29, wherein the set of partial match mapping tables consists of a maximum match mapping table and an external match mapping table and that, moreover, they are associated to a prefix length table.

37. The computer program product according to claim 36, wherein said maximum match mapping table contains in k-th position the reference to the longest prefix usable for the corresponding numerical string in the extended address table, whereas the length of said prefix is stored in k-th position of the prefix length table, whereas the external match mapping table contains for each string in k-th position of the extended address table the reference to the first more external interval with respect to the interval referred to by the reference contained in k-th position of the maximum match mapping table.

38. The computer program product according to claim 29, wherein a cancellation step is provided for one or more numerical strings from the first set of numerical strings, said cancellation step being followed by the sole modification of the references contained in the set of the partial match mapping tables and in the complete match mapping table.

39. The computer program product according to claim 29, wherein an enabling or disabling step is provided for one or more numerical strings from the first set of numerical strings, said enabling or disabling step being followed by the sole modification of the references contained in the set of partial match mapping tables and in the complete match mapping table.