# US 2012/0084396 A1 · Context switched route look up key engine

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0084396 A1
- Document ID: US20120084396A1
- Status: Published application
- Kind: A1
- Application number: 13/327,176
- Filed: 2011-12-15
- Published: 2012-04-05
- Earliest claimed: 2001-11-05
- Assignees: Juniper Networks, Inc.
- Inventors: Pankaj PATEL; Viswesh ANATHAKRISHNAN
- Web page: https://patentgrep.com/patent/US20120084396A1

## CPC

- H04L 45/00: Routing or path finding of packets in data switching networks (routing or path finding in wireless networks H04W40/00)
- H04L 45/56: {Routing software}
- H04L 45/60: Router architectures
- H04L 45/742: {Route cache; Operation thereof}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A key engine that performs route lookups for a plurality of keys may include a data processing portion configured to process one data item at a time and to request data when needed. A buffer may be configured to store a partial result from the data processing portion. A controller may be configured to load the partial result from the data processing portion into the buffer. The controller also may be configured to input another data item into the data processing portion for processing while requested data is obtained for a prior data item. A number of these key engines may be used by a routing unit to perform a large number of route lookups at the same time.

## Claims

### Claim at position 1

1-23. (canceled)

### Claim 24

A non-transitory memory device comprising:
one or more instructions which, when executed by one or more processors, cause the one or more processors to receive a plurality of keys, where each key, of the plurality of keys, includes information for performing routing of a corresponding data unit; and
one or more instructions which, when executed by the one or more processors, cause the one or more processors to concurrently process a quantity of at least two of the plurality of keys,
where the one or more instructions to concurrently process the quantity of the at least two of the plurality of keys include:
one or more instructions which, when executed by the one or more processors, cause the one or more processors to generate access requests for requesting information, from a memory, for processing the quantity of the at least two of the plurality of keys, and
where the quantity is based on a ratio of a latency of the memory to an average processing time associated with generating the access requests.

### Claim 25 (depends on 24)

The memory device of claim 24, further comprising:
one or more instructions to receive a plurality of data units; and
one or more instructions to convert each data unit, of the plurality of data units, into a data structure that includes a corresponding key, of the plurality of keys.

### Claim 26 (depends on 24)

The memory device of claim 24, where the one or more instructions to concurrently process the quantity of the at least two of the plurality of keys further include:
one or more instructions to determine routing information associated with a first key, of the quantity of the at least two of the plurality of keys, based on a routing table stored in the memory.

### Claim 27 (depends on 26)

The memory device of claim 26, where each key, of the plurality of keys, is included in a corresponding group of cells, of a plurality of groups of cells, the corresponding group of cells including the key and a data portion of the corresponding data unit, the memory device further comprising:
one or more instructions to modify a first group of cells, of the plurality of groups of cells, corresponding to the first key based on the determined routing information, and
one or more instructions to route the corresponding data unit based on the modified group of cells.

### Claim 28 (depends on 24)

The memory device of claim 24, where the one or more instructions to concurrently process the quantity of the at least two of the plurality of keys include:
one or more instructions to generate a partial result for a first key, of the quantity of the at least two of the plurality of keys,
one or more instructions to store the partial result and a processing state associated with processing the first key,
one or more instructions to generate a first access request, of the generated access requests, to request information for processing the first key from the memory, based on storing the partial result and the processing state, where the information for processing the first key is requested at a first time,
one or more instructions to receive the information for processing the first key from the memory at a second time that is subsequent to the first time, and
one or more instructions to process a second key, of the quantity of the at least two of the plurality of keys, during a period defined by the first time and the second time, where the second key is different from the first key.

### Claim 29 (depends on 28)

The memory device of claim 28, where the one or more instructions to process the second key include:
one or more instructions to determine that the information for processing the first key has been received, and
one or more instructions to store a partial result and a processing state associated with processing the second key based on determining that the information for processing the first key has been received.

### Claim 30 (depends on 24)

The memory device of claim 24, the memory device further comprising:
one or more instructions to route one or more data units, of the corresponding data units, based on one or more of a forwarding table or an encapsulation table stored in the memory, where the one or more data units correspond to one or more keys of the quantity of the at least two of the plurality of keys.

### Claim 31

A method comprising:
receiving, by one or more processors of a network device, a plurality of groups of data, where each group of data, of the plurality of groups of data, includes a key that includes information associated with routing a corresponding data unit; and
concurrently processing, by the one or more processors, a quantity of two or more keys, included in two or more groups of data, of the plurality of groups of data, where concurrently processing the quantity of the two or more keys includes:
generating, by the one or more processors, access requests to request processing information necessary to complete the processing of the quantity of the two or more keys, where the requests are generated to access a memory to obtain the processing information, and
where the quantity is determined based on a latency of the memory and an amount of time for the one or more processors to process a key.

### Claim 32 (depends on 31)

The method of claim 31, further comprising:
receiving a plurality of data units; and
converting each data unit, of the plurality of data units, into a group of data, of the plurality of groups of data, where each group of data, of the plurality of groups of data, includes the key, a data portion of the converted data unit, and parsed header information of the converted data unit.

### Claim 33 (depends on 31)

The method of claim 31, where concurrently processing the quantity of the two or more keys further includes:
determining routing information associated with a first key, of the quantity of the two or more keys, based on at least a first routing table stored in the memory.

### Claim 34 (depends on 33)

The method of claim 33, further comprising:
modifying a first group of data, of the plurality of groups of data, corresponding to the first key based on the determined routing information,
converting the modified first group of data into the corresponding data unit, and
routing the corresponding data unit based on information included in the modified first group of data.

### Claim 35 (depends on 31)

The method of claim 31, where concurrently processing the quantity of the two or more keys includes:
generating a partial result for a first key, of the quantity of the two or more keys,
storing the partial result and a processing state associated with processing the first key in a buffer associated with the one or more processors,
generating a first access request, of the generated access requests, to request processing information, needed to complete the processing of the first key, from the memory, based on storing the partial result and the processing state,
receiving the processing information, needed to complete the processing of the first key, from the memory, and
processing a second key, of the quantity of the two or more keys, during a period occurring between requesting the processing information, complete to finish the processing of the first key, and receiving the processing information, needed to complete the processing of the first key.

### Claim 36 (depends on 35)

The method of claim 35, where processing the second key includes:
determining that the processing information, needed for completing the processing of the first key has been received, and
storing a partial result and a processing state, associated with the processing of the second key, based on determining that the information needed for completing the processing of the first key has been received.

### Claim 37 (depends on 31)

The method of claim 31, the method further comprising:
routing one or more data units, of the corresponding data units, based on one or more of a forwarding table or an encapsulation table retrieved during the concurrent processing one or more keys, of the quantity of the two or more keys, where the one or more data units correspond to the one or more keys, of the quantity of the two or more keys.

### Claim 38

A network device comprising:
a processor to:
receive a plurality of data structures, where each data structure, of the plurality of data structures, includes a key associated with routing associated data, and
concurrently process up to a particular quantity of keys to obtain routing information for routing the associated data,
where the particular quantity corresponds to two or more, and
where the particular quantity is determined based on a latency of a memory and an amount of time for the processor to process a key.

### Claim 39 (depends on 38)

The network device of claim 38, where the processor is further to:
modify up to the particular quantity of data structures, of the plurality of data structures, based on concurrently processing the particular quantity of keys, and
route up to the particular quantity of data based on modifying up to the particular quantity of data structures.

### Claim 40 (depends on 38)

The network device of claim 38, where, when concurrently processing up to the particular quantity of data structures, the processor is further to:
begin a processing of a first data structure, of the particular quantity of data structures,
interrupt the processing of the first data structure, where the processing of the first data structure is interrupted prior to a completion of the processing of the first data structure,
begin a processing of a second data structure, of the particular quantity of data structures, based on the interruption of the processing of the first data structure, where the second data structure is different from the first data structure,
interrupt the processing of the second data structure, where the processing of the second data structure is interrupted prior to a completion of the processing of the second data structure, and
resume the processing of the first data structure based on the interruption of the processing of the second data structure.

### Claim 41 (depends on 38)

The network device of claim 38, where the plurality of data structures correspond to a plurality of packets received by the network device,
where each packet, of the plurality of packets, includes a header portion and a data portion, and
where, for each packet, of the plurality of packets, the processor is further to:
parse the header portion of the packet,
determine control information associated with the packet based on parsing the header, and
convert the packet into a corresponding data structure, of the plurality of data structures, where the corresponding data structure further includes the parsed header portion of the packet, the control information, and the data portion of the packet.

### Claim 42 (depends on 41)

The network device of claim 41, where the parsed header portion of the packet includes layer 2 data included in the header portion of the packet and layer 3 data included in the header portion of the packet, and
where the packet is converted into the corresponding data structure based on the layer 2 data and the layer 3 data.

### Claim 43 (depends on 38)

The network device of claim 38, where, when interrupting the processing of the first data structure, the processor is to:
generate a partial result associated with the processing of the first data structure, and
store the partial result and information identifying a processing state associated with the processing of the first data structure in a buffer of the network device, and
where, when resuming the processing of the first data structure, the processor is to:
obtain the partial result and the information identifying the processing state from the buffer, and
resume the processing of the first data structure based on the partial result and the information identifying the processing state.
