Optimal Allocation of Clients to Replicated Multicast Servers
Ammar, Mostafa H. (Mostafa Hamed)
Zegura, Ellen W.
MetadataShow full item record
Server replication is an approach that is often used to improve the scalability of a service. One of the important factors in the efficient utilization of replicated servers is the ability to direct client requests to the `best" server, according to some optimality criteria. Recently, there have been several proposals for multicast services in which a server delivers information to multiple clients simultaneously. Such proposals include multicasting of web content, multicast-based video services (on-demand and pay-per-view style services), multicasting of database content and broadcast disks. The goal of many of these proposals is to use multicast to enhance the ability of the service to handle a large number of clients economically. Multicast servers may be replicated for several reasons: to distribute the load among on-demand multicast servers, to balance the `feedback" load on the servers or on entities along the multicast tree from the servers, or to select the server that is at the root of the `best" multicast routing tree. In this paper we first give a definition of the static multicast server selection problem, in which we assume a set of static clients and multicast servers and consider how one might produce an optimalallocation of the clients to the servers. We propose a transformation method for deriving multicast server selection algorithms from the traditional multicast routing algorithms. To investigate the dynamic behavior of client join and leave and the cost incurred during the process, we next define the dynamic multicast server selection problem, in which the potential clients join and leave the multicast session dynamically, and the goal is to produce an optimal allocation of clients to servers with an emphasis on how this allocation behaves over time. We formulate the problem as a Markovian Decision Process (MDP) and analyze the tradeoff between the cost of the multicast tree(s) and the transition cost of establishing and removing links from the tree(s). We also explore the effect of join/leave frequency on optimal policy. Our analysis leads to two heuristics which we use to propose a selection algorithm. The algorithm uses a very simple join and leave strategy yet still can generate low cost trees. Our simulation compares the performance of our proposed algorithm with various other multicast server selection algorithms.