Scalable QoS-Based Resource Allocation in Hierarchical Networked Environment

In this paper, we study the problem of allocating end-to-end bandwidth to each of multiple traffic flows in a large-scale network. We adopt the QoS-based resource allocation model (Q-RAM) (K-S. Lui et al., 2000), whereby each flow derives an utility based on the amount of its allocated bandwidth. Our goal therefore is to maximize the total utility derived across all network flows. The NP-hard nature of the resource allocation problem is compounded by the need to select an appropriate path between each source-destination pair. We propose a hierarchical decomposition scheme that allows the resource allocation problem to be solved in a decentralized and scalable fashion. The hierarchy we use is based on a (natural) partitioning of the network into subnets, with resource allocation decisions made on a subnet-by-subnet basis. A novel distributed transaction scheme is used to ensure that resource allocations are consistent across all the subnets traversed by each flow. We provide both analytical and experimental evidence to show that our scheme is very scalable and yet does not sacrifice the quality of the allocations.