Address validating data structure used for validating addresses

• US 20050238009A1
• Filed: 04/26/2004
• Published: 10/27/2005
• Est. Priority Date: 04/26/2004
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Bell, Carol A.
• Granted Patent: US 7,505,460 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/35 involving non-standard use of addresses for implementing network functionalities, e.g. coding subscription information within the address or functional addressing, i.e. assigning an address to a function
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503
• CPC Class Codes: H04L 69/168 specially adapted for link layer protocols, e.g. asynchronous transfer mode [ATM], synchronous optical network [SONET] or point-to-point protocol [PPP]

Abstract

Provided is an address validating data structure used for validating addresses. A data structure comprising a plurality of arrays is buffered. Each array includes a plurality of words, wherein one word in each array indicates address words in the array having valid addresses. At least one mask word provides mask information for at least one address word having a valid address, wherein the mask information for one address word indicates bits in the address word. The data structure is used to validate an address received from a transmitting node.

Claims

1. A method, comprising:

buffering a data structure comprising a plurality of arrays, wherein each array includes a plurality of words, wherein one word in each array indicates address words in the array having valid addresses, wherein at least one mask word provides mask information for at least one address word having a valid address, wherein the mask information for one address word indicates bits in the address word; and

using the data structure to validate an address received from a transmitting node.

2. The method of claim 1, wherein at least one mask word provides mask information for a plurality of address words having valid addresses.

3. The method of claim 2, wherein the mask word provides mask values for a plurality of address words, wherein the mask value for one address word indicates bits in the word used to validate the address received from the transmitting node.

4. The method of claim 1, wherein each array is enabled to be read in a single memory read operation.

5. The method of claim 1, wherein each array indicates in one word a next array if there is one next array in the data structure.

6. The method of claim 5, wherein the word in each array indicating valid word addresses also indicates the next array if there is one next array.

7. The method of claim 1, wherein using the data structure to validate the received address comprises:

accessing one array in the data structure;

determining from the word indicating valid addresses those address words having valid addresses in the array; and

validating the received address in response to determining that one address word in the array matches bits in the received address indicated in the mask information for the matching address word.

8. The method of claim 7, wherein the array comprises a current array, further comprising:

accessing a next array in the data structure if there is one next array to determine whether one address word in the next array matches bits in the received address indicated in the mask information for the matching address word in response to determining that the received address does not match one address in the current array, and wherein the received address is not validated if one matching address word is not located after processing all address words in a last array.

9. The method of claim 1, wherein the received address comprises a source address in a header for a first network protocol encapsulating a message further encapsulated in a second network protocol, further comprising:

decapsulating the message encapsulated in the first network protocol yielding the message encapsulated in the second network protocol in response to validating the source address; and

forwarding the decapsulated message in the second network protocol for transmission to a network implementing the second network protocol.

10. The method of claim 9, wherein the first network protocol comprises Internet Protocol version 4 (IPv4) and the second network protocol comprises Internet Protocol version 6 (IPv6), wherein the source packet is received from a transmitting router by a receiving router, wherein the transmitting and receiving router are connected via an IPv4 tunnel and communicate IPv6 packets by encapsulating the IPv6 packets within an IPv4 header.

11. A network processor in communication with a transmitting node, comprising:

a buffer; and

circuitry enabled to;

(i) store in the buffer a data structure comprising a plurality of arrays, wherein each array includes a plurality of words, wherein one word in each array indicates address words in the array having valid addresses, wherein at least one mask word provides mask information for at least one address word having a valid address, wherein the mask information for one address word indicates bits in the address word; and

(ii) use the data structure to validate an address received from the transmitting node.

12. The network processor of claim 11, wherein at least one mask word provides mask information for a plurality of address words having valid addresses.

13. The network processor of claim 12, wherein the mask word provides mask values for a plurality of address words, wherein the mask value for one address word indicates bits in the word used to validate the address received from the transmitting node.

14. The network processor of claim 11, wherein each array is enabled to be read in a-single memory read operation.

15. The network processor of claim 11, wherein each array indicates in one word a next array if there is one next array in the data structure.

16. The network processor of claim 15, wherein the word in each array indicating valid word addresses also indicates the next array if there is one next array.

17. The network processor of claim 11, wherein using the data structure to validate the received address comprises:

accessing one array in the data structure;

determining from the word indicating valid addresses those address words having valid addresses in the array; and

validating the received address in response to determining that one address word in the array matches bits in the received address indicated in the mask information for the matching address word.

18. The network processor of claim 17, wherein the array comprises a current array, wherein the circuitry is further enabled to:

access a next array in the data structure if there is one next array to determine whether one address word in the next array matches bits in the received address indicated in the mask information for the matching address word in response to determining that the received address does not match one address in the current array, and wherein the received address is not validated if one matching address word is not located after processing all address words in a last array.

19. The network processor of claim 11, wherein the network processor is in communication with a network, wherein the received address comprises a source address in a header for a first network protocol encapsulating a message further encapsulated in a second network protocol, wherein the circuitry is further enabled to:

decapsulate the message encapsulated in the first network protocol yielding the message encapsulated in the second network protocol in response to validating the source address; and

forward the decapsulated message in the second network protocol for transmission to the network implementing the second network protocol.

20. The network processor of claim 19, wherein the first network protocol comprises Internet Protocol version 4 (IPv4) and the second network protocol comprises Internet Protocol version 6 (IPv6), wherein the source packet is received from a transmitting router by a receiving router, wherein the transmitting and receiving router are connected via an IPv4 tunnel and communicate IPv6 packets by encapsulating the IPv6 packets within an IPv4 header.

21. A network device in communication with a transmitting node, comprising:

a plurality of line cards, wherein at least one of the line cards includes;

(i) a buffer; and

(ii) circuitry enabled to;

(A) store in the buffer a data structure comprising a plurality of arrays, wherein each array includes a plurality of words, wherein one word in each array indicates address words in the array having valid addresses, wherein at least one mask word provides mask information for at least one address word having a valid address, wherein the mask information for one address word indicates bits in the address word; and

(B) use the data structure to validate an address received from the transmitting node; and

a switch fabric enabling communication among the line cards;

22. The network processor of claim 21, wherein at least one mask word provides mask information for a plurality of address words having valid addresses.

23. An article of manufacture to receive data from a transmitting node, wherein the article of manufacture causes operations to be performed, the operations comprising:

buffer a data structure comprising a plurality of arrays, wherein each array includes a plurality of words, wherein one word in each array indicates address words in the array having valid addresses, wherein at least one mask word provides mask information for at least one address word having a valid address, wherein the mask information for one address word indicates bits in the address word; and

use the data structure to validate an address received from the transmitting node.

24. The article of manufacture of claim 23, wherein at least one mask word provides mask information for a plurality of address words having valid addresses.

25. The article of manufacture of claim 24, wherein the mask word provides mask values for a plurality of address words, wherein the mask value for one address word indicates bits in the word used to validate the address received from the transmitting node.

26. The article of manufacture of claim 23, wherein each array is enabled to be read in a single memory read operation.

27. The article of manufacture of claim 23, wherein each array indicates in one word a next array if there is one next array in the data structure.

28. The article of manufacture of claim 27, wherein the word in each array indicating valid word addresses also indicates the next array if there is one next array.

29. The article of manufacture of claim 23, wherein using the data structure to validate the received address comprises:

accessing one array in the data structure;

determining from the word indicating valid addresses those address words having valid addresses in the array; and

validating the received address in response to determining that one address word in the array matches bits in the received address indicated in the mask information for the matching address word.

30. The article of manufacture of claim 29, wherein the array comprises a current array, wherein the article of manufacture is further enabled to:

access a next array in the data structure if there is one next array to determine whether one address word in the next array matches bits in the received address indicated in the mask information for the matching address word in response to determining that the received address does not match one address in the current array, and wherein the received address is not validated if one matching address word is not located after processing all address words in a last array.

31. The article of manufacture of claim 23, wherein the received address comprises a source address in a header for a first network protocol encapsulating a message further encapsulated in a second network protocol, wherein the article of manufacture is further enabled to:

decapsulate the message encapsulated in the first network protocol yielding the message encapsulated in the second network protocol in response to validating the source address; and

forward the decapsulated message in the second network protocol for transmission to a network implementing the second network protocol.

32. The article of manufacture of claim 31, wherein the first network protocol comprises Internet Protocol version 4 (IPv4) and the second network protocol comprises Internet Protocol version 6 (IPv6), wherein the source packet is received from a transmitting router by a receiving router, wherein the transmitting and receiving router are connected via an IPv4 tunnel and communicate IPv6 packets by encapsulating the IPv6 packets within an IPv4 header.

33. An article of manufacture enabled to receive data from a transmitting node and in communication with a network, wherein the article of manufacture is further enabled to:

buffer a data structure comprising a plurality of arrays, wherein each array includes a plurality of words, wherein one word in each array indicates address words in the array having valid addresses, wherein at least one mask word provides mask information for at least one address word having a valid address, wherein the mask information for one address word indicates bits in the address word;

receive from the transmitting node a source address in a header conforming to a first version of a network protocol encapsulating a message further encapsulated in a second version of the network protocol;

use the data structure to validate the received source address;

decapsulating the message encapsulated in the first version of the network protocol yielding the message encapsulated in the second version of the network protocol in response to validating the source address; and

forward the decapsulated message in the second version of the network protocol for transmission to the network implementing the second version of the network protocol.

34. The article of manufacture of claim 33, wherein the first version of the network protocol comprises Internet Protocol version 4 (IPv4) and wherein the second version of the network protocol comprises Internet Protocol version 6 (IPv6).