Admission control in networked services

• US 7,289,527 B2
• Filed: 12/12/2002
• Issued: 10/30/2007
• Est. Priority Date: 12/12/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Verma, Akshat, Karnik, Neeran M, Ghosal, Sugata
• Primary Examiner(s): Vu; Huy D.
• Assistant Examiner(s): MATTIS, JASON E
• Application Number:
  US10/317,358
• Publication Number:
  US 20040114514A1
• Time in Patent Office: 1,783 Days
• Field of Search: 370/444, 370/230, 370/443
• US Class Current: 370/444
• CPC Class Codes: G06F 9/505 considering the load
• 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/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/72 using reservation actions during connection setup
• CPC Class Codes: H04L 47/808 User-type aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/823 Prediction of resource usage
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Prediction-based online admission control for incoming jobs has an explicit objective of optimizing a utility function. The input to an algorithmic procedure is a set of requests made in respect of a network service. Each request has information about the length of the request. An output of the algorithmic procedure is a selected subset of requests that can be served within the capacity constraints of the network service, such that the utility function is approximately optimized (for example, minimized or maximized) depending on the context of the particular application.

Claims

1. A method for admission control of requests for a network service, said method comprising:

receiving requests R, having associated parameters, for the network service;

estimating system capacity consumed by received requests R that are admitted for system servicing; and

selectively accepting or rejecting each received request R according to an admission control criterion, wherein the admission control criterion is based upon at least parameters associated with each received request R, spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests, an estimate of expected requests, and parameters associated with said expected requests,

determining if two received requests R collide based upon whether said two received requests can be serviced using the spare system capacity;

defining a decision horizon T in which a received request R can be serviced;

applying an available capacity criterion at each time step t in the decision horizon T;

admitting a received request R only if the received request R meets the available capacity criterion at each time step t in the decision horizon T;

predicting expected requests R_D that may arrive during the decision horizon T; and

pre-reserving capacity for selected expected requests R_D,

wherein capacity is pre-reserved for expected requests R_D which satisfy a predetermined profitability criterion, and

wherein the predetermined profitability criterion is satisfied if an estimated probability of an expected request arriving and terminating during a remaining time in the decision horizon T after the expected colliding request R_D is serviced, multiplied by a sum of reward and penalty of an expected request exceeds a difference in the rewards of the received request R and the expected colliding request R_D.

2. The method as claimed in claim 1, wherein the parameters associated with each received request R comprise at least an estimated time and system capacity required to service the received request R, and any of rewards and penalties associated with performing the received request R.

3. The method as claimed in claim 2, wherein the admission control criterion attempts to maximize profitability under a service level agreement, and the rewards and penalties associated with received requests R are specified by the service level agreement.

4. The method as claimed in claim 2, wherein the admission control criterion attempts to maximize the received requests that are serviced under a service level agreement, and the rewards and penalties associated with received requests R are made equal for all received requests R.

5. The method as claimed in claim 1, wherein the available capacity criterion is satisfied for a received request R if the received request R can be serviced after system capacity is pre-reserved for selected expected request R_D.

6. The method as claimed in claim 1, wherein said requests R are received at a SOAP server.

7. The method as claimed in claim 3, wherein said service level agreement comprises a multiple-grade service level agreement.

8. The method as claimed in claim 7, wherein said multiple-grade service level agreement comprises different rewards for different values of service level agreement parameters.

9. The method as claimed in claim 8, further comprising checking whether failed requests R can be serviced in a next grade specified in said service level agreement.

10. The method as claimed in claim 9, further comprising continuing the checking process until all service level grades are exhausted upon which said failed requests R are rejected.

11. The method as claimed in claim 9, further comprising continuing the checking process until said failed requests R can be serviced.

12. A computer system for admission control of requests for a network services, the computer system comprising:

a receiver operable for receiving requests R, having associated parameters, for the network service;

a calculator operable for estimating system capacity consumed by received requests R that are admitted for system servicing; and

a controller operable for selectively accepting or rejecting each received request R according to an admission control criterion, wherein the admission control criterion is based upon at least parameters associated with each received request R, spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests, and an estimate of expected requests, and parameters associated with said expected requests;

a first component operable for determining if two received requests R collide, based upon whether said two received requests can be serviced using the spare system capacity;

a second component operable for defining a decision horizon T in which a received request R can be serviced;

a third component operable for applying an available capacity criterion at each time step t in the decision horizon T;

a fourth component operable for admitting a received request R only if the received request R meets the available capacity criterion at each time step t in the decision horizon T;

a fifth component operable for predicting expected requests R_D that may arrive during the decision horizon T; and

a sixth component operable for pre-reserving capacity for selected expected requests R_D,

wherein capacity is pre-reserved for expected requests R_D which satisfy a predetermined profitability criterion, and

wherein the predetermined profitability criterion is satisfied if an estimated probability of an expected request arriving and terminating during a remaining time in the decision horizon T after the expected colliding request R_D is serviced, multiplied by a sum of reward and penalty of an expected request exceeds a difference in rewards of the received request R and the expected colliding request R_D.

13. The computer system as claimed in claim 12, wherein the parameters associated with each received request R comprise at least an estimated time and system capacity required to service the received request R, and rewards and penalties associated with performing the received request R.

14. The computer system as claimed in claim 13, wherein the admission control criterion attempts to maximize profitability under a service level agreement, and the rewards and penalties associated with received requests R are specified by the service level agreement.

15. The computer system as claimed in claim 13, wherein the admission control criterion attempts to maximize the received requests that are serviced under a service level agreement, and the rewards and penalties associated with received requests R are made equal for all received requests R.

16. The computer system as claimed in claim 12, wherein the available capacity criterion is satisfied for a received request R if the received request R can be serviced after system capacity is pre-reserved for selected expected request R_D.

17. The computer system as claimed in claim 12, wherein said requests R are received at a SOAP server.

18. The computer system as claimed in claim 14, wherein said service level agreement comprises a multiple-grade service level agreement.

19. The computer system as claimed in claim 18, wherein said multiple-grade service level agreement comprises different rewards for different values of service level agreement parameters.

20. The computer system as claimed in claim 19, further comprising means for checking whether failed requests R can be serviced in a next grade specified in said service level agreement.

21. The computer system as claimed in claim 20, wherein the checking continues until all service level grades are exhausted upon which said failed requests R are rejected.

22. The computer system as claimed in claim 20, wherein the checking continues until said failed requests R can be serviced.

23. Computer software, recorded on a medium, performing a method for admission control of requests for a network service, the method comprising:

receiving requests R, having associated parameters, for the network service;

estimating system capacity consumed by received requests R that are admitted for system servicing; and

selectively accepting or rejecting each received request R according to an admission control criterion, wherein the admission control criterion is based upon at least parameters associated with each received request R, spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests, an estimate of expected requests, and parameters associated with said expected requests,

determining if two received requests R collide based upon whether said two received requests can be serviced using the spare system capacity;

defining a decision horizon T in which a received request R can be serviced;

applying an available capacity criterion at each time step t in the decision horizon T;

admitting a received request R only if the received request R meets the available capacity criterion at each time step t in the decision horizon T;

predicting expected requests R_D that may arrive during the decision horizon T; and

pre-reserving capacity for selected expected requests R_D,

wherein capacity is pre-reserved for expected requests R_D which satisfy a predetermined profitability criterion, and

wherein the predetermined profitability criterion is satisfied if an estimated probability of an expected request arriving and terminating during a remaining time in the decision horizon T after the expected colliding request R_D is serviced, multiplied by a sum of reward and penalty of an expected request exceeds a difference in the rewards of the received request R and the expected colliding request R_D.

24. The computer software as claimed in claim 23, wherein the parameters associated with each received request R comprise at least an estimated time and system capacity required to service the received request R, and any of rewards and penalties associated with performing the received request R.

25. The computer software as claimed in claim 24, wherein the admission control criterion attempts to maximize profitability under a service level agreement, and the rewards and penalties associated with received requests R are specified by the service level agreement.

26. The computer software as claimed in claim 24, wherein the admission control criterion attempts to maximize the received requests that are serviced under a service level agreement, and the rewards and penalties associated with received requests R are made equal for all received requests R.

27. The computer software as claimed in claim 23, wherein the available capacity criterion is satisfied for a received request R if the received request R can be serviced after system capacity is pre-reserved for selected expected requests R_D.

28. The computer software as claimed in claim 23, wherein said requests R are received at a SOAP server.

29. The computer software as claimed in claim 25, wherein said service level agreement comprises a multiple-grade service level agreement.

30. The computer software as claimed in claim 29, wherein said multiple-grade service level agreement comprises different rewards for different values of service level agreement parameters.

31. The computer software as claimed in claim 30, further comprising checking whether failed requests R can be serviced in a next grade specified in said service level agreement.

32. The computer software as claimed in claim 31, further comprising continuing the checking process until all service level grades are exhausted upon which said failed requests R are rejected.

33. The computer software as claimed in claim 31, further comprising continuing the checking process until said failed requests R can be serviced.

34. A computer architecture operable for admission control of requests for a network services, the computer system comprising:

a plurality of client sites that generate requests R, having associated parameters, for the network service;

a server operable for receiving the received requests R from the client sites, estimating system capacity consumed by received requests R that are admitted for system servicing; and

selectively accepting or rejecting each received request R according to an admission control criterion; and

network devices, operatively connected with the server, operable for servicing received requests R that are accepted by the server, wherein the admission control criterion is based upon at least parameters associated with each received request R, spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests, and an estimate of expected requests, and parameters associated with said expected requests;

means for determining if two received requests R collide based upon whether said two received requests can be serviced using the spare system capacity;

means for defining a decision horizon T in which a received request R can be serviced;

means for applying an available capacity criterion at each time step t in the decision horizon T;

means for admitting a received request R only if the received request R meets the available capacity criterion at each time step t in the decision horizon T;

means for predictin gexpected requests R_D that may arrive during the decision horizon T; and

means for pre-reserving capacity for selected expected requests R_D,

wherein capacity is pre-reserved for expected requests R_D which satisfy a predetermined profitability criterion, and

wherein the predetermined profitability criterion is satisfied if an estimated probability of an expected request arriving and terminating during a remaining time in the decision horizon T after the expected colliding request R_D is serviced, multiplied by a sum of reward and penalty of an expected request exceeds a difference in the rewards of the received request R and the expected colliding request R_D.