Method for adaptive control of windows and rates in networks

• US 5,426,635 A
• Filed: 09/08/1993
• Issued: 06/20/1995
• Est. Priority Date: 09/08/1993
• Status: Expired due to Term

• Current Assignee: AT&T IPM Corp. (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Mitra, Debasis, Seery, Judith B.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Jung, Min
• Application Number:
  US08/118,531
• Time in Patent Office: 650 Days
• Field of Search: 370/84, 370/94.1, 370/60, 370/85.2, 370/85.3
• US Class Current: 370/229
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/16 in connection oriented networks, e.g. frame relay
• 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
• CPC Class Codes: H04L 47/35 by embedding flow control information in regular packets, e.g. piggybacking
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Methods are disclosed for the adaptive control of windows and rates in networks. A periodic, one-bit feedback signal is combined with systematic damping and control of a gain signal to achieve a minimum bandwidth and a fair share of excess available bandwidth among virtual circuits in the network in a timely manner. The methods are demonstrated using a First-Come-First-Served service discipline, a Weighted Round-Robin service discipline, or a combination of the two disciplines.

Claims

1. In a network comprising a node and a virtual circuit passing through said node, said virtual circuit having a window of a size K having K packets of data in transit from a data source via said virtual circuit, a method of controlling said size K of said window comprising the steps of:

sending a feedback signal during a time slot from said node to a point in said network connected to said data source, said feedback signal reflecting an indication of congestion in said network;

determining at said point an ideal window of a size K based on said feedback signal and on a damping constant, said damping constant determining the relative weight accorded to a) the size of said ideal window in at least one prior time slot and b) said feedback signal, said size K of said ideal window reflecting an ideal number of packets in transit from said data source via said virtual circuit; and

generating a window size control signal for controlling said window of said size K based on said ideal window.

2. The method of claim 1 wherein said feedback signal comprises a single bit.

3. The method of claim 2 wherein said single bit is set when congestion is encountered at said node.

4. The method of claim 1 wherein said window size control signal comprises a signal to said data source to send one or more additional packets to said network.

5. The method of claim 1 wherein said step of generating a window size control signal comprises generating a signal to control said size K of said window upon an acknowledgment of receipt of the n^th packet in the K packets of data according to:

##EQU32## where n is an index identifying the packet K_n is said size of said window between acknowledgment of the n-1^th and n^th packets of data, and I is an index identifying the time slot during which said acknowledgement is received.

6. The method of claim 1 wherein said step of determining comprises determining:

space="preserve" listing-type="equation">K.sub.I =(1-d(I)γ

)K.sub.I-d(I) -ad(I)B.sub.I (I=1, 2, . . . )

where I is an index identifying the time slot during which said feedback signal was sent, K_I is the size of said ideal window during said time slot, γ

is said constant, a is a gain constant, d(I) is the number of time intervals since said feedback signal was sent, and B_I is said feedback signal.

7. The method of claim 6 wherein B_I =1 if said feedback signal indicates congestion in said network and wherein B_I =-1 if said feedback signal indicates no congestion in said network.

8. In a network comprising a plurality of virtual circuits adapted to communicate packets of data between a set of nodes in said network, the j^th of said virtual circuits having a window of a size K_j having K_j packets of data in transit from a data source via said j^th virtual circuit, a method of controlling said size K_j of said window comprising:

sending a feedback signal during a time slot from a node in said set of nodes to a point in said network connected to said source, said feedback signal reflecting an indication of congestion in said network;

determining at said point an ideal window of a size K_j for said j^th virtual circuit based on said feedback signal and on a damping constant, said damping constant determining the relative weight accorded to a) the size of said ideal window in at least one prior time slot and b) said feedback signal, said size K_j of said ideal window reflecting an ideal number of packets in transit from said data source via said j^th virtual circuit; and

generating a window size control signal for controlling said window of said size K_j based on said ideal window.

9. The method of claim 8 wherein said feedback signal comprises a single bit.

10. The method of claim 9 wherein said single bit is set when congestion is encountered in said network.

11. The method of claim 8 wherein said window size control signal comprises a signal to said data source to send one or more additional packets of data via said j^th virtual circuit.

12. The method of claim 8 wherein said step of generating a window size control signal comprises generating a signal to control said size of said window K_j upon acknowledgment of receipt of the n^th packet in the K_j packets of data according to:

##EQU33## where n is an index identifying the packet, K_j,n is the size of said window between acknowledgment of the n-1^th and n^th packets of data, and I is and index identifying the time slot during which said acknowledgment is received.

13. The method of claim 8 wherein said step of determining comprises determining:

space="preserve" listing-type="equation">K.sub.j,I =(1-d(I)γ

.sub.j)K.sub.j,I-d(I) -a.sub.j d(I)B.sub.I (I=1, 2, . . . )

where I is an index identifying the time slot during which said feedback signal was sent, K_j,I is the size of the ideal window of said j^th virtual circuit during said time slot, γ

_j is said constant for said j^th virtual circuit, a_j is a gain constant for said j^th virtual circuit, d(I) is the number of time intervals since said feedback signal was sent, and B_I is said feedback signal.

14. The method of claim 13, wherein B_I =1 if said feedback signal indicates congestion in said network in excess of a predetermined threshold, and wherein B_I =-1 if said feedback signal indicates congestion in said network is not in excess of said threshold.

15. The method of claim 8 wherein said step of determining comprises determining:

space="preserve" listing-type="equation">K.sub.j,I =max[K.sub.j,floor,{(1-d(I)γ

.sub.j)K.sub.j,I-d(I) -a.sub.j d(I)B(I.sub.j)}](I=1, 2, . . . )

where I is an index identifying the time slot during which said feedback signal was sent, K_j,I, is the size of the ideal window during said time slot, γ

_j is said constant for said j^th virtual circuit, a_j is a gain constant for said j^th virtual circuit, d(I) is the number of time intervals since said feedback signal was sent, B_I is said feedback signal, and K_j,floor =τ

_j (CIR) where τ

_j is the round trip delay time for said j^th virtual circuit and CIR_j is the committed information rate for said j^th virtual circuit.

16. The method of claim 8, wherein each of said nodes comprises a buffer memory for receiving packets of data from a preceding node, and wherein said feedback signal indicates the level of data relative to a predetermined threshold level.

17. The method of claim 8, wherein each of said nodes comprises a buffer memory for receiving packets of data from a preceding node for said j^th virtual circuit, and wherein said feedback signal indicates the level of data relative to a predetermined threshold level Q_T,j for the j^th virtual circuit.

18. The method of claim 17 wherein said buffer memory is serviced on a first-come-first-served basis.

19. The method of claim 17 wherein said buffer memory is serviced using a weighted round robin discipline.

20. In a network a method of controlling a rate of input of packets of data from a data source to said network comprising the steps of:

receiving a feedback signal during a time slot from said network at a point connected to said data source, said feedback signal reflecting an indication of congestion in said network;

determining at said point a rate R based on said feedback signal and on a damping constant, said damping constant determining the relative weight accorded to a) the size of said ideal window in at least one prior time slot and b) said feedback signal; and

responsive to said receiving, generating a rate control signal for setting to R said rate of input of packets of data from said data source to said network.

21. The method of claim 20 wherein said feedback signal comprises a single bit.

22. The method of claim 21 wherein said single bit is set when there is congestion in said network.

23. The method of claim 20 wherein said step of determining comprises determining:

space="preserve" listing-type="equation">R.sub.I =(1-d(I)γ

)R.sub.I-d(I) -ad(I)B.sub.I (I=1, 2, . . . )

where I is an index identifying the time slot during which said feedback signal was sent, R_I is said rate during said time slot, γ

is said constant, a is a gain constant, d(I) is the number of time intervals since said feedback signal was sent, and B_I is said feedback signal.

24. In a network comprising a plurality of virtual circuits adapted to communicate packets of data between a set of nodes in said network, a method of controlling the rate of input of packets of data from a data source to said network via the j^th virtual circuit comprising the steps of:

receiving a feedback signal from said network at a point connected to a data source, said feedback signal reflecting an indication of congestion in said j^th virtual circuit;

determining at said point a rate R_j based on said feedback signal and on a damping constant, said damping constant determining the relative weight accorded to a) the size of said ideal window in at least one prior time slot and b) said feedback signal; and

responsive to said receiving, generating a rate control signal for setting to R_j said rate of input of packets of data from said data source.

25. The method of claim 24, wherein each of said nodes comprises a buffer memory for receiving packets of data from a preceding node, and wherein said feedback signal indicates the level of data relative to a predetermined threshold level.

26. the method of claim 25 wherein said buffer memory is serviced on a first-come-first-served basis.

27. The method of claim 25 wherein said buffer memory is serviced using a weighted round robin discipline.

28. The method of claim 24 wherein said step of determining comprises determining:

space="preserve" listing-type="equation">R.sub.j,I =(1-d(I)γ

.sub.j)R.sub.j,I-d(I) -a.sub.j d(I)B.sub.I (I=1, 2, . . . )

where I is an index identifying the time slot during which said feedback signal was sent, R_j,I is said rate of said j^th virtual circuit during said time slot, γ

_j is said constant for said j^th virtual circuit, a_j is a gain constant for said j^th virtual circuit, d(I) is the number of time intervals since said feedback signal was sent, and B_I is said feedback signal.