Parallel scheduling for wireless networks
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 both power (rate) and codes for every user. This gives rise to a new class of 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 which is an unusual technique we bring to these problems. 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.
- L. Becchetti, S. N. Diggavi, S. Leonardi, A. Marchetti-Spaccamela, S. Muthukrishnan, T. Nandagopal, and A. Vitaletti, "Downlink Scheduling for Multirate Wireless Networks," Networks, vol. 45, iss. 1, pp. 9-22, 2005.Download: dimacs.pdfAbstract:This studied the online scheduling problem of allocating time or frequency slots to multiple users in a wireless broadcast channel. The study was from a CS algorithms viewpoint, with criteria such as delay (average/maximal) and stretch (relative delay). We gave a resource-augmented competitive analysis of many scheduling algorithms, and demonstrated that a small amount of overprovisioning (resource-augmentation) will make the scheduling algorithms competitive to the off-line optimal, even for adversarial demand inputs.
- L.Becchetti, S. N. Diggavi, S. Leonardi, A. Marchetti-Spaccamela, S. Muthukrishnan, T. Nandagopal, and A.Vitaletti, "Parallel scheduling problems in next generation wireless networks," in Proc. ACM Symp. Par. Alg. and Arch. (SPAA), 2002, pp. 238-247.