Patent Description:
Networking equipment, such as network switches, are used to connect devices on a computer network. Some networking equipment utilize using packet switching to receive and forward data to the destination device. One type of network switch is a multiport network bridge that uses media access control (MAC) addresses to forward data at the data link layer (layer <NUM>) of the open systems interconnection (OSI) model. Some switches can also forward data at the network layer (layer <NUM>) by additionally incorporating routing functionality. Such switches are commonly known as layer-<NUM> switches or multilayer switches. <CIT> describes exact match hash lookup databases in network switch devices.

In a first aspect there is provided a method for performing exact match lookup operations in a table according to claim <NUM>. In as second aspect, there is provided a computer program product for performing exact match lookup operations in a table according to claim <NUM>.

A better understanding of the present disclosure can be obtained when the following detailed description is considered in conjunction with the following drawings, in which:.

Some types of network switches manage the flow of data across a network by transmitting a received network packet only to the one or more devices for which the packet is intended. Each networked device connected to a switch can be identified by its network address, allowing the switch to direct the flow of traffic maximizing the security and efficiency of the network.

In connection with transmitting the received network packet to the one or more devices for which the packet is intended, the network switch processes the received network packet. Such processing may involve multiple table lookups, such as multiple hash table lookups.

A hash table is a data structure that implements an associative array abstract data type, a structure that can map "keys" to values. Such "keys" may be formed from network identifiers. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are typically accommodated in some way.

In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table.

In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. That is, the average latency of a lookup (how long it takes to locate the desired value based on the key) in a hash table is less than the average latency of a lookup in other table lookup structures.

For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets. As a result, they are commonly used by network switches in connection with packet processing to direct the flow of traffic.

Maintaining a low average lookup latency is important in order for networking equipment, such as network switches, to maintain line rate performance. Line rate performance refers to the ability of the networking equipment to process the maximum amount of data payload at the link speeds its interface uses.

However, networking equipment, such as network switches, may perform exact match lookups based on the keys formed from the network identifiers. An "exact match lookup," as used herein, refers to searching for the exact match to the search key in the hash table. When searching for the exact match to the search key, hash collisions occur as discussed above. When a hash collision occurs, the hash table is probed to find the exact match to the search key which involves latency or time. Such deviations from the average lookup latency may negatively affect the line rate performance.

Unfortunately, algorithms to address collisions focus on minimizing the average lookup latency as opposed to minimizing the deviation from the average lookup latency, which impacts the line rate performance. As a result, there is not currently a means for effectively minimizing the deviation from the average lookup latency to ensure appropriate line rate performance.

The embodiments of the present disclosure provide a means for effectively minimizing the deviation from the average lookup latency to ensure appropriate line rate performance by utilizing a concept referred to herein as "billeting," which as used herein, refers to a neighboring hash root bucket temporarily hosting or storing an element (data) of an originating home hash root bucket as discussed further below.

In some embodiments of the present disclosure, the present disclosure comprises a method which may be computer-implemented, a network switch and computer program product for performing exact match lookup operations in a table. In one embodiment of the present disclosure, fields of a received packet are extracted and concatenated to form a lookup key. A hash of the lookup key is performed to generate a value ("hash value") which is used to identify a location in the hash memory space organized into M independently addressable planes, where each row of the plane contains N hash root buckets. A "plane" or "bank," as used herein, refers to a logical storage within computer memory that is used for storing and retrieving data. "Hash root buckets" (also referred to as "hash buckets" or simply "buckets"), as used herein, refer to the slots in the hash table. A "hash table," as used herein, refers to a data structure that implements an associative array abstract data type, a structure that can map "keys" to values. The generated hash value may then be separated into a bucket row, a bucket column, a bucket plane and a sub-bucket (secondary hash value), where the bucket row, bucket column and bucket plane are used to identify an originating home hash root bucket. In one embodiment, the head entry on the collision chain of the neighboring hash root bucket is read to determine if an exact match of the lookup key exists in response to a state field of the neighboring hash root bucket storing the secondary hash value, a column offset to a column location of the originating home hash root bucket and a plane offset to a plane location of the originating home hash root bucket. If the head entry on the collision chain of the neighboring hash root bucket exactly matches the lookup key, then a finding of an exact match of the lookup key is reported. If, however, the state field of the neighboring hash root buckets do not store the secondary hash value, the column offset to the column location of the originating home hash root bucket and the plane offset to the plane location of the originating home hash root bucket or if the head entry on the collision chain of the neighboring hash root bucket does not exactly match the lookup key, then a chain length in the chain length field and a value of the state field of the originating home hash root bucket are examined. If the value of the chain length is zero or if the value of the chain length is one and the value in the state field of the originating home hash root bucket is nonzero, then a finding of not having an exact match of the lookup key is reported. Otherwise, the root pointer entry of the originating home hash root bucket is read. If the root pointer entry exactly matches the lookup key and does not temporarily store an element of another originating home hash root bucket, then a finding of an exact match of the lookup key is reported. Otherwise, the next entry to the root pointer entry in the collision chain is read to determine if such an entry exactly matches the lookup key. If such an entry exactly matches the lookup key, then a finding of an exact match of the lookup key is reported. Otherwise, the subsequent entry in the chain is read to determine if such an entry matches the lookup key. Such a process continues until either a finding of an exact match occurs or until the last entry in the collision chain is read. If the last entry in the collision chain does not exactly match the lookup key, then a finding of not having an exact match of the lookup key is reported. In this manner, the deviation from the average lookup latency is minimized to ensure appropriate line rate performance.

In the following description, numerous specific details are set forth to provide a thorough understanding of the present disclosure. However, it will be apparent to those skilled in the art that the present disclosure may be practiced without such specific details. In other instances, well-known circuits have been shown in block diagram form in order not to obscure the present disclosure in unnecessary detail. For the most part, details considering timing considerations and the like have been omitted inasmuch as such details are not necessary to obtain a complete understanding of the present disclosure and are within the skills of persons of ordinary skill the relevant art.

Referring now to the Figures in detail, <FIG> illustrates an embodiment of the present disclosure of a communication system <NUM> for practicing the principles of the present disclosure. Communication system <NUM> includes networking equipment, such as a network switch <NUM>, configured to receive data packets over a network <NUM>, which is forwarded to the appropriate computing device 103A-103B (identified as "Computing Device A," and "Computing Device B," respectively, in <FIG>) over a network <NUM>, such as shown in <FIG>. Computing devices 103A-103B may collectively or individually be referred to as computing devices <NUM> or computing device <NUM>, respectively.

Data packets (also referred to herein as simply "packets") refer to the data grouped by the method of packet switching that are transmitted over a digital network. Packets are comprised of a header and a payload. Data in the header is used by the networking equipment, such as network switch <NUM>, to direct the packet to its destination, where the payload is extracted and used by an operating system, application software or higher layer protocols of a computing device, such as computing device <NUM>.

As previously discussed, network traffic, such as data packets received over network <NUM>, is forwarded to and from computing devices, such as computing devices <NUM>, by network switch <NUM> over network <NUM>. In one embodiment, network switch <NUM> connects devices <NUM> on a computer network by using packet switching to receive and forward data to the destination device. In one embodiment, network switch <NUM> is a multiport network bridge that uses MAC addresses to forward data at the data link layer (layer <NUM>) of the open systems interconnection (OSI) model. In one embodiment, network switch <NUM> also forwards data at the network layer (layer <NUM>) by additionally incorporating routing functionality.

Furthermore, network switch <NUM> manages the flow of data across a network by transmitting a received network packet only to the one or more devices (e.g., computing device 103B) for which the packet is intended. Each networked device <NUM> connected to a network switch (e.g., network switch <NUM>) can be identified by its network address, allowing the switch to direct the flow of traffic thereby maximizing the security and efficiency of the network.

In connection with transmitting the received network packet to the one or more devices for which the packet is intended, network switch <NUM> processes the received network packet. Such processing involves multiple table lookups, such as multiple hash table lookups.

In one embodiment, network switch <NUM> minimizes the deviation from the average lookup latency of the hash table by utilizing a concept referred to herein as "billeting," which as used herein, refers to a neighboring hash root bucket temporarily hosting or storing an element (data) of an originating home hash root bucket. A further description of these and other features is provided below.

A description of the components of network switch <NUM> is provided below in connection with <FIG>. A description of the software components used by network switch <NUM> for minimizing the deviation from the average lookup latency of the hash table is provided further below in connection with <FIG>.

Referring again to <FIG>, computing devices <NUM> may be any type of computing device (e.g., portable computing unit, Personal Digital Assistant (PDA), laptop computer, mobile device, tablet personal computer, smartphone, mobile phone, navigation device, gaming unit, desktop computer system, workstation, Internet appliance, server, and the like) configured with the capability of connecting to network <NUM> and consequently communicating with other computing devices <NUM> and network switch <NUM>.

Networks <NUM>, <NUM> may be, for example, a local area network, a wide area network, a wireless wide area network, a circuit-switched telephone network, a Global System for Mobile Communications (GSM) network, a Wireless Application Protocol (WAP) network, a WiFi network, an IEEE <NUM> standards network, various combinations thereof, etc. Other networks, whose descriptions are omitted here for brevity, may also be used in conjunction with system <NUM> of <FIG> without departing from the scope of the present disclosure.

System <NUM> is not to be limited in scope to any one particular network architecture. System <NUM> may include any number of network switches <NUM>, networks <NUM>, <NUM>, and computing devices <NUM>. Furthermore, while <FIG> illustrates two separate networks, such as networks <NUM>, <NUM>, system <NUM> may include a single network interconnecting the components shown in <FIG>.

A discussion regarding the components of network switch <NUM> is provided below in connection with <FIG>.

<FIG> illustrates an embodiment of the present disclosure of the components of network switch <NUM> which is representative of a hardware environment for practicing the present disclosure.

Referring to <FIG>, network switch <NUM> includes a processor <NUM> connected to memory <NUM>. In one embodiment, processor <NUM> is a network traffic processor configured to process data packets by transmitting a received network packet only to the one or more devices (e.g., computing device 103B of <FIG>) for which the packet is intended. Furthermore, in one embodiment, network traffic processor <NUM> is configured to minimize the deviation from the average lookup latency of the hash table using the principles of the present disclosure as discussed herein. Network traffic processor <NUM> may be implemented in hardware, software or in a combination thereof.

Network switch <NUM> may further include a replication engine <NUM> connected to processor <NUM>. In one embodiment, replication engine <NUM> is tasked with duplicating packets of data and sending them to their designated destinations. For example, a single data packet may be sent to multiple destinations in a network. For instance, a user may desire to send documents or business reports to multiple people within the user's organization.

Network switch <NUM> may additionally include a forwarding engine <NUM> connected to processor <NUM>. In one embodiment, forwarding engine <NUM> is configured to perform the switching and routing decisions. In one embodiment, forwarding engine <NUM> contains lookup tables <NUM>, such as a hash lookup table(s) discussed herein, which is used by forwarding engine <NUM> to send data packets to their appropriate destination. Each packet of data contains information, such as the destination and source addresses of the packet. Forwarding engine <NUM> reads the destination address on the data packet and then sends it there accordingly.

Additionally, network switch <NUM> includes a switch fabric <NUM> connected to processor <NUM>. In one embodiment, switch fabric <NUM> is comprised of hardware and software that work in tandem to ensure that data coming into the network is sent out via the appropriate port (not shown). In one embodiment, the hardware and software include the switching units contained in a network node and the software required to control the switching paths.

In one embodiment, memory <NUM> stores the code for operating system <NUM> and application <NUM>. In one embodiment, processor <NUM> executes the code for operating system <NUM> which provides control and coordination of the functions of the various components of <FIG>. Furthermore, in one embodiment, processor <NUM> executes the code for application <NUM>. An application <NUM> in accordance with the principles of the present disclosure runs in conjunction with operating system <NUM> and provides calls to operating system <NUM> where the calls implement the various functions or services to be performed by application <NUM>. Application <NUM> may include the software components used by network switch <NUM>, including forwarding engine <NUM>, to minimize the deviation from the average lookup latency of the hash table using the principles of the present disclosure as discussed below in connection with <FIG>.

Memory <NUM> may include, but not limited to, random access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM or Flash memory), static random access memory (SRAM), combinations thereof, etc..

Furthermore, network switch <NUM> may include a storage device <NUM> connected to processor <NUM>. Examples of storage device <NUM> include, but not limited to, a hard disk, a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, etc..

Referring now to <FIG> illustrates the software components used by network switch <NUM> for minimizing the deviation from the average lookup latency of the hash table in accordance with an embodiment of the present disclosure.

In one embodiment, network switch <NUM> includes a lookup table creator engine <NUM> configured to create and populate a hash table in a manner that minimizes the deviation from the average lookup latency of the hash table by utilizing a concept referred to herein as "billeting," which as used herein, refers to a neighboring hash root bucket temporarily hosting or storing an element (data) of an originating home hash root bucket.

Network switch <NUM> further includes a packet analyzer <NUM> configured to perform exact match lookup operations in such a hash table in a manner that minimizes the deviation from the average lookup latency of the hash table.

Referring now to <FIG>, in conjunction with <FIG>, in one embodiment, application <NUM> of network switch <NUM> includes the software components of lookup table creator engine <NUM> and packet analyzer <NUM>. In one embodiment, such components may be implemented in hardware, where such hardware components would be connected to processor <NUM>. The functions discussed herein performed by such components are not generic computer functions. As a result, network switch <NUM> is a particular machine that is the result of implementing specific, non-generic computer functions.

In one embodiment, the functionality of such software components (e.g., lookup table creator engine <NUM> and packet analyzer <NUM>) of network switch <NUM>, including the functionality for minimizing the deviation from the average lookup latency of the hash table, may be embodied in an application specific integrated circuit.

The present disclosure may be a system, a method, and/or a computer program product at any possible technical detail level of integration.

Computer readable program instructions for carrying out operations of the present disclosure may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, configuration data for integrated circuitry, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++, or the like, and procedural programming languages, such as the "C" programming language or similar programming languages. In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present disclosure.

The embodiments of the present disclosure provide a means for effectively minimizing the deviation from the average lookup latency to ensure appropriate line rate performance by utilizing a concept referred to herein as "billeting," which as used herein, refers to a neighboring hash root bucket temporarily hosting or storing an element (data) of an originating home hash bucket as discussed further below in connection with <FIG> and <FIG>. <FIG> illustrates an embodiment of a hash memory space. <FIG> illustrates an embodiment of the descriptor of the hash root buckets. <FIG> is a flowchart of a method for populating a hash table in a manner that minimizes the deviation from the average lookup latency of the hash table. <FIG> illustrates prepending the element to the collision chain that exists on the neighboring hash root bucket. <FIG> illustrates adding an element at the end of the collision chain that exists on the home hash root bucket. <FIG> are a flowchart of a method for performing an exact match lookup operation in a hash table in a manner that minimizes the deviation from the average lookup latency to ensure appropriate line rate performance.

As stated above, <FIG> illustrates an embodiment of a hash memory space <NUM> in accordance with an embodiment of the present disclosure.

Referring to <FIG>, in conjunction with <FIG>, hash memory space <NUM>, the memory location of the hash table, may be part of memory <NUM> (<FIG>), such as part of standard RAM, or part of lookup table <NUM> of forwarding engine <NUM>. In one embodiment, hash memory space <NUM> is organized into M independently addressable planes or banks 401A-401B, where the row of each memory plane contains N hash root buckets <NUM>. Planes 401A-401B may collectively or individually be referred to as planes <NUM> or plane <NUM>, respectively. A "plane" or "bank," as used herein, refers to a logical storage within computer memory that is used for storing and retrieving data. In one embodiment, "hash root buckets" (also referred to as "hash buckets" or simply "buckets"), as used herein, refer to the slots in the hash table. As discussed above, a hash table is a data structure that implements an associative array abstract data type, a structure that can map "keys" to values. Furthermore, such "keys" may be formed from network identifiers. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found.

In one embodiment, the key or lookup key is hashed by a hash function to generate a value ("hash value") to identify a location in the table. In one embodiment, the created hash value is separated into multiple fields, such as a bucket row, a bucket column, a bucket plane and a sub-bucket. The bucket row, bucket column and bucket plane are used to identify a home hash root bucket within hash memory space <NUM> as well as inherently provide N-<NUM> adjacent neighboring hash root buckets within the same row.

In one embodiment, the sub-bucket is a secondary hash value that is used to return M memory rows on alternative memory planes to the home memory plane thereby providing (M-<NUM>) x N neighboring buckets. In one embodiment, the sub-bucket is hashed differently for each alternative memory plane <NUM> allowing for a random distribution of alternate rows on each plane <NUM> depending on the sub-bucket.

Referring again to <FIG> illustrates an example of a hash memory space <NUM> being organized into two planes 401A-401B, where the row <NUM> ("bucket row") of each plane <NUM> contains three hash root buckets <NUM>, one for each of the three columns <NUM> ("bucket column"). In one embodiment, the home hash root bucket is identified by the row, column and plane of plane 402A. For example, the home hash root bucket <NUM> is identified by the row, column and plane of plane 402A, which are obtained from the created hash value. The two hash root buckets on the sides of home hash root bucket <NUM> correspond to the "close neighbors" 406A-406B. A "close neighbor," as used herein, refers to those hash root buckets in the same row as the home hash root bucket. Close neighbors 406A-406B may collectively or individually be referred to as close neighbors <NUM> or close neighbor <NUM>.

Furthermore, as shown in <FIG>, the sub-bucket portion of the hash (see element <NUM>) is used to transform the row in the independently addressable alternative memory plane 402B, such as via a multiplier <NUM>, which multiplies sub-bucket <NUM> with bucket row <NUM> containing the home hash root bucket <NUM> in question. For example, as shown in <FIG>, sub-bucket <NUM> is used to identify three "distant neighbors" <NUM> of home hash root bucket <NUM> in plane 401B. A "distant neighbor," as used herein, refers to those hash root buckets that were identified based on sub-bucket <NUM> in an alternative plane <NUM>, such as plane 401B.

A description of the descriptor of the hash root buckets <NUM> is provided below in connection with <FIG>.

<FIG> illustrates an embodiment of descriptor <NUM> of hash root buckets <NUM> in accordance with an embodiment of the present disclosure.

Referring to <FIG>, in conjunction with <FIG>, in one embodiment, descriptor <NUM> of hash root buckets <NUM> includes a "billet" state field <NUM>, a chain length field <NUM> and a root pointer field <NUM>. The term "billeting," as used herein, refers to a neighboring hash root bucket temporarily hosting or storing an element (data) of an originating home hash root bucket (also simply referred to herein as simply the "home hash root bucket" or "home hash bucket"). The term "billet," as used herein, refers to the element of data of an originating home hash root bucket (e.g., home hash root bucket <NUM>) temporarily hosted or stored in a chain (e.g., collision chain). When such a situation occurs, the "billet" state field <NUM> includes sub-bucket <NUM>, a column offset <NUM> and a plane offset <NUM> that identifies the location of a neighboring hash root bucket with respect to the originating home hash root bucket. For example, referring to <FIG>, billet state field <NUM> may identify the location of a neighboring hash root bucket in plane 401B with respect to the originating home hash root bucket <NUM> that is used to temporarily host or store an element of originating home hash root bucket <NUM>.

Chain length field <NUM> stores the collision chain (also referred to herein as simply "chain") of a certain depth. The "collision chain," as used herein, refers to a linked list of elements that have the same hash function value. In one embodiment, such a field <NUM>, is used to handle collisions via "separate chaining. " "Separate chaining," as used herein, refers to a scheme in which each position in the hash table has a list to handle collisions. Each position may be a link to the list or may be an item and a link, essentially, the head of a list.

The root pointer field <NUM>, as used herein, stores a pointer that points to the first element in a linked list, such as the list of elements stored in a collision chain.

A further discussion regarding descriptor <NUM> of hash root buckets <NUM> is provided below in connection with the method for populating a hash table, such as the table formed in hash memory space <NUM>, as discussed in <FIG>.

<FIG> is a flowchart of a method <NUM> for populating a hash table, such as the table formed in hash memory space <NUM> (<FIG>), in a manner that minimizes the deviation from the average lookup latency of the hash table in accordance with an embodiment of the present disclosure. In particular, in one embodiment, method <NUM> determines which of the available M x N hash root buckets in memory space <NUM> is the best choice to insert or store an element.

Referring to <FIG>, in conjunction with <FIG>, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> examines billet state field <NUM> of each of the neighboring hash root bucket locations. As previously discussed, billet state field <NUM> is used to identify the location of a neighboring hash root bucket in plane <NUM> with respect to the originating home hash root bucket (e.g., originating home hash root bucket <NUM>) that is used to temporarily host or store an element of the originating home hash root bucket.

For example, a home hash root bucket may be identified based on hashing a lookup key (e.g., concatenation of the fields of a packet received by network switch <NUM>) by a hashing algorithm (e.g., cyclic redundancy check, XOR, summing tuple, modular hashing, etc.) to produce a hashing value. The hashing value may be separated into multiple fields, such as a bucket row <NUM>, a bucket column <NUM>, a bucket plane <NUM> and a sub-bucket <NUM> as previously discussed. Neighbor hash root bucket locations may then be determined based on identifying those hash root buckets <NUM> ("close neighbors" <NUM>) located in the same row as the home hash root bucket (e.g., home hash root bucket <NUM>) as well identifying those located in alternative planes <NUM> ("distant neighbors" <NUM>) using sub-bucket <NUM> as discussed above.

As also discussed above, method <NUM> determines which of the available M x N hash root buckets in memory space <NUM> is the best choice to insert or store an element. As a result, each of the (M x N) - <NUM> neighbor hash bucket locations has the possibility of hosting this insertion as a "billet. " As previously discussed, such a "billet" refers to the element of data of an originating home hash root bucket (e.g., home hash root bucket <NUM>) temporarily hosted or stored in a chain (e.g., collision chain). By incorporating the concept of storing a billet, the deviation from the average lookup latency is minimized by providing randomness to the alternative secondary hash locations allowing more opportunities for hash chaining to be avoided thereby reducing the average probe depth to find a hash hit or miss.

As a result, billet state field <NUM> is examined in each of the neighboring hash root buckets (e.g., hash root buckets <NUM>, <NUM>) to determine if a neighboring hash root bucket is already temporarily hosting or storing an element of an originating home hash root bucket.

For each of the examined neighboring hash root buckets, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> determines whether the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) in question stores a billet. That is, lookup table creator engine <NUM> determines whether billet state field <NUM> in the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) in question is already hosting or storing a billet corresponding to an element of the originating home hash root bucket (e.g., home hash root bucket <NUM>).

If the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) is storing an existing billet, then, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> disqualifies the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) from storing the element.

If, however, the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) does not store an existing billet, then, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> determines whether any of the neighboring hash root buckets (e.g., hash root bucket <NUM>, <NUM>) have a matching billet state. A "matching" billet state, as used herein, refers to billet state field <NUM> containing the values of sub-bucket <NUM>, column offset <NUM> and plane offset <NUM> that identifies the neighboring hash root bucket in question as storing the element of the home hash root bucket in question (e.g., home hash root bucket <NUM>).

If a neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) has a matching billet state, then, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> disqualifies the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) from storing the element.

If, however, the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) does not have a matching billet state, then, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> examines the depth of the collision chain of each neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) that does not store an existing billet and does not have a matching billet state as well as examines the depth of the collision chain of the originating home hash root bucket (e.g., originating home hash root bucket <NUM>). The "originating home hash root bucket," as used herein, refers to the home hash root bucket (e.g., home hash root bucket <NUM>) that is identified based on the hash value generated from performing a hash of the lookup key. The "collision chain depth," as used herein, refers to the length of the linked list of elements that have the same hash function value as stored in chain length field <NUM> of the respective hash root bucket. In one embodiment, method <NUM> will choose to insert or store the element into the shortest available location. That is, method <NUM> will insert or store the element into the chain (collision chain) with the shortest length as defined in chain length field <NUM>.

In step <NUM>, lookup table creator engine <NUM> of network switch <NUM> stores the element in the neighboring hash root bucket (e.g., neighbor hash root bucket <NUM>, <NUM>) or in the originating home hash root bucket (e.g., home hash root bucket <NUM>) with the shortest available location. That is, lookup table creator engine <NUM> of network switch <NUM> stores the element in the neighboring hash root bucket (e.g., neighbor hash root bucket <NUM>, <NUM>) or in the originating home hash root bucket (e.g., home hash root bucket <NUM>) with the shortest depth (shortest length) of its collision chain as discussed further below.

In step <NUM>, a determination is made by lookup table creator engine <NUM> of network switch <NUM> as to whether the element is to be stored in a neighboring hash root bucket (e.g., neighboring hash root bucket <NUM>, <NUM>).

If the element is to be stored in a neighboring hash root bucket (e.g., neighboring hash root bucket <NUM>, <NUM>) because the neighboring hash root bucket has a collision chain with the shortest length, then, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> updates billet state field <NUM> to indicate that the respective neighboring hash root bucket (e.g., neighboring hash root bucket <NUM>, <NUM>) is holding a billet from the originating home location (i.e., from the originating home hash root bucket). That is, in step <NUM>, lookup table creator engine <NUM> updates billet state field <NUM> to indicate temporarily storing the element from the originating home hash root bucket.

In step <NUM>, lookup table creator engine <NUM> of network switch <NUM> prepends the element to the chain (collision chain) that exists on the neighboring hash root bucket (e.g., neighboring hash root bucket <NUM>, <NUM>) as shown in <FIG>.

<FIG> illustrates prepending the element to the collision chain that exists on the neighboring hash root bucket in accordance with an embodiment of the present disclosure.

Referring to <FIG>, in conjunction with <FIG>, <FIG> illustrates billet state <NUM> as stored in billet state field <NUM> for both the originating home hash root bucket <NUM> ("home bucket") as well as the close neighbors <NUM> and distant neighbors <NUM>. Furthermore, <FIG> illustrates the chain length <NUM> as stored in chain length field <NUM>, which indicates the depth of the collision chain or the length of the linked list of elements that have the same hash function value. Additionally, <FIG> illustrates the root pointer <NUM> as stored in root pointer field <NUM>, which includes a pointer that points to the first element in the linked list, such as the list of elements stored in a collision chain <NUM>.

In the situation where the neighboring hash root bucket has a collision chain with the shortest length, lookup table creator engine <NUM> prepends the element <NUM> to the chain that exists on the neighboring hash root bucket (e.g., neighboring hash root bucket <NUM>, <NUM>) as the new billet as shown in <FIG>. Billet state <NUM> is updated, such as shown in element <NUM> (e.g., "ddd"), to indicate that the neighboring hash root bucket is holding a billet from the originating home location. Also, in one embodiment, chain length <NUM> is updated, such as shown in element <NUM> (e.g., "<NUM>"), to reflect an increase in the depth of the collision chain (i.e., the length of the linked list of elements).

Returning to step <NUM> of <FIG>, if, however, the element is to be stored in the originating home hash root bucket (e.g., home hash root bucket <NUM>) because the originating home hash root bucket has a collision chain with the shortest length, then, in step <NUM>, lookup table creator engine <NUM> of network switch <NUM> adds the element to the end of the collision chain that exists on the originating home hash root bucket (e.g., home hash root bucket <NUM>) as illustrated in <FIG>.

<FIG> illustrates adding an element at the end of the collision chain that exists on the home hash root bucket in accordance with an embodiment of the present disclosure.

Referring to <FIG>, in conjunction with <FIG> and <FIG>, in the situation where the originating home hash root bucket (e.g., home hash root bucket <NUM>) has a collision chain with the shortest length, lookup table creator engine <NUM> adds the element <NUM> to the collision chain that exists on the originating home hash root bucket as shown in <FIG>. Also, in one embodiment, chain length <NUM> is updated, such as shown in element <NUM> (e.g., "<NUM>"), to reflect an increase in the depth of the collision chain (i.e., the length of the linked list of elements).

Upon populating the hash table, such as the table formed in hash memory space <NUM> (<FIG>), in a manner that minimizes the deviation from the average lookup latency of the hash table, an exact match lookup operation is performed in such a hash table in a manner that minimizes the deviation from the average lookup latency to ensure appropriate line rate performance as discussed below in connection with <FIG>.

<FIG> are a flowchart of a method <NUM> for performing an exact match lookup operation in a hash table in a manner that minimizes the deviation from the average lookup latency to ensure appropriate line rate performance in accordance with an embodiment of the present disclosure.

Referring to <FIG>, in conjunction with <FIG>, in step <NUM>, packet analyzer <NUM> of network switch <NUM> receives a packet, such as a packet of network traffic received over network <NUM>.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> extracts and concatenates the fields of the packet to form a lookup key. For example, in one embodiment, packet analyzer <NUM> extracts and concatenates the source port and destination port fields from the packet to form a lookup key. In one embodiment, the length field of the packet, which specifies the length of the header and data, may also be extracted and concatenated to form the lookup key.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> performs a hash of the lookup key to generate a value which is used to identify a location in hash memory space <NUM> organized into M independently addressable planes <NUM>, where each row of plane <NUM> contains N hash root buckets <NUM>. For example, a value ("hash value") may be generated based on hashing the lookup key by a hashing algorithm (e.g., cyclic redundancy check, XOR, summing tuple, modular hashing, etc.). By performing such a hash, an originating home hash root bucket <NUM> may be identified.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> separates the value into fields including a bucket row <NUM>, a bucket column <NUM>, a bucket plane <NUM> and a sub-bucket <NUM> (secondary hash value), where bucket row <NUM>, bucket column <NUM> and bucket plane <NUM> are used to identify an originating home hash bucket <NUM>.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> accesses M x N hash root buckets <NUM>, such as the neighboring hash root buckets <NUM>, <NUM>, from the memory subsystem. The "memory subsystem," as used herein, refers to the hardware and software components that include the primary storage area of network switch <NUM> (e.g., memory <NUM>), where the programs and the data they use are stored while the programs are executing. Examples of such a memory subsystem include both hardware and software components, such as processor <NUM> and memory <NUM>. In one embodiment, the memory subsystem is able to provide such information to packet analyzer <NUM> based on hash memory space <NUM> being part of memory <NUM> or part of lookup table <NUM> of forwarding engine <NUM>.

As previously discussed, neighboring hash root bucket locations may be determined based on identifying those hash root buckets <NUM> (e.g., "close neighbors" <NUM>) located in the same row as the home hash root bucket <NUM> as well identifying those hash root buckets <NUM> located in alternative planes <NUM> ("distant neighbors" <NUM>) using sub-bucket <NUM> as discussed above.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> examines the billet state field <NUM> of neighboring hash root buckets (e.g., neighboring hash root buckets <NUM>, <NUM>).

As previously discussed, billet state field <NUM> is used to identify the location of a neighboring hash root bucket in plane <NUM> with respect to the originating hash root bucket (e.g., home hash root bucket <NUM>) that is used to temporarily host or store an element of the originating hash root bucket.

As a result, billet state field <NUM> is examined in each of the neighboring hash root buckets (e.g., hash root bucket <NUM>, <NUM>) to determine if a neighboring hash root bucket is already temporarily hosting or storing an element of an originating home hash root bucket <NUM>.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> determines whether any of the neighboring hash root buckets (e.g., hash root bucket <NUM>, <NUM>) has a matching billet state. A "matching" billet state, as used herein, refers to billet state field <NUM> containing the values of sub-bucket <NUM>, column offset <NUM> and plane offset <NUM> that identifies the neighboring hash root bucket in question as storing the element of the originating home hash root bucket in question (e.g., home hash root bucket <NUM>).

If the neighboring hash root bucket (e.g., hash root bucket <NUM>, <NUM>) has a matching billet state, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> reads the head entry on the collision chain of the neighboring hash root bucket (e.g., neighboring hash root bucket <NUM>, <NUM>), such as reading head entry <NUM> of the collision chain. It is noted that only the head entry needs to be read from memory and checked for a full match with the lookup key since the billet is stored as the head entry on a chain in a neighboring hash root bucket as previously discussed.

In step <NUM>, a determination is made by packet analyzer <NUM> of network switch <NUM> as to whether there is an exact match with the lookup key. That is, a determination is made by packet analyzer <NUM> as to whether the value of the head entry is an exact match with the lookup key.

If there is an exact match with the lookup key, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> completes the lookup operation and reports a finding of an exact match of the lookup key. In one embodiment, network switch <NUM> transmits the received network packet to the appropriate device using the value in the hash table associated with the matched lookup key, such as the destination address.

Returning to steps <NUM> and <NUM>, if, however, the neighboring hash root bucket (e.g., neighboring hash root bucket <NUM>, <NUM>) does not have a matching billet state, or if, however, there is not an exact match with the lookup key, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> examines chain length <NUM> and billet state <NUM> of the originating home hash root bucket <NUM>.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> determines whether chain length <NUM> is <NUM> (implying that there are no elements stored in the collision chain) or whether chain length <NUM> is <NUM> and billet state <NUM> is non-zero (implying that there is only one entry in the collision chain and it is a billet).

If chain length <NUM> is <NUM> or chain length <NUM> is <NUM> and billet state <NUM> is non-zero, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> reports not finding an exact match of the lookup key. That is, packet analyzer <NUM> reports a finding that no exact match entries were identified.

Referring now to <FIG>, in conjunction with <FIG>, if however, chain length <NUM> is not <NUM> and is not <NUM> along with billet state <NUM> being non-zero, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> reads the root pointer entry in collision chain <NUM> of the originating home hash root bucket <NUM>. The "root pointer entry," as used herein, refers to the first entry in collision chain <NUM> pointed to by root pointer <NUM>.

In step <NUM>, packet analyzer <NUM> of network switch <NUM> determines if the first entry in collision chain <NUM> pointed to by root pointer <NUM> corresponds to a billet.

If the entry pointed to by root pointer <NUM> does not correspond to a billet, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> reads the entry followed by determining in step <NUM> as to whether there is an exact match with the lookup key. That is, a determination is made by packet analyzer <NUM> in step <NUM> as to whether the value of the entry read in step <NUM> is an exact match with the lookup key.

If, however, the entry pointed to by root pointer <NUM> corresponds to a billet, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> reads the next entry in collision chain <NUM> followed by determining in step <NUM> as to whether there is an exact match with the lookup key. That is, a determination is made by packet analyzer <NUM> in step <NUM> as to whether the value of the entry read in step <NUM> is an exact match with the lookup key.

If, however, there is not an exact match with the lookup key, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> determines whether there are any additional entries in collision chain <NUM>.

If there are additional entries in collision chain <NUM>, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> reads the next entry in collision chain <NUM> followed by determining in step <NUM> as to whether there is an exact match with the lookup key. That is, a determination is made by packet analyzer <NUM> in step <NUM> as to whether the value of the entry read is an exact match with the lookup key.

If, however, there are no additional entries in collision chain <NUM>, then, in step <NUM>, packet analyzer <NUM> of network switch <NUM> reports not finding an exact match of the lookup key. That is, packet analyzer <NUM> reports a finding that no exact match entries were identified.

In this manner, the deviation from the average lookup latency is minimized to ensure appropriate line rate performance. In one embodiment, the deviation from the average lookup latency is minimized by providing randomness to the alternative secondary hash locations allowing more opportunities for hash chaining to be avoided thereby reducing the average probe depth to find a hash hit or miss. That is, billeting reduces the likelihood of having to create hash chaining, which in turn, reduces the overall latency of the lookup.

Furthermore, the principles of the present disclosure improve the technology or technical field involving networking equipment.

The technical solution provided by the present disclosure cannot be performed in the human mind or by a human using a pen and paper. That is, the technical solution provided by the present disclosure could not be accomplished in the human mind or by a human using a pen and paper in any reasonable amount of time and with any reasonable expectation of accuracy without the use of a computer. A computer-implemented method, network switch and computer program product for performing exact match lookup operations in a table. A hash of the lookup key is performed to generate a value which is used to identify a location in the hash memory space. The generated value is separated into a bucket row, a bucket column, a bucket plane and a secondary hash value, where the bucket row, bucket column and bucket plane are used to identify an originating home hash root bucket. The head entry on the collision chain of a hash root bucket identified via the secondary hash value that is a neighbor to the home hash root bucket is read to determine if an exact match of the lookup key exists. If the head entry exactly matches the lookup key, then a finding of an exact match of the lookup key is reported.

Claim 1:
A method for performing exact match lookup operations in a table (<NUM>), the method comprising:
receiving a packet (<NUM>);
extracting and concatenating fields in said packet to form a lookup key (<NUM>) ;
performing a hash of said lookup key to generate a value which is used to identify a location in said table (<NUM>);
separating said value (<NUM>) into fields comprising a bucket row (<NUM>), a bucket column (<NUM>), a bucket plane (401A) and a secondary hash value, wherein said bucket row (<NUM>), said bucket column (<NUM>) and said bucket plane (401A) are used to identify an originating home hash root bucket (<NUM>);
reading a head entry (<NUM>) on a collision chain of one of one or more hash root buckets neighboring (<NUM>, <NUM>) to the originating home hash root bucket (<NUM>) to determine if an exact match of said lookup key exists in response to a state field (<NUM>) of said one of said one or more neighboring hash root buckets (<NUM>, <NUM>) comprising said secondary hash value, a column offset (<NUM>) to said bucket column of said originating home hash root bucket (<NUM>) and a plane offset (<NUM>) to the bucket plane of said originating home hash root bucket (<NUM>); and
reporting a finding of an exact match of said lookup key (<NUM>) in response to said head entry on said collision chain of said one of said one or more neighboring hash root buckets (<NUM>,<NUM>) exactly matching said lookup key.