# US 6,731,643 B1 · Method and apparatus for routing information packets associated to addresses represented through numerical strings

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 6,731,643 B1
- Document ID: US6731643B1
- Status: Granted
- Kind: B1
- Application number: 09/464,392
- Filed: 1999-12-16
- Granted: 2004-05-04
- Earliest claimed: 1998-12-30
- Assignees: Alcatel
- Inventors: Silvio Cucchi; Cristian Perissinotto
- Web page: https://patentgrep.com/patent/US6731643B1

## CPC

- H04L 45/04: {Interdomain routing, e.g. hierarchical routing}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 2)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 3)

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

### Claim 6 (depends on 5)

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.

### Claim 7 (depends on 3)

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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 3)

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.

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 3)

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.

### Claim 13 (depends on 3)

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.

### Claim 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.

### Claim 15 (depends on 14)

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.

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 16)

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

### Claim 19 (depends on 18)

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.

### Claim 20 (depends on 16)

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.

### Claim 21 (depends on 20)

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.

### Claim 22 (depends on 20)

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.

### Claim 23 (depends on 16)

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.

### Claim 24 (depends on 23)

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.

### Claim 25 (depends on 14)

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.

### Claim 26 (depends on 14)

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.

### Claim 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.

### Claim 28 (depends on 27)

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.

### Claim 29 (depends on 28)

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.

### Claim 30 (depends on 29)

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.

### Claim 31 (depends on 29)

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

### Claim 32 (depends on 29)

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.

### Claim 33 (depends on 29)

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.

### Claim 34 (depends on 33)

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.

### Claim 35 (depends on 33)

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.

### Claim 36 (depends on 29)

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.

### Claim 37 (depends on 36)

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.

### Claim 38 (depends on 29)

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.

### Claim 39 (depends on 29)

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.
