Stochastic circuit identification in a multi-protocol network switch

Claim 2

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.

Claim 3

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

Claim 4

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

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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

Claim 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; 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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 18

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.

Claim 19

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.

Claim 20

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

Claim 21

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

Claim 22

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.

Claim 23

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.

Claim 24

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