1st International ICST Workshop on Tools for solving Structured Markov Chains

Research Article

Approximating Optimal Load Balancing Policy in Discriminatory Processor Sharing Systems

Download177 downloads
  • @INPROCEEDINGS{10.4108/smctools.2007.1929,
        author={Juha Leino},
        title={Approximating Optimal Load Balancing Policy in Discriminatory Processor Sharing Systems},
        proceedings={1st International ICST Workshop on Tools for solving Structured Markov Chains},
        proceedings_a={SMCTOOLS},
        year={2010},
        month={5},
        keywords={Approximation discriminatory processor sharing Markov decision processes queue length load balancing},
        doi={10.4108/smctools.2007.1929}
    }
    
  • Juha Leino
    Year: 2010
    Approximating Optimal Load Balancing Policy in Discriminatory Processor Sharing Systems
    SMCTOOLS
    ICST
    DOI: 10.4108/smctools.2007.1929
Juha Leino1,*
  • 1: Networking Laboratory TKK Helsinki University of Technology P.O. Box 3000, FI-02015 TKK, Finland
*Contact email: Juha.Leino@netlab.tkk.fi

Abstract

In this paper, we study load balancing between multiple discriminatory processor sharing queues. Arriving customers are divided between the queues according to a load balancing policy. Such models have numerous applications in many fields, e.g., in computer and telecommunication systems. We use a method called value extrapolation to approximate the performance of different heuristic load balancing policies. Policy iteration is used jointly with value extrapolation to approximate the performance of the optimal policy. We provide numerical results suggesting that a policy obtained with a well-chosen initial policy and one iteration round can outperform the heuristic policies. If the initial policy is static, the relative values of the states can be derived using prior results concerning a single DPS queue, hence the first iteration round can be conducted without significant computations, thus the first policy iteration policies may prove to be useful in practical applications.