Defferrable processing option for fast path forwarding

Details Defferrable processing option for fast path forwarding Defferrable processing option for fast path forwarding

1999-08-25

2004-09-07

Ton, Dang (Department: 2666)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S429000

Reexamination Certificate

active

06788680

ABSTRACT:

CROSS REFERENCE TO RELATED APPLICATIONS
N/A
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
N/A
BACKGROUND OF THE INVENTION
Networking devices are typically designed to process received packets at high speeds. For example, a network switch must perform high speed packet forwarding so that it does not become a bottleneck on packet throughput within the network. High speed processing of received packets usually requires custom designed hardware circuitry, as may be provided by one or more Application Specific Integrated Circuits (ASICs). While all functions of the device could be performed by such high speed hardware, the costs associated with designing, debugging, and manufacturing such circuits increase significantly with their functional complexity. Accordingly, the functions provided by such devices are often divided into two categories: “core” functions processed within a high speed, hardware processing path (referred to as the “fast forwarding path”, or “fast path”), and other functions processed outside the fast path, using lower cost, lower speed components.
For example, a router typically has its routing functionality implemented in a number of application specific integrated circuits (ASICs) to permit high speed forwarding of received packets. The hardware used to provide this fast path is often provided on a per-port basis, so that each port is provided with dedicated logic for processing packets passing through it. A slower processing path, which may be implemented by a shared management subsystem of the device, is also provided to perform functions not performed by the fast path. Functions performed in the slower processing path include, for example, processing of packets containing certain Internetworking Protocol (IP) options fields. One such IP option permits the source of a packet to indicate, within the packet, a specific route through the network which the packet must take to its destination. Since processing of packet information in this relatively slower path is often done under microprocessor control, it is sometimes referred to as the “microprocessor path”. However, since this slower path may be any secondary processing path of the device other than the fast path, whether it is implemented using a microprocessor or some other processing technology, it is referred to herein as the “slow path”.
In existing networking devices, most received packets are processed completely using the fast path only. Some relatively small subset of received packets are forwarded to the slow path, including, for example, SNMP (Simple Network Management Protocol) packets. Those packets forwarded to the slow path are processed using the management subsystem, and then forwarded through an output port of the device or discarded.
Typical data units (“packets”) used to convey messages between nodes in a communications network include one or more header portions, in addition to a data portion. Packet headers are often provided with a fixed part and a variable part. Specifically, an IP header for an IP packet includes a variable length part including some number of optional fields, referred to as “options”. The options within the packet header are encoded using a form of type, length, value (TLV) encoding. Specific options may or may not be supported by each networking device. When a device determines that an option within a received packet is not supported, the type of the option controls whether the packet must be dropped at that device, or whether the option can be skipped, and the remainder of the packet processed as needed. In this sense, existing options may be considered to fall within one of two categories: 1) those requiring the receiver to drop the received packet if the option is not understood, and 2) those requiring the receiver to simply skip the option if it is not supported.
In many networking devices, when any optional field is detected in a received packet, the entire packet is passed over to the slow path for processing of the option prior to the packet being forwarded from the device. Other existing systems provide processing of some options in the fast path, while other options require passing the packet to the slow path, which processes the option and then causes the packet to be forwarded if necessary. A significant drawback of such designs is that they delay forwarding of a received packet which includes an option field until after the option has been completely processed. This effectively limits the use of options, since any options that are processed by a networking device such as a router, and that are included in packets that must be forwarded, may increase the delay experienced by those packets at the router.
Accordingly it would be desirable to have a system for performing optional processing of a received data unit, which does not introduce undue delay into the packet forwarding process. The system should permit support for new options to be conveniently added and be compatible with existing systems.
BRIEF SUMMARY OF THE INVENTION
A system and method for providing deferred processing of information within a received data unit is disclosed, in which the data unit is forwarded as usual, and a portion of the packet is also stored for processing independent of the packet forwarding. The system detects whether the received data unit includes an indication of deferrable processing, such as a particular option type or flag. Option type ranges and multiple flags may be used to indicate various portions of the received packet that are to be stored for deferred processing, as well as whether individual or multiple copies of duplicate packets or packets with common characteristics should be stored. The number of packets or packet portions that can be stored may also be determined by cache sizes or system configuration parameters. An example of a packet portion that is stored is the packet header, such as an IP header in the case where the deferred processing indication is contained within the IP header's optional portion.
After the system stores the portion of the packet, if any, that is needed to perform the deferred processing, the received packet may then be forwarded out of the receiving device, and the deferred processing may be started. The deferred processing may be performed later, for example as necessary resources become available. The deferred processing may also be performed in parallel with packet forwarding, but need not complete before the received packet is forwarded. In this way, completion of the deferred processing is not a bottle neck with regard to packet forwarding throughput.
The disclosed system is advantageously embodied in a networking device, such as a router, having a fast received packet processing path (the “fast path”), as well as a slower received packet processing path (the “slow path”). In such an embodiment, the disclosed system includes detection of a deferred processing indication by the fast path, which then stores the packet or necessary portion thereof, in addition to forwarding the packet. Adding support for deferred processing detection, as well as support for storage of packets or portions thereof, to the fast path introduces some minimal additional hardware complexity, but does not require the actual deferred processing to be performed by the fast path logic. Moreover, the disclosed system is conveniently extensible, since introducing support for new varieties of deferred processing to a device often will only require loading a new microprocessor program image.


REFERENCES:
patent: 5062106 (1991-10-01), Yamazaki et al.
patent: 5442633 (1995-08-01), Perkins et al.
patent: 5570084 (1996-10-01), Ritter et al.
patent: 5940399 (1999-08-01), Weizman
patent: 6119171 (2000-09-01), Alkhatib
patent: 6122665 (2000-09-01), Bar et al.
patent: 6147976 (2000-11-01), Shand et al.
patent: 6160808 (2000-12-01), Maurya
patent: 6212185 (2001-04-01), Steeves et al.

Affiliated with

Also associated with

Rating

Defferrable processing option for fast path forwarding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Defferrable processing option for fast path forwarding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Defferrable processing option for fast path forwarding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3219682