On admission control for profit maximization of networked service providers

ABSTRACT

Variability and diverseness among incoming requests to a service hosted on a finite capacity resource necessitates sophisticated request admission control techniques for providing guaranteed quality of service (QoS). We propose in this paper a service time based online admission control methodology for maximizing profits of a service provider. The proposed methodology chooses a subset of incoming requests such that the revenue of the provider is maximized. Admission control decision in our proposed system is based upon an estimate of the service time of the request, QoS bounds, prediction of arrivals and service times of requests to come in the short-term future, and rewards associated with servicing a request within its QoS bounds. Effectiveness of the proposed admission control methodology is demonstrated using experiments with a content-based messaging middleware service.

REFERENCES

• 1: Arun K. Iyengar , Mark S. Squillante , Li Zhang, Analysis and characterization of large-scale Web server access patterns and performance, World Wide Web, v.2 n.1-2, p.85-100, 1999 [doi>10.1023/A:1019244621570]
• 2: Xiangping Chen , Prasant Mohapatra , Huamin Chen, An admission control scheme for predictable server response time for web accesses, Proceedings of the 10th international conference on World Wide Web, p.545-554, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372156]
• 3: A Cost-Based Admission Control Algorithm for Handling Mixed Workloads in Multimedia Server Systems, Proceedings of the Eighth International Conference on Parallel and Distributed Systems, p.543, June 26-29, 2001
• 4: Zhen Liu , Mark S. Squillante , Joel L. Wolf, On maximizing service-level-agreement profits, Proceedings of the 3rd ACM conference on Electronic Commerce, p.213-223, October 14-17, 2001, Tampa, Florida, USA [doi>10.1145/501158.501185]
• 5: T. S. Jayram , Tracy Kimbrel , Robert Krauthgamer , Baruch Schieber , Maxim Sviridenko, Online server allocation in a server farm via benefit task systems, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.540-549, July 2001, Hersonissos, Greece [doi>10.1145/380752.380849]
• 6: J.A. Garay, I.S. Gopal, S. Kutten, Y. Mansour, and M. Yung. Efficient online call control algorithms. In Proc. Israeli Conf. on Theory of Computing and Systems, pp. 285--293, 1993.
• 7: R. Lipton, Online interval scheduling, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.302-311, January 23-25, 1994, Arlington, Virginia, United States
• 8: Amotz Bar-Noy , Ran Canetti , Shay Kutten , Yishay Mansour , Baruch Schieber, Bandwidth Allocation with Preemption, SIAM Journal on Computing, v.28 n.5, p.1806-1828, April/May 1999 [doi>10.1137/S0097539797321237]
• 9: Amotz Bar-Noy , Yishay Mansour , Baruch Schieber, Competitive dynamic bandwidth allocation, Proceedings of the seventeenth annual ACM symposium on Principles of distributed computing, p.31-39, June 28-July 02, 1998, Puerto Vallarta, Mexico [doi>10.1145/277697.277704]
• 10: Y.-C. Chang, X. Guo, T. kimbrel, and A. King. Optimal allocation policies for web hosting. In Proc. Informs Conf. on Applied Probability, New York, NY, 2001.
• 11: Sandy Irani, Page replacement with multi-size pages and applications to Web caching, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.701-710, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258666]
• 12: Niranjan Joshi , Srinivas R. Kadaba , Sarvar Patel , Ganapathy S. Sundaram, Downlink scheduling in CDMA data networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.179-190, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345941]
• 13: M.S. Squillante, D.D. Yao, and L. Zhang. Web traffic Modeling and web server performance analysis. In Proc. IEEE Conf. on Decision and Control, pp. 4432--4437, 1999.
• 14: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.735-744, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335410]
• 15: Abraham Silberschatz , Peter Baer Galvin, Operating System Concepts, John Wiley & Sons, Inc., New York, NY, 1999
• 16: R. Morris, and D. Lin. Variance of aggregated web traffic. In Proc. IEEE INFOCOM, 2000.
• 17: Marcos K. Aguilera , Robert E. Strom , Daniel C. Sturman , Mark Astley , Tushar D. Chandra, Matching events in a content-based subscription system, Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, p.53-61, May 04-06, 1999, Atlanta, Georgia, United States [doi>10.1145/301308.301326]
• 18: P.A. Samuelson and W.D. Nordhaus. Economics. Tata McGraw-Hill, pp. 80--83, 1998.
• 19: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 20: Mark E. Crovella , Murad S. Taqqu , Azer Bestavros, Heavy-tailed probability distributions in the World Wide Web, A practical guide to heavy tails: statistical techniques and applications, Birkhauser Boston Inc., Cambridge, MA, 1998
• 21: Clarknet HTTP Trace. Available at ftp://ita.ee.ibl.gov/traces/clarknet_access_log_Sep4.gz, Oct 15, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Algorithms, Management, Performance

Keywords:
admission control, profit maximization, quality of service (QoS), service level agreement (SLA), service time estimation, short-term prediction, shortest remaining job first (SRJF), web service