Deng, Han (2017-08). A New Competitive Ratio for Network Applications with Hard Performance Guarantee. Doctoral Dissertation. Thesis uri icon

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.
  • 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.

publication date

  • August 2017