Algorithmic Issues in Wireless Data Delivery

Outline of the Talk

TALK in three parts:

1. Setting the new problems that araise with the use of wireless medium yields new problems
2. Presenting some solutions for one of them: the Data Broadcast Problem
3. Open issues

INTRODUCTION: SETTING THE PROBLEM

Data delivery with a wireless medium

• Traditional data delivery: clients send requests for (or pull) pages of information from a server
• Is this solution relevant if a wireless (Cellular, Satellite, Radio...) or shared access medium (Cable TV, Ethernet,...) is used?
• Some examples: Satelitte Internet access, Cable TV,...
• Since every client can listen at the same time, clients can merge their requests to save bandwidth!
• New solutions have to be designed: compare with the unicast case where the Shortest Remaining Time was the best algorithm.
• Is a FIFO queue of the requests satisfying?
• If the number of clients is small, it can work fine.
• If the number of clients is huge, first the server is overloaded with the treatment of the requests and second the information are inefficiently broadcast, in an order that doesnot take into account their relative popularities. (see [AAFZ95,FZ98])
• Better to find a good broadcast schedule of the pages of information taking into account of their relative popularities. The users do not send requests but connect until the page they are interested in is broadcast; the server is said to push the informations. This is called the Data Broadcast Problem.

Modeling the Data Broadcast Problem

• Basic definition:
• Input: A set of pages (or messages, or information) to broadcast to the users
• Broadcast of the pages may be preempted or not, depending on the target applications (e.g. Radio vs TV).
• The server can broadcast on a single or several channels.
• Modelling the users:
• The large scale case (Sattelite, Customized newspapers on the Internet,...):
• The distribution of the interests of the users over the pages available (or the popularities of the pages) is used as the input to compute the schedule.
• User request arrivals are modeled as a Poisson Process.
• The small number of clients case:
• no hypothesis on the requests.
• on-line or off-line algorithms.
• Modelling the broadcast of the server
• A lot of different models have been proposed. Some of them follow:
• The Broadcast Disk (See Acharya, Franklin, Zdonik [Ach98,...]) are several disks turning at different speeds broadcasting some of the pages in Round Robin order. The resulting schedule is obtained by interleaving the resulting streams. The disks with the most popular pages turn faster than the one with less popular pages.
• The general schedule model (See Ammar and Wong [AW85]; Bar-Noy, Bhatia, Noar and Schieber [BNBNS98]; Kenyon, Schabanel, Young [KS99,...]) where the server broadcasts the message according to a given schedule over a fixed number of channels.
• Determining the objective function:
• The maximal response time?
• Relevent for the on-request case (See Bartal and Muthukrishnan [BM00])
• This is irrelevant for the push-case, because the optimal solution consists then in scheduling the pages in Round Robin order, regarless of their relative popularities!
• The (average or) expected response time: the expected response time to a random user request.
• Well studied for the push-case:
• It is NP-Hard.
• Work initiated with a study of Ammar and Wong in 1985 and will be discuss in the second part of the talk.
• An open interresting question for the on-request broadcast case
• Note that we can simulate Poisson arrival requests and then this case include the push case.
• Should we take into account the length of the messages?
• Is it the same to wait 2 sec. for a message of transmission time 1 sec. and 1 min.?
• Wouldn't it be better to take into account the stretch of the messages instead of the delay of their transmission?
• Minimize the stretch, that is to say the ratio of the total response time over the length of the message: waiting 2 sec. for a message of length 1 sec. is then counted the same as waiting 2 min. for a message of length 1 min.
• This appears to be a relevant measure.
• Minimizing the expected stretch is open for the broadcast on-request case. For the push based case, this is just a slight modification of the objective function.
• Shouldn't we also try to save the energy spent by the client devices?
• Since mid 90's, client are using mobile device to connect to wireless channels. The problem of the data broadcast protocole is that user have to listen to the channel until their message is broadcast.
• A solution is that the server broadcasts from time to time an index of the next broadcasts. The user use this index to disconnect and reconnect at the right time.
• The aim is then to minimize the expected response time as well as the tuning time. This problem was formally settled by Imielinski, Viswanathan, and Badrinath [IVB94a] in 1994 and recently some general approximation was provided by Khanna and Liberatore [KL98] in 1998.
• What about Cache issues?
• Thanks to miniaturization of the electronic deive, the mobile device are getting more and more complex and now provide a huge memory (e.g. Palm Pilot). The question of client cache memory managment is then relevant and could decrease drastically the expected response time, thanks to prefetching for instance.
• Client cache managment in the Data Broadcast setting is very different from the usual computer setting:
• The cost of a page miss depends on the time of the request and on the upcoming schedule: the longer with have to wait for the next broadcast of the page, the more it costs.
• Usual eviction strategies fail: LRU (Least recently used) is irrelevant, because we could evict a page that is very rarely broadcast. A better strategy would on the contrary consists in evicting a page which is broadcast very often and that won't cost a lot later (See the work of Acharya, 1998 [Ach98,...]).
• Furthermore, prefetching is very crucial and allow to increase considerably the performance, since it is free to download the page which is currently broadcast.
• This problem seems very challenging:
• Only very special case have been studied. One formal study by Khanna and Zhou, 1998 [KZ98], shows in particular that without any hypothesis on the requests of the user, only big approximation ratio can be achieved by a polynomial time cache managment unit.
• As far as I know, no one tried yet to optimize at the same time the broadcast schedule and the cache managment algorithm.

SECOND PART: SCHEDULING TO MINIMIZE EXPECTED WAITING TIME WITH A LARGE NUMBER OF USERS

Defining the problem: we consider the push based case.

• Input: A set of m pages M₁,...,M_m with their popularities p₁,...,p_m among the users.
• Users: The user connect uniformly at a random time (according to some Poisson process) and request the page M_i with probability p_i.
• Aim: Find an infinite schedule of the pages over the wireless channels that minimizes the expected wait of (or expected response time for) the random user.

The case where all the messages have the same length

• The first important step was made by Ammar and Wong, 1985 [AW85], in the case where all the messages have the same length. They propose a good relaxation of the problem that yields a lower bound that provides some indications on the structure of the optimal.
• They remark that if we relax the non-overlaping constraints, the best is to schedule each message Mi regularly every some t_i. And the best t_i's are proportional to the square root of the p_i's. Ex: If page A is requested by 80% of the users and page B by 20%, A should be broadcast twice as much as B.
• They provide a randomized algorithm that realizes a 2-approximation:
• In each time slot, choose the next message M_i to broadcast with probability 1/t_i
• The expected wait for M_i is then ti instead t_i/2 according to the lower bound.
• They also provide a greedy algorithm that was proved later by Bar-Noy, Bhatia, Noar and Schieber [BNBNS98] to be a 2-approximation too (and in fact the derandomization of the randomized one):
• In each time slot, choose the next message M_i to broadcast that maximizes the cumulated wait of the requests arrived.
• After several improvements, Kenyon, Schabanel, and Young [KSY00] propose a PTAS (a algorithm that provides a (1+e)-approximation for any given precision e) for this case based on different improvements:
• They show that we can partition the messages into 3 categories: the Important messages, a set of Large Group of messages with similar popularities, a set of Negligible messages.
• The important messages are optimally broadcast and the large groups of messages are broadcast in some Round Robin way. The negligible message are then inserted from time to time.

The case the messages have different lengths

• Conversely to the case where all the messages have the same length, it is known to be NP-hard.
• Only constant factor approximation are known (Kenyon, Schabanel, 1999 for the non-preemptive case [KS99]; Schabanel 2000 for the preemptive case [Sch00a]).
• The non-uniform length and non-preemptive case is very different from the uniform length case.
• In particular, adding a new broadcast channel can reduce by an arbitrary factor the cost of the schedule (imaging that a very long message delay all the other; we can drastically reduce the wait by broadcastint it on the new channel).
• Only the single channel case has been studied theoretically (Kenyon, Schabanel, 1999 [KS99])
• Preemption helps a lot [Sch00b]:
• Cut the message into packets of size one and schedule the packets. A user is served when it has downloaded all the packets of the message it is interested in.
• Preemption can reduce the cost of the schedule by an arbitrary factor (the broadcast of a very long boring message that can be interrupted to broadcast small important messages).
• So, depending of the application, if preemption can be used, it should be used.

OPEN ISSUES

• Defining the right model:
• Depending on the application, the objective function, the users behavior are different
• Cache managing is widely open
• Data Broadcast:
• Can we handle depencies between the messages? like A then B, A or B,...
• The "Customized Newspaper Problem": Client are interested in downloaded personalized newspaper; there are different type of information, for instance News (N), Weather (W), Traffic (T); 40% are interested in downloading N+W, 50% in N+W+T, 10% in W+T; How should I schedule these 3 pages? This can be seen as a generalization of the preemption case where the messages share packets.

Bibliography