Skip to main content
eScholarship
Open Access Publications from the University of California

Optimal bandwidth allocation in a delay channel

  • Author(s): Ehsan, Navid
  • Liu, Mingyan
  • et al.
Abstract

In this paper, we consider the problem of allocating bandwidth to two queues with arbitrary arrival processes, so as to minimize the total expected packet holding cost over a finite or infinite horizon. Bandwidth is in the form of time slots in a time-division multiple-access schedule. Allocation decisions are made based on one-step delayed queue backlog information. In addition, the allocation is done in batches, in that a queue can be assigned any number of slots not exceeding the total number in a batch. We show for a two queue system that if the holding cost as a function of the packet backlog in the system is nondecreasing, supermodular, and superconvex, then: 1) the value function at each slot will also satisfy these properties; 2) the optimal policy for assigning a single slot is of the threshold type; and 3) optimally allocating M slots at a time can be achieved by repeatedly using a policy that assigns each slot optimally given the previous allocations. Thus, the problem of finding the optimal allocation strategy for a batch of slots reduces to that of optimally allocating a single slot, which is conceptually much easier to obtain. These results are applied to the case of linear and equal holding,costs, and we also present a special case where the above results extend to more than two queues.

Many UC-authored scholarly publications are freely available on this site because of the UC Academic Senate's Open Access Policy. Let us know how this access is important for you.

Main Content
Current View