Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2001-03-06
2004-12-14
Ho, Duc (Department: 2665)
Multiplex communications
Data flow congestion prevention or control
C370S413000
Reexamination Certificate
active
06831891
ABSTRACT:
FIELD OF THE INVENTION
The present invention is in the field of routing packets through alternative paths between nodes in a routing fabric, and pertains in particular to methods by which back-ups in a fabric may be avoided.
BACKGROUND OF THE INVENTION
With the advent and continued development of the well-known Internet network, and of similar data-packet networks, much attention has been paid to computing machines for receiving, processing, and forwarding data packets. Such machines, known as routers in the art, typically have multiple interfaces for receiving and sending packets, and circuitry at each interface, including typically a processor, for handling and processing packets. The circuitry at the interfaces is implemented on modules known as line cards in the art. In some routers the line cards are interconnected through what is known as the internal fabric, which comprises interconnected fabric cards handling transmissions through the fabric. Fabric interconnection has not always been a part of routers in the art, and is a fairly recent innovation and addition for packet routers.
FIG. 1
, labeled prior art, illustrates a number of interconnected fabric nodes, labeled in this example A through J, each node of which may be fairly considered to comprise a fabric card in a switching fabric in a router. It will be apparent to the skilled artisan that
FIG. 1
is an exemplary and partial representation of nodes and interconnections in a switching fabric, and that there are typically many more nodes and interconnections than those shown.
One purpose of
FIG. 1
in this context is to illustrate that there are a wide variety of alternative paths that data may take within a switching fabric. For example, transmission from node E to node J may proceed either via path E-F-H-G-J, or alternatively via E-F-D-G-J. The skilled artisan will also recognize that the nodes and interconnections shown are but a tiny fraction of the nodes and interconnections that might be extant in a practical system.
In conventional switching fabric at the time of the present patent application fabric nodes in such a structure are implemented on fabric cards or chips that do Flow Control. Such Flow Control is very well-known in the art, and comprises a process of monitoring ports for real or potential traffic overflow, and notifying an upstream port to stop or slow sending of further data. That is, if node G as shown in
FIG. 1
, becomes overloaded at a particular input port, for example, the port from D, the Flow Control at G will notify D to restrict or suspend traffic to G In this example, D may receive traffic from upstream neighbors that it cannot forward to G, and it may then have to notify these neighbors to suspend sending traffic to D. This example illustrates how Flow Control may cause traffic changes made by nodes as a result of an overflow condition at a downstream node to propagate further upstream affecting further nodes, and further stopping or diverting traffic. In
FIG. 1
arrows between nodes are indicative of Flow Control indicators passed, and the skilled artisan will also understand that traffic may be in any direction, and that Flow Control indicators are therefore passed in both directions as well.
A serious problem with Flow Control as conventionally practiced is that the upstream notifications, inherent in flow control, propagate further upstream and hinder or stop traffic that there is no need to stop, partly because the interconnections of nodes may be quite complicated and the alternative paths quite numerous. Further, a node that has been informed of a downstream overload condition cannot select to stop or divert traffic just for that particular link, but only to stop or divert all traffic. These effects, because of the complexity and interconnection of nodes in a fabric, can result in complete stultification of parts of a system, or of an entire network.
There have been in the art several attempts to improve upon flow control, but all such solutions have only been partly successful, and still use upstream propagation of control indicators, which always still have a good chance of causing unwanted difficulty.
What is clearly needed is a way to deal with temporary overloads at fabric nodes without resorting to problematic upstream messaging without impacting traffic that does not need to use the overloaded link.
SUMMARY OF THE INVENTION
In a preferred embodiment of the present invention a method for managing data traffic at switching element in a fabric network, each node having two or more internally coupled ports is provided, comprising the steps of (a) establishing a managed queuing system comprising one or more queues associated with each port, for managing incoming data traffic; and (b) accepting or discarding data directed to a queue according to the quantity of data in the queue relative to queue capacity.
In some embodiments all data is discarded for a full queue. In some other embodiments the queue manager monitors quantity of queued data in relation to a preset threshold, and begins to discard data at a predetermined rate when the quantity of queued data reaches the threshold. In still other embodiments the queue manager increases the rate of discarding as quantity of queued data increases above the preset threshold, discarding all data traffic when the queue is full.
In another aspect of the invention a switching element for a fabric network is provided, comprising two or more internally-coupled ports, and a managed queuing system comprising one or more queues associated with each port, for managing incoming data traffic. The switching element is characterized in that the queue manager accepts or discards data directed to a queue according to the quantity of data in the queue relative to queue capacity.
In some embodiments all data is discarded for a full queue. In some other embodiments the queue manager monitors quantity of queued data against a preset threshold, and begins to randomly discard data when the quantity of queued data exceeds the threshold. In still other embodiments the queue manager increases the rate of discarding as the quantity of queued data increases above the preset threshold.
In still another aspect of the invention a data router having external connections to other data routers is provided, comprising an internal fabric network, and a plurality of switching elements in the internal fabric network, each having internally-coupled ports, and a managed queuing system comprising one or more queues associated with each port, for managing incoming data traffic. The router is characterized in that the queue manager accepts or discards data directed to a queue according to the quantity of data in the queue relative to queue capacity.
In some embodiments all data is discarded for a full queue. In some other embodiments the queue manager monitors quantity of queued data against a preset threshold, and begins to randomly discard data when the quantity of queued data exceeds the threshold. In still other embodiments the queue manager increases the rate of discarding as the quantity of queued data increases above the preset threshold.
In various embodiments of the invention taught below in enabling detail, for the first time a system is provided for routers that accomplished the purposes of flow control without requiring upstream notification of problems, which can often result in extensive and unnecessary cessation or diversion of traffic.
REFERENCES:
patent: 5282203 (1994-01-01), Oouchi
patent: 5442624 (1995-08-01), Bonomi et al.
patent: 5555264 (1996-09-01), Sallberg et al.
patent: 5768257 (1998-06-01), Khacherian et al.
patent: 5768258 (1998-06-01), Van As et al.
patent: 5777984 (1998-07-01), Gun et al.
patent: 5793747 (1998-08-01), Kline
patent: 5828653 (1998-10-01), Goss
patent: 5949757 (1999-09-01), Katoh et al.
patent: 6122252 (2000-09-01), Aimoto et al.
patent: 6144640 (2000-11-01), Simpson et al.
patent: 6167027 (2000-12-01), Aubert et al.
patent: 6246687 (2001-06-01), Siu
patent: 6292492 (2001-09-01), Bonomi et al.
patent: 6320845 (2001-11-01),
Basturk Erol
Mansharamani Deepak
Boys Donald R.
Central Coast Patent Agency Inc.
Ho Duc
Nguyen Phuongchau Ba
Pluris, Inc.
LandOfFree
System for fabric packet control does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for fabric packet control, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for fabric packet control will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3290243