Stochastic circuit identification in a multi-protocol network switch

• US 5,949,786 A
• Filed: 10/02/1996
• Issued: 09/07/1999
• Est. Priority Date: 08/15/1996
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Bellenger, Donald M.
• Primary Examiner(s): Patel, Ajit
• Application Number:
  US08/724,742
• Time in Patent Office: 1,070 Days
• Field of Search: 370/229, 370/230, 370/235, 370/236, 370/237, 370/252, 370/254, 370/400, 370/401, 370/402, 370/392, 370/466, 370/389
• US Class Current: 370/401
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• 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 flow based network switch function is based on a route cache and flow detect logic which generates hash codes for use in accessing the route cache. Flow detect logic is implemented with read-write register functions. A network switch which comprises a port for access to a communication medium to receive incoming frames. A route table memory has a set of accessible locations for storing routing information. The set of accessible locations is addressable in response to N bits, and locations in the set store a tag comprising M bits for identifying a network flow. Routing information is also stored in each of the accessible locations for the identified network flow. Flow detect logic is coupled with a port and monitors frames received by the port generate and N bit address, and an identifying tag comprising M bits for use in accessing the route table memory in response to an incoming frame on the port. Match logic is coupled with the route table memory and the flow detect logic, which accesses a particular location in the set of accessible locations in the route table memory in response to the N bit address, compares the identifying tag with the tag stored in the particular location to determine whether the incoming frame matches the network flow identified by the stored tag, and supplies the routing information for level 3 or higher stored in the particular location if a match occurs. If a match does not occur, a route table miss is indicated, and the frame is forwarded to multi-protocol routing algorithms for the purpose of generating the routing information for the incoming frame.

Claims

1. A network switch, comprising:

a port for access to a communication medium to receive incoming frames having particular frame formats;

route table memory having a set of accessible locations for storing routing information, the set of accessible locations being addressable in response to N bits, and locations in the set storing a tag comprising M bits for identifying a network flow, and storing routing information for the network flow;

flow detect logic, coupled with the port, which monitors frames received by the port and generates an N bit address and an identifying tag comprising M bits for use in accessing the route table memory in response to the particular frame format of an incoming frame; and

match logic, coupled with the route table memory and the flow detect logic, which accesses a particular location in the set of accessible locations in the route table memory in response to the N bit address, compares the identifying tag with the tag stored in the particular location to determine whether the incoming frame matches the network flow identified by the stored tag, and supplies the routing information stored in the particular location if a match occurs, else signals a route table miss.

2. The network switch of claim 1, wherein M plus N is 32 or greater.

3. The network switch of claim 1, wherein M plus N is 64 or greater.

4. The network switch of claim 1, wherein the flow detect logic includes:

logic, coupled with the port, which computes a hash value in response to a set of control fields in the incoming frame, where the set of control fields correlates with a network frame format, and applies N bits of the hash value as the N bit address, and M bits of the hash value as the identifying tag.

5. The network switch of claim 4, wherein the hash value comprises a pseudo random number seeded in response to the set of control fields in the incoming frame.

6. The network switch of claim 1, including:

logic, coupled with the match logic, for applying routing algorithms to generate route information for the incoming frame for use if a route table miss occurs.

7. The network switch of claim 1, wherein the incoming frame has a data link layer format and a network layer format, and said routing information stored in the set of accessible locations of the route table memory comprises routing information at the network layer.

8. A network switch comprising:

a port for access to a communication medium to receive incoming frames;

route table memory having a set of accessible locations for storing routing information, the set of accessible locations being addressable in response to N bits, and locations in the set storing a tag comprising M bits for identifying a network flow, and storing routing information for the network flow;

flow detect logic coupled with the port, which monitors frames received by the port and generates an N bit address and an identifying tag comprising M bits for use in accessing the route table memory in response to an incoming frame;

match logic, coupled with the route table memory and the flow detect logic, which accesses a particular location in the set of accessible locations in the route table memory in response to the N bit address, compares the identifying tag with the tag stored in the particular location to determine whether the incoming frame matches the network flow identified by the stored tag, and supplies the routing information stored in the particular location if a match occurs, else signals a route table miss,

a plurality of flow detect filters, the flow detect filters including respectively a template register which stores a mask for a particular network frame format, and logic applying the mask to the incoming frame to generate a hash seed value from the incoming frame, and a pseudo random number generator responsive to the hash seed which generates a hash; and

a selector, coupled with the plurality of flow detect filters, which selects a hash from the plurality of flow detect filters as the hash value, and applies N bits of the hash value as the N bit address, and M bits of the hash value as the identifying tag for the match logic.

9. The network switch of claim 8, wherein said template register comprises a read/write register.

10. The network switch of claim 8, wherein a flow detect filter in said plurality of flow detect filters includes:

a read/write protocol filter register which stores a protocol filter identifying a protocol for which the template register is adapted; and

mask enable logic responsive to the protocol filter which enables the logic applying the mask in response to processing the incoming frame with the protocol filter.

11. The network switch of claim 8, wherein a flow detect filter in said plurality of flow detect filters includes:

a read/write protocol hierarchy register which stores a protocol hierarchy value identifying a priority for the protocol for which the template register is adapted; and

wherein the selector is responsive to the protocol hierarchy.

12. The network switch of claim 8, wherein a flow detect filter in said plurality of flow detect filters includes:

a read/write protocol filter register which stores a protocol filter identifying a protocol for which the template register is adapted;

mask enable logic responsive to the protocol filter which enables the logic applying the mask in response to processing the incoming frame with the protocol filter;

a read/write protocol hierarchy register which stores a protocol hierarchy value identifying a priority for the protocol for which the template register is adapted; and

wherein the selector is responsive to the protocol hierarchy.

13. A network switch, comprising:

a port for access to a communication medium to receive incoming frames having a data link layer format and a network layer format;

route table memory having a set of accessible locations for storing routing information, the set of accessible locations being addressable in response to N bits, and locations in the set storing a tag comprising M bits for identifying a network flow, and storing network layer routing information for the network flow;

a plurality of flow detect filters, the flow detect filters including respectively a read/write template register which stores a mask for a particular network frame format, and logic applying the mask to the incoming frame to generate a hash seed value from the incoming frame, and a pseudo random number generator responsive to the hash seed which generates a hash;

a selector, coupled with the plurality of flow detect filters, which selects a hash from the plurality of flow detect filters as a hash value, and applies N bits of the hash value as an N bit address, and M bits of the hash value as an identifying tag for use in accessing the route table memory in response to an incoming frame; and

match logic, coupled with the route table memory and the flow detect logic, which accesses a particular location in the set of accessible locations in the route table memory in response to the N bit address, compares the identifying tag with the tag stored in the particular location to determine whether the incoming frame matches the network flow identified by the stored tag, and supplies the routing information stored in the particular location if a match occurs, else signals a route table miss.

14. The network switch of claim 13, wherein a flow detect filter in said plurality of flow detect filters includes:

a read/write protocol filter register which stores a protocol filter identifying a protocol for which the template register is adapted; and

mask enable logic responsive to the protocol filter which enables the logic applying the mask in response to processing the incoming frame with the protocol filter.

15. The network switch of claim 13, wherein a flow detect filter in said plurality of flow detect filters includes:

a read/write protocol hierarchy register which stores a protocol hierarchy value identifying a priority for the protocol for which the template register is adapted; and

wherein the selector is responsive to the protocol hierarchy.

16. The network switch of claim 13, wherein a flow detect filter in said plurality of flow detect filters includes:

a read/write protocol filter register which stores a protocol filter identifying a protocol for which the template register is adapted;

mask enable logic responsive to the protocol filter which enables the logic applying the mask in response to processing the incoming frame with the protocol filter;

a read/write protocol hierarchy register which stores a protocol hierarchy value identifying a priority for the protocol for which the template register is adapted; and

wherein the selector is responsive to the protocol hierarchy.

17. The network switch of claim 13, wherein M plus N is 32 or greater.

18. The network switch of claim 13, wherein M plus N is 64 or greater.

19. A network switch, comprising:

a port for access to a communication medium to receive incoming frames having a data link layer format and a network layer format;

route table memory having a set of accessible locations for storing routing information, the set of accessible locations being addressable in response to N bits, and locations in the set storing a tag comprising M bits for identifying a network flow, and storing network layer routing information for the network flow;

a plurality of flow detect filters, the flow detect filters including respectively

a read/write template register which stores a mask for a particular network frame format,

logic applying the mask to the incoming frame to generate a hash seed value from the incoming frame,

a read/write protocol filter register which stores a protocol filter identifying a protocol for which the template register is adapted,

mask enable logic responsive to the protocol filter which enables the logic applying the mask in response to processing the incoming frame with the protocol filter,

a pseudo random number generator responsive to the hash seed which generates a hash, and

a read/write protocol hierarchy register which stores a protocol hierarchy value identifying a priority for the protocol for which the template register is adapted;

a selector, coupled with the plurality of flow detect filters, which selects a hash from the plurality of flow detect filters as a hash value in response to the protocol hierarchy values, and applies N bits of the hash value as an N bit address, and M bits of the hash value as an identifying tag for use in accessing the route table memory in response to an incoming frame, where M plus N is 32 or greater; and

match logic, coupled with the route table memory and the flow detect logic, which accesses a particular location in the set of accessible locations in the route table memory in response to the N bit address, compares the identifying tag with the tag stored in the particular location to determine whether the incoming frame matches the network flow identified by the stored tag, and supplies the routing information stored in the particular location if a match occurs, else signals a route table miss.

20. The network switch of claim 19, wherein M plus N is 64 or greater.