Thumbnail
Access Restriction
Open

Author Ehsan, Navid ♦ Liu, Mingyan
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Optimal Bandwidth Allocation ♦ Delay Channel ♦ Single Slot ♦ Stochastic Optimal Control ♦ Index Term Convexity ♦ Optimal Policy ♦ Satellite Communication ♦ Special Case ♦ Value Function ♦ Queue System ♦ Queue Backlog Information ♦ Time Slot ♦ Arbitrary Arrival Process ♦ Optimal Resource Bandwidth Allocation ♦ Total Number ♦ Equal Holding Cost ♦ Slot Reduces ♦ Packet Backlog ♦ State Observation ♦ Optimal Allocation Strategy ♦ Infinite Horizon ♦ Allocation Decision ♦ Previous Allocation ♦ Time-division Multiple-access Schedule ♦ Threshold Type
Abstract 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 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. Index Terms—Convexity, delayed state observation, optimal resource/bandwidth allocation, satellite communication, stochastic optimal control, superconvexity, supermodularity. I.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study