Optimal resource allocation in packet networks

Abstract

This limitation can be overcome by considering a Non-Rate Proportional resource allocation. We present an Optimal Call Admission Control (CAC) algorithm for Generalized Processor Sharing (GPS) schedulers that performs a general resource allocation or a non-rate proportional resource allocation in the single-node case. Its fundamental merit arises from the fact that it takes into account the bandwidth released by the sessions that have completed their backlogs while calculating the session rates. The algorithm allots minimum rates to the sessions so that their delay bounds are not violated. Numerical results show that the Optimal Call Admission Control can accept significantly more connections than the CAC based on rate-proportional allocation, and hence results in better network utilization. It is further shown that a lesser resource allocation occurs in the case of Shaped Generalized Processor Sharing schedulers (i.e., an appropriate shaper is introduced before the GPS scheduler). Finally, we address the problem of reserving bandwidth optimally in a network of GPS schedulers to provide deterministic end-to-end delay guarantees. The CAC problem in a network setting is practically more important and has not been addressed in the literature. This problem is non-trivial and has several dimensions apart from those involved in a single-node case, such as the varying connection characteristics as it passes through the nodes in the network and its complex interaction with other sessions in the network. Bandwidth allocation in the network case starts by allocating enough bandwidth at each node such that the end-to-end delays can be guaranteed. Then, one seeks to reduce the nodal rate allocations so that the end-to-end delay guarantees are satisfied with equality, i.e., the end-to-end delays are not strictly smaller than the required values. It is observed that the “no slack” end-to-end delays can be provided by a number of allocations of the nodal bandwidths. This raises the issue: What is the optimal allocation? It is shown that this problem can be viewed in the framework of a Linear Program, which allows the optimal allocation to be identified easily.