Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-02-14
2004-08-17
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S429000, C370S389000
Reexamination Certificate
active
06778546
ABSTRACT:
BACKGROUND OF THE INVENTION
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
In a communications network, routing devices receive messages at one of a set of input interfaces and forward them on to one of a set of output interfaces. Users typically require that such routing devices operate as quickly as possible in order to keep up with the high rate of incoming messages. In a packet routing network, where information is transmitted in discrete chunks or “packets” of data, each packet includes a header. The header contains information used for routing the packet to an output interface and subsequent forwarding to a destination device. The packet may also be forwarded to another router for further processing and/or forwarding. Header information used for routing may include the destination address and source address for the packet. Additionally, header information such as the destination device port, source device port, protocol, packet length, and packet priority may be used. Header information used by routing devices for administrative tasks may include information about access control, accounting, quality of service (QoS), or class of service (CoS).
FIG. 1
is a generic packet routing/switching system
100
that will be used to describe both the prior art and the invention. A well-known routing device or switch
100
consists of a set of linecards
110
and a switching fabric
120
. Each linecard
110
includes an input interface
111
, an output interface
112
, a fabric interface
170
, and a control element
130
. Linecards
110
connect to communications network
1
, which may be any form of local, enterprise, metropolitan, or wide area network known in the art, through both input interface
111
and output interface
112
. More than one input interface
111
may be provided, with each interface carrying a fraction of the full capacity of control element
130
.
Control element
130
is configured to receive inbound packets
113
(i.e., packets entering the system from network
1
) from input interface
111
, process the packet, and transmit it through fabric interface
170
to switching fabric
120
through which it is sent to another (or the same) linecard
110
for further processing. This path is referred to as the “receive” path into the device from the network.
Outbound packets
114
(i.e., those to be transmitted out of the switch device) are received from switching fabric
120
through fabric interface
170
, processed in control element
130
, and transmitted to network
1
on output interface
112
. Accordingly, this path is known as the “transmit” path from the device to the network.
As known in the prior art, control element
130
consists of an inbound packet receiver
140
, lookup circuit
145
, inbound memory controller
150
, first memory
160
, outbound memory controller
150
, second memory
160
, and outbound transmitter
180
. Control circuits
190
are also provided to perform configuration, initialization, statistics collection, and accounting functions as well as to process certain exception packets.
In a manner well-known in the art, packets are received from the physical medium of the network at input interface
111
. The inbound packet receiver
140
operates in conjunction with lookup circuit
145
to determine routing treatments for inbound packets
113
. Lookup circuit
145
includes routing treatment information disposed in a memory data structure. Access and use of this information in response to data in the header of inbound packet
113
is accomplished with means well-known in the router art. These routing treatments can include one or more of the following:
selection of one or more output interfaces to which to forward inbound packets
113
responsive to the destination device, to the source and destination device, or to information in any other packet header fields (packets may also be dropped, i.e., not forwarded);
determination of access control list (ACL) treatment for inbound packets
113
:
determination of class of service (CoS) treatment for inbound packets
113
;
determination of one or more accounting records or treatments for inbound packets
113
; and
determination of other administrative treatment for inbound packets
113
.
Examples of such systems may be found in U.S. Pat. No. 5,088,032, METHOD AND APPARATUS FOR ROUTING COMMUNICATIONS AMONG COMPUTER NETWORKS to Leonard Bosack; U.S. Pat. No. 5,509,006, APPARATUS AND METHOD FOR SWITCHING PACKETS USING TREE MEMORY to Bruce Wilford et al.; U.S. Pat. No. 5,852,655, COMMUNICATION SERVER APPARATUS HAVING DISTRIBUTED SWITCHING AND METHOD to John McHale et al.; and U.S. Pat. No. 5,872,783, ARRANGEMENT FOR RENDERING FORWARDING DECISIONS FOR PACKETS TRANSFERRED AMONG NETWORK SWITCHES to Hon Wah Chin, incorporated in their entireties herein by reference.
One shortcoming known in the prior art arises from the ever-increasing need for speed in network communications. Attempts to scale prior art routers and switches to gigabit speed have shown that architectures that require a deep packet buffering prior to determining routing treatment suffer from high packet latency. Many distributed routing schemes, such as that described above wherein routing is performed in each linecard on packet receipt, have had only limited success in providing the necessary increase in throughput speed.
A related limitation has been the inability of a general purpose digital computer to perform the necessary lookup and queue management functions using software in real time, i.e., approaching the wire speed (line rate) of the incoming packets. As the need for increased packet throughput has grown, software-based systems have been shown to lack sufficient scaleability to the demands of modern internetworking systems.
A further drawback is the lack of flexibility in prior art systems tuned for speed with hardware implementations of functions once performed by software. As the hardware is less able to be reconfigured without redesign, these prior art designs are often rendered obsolete by the adoption of new standards and communications protocols.
A still further drawback of prior art systems is their relative inability to rapidly provide a range of services based on packet priority, as represented by various fields in the packet header. Such systems are often described as providing type of service (TOS), quality of service (QoS), or class of service (CoS) routing. Prior art systems typically experience additional packet latency and throughput reduction when performing routing based on packet priority.
What is needed is a flexible switch system, preferably distributed on a linecard, that provides ultra-high throughput packet switching based at least in part on packet priority. The system architecture should be able to be reconfigured to handle a variety of network protocols and optimizations. In particular, low latency switching determined by individual packet class of service is desired. Such a linecard should operate as close to line rate as possible, i.e., at or near the maximum speed of transmission over the physical medium and without any appreciable buffering delay.
SUMMARY
A high speed hardware-based dequeuing apparatus and method for switching packets in a communications network is disclosed. The dequeuing apparatus is part of a linecard consisting of two transmission 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. While each linecard typically has both a receive and a transmit path, such an arrangement is not essential. Separate transmit and receive linecards employing the architecture of the present invention are also possible.
In the receive path, packets are processed and switched in an asynchronous, multi-stage pipeline that operates on several packets at the same time to determine each packet's routing destination. Once that de
Epps Garry P.
Laor Michael
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Hsu Alpus H.
Tran Thien
LandOfFree
High-speed hardware implementation of MDRR algorithm over a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High-speed hardware implementation of MDRR algorithm over a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High-speed hardware implementation of MDRR algorithm over a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3344916