Average response time minimization in star-connected computer networks

The authors consider static and adaptive-decentralized optimisation of the performance of a distributed computing system with a central processor (CP), denoted by S₀ loosely coupled to N peripheral processors (PPs), denoted by S _i, i=1, . . ., N. Each PP receives a stream of Poisson job arrivals with a rate λ_i. The arriving load at S_i is distributed between the CP and itself with probabilities P_i and (1-P_i) respectively. The service time distribution at each processor is arbitrary with mean 1/μ_i and second moment E[Y_i²], i=0, . . ., N. The objective is to determine the probabilities P _i, i=1, . . ., N so as to minimize the expected steady state response time of jobs. The authors solve the problem for the case of known parameters through nonlinear optimization techniques and develop a centralized computational algorithm. An adaptive technique for each PP to compute its optimal P_i is developed. The latter technique is useful when the system parameters are unknown a priori. In this case, it is assumed that the CP gives the processing time (of a remote job) to a PP when returning the remote job submitted by that PP. The sequences of estimates (computed by PPs) are shown to converge to the jointly optimum routing probabilities with probability 1 and in the mean square sense. Simulation results demonstrate the practicality of the adaptive approach