Adaptive bandwidth throttling for network services

• US 6,961,341 B1
• Filed: 03/07/2001
• Issued: 11/01/2005
• Est. Priority Date: 07/02/1996
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Krishnan, Murali R.
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): PIZARRO, RICARDO M
• Application Number:
  US09/802,309
• Time in Patent Office: 1,700 Days
• Field of Search: 370/230, 370/231, 370/232, 370/233, 370/234, 370/229, 370/463, 370/468, 370/228, 370/412, 709/223, 709/224, 709/231, 709/232
• US Class Current: 370/412
• CPC Class Codes: H04J 3/1682 Allocation of channels according to the instantaneous demands of the users, e.g. concentrated multiplexers, statistical multiplexers
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/15 in relation to multipoint traffic arrangements for broadcast or multicast in data networks H04L12/18
• CPC Class Codes: H04L 47/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: H04L 47/2425 for supporting services specification, e.g. SLA
• CPC Class Codes: H04L 47/26 using explicit feedback to the source, e.g. choke packets
• CPC Class Codes: H04L 47/29 using a combination of thresholds
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/745 Reaction in network
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/825 Involving tunnels, e.g. MPLS
• CPC Class Codes: H04L 67/01 Protocols
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• 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

Abstract

The adaptive bandwidth throttling system implements a graceful diminution of services to the clients by delaying a first class of services provided by a network server in response to the effective bandwidth utilized by this network server exceeding a first threshold. If the demand for the bandwidth by this network server exceeds a second threshold, the bandwidth throttling system escalates the throttling response and blocks the first class of services from execution and can also concurrently delay execution of a second class of services. The implementation of the throttling process can be varied, to include additional levels of response or finer gradations of the response, to include subsets of a class of services. In addition, the threshold levels of bandwidth used to trigger the throttling response can be selected as desired by the system administrator. Typically, once the effective bandwidth utilization is approximately equal to the allocated bandwidth for the network server, the first level of the hierarchical bandwidth throttling is activated. The second level of the hierarchical bandwidth throttling is activated once the effective bandwidth utilization exceeds the allocated bandwidth for the network server by greater than a predetermined amount.

Claims

1. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

store data indicative of a data transmission rate for each of previous server operations;

generate, by averaging the stored data transmission rates, a bandwidth value indicating an average bandwidth used by a server to perform the previous server operations;

receive a request for the server to perform an additional server operation;

compare the bandwidth value to a first threshold and a second threshold; and

restrict the request in a first manner if the bandwidth value exceeds the first threshold but does not exceed the second threshold, and restrict the request in a second manner if the bandwidth value exceeds the second threshold;

wherein to restrict the request in the first manner is to delay the request;

wherein to restrict the request in the second manner is to block the request.

6. One or more computer-readable media as recited in claim 1, wherein the previous server operations and the additional server operation include one or more of read operations, write operations, and transmit operations.

9. One or more computer-readable media as recited in claim 1, wherein the restricting the request in the first manner comprises delaying the request.

10. One or more computer-readable media as recited in claim 1, wherein the restricting the request in the first manner comprises blocking the request.

11. One or more computer-readable media as recited in claim 1, wherein the restricting the request in the first manner comprises preventing the request from being presented to the server.

12. One or more computer-readable media as recited in claim 1, wherein the restricting the request in the first manner comprises preventing the request from entering a request queue of the server.

2. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

generate a bandwidth value indicating an average bandwidth used by a server to perform previous server operations;

receive a request for the server to perform an additional server operation;

compare the bandwidth value to a first threshold and a second threshold; and

restrict the request in a first manner if both the bandwidth value exceeds the first threshold and the additional server operation is of a first type, and restrict the request in a second manner if the bandwidth value exceeds the second threshold;

wherein to restrict the request in the first manner is to delay the request;

wherein to restrict the request in the second manner is to block the request.

3. One or more computer-readable media as recited in claim 2, wherein the first type comprises a read operation.

4. One or more computer-readable media as recited in claim 2, wherein the first type comprises a write operation.

5. One or more computer-readable media as recited in claim 2, wherein the first type comprises a transmit operation.

7. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

generate a bandwidth value indicating an average bandwidth used by a server to perform previous server operations;

receive a request for the server to perform an additional server operation;

compare the bandwidth value to a threshold;

restrict the request in a first manner if the bandwidth value exceeds the threshold, wherein to restrict the request in the first manner is to delay the request;

compare the bandwidth value to another threshold, wherein the threshold is less than the another threshold; and

restrict the request in a second manner if the bandwidth value exceeds the another threshold, wherein to restrict the request in the second manner is to block the request.

8. One or more computer-readable media as recited in claim 7, wherein:

the threshold is less than the another threshold;

restricting the request in the first manner comprises delaying the request; and

restricting the request in the second manner comprises blocking the request.

13. One or more computer-readable media having stored thereon a plurality of instructions that when executed by one or more processors of a computer, cause the one or more processors to:

generate a bandwidth value indicating an average bandwidth used by a server to perform previous server operations by;

generating a value for each of the previous server operations by, identifying a time interval duration between a start time of the previous server operation and an end time of the previous server operation,

identifying a number of bytes transferred for the previous server operation, and

dividing the number of bytes by the time interval duration; and

dividing a sum of the values of the previous server operations by the number of previous server operations;

receive a request for the server to perform an additional server operation;

compare the bandwidth value to a threshold; and

restrict the request in a first manner if the bandwidth value exceeds the threshold.

14. A method comprising:

receiving a request to perform a server operation;

storing data indicative of a data transmission rate for each of previous server operations;

generating an average bandwidth by averaging the stored data transmission rates; and

restricting performance of the request based at least in part on the average bandwidth, wherein the restricting comprises;

comparing the average bandwidth to at least one of a first threshold and a second threshold;

restricting the request in a first manner if the average bandwidth exceeds the first threshold but does not exceed the second threshold; and

restricting the request in a second manner if the average bandwidth exceeds the second threshold;

wherein restricting the request in the first manner comprises delaying the request;

wherein restricting the request in the second manner comprises blocking the request.

15. A method as recited in claim 14, further comprising:

storing data indicative of a data transmission rate for each of the previous server operations; and

generating the average bandwidth by averaging the stored data transmission rates.

16. A method as recited in claim 14, wherein the restricting further comprises restricting the request in the first manner if both the average bandwidth exceeds the first threshold and the server operation is of a first type.

17. A method as recited in claim 16, wherein the first type comprises a read operation.

18. A method as recited in claim 16, wherein the first type comprises a write operation.

19. A method as recited in claim 16, wherein the first type comprises a transmit operation.

20. A method as recited in claim 14, wherein restricting the request in the first manner comprises delaying the request and wherein restricting the request in the second manner comprises blocking the request.

21. A host system comprising:

at least one network server;

an asynchronous thread queue to receive a request, form a client process, to be performed by one of the at least one network server; and

a bandwidth throttling system, coupled to the asynchronous thread queue, to determine whether performance of the request by the one of the at least one network server is to be restricted in a first manner or a second manner based at least in part on both an average bandwidth used by the one of the at least one network server in performing previous server operations and on a type of the request, wherein the bandwidth throttling system is further to;

store data indicative of a data transmission rate for each of the previous server operations; and

generate the average bandwidth by averaging the stored data transmission rates; and

wherein to restrict the request in the first manner is to delay the request wherein to restrict the request in the second manner is to block the request.

22. A host system as recited in claim 21, further comprising an ancillary function driver, coupled to the asynchronous thread queue, to couple the host system to a network.

23. A host system comprising:

at least one network server;

an asynchronous thread queue to receive a request from a client process, to be performed by one of the at least one network server; and

a bandwidth throttling system, coupled to the asynchronous thread queue, to determine whether performance of the request by the one of the at least one network server is to be restricted based at least in part on an average bandwidth used by the one of the at least one network server in performing previous operations;

wherein the at least one network server comprises a plurality of network servers, and wherein the bandwidth throttling system determines whether performance of a request by a particular one of the plurality of network servers is to be restricted based on the average bandwidth used by that particular network server in performing previous operations and independent of the average bandwidth used by other network servers of the plurality of network servers in performing previous operations.

24. A host system comprising:

at least one network server;

an asynchronous thread queue to receive a request from a client process to be performed by one of the at least one network server; and

a bandwidth throttling system, coupled to the asynchronous thread queue, to determine whether performance of the request by the one of the at least one network server is to be restricted based at least in part on an average bandwidth used by the one of the at least one network server in performing previous operations;

wherein the bandwidth throttling system comprises;

a measurement subsystem to compute the average bandwidth used by the one of the at least one network server in performing previous operations; and

a control subsystem, coupled to the measurement subsystem, to make the determination and communicate how the asynchronous thread queue is to restrict performance of the request.

25. A method comprising:

storing data indicative of a data transmission rate for each of previous server operations;

generating, by averaging the stored data transmission rates, a value indicating a bandwidth used by a server to perform the previous server operations;

receiving a request for the server to perform an additional server operation; and

restricting the request in a first manner if the additional server operatoin is of a first type and the value exceeds a first threshold but does not exceed a second threshold, and restricting the request in a second manner if the value exceeds the second threshold;

wherein to restrict the request in the first manner is to delay the request;

wherein to restrict the request in the second manner is to block the request.

28. A method as recited in claim 25, wherein the first manner comprises delaying the request.

29. A method as recited in claim 25, wherein the second manner comprises blocking the request.

30. A method as recited in claim 25, wherein the restricting the request in the first manner comprises preventing the request from being presented to the server.

31. A method as recited in claim 25, wherein the restricting the request in the first manner comprises preventing the request from entering a request queue of the server.

32. A method as recited in claim 25, wherein the value indicates an average bandwidth used by the server.

33. A method as recited in claim 25, wherein the restricting comprises restricting the request in the first manner or the second manner only if the request is of a first type.

34. A method as recited in claim 33, wherein the first type comprises a read operation.

35. A method as recited in claim 33, wherein the first type comprises a write operation.

36. A method as recited in claim 33, wherein the first type comprises a transmit operation.

37. One or more computer-readable memories comprising computer-readable instructions that, when executed by a processor, direct a computer system to perform the method as recited in claim 25.

26. A method comprising:

generating a value indicating a bandwidth used by a server to perform previous server operations;

receiving a request for the server to perform an additional server operation;

restricting the request in a first manner if the value exceeds a first threshold but does not exceed a second threshold, and restricting the request in a second manner if the value exceeds the second threshold;

generating another value indicating bandwidth used by another server to perform other previous server operations;

receiving another request for the another server to perform another additional server operation; and

restricting the other request in the first manner if the value exceeds a third threshold but does not exceed a fourth threshold, and restricting the other request in the second manner if the value exceeds the fourth threshold.

27. A method as recited in claim 26, wherein the first threshold is different than the third threshold, and wherein the second threshold is different than the fourth threshold.

38. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

store data indicative of a data transmission rate for each of previous server operations;

generate, by averaging the stored data transmission rates, a value indicating a bandwidth used by a server to perform previous server operations;

receive a request for the server to perform an additional server operation;

compare the value to at least one of a first threshold and a second threshold;

restrict performance of a request based at least in part on an average bandwidth used in performing said previous server operations; and

delay the request if the value exceeds the first threshold but does not exceed the second threshold, and block the request if the value exceeds the second threshold.

39. One or more computer-readable media as recited in claim 38, wherein the value indicates an average bandwidth used by the server.

40. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

generate a value indicating a bandwidth used by a server to perform previous server operations by averaging stored data transmission rates indicative of data transmission rates of said previous server operations;

receive a request for the server to perform an additional server operation;

compare the value to at least one of a first threshold and a second threshold;

restrict performance of a requested based at least in part on an average bandwidth used in performing said previous server operations; and

delay the request only if the request is of a first type and if the value exceeds the first threshold but does not exceed the second threshold, and block the request only if the request is of the first type and if the value exceeds the second threshold.

41. One or more computer-readable media as recited in claim 40, wherein the first type comprises a read operation.

42. One or more computer-readable media as recited in claim 40, wherein the first type comprises a write operation.

43. One or more computer-readable media as recited in claim 40, wherein the first type comprises a transmit operation.

44. A host system comprising:

at least one network server;

an asynchronous thread queue to receive a request from a client process, to be performed by one of the at least one network server; and

a bandwidth throttling system, coupled to the asynchronous thread queue, to compare a value indicating a bandwidth used by the one of the at least one network server to perform previous server operations to at least one of a first threshold and a second threshold, to restrict the request in a first manner if the value exceeds the first threshold but does not exceed the second threshold, and to restrict the request in a second manner if the value exceeds the second threshold;

wherein the bandwidth throttling system is further to;

store data indicative of a data transmission rate for each of the previous server operations; and

generate the value by averaging the stored data transmission rates.

45. A host system comprising:

at least one network server;

an asynchronous thread queue to receive a request, from a client process, to be performed by one of the at least one network server; and

a bandwidth throttling system, coupled to the asynchronous thread queue, to compare a value indicating a bandwidth used by the one of the at least one network server to perform previous server operations to at least one of a first threshold and a second threshold to restrict the request in a first manner if the value exceeds the first threshold but does not exceed the second threshold, and to restrict the request in a second manner if the value exceeds the second threshold;

further comprising a plurality of network server, and wherein the bandwidth throttling system determines whether to restrict a request for a particular one of the plurality of network servers based on the value indicating bandwidth used by that particular network server in performing the previous server operations and independent of bandwidth used by other network servers of the plurality of network servers in performing the previous server operations.

46. A host system comprising:

at least one network server;

an asynchronous thread queue to receive a request from a client process, to be performed by one of the at least one network server; and

a bandwidth throttling system, coupled to the asynchronous thread queue, to compare a value indicating a bandwidth used by the one of the at least one network server to perform previous server operations to at least one of a first threshold and a second threshold, to restrict the request in a first manner if the value exceeds the first threshold but does not exceed the second threshold, and to restrict the request in a second manner if the value exceeds the second threshold;

wherein the bandwidth throttling system comprises;

a measurement subsystem to compute, as the value, an average bandwidth used by the network server in performing the previous server operations; and

a control subsystem, coupled to the measurement subsystem, to make the determination and communicate how the asynchronous thread queue is to restrict performance of the request.

47. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

determine a presently used bandwidth for each of at least one network server by way of a data transmission rate measurement during execution of an operation for each of said at least one network server that includes;

storing data indicative of said data transmission rate measurement of said operation for n last most recently executed operations for each of said at least one network server, wherein n is a positive integer greater than 2, and

generating data indicative of an effective presently used bandwidth for each of said at least one network server wherein said effective presently used bandwidth includes an average of said data transmission rate measurement over said n last most recently executed operations;

effect provision of a plurality of classes of service provided by one of said at least one network server in a first manner, in response to said effective presently used bandwidth for said one of said at least one network server that exceeds a first threshold; and

effect provision of said plurality of classes of service provided by said one of said at least one network server in a second manner that differs from said first manner, in response to said effective presently used bandwidth for said one of said at least one network server that exceeds a second threshold that is greater than said first threshold.

48. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

store data indicative of a predetermined allocated data transmission bandwidth for each of a plurality of network servers, each of said plurality of network servers providing a plurality of classes of service;

determine an effective bandwidth for each of said plurality of network servers, comprising;

calculating a bandwidth for each operation performed by each of said plurality of network servers,

tabulating a count of bandwidth used by each of said plurality of network servers in each of a plurality of last time intervals, and

averaging said tabulated count of bandwidth to obtain a value indicative of said effective bandwidth;

delay, in response to said effective bandwidth for a one of said network servers substantially corresponding to said predetermined allocated data transmission bandwidth for said one network server, for delaying a first subset of said plurality of classes of service provided by said one network server; and

reject, in response to said effective bandwidth for said one network server exceeding said predetermined allocated data transmission bandwidth for said one network server, request for said first subset of classes of service provided by said one network server and for delaying service for a second subset of said plurality of classes of service provided by said one network server.

49. One or more computer-readable media having stored thereon a plurality of instructions that, when executed by one or more processors of a computer, cause the one or more processors to:

determine a presently used bandwidth for each of a plurality of network servers by way of a data transmission rate measurement taken during execution of an operation for each of said plurality of network servers, said determining including;

storing data indicative of a predetermined allocated data transmission bandwidth for each of said plurality of network servers, and

storing data indicative of a first threshold, wherein said first threshold includes an indication of a different from said predetermined allocated data transmission bandwidth for each of said plurality of network servers; and

effect provision of a plurality of classes of service provided by a first one of said plurality of network servers in a manner that is individually defined for a plurality of successively greater thresholds in response to said effective presently used bandwidth of said first one of said plurality of network servers exceeding one of said plurality of successively greater thresholds, wherein said manner defined for said first one of said plurality of network servers differs from every other manner defined for other ones of said plurality of network servers.