US 6,980,552 B1 · Pipelined packet switching and queuing architecture

Abstract

A pipelined linecard architecture for receiving, modifying, switching, buffering, queuing and dequeuing packets for transmission in a communications network. The linecard has two paths: the receive path, which carries packets into the switch device from the network, and the transmit path, which carries packets from the switch to the network. In the receive path, received packets are processed and switched in a multi-stage pipeline utilizing programmable data structures for fast table lookup and linked list traversal. The pipelined switch operates on several packets in parallel while determining each packet's routing destination. Once that determination is made, each packet is modified to contain new routing information as well as additional header data to help speed it through the switch. Using bandwidth management techniques, each packet is then buffered and enqueued for transmission over the switching fabric to the linecard attached to the proper destination port. The destination linecard may be the same physical linecard as that receiving the inbound packet or a different physical linecard. The transmit path includes a buffer/queuing circuit similar to that used in the receive path and can include another pipelined switch. Both enqueuing and dequeuing of packets is accomplished using CoS-based decision making apparatus, congestion avoidance, and bandwidth management hardware.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims33

Dependent claims

An apparatus for switching packets, each packet having a header portion, an optional corresponding tail portion, and a class of service indicator, the apparatus comprising:

a pipelined switch including:
a plurality of packet header buffers (PHBs);
a plurality of PHB pointers, each of the plurality of PHB pointers pointing to a PHB;
and
a plurality of pipeline stage circuits connected in a sequence and comprising at least a first stage circuit and a last stage circuit, wherein:
each of the plurality of pipeline stage circuits begins an operation substantially simultaneously with each other of the plurality of pipeline stage circuits;
each of the plurality of pipeline stage circuits passes data to a next stage circuit;
at least one of the plurality of pipeline stage circuits is operable to access a content addressable memory;
the first stage circuit reads the header portion and stores the header portion in at least one of the plurality of PHBs using at least one of the plurality of PHB pointers;
and
said last stage circuit outputs a modified header portion.

8 more elements

An apparatus for switching packets, each packet having a header portion, an optional corresponding tail portion, and a class of service indicator, the apparatus comprising:

a plurality of buffers;
a plurality of buffer pointers, each of the plurality of buffer pointers pointing to a buffer;
and
a plurality of means for processing packets, the plurality of means for processing packets being connected in a sequence and wherein:
each of the plurality of means for processing packets begins an operation substantially simultaneously with each other of the plurality of means for processing packets;
at least one of the plurality of means for processing packets passes data to at least another of the plurality of means for processing packets;
at least one of the plurality of means for processing packets further comprises a means for accessing a content addressable memory;
at least one of the plurality of means for processing packets further comprises a means for reading the header portion and storing the header portion in at least one of the plurality of buffers;
and
at least one of the plurality of means for processing packets further comprises a means for outputting a modified header portion.

7 more elements

Dependencies are inferred from the claim text.

Description23,015 words

Summary2,077 words

#1. Field of the Invention

#The present invention relates to communications devices, specifically devices that enable packet forwarding and handling in communications networks.

#2. Description of the Related Art

Brief description of the drawings25 figures

#The present disclosure may be better understood, and its numerous objects, features, and advantages made apparent to those skilled in the art by referencing the accompanying drawings.

#FIG. 1 is a high-level schematic representation of a switch system that contains prior art circuitry for the circuit/process of routing information packets.

#FIG. 2 is a high-level schematic of linecard control element 200 according to one embodiment of the present invention.

Detailed description20,371 words

#The use of the same reference symbols in different drawings indicates similar or identical items.

#The following sets forth a detailed description of at least the best contemplated mode for carrying out the one or more devices and/or processes described herein. The description is intended to be illustrative and should not be taken to be limiting.

#The present invention is an architecture for a linecard in a network communications device such as a router or switch. The linecard provides an interface between a routing or switching device and a network that operates bi-directionally, both receiving a data stream (e.g., packets) from the network and transmitting a data stream to the network. Typical devices comprise multiple linecards (and thus multiple network connections) and a single switching interconnect core or “fabric” that provides the physical connection between linecards.

Facts

Application

10/219,460Filed 15 Aug 2002 · continuation in part

Priority

14 Feb 2000

Granted

27 Dec 2005

Term ended

25 Nov 2020

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 285 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification17 codes

H04L 47/527
By attributing bandwidth to queues: quantum based scheduling, e.g. credit or deficit based scheduling or token bank
H04L 47/10
Traffic control in data switching networks: flow control; Congestion control
H04L 47/21
Flow control; Congestion control: using leaky-bucket
H04L 47/326
By discarding or delaying data units, e.g. packets or frames: with random discard, e.g. random early discard [RED]

Pipelined packet switching and queuing architecture

Life of this patent

Pipelined packet switching and queuing architecture

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims33

Description23,015 words

Drawings

Classification17 codes

Life of this patent

Description23,015 words