Relaxed asynchronous flow-control algorithms for multiclass service networks

This paper addresses resource sharing in a multiclass service center. The flow of service requests from each class of customers is regulated by a class manager who attempts to maximize the class net benefit (throughput reward less delay cost). Relaxed asynchronous algorithms are proposed for obtaining a Nash equilibrium among these competing classes in which each manager iteratively updates his throughput strategy in response to local (and possibly delayed) information on the strategies of the others. The novelty of these flow-control algorithms is in the relaxation, whereby each manager employs a strategy update that is a convex combination of his previous strategy and his best-reply strategy to current information. Alternatively, this relaxation can be viewed as an exponential smoothing of all previous best-reply strategies. For a particular number of classes with specified cost/reward parameters, relaxation conditions for asymptotic convergence to the unique interior Nash equilibrium are presented. For more than two classes, it is shown that relaxation not only accelerates convergence (at least in a special case), but also is a necessary condition for convergence. Due to an equivalent functional form, these results can be directly translated to a network of users employing a power criterion, a common objective in the communications literature.