Admission control in networked services

• US 20040114514A1
• Filed: 12/12/2002
• Published: 06/17/2004
• Est. Priority Date: 12/12/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Verma, Akshat, Karnik, Neeran M., Ghosal, Sugata
• Granted Patent: US 7,289,527 B2
• Time in Patent Office: Days
• US Class Current: 370/230
• 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, the method comprising the steps of:

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 (i) parameters associated with each received request R, and (ii) spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests.

2. The method as claimed in claim 1, wherein the parameters associated with each received request R comprise at least (i) the estimated time and system capacity required to service the received request R, and (ii) the rewards and/or 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/or 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/or penalties associated with received requests R are made equal for all received requests R.

5. The method as claimed in claim 1, wherein the admission control criterion is further based upon (iii) an estimate of expected requests, and parameters associated with said expected requests.

6. The method as claimed in claim 5, further comprising the steps of

determining if two received requests R collide, based upon whether said two received requests can be serviced using the spare service 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; and

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.

7. The method as claimed in claim 6, further comprising the step of predicting expected requests RD that may arrive during the decision horizon T.

8. The method as claimed in claim 7, further comprising the step of pre-reserving capacity for selected expected requests R_D.

9. The method as claimed in claim 8, 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.

10. The method as claimed in claim 8, wherein capacity is pre-reserved for expected requests R_D which satisfy a predetermined profitability criterion.

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

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

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

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

means 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 (i) parameters associated with each received request R, and (ii) spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests.

13. The computer system as claimed in claim 12, wherein the parameters associated with each received request R comprise at least (i) the estimated time and system capacity required to service the received request R, and (ii) the rewards and/or 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/or 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/or 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 admission control criterion is further based upon (iii) an estimate of expected requests, and parameters associated with said expected requests.

17. The computer system as claimed in claim 16, further comprising

means for determining if two received requests R collide, based upon whether said two received requests can be serviced using the spare service 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; and

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.

18. The computer system as claimed in claim 17, further comprising means for predicting expected requests R_D that may arrive during the decision horizon T.

19. The computer system as claimed in claim 18, further comprising means for pre-reserving capacity for selected expected requests R_D.

20. The computer system as claimed in claim 19, 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.

21. The computer system as claimed in claim 19, wherein capacity is pre-reserved for expected requests R_D which satisfy a predetermined profitability criterion.

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

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

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

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

software code means 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 (i) parameters associated with each received request R, and (ii) spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests.

24. The computer software as claimed in claim 23, wherein the parameters associated with each received request R comprise at least (i) the estimated time and system capacity required to service the received request R, and (ii) the rewards and/or 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/or 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/or 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 admission control criterion is further based upon (iii) an estimate of expected requests, and parameters associated with said expected requests.

28. The computer software as claimed in claim 27, further comprising software code means for determining if two received requests R collide, based upon whether said two received requests can be serviced using the spare service capacity.

29. The computer software as claimed in claim 28, further comprising software code means for defining a decision horizon T in which a received request R can be serviced;

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

software code 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; and

software code means for predicting expected requests RD that may arrive during the decision horizon T.

30. The computer software as claimed in claim 29, further comprising software code means for pre-reserving capacity for selected expected requests RD.

31. The computer software as claimed in claim 30, 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 RD.

32. The computer software as claimed in claim 30, wherein capacity is pre-reserved for expected requests RD which satisfy a predetermined profitability criterion.

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

34. A computer architecture 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 for (i) receiving the received requests R from the client sites, estimating system capacity consumed by received requests R that are admitted for system servicing; and

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

network devices, operatively connected with the server, for servicing received requests R that are accepted by the server;

wherein the admission control criterion is based upon at least (i) parameters associated with each received request R, and (ii) spare system capacity, estimated as total system capacity less total system capacity estimated to be consumed by admitted requests.