Method for flow controlling ATM traffic

• US 6,249,819 B1
• Filed: 12/04/1997
• Issued: 06/19/2001
• Est. Priority Date: 12/06/1996
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited, Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Original Assignee: Fujitsu Limited, Fujitsu Network Communications Incorporated (Fujitsu Limited)
• Inventors: Nair, Raj Krishnan, Hunt, Douglas H.
• Primary Examiner(s): Harrell, Robert B.
• Assistant Examiner(s): WILLETT, STEPHAN F
• Application Number:
  US08/985,048
• Time in Patent Office: 1,293 Days
• Field of Search: 709/226, 709/232, 709/235, 340/825.5, 340/825.33, 710/36, 710/37, 710/58, 710/59, 710/66, 370/229, 370/230, 370/231, 370/232, 370/233, 370/235, 370/236
• US Class Current: 709/232
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket
• CPC Class Codes: H04L 2012/5631 Resource management and allocation
• CPC Class Codes: H04L 2012/5634 In-call negotiation
• CPC Class Codes: H04L 2012/5647 Cell loss
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Permission based flow control is implemented in a computer network having at least a downstream, intermediate and upstream network device by receiving credits at the intermediate network device from the downstream network device and granting credits from the intermediate network device to the upstream network device based at least in part upon the credits received at the intermediate network device from the downstream network device. Credit chaining as described above is employed to permit the granting of the right to transmit downstream to be predicated upon buffer availability downstream of the next downstream network device. Via the use of credit chaining, high utilization of network resources is achieved with minimal loss of data traffic.

Claims

1. A method for implementing permission based flow control in a computer network having at least first, second and third network devices, where the first network device is downstream relative to the second network device and the third network device is upstream relative to the second network device, and wherein the second network device receives data units from and provides permission credits to the third network device and transmits data units to the first network device and receives permission credits from the first network device, comprising the steps of:

receiving permission credits at the second network device from the first network device; and

granting permission credits from the second network device to the third network device based at least in part upon the credits received at the second network device from the first network device, and wherein, at least at some times, the credits granted from the second network device to the third network device are greater than the credits received at the second network device from the first network device, and wherein, at least at some other times, the credits granted from the second network device to the third network device are no greater than the credits received at the second network device from the first network device.

2. The method of claim 1 wherein the first network device is a final destination, and wherein one or more network devices are coupled between the first network device and a source network device, and including, at least at some times, the further step of chaining the credits granted in the granting step through each network device from the first network device to the source network device prior to transmitting any data units from the source network device.

3. The method of claim 1 including the further step of transmitting a request to transmit from the third device to the second device.

4. The method of claim 3 including the further step of, in response to the request transmitted from the third network device to the second network device, transmitting a request to transmit from the second network device to the first network device.

5. The method of claim 4 including the further step of determining a number of credits in the first network device in response to the request to transmit received from the second network device.

6. The method of claim 5, wherein the computer network further includes a fourth network device, the fourth network device located upstream relative to the third network device, and wherein the third network device receives data units from and transmits permission credits to the fourth network device, and including the further step of granting, from the third network device to the fourth network device, less than or equal to the amount of credits received at the third network device from the second network device.

7. The method of claim 6 including the further step of granting, from the third network device to the fourth network device, an amount of credits in proportion to the drain rate of the third network device.

18. The method of claim 1, wherein the first network device, second network device and third network device each include at least one input port and at least one output port, and further comprising:

receiving the permission credits received at the second network device at the at least one input port of the second network device;

transmitting the permission credits granted by the second network device at the at least one output port of the second network device; and

receiving the permission credits granted by the second network device at the at least one input port of the third network device.

8. A network device for facilitating flow of data within a network including at least one network device that is upstream relative to the facilitating device and at least one network device that is downstream relative to the facilitating device, comprising:

a flow controller operative in response to a first transmit permission received from the downstream network device, and to provide a corresponding second transmit permission to the upstream network device based at least in part upon the first transmit permission, said first permission including a first number of permission credits, said second permission including a second number of permission credits, and wherein, at least at some times, said second number of permission credits is greater than said first number of permission credits, and wherein, at least at some other times, said second number of permission credits is not greater than said first number of permission credits.

9. The network device of claim 8 wherein said flow controller is further operative, in response to a first request to transmit received from the upstream network device, to generate a second request to transmit which is provided to the downstream network device.

10. The network device of claim 8 wherein said flow controller maintains indications of burst tolerance, a most recent permission credit value sent to the upstream network device, a running sum of permission credit values sent to the upstream network device, a most recent permission credit value received from the downstream network device and a running sum of permission credit values received from the downstream network device.

11. The network device of claim 10 wherein, responsive to a transmit permission received from the downstream network device, the most recent permission credit value received from the downstream network device and the running sum of permission credit values received from the downstream network device are updated.

12. The network device of claim 11 wherein, responsive to a transmit permission provided to the upstream network device, the sum of the most recent permission credit value sent to the upstream network device combined with the sum of permission credit values sent to the upstream network device is less than or equal to the lesser of the most recently received permission credit value and the burst tolerance combined with the sum of permission credit values received from the downstream network device.

19. The network device of claim 8, further comprising:

at least one input port;

at least one output port; and

wherein the first transmit permission received from the downstream network device is received at the at least one input port, and the second transmit permission is transmitted at the at least one output port.

13. A method for performing flow control in a credit based flow controlled computer network having at least a first virtual connection for communication first information from a first computer network device to a second computer network device and further for communicating said first information from said second computer network device to a third computer network device and having at least a second virtual connection for communicating second information from said third computer network device to said second computer network device and further for communicating said second information from said second computer network device to said first computer network device, said method comprising the steps of:

forwarding a first credit message from said third computer network device for receipt by said second computer network device via said second virtual connection, said first credit message including at least a first number of credits indicative of buffer availability within said third computer network device;

forwarding a second credit message from said second computer network device for receipt by said first computer network device via said second virtual connection, said second credit message including a second number of credits, wherein said second number of credits is based, at least in part, upon the first number of credits contained within said first credit message, and wherein, at least at some times, said second number of credits is greater than said first number of credits, and wherein, at least at some other times, said second number of credits is not greater than said first number of credits; and

in response to receipt of said second credit message at said first computer network device, transmitting from said first computer network device for receipt by said second computer network device at least some of said first information wherein the amount of said first information transmitted is based, at least in part, upon the second number of credits specified in said second credit message.

14. The method of claim 13 wherein said second number of credits is in proportion to the first number of credits contained within said first credit message.

15. The method of claim 13, wherein the computer network further includes a fourth computer network device, wherein said first virtual circuit is further for communicating said first information from said third computer network device to said fourth computer network device, wherein said second virtual circuit is further for communicating said second information from said fourth computer network device to said third computer network device, and wherein said first number of credits in said first credit message is not greater than a number of credits contained within a third credit message previously received by said third computer network device from said fourth computer network device.

16. The method of claim 13 including the further step of transmitting from said first computer network device for receipt by said second computer network device at least some of said first information wherein the amount of said first information transmitted is proportional to the first number of credits specified in said second credit message.

17. The method of claim 13 including the further step of transmitting from said second computer network device for receipt by said third computer network device at least some of said first information wherein the amount of said first information transmitted is not greater than the first number of credits specified in said first credit message.

20. A method for implementing permission based flow control in a computer network in which transmission permission credits are chained between network devices, wherein said method includes over-subscription at a logical link level, comprising:

first, second and third network devices, wherein said first network device is downstream relative to said second network device, and said third network device is upstream relative to said second network device, wherein said second network device receives data units from said third network device and transmits permission credits to said third network device, and wherein said second network device transmits data units to said first network device and receives permission credits from said first network device;

wherein said transmission permission credits transmitted from said second network device to said third network device are based at least in part upon transmission permission credits provided from said first network device to said second network device;

wherein said second network device may, at least at sometimes, be over-subscribed at said logical link level by transmitting to said third network device a number of transmission permission credits exceeding a size of a logical link buffer in said second network device; and

wherein, at least at some other times, said second network device may transmit to said third network device a number of transmission permission credits not exceeding a size of a logical link buffer in said second network device.