NDLI: A Better Model for Task Assignment in Server Farms:How Replication can Help

Content Provider	ACM Digital Library
Author	Harchol-Balter, Mor
Abstract	An age-old problem in the design of server farms is the choice of the task assignment policy. This is the algorithm that determines how to assign incoming jobs to servers. Popular policies include Round-Robin assignment, Join-the-Shortest-Queue, Join-Queue-with-Least-Work, and so on. While much research has studied assignment policies, little has taken into account server-side variability -- the fact that the server we choose might be temporarily and unpredictably slow. We show that when server-side variability dominates runtime, replication of jobs can be very beneficial. We introduce the Replication-d algorithm that replicates each arrival to d servers chosen at random, where the job is considered "done" as soon as the first replica completes. We provide an exact closed-form analysis of Replication-d. We next introduce a much more general model, one which takes both the inherent job size distribution and the server-side variability into account. This is a departure from traditional queueing models which only allow for one "size" distribution. We propose and analyze a new task assignment policy, Replicate-Idle-Queue (RIQ), which is designed to perform well given these dual sources of variability.
Starting Page	73
Ending Page	73
Page Count	1
File Format	PDF
ISSN	01635999
DOI	10.1145/2964791.2901900
Journal	ACM SIGMETRICS Performance Evaluation Review (PERV)
Volume Number	44
Issue Number	1
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-01-10
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Queueing Power-of-d Resource allocation Replication Load balancing
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Better Model for Task Assignment in Server Farms: How Replication can Help

Surprising results on task assignment in server farms with high-variability workloads

Universality of Power-of-d Load Balancing Schemes

A queueing network approach to the module allocation problem in distributed systems

Contextual Resource Negotiation-Based Task Allocation and Load Balancing in Complex Software Systems

The Power of d Choices for Redundancy

Power of d Choices for Large-Scale Bin Packing:A Loss Model

Insensitive load balancing

Load balancing and the power of preventive probing

A Better Model for Task Assignment in Server Farms:How Replication can Help

Similar Documents

A Better Model for Task Assignment in Server Farms: How Replication can Help

Surprising results on task assignment in server farms with high-variability workloads

Universality of Power-of-d Load Balancing Schemes

A queueing network approach to the module allocation problem in distributed systems

Contextual Resource Negotiation-Based Task Allocation and Load Balancing in Complex Software Systems

The Power of d Choices for Redundancy

Power of d Choices for Large-Scale Bin Packing:A Loss Model

Insensitive load balancing

Load balancing and the power of preventive probing

A Better Model for Task Assignment in Server Farms:How Replication can Help