STATIC AND DECENTRALIZED-ADAPTIVE LOAD BALANCING IN A STAR CONFIGUREDDISTRIBUTED COMPUTING SYSTEM

The problem of minimizing the average job response time (sojourn time) in a star configured Distributed Computing System (DCS) with N periph eral processors and one central processor is studied. Each peripheral processor (satellite) receives a stream of Poisson arrivals, A job arr iving at a satellite S-i will be processed with a probability (1 - P-i ) by itself and routed to the central site for remote processing with probability P-i. The service time distribution at each processor is ar bitrary with means 1/mu(i) and second moments E[Y-i(2)], i = 0,..., N. We first develop an algorithm to compute the optimal routing probabil ities when the arrival and the service parameters are known a priori. For a special case, when all the professors have exponential service t ime distributions, we obtain explicit closed form expressions for the static optimal routing probabilities under the assumption that the der ivative of the objective function vanishes inside or on the N-cube of routing probabilities. If this assumption is violated, at least one of the computed probability falls outside [0, 1]. We develop an O(N log N) algorithm to compute the optimal probabilities within the valid ran ge. The second and a major contribution of the paper is the developmen t of an adaptive estimator to be used by each satellite to compute its optimal routing probability, when the parameters (everywhere) are unk nown a priori. A copy of the algorithm runs on each peripheral process or and uses the sojourn time measurements that the peripheral processo r can gather on its own from those jobs that are sent to the central p rocessor and returned to the originating site after service. It is ass umed that the central processor gives the processing time (of a remote job) to a peripheral processor when returning the remote job submitte d by that PP. The algorithm does not use any other message transmissio n between processors. This makes our algorithm thoroughly decentralize d. We prove the convergence, with probability 1 and in mean square, of the proposed adaptive estimator to the optimum routing probabilities, under the assumption that the arrival and service parameters are cons tants. We present simulation results to demonstrate the performance of the algorithm under several sets of conditions, including one in whic h the parameters change with sudden jumps.