MANY-SERVER QUEUES WITH CUSTOMER ABANDONMENT:A SURVEY OF DIFFUSION AND FLUID APPROXIMATIONS

The performance of a call center is sensitive to customer abandonment. In this survey paper, we focus on G/GI/n ＋ GI parallel-server queues that serve as a building block to model call center operations. Such a queue has a general arrival process （the G ）, independent and identically distributed （iid） service times with a general distribution （the first G1 ）, and iid patience times with a general distribution （the ＋GI）. Following the square-root safety staffing rule, this queue can be operated in the quality- and efficiency-driven （QED） regime, which is characterized by large customer volume, the waiting times being a fraction of the service times, only a small fraction of customers abandoning the system, and high server utilization. Operational efficiency is the central target in a system whose staffing costs dominate other expenses. If a moderate fraction of customer abandonment is allowed, such a system should be operated in an overloaded regime known as the efficiency-driven （ED） regime. We survey recent results on the many-server queues that are operated in the QED and ED regimes. These results include the performance insensitivity to patience time distributions and diffusion and fluid approximate models as practical tools for performance analysis.

Approximate Sorting of Packet-Scheduling in High-Speed Networks

Fairness, latency and computational complexity are three important factors in evaluating the performance of a scheduling algorithm. Fairness must be satisfied so that service can be distributed according to the reserved rate. Only when latency is irrelevant to the number of connections, is it possible to minimize the end-to-end delay through controlling the reserved rate. Among existing scheduling algorithms, Round Robin is the least complex. However, conventional Round Robin is unable to ensure fairness, and the improved round robin algorithms like Deficit Round Robin, Weighted Round Robin and Virtual Round Robin are unable to ensure that their latencies are irrelevant to the number of connections although they gua- rantee fairness. Potential Round Robin developed for analysis of fairness and latency reduction is thus proposed. It is based on the introduction of a new concept, Round Potential Function. The function splits service time into a number of service round periods to guarantee fairness regardless of the serving process used in the period. In the analysis of latency, service round periods are re-split into multiple scanning cycles for further service distribution with approximate sorting between scanning cycles. As a result, latency is no longer relevant to the number of connections while the low complexity of round robin is kept.