Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-06-22
2003-04-22
Patel, Ajit (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S415000
Reexamination Certificate
active
06553035
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital communications, and more particularly to systems and methods for queuing data being transferred between devices such as switching nodes in a digital data network.
BACKGROUND OF THE INVENTION
In digital communications systems, data can be transferred from an input or transmitting device to an output or receiving device. In such systems, it often occurs that data cannot immediately be transferred from the input device to the output device for some reason such as congestion or high data traffic at the input device and/or the output device. To solve this problem, such systems implement a queuing function which can buffer or queue data at the input and/or output devices. Input-queued data can be temporarily stored until it can be transferred to the output device. Output-queued data, which has been transferred from the input device, can be temporarily stored until it is forwarded to its eventual destination by the output device. One application for data queuing is in digital networks.
Digital networks have been developed to facilitate the transfer of information including data and programs among digital computer systems and numerous other types of devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In modem networks, information is transferred through a mesh of switching nodes which are interconnected by communication links in a variety of patterns. The mesh interconnected pattern can allow for a number of paths to be available through the network from each computer system or other device.
Information transferred from a source device to a destination device is generally transferred in the form of fixed-length or variable-length data packets, each of which is in general received by a switching node over a communication link and transmitted over another communication link to facilitate transfer of the packet to the destination device or to another switching node along a path to the destination device. Each packet typically includes address information including a source address that identifies the device that generated the packet and a destination address that identifies the particular device or devices which are to receive the packet.
Typically, a switching node includes one or more input ports, each of which is connected to a communication link on the network to receive data packets, and one or more output ports, each of which is also connected to a communication link on the network to transmit packets. Each node typically also includes a switching fabric that couples data packets from the input ports to the outport ports for transmission.
When an input port receives a packet from the network, it typically buffers the packet. It uses the destination address of the packet to identify the particular output port that is to transmit the packet onto the network and then transfers the packet to the identified output port through the switching fabric. When the output port receives the packet, it typically buffers the packet in a queue where it awaits transmission onto the network over the appropriate communication link. While buffering and scheduling by the output port can provide for efficient packet transmission by the output port, since the output port can be kept continually busy, several problems can arise with conventional output port buffering. Generally, each output port effectively provides one queue for each input port, in which case the total number of queues provided by the switching node will be on the order of N
2
, where N is the number of input ports, which, in turn, corresponds to the number of output ports, if, as is typical, each communication link provides for bidirectional transmission of packets. Thus, as N increases, the number of queues maintained by the output ports generally increases approximately quadratically.
Queues are generally expensive pieces of hardware, and, in general, the longer the queue, the more expensive it is to implement. Switching nodes in modern networks must accommodate large amounts of data which are transferred over network links at increasingly high rates. Communication links and the switching nodes to which they are connected must accommodate large bursts of data which occur in very short amounts of time, i.e., at very high rates. The average data rates that must be accommodated can also be very high. With these increased high data rates comes an increase in the required queuing capacities of the switching nodes, which results in the requirement that larger queues be implemented. Thus, the development of larger and faster systems results in the need for increasing numbers of longer queues, which in conventional queuing approaches can in turn result in increased cost.
SUMMARY OF THE INVENTION
The present invention is directed to an apparatus and method for queuing data. The invention can be employed in systems such as switching nodes on a digital network to queue data packets that are being transferred over the network or other types of data that are being transferred within the switching node itself. The queuing system of the invention is used to queue data that is being transferred from an input device, such as an input port module in a network switching node, to an output device, such as an output port module in a network switching node. The queuing apparatus of the invention utilizes a plurality of input ports in the input device that receive data to be transferred to the output device, such as from a communication link on a digital network. Each input port is adapted to receive the data at a data rate that is associated with the input port. The device includes a plurality of short queues for storing data received at the plurality of input ports. A long queue having more data storage capability than each of the short queues receives and stores data from the plurality of short queues and forwards the stored data toward the output device. A control circuit controls the transfer of data from the short queues to the long queues. The data are transferred at a second data rate higher than at least one of the data rates associated with the short queues such that a data threshold associated with at least one of the short queues is not exceeded. That is, in one embodiment, the short queues are emptied at a rate that is fast enough the prevent the at least one short queue from becoming full.
In general, each of the input ports can be associated with and operate at a different data rate. In one embodiment, the data rate associated with the input ports is selected to be the maximum data rate of all of the data rates associated with all of the input ports. In this case, because the control circuit transfers data from the short queues to the long queues at a rate faster than the selected rate, it is insured that none of the input queues will store data beyond their thresholds. For example, none of the queues will become full.
In one embodiment, the control circuit is associated with the output device for transferring data from the associated short queues to the associated long queue. The output device can include multiple output ports, in which case, the system would include multiple control circuits, each associated with a single output port.
The control circuit can include a selection circuit which selects the short queues to enable each short queue to transfer data to the long queue. The short queues can be selected in turn in a round-robin fashion, with each short queue being selected at a rate faster than the data rate associated with the input communication link. In one particular embodiment, during the round-robin selection process, before each queue is accessed, the control circuit determines whether each queue has data to be transferred. If no data is to be transferred, the queue can be skipped. This results in saving the time that would have been allocated for retrieval of data from the particular short queue. In one embodiment, the selection circuit includes a multiplexer for selectively
Koehler Jeffrey A.
Pelletier Eric J.
Schwartz Steven J.
Spada Eric J.
Boys Donald R.
Central Coast Patent Agency Inc.
Patel Ajit
Pluris, Inc.
LandOfFree
Apparatus and method for queuing data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for queuing data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for queuing data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3094842