Browse Prior Art Database

LOAD BALANCING IN DISTRIBUTED SYSTEMS WITH MULTIPLE CLASSES AND SITE CONSTRAINTS

IP.com Disclosure Number: IPCOM000128336D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 14 page(s) / 42K

Publishing Venue

Software Patent Institute

Related People

Edmundo Silva: AUTHOR [+4]

Abstract

In this paper we consider a distributed computer system formed by heterogeneous compwer sa oosmected by a ~uaication network and supporting multiple job dassei. Jobs arriving at a site may ~., processed locally or seat to a remote site for execution. Restz=oas may apply is the remote e dispatcher, so that a class of jobs may be allowed to run only is a subset of all sites in the network. Ice oar study, we assume that the cmm=utlicatioa network as well as each of the computer sites can be modeled as product form queueing networks. Our goal is to find the optimum assignment of jobs to sites so that a weighted sum of response times over classes is minimized. We propose an effideat algorithm for fining the op. bimum load balancing strategy. The algorithm is based on a downhill procedure to search for the global minimum. We show that the steepest descent direction (a key step in the downhill procedure) can be easi- ly calculated using the Mean Value Analysis Algorithm. A numerical example is presented.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 11% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

LOAD BALANCING IN DISTRIBUTED SYSTEMS WITH MULTIPLE CLASSES AND SITE CONSTRAINTS

Edmundo Silva Mario Gerla Report No. CSD-840033

TER CnPY

LOAD BA,LANCINP IN DISTRIBUTED SYSTEM WITS MULTIPLE CLASSES AND SITE CONSTRAINTS F.dmnado de Santa a Silva Maxio Gala

UCLA Computer Science Department Loa Angeles, CA 90024

April 1984 '"~'' This research was supported in part by DARPA contract MDA 903-82- C-0064 and in part by UC-MICRO contract 442515-19900. LOAD BALANCING IN DISTRIBUTED SYSTEMS WITH MULTIPLE CLASSES AND SITE CONSTRAINTS

Abstract

In this paper we consider a distributed computer system formed by heterogeneous compwer sa oosmected by a ~uaication network and supporting multiple job dassei. Jobs arriving at a site may ~., processed locally or seat to a remote site for execution. Restz=oas may apply is the remote e dispatcher, so that a class of jobs may be allowed to run only is a subset of all sites in the network. Ice oar study, we assume that the cmm=utlicatioa network as well as each of the computer sites can be modeled as product form queueing networks. Our goal is to find the optimum assignment of jobs to sites so that a weighted sum of response times over classes is minimized. We propose an effideat algorithm for fining the op. bimum load balancing strategy. The algorithm is based on a downhill procedure to search for the global minimum. We show that the steepest descent direction (a key step in the downhill procedure) can be easi- ly calculated using the Mean Value Analysis Algorithm. A numerical example is presented.

1. Introduction

The pmt fear years have witnessed an lag number of distdbtrted computer system imple- mentations based on local area networks. In thaw systems a number of resources (CJ's, Me servers, disks, etc.) are shared among jobs originating at different computer sites. An example of successful implo- motion is the LOCUS operating system [PaPE81]. Under the LOCUS system, generated by users at one site is the network are allowed to rue on other sites.

in general, is a distributed system environment it is desirable to equalize the usage of resources (balance the load) is order to reduce the response time of jobs and improve the utilization of the resources.

The load balaaoag problem is a dish resource system is not new and. can take differ forms for different problems. For example, is a long haul packet computer network (where the resources are the cIs), load baian g becomes the routing problem The goal there is to ford optimum paths on which to distribute flee packets, so that some well defined parformenoe criterion (overall delay, for stance) is optimized.

UCLA Page 1 Dec 31, 1984

Page 2 of 14

LOAD BALANCING IN DISTRIBUTED SYSTEMS WITH MULTIPLE CLASSES AND SITE CONSTRAINTS

In a distributed muter system, the load balancing problem may be form as the problem of distributing the execution of processes throughout the network is order to minimize...