In-line packet processing

Details In-line packet processing In-line packet processing

1998-08-04

2004-09-14

Hsu, Alpus H. (Department: 2665)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S392000, C370S395100, C370S428000, C370S474000

Reexamination Certificate

active

06791947

ABSTRACT:

BACKGROUND
The present invention relates generally to data routing systems, and more particularly to methods and apparatus for efficiently routing packets through a network.
In packet switched communication systems, a router is a switching device that receives packets containing data or control information on one port, and based on destination information contained within the packet, routes the packet out another port to a destination (or an intermediary destination). Conventional routers perform this switching function by evaluating header information contained within a first data block in the packet. The header includes destination information that can be used in determining the proper output port for a particular packet.
Efficient switching of packets through the router is of paramount concern. Referring now to
FIG. 1
, a conventional router includes a plurality of input ports
2
each including an input buffer (memory)
4
, a switching device
6
and a plurality of output ports
8
. Data packets received at input port
2
are stored at least temporarily, in memory
4
while destination information associated with each packet is decoded to determine the appropriate switching through switching device
6
.
Data packets include both header and data fields and can be of variable lengths. The header includes both format information related to the type of packet and layer data. Networking protocols are defined in terms of layers, with each layer responsible for different portions of the communications in the network. For example TCP/IP is a standard internet network protocol that includes an application layer, transport layer, IP layer (network layer or L
3
), link layer (L
2
) and physical layer (L
1
). A data packet can include a plurality headers, one for each relevant layer that is to handle the packet during routing. Each layer header can include source and destination information as well as other layer specific information. To transfer the packet out of the switch, portions of the header are required to be examined (e.g., Layer
2
and Layer
3
, L
2
and L
3
respectively, header information). Typically, packets are stored in memory
4
while header processing is performed.
Complicating the examination process, the format of the packet headers can vary. Destination or other information (e.g., L
3
information) may not always be located at the same position in a header.
Unfortunately, conventional routers are inefficient in a number of respects. Conventional routers are incapable of processing packets in-line. All of the packet header typically must be received prior to the beginning of header processing. Packets are not screened early on for faults necessitating additional bandwidth and resources for handling these bad packets.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention provides a method of in-line processing a data packet while routing the packet through a router in a system transmitting data packets between a source and a destination over a network including the router. The method includes receiving the data packet and pre-processing layer header data for the data packet as the data packet is received and prior to transferring any portion of the data packet to packet memory. The data packet is thereafter stored in the packet memory. A routing through the router is determined including a next hop index describing the next connection in the network. The data packet is retrieved from the packet memory and a new layer header for the data packet is constructed from the next hop index while the data packet is being retrieved from memory. The new layer header is coupled to the data packet prior to transfer from the router.
Aspects of the invention include numerous features. The pre-processing step includes screening header layer data associated with the data packet for errors and dropping a bad data packet prior to transferring any portion of the data packet to packet memory. The screening includes screening Layer
2
(L
2
) and Layer
3
(L
3
) headers for errors. The L
2
header can be examined to detect errors arising from unrecognized L
2
header formats and unconfigured L
2
connections. The L
3
header can be examined to detect data packets with checksum errors, packet length errors and L
3
header errors.
The step of storing the data packet in memory includes dividing the data packet into cells of a fixed size and storing the cells in a distributed memory. The step of retrieving the data packet from memory includes reconstructing the packet from cells stored in the memory.
The pre-processing includes stripping L
2
header data from a data packet prior to storage the packet memory, identifying the beginning of the L
3
header and examining the L
3
header for errors prior to the storage of the data packet in the packet memory. The next hop index is a pointer to a sequence stored in a storage device within the router and the step of constructing a new layer header includes executing the sequence. The execution of the sequence includes retrieving a common template for constructing a common portion of an L
2
header to be attached to the data packet and a custom template for constructing a unique portion of the L
2
header. The common and unique templates can be executable code operable to construct and associated portion of an L
2
header for the data packet.
The step of receiving the data packet includes receiving a plurality of data packets for processing from a plurality of input ports representing a plurality of streams of data to be routed through the router. The step of pre-processing the data packet includes dividing the data packet into fixed length cells and parsing the L
2
header associated with the first cell of the data packet prior to receipt of the entire data packet. The step of parsing the L
2
header includes examining the L
2
header for errors and identifying the start of a next layer header in the data packet.
The cells for a data packet can be temporarily stored in a queue after L
2
header parsing is completed. Consecutive cells in a data packet can be sprayed to a different bank in the packet memory.
The method can include snooping while the cells are being written to the queue and parsing the L
3
header including examining the L
3
header for errors. A data packet can be dropped if errors are detected in the L
2
header during L
2
header parsing without storing a cell associated with the data packet in the queue.
In another aspect, the invention provides a router for in-line processing a data packet while routing the packet in a system transmitting data packets between a source and a destination over a network including the router. The router includes a packet memory for storing portions of the data packet, an input port for receiving a data packet including a header processing engine for evaluating header layer information upon receipt and prior to the storage of the data packet in the packet memory, a controller operable to determine packet routing through the router and output a next hop index indicating the next connection in the network for each data packet to be routed through the router and an output port for transferring the data packet to the destination. The output port includes a output formatter for constructing a layer header for the data packet to facilitate the transfer of the packet to the destination.
Aspects of the invention include numerous features. The header processing engine is operable to screen header layer data associated with the data packet for errors and drop a bad data packet prior to transferring any portion of the data packet to packet memory. The header processing engine screens Layer
2
(L
2
) and Layer
3
(L
3
) headers for errors. The header processing engine examines the L
2
header to detect errors arising from unrecognized L
2
header formats and unconfigured L
2
connections. The header processing engine examine the L
3
header to detect data packets with checksum errors, packet length errors and L
3
header errors.
The router can include a cell packetizer operable to divide the da

Affiliated with

Also associated with

Rating

In-line packet processing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with In-line packet processing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and In-line packet processing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3224032