A calculus of variations approach to file allocation problems in computer systems

This paper is concerned with the parameter optimization in closed product-form queueing networks. Our approach is to combine the techniques of the calculus of variations with the mean value analysis (MVA) recursion of closed queueing networks. We view the MVA recursion as nonlinear difference equations describing a multi-stage system, wherein a stage corresponds to the network population, and the response times at each node constitute the state variables of the multi-stage system. This viewpoint leads to a two-point boundary value problem, in which the forward system corresponds to the MVA recursion and the backward system corresponds to an MVA-like adjoint recursion. The method allows for a very general class of objective functions, and the adjoint equations provide the necessary information to compute the gradient of the cost function. The optimization problem can then be solved by any of the gradient-based methods. For the special case when the objective function is the network delay function, the gradient vector is shown to be related to the moments of the queue lengths. In addition, the adjoint vector offers the potential for the on-line adaptive control of queueing networks based on the state information (e.g., actual degree of multi-programming, response times at the devices.) The theory is illustrated via application to the problem of determining the optimal disk routing probabilities in a large scale, modern I/O (Input/Output) subsystem. A subsequent paper will deal with extensions of the theory to multi-class networks.