Rate based congestion control for packet networks

• US 20070165524A1
• Filed: 08/12/2004
• Published: 07/19/2007
• Est. Priority Date: 08/29/2003
• Status: Active Grant

• Current Assignee: Saverio Mascolo
• Original Assignee: Saverio Mascolo
• Inventors: Mascolo, Saverio
• Granted Patent: US 7,593,335 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/18 End to end
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures
• CPC Class Codes: H04N 21/6373 for rate control , e.g. request to the server to modify its transmission rate flow control in packet networks H04L47/10
• CPC Class Codes: H04N 21/6377 directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/6437 Real-time Transport Protocol [RTP]
• CPC Class Codes: H04N 21/64769 for rate control flow control in packet networks H04L47/10
• CPC Class Codes: H04N 21/658 Transmission by the client directed to the server
• CPC Class Codes: H04W 28/10 Flow control between communication endpoints
• CPC Class Codes: H04W 8/04 Registration at HLR or HSS [Home Subscriber Server]
• CPC Class Codes: Y02D 30/50 in wire-line communication networks, e.g. low power modes or reduced link rate

Abstract

The invention herein described consists of a method to compute in a end-to-end fashion the sending rate of data, audio and video flows over a packet switching network such as the Internet Protocol Network. The sending rate is computed as a function of the data sent in the recent past and as a function of a probing function w(t) that is dynamically set by taking into account signals of network congestion and the network changing available bandwidth.

Claims

1. A method to compute a sending rate r(t) of data, audio or video over a packet switching network in which a user of a client/server machine connects to a client/server machine, comprising:

computing the sending rate r(t);

computing samples B(t) of available bandwidth by taking into accounts the flow of packets received by the client, if the routine is implemented at the receiver side, or by taking into accounts acknowledgment packets received by the sender, if the routine is implemented at the sender side;

computing the available bandwidth {circumflex over (B)}(t) by filtering the samples B(t) of available bandwidth using a discrete time low-pass filter.

2. The method according to claim 1, wherein the sending rate r(t) is computed as:

$r<br><br>\left(t\right)=k·<br><br>{\left[\min <br><br>\left(w<br><br>\left(t\right),s<br><br>\left(t\right)\right)-{\int <br><br>}_{t-\mathrm{RTT}}^t<br><br>r<br><br>\left(\mathrm{\tau <br><br>}\right)<br><br>d<br><br>\mathrm{\tau <br><br>}\right]}^{+}$

where;

a) [x]⁺=max(0,x);

b) k is a proportional constant;

c) RT is the round trip time;

d) w(t) is an input function that consists of an Increasing Phase to probe network capacity and a Decreasing Phase that is entered at the end of the Increasing Phase after that network capacity has been hit. After the Decreasing Phase the Increasing Phase is entered again;

e) s(t) is a function that is equal to infinity if no explicit congestion feedback is provided by the network to the sender or is equal to a proper value if a congestion feedback is provided by the network.

3. The method according to claim 2, wherein the Increasing Phase of the function w(t) is made of two phases:

a) A quick probing phase, during which the function w(t) is set as follows;

$w<br><br>\left(t\right)=w<br><br>\left(t_0\right)·<br><br>c^{\frac{t-t_0}{\mathrm{\alpha <br><br>}}}$

where t₀ is the last time the quick probing phase was entered. When w(t) is equal to a threshold value ssthresh, the gentle probing phase is entered.

b) A gentle probing phase, during which the function w(t) is set as follows;

$w<br><br>\left(t\right)=w<br><br>\left(t_0\right)+\frac{t-t_0}{\mathrm{\beta <br><br>}}$

where t₀ is the time the gentle probing phase was entered.

4. A method according to claim 2, wherein the Decreasing Phase of the function w(t) is set as follows:

a) When the congestion episode is notified at time t₁ by means of a feedback report or n duplicate ACKs (typically n=3) sent by the receiver to the sender because of a hole in the sequence of received packets, or when the congestion episode is notified by Explicit Congestion Notification (ECN), the function w(t) decreases from the value w(t₁) at time t₁ to the value w(t_f)={circumflex over (B)}(t₁)

$\left({\mathrm{RTT}}_m+\frac{1}{k}\right)$

at time t_f=t₁+RTT_m, where {circumflex over (B)}(t₁) is the available bandwidth at time t₁ and RTT_m is the minimum round trip time. When t=t₁+RTT_m, the setting of w(t) again enters the gentle probing phase.

b) When congestion event at time t₁ is notified by timeout (the sender does not receive any report from the receiver for a long time so that a timeout expires) the function w(t) is set as follows;

w(t)=w(t₁)=2 or few segments

and the quick probing phase

$w<br><br>\left(t\right)=w<br><br>\left(t_1\right)·<br><br>c^{\frac{t-t_1}{\mathrm{\alpha <br><br>}}}$

is entered again with the threshold ssthresh set at the value

$\mathrm{ssthresh}=\hat{B}<br><br>\left(t_1\right)·<br><br>\left({\mathrm{RTT}}_m+\frac{1}{k}\right)$

where {circumflex over (B)}(t₁) is the available bandwidth at time t₁ and RTT_m is the minimum round trip time. When w(t) reaches the ssthresh, then the function w(t) enters the gentle probing phase.

5. A method according to claim 2, wherein the Decreasing Phase of the function w(t) is set as follows

a) When the congestion episode is notified at time t₁ by means of a feedback report or n duplicate ACKs (typically n=3) sent by the receiver to the sender because of a hole in the sequence of received packets, or when the congestion episode is notified by Explicit Congestion Notification (ECN), the function w(t) is set as follows:

$w<br><br>\left(t\right)=w<br><br>\left(t_1\right)-\frac{w<br><br>\left(t_1\right)-w<br><br>\left(t_f\right)}{{\mathrm{RTT}}_m}<br><br>\left(t-t_1\right)$$\mathrm{where}$$w<br><br>\left(t_f\right)=\hat{B}<br><br>\left(t_1\right)·<br><br>\left({\mathrm{RTT}}_m+\frac{1}{k}\right)$

{circumflex over (B)}(t₁) is the available bandwidth at time t₁, RTT_m is the minimum round trip time and t_f=t₁+RTT_m. When t=t₁+Rtt_m, the function w(t) again enters the gentle probing phase.

b) When congestion event at time t₁ is notified by timeout (the sender does not receive any report from the receiver for a long time so that a timeout expires) the function w(t) is set as follows;

w(t)=w(t₁)=2 or few segments

and the quick probing phase

$w<br><br>\left(t\right)=w<br><br>\left(t_1\right)·<br><br>c^{\frac{t-t_1}{\mathrm{\alpha <br><br>}}}$

is entered again with the threshold ssthresh set at the value

$\mathrm{ssthresh}=\hat{B}<br><br>\left(t_1\right)·<br><br>\left({\mathrm{RTT}}_m+\frac{1}{k}\right)$

where {circumflex over (B)}(t₁) is the available bandwidth at time t₁ and RTT_m is the minimum round trip time. When w(t) reaches the ssthresh, then the function w(t) enters the gentle probing phase.

6. A method according to claim 1, wherein a sample B(i) at time t=t_i of available bandwidth is computed every Round Trip Time (RTT) or every Smoothed Round Trip Time (SRTT), as follows:

$B<br><br>\left(i\right)=\frac{D<br><br>\left(i\right)}{T<br><br>\left(i\right)}$

where D(i) is the amount of data received during the last RTT=T(i) or SRT=T(i).

7. A method according to claim 1, wherein computing the available bandwidth {circumflex over (B)}(t) includes:

8. A method according to claim 1, wherein computing the available bandwidth {circumflex over (B)}(t) includes low-pass filtering samples B(t) of available bandwidth using the following filter with time-varying coefficients:

$\hat{B}<br><br>\left(i\right)=\frac{2<br><br>{\mathrm{\tau <br><br>}}_f-T<br><br>\left(i\right)}{2<br><br>{\mathrm{\tau <br><br>}}_f+T<br><br>\left(i\right)}<br><br>\hat{B}<br><br>\left(i-1\right)+T<br><br>\left(i\right)<br><br>\frac{B<br><br>\left(i\right)+B<br><br>\left(i\right)}{2<br><br>{\mathrm{\tau <br><br>}}_f+T<br><br>\left(i\right)}$

where {circumflex over (B)}(i) is the filter output at time t_i, {circumflex over (B)}(i−

1) is the filter output at time t<sub>i−

1</sub>, B(i) is a sample B(t) of available bandwidth computed at t=t_i, τ

_f is the time-constant of the filter. When T(i)>

τ

_f/4 we interpolate and re-sample using N=integer of (4.T(i)/τ

_f) virtual samples B(i) arriving with interarrival time T_v(i)=τ

_f/4.

9. A method according to claim 1, wherein computing the available bandwidth {circumflex over (B)}(t) includes:

low-pass filtering samples B(t) of available bandwidth using a filter with constant coefficients.

10. A method according to claim 1, wherein computing the available bandwidth {circumflex over (B)}(t) includes:

low-pass filtering samples B(t) of available bandwidth using the following filter with constant coefficients;

{circumflex over (B)}(i)=α

·

{circumflex over (B)}(i−

1)+(1−

α

)·

B(i)

where {circumflex over (B)}(i) is the filter output at time t_i, {circumflex over (B)}(i−

1) is the filter output at time t<sub>i−

1</sub>, B(i) is a sample B(t) of available bandwidth computed at t_i and α

is a constant.

11. A method according to claim 1, wherein computing the available bandwidth {circumflex over (B)}(t) includes:

a chain of filters in cascade, where each filter of the chain is according to anyone of claims 7 to 10 and where samples B(t) of available bandwidth are inputs to the first filter in the chain.

12. A method according to any of preceding claims, wherein it is implemented in TCP congestion control.

13. A methods according to anyone of claims 1 to 11, wherein it is implemented within applications for sending data over packet networks.

14. A methods according to anyone of claims 1 to 11, wherein it is implemented within applications for audio/video streaming.

15. A methods according to anyone of claims 1 to 11, wherein it is implemented within applications for real-time conferencing over packet networks.

16. A method according to anyone of claims 1 to 11, wherein it is implemented within peer-to-peer applications for file sharing over packet networks.

17. A method for adaptively selecting the quality of coding, or the numbers of layers to be transmitted in a layered coding of an audio/video source, by using the estimate {circumflex over (B)}(t) of available bandwidth computed according to claims 1 or anyone of claims 6 to 11.