Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-06-04
2003-09-30
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S401000
Reexamination Certificate
active
06628653
ABSTRACT:
BACKGROUND TO THE INVENTION
1. Field of the Invention
The invention relates to packet processing apparatus, to methods of reconfiguring a packet processor, and to methods of using a packet processor.
2. Background Art
It is known to transmit data in packets, each packet having header information as part of the packet, for use in processing the packet. The location and meaning of the header information within each packet is defined by a protocol. Most packet data transmission networks use multiple layers of protocols, in a hierarchy, according to the well known ISO model. Starting with the raw data from a top level application, each protocol adds its own header information to that added previously by preceding (higher) protocols. In the course of transmission through the network, the packet may pass through and be routed, forwarded switched or processed according to information stored in various parts of the packet header, depending on which level of the various levels of protocols, is being used.
Conventionally, in a router or switch operating according to a given one of the protocols, for each incoming packet, particular bits in the header relating to that given protocol are examined. The packet would be routed using those bits and passed to a chosen output port. Dedicated hardware is often used for speed of operation.
New types of protocol processing using different parts of header or payload information with different meanings, are always being proposed, at all different layers, to meet new requirements for e.g. quality of service, billing functions, error handling, grouping of packets, prioritizing, and so on. However, development of appropriate hardware is time consuming, even when groups of programmable logic chips are used, for a number of reasons. Connections between such chips must be defined and fixed, and changes made to the relatively complex logic which is often involved, will often have consequences to other parts of the logic, which are difficult to manage.
Software simulations and verifications of hardware designs can be carried out, but often do not reveal all the problems of a real hardware implementation.
Programmable chips for switching packets of particular protocols are known, e.g. ethernet switching chips, and protocol-specific dedicated router chips. Such router chips can extract destination information from a packet using hardcoded logic to achieve higher speed or throughput. They use a routing table whose entries can programmed from an external host.
A chipset produced by Obtek provides multiprotocol packet routing. A programmable filter examines the contents of each incoming packet to derive the buried protocols and retrieve source and destination addresses. The filter passes a packet descriptor to a routing systems control chip which manages memory allocation, input and output queues.
This filter is programmable using a proprietary language, a rule-based language which enables a programmer to define actions to be taken according to recognition of bits in a packet. As the filter's active structure parses and processes the unknown incoming packet, it is capable of activating other processors (including a host) or special hardware (for very high performance) to perform concurrent and supporting tasks.
SUMMARY OF THE INVENTION
It is an object of the invention to provide improved methods and apparatus.
According to a first aspect of the invention there is provided a packet processing apparatus comprising:
a programmable hardware discriminator for receiving incoming packets, and selecting bits from any part of the incoming packets;
a decision table for storing information relating to how the packets are to be processed;
programmable hardware searching logic coupled to the decision table and to the discriminator for accessing the information in the table according to the selected bits; and
a packet handler coupled to the searching logic, for processing the packets according to the result of the access.
Advantages include the following:
a) Providing programmable table searching logic means that the search algorithm and any corresponding table maintenance functions can be altered without necessarily altering the table contents, or the bit selection hardware. This separation of these functions can make it easier to develop and refine applications using new protocol components, since changes to algorithms can be made more directly, at a lower level. It may enable applications to be developed to run faster, or use memory more efficiently for example. This was not possible in previous arrangements in which it was only possible to define the overall outputs of such algorithms for given states of the bits selected from the packet, without being able to define how the selected bits were processed, or how a table of all the possible outputs is searched.
b) Since many networking processing tasks can be broken down into bit selection and table searching, this generic type of arrangement will suit a wide variety of applications.
c) Having the bit selection function programmable, and able to select bits from any part of the incoming packets enables a wider range of operations using different protocols to be handled. This also makes it easier to interface with different input line interfaces, and enables subsequent processing to be streamlined, if all the necessary information in the packet can be extracted in one step.
d) Providing the table searching logic in hardware enables the speed of operation to be faster than equivalent software, and makes it easier for the developer to resolve timing issues in the design.
e) Developing logic directly in hardware can reduce the effort needed to convert a working prototype into a product ready for use in the field, and thus reduce the all important time to market for a product. The arrangement could be used in networks which are designed to be reconfigurable in operation, e.g. active networks which may be reconfigured to suit traffic conditions.
f) Having a programmable search algorithm enables the algorithm to be tailored to reduce search times, and improve throughput, for example by using the minimum number of bits or columns in the table necessary for searching, according to the application.
g) Having an explicit table can make it easier to maintain the contents of the table if it can be accessed directly. This is in contrast to previous arrangements having an implicit table not accessible directly, but defined by mappings of output for a given state of bits selected from the packet. If there are many such mappings having the same output, then any change in that one output would require changing all the mappings which mention that output. Having direct access to the table enables one table entry to be changed which may be simpler and quicker than changing multiple mappings in such a case.
Preferably the apparatus further comprises at least one packet output port, and the packet handler comprises a programmable hardware interpreting logic coupled to the packet output port, for interpreting the result of the access, to control the packet output port.
An advantage of providing a programmable interpreting logic is that the reaction to the result of the table search can be separately programmed, without necessarily altering other elements.
Preferably the interpreting logic is arranged to react to both a match and a mismatch result.
An advantage of being able to program action on a mismatch is that it broadens the range of applications to cover for example those in which a mismatch result can be used to alter the table, or to broadcast a packet. This is significant for following the “route once, switch many” principle, which means where a packet is received, if the table does not include its destination, it may be routed by for example a host CPU based routing algorithm, or by broadcasting to neighbouring nodes, but thereafter, the table learns the destination, and the remaining packets can be switched without the lengthy delay of using the CPU, or the inefficiency inherent in broadcasting.
Preferably the programmable hardware
Nguyen Chau
Trinh D.
LandOfFree
Programmable packet switching device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Programmable packet switching device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable packet switching device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3096972