Arrangement for searching packet policies using multi-key hash searches in a network switch

• US 6,950,434 B1
• Filed: 02/01/2000
• Issued: 09/27/2005
• Est. Priority Date: 12/07/1999
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Viswanath, Somnath, Krishna, Gopal
• Primary Examiner(s): Vu, Huy D.
• Assistant Examiner(s): RYMAN, DANIEL J
• Application Number:
  US09/496,212
• Time in Patent Office: 2,065 Days
• Field of Search: 370/389, 370/392, 370/395.31, 370/395.32, 370/395.7, 211/216, 211/200
• US Class Current: 370/392
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/351 for local area network [LAN], e.g. Ethernet switches
• CPC Class Codes: H04L 49/602 Multilayer or multiprotocol switching, e.g. IP switching

Abstract

A network switch, configured for performing layer 2 and layer 3 switching in an Ethernet (IEEE 802.3) network without blocking of incoming data packets, includes network switch ports, each including a flow module configured for generating a packet signature based on layer 3 information within a received data packet. The flow module generates first and second hash keys according to a prescribed hashing function upon obtaining first and second portions of layer 3 information. The flow module combines the first and second hash keys to form the packet signature, and searches an on-chip signature table that indexes addresses of layer 3 switching entries by entry signatures, where the entry signatures are generated using the same prescribed hashing function on the first and second layer 3 portions of the layer 3 switching entries.

Claims

1. A method in a network switch of searching for a selected layer 3 switching entry for a received data packet, the method comprising:

generating first and second hash keys according to a prescribed hash function in response to first and second layer 3 information within the received data packet, respectively;

combining the first and second hash keys according to a prescribed combination into a signature for the received data packet; and

searching, by the network switch, a table, configured for storing layer 3 signatures that index respective layer 3 switching entries according to the prescribed hash function and the prescribed combination, for the selected layer 3 switching entry based on a match between the corresponding layer 3 signature and the signature for the received data packet.

2. The method of claim 1, wherein received data packet includes an Internet Protocol (IP) header, the generating step including detecting the first and second layer 3 information from the IP header as the data packet is received by a corresponding network switch port.

3. The method of claim 2, wherein the detecting step includes selecting at least two of an IP source address, an IP destination address, a Transmission Control Protocol (TCP) source port, a TCP destination port, a User Datagram Protocol (UDP) source port, and a UDP destination port as the first and second layer 3 information from the IP header based on elements of each of the layer 3 switching entries used to generate the corresponding layer 3 signature.

4. The method of claim 1, further comprising verifying whether the selected layer 3 switching entry matches the received data packet.

5. The method of claim 4, wherein the verifying step includes:

fetching the first and second layer 3 information from the selected layer 3 switching entry; and

determining whether the first and second layer 3 information from the selected layer 3 switching entry matches the first and second layer 3 information within the received data packet.

6. The method of claim 1, further comprising:

detecting a group of the layer 3 switching entries, each having a corresponding layer 3 signature that matches the signature for the received data packet; and

verifying one entry from the group of the layer 3 switching entries matches the received data packet.

7. The method of claim 6, wherein the verifying step includes:

fetching the first and second layer 3 information for each of the entries of the group of layer 3 switching entries; and

identifying the one entry having the corresponding first and second layer 3 information that matches the first and second layer 3 information within the received data packet.

8. The method of claim 7, wherein the network switch is an integrated circuit chip, the searching step including searching a signature table located on the integrated circuit chip, and the fetching step including accessing the first and second layer 3 information from a policy table in a memory external to the integrated circuit chip.

9. The method of claim 1, further comprising forwarding an identifier specifying the selected layer 3 switching entry from a network switch port, having received the received data packet, to layer 3 switching logic within the network switch.

10. The method of claim 1, wherein the network switch and the table are implemented on a single chip, the generating first and second hash keys, the combining the first and second hash keys, and the searching the table each being performed by the network switch.

11. A method of identifying a layer 3 switching decision within an integrated network switch having a plurality of network switch ports and switching logic, the method including:

storing, in a first table, layer 3 switching entries that identify data packet types based on layer 3 information, respectively, each layer 3 switching entry identifying a corresponding layer 3 switching decision to be performed by the integrated network switch;

generating an entry signature for each of the layer 3 switching entries based on a prescribed hash operation performed on first and second portions of the corresponding layer 3 information based on;

(1) generating first and second hash keys for the first and second portions of the corresponding layer 3 information in the layer 3 switching entry based on the prescribed hash operation; and

(2) combining the first and second hash keys to form the entry signature;

generating a packet signature by a network switch port of the integrated network switch for a data packet received at the network switch port based on performing the prescribed hash operation on the first and second portions of the layer 3 information in the corresponding received data packet; and

identifying by the network switch port one of the layer 3 switching entries for switching of the received data packet based on detecting a match between the packet signature and the corresponding entry signature;

wherein the integrated network switch is implemented on a single chip.

12. The method of claim 11, wherein the step of generating an entry signature includes:

selecting at least two of an IP source address, an IP destination address, a Transmission Control Protocol (TCP) source port, a TCP destination port, a User Datagram Protocol (UDP) source port, and a UDP destination port as the first and second portions of the corresponding layer 3 information.

13. The method of claim 12, wherein the step of generating a packet signature includes:

selecting the at least two of an IP source address, an IP destination address, a Transmission Control Protocol (TCP) source port, a TCP destination port, a User Datagram Protocol (UDP) source port, and a UDP destination port as the first and second portions of the corresponding layer 3 information in the received data packet;

generating third and fourth hash keys for the first and second portions of the corresponding layer 3 information in the received data packet based on the prescribed hash operation; and

combining the third and fourth keys to form the packet signature.

14. The method of claim 11, wherein the step of identifying one of the layer 3 switching entries includes:

searching a signature table within the integrated network switch for one of the entry signatures matching the packet signature;

retrieving from the signature table an address location of the one layer 3 switching entry corresponding to the matched entry signature; and

accessing the one layer 3 switching entry from an external memory based on the retrieved address location.

15. The method of claim 14, wherein the step of identifying the one layer 3 switching entry includes verifying that the one layer 3 switching entry matches the received data packet.

16. An integrated network switch configured for executing layer 3 switching decisions, comprising:

an index table that includes addresses of layer 3 switching entries that identify respective data packet types based on layer 3 information, the index table also including for each address entry a corresponding entry signature representing a combination of selected first and second portions of the corresponding layer 3 information hashed according to a prescribed hashing operation;

a plurality of network switch ports, each comprising;

(1) a frame identifier configured for obtaining the first and second portions of layer 3 information within a data packet being received by the network switch port, and

(2) a flow module configured for generating a packet signature by generating first and second hash keys for the first and second portions from the data packet based on a prescribed hash operation, the flow module identifying one of the layer 3 switching entries for execution of the corresponding layer 3 switching decision for the data packet based on a determined correlation between the packet signature and the corresponding entry signature; and

layer 3 switching logic for executing the layer 3 switching decision for the data packet based on the corresponding identified one layer 3 switching entry;

wherein the integrated network switch is implemented on a single chip.

17. The switch of claim 16, wherein the flow module, in response to determining the correlation between the packet signature and the entry signature, fetches selected portions of the layer 3 information from the one layer 3 switching entry for verification that the one layer 3 switching entry matches the data packet.

18. The switch of claim 16, wherein the frame identifier selects at least two of an IP source address, and IP destination address, a Transmission Control Protocol (TCP) source port, a TCP destination port, a User Datagram Protocol (UDP) source port, and a UDP destination port as the first and second portions of layer 3 information within the data packet.

19. The switch of claim 16, further comprising an external memory interface configured for providing access by the flow module to the one layer 3 switching entry, stored in a memory external to the integrated network switch, based on the corresponding address entry.

20. The switch of claim 16, wherein the flow module is configured for generating the packet signature based on combining the first and second hash keys.