Imbedding gradient estimators in load balancing algorithms

Author

Pulidas, Spiridon ; Towsley, Don ; Stankovic, John A.

Author_Institution

Massachusetts Univ., Amherst, MA, USA

fYear

1988

fDate

13-17 Jun 1988

Firstpage

482

Lastpage

490

Abstract

The problem of efficiently determining the optimum threshold parameter values for a decentralized load balancing algorithm is investigated. Simulation is used to study the behavior of a gradient-based decentralized optimization algorithm for obtaining good values. The algorithm computes the incremental job delay as a function of changes in both the local and remote job arrival rate. Estimators for these two quantities that are embedded in the optimization algorithm are described. Several experiments designed to evaluate the performance of the algorithm in a stationary environment and in an environment where there are changes in the workload are presented. The results indicate that the estimators are accurate, the algorithm chooses good thresholds, and the resultant response time of jobs is near optimal

Keywords

delays; distributed processing; optimisation; performance evaluation; supervisory programs; distributed computer systems; gradient-based decentralized optimization algorithm; incremental job delay; load balancing algorithms; optimum threshold parameter; remote job arrival rate; response time; Algorithm design and analysis; Contracts; Delay effects; Delay estimation; Distributed computing; Information analysis; Iterative algorithms; Load management; Optimal control; Yarn;

fLanguage

English

Publisher

ieee

Conference_Titel

Distributed Computing Systems, 1988., 8th International Conference on

Conference_Location

San Jose, CA

Print_ISBN

0-8186-0865-X

Type

conf

DOI

10.1109/DCS.1988.12551

Filename

12551