Online Computations in Scheduling and Network Applications

Abstract

In this work we design and analyze algorithms for problems whose input arrives or alters over time. This is in contrast to many problem scenarios where the information needed for decision making is available from the very beginning. In these situations, the complete solution is produced altogether. Due to the dynamic nature of many real world applications, it is necessary to consider algorithms that adapt to the ever changing environment, augmenting and adjusting solutions as time progresses. We concentrate on problems that arise in scheduling and network applications.

One traditional approach for online computation is competitive analysis. Competitive analysis compares the performance of the online algorithm with that of the offline algorithm, over all possible input sequences. The goal is to design algorithms that optimize over the worst possible input sequence. We study two problems under this framework. We first extend the traditional paging model to allow reordering of the requests, which is motivated by web caching applications. For this new model, we provide a complete study of the upper and lower bounds on the performance of any online algorithm (deterministic or randomized) against various optimal offline algorithms. Next we study the problem of queue management in Quality of Service (QoS) networks. We provide matching upper and lower bounds for three different queueing policies, improving upon the previous known results.

While competitive analysis assumes the input data develops piece by piece, in some applications the input constantly evolves over time. This phenomenon is evident in ad-hoc wireless mobile networks. The algorithms thus need to adjust or modify the solutions as the input evolves. In these situations, there is a tradeoff between the quality of the solutions maintained and the number of changes occurs in the solutions.

We first study the problem of clustering nodes in a mobile network. We show asymptotic tight bounds on the tradeoffs between the two measures. Next we show how the clustering algorithm can be used as a subroutine to maintain routing graphs in mobile networks. We provide theoretical bounds as well as simulation results on the length of the actual routing paths for pairwise communications.

Back to publications
Back to previous page