Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reexamination Certificate
1997-12-04
2001-06-19
Harrell, Robert B. (Department: 2756)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C709S226000, C709S232000, C340S870030, C370S229000, C710S036000, C710S058000, C710S066000
Reexamination Certificate
active
06249819
ABSTRACT:
STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT
Not Applicable
BACKGROUND OF THE INVENTION
The present invention is related to flow control in a communications network, and more particularly to credit chaining to control data flow and eliminate data loss.
Broadly, flow control in communications networks can be permission based or non-permission based. In a permission based network, a transmitter obtains permission to transmit from a receiver prior to transmitting data. The permission includes an indication that sufficient buffer space is available at the receiver for receipt of the data. Permissions may be periodically sent as a matter of course or may be in direct response to a request to transmit generated by the transmitter. In a non-permission based network the transmitter operates without explicit advance indication that sufficient buffer space is available at the receiver. Permission based flow control provides improved accuracy and control relative to non-permission based flow control, and in particular allows for a service that avoids loss due to network congestion.
One known type of permission based flow control is Quantum Flow Control (“QFC”). QFC supports an Available Bit Rate (“ABR”) service in an Asynchronous Transfer Mode (“ATM”) network by controlling the number of ATM cells buffered at each device in a connection. In particular, QFC is applied to each flow through an input port and associated buffer in a receiving device to assure that sufficient buffer space is available.
Implementation of QFC avoids ATM cell loss due to network congestion. However, devices that are primarily output buffered present a difficulty because flows from a plurality of input ports in the device may converge upon a single output port and associated output buffer. The calculations necessary to avoid cell loss in the output buffered device consequently involve a many (transmitters):1 (receiver) relation, rather than the 1 (transmitter):1 (receiver) relation in the case of a primarily input buffered device. It is known to alleviate this problem by partitioning each output buffer to create one partition for each input port. However, the use of reserved buffer partitions can result in inefficient underusage of overall buffer space because unused but dedicated partitions are unavailable for use by other ports and flows. Further, the requisite overall buffer size grows as the number of input ports increases, and hence may not scale well in some device configurations.
BRIEF SUMMARY OF THE INVENTION
In accordance with the present invention, credits are chained between network devices. In a network with an intermediate network device, a network device that is upstream relative to the intermediate network device, and a network device that is downstream relative to the intermediate network device, credits are provided from the intermediate network device to the upstream network device based at least in part upon credits provided from the downstream network device to the intermediate network device. In order to achieve more efficient buffer utilization in some node architectures, e.g., output buffered architectures, credits may be chained as described above through each network device from the final destination device to the initial source device, thereby assuring sufficient buffer space to accommodate the data unit throughout the network prior to transmission from the initial source device. Alternatively, credits may be chained through fewer than each network device from the final destination device to the initial source device.
Credit chaining provides more efficient sharing of buffers among flows and prevents flows from becoming deadlocked. Some known flow control protocols dedicate a predetermined amount of buffer space to each individual flow. The dedicated buffer space is unavailable for use by other flows, even in the case where the flow to which the buffer space is dedicated is not utilizing the buffer space. More efficient buffer sharing is provided by credit chaining. Buffer sharing is implemented by preventing each individual flow from utilizing more than a predetermined proportional amount of buffering for storage at any network element at any time. The proportional amount is dynamically adjusted to ensure that each flow receives a “fair” proportion of the buffer space. Flows are prevented from becoming deadlocked because permission to forward traffic to devices further downstream than the next hop is obtained in advance. Advantageously, buffering requirements in network devices that implement credit chaining scale well as the number of ports and flows increases.
REFERENCES:
patent: 4849968 (1989-07-01), Turner
patent: 4897833 (1990-01-01), Kent et al.
patent: 5029164 (1991-07-01), Goldstein et al.
patent: 5128932 (1992-07-01), Li
patent: 5166930 (1992-11-01), Braff et al.
patent: 5179556 (1993-01-01), Turner
patent: 5258979 (1993-11-01), Oomuro et al.
patent: 5280470 (1994-01-01), Buhrke et al.
patent: 5289462 (1994-02-01), Ahmadi et al.
patent: 5289463 (1994-02-01), Mobasser
patent: 5291481 (1994-03-01), Doshi et al.
patent: 5313454 (1994-05-01), Bustini et al.
patent: 5319638 (1994-06-01), Lin
patent: 5341373 (1994-08-01), Ishibashi et al.
patent: 5367520 (1994-11-01), Cordell
patent: 5371893 (1994-12-01), Price et al.
patent: 5377327 (1994-12-01), Jain et al.
patent: 5392280 (1995-02-01), Zheng
patent: 5432784 (1995-07-01), Ozveren
patent: 5432824 (1995-07-01), Zheng et al.
patent: 5463775 (1995-10-01), DeWitt et al.
patent: 5491694 (1996-02-01), Oliver et al.
patent: 5515359 (1996-05-01), Zheng
patent: 5517495 (1996-05-01), Lund et al.
patent: 5528591 (1996-06-01), Lauer
patent: 5533009 (1996-07-01), Chen
patent: 5610745 (1997-03-01), Bennett
patent: 5617409 (1997-04-01), Ozveren et al.
patent: 5748613 (1998-05-01), Kilk et al.
patent: 5781533 (1998-07-01), Manning et al.
patent: 5852602 (1998-12-01), Sugawara
patent: 5953318 (1999-09-01), Nattkemper et al.
Dynamic Queue Length Thresholds in a Shared Memory ATM Switch Abhijit K. Choudhury and Ellen L. Hahne, AT&T Bell Laboratories, Murray Hill, NJ 07974-0636.
Design and Performance of Multinet Switch: A Multistage ATM Switch Architecture with Partially Shared Buffers Hyong S. Kim, Member, IEEE.
VLSI Implementations of ATM Buffer Management, Charles Zukowski 7 Tong-Bi Pei Departement of Electrical Engineering Center for Telecommunications Research, Columbia University.
Traffic Characteristics Evaluation of a Shared Buffer ATM Switch Noboru Enco, Toshiya Ohuchi Takahiko Kozaki, Hiroshi Kuwahara and Makoto Mori Central Research Laboratory, Hitachi, Ltd., Totsuka Works, Hitachi, Ltd.
Methodologies for Bandwidth Allocation, Transmission Scheduling, and Congestion Avoidance in Broadband ATM Networks, K. Sriram Room 3H-607, AT&T bell Laboratories, Holmdel, NJ 07733.
Overflow Analysis for Finite Waiting Room Systems, Roch Guerin, Member, IEEE, and Luke Y. C. Lien.
Hunt Douglas H.
Nair Raj Krishnan
Fujitsu Network Communications, Inc.
Harrell Robert B.
Weingarten, Schurgin Gagnebin & Hayes LLP
Willett Steve
LandOfFree
Method for flow controlling ATM traffic does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for flow controlling ATM traffic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for flow controlling ATM traffic will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514891