End-system dynamic rate limiting of background traffic

• US 8,385,201 B2
• Filed: 03/26/2010
• Issued: 02/26/2013
• Est. Priority Date: 04/26/2006
• Status: Active Grant

• Current Assignee: Rainberry, Inc.
• Original Assignee: Bittorrent Incorporated
• Inventors: Cohen, Bram, Harrison, David, Hazel, Gregory
• Primary Examiner(s): GREY, CHRISTOPHER P
• Application Number:
  US12/732,264
• Publication Number:
  US 20100284276A1
• Time in Patent Office: 1,068 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/233, 370/234, 370/235, 370/248, 370/389, 370/392, 370/395.31, 709223-226
• US Class Current: 370/234
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1042 using topology management mechanisms
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Abstract

Dynamic rate limiting of background traffic to alleviate congestion in the access network is enabled. ICMP echo round-trip times and ICMP losses to a nearby node outside the local area and just beyond the divergence in end-to-end paths are measured, allowing unambiguous discrimination of nearby from distant congestion points. Using round-trip time samples, either short-run delay or short-run variance in delay can be measured to estimate congestion. When combined with an appropriate control law, background traffic can be rapidly reduced to allow interactive traffic to traverse unhindered through the access network. The described system and methods can be implemented in the application-layer and without any additional support from the network.

Claims

1. A computer system for rate-limiting traffic in a peer-to-peer network, the computer system comprising:

a processor; and

a computer program product, the computer program product stored on a non-transitory computer-readable storage medium and including program code for causing the processor to execute steps comprising;

estimating congestion in the network;

determining a congestion control law associated with the estimated congestion, the congestion control law including a first rate limit for peer-to-peer traffic and a second rate limit for other traffic; and

providing a bounding mechanism on the congestion control law by;

calculating an average upload rate;

determining a first number corresponding to the relative importance of other traffic;

determining a second number corresponding to the relative importance of peer-to-peer traffic;

calculating a minimum allowable rate limit as a fraction of the average upload rate, the fraction having as a numerator the second number and as a denominator the sum of the first number and the second number; and

responsive to the determined first rate limit being below the minimum allowable rate limit, setting the first rate limit equal to the minimum allowable rate limit.

2. The computer system of claim 1, the program code further causing the process to execute the steps of:

identifying a path in the network shared by a plurality of peers by;

tracing at least one route from a first peer to at least one other peer, each traced route comprising one or more nodes; and

determining a last common node, wherein the last common node is a node that is most distant from the first peer and that is common to all traced routes.

3. The computer system of claim 1 wherein the first rate limit is an upload rate limit.

4. The computer system of claim 3 wherein the first rate limit is determined using an Additive Increase with Multiplicative Decrease technique.

5. The computer system of claim 1 wherein the second rate limit is a maximum rate supported by the network.

6. The computer system of claim 1, wherein estimating congestion in the network further comprises:

identifying a last common node within a path in the network shared by a plurality of peers;

pinging the last common node a plurality of times to observe a plurality of round-trip times;

calculating a delay metric corresponding to a buffer associated with the last common node being full based on a subset of observed round-trip times; and

setting a single congestion threshold based on the delay metric.

7. The computer system of claim 1 wherein estimating congestion the network further comprises:

identifying a last common node within a path in the network shared by a plurality of peers;

pinging the last common node a plurality of times to observe a plurality of round-trip times;

calculating a smoothed ping time based on the observed round-trip times;

subtracting a minimum observed round-trip time from the smoothed ping time to calculate a queuing delay; and

comparing the queuing delay to the delay metric.

8. The computer system of claim 7 wherein calculating a smoothed ping time further comprises calculating an exponentially weighted moving average of the observed round-trip times.

9. The computer system of claim 7 wherein calculating a smoothed ping time further comprises calculating a mean of the observed round-trip times over a moving window.

10. The computer system of claim 7 wherein calculating a smoothed ping time further comprises calculating a median of the observed round-trip times over a moving window.

11. The computer system of claim 1 wherein estimating congestion in the network further comprises:

identifying a last common node within a path in the network shared by a plurality of peers;

pinging the last common node a plurality of times to observe a plurality of round-trip times;

calculating a variance of the observed round-trip times; and

estimating congestion based on the variance.

12. A computer system for rate-limiting traffic in a peer-to-peer network, the computer system comprising:

a processor; and

a computer program product, the computer program product stored on a non-transitory computer-readable storage medium and including program code for causing the processor to execute steps comprising;

estimating congestion in the network;

determining a congestion control law associated with the estimated congestion, the congestion control law including a first rate limit for peer-to-peer traffic and a second rate limit for other traffic; and

providing a bounding mechanism on the congestion control law by;

determining a capacity of the network;

determining a first number corresponding to the relative importance of other traffic;

determining a second number corresponding to the relative importance of peer-to-peer traffic;

calculating a minimum allowable rate limit as a fraction of the capacity, the fraction having as a numerator the second number and as a denominator the sum of the first number and the second number; and

responsive to the determined first rate limit being below the minimum allowable rate limit, setting the first rate limit equal to the minimum allowable rate limit.

13. The computer system of claim 12, the program code further causing the process to execute the steps of:

identifying a path in the network shared by a plurality of peers by;

tracing at least one route from a first peer to at least one other peer, each traced route comprising one or more nodes; and

determining a last common node, wherein the last common node is a node that is most distant from the first peer and that is common to all traced routes.

14. The computer system of claim 12, wherein estimating congestion in the network further comprises:

identifying a last common node within a path in the network shared by a plurality of peers;

pinging the last common node a plurality of times to observe a plurality of round-trip times;

calculating a delay metric corresponding to a buffer associated with the last common node being full based on a subset of observed round-trip times; and

setting a single congestion threshold based on the delay metric.

15. The compute system of claim 12 wherein estimating congestion in the network further comprises:

identifying a last common node within a path in the network shared by a plurality of peers;

pinging the last common node a plurality of times to observe a plurality of round-trip times;

calculating a smoothed ping time based on the observed round-trip times;

subtracting a minimum observed round-trip time from the smoothed ping time to calculate a queuing delay; and

comparing the queuing delay to the delay metric.

16. The computer system of claim 15 wherein calculating a smoothed ping time further comprises calculating an exponentially weighted moving average of the observed round-trip times.

17. The computer system of claim 15 wherein calculating a smoothed ping time further comprises calculating a mean of the observed round-trip times over a moving window.

18. The computer system of claim 15 wherein calculating a smoothed ping time further comprises calculating a median of the observed round-trip times over a moving window.

19. The computer system of claim 12 wherein estimating congestion in the network further comprises:

identifying a last common node within a path in the network shared by a plurality of peers;

pinging the last common node a plurality of times to observe a plurality of round-trip times;

calculating a variance of the observed round-trip trip times; and

estimating congestion based on the variance.

20. A method for rate-limiting traffic in a peer-to-peer network, the method comprising:

estimating by a processor congestion in the network;

determining by the processor a congestion control law associated with the estimated congestion, the congestion control law including a first rate limit for peer-to-peer traffic and a second rate limit for other traffic; and

providing by the processor a bounding mechanism on the congestion control law by;

calculating an average upload rate;

determining a first number corresponding to the relative importance of other traffic;

determining a second number corresponding to the relative importance of peer-to-peer traffic;

calculating a minimum allowable rate limit as a fraction of the average upload rate, the fraction having as a numerator the second number and as a denominator the sum of the first number and the second number; and

responsive to the determined first rate limit being below the minimum allowable rate limit, setting the first rate limit equal to the minimum allowable rate.

21. A method for rate-limiting traffic in a peer-to-peer network, the method comprising:

estimating by a processor congestion in the network;

determining by the processor a congestion control law associated with the estimated congestion, the congestion control law including a first rate limit for peer-to-peer traffic and a second rate limit for other traffic; and

providing by the processor a bounding mechanism on the congestion control law by;

calculating a capacity of the network;

determining a first number corresponding to the relative importance of other traffic;

determining a second number corresponding to the relative importance of peer-to-peer traffic;

calculating a minimum allowable rate limit as a fraction of the capacity of the network, the fraction having as a numerator the second number and as a denominator the sum of the first number and the second number; and

responsive to the determined first rate limit being below the minimum allowable rate limit, setting the first rate limit equal to the minimum allowable rate limit.