NDLI: Load balancing with migration penalties

Content Provider	IEEE Xplore Digital Library
Author	Farias, V.F. Moallemi, C.C. Prabhakar, B.
Copyright Year	2005
Description	Author affiliation: Dept. of Electr. Eng., Stanford Univ., CA (Farias, V.F.; Moallemi, C.C.; Prabhakar, B.)
Abstract	Many practical systems perform load balancing. The main aim of load balancing is to utilize the capacity of a system of parallel processors efficiently and to reduce the delay of processing jobs. This paper is concerned with load balancing, or process migration, when there is a penalty associated with migration. We consider the following model: jobs arrive at each of n parallel servers. An arriving job can either be processed in a unit of time, on average, at the server where it arrives, or it can migrate to another server where it creates K ges 1 independent jobs. When K = 1, migrating jobs impose no extra cost and this problem is considered extensively in the literature. We are interested in the situation K > 1. The problem is to decide whether a job should migrate or not. On the one hand migration leads to load balancing and hence reduces backlogs. However, it also leads to the creation of extra work and, hence, to a potential loss of throughput. We ask: do there exist simple migration policies that can reduce backlogs while providing the highest throughput? Somewhat surprisingly, we find that policies like "migrate to the least loaded server" are unstable: they cause a loss of throughput. However, we find that a simple variant of this rule is stable and leads to a reduction of backlogs
Starting Page	558
Ending Page	562
File Size	685488
Page Count	5
File Format	PDF
ISBN	0780391519
DOI	10.1109/ISIT.2005.1523397
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-09-04
Publisher Place	Australia
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Load management Throughput Delay Costs Sampling methods Performance analysis Algorithm design and analysis Queueing analysis Computer science Random variables
Content Type	Text
Resource Type	Article

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