RTAS 2005 START ConferenceManager    

Scalable QoS-Based Resource Allocation in Hierarchical Networked Environment

Sourav Ghosh, Ragunathan (Raj) Rajkumar, Jeffery Hansen, John Lehoczky

Presented at IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2005), San Francisco, California, March 7 - 10, 2005


In this paper, we study the problem of allocating end-to-end bandwidth to each of multiple traffic flows in a largescale network. We adopt the QoS-based Resource Allocation Model (Q-RAM) [9], 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.

START Conference Manager (V2.47.7)
Maintainer: hjkim@redwood.snu.ac.kr