Method and apparatus for multiprotocol switching and routing

• US 6,876,654 B1
• Filed: 04/10/1998
• Issued: 04/05/2005
• Est. Priority Date: 04/10/1998
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Hegde, Gopal Dattaray
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/058,335
• Time in Patent Office: 2,552 Days
• Field of Search: 370/392, 370/393, 370/401, 370/466, 370/378, 370/379, 370/382, 370/400, 370/402, 370/465, 370/467
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge

Abstract

A packet forwarding method and apparatus performs multiprotocol routing (for IP and IPX protocols) and switching. Incoming data packets are examined and the flow (i.e., source and destination addresses and source and destination socket numbers) with which they are associated is determined. A flow table contains forwarding information that can be applied to the flow. If an entry is not present in the table for the particular flow, the packet is forwarded to the CPU to be processed. The CPU can then update the table with new forwarding information to be applied to all future packets belonging to the same flow. When the forwarding information is already present in the table, packets can thus be forwarded at wire speed. A dedicated ASIC is preferably employed to contain the table, as well as the engine for examining the packets and forwarding them according to the stored information. Decision-making tasks are thus more efficiently partitioned between the switch and the CPU so as to minimize processing overhead.

Claims

1. An apparatus for forwarding packets between ports, said ports including a first port associated with a first host having a first layer 2 address and a first layer 3 address, and a second port associated with a second host having a second layer 2 address and a second layer 3 address, a layer 2 flow of packets between said first and second hosts being based on said first and second layer 2 addresses, a layer 3 flow of packets between said first and second hosts being based on said first and second layer 3 addresses, said apparatus comprising:

a flow table comprising a plurality of address resolution records stored in an address resolution record table including;

a first address resolution record that corresponds said first port with said first layer 2 address,

a second address resolution record that corresponds said first port with said first layer 3 address,

a third address resolution record that corresponds said second port with said second layer 2 address, and

a fourth address resolution record that corresponds said second port with said second layer 3 address, wherein said first and second hosts have first and second sockets, respectively, said layer 3 flow being further based on said first and second sockets, said second address resolution record further corresponding said first port with said first socket, said fourth address resolution record further corresponding said second port with said second socket;

a switch module coupled to said ports and said flow table that detects said layer 2 flow arriving at one of said first and second ports, and forwards packets belonging thereto to the other of said first and second ports based on said first and third address resolution records, said switch module also detecting said layer 3 flow arriving at one of said first and second ports, and forwards packets belonging thereto to the other of said first and second ports based on said second and fourth address resolution records;

a CPU coupled to said flow table and communicating with said switch module, said CPU creating said first, second, third and fourth address resolution records in said address resolution record table;

a switch engine that determines whether said first and third address resolution records exist in said address resolution record table when said first flow is detected, and whether said second and fourth address resolution records exist in said address resolution record table when said second flow is detected; and

a CPU interface that sends a first message to said CPU when said first flow is detected and said switch engine determines that said first and third address resolution records do not exist in said address resolution record table, said CPU interface sends a second message to said CPU when said second flow is detected and said switch engine determines that said second and fourth address resolution records do not exist in said address resolution record table, said CPU creating said first and third address resolution records in response to said first message, and said second and fourth address resolution records in response to said second message, wherein said flow table further includes an address resolution hash table comprising a plurality of address resolution hash records including;

a first address resolution hash record that corresponds a portion of said first layer 2 address with said first address resolution record;

a second address resolution hash record that corresponds a portion of said first layer 3 address with said second address resolution record;

a third address resolution hash record that corresponds a portion of said second layer 2 address with said third address resolution record; and

a fourth address resolution hash record that corresponds a portion of said second layer 3 address with said fourth address resolution record,

said switch module accessing said first, second, third and fourth address resolution records in accordance with said corresponding portions of said addresses and said first, second, third and fourth address resolution record hash records, respectively,

said CPU linking said first and third address resolution hash records with said first and third address resolution records, respectively, in response to said first message, and linking said second and fourth address resolution hash records with said second and fourth address resolution records, respectively, in response to said second message.

2. An apparatus as defined in claim 1, wherein said switch module is comprised of an ASIC.

3. An apparatus as defined in claim 1, wherein said switch module and said flow table are together comprised of an ASIC.

4. An apparatus as defined in claim 1, wherein said first and second hosts belong to different networks.

5. An apparatus as defined in claim 1, wherein said layer 3 flow is in accordance with one of IP and IPX protocols.

6. An apparatus as defined in claim 5, wherein said layer 2 flow is in accordance with all protocols except IP and IPX.

7. A method of forwarding packets between ports of a switch, said ports being associated with hosts having addresses, said method comprising:

identifying a first address of a first one of said hosts;

identifying a first port associated with said first host;

creating a record that corresponds said first address with said first port;

storing said record in a table;

linking said record to a hash;

associating said hash with a portion of said first address;

receiving a data packet at a second port;

extracting said first address from said data packet;

retrieving said record by hashing onto said table using said portion of said first address; and

forwarding said data packet to said first port in accordance with said record;

corresponding a swap address with said record;

receiving a second data packet at a third port;

routing said second data packet by forwarding said second data packet to said third port in accordance with said record and swapping a second address, the second address within said second data packet, with said swap address in accordance with said record.

8. A method as defined in claim 7, further comprising:

identifying a third address of a second one of said hosts, said second port associated with said second host;

creating a second record that corresponds said third address with said second port;

storing said second record in said table;

linking said second record to said hash;

associating said hash with a portion of said third address;

sorting said first and second records in said table based on said first and third addresses;

receiving a third data packet at the first port;

extracting said third address from said third data packet;

retrieving said second record by hashing onto said table using said portion of said third address and searching among said first and second records based on said third address; and

forwarding said third data packet to said second port in accordance with said second record.

9. A method as defined in claim 7, wherein said second port is associated with a second one of said hosts, said first and second hosts belonging to different networks.

10. A method of forwarding packets between ports of a switch, said ports including a first port associated with a first host having a first layer 2 address and a first layer 3 address, and a second port associated with a second host having a second layer 2 address and a second layer 3 address, a layer 2 flow of packets between said first and second hosts being based on said first and second layer 2 addresses, a layer 3 flow of packets between said first a id second hosts being based on said first and second layer 3 addresses, said method comprising:

preparing a first address resolution record in a flow table that corresponds said first port with said first layer 2 address;

preparing a second address resolution record in said flow table that corresponds said first port with said first layer 3 address;

preparing a third address resolution record in said flow table that corresponds said second port with said second layer 2 address;

preparing a fourth address resolution record in said flow table that corresponds said second port with said second layer 3 address;

detecting said layer 2 flow arriving at one of said first and second ports and forwarding packets belonging thereto to the other of said first and second ports based on said first and third address resolution records;

detecting said layer 3 flow arriving at one of said first and second ports, and forwarding packets belonging thereto to the other of said first and second ports based on said second and fourth address resolution records;

determining wt ether said first and third address resolution records exist in said flow table when said layer 2 flow is detected;

determining whether said second and fourth address resolution records exist in said flow table when said layer 3 flow is detected;

creating said first and third address resolution records when said layer 2 flow is detected and when it is determined that said first and third address resolution records do not exist in said flow table;

creating said second and fourth address resolution records when said layer 3 flow is detected and when it is determined that said second and fourth address resolution records do not exist in said flow table;

preparing a first address resolution hash record in said flow table that corresponds a portion of said first layer 2 address with said first address resolution record;

preparing a second address resolution hash record in said flow table that corresponds a portion of said first layer 3 address with said first address resolution record;

preparing a third address resolution hash record in said flow table that corresponds a portion of said second layer 2 address with said third address resolution record;

preparing a fourth address resolution hash record in said flow table that corresponds a portion of said second layer 3 address with said fourth address resolution record;

linking said first and third address resolution hash records with said first and third address resolution records, respectively, when said layer 2 flow is detected and when it is determined that said first and third address resolution records do not exist in said flow table; and

linking said second and fourth address resolution hash records with said second and fourth address resolution records, respectively, when said layer 3 flow is detected and when it is determined that said second and fourth address resolution records do not exist in said flow table.

11. A method as defined in claim 10, wherein said step of forwarding said packets belonging to said layer 2 flow includes accessing said first and third address resolution records in accordance with said corresponding portions of said addresses and said first and third address resolution record hash records, respectively, and wherein said step of forwarding said packets belonging to said layer 2 flow includes accessing said second and fourth address resolution records in accordance with said corresponding portions of said addresses and said second and fourth address resolution record hash records, respectively.

12. A method as defined in claim 10, wherein said layer 3 flow is in accordance with one of IP and IPX protocols.

13. A method as defined in claim 12, wherein said layer 2 flow is in accordance with all protocols except IP and IPX.

14. A method of forwarding packets between ports of a switch, said ports including a first port associated with a first host having a first layer 2 address and a first layer 3 address, and a second port associated with a second host having a second layer 2 address and a second layer 3 address, a layer 2 flow of packets between said first and second hosts being based on said first and second layer 2 addresses, a layer 3 flow of packets between said first and second hosts being based on said first and second layer 3 addresses, said method comprising:

preparing a first address resolution record in a flow table that corresponds said first port with said first layer 2 address;

preparing a second address resolution record in said flow table that corresponds said first port with said first layer 3 address;

preparing a third address resolution record in said flow table that corresponds said second port with said second layer 2 address;

preparing a fourth address resolution record in said flow table that corresponds said second port with said second layer 3 address;

detecting said layer 2 flow arriving at one of said first and second ports and forwarding packets belonging thereto to the other of said first and second ports based on said first and third address resolution records;

detecting said layer 3 flow arriving at one of said first and second ports, and forwarding packets belonging thereto to the other of said first and second ports based on said second and fourth address resolution records, wherein said first and second hosts have first and second sockets, respectively, said layer 3 flow being further based on said first and second sockets, said second address resolution record further corresponding said first port with said first socket, said fourth address resolution record further corresponding said second port with said second socket;

determining whether said first and third address resolution records exist in said flow table when said layer 2 flow is detected;

determining whether said second and fourth address resolution records exist in said flow table when said layer 3 flow is detected;

creating said first and third address resolution records when said layer 2 flow is detected and when it is determined that said first and third address resolution records do not exist in said flow table;

creating said second and fourth address resolution records when said layer 3 flow is detected and when it is determined that said second and fourth address resolution records do not exist in said flow table;

preparing a first address resolution hash record in said flow table that corresponds a portion of said first layer 2 address with said first address resolution record;

preparing a second address resolution hash record in said flow table that corresponds a portion of said first layer 3 address with said first address resolution record;

preparing a third address resolution hash record in said flow table that corresponds a portion of said second layer 2 address with said third address resolution record;

preparing a fourth address resolution hash record in said flow table that corresponds a portion of said second layer 3 address with said fourth address resolution record;

linking said first and third address resolution hash records with said first and third address resolution records, respectively, when said layer 2 flow is detected and when it is determined that said first and third address resolution records do not exist in said flow table; and

linking said second and fourth address resolution hash records with said second and fourth address resolution records, respectively, when said layer 3 flow is detected and when it is determined that said second and fourth address resolution records do not exist in said flow table.

15. A method as defined in claim 14, wherein said step of forwarding said packets belonging to said layer 2 flow includes accessing said first and third address resolution records in accordance with said corresponding portions of said addresses and said first and third address resolution record hash records, respectively, and wherein said step of forwarding said packets belonging to said layer 3 flow includes accessing said second and fourth address resolution records in accordance with said corresponding portions of said addresses and said second and fourth address resolution record hash records, respectively.

16. A method as defined in claim 14, wherein said first and second hosts belong to different networks.