In this paper we study an optimal server allocation problem, where a single server is shared among multiple queues based on the queue backlog information. Due to the physical nature of the system this information is delayed, in that when the allocation decision is made, the server only has the backlog information from an earlier time. Queues have different arrival processes as well as different buffering/holding costs. The objective is to minimize the expected total discounted holding cost over a finite or infinite horizon. We introduce an index policy where the index of a queue is a function of the state of the queue. Our primary interest is to characterize conditions under which this index policy is optimal. We present a fairly general method bounding the reward of serving one queue instead of another. Using this result, sufficient conditions on the optimality of the index policy can be derived for a variety of arrival processes and packet holding costs. These conditions are in general in the form of sufficient separation among indices, and they characterize the part of the state space where the index policy is optimal. We provide examples and derive the indices and illustrate the region where the index policy is optimal.

In this correspondence, we consider the problem of delay optimal rate allocation in a (potentially asymmetric) multiaccess channel. The rate feasibility region of such a network is well studied and is shown to be of a polymatroid structure. We consider this problem with unsaturated sources, i.e., jobs arrive at sources at random times and the source has the possibility of being empty. In such a setting, all stable rate allocation policies result in a throughput matched with the average arrival rate. Hence, we are interested in rate allocation policies that minimize expected delay in the system. In this correspondence, we show that a policy of threshold type is optimal in minimizing the average queueing delay. We study the average delay criterion as the limit of an infinite-horizon discounted cost function when the discount factor approaches 1.

In this paper we study optimal transmission strategies in wireless ad-hoc networks using directional antennas. Each node is capable of adjusting its transmission rate as well as its transmission and reception beam-widths. We explore the different tradeoffs involved in optimizing the performance. Specifically we look at the problem of optimally allocating the transmission rate given specific transmission and reception beam-widths. We then use those results to find the optimum beam-widths for maximizing the average throughput-distance. We illustrate this two stage optimization algorithm by numerical examples. We show that even when the transmission rate is chosen optimally, a bad choice of beam-width can degrade the performance by over 50%.

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.

We study the optimality of an index policy for a bandwidth allocation problem, where a single server is allocated among N queues in a slotted system based on the queue backlog information. Due to the physical nature of the system this information is delayed, in that when the allocation decision is made, the server only has the backlog information from an earlier time. This results in imperfect and partial state observation. Queues have Bernoulli arrival processes with different probabilities of arrival, as well as different buffering/holding costs to differentiate heterogeneous classes of traffic/service. The objective is to minimize the expected total discounted holding cost over a finite or infinite horizon. We introduce an index policy with indices defined as functions of the state of a queue. We first show that when the state of the system is away from the boundary, i.e., no empty queues, the index policy is optimal. When there are empty queues, we show that under sufficient separation of the indices the index policy is still optimal. We show by example that if the separation does not hold, the index policy is not necessarily optimal. We then formulate the optimal bandwidth allocation as a restless bandit problem and show under what conditions the index policy calculated using Whittle's heuristics, which in general is only asymptotically optimal, is optimal for the finite case.

In this paper we present a Markov chain for TCP congestion avoidance phase. With this model we are able to analyze congestion window behavior as a discrete-time stochastic process and distinguish between window transient period and steady state. Using this result we are able to obtain more accurate estimate of TCP latency over lossy links compared to existing models. We then simplify the proposed model and show that the transient period evolves with an exponential rate. Our results are validated using NS2 simulation and show significant improvement in latency estimate for a wide range of file sizes.