Technischer Bericht TR-1996-03

Hagin, Alexander; Dermler, Gabriel; Rothermel, Kurt: Problem Formulations, Models and Algorithms for Mapping Distributed Multimedia Applications to Distributed Computer Systems.
Universität Stuttgart, Fakultät Informatik, Fakultätsbericht Nr. 1996/03.
66 Seiten, englisch.
CR-Klassif.C.2.4 (Distributed Systems)
C.4 (Performance of Systems)
G.1.6 (Numerical Analysis Optimization)
G.2.2 (Graph Theory)
I.6 (Simulation and Modeling)
KeywordsMapping; Distributed Multimedia Application; Distributed System

In the report, the problem of optimal allocation of Distributed Multimedia Applications (DMA) into Distributed Computer Systems (DCS) is examined. We are given precedence graphs representing topologies of the DMA and data streams between components of DMA. Nodes and arcs of the graphs are weighted by the computational and communication resources needed to meet quality of service requirements of DMA. A special-purpose precedence graph model is proposed to present the structure of DCS including computers, virtual channel connections and communication resources of DCS over which the channels are routed. Nodes and links of the graph are weighted by the computational resources and capacities of communication resources available to mapped DMA.

An approach, based on the solving two kinds of the mapping problem, is proposed. The first one is formulated as a nonlinear integer programming problem with cost function under constraints on DCS resources available to mapped DMA. If the first one has not an acceptable solution, then other problem, formulated as minimax nonlinear integer one to find the DMA location into the DCS with minimum DCS resource gap, is solved. To solve both problems, effective algorithms based on the branch-bound method are proposed. Computational efficiency of the algorithms is examined and illustrated by numerical examples

Volltext und
andere Links
HTML (aus PostScript generiert)
Abteilung(en)Universität Stuttgart, Institut für Parallele und Verteilte Höchstleistungsrechner, Verteilte Systeme
Eingabedatum23. April 1996
   Publ. Abteilung   Publ. Institut   Publ. Informatik