Robustness of threshold policies in beneficiary-donor model

ABSTRACT

A common problem in multiserver systems is deciding how to allocate resources among jobs so as to minimize mean response time. Since good parameter settings typically depend on environmental conditions such as system loads, an allocation policy that is optimal in one environment may provide poor performance when the environment changes, or when the prediction of the environment is wrong. We say that such a policy is not robust. In this paper, we analytically compare the robustness of several threshold-based allocation policies, in a dual server beneficiary-donor model. We introduce two types of robustness: static robustness, which measures robustness against mis-estimation of the true load, and dynamic robustness, which measures robustness against fluctuations in the load. We find that policies employing multiple thresholds offer significant benefit over single threshold policies with respect to static robustness. Yet they surprisingly offer much less benefit with respect to dynamic robustness.

REFERENCES

• 1: H. Ahn, I. Duenyas, and R. Zhang. Optimal control of a flexible server. Advances in Applied Probability, 36:139--170, 2004.
• 2: S. Bell and R. Williams. Dynamic scheduling of a system with two parallel servers in heavy traffic with complete resource pooling: Asymptotic optimality of a continuous review threshold policy. Annals of Applied Probability, 11:608--649, 2001.
• 3: D. Cox and W. Smith. Queues. Kluwer Academic Publishers, 1971.
• 4: Noah Gans , Ger Koole , Avishai Mandelbaum, Commissioned Paper: Telephone Call Centers: Tutorial, Review, and Research Prospects, Manufacturing & Service Operations Management, v.5 n.2, p.79-141, April 2003 [doi>10.1287/msom.5.2.79.16071]
• 5: L. Green. A queueing system with general use and limited use servers. Operations Research, 33(1):168--182, 1985.
• 6: J. M. Harrison. Heavy traffic analysis of a system with parallel servers: Asymptotic optimality of discrete review policies. Annals of Applied Probability, 8(3):822--848, 1998.
• 7: Sean P. Meyn, Sequencing and Routing in Multiclass Queueing Networks Part I: Feedback Regulation, SIAM Journal on Control and Optimization, v.40 n.3, p.741-776, 2001 [doi>10.1137/S0363012999362724]
• 8: T. Osogami, M. Harchol-Balter, A. Scheller-Wolf, and L. Zhang. Exploring threshold-based policies for load sharing. In 42nd Annual Allerton Conference on Communication, Control, and Computing, Sept. 2004.
• 9: M. Squillante, C. Xia, D. Yao, and L. Zhang. Threshold-based priority policies for parallel-server systems with affinity scheduling. In IEEE American Control Conference, pages 2992--2999, June 2001.
• 10: R. Williams. On dynamic scheduling of a parallel server system with complete resource pooling. In D. McDonald and S. Turner, editors, Analysis of Communication Networks: Call Centers, Traffic and Performance. American Mathematical Society, 2000.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.5 Servers

General Terms:
Design, Performance, Theory