Multicast server selection: problems, complexity, and solutions
Tóm tắt
We formulate and investigate fundamental problems that arise when multicast servers, that deliver content to multiple clients simultaneously, are replicated to enhance scalability and performance. Our study consists of two parts. First, we consider the problem under the assumption that the multicast clients are static for the duration of the multicast content distribution session. In this context, we examine two models for server behavior: fixed-rate servers, which transmit at a constant rate, and rate-adaptive servers, which adapt their transmission rate based on network conditions and/or feedback from clients. In both cases, we show that general versions of the client assignment problems are NP-hard. We then develop and evaluate efficient algorithms for interesting special cases, as well as heuristics for general cases. Second, we consider the case in which the set of clients changes dynamically during the multicast content distribution session. We again consider both fixed-rate and rate-adaptive servers. We formulate the problem as a Markov decision process, capturing the costs associated with trees, as well as the transition costs to dynamically change the trees. We use the properties of optimal solutions for small examples to develop a set of dynamic server selection heuristics.
Từ khóa
#Network servers #Feedback #Costs #Web server #Streaming media #Context modeling #Multimedia communication #Radio broadcasting #TV broadcasting #ScalabilityTài liệu tham khảo
hao, 2001, supporting server selection in differentiated service networks, Proc IEEE INFOCOM 2001
katabi, 2000, a framework for global ip-anycast (gia), Proc ACM SIGCOMM 2000, 1
10.1109/INFCOM.1992.263559
10.1109/INFCOM.1998.662930
10.1109/90.851976
10.1145/190809.190320
cheung, 1996, on the use of destination set grouping to improve fairness in multicast video distribution, Proc INFOCOM 96, 10.1109/INFCOM.1996.493348
10.1145/277851.277913
fei, 2001, optimizing the allocation of clients to replicated rate-adaptive multicast servers, Proc SPIE Int Symp Scalability and Traffic Control in IP Networks
10.1137/0116001
10.1109/90.650139
10.1145/192593.192614
howard, 1960, Dynamic Programming and Markov Processes
myers, 1999, performance characteristics of mirror servers on the internet, Proc INFOCOM 99, 10.1109/INFCOM.1999.749296
10.1109/65.768488
10.1109/INFCOM.1997.631117
seshan, 1997, spand: shared passive network performance discovery, Proc 1st Usenix Symp Internet Technologies and Systems (USITS 97)
10.1109/65.681926
10.1109/90.865074
10.1109/49.564128
10.1007/BF00288961
10.1109/35.587723
garey, 1979, Computers and Intractability A Guide to the Theory of NP-Completeness
10.1145/78952.78953
fei, 2000, Selection of replicated adaptive multicast servers
10.1109/INFCOM.1993.253246
10.1109/49.12889