Network protocol processing for routing and bridging

• US 7,359,380 B1
• Filed: 06/24/2003
• Issued: 04/15/2008
• Est. Priority Date: 06/24/2003
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Sidenblad, Paul J., Nanda, Sameer, Maufer, Thomas A., Gyugyi, Paul J.
• Primary Examiner(s): Ngo; Ricky Q.
• Assistant Examiner(s): PATEL, CHANDRAHAS B
• Application Number:
  US10/606,336
• Time in Patent Office: 1,757 Days
• Field of Search: 370/401, 370/389, 370/392
• US Class Current: 370/392
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/306 Route determination based on the nature of the carried application
• CPC Class Codes: H04L 45/60 Router architectures
• CPC Class Codes: H04L 45/742 Route cache; Operation thereof
• CPC Class Codes: H04L 61/2514 between local and global IP addresses
• CPC Class Codes: H04L 63/0236 Filtering by address, protocol, port number or service, e.g. IP-address or URL
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources

Abstract

Method and apparatus for routing and bridging are described. An address from a packet is obtained and used to find an index in a table. If the address is found in the table, the index stored in association with the address obtained. The index is stored in a data structure associated with the packet.

Claims

1. A method for routing a packet using a routing table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having an Internet Protocol destination address and a media access control destination address in a data structure, the method comprising:

determining whether a media access control destination address for the packet matches an interface of the packet;

determining whether the packet contains a routable protocol responsive to the media access control destination address matching the interface;

if the packet contains the routable protocol,

checking for layer-level validity of the packet;

marking the data structure associated with the packet to indicate the layer-level validity was checked;

checking for Internet Protocol options being supported and valid; and

marking the data structure associated with the packet to indicate the Internet Protocol options were checked for support and validity; and

if the layer-level is valid and the Internet Protocol options are supported and valid,

accessing the Internet Protocol destination address from the packet;

looking for the Internet Protocol destination address in the routing table;

obtaining an address resolution table index stored in association with the Internet Protocol destination address in the routing table responsive to the Internet Protocol destination address being found in the routing table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

storing in the data structure associated with the packet the address resolution table index obtained.

2. The method, according to claim 1, wherein the interface is an incoming interface.

3. The method, according to claim 1, wherein the interface is an outgoing interface.

4. The method, according to claim 1, wherein the routable protocol is an Internet Protocol, and wherein the Internet Protocol is version four.

5. The method, according to claim 1, wherein the routable protocol is an Internet Protocol, and wherein the Internet Protocol is version six.

6. The method, according to claim 1, further comprising:

determining whether routing is supported within a network processing unit.

7. The method, according to claim 1, wherein the address resolution table index obtained is stored in a plurality of canonical frame headers.

8. The method, according to claim 7, wherein the address resolution table index is stored in a canonical frame header of the plurality of canonical frame headers.

9. The method, according to claim 1, wherein the routing table is more compact than a general routing table.

10. The method, according to claim 1, wherein the look up is done by finding an exact match in the routing table of the Internet Protocol destination address.

11. A method for routing a packet using a routing table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having an Internet Protocol source address, an Internet Protocol destination address and a media access control destination address in a data structure, the method comprising:

determining whether the media access control destination address for the packet matches an interface of the packet;

determining whether the packet is a multicast packet and whether multicast routing is invoked responsive to the media access control destination address not matching the interface;

if the packet is a packet for multicasting and multicasting is invoked,

accessing the Internet Protocol source address from the packet; and

checking a routing table for the Internet Protocol source address;

if the routing table contains the Internet Protocol source address,

checking for layer-level validity of the packet;

marking a data structure associated with the packet to indicate the layer-level validity was checked;

checking for Internet Protocol options being supported and valid; and

marking the data structure associated with the packet to indicate the Internet Protocol options were checked for support and validity; and

if the layer-level is valid and the Internet Protocol options are supported and valid,

accessing the Internet Protocol destination address from the packet;

looking for the Internet Protocol destination address in the routing table;

obtaining an address resolution table index stored in association with the Internet Protocol destination address in the routing table responsive to the Internet Protocol destination address being found in the routing table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

storing in the data structure associated with the packet the address resolution table index obtained.

12. The method, according to claim 11, wherein the address resolution table index obtained is stored in a plurality of canonical frame headers.

13. The method, according to claim 11, wherein the routing table is substantially more compact than a general routing table.

14. The method, according to claim 11, wherein the look up is done by finding an exact match in the routing table to the destination address.

15. A method for bridging a packet using an address resolution table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having a media access control destination address in a data structure, said method comprising:

determining whether the media access control destination address for the packet matches an interface of the packet;

determining whether the packet is a multicast packet and whether multicast routing is invoked responsive to the media access control address not matching the interface; and

if the packet is not a packet for multicasting or multicasting is not invoked,

looking for the media access control destination address in an address resolution table;

obtaining an address resolution table index stored in association with the media access control destination address in the address resolution table responsive to the media access control destination address being found in the address resolution table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

storing in the data structure associated with the packet the address resolution table index obtained.

16. The method, according to claim 15, wherein the data structure is apportioned for having a canonical frame header, wherein the address resolution table index is stored in the canonical frame header.

17. The method, according to claim 15, further comprising checking whether the bridging is supported within a network processing unit.

18. A computer-readable storage medium containing a program which, when executed by a processor, causes execution of a method for routing a packet using a routing table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having an Internet Protocol destination address and a media access control destination address in a data structure, said method comprising:

determining whether a media access control destination address for the packet matches an interface of the packet;

determining whether the packet contains a routable protocol responsive to the media access control destination address matching the interface;

if the packet contains the routable protocol,

checking for layer-level validity of the packet;

marking the data structure associated with the packet to indicate the layer-level validity was checked;

checking for Internet Protocol options being supported and valid; and

marking the data structure associated with the packet to indicate the Internet Protocol options were checked for support and validity; and

if the layer-level is valid and the Internet Protocol options are supported and valid,

accessing the Internet Protocol destination address from the packet;

looking for the Internet Protocol destination address in the routing table;

obtaining an address resolution table index stored in association with the Internet Protocol destination address in the routing table responsive to the Internet Protocol destination address being found in the routing table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

storing in the data structure associated with the packet the address resolution table index obtained.

19. A computer-readable storage medium containing a program which, when executed by a processor, causes execution of a method for routing a packet using a routing table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having an Internet Protocol source address, an Internet Protocol destination address and a media access control destination address in a data structure, said method comprising:

determining whether the media access control destination address for the packet matches an interface of the packet;

determining whether the packet is a multicast packet and whether multicast routing is invoked responsive to the media access control destination address not matching the interface;

if the packet is a packet for multicasting and multicasting is invoked,

accessing the Internet Protocol source address from the packet; and

checking a routing table for the Internet Protocol source address;

if the routing table contains the Internet Protocol source address,

checking for layer-level validity of the packet;

marking a data structure associated with the packet to indicate the layer-level validity was checked;

checking for Internet Protocol options being supported and valid; and

marking the data structure associated with the packet to indicate the Internet Protocol options were checked for support and validity; and

if the layer-level is valid and the Internet Protocol options are supported and valid,

accessing the Internet Protocol destination address from the packet;

looking for the Internet Protocol destination address in the routing table;

obtaining an address resolution table index stored in association with the Internet Protocol destination address in the routing table responsive to the Internet Protocol destination address being found in the routing table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

storing in the data structure associated with the packet the address resolution table index obtained.

20. A computer-readable storage medium containing a program which, when executed by a processor, causes execution of a method for bridging a packet using an address resolution table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having a media access control destination address in a data structure, said method comprising:

determining whether the media access control destination address for the packet matches an interface of the packet;

determining whether the packet is a multicast packet and whether multicast routing is invoked responsive to the media access control address not matching the interface; and

if the packet is not a packet for multicasting or multicasting is not invoked,

looking for the media access control destination address in an address resolution table;

obtaining an address resolution table index stored in association with the media access control destination address in the address resolution table responsive to the media access control destination address being found in the address resolution table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

storing in the data structure associated with the packet the address resolution table index obtained.

21. An apparatus for routing a packet using a routing table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having an Internet Protocol destination address and a media access control destination address in a data structure, said apparatus comprising:

means for determining whether a media access control destination address for the packet matches an interface of the packet;

means for determining whether the packet contains a routable protocol responsive to the media access control destination address matching the interface;

responsive to the packet contains the routable protocol,

means for checking for layer-level validity of the packet;

means for marking the data structure associated with the packet to indicate the layer-level validity was checked;

means for checking for Internet Protocol options being supported and valid; and

means for marking the data structure associated with the packet to indicate the Internet Protocol options were checked for support and validity; and

responsive to the layer-level is valid and the Internet Protocol options are supported and valid,

means for accessing the Internet Protocol destination address from the packet;

means for looking for the Internet Protocol destination address in the routing table;

means for obtaining an address resolution table index stored in association with the Internet Protocol destination address in the routing table responsive to the Internet Protocol destination address being found in the routing table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

means for storing in the data structure associated with the packet the address resolution table index obtained.

22. An apparatus for routing a packet using a routing table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having an Internet Protocol source address, an Internet Protocol destination address and a media access control destination address in a data structure, said apparatus comprising:

means for determining whether the media access control destination address for the packet matches an interface of the packet;

means for determining whether the packet is a multicast packet and whether multicast routing is invoked responsive to the media access control destination address not matching the interface;

responsive to the packet is a packet for multicasting and multicasting is invoked,

means for accessing the Internet Protocol source address from the packet; and

means for checking a routing table for the Internet Protocol source address;

responsive to the routing table contains the Internet Protocol source address,

means for checking for layer-level validity of the packet;

means for marking a data structure associated with the packet to indicate the layer-level validity was checked;

means for checking for Internet Protocol options being supported and valid; and

means for marking the data structure associated with the packet to indicate the Internet Protocol options were checked for support and validity; and

responsive to the layer-level is valid and the Internet Protocol options are supported and valid,

means for accessing the Internet Protocol destination address from the packet;

means for looking for the Internet Protocol destination address in the routing table;

means for obtaining an address resolution table index stored in association with the Internet Protocol destination address in the routing table responsive to the Internet Protocol destination address being found in the routing table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

means for storing in the data structure associated with the packet the address resolution table index obtained.

23. An apparatus for bridging a packet using an address resolution table that is cross-linked with a state table that is indexed with an address resolution table index, the packet having a media access control destination address in a data structure, said apparatus comprising:

means for determining whether the media access control destination address for the packet matches an interface of the packet;

means for determining whether the packet is a multicast packet and whether multicast routing is invoked responsive to the media access control address not matching the interface; and

responsive to the packet is not a packet for multicasting or multicasting is not invoked,

means for looking for the media access control destination address in an address resolution table;

means for obtaining an address resolution table index stored in association with the media access control destination address in the address resolution table responsive to the media access control destination address being found in the address resolution table, wherein the address resolution table index obtained is an index into the state table for locating an entry in the state table; and

means for storing in the data structure associated with the packet the address resolution table index obtained.