SERVER SCHEDULING TO BALANCE PRIORITIES, FAIRNESS, AND AVERAGE QUALITY OF SERVICE

Often server systems do not implement the best known algorithms for optimizing average Quality of Service (QoS) out of concern that these algorithms may be insufficiently fair to individual jobs. The standard method for balancing average QoS and fairness is to optimize the l(p) norm, 1 < p < infinity. Thus we consider server scheduling strategies to optimize the l(p) norms of the standard QoS measures, flow and stretch. We first show that there is no n(o(1))- competitive online algorithm for the l(p) norms of either flow or stretch. We then show that the standard clairvoyant algorithms for optimizing average QoS, Shortest Job First (SJF), and Shortest Remaining Processing Time (SRPT), are scalable for the l(p) norms of flow and stretch. We then show that the standard nonclairvoyant algorithm for optimizing average QoS, Shortest Elapsed Time First (SETF), is also scalable for the l(p) norms of flow. We then show that the online algorithm, Highest Density First (HDF), and the nonclairvoyant algorithm, Weighted Shortest Elapsed Time First (WSETF), are scalable for the weighted l(p) norms of flow. These results suggest that the concern that these standard algorithms may unnecessarily starve jobs is unfounded. In contrast, we show that the Round Robin, or Processor Sharing, algorithm, which is sometimes adopted because of its seeming fairness properties, is not O(1 + epsilon)-speed, n(o(1))-competitive for sufficiently small epsilon.