On maximizing service-level-agreement profits

ABSTRACT

We present a methodology for maximizing profits in a general class of e-commerce environments. The cost model is based on revenues that are generated when Quality-of-Service (QoS) guarantees are satisfied and on penalties that are incurred otherwise. The corresponding QoS criteria are derived from multiclass Service-Level-Agreements (SLAs) between service providers and their clients, which include the tail distributions of the per-class delays in addition to more standard QoS metrics such as throughput and mean delays. Our approach consists of formulating the optimization problem as a network flow model with a separable set of concave objective functions based on queueing-theoretic formulas, where the SLA classes are taken into account in both the constraints and the objective function. This problem is then solved via a fixed-point iteration. Numerous experiments illustrate the benefits of our approach.

REFERENCES

• 1: R. Ahuja, T. Magnanti, and J. Orlin. Network Flows. Prentice Hall, Englewood Cliffs, New Jersey, 1993.
• 2: S. Borst, O. Boxma, and P. R. Jelenkovic. Asymptotic behavior of generalized processor sharing with long-tailed traffic sources. In Proceedings of the INFOCOM, Tel-Aviv, Israel, 2000.
• 3: A. Federgruen , H. Groenevelt, The greedy procedure for resource allocation problems: Necessary and sufficient conditions for optimality, Operations Research, v.34 n.6, p.909-918, Nov.-Dec. 1986 [doi>10.1287/opre.34.6.909]
• 4: B. Fox. Discrete optimization via marginal analysis. Management Science, 13:210-216, November 1966.
• 5: G. Frederickson and D. Johnson. The complexity of selection and ranking in x + y and matrices with sorted columns. Journal of Computer and System Sciences, 24:197-208, 1982.
• 6: Zvi Galil , Nimrod Megiddo, A Fast Selection Algorithm and the Problem of Optimum Distribution of Effort, Journal of the ACM (JACM), v.26 n.1, p.58-64, Jan. 1979 [doi>10.1145/322108.322114]
• 7: Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
• 8: F. P. Kelly. Reversibility and Stochastic Networks. John Wiley & Sons, New York, 1979.
• 9: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 10: Z. Liu , N. Niclausse , C. Jalpa-Villanueva, Web traffic modeling and performance comparison between HTTP1.0 and HTTP1.1, System performance evaluation: methodologies and applications, CRC Press, Inc., Boca Raton, FL, 2000
• 11: Z. Liu, M. S. Squillante, and J. L. Wolf. On maximizing service-level-agreement profits. Technical report, IBM Research Division, 2001.
• 12: Daniel A. Menascé , Virgilio A. F. Almeida , Rodrigo Fonseca , Marco A. Mendes, A methodology for workload characterization of E-commerce sites, Proceedings of the 1st ACM conference on Electronic commerce, p.119-128, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337024]
• 13: Daniel A. Menascé , Virgilio A. F. Almeida , Rodrigo Fonseca , Marco A. Mendes, Business-oriented resource management policies for e-commerce servers, Performance Evaluation, v.42 n.2-3, p.223-239, Oct. 2000 [doi>10.1016/S0166-5316(00)00034-1]
• 14: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 15: Abhay K. Parekh , Robert G. Gallagher, A generalized processor sharing approach to flow control in integrated services networks: the multiple node case, IEEE/ACM Transactions on Networking (TON), v.2 n.2, p.137-150, April 1994 [doi>10.1109/90.298432]
• 16: Peter L. T. Pirolli , James E. Pitkow, Distributions of surfers’ paths through the World Wide Web: Empirical characterizations, World Wide Web, v.2 n.1-2, p.29-45, 1999 [doi>10.1023/A:1019288403823]
• 17: H. Takagi. Queueing Analysis: A Foundation of Performance Evaluation. Volume 1: Vacation and Priority Systems, Part 1. North Holland, Amsterdam, 1991.
• 18: A. N. Tantawi , G. Towsley , J. Wolf, Optimal allocation of multiple class resources in computer systems, Proceedings of the 1988 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.253-260, May 24-27, 1988, Santa Fe, New Mexico, United States
• 19: Z.-L. Zhang, Z. Liu, J. Kurose, and D. Towsley. Call admission control schemes under the generalized processor sharing scheduling discipline. Telecommunication Systems, 7:125-152, 1997.
• 20: Z.-L. Zhang, Z. Liu, and D. Towsley. Closed-form deterministic performance bounds for the generalized processor sharing scheduling discipline. Journal of Combinatorial Optimaization,1, 1998.
• 21: Z. L. Zhang, D. Towsley, and J. Kurose. Statistical analysis of the generalized processor sharing scheduling discipline. IEEE Journal on Selected Areas in Communications, 13(6):1071-1080, 1995.
• 22: A. P. Zwart , O. J. Boxma, Sojourn time asymptotics in the M$/$G$/$1 processor sharing queue, Queueing Systems: Theory and Applications, v.35 n.1-4, p.141-166, 2000 [doi>10.1023/A:1019142010994]

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

Additional Classification:
  J. Computer Applications
  J.1 ADMINISTRATIVE DATA PROCESSING
      Subjects: Business
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Experimentation, Management, Theory