A New Competitive Ratio for Network Applications with Hard Performance Guarantee

Abstract

Online algorithms are used to solve the problems which need to make decisions without future knowledge. Competitive ratio is used to evaluate the performance of an online algorithm. This ratio is the worst-case ratio between the performance of the online algorithm and the offline optimal algorithm. However, the competitive ratios in many current studies are relatively low and thus cannot satisfy the need of the customers in practical applications. To provide a better service, a practice for service provider is to add more redundancy to the system. Thus we have a new problem which is to quantify the relation between the amount of increased redundancy and the system performance.

In this dissertation, to address the problem that the competitive ratio is not satisfactory, we ask the question: How much redundancy should be increased to fulfill certain performance guarantee? Based on this question, we will define a new competitive ratio showing the relation between the system redundancy and performance of online algorithm compared to offline algorithm. We will study three applications in network applications. We propose online algorithms to solve the problems and study the competitive ratio. To evaluate the performances, we further study the optimal online algorithms and some other commonly used algorithms as comparison.

We first study the application of online scheduling for delay-constrained mobile offloading. WiFi offloading, where mobile users opportunistically obtain data through WiFi rather than through cellular networks, is a promising technique to greatly improve spectrum efficiency and reduce cellular network congestion. We consider a system where the service provider deploys multiple WiFi hotspots to offload mobile traffic with unpredictable mobile users’ movements. Then we study online job allocation with hard allocation ratio requirement. We consider that jobs of various types arrive in some unpredictable pattern and the system is required to allocate a certain ratio of jobs. We then aim to find the minimum capacity needed to meet a given allocation ratio requirement. Third, we study online routing in multi-hop network with end-to-end deadline. We propose reliable online algorithms to schedule packets with unpredictable arriving information and stringent end-to-end deadline in the network.