Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2001-03-08
2004-11-30
Vincent, David (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000
Reexamination Certificate
active
06826180
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention is related to the field of packet communications, and in particular, to packet processing circuitry.
2. Statement of the Problem
A communication packet is a unit of information that is transferred from one point to another over a communication system. The packet includes a header that indicates to the communication system how the packet should be processed. The primary task when processing a packet is properly routing the packet from the sender to the receiver, although there are many other tasks, such as security, service classification, billing, and address translation. Two common examples of packet communication protocols are the Internet Protocol (IP) and the Asynchronous Transfer Mode (ATM) protocol.
Communication packet processors are integrated circuits that receive, process, and transmit packets. With an insatiable demand for high-speed communications, packet processors are being driven to handle more packets at higher speeds. Compounding the problem is the desire that packet processors offer a more robust set of packet handling options.
To accomplish this difficult task, a packet processor includes a high-speed core processor that executes a packet processing software application. Under software control, the core processor processes the header of an incoming packet to retrieve context information from a memory for the packet. The context information specifies how the packet should be handled with respect to routing, security, and other areas. Under software control, the core processor then processes the context information to control packet handling.
To retrieve the desired context information, the core processor must associate the packet header with the memory locations that hold the desired context information. The core processor must then retrieve the desired context information from the associated memory locations. If the core processor modifies the context information, it must then write the modified context information back to the correct memory locations. This process is repeated for each packet, so the core processor is repeatedly associating headers with memory locations, retrieving context information, and writing modified context information to the memory locations.
This task is further complicated by the increase in processing options that can be applied to a packet. As the processing options increase, so does the size of the context information that specifies these options. The core processor must now handle increasingly larger amounts of context information, or the core processor must selectively retrieve only the desired data contained in the context information.
With increasing speeds and processing requirements, the core processor is becoming over-tasked. The result is either a loss of speed or processing options. One solution is simply to add higher-speed processors. Unfortunately, this solution adds too much cost to the underlying system.
A Content-Addressable Memory (CAM) is an integrated circuit that can search a list at high speed to provide a corresponding result. The CAM is configured with a list of selector entries. Each selector entry has a corresponding result. When the CAM receives an input selector, it searches the list of selector entries for a match. The search is accomplished at high speed by concurrently comparing each selector entry to the input selector. Unfortunately, CAMs have not been effectively applied to help solve the above problem.
SUMMARY OF THE SOLUTION
The invention helps solve the above problems with packet processing circuitry that relieves the core processor of the complexity of retrieving selected context information. A look-up engine operates with a CAM to selectively retrieve context information from memory and present the core processor with a summation block of relevant context information for each packet. The look-up engine can then write a selector to the CAM and write the summation block to a corresponding memory location. Advantageously, the CAM can be used to quickly retrieve the entire summation block. The circuitry can operate at high speeds, and core processor capacity is freed up for other processing tasks. In addition, the context information can be managed as a single database of context structures that is shared by the packets.
In some examples of the invention, packet processing circuitry comprises a processor and a look-up engine. The processor receives and processes a summation block to control handling of first and second communication packets. The processor also generates and transfers an installation instruction to the look-up engine. For the first communication packet, the look-up engine: 1) transfers a first selector to a CAM and receives a corresponding first result from the CAM, 2) retrieves a first context structure based on the first result and builds a summation block using the first context structure, 3) transfers the summation block to the processor, 4) receives the installation instruction for the summation block, 5) writes a second selector to the CAM and receives a corresponding second result from the CAM, and 6) writes the summation block to a memory location corresponding to the second result. For the second communication packet, the look-up engine: 1) transfers the second selector to the CAM and receives the corresponding second result from the CAM, and 2) retrieves the summation block based on the second result and transfers the summation block to the processor.
The processor may process first header information from the first communication packet to generate and transfer the first selector to the look-up engine. The processor may process second header information from the second communication packet to generate and transfer the second selector to the look-up engine. The first context structure may relate to network address translation, billing, packet forwarding, packet security, and packet classification. For the first communication packet, the look-up engine may: 1) transfer a third selector to the CAM and receive a corresponding third result from the CAM, 2) retrieve a second context structure based on the third result, and 3) build the summation block using the second context structure.
The circuitry may include the CAM. The CAM may receive and process the first selector for a first match and transfer the first result corresponding to the first match. The CAM may receive and write the second selector and transfer the corresponding second result. The CAM may receive and process the second selector for a second match and transfer the second result corresponding to the second match.
The look-up engine may receive a de-installation instruction, and in response, clear the second selector and the second result from the content-addressable memory and clear the summation block from the memory location. The look-up engine may track an age of the summation block, and if the age exceeds an aging threshold, clear the second selector and the second result from the content-addressable memory and clear the summation block from the memory location. The summation block may include counters and the look-up engine may automatically increment the counters in response to the first communication packet and automatically increment the counters in response to the second communication packet. The processor, look-up engine, and CAM may be configured on a single integrated circuit.
REFERENCES:
patent: 5329618 (1994-07-01), Moati et al.
patent: 5926626 (1999-07-01), Takeuchi et al.
patent: 6304903 (2001-10-01), Ward
patent: 6377577 (2002-04-01), Bechtolsheim et al.
patent: 6502163 (2002-12-01), Ramankutty
patent: 6535951 (2003-03-01), Ross
patent: 2001/0043614 (2001-11-01), Viswanadham et al.
patent: 2003/0123448 (2003-07-01), Chang
patent: 2004/0039845 (2004-02-01), Feldmeier et al.
patent: WO 99/14893 (1999-03-01), None
Bergantino Paul V.
Kujtkowski Anna K.
Winston Jeffrey M.
Kind Keith
Mindspeed Technologies Inc.
Vincent David
LandOfFree
Communication packet processor with a look-up engine and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Communication packet processor with a look-up engine and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication packet processor with a look-up engine and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3297301