DIMACS TR: 2002-29
Parallel Scheduling Problems in Next Generation Wireless Networks
Authors: L. Becchetti, S. Diggavi, S. Leonardi, A. Marchetti-Spaccamela, S. Muthukrishnan, T. Nandagopal and A. Vitaletti
ABSTRACT
Next generation 3G/4G wireless data networks allow multiple codes (or
channels) to be allocated to a single user, where each code can
support multiple data rates. Providing fine-grained QoS to users in
such networks poses the two dimensional challenge of assigning {\em
both} power (rate) and codes for every user. This gives rise to a new
class of parallel scheduling problems. We abstract general downlink
scheduling problems suitable for proposed next generation wireless
data systems. This includes a communication-theoretic model for
multirate wireless channels. In addition, while conventional focus
has been on throughput maximization, we attempt to optimize the
maximum response time of jobs, which is more suitable for stream of
user requests. We present provable results on the algorithmic
complexity of these scheduling problems. In particular, we are able
to provide very simple, online algorithms for approximating the
optimal maximum response time. This relies on resource augmented
competitive analysis. We also perform an experimental study with
realistic data of channel conditions and user requests to show that
our algorithms are more accurate than our worst case analysis shows,
and they provide fine-grained QoS to users effectively.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-29.ps.gz
DIMACS Home Page