| Distributed Computing Systems are rapidly becoming the computing environment of choice since they possess great advantages of power, cost, and flexibility over mainframes.;The performance of a distributed computing system is often adversely affected by a phenomenon called Load Imbalance, in which some computing sites are overloaded while some others are simultaneously underloaded. Load Imbalance wastes computing resources, decreases system utilization, and retards performance. A technique called Load Sharing is used to redistribute system load and improve system performance.;In this dissertation we use analytic techniques based upon stochastic queuing theory to investigate load imbalance in detail. Three aspects of load imbalance are identified: frequency, magnitude, and temporal. The frequency aspect deals with how often load imbalance occurs and how many computing sites are involved in a load imbalance. The magnitude aspect relates to the total number of jobs across the system which can usefully be redistributed to alleviate load imbalance. The temporal aspect of load imbalance is concerned with the duration of load imbalance, i.e., for how long load imbalance persists once it has started.;For each of these three facets of load imbalance, we identify descriptive random variables such as Severity of Load Imbalance, Number of Sharable Jobs, Job Sharing Coefficient, Load Sharing Window, and derive general expressions for their probability distribution functions. These random variables lead to measures quantifying load sharing potential. Measures of load sharing potential are computed for common queuing models such as M/M/1, M/D/1 etc., and the results plotted for representative values of system parameters. We also define Quantile Rules, criteria for maximizing probability of successful job transfer and for performing bulk job transfer.;The research described in this thesis provides a basis for constructing improved load sharing algorithms which take into account detailed insights into the nature of load imbalance, thereby maximizing resource utilization and enhancing the performance of distributed computing systems. |
