Scheduling Data Delivery in Wireless Servers

Shanmugauelayut Muthukrishnan, AT&T Labs-Research

BACKGROUND: There is increasing wireless support for data networks with the abundance of mobile clients (palm/hand-held computers, smart devices) as well as the rise in wireless “data-centric” applications (traffic information systems, stock/sports tickers and wireless internet access). This requires support infrastructure via data servers such as portable kiosks, infostations, etc. for timely and efficient delivery of information.

QUESTIONS: We focus on efficient scheduling of data delivery to improve responsiveness of wireless data servers. What is the measure of responsiveness for data delivery? Traditional measures are related to response time, but stretch (slowdown) related measures may be more relevant. What is the mechanism for data delivery? Both unicasting and broadcasting are relevant. What is the suitable user request model, such as (dis)allowing multiple requests simultaneously, single or multiple channel, etc.? Many different scheduling problems arise – some are well known in the classical scheduling literature, some are variations thereof, others are quite novel.

TALK: We will present new online and offline algorithms for scheduling problems in this context, mainly focused on the stretch measure for scheduling data delivery. This will be the bulk of the talk. We will also present experimental results comparing the different algorithms on delivering web data. Many open issues need to be understood before an ultimate solution emerges for data delivery in wireless servers. We will also present a list of open scheduling problems that are likely to be very relevant for data delivery in wireless servers.