Decentralized resource allocation mechanisms in networks.
Tudor Mihai Stoenescu · Deep Blue (University of Michigan) · 2004
One of the main challenges in the development of communication networks is the design of resource allocation strategies which guarantee the delivery of different services, each with its own Quality of Service (QoS) requirement, and maximize some performance criterion (e.g. the network's utility to its users). The challenge in determining such resource allocation strategies comes from the fact that networks are informationally decentralized systems, consisting of two type of agents: users and network. Each user has preferences over the set of services offered by the network. These preferences are usually expressed by a utility function. A user's utility function is its own private information. Each user requests services so as to maximize its utility function and is unaware as well as uninterested in the method used for the delivery of the requested services. Furthermore each user is unaware of the set of other users requesting network services. The network (network manager) knows the network topology and the network's resources (e.g. link capacities, buffer size at each node) but is unaware of the number of users that may request services, as well as the users' utilities. In this thesis we investigate some of the key features of decentralized resource allocation mechanisms in the context of network problems. The main contributions of this thesis are: (1) the development of goal realizing resource allocation pricing mechanisms for (i) unicast networks with routing and Quality of Service requirements, and (ii) multi-rate multicast; (2) the proof that the above pricing mechanisms have a message space of dimensionality which is a lower bound for the dimensionality of the message spaces of all goal realizing and regular mechanisms; and (3) the proof that for a large class of environments the above pricing mechanisms are informationally efficient.