System Utility Maximisation With Fast Network and User Adaptation

Kelly, Maulloo, and Tan (1998) proposed a decomposition of a system utility maximisation problem into a network utility maximisation problem, to be solved by a network entity, and a set of decoupled user optimisation problems, to be solved by the individual users. They proposed an iterative scheme where the users signal their willingness to pay (a scalar quantity) while the network signals the charges per unit flow. Their scheme involves a slow adaptation by the network and a fast adaptation by the users. Their scheme converges to the system optimal solution and has the advantage that the network entity need not know the users' utility functions and the individual users need not know the network state or utility functions of other users. In this talk, we will discuss a special case and a modified algorithm where the network also makes a fast adapation. We will then show that the algorithm converges to the global optimum solution.