System and method for controlling network demand via congestion pricing

• US 7,284,047 B2
• Filed: 11/08/2001
• Issued: 10/16/2007
• Est. Priority Date: 11/08/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Black, Richard, Barham, Paul, Key, Peter, Stratford, Neil
• Primary Examiner(s): Cardone; Jason
• Assistant Examiner(s): Swearingen; Jeffrey R
• Application Number:
  US10/010,881
• Publication Number:
  US 20030097461A1
• Time in Patent Office: 2,168 Days
• Field of Search: 709/223, 709/224, 709232-235, 705/30, 370/229, 370232-235
• US Class Current: 709/224
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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: H04L 9/40 Network security protocols

Abstract

A method and system for avoiding network congestion by measuring network load to adjust a rate at each source. The load (e.g., as a price value) is provided to network traffic sources, which adjust their flows based on a per-flow weight (willingness to pay). The load may be determined in-band by routers or out-of-band by an observer node. A load value (e.g., as a price) is increased or decreased based on the actual load or an estimate based on the actual load. The sources obtain the load value and control the output rates per flow based on each flow'"'"'s associated weight (willingness to pay), e.g., as set by an administrator. Further, two classes of applications are enabled by allowing certain applications to ignore price.

Claims

1. In a computer network having a node and an observer, the node acting as a source of data transmissions and consuming network data transmission services, and the observer monitoring network load, a method of the node adjusting its service request, based on network load, to avoid data packets being dropped by the network so as to require retransmission of dropped data packets, the method comprising:

at the node that requests data transmission services, obtaining price information for the data transmission services, the price being variable based on current network traffic relative to network capacity; and

at the node that requests the data transmission services, and while transmitting the data, controlling a rate of transmitting data by the node over the network, the node generating the data as original data free of containing any retransmitted content, the controlling being based on the price information and on a weight value set by an administrator of the node, wherein the weight value corresponds to an assigned predetermined number associated with an operator of the node.

2. The method of claim 1 wherein obtaining price information includes receiving the price information from another computer system on the network.

3. The method of claim 2 wherein the other computer system on the network determines the price information by measuring the current network traffic as an amount of the network capacity which can be served with a congestion below a congestion threshold.

4. The method of claim 3 wherein the amount comprises a threshold value, and wherein the other computer system determines the price information by measuring the current network traffic, and increasing a previous price if the current network traffic relative to network capacity is greater than a threshold value, or decreasing the previous price if the current network traffic relative to network capacity is less than the threshold value.

5. The method of claim 4 wherein the other computer system on the network increases the previous price by multiplying the previous price by a first factor, and decreases the previous price by multiplying the previous price by a second factor.

6. The method of claim 2 wherein the other computer system broadcasts the price information.

7. The method of claim 2 wherein the other computer system periodically updates the price information.

8. The method of claim 1 wherein controlling a rate of transmitting data includes determining the rate based on the weight value divided by the price information.

9. The method of claim 1 wherein controlling a rate of transmitting data includes, obtaining the weight value for a selected application, and controlling the transmit rate for the selected application based on that weight value and the price information.

10. The method of claim 1 wherein controlling a rate of transmitting data includes, obtaining the weight value for each of a plurality of selected applications, and for each application, controlling the transmit rate based on the application'"'"'s respective weight value and the price information.

11. The method of claim 10 wherein at least one other application does not have its transmit rate controlled according to the price information.

12. The method of claim 10 wherein at least one application has its transmit rate comprised of a fixed amount not controlled according to the price information, and a rate based on the price and the application'"'"'s respective weight value.

13. The method of claim 12 wherein the price information being determined is based on an amount of the network capacity being used by at least one application whose rate at least in part is not controlled according to price information.

14. The method of claim 13 wherein a rate adjustment is smoothed based on the amount of the network capacity being used by at least one application whose rate at least in part is not controlled according to price information.

15. In a computer network, a system for controlling a rate of data transmission by a node to a destination such that data packets are not dropped and required to be retransmitted, system comprising,

an observer mechanism that determines network demand;

a pricing mechanism configured to determine a price which is variable based on the network demand and network capacity data, the pricing mechanism further being configured to provide price information corresponding to the price to at least a node on the network, the node requesting data transmission services and acting as a source of originally generated data packets free of retransmitted content; and

a rate control mechanism at the node, the rate control mechanism being configured to receive the price information and to control a transmit rate of the data packets based on the received price information and based on a weight value set by an administrator of the node.

16. The system of claim 15 wherein the observer mechanism is incorporated into a computing device on the network.

17. The system of claim 16 wherein the computing device comprises a router.

18. The system of claim 16 wherein the computing device comprises a gateway.

19. The system of claim 16 wherein the pricing mechanism is incorporated into the same computing device as the observer.

20. The system of claim 15 wherein the pricing mechanism provides price information by broadcasting the price information on the network.

21. The system of claim 20 wherein the pricing mechanism provides the price information at periodic intervals.

22. The system of claim 15 wherein the pricing mechanism determines price information by dividing a value representative of the network demand by the network capacity data.

23. The system of claim 22 wherein the network capacity data comprises a fixed value.

24. The system of claim 22 wherein the network capacity is not constant.

25. The system of claim 22 wherein the value representative of the network demand comprises a number of bytes of network traffic per unit time.

26. The system of claim 25 wherein the number of bytes includes packet overhead.

27. The system of claim 15 further comprising an application program executing at the node, and wherein the rate control mechanism controls a transmit rate for the application based on a weight value associated with the application program and the received price information, wherein the weight value associated with the application program corresponds to an assigned predetermined number associated with an operator of the node.

28. The system of claim 27 further comprising at least one other application that does not have its transmit rate controlled by the rate control mechanism.

29. The system of claim 27 wherein at least one application has its transmit rate comprised of a fixed amount not controlled according to the price information, and a rate based on the price and the application'"'"'s respective weight value.

30. The system of claim 29 wherein the price information being determined is based on an amount of the network capacity being used by at least one application whose rate at least in part is not controlled according to price information.

31. The system of claim 30 wherein a rate adjustment is smoothed based on the amount of the network capacity being used by at least one application whose rate at least in part is not controlled according to price information.

32. The system of claim 27 wherein the pricing mechanism determines the price information by comparing the network demand to a threshold value, and if the network demand achieves the threshold value, increasing a previous price, and if not, decreasing the previous price.

33. The system of claim 15 wherein the rate control mechanism comprises protocol code implemented at the Internet Protocol (IP) layer.

34. The system of claim 15 wherein the rate control mechanism controls the at least one transmit rate by controlling a rate of acknowledging packet receipt.

35. A computer-implemented method for avoiding data packets being dropped over a network connection in which a node requests data transmission services in transmitting data packets to a destination computer, the computer-implemented method comprising:

receiving a plurality of packets transmitted on a network during a period of time;

determining a network demand value based on an accumulated size of the packets received during the period of time and a network capacity value;

determining a price value based on the network demand value relative to a threshold, wherein the price value is variable based on the network demand;

providing the price value to a node computer operable to generate original packets free of retransmitted content on the network; and

at the node computer that requests data transmission services, and while the node computer transmits data packets, controlling a rate of transmitting data packets on the network based on the price value and based on a weight value set by an administrator of the node computer.

36. The method of claim 35 wherein receiving a plurality of packets includes operating a computing device in a mode that is intended to receive all packets transmitted on the network.

37. The method of claim 35 wherein determining a network demand value comprises calculating a current percentage of the network capacity in use.

38. The method of claim 35 wherein determining a price value comprises increasing a previous price if the threshold is achieved, else decreasing the price.

39. The method of claim 35 wherein providing the price value comprises broadcasting price information on the network.

40. The method of claim 35 wherein controlling the rate of transmitting data packets comprises, selecting an application program, obtaining a weight value associated with the application program, and controlling the rate based on the weight value and the price value, wherein the weight value corresponds to an assigned predetermined number associated with an operator of the node computer.

41. The method of claim 35 further comprising acknowledging the receipt of the received packets and wherein controlling a rate of transmitting data packets on the network comprises controlling a rate of acknowledging the receipt of data packets by a destination computer.

42. A computer-implemented method for adjusting a service request of a node computer, based on current network load, to avoid data packets being dropped over a network, the computer-implemented method comprising:

receiving load information corresponding to network load at a destination of network packets, wherein the network load information is variable as determined by network traffic; and

at a node computer that requests data transmission services by generating network packets free of retransmitted content, and while the node computer transmits the network packets, controlling a rate of a flow of packets from the source to the destination based on the load information and a weight value associated with the flow, wherein the weight value is set by an administrator of the node computer.

43. The method of claim 42 wherein controlling a rate of a flow of packets to the destination comprises controlling a rate of acknowledging packets received from the source.