We examine the configuration management problem for distributed multimedia applications (DMA) including such issues as quality of service (QoS) specification, QoS negotiation, placement of a DMA in a distributed computer system (DCS), and resource reservation to support requested QoS. An algorithm for the DMA configuration management is proposed that takes into account all mentioned above issues and is based on the XNRP protocol developed earlier to negotiate QoS and to reserve needed resources.

We examine in detail the problem of assigning a DMA to a DCS in a cost optimized way, where the DMA and the DCS are represented by weighted oriented graphs. We present two efficient heuristic algorithms to solve the assignment problem. The first one, a clustering algorithm, finds a suboptimal DMA placement in the DCS minimizing the communication cost. The second one, the so-called initial assignment improving algorithm (SIGMA), reassigns the DMA in the DCS minimizing the total computational and communication cost.

In comparison with other approaches, both algorithms take into account the heterogeneity of the DMA and DCS as well as different kinds of constraints and behavior characteristics that are essential to distributed multimedia systems. To estimate the accuracy of the proposed algorithm, branch-and-bound-type algorithms with different objective functions have been designed. The time complexity and accuracy evaluation based on a great variety of experiments conducted for randomly generated DMA and DCS graphs is very encouraging, since, at significantly lower execution time, we obtained allocations with cost very close to the optimal one.