Method and device for routing or compressing packets destination address containing classless address

• US 7,289,502 B1
• Filed: 10/04/2000
• Issued: 10/30/2007
• Est. Priority Date: 10/04/2000
• Status: Expired due to Fees

• Current Assignee: Italtel SPA (Italtel Group SPA)
• Original Assignee: Italtel SPA (Italtel Group SPA)
• Inventors: Crudo, Salvatore Matteo, Gemelli, Riccardo, Pavesi, Marco
• Primary Examiner(s): Yao; Kwang Bin
• Assistant Examiner(s): Wong; Warner
• Application Number:
  US10/148,796
• Time in Patent Office: 2,582 Days
• Field of Search: 370/393, 370/475, 37039531-39532, 370/401, 370/427, 370/521, 370/477
• 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: H04L 45/742 Route cache; Operation thereof

Abstract

The invention relates to a method of routing or compressing packets destination address through an electronic routing or compressing device, the packets destination address being n bit packets and having address indicative of a desired destination, the address being classless, the routing device having at least a data base of prefix entries, each of which containing entries corresponding to a desired output data link, the method having the steps of: a) generating an address mask until an entry matching a masked address obtained by making an AND operation between the packets destination address and the address mask, is found in the data; the address mask having a number of bit equal to that of the packets destination address and having, starting from the most significant n-bit equal to 1 and the remaining i bit equal to 0, with 0<=u<=b.1, with the first generated mask having i=0 or i=1, b) if a match is found, stopping the generation of masked address and outputting the output data link corresponding to the match, c) if no match is found, outputting a message indicating that no output data link was found.

Claims

1. A method of routing packets with a destination address (2, 2A, 2B) through an electronic routing device, said packets destination address comprises bit packets and wherein said address is a classless address indicative of a desired destination, said routing device having at least a database (10) of prefix entries, said entries corresponding to a desired output data link, wherein said method for each packet destination address (2, 2A, 2B) comprises the steps of:

generating an address mask (3, 3A, 3B-C, 6A-I) having a number of bits equal to that of the packets destination address (2, DA, 2B) and comprising two portions;

a first portion (14, 14A) starting from bit 0 (MSB) and ending with a bit (n−

1)−

i, and a second portion (15, 15A) starting from bit n−

i and ending with bit n−

1, wherein the first portion (14,14A) comprises only a non masking value and the second portion (15, 15A) comprises only a masking value,

i being an integer comprised between 0 and n−

1,

wherein i=0 in the first iteration, and i being incremented by one for each subsequent iteration until a match is found or it has reached a fixed value (n−

1);

continuing to generate an address mask (3, 3A, 3B-C, 6A-1) until an entry, matching a masked address (1, 1A) obtained by performing a masking operation on said packet destination address (2, 2A, 2B) and said address mask (3, 3A, 3B-C, 6A-1), is found in said data base (10);

wherein said masking operation is an AND operation if a masking value is 0 and a non masking value 1, said masking operation is an OR operation if the masking value is 1 and the not masking value 0, and the packets destination address and the address mask are negated before being inputted to the OR operation and the output of said OR operation is negated;

stopping, if a match is found, said generation of address masks (3, 3A, 3B-C, 6A-I) and outputting the output data link corresponding to said match; and

outputting, if no match is found or i is equal to said fixed value (Nbit), a message indicating that no output data link was found.

3. Method according to claim 1 wherein the fixed value (Nbit) is the smallest bit index of the IP network portion of the packets destination address (2, 2A, 2B).

4. Method according to claim 1 wherein the matching between the data base entry and the masked address (1, 1A) is an exact prefix matching.

5. Method according to claim 1 wherein the matching between the data base entry and the masked address (1, 1A) is a best prefix matching.

6. Method according to claim 1 wherein a predictable duration routing or compression method is used.

7. Method according to claim 6 wherein a pipelined compression algorithm is used.

8. Method according to claim 6 wherein a CSSA clustered sequential search algorithm is used.

9. Method according to claim 1 wherein at every clock cycle an address mask (3, 3A, 3B-C, 6A-I) is generated.

10. Method according to claim 1 wherein at every clock cycle a masked address (1, 1A) obtained by making a masking operation between the current packets destination address (2, 2A, 2B) and the address mask (3, 3A, 3B-C, 6A-I), corresponding to the current clock cycle is generated.

11. Method according to claim 10 wherein at every clock cycle the masked address (1, 1A) is inputted to a routing or compression algorithm.

12. Method according to claim 1, wherein:

a) the masked address (1, 1A) is scanned starting from the bit corresponding to the last bit set to a masking value in the address mask (3, 3A, 3B-C, 6A-I) to search for a string of adjacent masking values and as soon as a bit corresponding to a said first portion comprising the non masking value is found the search is stopped;

b) all the bits of the address mask (3, 3A, 3B-C, 6A-1) having corresponding positions to the bit of the masked address (1, 1A) found at masking value at previous step are set to masking values,

c) the masked address (1, 1A) is updated, by performing an AND operation on the packet destination address (2, 2A, 2B) and the address mask (3, 3A, 3B-C, 6A-I) if the masking value is 0 or an OR operation on the packet destination address (2, 2A, 2B) and the address mask (3, 3A, 3B-C, 6A-I) if the masking value is 1.

13. Method according to claim 12 wherein previous to the scanning of the masked address (1, 1A) the clustered sequential search algorithm is performed on the masked address (1, 1A) and then the next bit of the address mask (3, 3A, 3B-C, 6A-I) is set to a masking value.

14. Method according to claim 1, wherein every time the packet destination address (2, 2A, 2B) to be masked includes the entire pattern of adjacent masking values of any length, the masking process is done in a single step instead of step by step.

2. A method of compressing packets with a destination address (2, 2A, 2B) through an electronic compressing device, said packets destination address comprising bit packets and wherein said address is a classless address indicative of a desired destination, said compressing device having at least a database (10) of prefix entries, each of which containing entries corresponding to a desired output data link, wherein said method for each packet destination address (2, 2A, 2B) comprises the steps of:

generating an address mask (3, 3A, 3B-C, 6A-I), having a number of bits equal to that of the packets destination address (2, 2A, 2B) and comprising two portions;

a first portion (14, 14A) starting from bit 0 and ending with a bit (n−

1)−

i, and a second portion (15, 15A) starting from bit n−

i and ending with bit n−

1, wherein the first portion (14, 14A) comprises only a not masking value and the second portion (15, 15A) comprises only a masking value,

wherein i is an integer between 0 and n−

1;

wherein i=0 in the first iteration, and i being incremented by one for each subsequent iteration until a match is found or it has reached a fixed value (n−

1);

continuing to generate an address mask (3, 3A, 3B-C, 6A-I) until an entry, matching a masked address (1, 1A), obtained by performing a masking operation on said packet destination address (2, 2A, 2B) and said address mask (3, 3A, 3B-C, 6A-I), is found in said data base (10);

wherein said masking operation is an AND operation if a masking value is 0 and a not masking value 1; and

the not masking value 0, and the packets destination address and the address mask are negated before being inputted to the OR operation and the output of said OR operation is negated;

stopping, if a match is found, said generation of address masks (3, 3A, 3B-C, 6A-I) and outputting the output data link corresponding to said match; and

outputting, if no match is found or i is equal to said fixed value (Nbit), a message indicating that no output data link was found.

15. Routing device for routing packets with a destination address (2, 2A, 2B), said packets destination address comprising bit packets and a classless address indicative of a desired destination, said routing device comprising at least a database (10) of prefix entries, each of which containing entries corresponding to a desired output data link, comprising:

means (11, 13) for generating an address mask (3, 3A, 3B-C, 6A-I) having a number of bits equal to that of the packets destination address (2, 2A, 2B) and comprising two portions;

a first portion (14, 14A) starting from bit 0 and ending with a bit (n−

1)−

i, and a second portion (15, 15A) starting from bit n−

i and ending with bit n−

1;

wherein the first portion (14, 14A) comprises only a not masking value and the second portion (15, 15A) comprises only a masking value, i being an integer comprised between 0 and n−

1;

means (12) for generating a masked address (1, 1A) obtained by performing a masking operation on said packet destination address (2, 2A, 2B) and said address mask (3, 3A, 3B-C, 6A-I) said masking operation is an AND operation if a masking value is 0 and a not masking value 1;

said masking operation is an OR operation if the masking value is 1 and the not masking value 0, and the packet destination address and the mask are negated before being inputted to the OR operation and the output of said OR operation is negated;

means (9) for searching in said database (10) for an entry matching the current masked address;

control means (11) for creating a first address mask comprising only said first part wherein i=0 in the first iteration, and for generating said masked address and for making said search until an entry matching said masked address is found in said data base or no match is found, said control means incrementing i until a match is found or it has reached a fixed value (Nbit), and if found outputting the found output data link corresponding to the matching entry.

17. Device according to claim 15 wherein the searching means (9) are exact prefix searching means.

18. Device according to claim 15 wherein the searching means (9) are best prefix searching means.

19. Device according to claim 15, wherein the searching means (9) are pipelined searching means.

20. Device according to claim 15 wherein the means (12) for generating a masked address (1, 1A) generate a new masked address at every clock cycle.

21. Device according to claim 15 wherein the means (11, 13) for generating an address mask (3, 3A, 3B-C, 6A-I) generate a new address mask every clock cycle.

22. Device according to claim 15 wherein at every clock cycle the masked address (1, 1A) is inputted to the searching means (9).

23. Device according to claim 15 comprising:

means for scanning the masked address (1, 1A) starting from the bit corresponding to the last bit set to a masking value in the address mask (3, 3A, 3B-C, 6A-I);

means for searching for a string of adjacent masking values, said searching means interrupting the search as soon as a bit set to a non masking value is found, means for setting to a masking value all the bits of the address mask (3, 3A, 3B-C, 6A-I) having corresponding positions to the bit of the masked address (1, 1A) found at masking value by said searching means; and

means for updating the masked address (1, 1A) by making an AND operation between the packet destination address (2, 2A, 2B) and the address mask (3, 3A, 3B-C, 6A-I) if the masking value is 0 or an OR operating between the packet destination address (2, 2A, 2B) and the address mask (3, 3A, 3B-C, 6A-I) if the masking value is 1.

24. Device according to claim 23 wherein previous to the scanning means there are provided means for performing the clustered sequential search algorithm over the masked address (1, 1A) and means for setting the next bit of the address mask (3, 3A, 3B-C, 6A-I) to a masking value.

16. Compression device for compressing packets with a destination address (2, 2A, 2B), said packets destination address comprising n bit packets and a classless address indicative of a desired destination, and compressing device having at least a database (10) of prefix entries, each of which containing entries corresponding to a desired output data link, comprising:

means (11, 13) for generating an address mask (3, 3A, 3B-C, 6A-I) having a number of bits equal to that of the packets destination address (2, 2A, 2B) and comprising two portions;

a first portion (14, 14A) starting from bit 0 and ending with a bit (n−

i)−

i, and a second portion (15, 15A) starting from bit n−

i and ending with bit n−

1;

wherein the first portion (14, 14A) comprises only a not masking value and the second portion (15, 15A) comprises only a masking value, i being an integer comprised between 0 and n−

1;

means (12) for generating a masked address (1, 1A) obtained by performing a masking operation on said packet destination address (2, 2A, 2B) and said address mask (3, 3A, 3B-C, 6A-I), said masking operation is an AND operation if a masking value is 0 and a not masking value 1;

said masking operation is an OR operation if;

the masking value is 1 and the not masking value 0, and the packet destination address and the address mask are negated before being inputted to the OR operation and the output of said OR operation is negated;

means (9) for searching in said database (10) for an entry matching the current masked address; and

control means (11) for creating a first address mask comprising only said first part wherein i=0 in the first iteration, and for generating said masked address and for making said search until an entry matching said masked address is found in said data base or no match is found, said control means incrementing i until a match is found or i has reached a fixed value (Nbit), and if found, outputting the output data link corresponding to the matching entry.