Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2000-03-07
2003-11-25
Vincent, David (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
C370S236000
Reexamination Certificate
active
06654342
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to communicating flow control information in packet switching systems; and more particularly, the invention relates to accumulating and distributing flow control information via update messages and piggybacked flow control information in other messages in a packet switching system.
BACKGROUND OF THE INVENTION
The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology.
As used herein, the term “packet” refers to packets of all types, including, but not limited to, fixed length cells and variable length packets. Moreover, these packets may contain one or more types of information, including, but not limited to, voice, data, video, and audio information. Furthermore, the term “system” is used generically herein to describe any number of components, packet switch elements, packet switches, networks, computer and/or communication devices or mechanisms, or combinations thereof.
Consumers and designers of these systems typically desire high reliability and increased performance at a reasonable price. A commonly used technique for helping to achieve this goal is for these systems to provide multiple paths between a source and a destination. Packets of information are then dynamically routed and distributed among these multiple paths. It is typically more cost-effective to provide multiple slower rate links or switching paths, than to provide a single higher rate path. Such designs also achieve other desired performance characteristics.
Under certain circumstances and typically for a limited duration, these switching systems can have internal congestion as well as congestion at the output ports. The amount of the congestion can be decreased if the ports sending packets over the congested paths or to the congested output ports stop or decrease sending packets for a period of time. A mechanism is needed to provide this flow control information to the sending ports.
Many prior communications systems, such as early routers and switches, were typically bus based with no internal buffering. In such systems, when there was congestion, either the output line cards would drop cells locally or the output line cards would send messages back to the input line cards informing them of the congestion. Such systems either sent a broadcast message for each flow control data item, or sent multiple messages. Such techniques required a significant amount of bandwidth. New methods and apparatus are needed to efficiently communicate flow control information between output and input line cards.
Additionally, in other communications systems which had buffered switching fabrics, fabrics typically turn off all traffic going to all destinations when their buffers become filled, regardless of which internal pathway or destination is congested. Other prior systems support event-based flow control, wherein the fabric will individually turn on or off traffic going to individual destinations by sending separate messages for each such event to the input line cards.
Once again, such prior approaches are deficient in their approach because they over-react (e.g., stopping traffic to non-congested ports) and/or because they require a significant amount of bandwidth to communicate flow control information. New methods and apparatus are needed to efficiently communicate flow control information between output and input line cards, and between the switch fabric and input line cards.
New methods and systems are needed for a packet switching system to efficiently and effectively react to the generated and communicated flow control information, especially when multiple sources are sending to a single output. These sources when turned off to a particular destination may accumulate packets in their buffers. If all these sources begin sending at the same time in response to a flow control message turning on the traffic to the particular output, congestion may quickly return and force the sources to be turned off, as well as possibly overflowing buffers within the packet switching system.
SUMMARY OF THE INVENTION
A method is disclosed for propagating flow control information from a first element to a second element of a packet switching system. In one embodiment, the first element sends a flow control data structure update message to a second element. The first element also includes flow control information in a first non-flow control message being sent from the first element to the second element.
REFERENCES:
patent: 4491945 (1985-01-01), Turner
patent: 4494230 (1985-01-01), Turner
patent: 4630260 (1986-12-01), Toy et al.
patent: 4734907 (1988-03-01), Turner
patent: 4829227 (1989-05-01), Turner
patent: 4849968 (1989-07-01), Turner
patent: 4893304 (1990-01-01), Giacopelli et al.
patent: 4901309 (1990-02-01), Turner
patent: 5127000 (1992-06-01), Henrion
patent: 5173897 (1992-12-01), Schrodi et al.
patent: 5179551 (1993-01-01), Turner
patent: 5179556 (1993-01-01), Turner
patent: 5229991 (1993-07-01), Turner
patent: 5253251 (1993-10-01), Aramaki
patent: 5260935 (1993-11-01), Turner
patent: 5339311 (1994-08-01), Turner
patent: 5367523 (1994-11-01), Chang et al.
patent: 5402415 (1995-03-01), Turner
patent: 5491801 (1996-02-01), Jain et al.
patent: 5815667 (1998-09-01), Chien et al.
patent: 5842040 (1998-11-01), Hughes et al.
patent: 5901138 (1999-05-01), Bader et al.
patent: 6272107 (2001-08-01), Rochberger et al.
patent: 6304549 (2001-10-01), Srinivasan et al.
patent: 6377548 (2002-04-01), Chuah
patent: 6505253 (2003-01-01), Chiu et al.
Stallings, Data And Computer Communications, 5th edition, 1997, pp.: 313, 317-318, 323.*
Jonathan S. Turner, “An Optimal Nonblocking Multicast Virtual Circuit Switch,” Jun. 1994, Proceedings of Infocom, 8 pages.
Chaney et al., “Design of a Gigabit ATM Switch,” Feb. 5, 1996, WUCS-96-07, Washington University, St. Louis, MO, 20 pages.
Turner et al., “System Architecture Document for Gigabit Switching Technology,” Aug. 27, 1998, Ver. 3.5, ARL-94-11, Washington University, St. Louis, MO, 110 pages.
Dittia Zubin D.
Eatherton William N.
Fingerhut John Andrew
Galles Michael B.
Turner Jonathan S.
Cisco Technology Inc.
The Law Offices of Kirk D. Williams
Vincent David
LandOfFree
Accumulating and distributing flow control information via... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Accumulating and distributing flow control information via..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Accumulating and distributing flow control information via... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3131997