QoS Support for Streaming Media using a Multimedia Server Cluster
K. Ratakonda, Deepak S. Turaga, Junwen Lai · 2006
We develop algorithms to provide Quality of Service (QoS) support for prioritized, bandwidth-adaptive and fair media streaming using a multimedia server cluster. We formulate the underlying related problems of prioritized client admission control, redirection to appropriate streaming server, adaptive client quality control, and server load-balancing as one combined optimization. This optimization corresponds to solving a Multiple Choice Multiple Knapsack Problem, which is in general NP hard. By partitioning this optimization into two separate related optimizations we can design several low- complexity algorithms to provide exact and approximate solutions. We select a log-linear utility function that maintains differentiability and captures the video quality to measure the derived client and system benefit. We provide bounds on the performance of these algorithms, and examine the system time evolution in terms of the number of clients supported and QoS provided to each client, over realistic simulation scenarios. which may be determined in terms the underlying group (administrator, user, executive) that the client belongs to etc. Hence clients with higher priority should receive higher QoS. However, given the long duration of client connections it is not always possible to guarantee fairness, as low-priority clients may arrive into the system during periods of light load, while high-priority clients may arrive during periods of heavy load. Reservation based schemes avoid this problem, but are very restrictive, especially under light server load. Instead, in our streaming system, we provide clients the best QoS possible given the underlying load conditions and client priorities. We then allow for the multimedia quality to vary during the client connection, i.e., when a new client with high priority enters the system, the quality received by low-priority clients may be reduced, if the available resources are not enough. Dynamic variation of multimedia quality in response to bandwidth variations or resource constraints has been extensively examined in prior research, and several schemes using scalable video coding (6) or stream switching (5) have been proposed. We consider a server cluster consisting of servers with different resource capacities serving clients with different priorities and QoS requirements. We design algorithms that dynamically determine which server a client request is directed to, as well as the particular QoS, in terms of the video representation that is served to the client. At the same time, we also determine whether existing client connections need to be modified to accommodate the new client request. We consider two different streaming scenarios: (a) the bandwidth of existing client connections may be modified when a new client enters the system, and (b) the bandwidth may be modified, and client connections may be transferred across servers to improve overall server utilization. The second system provides more flexibility to utilize resources efficiently, however switching across servers may lead to quality disruptions. We formulate this resource allocation problem as a Multiple Choice Multiple Knapsack Problem, and propose a sub-optimal solution by decomposing this into a Multiple Choice Knapsack Problem followed by a Multiple Knapsack Problem. We design low complexity algorithms to solve these sub-problems. We evaluate the performance of our streaming system in terms of client QoS (average bandwidth received by a client, number of variations in quality etc.) and system performance (number of clients supported).