The distributed utility model applied to optimal admission control and QoS adaptation in multimedia systems and enterprise networks

Allocation and reservation of resources, such as CPU cycles and I/O bandwidth of multimedia servers and link bandwidth in the network, is essential to ensure Quality of Service (QoS) of multimedia services delivered over the Internet. We propose a Distributed Multimedia Server System (DMSS) configured out of a collection of networked multimedia servers where multimedia data are partitioned and replicated among the servers. We also introduce Utility Model-Distributed (UM-D), the distributed version of the Utility Model, for admission control and QoS adaptation of multimedia sessions to maximize revenue from multimedia services for the DMSS.; Two control architectures, a centralized and a distributed, have been proposed to solve the admission control problem formalized by the UM-D. In the centralized broker architecture, the admission control in a DMSS can be mapped to the Multidimensional Multiple-choice Knapsack Problem (MMKP), a variant of the classical 0–1 Knapsack Problem. An exact solution of MMKP, an NP-hard problem, is not applicable for the on line admission control problem in the DMSS. We therefore developed three new heuristics, M-HEU, I-HEU and C-HEU for solving the MMKP for on-line real-time admission control and QoS adaptation. We present a qualitative analysis of the performance of these heuristics to solve admission control problems based on the worst-case complexity analysis and the experimental results from different sized data sets.; The fully distributed admission control problem in a DMSS, on the other hand, maps to the Multidimensional Multiple-choice Multi Knapsack Problem (MMMKP), a new variant of the Knapsack Problem. We have developed D-HEU and A-HEU, two new distributed heuristics to solve the MMMKP. D-HEU requires a large number of messages and it is not suitable for a on line admission controller. A-HEU finds the solution with fewer messages but achieves less optimality than D-HEU.; We have applied the admission control strategy described in the UM-D to the set of Media Server Farms providing streaming videos to users. The performance of different heuristics in the broker has been discussed using the simulation results. We have also shown application of UM-D to Distributed SLA (Service Level Agreement) Controllers in Enterprise Networks. Simulation results and qualitative comparison of different heuristics are also provided.