Data packet flow control scheme for switching networks

• US 4,475,192 A
• Filed: 02/16/1982
• Issued: 10/02/1984
• Est. Priority Date: 02/16/1982
• Status: Expired due to Term

• Current Assignee: Bell Telephone Laboratories, Inc. (Nokia Corporation)
• Original Assignee: AT&T, Inc.
• Inventors: Levy, Roger P., Fernow, James P.
• Primary Examiner(s): Olms, Douglas W.
• Application Number:
  US06/349,032
• Time in Patent Office: 959 Days
• Field of Search: 370/94, 370/60, 340/825.52
• US Class Current: 370/232
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/30 in combination with information about buffer occupancy at either end or at transit nodes

Abstract

Flow of data packets through virtual circuits in a multinode packet switching network is controlled by authorizing packets to enter and to leave each node. When a packet entering a node does not have an authorization (credit) to leave, it is placed in a pool of buffers common to all virtual circuits to await reception of an output credit for the virtual circuit. To avoid buffer congestion, a count is maintained of packets presently stored in and being processed through the node and packets that the node anticipates it will receive. If the count exceeds a predetermined threshold, a packet cannot get an authorization to enter the node unless it has a credit to leave. If the count is below the threshold, credits are granted for packets to enter the node even though there is no authorization to leave.

Claims

1. A method of controlling flow rate of data packets through a node on each of a plurality of paths extending from a plurality of sender units to a plurality of receiver units connected thereto through the node, the node being arranged to grant a number of node credits to each sender unit to permit such sender unit to send a corresponding number of data packets to the node, to forward a number of the data packets sent to the node toward the receiver unit connected thereto when holding a corresponding number of receiver credits granted by such receiver unit and to process the data packets from all sender units through shared resources of the node, comprising the steps of:

determining a quantity of node congestion in accordance with the quantity of packets from all sender units being processed through the shared resources,

granting node credits to each individual one of the sender units limited in number to a selected number when the node congestion quantity exceeds a predetermined threshold, and

granting a further number of node credits to the one sender unit in excess of the selected number when the node congestion quantity fails to exceed the threshold.

2. A method of controlling flow rate in accordance with claim 1 wherein the step of granting node receiver credits includes limiting the selected number to the number of node held credits granted by the receiver unit connected thereto.

3. A method of controlling flow rate in accordance with claim 1 wherein the step of determining node congestion quantity includes the step of increasing the determined quantity when granting a further number of node credits to the several sender units.

4. A method of controlling flow rate in accordance with claims 1 or 3 wherein the step of determining node congestion quantity includes the step of decreasing the determined quantity in response to receiver credits granted by the several receiver units.

5. A method of controlling flow rate in accordance with claim 2 wherein the step of granting node credits includes the step of determining a difference between the node held receiver credits granted by the receiver unit connected thereto and the quantity of packets from the one sender unit being processed through the node.

6. A method of controlling flow rate in accordance with claim 5 wherein the step of granting a further number of node credits includes the step of adding a predetermined integral number to the difference determination.

7. A method of controlling flow rates of data packets through a common node, the data packets flowing through a plurality of virtual circuits extending from sender units to receiver units connected thereto by way of the common node, activities of the node including granting node credits to each of the sender units, which node credits are satisfied by receiving packets from the sender units, sending packets to each of the receiver units to satisfy receiver credits granted by such receiver unit and processing packets received from sender units in anticipation of sending same to receiver units connected thereto, comprising the steps of:

granting a node credit to each individual one of the sender units when a number relating to a difference between the number of unsatisfied receiver credits granted by the receiver unit connected thereto and the number of packets from the one sender unit being processed in the node exceeds the number of unsatisfied node credits granted to the one sender unit, and

adding an incremental number to the difference number when the quantity of node activity is below a predetermined threshold whereby a node credit is granted without the node holding a corresponding receiver credit for the sender unit packet that will satisfy the granted receiver credit.

8. A method of controlling flow rates in accordance with claim 7 and including the step of maintaining a count of node credits granted to all sender units without the receiver credits from the receiver unit connected thereto to determine quantity of node activity.

9. A method of controlling flow rates in accordance with claim 8 and including the step of decrementing the count in response to receiver credits granted by the receiver units.