Thumbnail
Access Restriction
Open

Author Bansal, Nikhil ♦ Pruhs, Kirk
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Lp Norm ♦ Extended Abstract ♦ Tide Lift Boat ♦ Average Qos ♦ L_p Norm ♦ Known Algorithm ♦ Standard Qos Measure ♦ Pittsburgh Kirk C ♦ Standard Algorithm ♦ Round Robin ♦ Average Quality ♦ Near Peak Capacity ♦ Processor Sharing Algorithm ♦ Edu Abstract Often ♦ Standard Nonclairvoyant Algorithm ♦ Fairness Property ♦ Server Scheduling Strategy ♦ Standard Method ♦ Individual Job ♦ Standard Clairvoyant Algorithm ♦ Kirk Pruhs University ♦ Nikhil Bansal Carnegie Mellon University ♦ Competitive Online Algorithm
Abstract Nikhil Bansal Carnegie Mellon University nikhil@cs.cmu.edu Kirk Pruhs University of Pittsburgh kirk@cs.pitt.edu ABSTRACT Often server systems do not implement the best known algorithms for optimizing average Quality of Service (QoS) out of concern of that these algorithms may be insu#ciently fair to individual jobs. The standard method for balancing average QoS and fairness is optimize the Lp metric, 1 <p<#. Thus we consider server scheduling strategies to optimize the Lp norms of the standard QoS measures, flow and stretch. We first show that there is no n -competitive online algorithm for the Lp norms of either flow or stretch. We then show that the standard clairvoyant algorithms for optimizing average QoS, SJF and SRPT,areO(1+#)-speed O(1/# )- competitive for the Lp norms of flow and stretch. And that the standard nonclairvoyant algorithm for optimizing average QoS, SETF,isO(1+#)-speed O(1/# )-competitive for the Lp norms of flow. These results argue that these standard algorithms will not starve jobs until the system is near peak capacity. 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 + #)-speed n -competitive for su#ciently small #.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2003-01-01