R. Leelahakriengkrai, R. Agrawal, `` Scheduling
in Multimedia DS-CDMA Wireless Networks,'' Technical Report ECE-99-3,
ECE Dept., University of Wisconsin - Madison, July 1999.
R. Agrawal, A. M.
Makowski, P.
Nain, `` On a Reduced Load Equivalence for Fluid
Queues Under Subexponentiality,'' Technical Report ECE-98-3, ECE Dept.,
University of Wisconsin - Madison, June 1998. To appear in QUESTA.
R. Agrawal, F.
Baccelli, R. Rajan, `` An Algebra for Queueing Networks
with Time Varying Service and its application to the analysis of integrated
service networks,'' Technical Report ECE-98-2, ECE Dept., University
of Wisconsin - Madison, May 1998. (Also INRIA
Report 3435.)
R. Agrawal, R. L. Cruz,
C. Okino, R. Rajan, `` Performance Bounds for Flow
Control Protocols,'' IEEE Transactions on Networking.
Vol. 7, No. 3, pp. 310-323, June 1999.
R. S. Pazhyannur and R. Agrawal, `` Rate Based Flow
Control with Delayed Feedback in Integrated Services Networks,'' Technical
Report ECE-97-4, ECE Dept., University of Wisconsin - Madison, July 1997.
R. Agrawal, R. Rajan, ``
Performance Bounds for Guaranteed and Adaptive Services,'' Research
Report RC 20649 (91385) 12/5/96, Computer Science/Mathematics, IBM Research
Division, T. J. Watson Research Center, Yorktown Heights, NY, December
1996.
R. Rajan, R. Agrawal, `` Synchronous Constrained
Fluid Systems,'' Research Report RC 20313 (89735) 12/12/95, Computer
Science/Mathematics, IBM Research Division, T. J. Watson Research Center,
Yorktown Heights, NY, December 1995.
R. Rajan, R. Agrawal, ``Concavity of Queueing Systems with NBU Service
Times.'' Advances in Applied Probability, Vol. 30, pp. 551-567,
1998.
For a more detailed version see
Technical Report
ECE-94-2, ECE Dept., University of Wisconsin - Madison, February 1994.
R. Agrawal, R. Mansharamani, M. Vernon, `` Response
Time Bounds for Parallel Processor Allocation Policies.'' Technical
Report 1152, CS Dept., University of Wisconsin - Madison, June 1993.
R. Rajan, R. Agrawal, ``Server Allocation and Routing in Homogeneous
Queues with Switching Penalties.'' IEEE Transactions on Automatic Control,
Vol. 41, No. 11, pp. 1657-1661, November 1996.
Abstract: This paper considers a multiclass routing
and server allocation problem in a queueing system of multiple stations
in parallel with penalties for switching the server between stations. We
proceed by dynamically ranking the queues, so that, if all arrivals ceased,
switches of the server between queues would be maximally delayed by serving
queues in order of rank. The main result of this paper shows that we may
improve any policy by constructing a greedy version that routes
arriving customers to the queue of highest acceptable rank, and allocates
the server to the queue of highest rank whenever it switches. We also establish
analogous results for a variant of the problem that encourages fairness
in server allocation by restricting attention to pseudo-cyclic policies
which visit each queue periodically.
R. Agrawal, ``Sample Mean Based Index Policies with O(log n) Regret
for the Multi-Armed Bandit Problem,'' Advances in Applied Probability,
Vol. 27, No. 4, pp. 1054-1078, December 1995.
Abstract: We consider a non-Bayesian infinite horizon
version of the multi-armed bandit problem with the objective of designing
simple policies whose regret increases slowly with time. In their
seminal work on this problem, Lai and Robbins had obtained a O(log n) lower
bound on the regret with a constant that depends on the Kullback- Leibler
number. They also constructed policies for some specific families of probability
distributions (including exponential families) that achieved the lower
bound. In this paper we construct index policies that depend on the rewards
from each arm only through their sample mean. These policies are computationally
much simpler and are also applicable much more generally. They achieve
a O(log n) regret with a constant that is also based on the Kullback-Leibler
number. This constant turns out to be optimal for one-parameter exponential
families; however, in general it is derived from the optimal one via a
``contraction'' principle. Our results rely entirely on a few key lemmas
from the theory of large deviations.
R. Agrawal, ``The Continuum-Armed Bandit Problem,'' SIAM J. Control
and Optimization, Vol.33, No. 6, pp. 1926-1951, November 1995.
Abstract: In this paper we consider the multi-armed
bandit problem where the arms are chosen from a subset of the real line
and the mean rewards are assumed to be a continuous function of the arms.
The problem with an infinite number of arms is much more difficult than
the usual one with a finite number of arms because the built-in learning
task is now infinite dimensional. We devise a kernel estimator based learning
scheme for the mean reward as a function of the arms. Using this learning
scheme, we construct a class of certainty equivalence control with forcing
schemes and derive asymptotic upper bounds on their learning loss. To the
best of our knowledge these bounds are the strongest rates yet available.
Moreover, they are stronger than the o(n) required for optimality with
respect to the average-cost-per-unit-time criterion.
R. S. Pazhyannur and R. Agrawal, ``Feedback Based Flow Control of High-Speed
Networks,'' IEEE Journal on Selected Areas in Communications, Special
Issue on Advances in the Fundamentals of Networking, Vol. 13, No. 7, pp.
1252-1266, September 1995.
Abstract: We consider a system comprising of a single
bottleneck switch/node that is fed by N independent Markov modulated
fluid sources. There is a fixed propagation delay incurred by the traffic
between these sources and the switch. We assume that the switch sends periodic
feedback in the form of a single congestion indicator bit. This feedback
also incurs a fixed propagation delay in reaching the sources. Upon reaching
the sources (or the access controllers associated with the sources), this
congestion indicator bit is used to choose between two rates for the excess
traffic, high or low, possibly depending on the state of that source. The
switch employs a threshold mechanism based on its buffer level to discard
excess traffic. We show that the stationary distribution of this system
satisfies a set of first-order linear differential equations along with
a set of split boundary conditions. We obtain an explicit solution to these
using spectral decomposition. To this end we investigate the related eigenvalue
problem. Based on these results we investigate the role of delayed feedback
vis-a-vis various certain time-constants and traffic parameters associated
with the system. In particular, we identify conditions under which the
feedback scheme offers significant improvement over the open-loop scheme.
R. Rajan, R. Agrawal, ``Second-Order Properties of Families of Discrete-Event
Systems,'' IEEE Transactions on Automatic Control, Vol. 40, No.
2, pp. 261-271, February 1995.
Abstract: We consider discrete event systems (DES)
whose logical component is characterized by a constraint set, and
whose temporal mechanism involves synchronization of the clock sequence
with a master clock. We are interested in determining sufficient conditions
on the constraint sets of a family of such synchronous DES that
ensure that the event counting process of one system dominates the convex
combination of the event counting processes of a collection of systems.
Our point of departure is a result due to Glasserman and Yao, which establishes
a sufficient condition based on characteristic functions. First
we show that the characteristic function condition is equivalent to a simpler
condition on the score spaces themselves. However, as both of these (equivalent)
conditions are rather strong, we introduce coevality to obtain weaker
sufficient conditions. To demonstrate the scope of these two results, we
prove the near-concavity of the throughput in various system parameters,
for min-linearly constrained DES. This not only covers various known
concavity results for tandems, cycles, and fork-join networks of stations
with general blocking and starvation, but also establishes new ones for
certain classes of networks which involve splitting and merging of traffic
streams. These results are finally extended to the class of generalized
min-linearly constrained DES.
R. Rajan, R. Agrawal, ``Cyclic Networks with General Blocking and Starvation,''
Queueing
Systems -- Theory and Applications, pp.99-136, February 1994.
Abstract: We introduce general starvation and
consider cyclic networks with general blocking and starvation (GBS).
The mechanism of general blocking allows the server to process a limited
number of jobs when the buffer downstream is full, and that of general
starvation allows the server to perform a limited number of services in
anticipation of jobs that are yet to arrive. The two main goals of this
paper are to investigate how the throughput of cyclic GBS networks is affected
by varying (1) the total number of jobs J, and (2) the buffer allocation
k
= (k_1, ... , k_m) subject to a fixed total buffer capacity
K
= k_1 + ... + k_m. In particular, we obtain sufficient conditions for
the throughput to be symmetric in J and to be maximized when
J=K/2.
We also show that the equal buffer allocation is optimal under the two
regimes of light or heavy usage. In order to establish these results, we
obtain several intermediate structural properties of the throughput, using
duality, reversibility, and concavity, which are of independent interest.