Universität Stuttgart

Fakultät Informatik

I V P R

Fakultät Informatik Institut für Parallele und Verteilte 
Höchstleistungsrechner Universität Stuttgart Breitwiesenstraße 20 - 22 
D-70565 Stuttgart

Foundations for Mapping

of Distributed Multimedia Applications

to Distributed Computer System

Alexander Hagin

Foundations for Mapping

of Distributed Multimedia Applications

to Distributed Computer System

Alexander Hagin

CR-Klassifikation: C.2.4, C.4, G.1.6, G2.2, I.6

Fakultätsbericht 13/1994 Technical Report October 1994

Abstract

Distributed multimedia applications need convenient framework for their 
realiza-

tion in a distributed computer system. This paper deals with the problem 
of mapping

distributed multimedia applications to a distributed computer system. An 
approach

for formalization of this problem as well as a set of abstractions, 
mathematical pro-

gramming formulations, models and solution procedures are proposed.

Distributed multimedia application is represented by one or a set of 
data flow graphs

that specify quality of service and resource requirements of the 
application. Distri-

buted computer system is represented as a relevant directed weighted 
graph with

information about available computer and communication resources. A 
problem of

best placement (from the point of preliminary defined cost criteria) of 
data flow

graphs onto distributed computer system is decided.

2

CONTENTS

1. 
INTRODUCTION..................................................................................................5

2. DATA FLOW GRAPH (DFGraph) of

DISTRIBUTED MULTIMEDIA APPLICATION (DMMApplication).............7

2.1. DFGraph 
topologies........................................................................................ 
7

2.1.1. Basic 
components......................................................................................... 
7

2.1.2. Basic schemes 
............................................................................................. 
7

2.1.3. Centralised and decentralised topologies 
...................................................9

2.1.3.1. Centralised topologies 
...............................................................................9

2.1.3.2. Decentralised topologies 
...........................................................................9

2.2. DFGraph stream parameters 
........................................................................ 
12

3. QUALITY of SERVICE (QoS) REQUIREMENTS of DMMApplications .. 15

3.1. Problem of QoS parameter 
negotiation......................................................... 15

3.2. Relationships for QoS requirements negotiation 
........................................ 18

3.3. Assignment of resource capacity requiremants 
...........................................20

3.4. Stream synchronization parameters for basic schemes of DFGraph .. 
......25

3.4.1. Point-to-point scheme 
.............................................................................. 
25

3.4.1.1. Recovery a regular stream 
..................................................................... 25

3.4.1.2. Recovery an original stream 
.................................................................. 30

3.4.2. Collector scheme 
........................................................................................ 
30

4. MAPPING PROBLEM 
.................................................................................... 
31

4.1. System of methods and models for mapping decision 
................................. 31

4.2. Mapping task statement 
............................................................................... 
33

4.3. Approachs and algorithms for mapping decision 
......................................... 35

5. MODELS for PERFORMABILITY and RELIABILITY EVALUATION of

DISTRIBUTED COMPUTER SYSTEM (DCSystem),

3

its SUBSYSTEM and ELEMENTS 
..................................................................... 36

5.1. Models for computer performance and reliability evaluation 
......................... 36

5.2. Models for evaluation of data stream 
............................................................. 36

5.3. Models for data link performance and reliability evaluation 
......................... 36

5.4. Models for network performance and reliability evaluation 
.......................... 36

5.5. Models for DCSystem performance and reliability evaluation 
..................... 36

5.6. Models for cost functions of computer and communication 
resources.......... 36

6. EXAMPLE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . .36

7. CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . .44

APPENDIX. GENERAL TASK STATEMENT of DFGraph MAPPING

to DCSystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . . 46

REFERENCES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 
. . . . . . . . . . . . . . . . . . . . 50


4

1. INTRODUCTION

Recent technological developments in high speed networks and multimedia 
workstations are making possible entirely new classes of distributed 
application such as distance learning, desktop videoconferencing, remote 
multimedia database access and so on. Multimedia systems combine a 
variety of information sources, such as voice, graphics, animation, 
images, audio, and full-motion video, into a wide range of applications. 
Research and development efforts in multimedia computing can be divided 
into two groups. One group centers its efforts on the stand-alone 
multimedia workstation and associated software systems and tools. The 
other combines multimedia computing with distributed systems. Potential 
new applications based on distributed multimedia systems [Furht, 94].

Works on distributed multimedia systems are based more or less on 
intuitive feelings about the required capabilities. Because requirements 
are mostly srecified in an informal and imprecise way, they are open to 
different interpretations, which can cause disagreement about the design 
choices. Often, disagreements detected only after progress has been made 
on the design of protocols or protocol entities.

Distributed MultiMedia Application (DMMApplication) can be represented 
by one or a set of Data Flow Graphs (DFGraph) [Rothermel, 94]. In a 
DFGraph the nodes represent socalled components that are interconnected 
by edges representing streams. Each component is associated at least 
with one device that produces (source component), processes 
(intermediate component - filter or mixer) or consumes (sink component) 
data streams. The DFGraph includes weights per components or nodes (such 
as type of component, CPU service time requirement, memory requirement 
and so on) and per streams or edges ( message length, stream rate, 
bandwidth requirement and so on). Media streams may originate at 
multiple sources, traverse a number of intermediate components and end 
at multiple sinks.

A Distributed Computer System (DCSystem) considered consists of 
computers communicating with each other by local or/and global 
network(s). For every DMMApplication a relevant part of DCSystem each 
computer that can be used for execution of functions of one or more 
components always will be considered.

Our interest in this paper is on the system support aspects.The main 
purpose consists of investigation of the problem of DMMApplication 
mapping to DCSystem that roughly is formulated as following one:

Given Data Flow Graph(s) of a Distributed MultiMedia Application and 
Distributed Computer System with information about available resources 
does there exist a mapping function such that calculates:

- the best (from the point of preliminary defined cost criteria) 
placement of the DFGraph onto DCSystem,

- the multipoint routes in DCSystem realizing connections between 
computers to which sources(s), intermediate and sink(s) components are 
mapped,

- the needed computer and communication resources (CPU service rate, 
memory size, buffer size, bandwidth),

5

- computer schedules for placed components,

- values of Quality of Service (QoS) such that QoS requirements of 
DMMApplication are satisfied?

Further we will :

- define a row of notions needed widely used in multimedia subject 
literature but that are often different treated,

- specify a DFGraph topologies and stream parameters for DFGraph 
[Section 2],

- define QoS parameters of DMMApplication and consider QoS negotiation 
problem [Section 3.1, 3.2],

- propose the method of resource capacity requirement assignment for 
components and edges of DFGraph that allows to specify and negotiate 
resource requirements of DFGraph elements [Section 3.3],

- specify and accurately formulate the mapping problem, propose 
hierarchical system of methods and models for its decision, plan 
possible approachs for mapping decision [Section 4],

- propose some models for performance and reliability evaluations of 
DCSystem, its subsystem and elements and mechanisms supporting 
DMMApplication [Section 5],

- consider an example of mapping problem decision [Section 6],

- summarize the paper and suggest future work.

Note, due to time limitations of this work (two weeks) the author 
couldn't decide all menthioned problems but he retains its in contents 
to represent main tasks associated with these problems and hopes to 
decide its nearest future.

6

2. DATA FLOW GRAPH OF DMMApplications

2.1. DFGraph topologies

An DMMApplication is established for purpose of computing and 
transferring data between components. Many DFGraph topologies of 
DMMApplications may be defined. It is necessary (particular for mapping 
problem formulation too) to clearly specify possible types of DFGraph 
topologies and define for their needed QoS requirements. The proposed 
classification of DFGraph topologies is based on concepts 
[Rothermel,94], [Maisonniaux,94].

2.1.1. Basic components

Let's denote graphically a component of DFGraph by a rectangle and 
component input and output ports by small circles (see Figure 2.1).

There are following basic components (see Figure 2.1):

- The One-point Source (or simply Source) used for producing and sending 
data to at least one component.

- The Multisource used for producing and sending different data to at 
least two other components.

- The One-point Sink (or simply Sink) used for receiving data from only 
one other component.

- The Mixer-Sink used for receiving data that are mixed from at least 
two other components.

- The Filter used for any intermediate process of transmitted data or 
exchanging of its transfer pameters.

- The Mixer used for receiving data that are mixed from at least two 
other components and for following sending the same data through its one 
output port.

- The Mixer-multioutput used for receiving different data that are mixed 
from at least two other components and for following sending the 
different mixed data through its some output ports to at least two other 
components. For n input ports of Mixer-multioutput there are  possible 
combinations of mixed data and the same number of output ports.

-
2.1.2. Basic schemes

There are following basic schemes (see Figure 2.2):

- Point-to-point scheme,

- Multicast scheme,

- Collector scheme,

- Emission scheme.

2n 1 ?


7

The first basic scheme stands for the point-to-point data exchanges. It 
associates a unique Source to its Sink. The three other schemes are 
dedicated to multipoint data exchanges. The Multicast scheme associates 
a unique Source to its Sinks. The Collector scheme associates a

Source Multisource

..

Mixer-Sink

..

Figure 2.1. Representation of basic components

Sink

Filter

..

Mixer-multioutput

..

..

Mixer

Point-to-point scheme

..

Collector scheme

...

Multicast scheme

Figure 2.2. Basic Schemes

.. ...

Emission scheme

.. ...

8

unique Mixer-Sink to its Sources. The Emission sceme associates a unique 
Multisource to its Sinks.

2.1.3. Centralised and decentralised topologies

Proposed basic components and schemes allow to construct different 
DFGraph topologies.

2.1.3.1. Centralised topologies

In the Centralised Topology (see Figure 2.3) there is only a unique 
central component. The other components can only play a point-to-point 
role according to the central component. There are following types of 
Central Topology:

- Multicast Topology characterises a communication made of only one 
Multicast sheme where the central component is Source.

- Collector Topology characterises a communication made of only one 
Collector scheme where the central component is Mixer-Sink.

- Emission Topology characterises a communication made of only one 
Multicust scheme where the central component is Multisource with 
multiple output ports one for each Sink.

- Collector-Multicast Topology characterises a communication made of one 
Multicast Scheme and one Collector scheme where the central component is 
Mixer .

- Collector-Emission Topology characterises a communication made of one 
Multicast Scheme and one Collector scheme where the central component is 
Mixer-multioutput.

2.1.3.2. Decentralised topologies

The Decentralised Topologies allow many Multicast and/or Collector 
and/or Emission and/or Point-to-point schemes with distinct central 
components or without their (see Figure 2.4). In Decentralised Topology 
there is not a central component which is connected with all other that 
play only point-to-point role according to the central component.

In Figure 2.4 the topology b) is a hierarchical one with two level of 
mixing

9

Multicast Topology Collector Topology

..

.
..

..

...

.. . ..

Collector-Multicast Topology

Collector-Emission Topology

Figure 2.3. Centralised topologies

Emission Topology

10

a)

b)

Figure 2.4. Decentralised topologies

Mixer Level 1

MixerMulticast Level 2

11

2.2. DFGraph stream parameters

Filters and mixers, processing messages of input streams 
(composing/decomposing, compressing/decompressing), may change stream 
parameters such that stream rate and message length. Due to filters and 
mixers DFGraph can not be consider as a traditional communication 
network. It belongs a network with message absorptions and 
multiplications. Two examples of this phenomena are presented in Figure 
2.5.

To specify DFGraph we consider the task of computing stream parameters 
such as stream rate  (message/sec) and message length V (bit/sec). Let's 
consider Mixer-multipoint component with n input ports and m output 
ports (see Figure 2.6). Let  be the rate modification factor for stream 
directed from input port i to output port j, . Thus matrix ( ) 
determines all possible rate modification of streams transfered through 
mixer.

a)

b)

Figure 2.5. Stream modification

a) by filter (as a result of message compressing),

b) by mixer (as a result of message composing)

l

aij
aij 0 ?

a i j i , 1 n , j , 1 m ,
= =

12

For every output port j we can define the summary rate of output stream

(2.1)

where  are stream rates for input port i and output port j 
correspondingly.

The summary rate of component input stream

(2.2)

and the summary rate of component output stream

(2.3)

For a source  and . For a sink  and . For filter n = m = 1, .

Similar, denote  the message length modification factor for stream 
directed from input port i to output port j, . Thus matrix  ( ) 
determine all possible message length modification of streams 
transferred through component.

1

i

n

.
..

.
..

1

j

m

.
..

.
..

a1j

am1

aij

Figure 2.6. Structure of Mixer-multipoint component

l j
ou t li ina i j j ,

i 1 =

n

? 1 m ,
= =

li
in l j ou t
,

lin l i i n

i 1 =

n

?
=

lou t l j ou t

j 1 =

m

?
=

lin 0 = lou t 0 > lin 0 > lou t 0 =
lou t alin =

bij
b i j 0 ? b i j i , 1 n , j , 1 m ,
= =

13

If message from input port k absorbs exactly one message from other 
input ports (associated with output port j) and the summary message is 
directed to output port j then stream parameters of output port j are 
determined as

(2.4)

(2.5)

For every scheme of message mixing we have to determine similar 
equations.

Now consider the stream parameter calculation for DFGraph.

Assumption. DFGraph is a directed graph without cycles.

Let's number components and edges of DFGraph so that  are numbers of

 all  components and  are numbers of all  edges.

Let's consider any component that one of its input ports is connected 
with edge i and one of its output ports is connected with edge j. Then 
we can interpret  as the rate modification factor of the stream from 
edge i to edge j by the component. So determine factors

 over the set of edges . We demand that , if, in particular, edges i and 
j are not connected with each other immediately, that is edges i and j 
are not a pair such that edge i is the input one for a component and 
edge j is the output one for the same component.

Using factors  write the stream rate conservation law for every edges:

(2.6)

Assume that stream rates  for output edges of source-components are 
given. Then a system (2.6) is heterogeneous one of M linear equations 
with M variables such that , where  is a number of source edges with 
given stream rates . Thus we get from equations (2.6) all stream rates 
in DFGraph edges.

Now given stream rates in edges the summary rate of input stream for 
every component can be calculated using equation (2.2).

Analogously we can determine the message length of a stream for every 
elements of DFGraph.

Thus the stream parameters can be calculated for every element 
(component and edge) of DFGraph. These parameters characterize loads 
(communication traffic, processing loads) cre-

V j
out Vi inb i j i 1 =

n

?
=

l j
ou t lk in ak j , 1 i aij 0 =
\
"
,
= =

i 1 N C ,
=

NC j N C 1 NC NE +
,
+
= N E

a i j

aij i j , NC 1 NC NE +
,
+
= aij 0 =

aij

l j l l alj j ,

l
? NC 1 + NC NE +
,
= =

l j
0

M NE NE 0
?
= NE 0 l j 0


14

ated by every elements of DFGraph. The load requirements of every 
DFGraph elements are used further for computing needed resource 
requirements of every DFGraph elements (see, Section 3.3).

15

3. QUALITY OF SERVICE REQUIREMENTS OF DMMApplications

3.1. Problem of QoS negotiation

A DMMApplication defines the set of QoS requirements that must be 
satisfied to allow the realization of the DMMApplication and can be 
possibly re-negotiated during the DMMApplication lifetime. Negotiation 
of QoS requirements includes:

- negotiation between QoS requirements and component parameters of 
DFGraph (in particular, for excluding component parameter conflicts in 
DFGraph - for example, between picture sizes),

- negotiation between different kinds of streams. For example, to 
support video connections high throughput is required and therefore high 
bandwidth guarantees will have to be done. Audio, on the other hand, 
will not require such a high bandwidth,

- mapping QoS requirements of DMMApplication down onto the communication 
subsystem, that is, high level requirements must be mapped onto 
transport level,

- partition of DMMA QoS requirements among components and edges of 
DFGraph as well as among computer and communication resources along 
transport paths in DCSystem and network(s).

DMMApplications that can accurately forecast their requirements may 
prefer to reserve processing, transport and network resources in advance 
via a connection oriented service. Also transactions that require fast 
response often cannot wait for the connection time associated with 
resource allocation which is greater than twice the round trip delay 
(for all protocols requiring explicit connection set-up). 
DMMApplications that require any guaranteed QoS higher than best-effort 
must request that resources be allocated to their connection in the 
network, the transport and application interfaces.

Thus guaranteed QoS demands the integration of a range of QoS 
configurable protocols and mechanisms in both the hosts (computers of 
DCSystem) and network [Campbell,94]. In hosts, these include thread or 
process scheduling, buffer allocation, jitter correction and 
coordination over multiple related connections. In communication 
systems, protocol support such as end-to-end QoS negotiation, 
renegotiation and indication of QoS degradation are required. Suitable 
resource reservation protocol and service disciplines in switch queues 
are needed. It is also necessary to provide maintenance and management 
of QoS over all system layers. This includes management functions such 
as admission control for new connections and monitoring to ensure that 
QoS levels are being maintained by the service provider.

The development of DCSystems to support DMMApplications which exploit 
continuous media introduces new syncronization requirements. In 
particular, the upper layers require support for the following two 
varieties of syncronization [Leopold,92]:

- event-driven synchronization: This is the act of notifying that a 
relevant event or set of events has taken place, and then causing an 
associated real-time action or actions. For example, a user clicking on 
the stop button relating to a video play-out could cause the play-out to 
stop instantaneously.

16

- continuous synchronization: This is where two or more continuous 
streams need to be kept in step by an on going commitment to a 
repetitive pattern of event driven synchronization relationships. An 
example scenario where it is required to form a continuous 
synchronizatio relationships is a language laboratory where separate 
audio tracks in different languages are stored on a single server but 
are to be distributed to different workstations in a real-time 
interactive language lesson.

Some authors refer to these sorts of linkage as orchestration 
[Leopold,92], [Woo,94]. They employ the term ?orcherstration? rather 
than ?synchronization? for two reasons. Firstly, cross-stream 
relationships may encompass more than just temporal co-ordination, and 
secondly the term synchronization is already overloaded and given a 
different emphasis in current OSI usage (the OSI concepts pertains to 
checkpointing and synchronization between peer entities).

Most of DMMApplications use some pre-orchestrated, stored multimedia 
data, precipitating the necessity for management of heterogeneous data 
with vasty different storage, communication, and presentation 
requirements. Especially with respect to communication, this data posses 
drastically different performance and reliability characteristics. For 
example, audio and video data are isochronous in nature, requiring a 
service supporting real-time delivery and fine-grain synchronization. On 
the other hand, traditional data such as text or graphics posses less 
stringent end-to-end delivery requirements yet needs superior 
reliability in transmission. However, if this data has sythetic timing 
relationships with other data, as is a case of preorchestrated 
multimedia information, it should be delivered on time without error.

Diverse requirements of DMMApplications can be specified through an 
extended set of QoS parameters, which includes:

- throughput (minimum, maximum, average),

- end-to-end delay (maximum, average),

- jitter (maximum),

- error (loss) rate (maximum).

The values of these parameters are negotiated at the time of connection 
establishment and are guaranteed during the data transfer phase. An 
efficient way for supporting desired QoS is to provide a set of 
application and transport protocols which can be applied for multiple 
virtual circuits over the communication network. Multiple virtual 
circuits are used for transferring different media type data on separate 
vurtual channels, thus utilizing different QoS parameters for each 
channel. Guaranteeing QoS for a particular media using an independent 
virtual channels is viable in a broadband network, e.g., the ATM 
technology.

Note, that the task of QoS requirement determination for DMMApplication 
is not simple. At first, all QoS parameters mentioned above are 
interdependent. For example, if message delivered to sink with delay 
more than admissible maximum delay is discarded then the maximum message 
delay Tmax must be negotiate with maximum loss rate (probability) Rloss 
such that

P(t > Tmax) < Rloss ,

17

where P(t > Tmax) is the probability that the message delay t is more 
than Tmax.

At second, components and edges of DFGraph of DMMApplication must be 
specified by resource capacity requirements that meet QoS requirements 
of DMMApplication. It is a task of DMMA QoS requirement partition among 
components and edges of DFGraph.

At third, it's needed to determine for which objects of DFGraph QoS 
requirements must be given? For each separate element (component and 
edge) of DFGraph, for each path between sources and sinks or for any 
other sets of DFGraph elements? In the first case it's very difficult to 
choose negotiated QoS requirements for all elements. In the second case 
it's impossible for path consisting , for example, of mixers to meet 
different requirements of different kinds of streams along the path from 
the source to the sink. Let's look the Figure 6.2. From component C1 to 
component C5 there is an audio stream and further from C5 to C7 there is 
mixed one combining video and audio streams. It's known that QoS 
requirements for video and audio streams are strong different 
[Furth,94].

We offer to use the termin ?media path? (or simply path) for the 
sequence of adjacent elements in DFGraph for which we can specify 
particular QoS requirements. A media path is the sequence of adjacent 
DFGraph elements through which one or some kinds of media streams with 
the same or close parameters and QoS requirements are transmitted. In 
particular, a path can coincide with a path from source to sink and, on 
other hand, a path can consist of only two elements - a component with 
its output edge. A degree of DFGraph decomposition into paths can also 
depend on the necessary precision of calculations.

We name the first element in a path as sender and the last one as 
receiver.

Further we assume that paths and corresponding requirements for every 
path are given. And we demand that each element of DFGraph must be used 
at least in one path. The last claim is needed if we want to determine 
resource requirements for every element of DFGraph. On other hand, we 
don't need all possible paths in DFGraph. The number of DFGraph paths 
have to be enough for DMMApplication QoS requiremen assignment for every 
kind of streams as well as for computing a resource requirements of 
every DFGraph elements. In particular, a number of paths may coincide 
with number of stream types in DFGraph.

Thus decision of DFGraph mapping to DCSystem includes:

1. Specification and negotiation of QoS requirements of DMMApplication 
for all DFGraph media paths,

2. Specification and negotiation of resource requirements of DFGraph 
components and edges,

3. Itself mapping of DFGraph to DCSystem,

4. Relaxation of resources requested in plenty.

Further we follow these steps of mapping problem decision.

18

3.2. Relationships for QoS requirement negotiation

Let's denote QoS requirements of DFGraph path m=1,...,M :

 - average, minimum and maximum message delays,

 - average, minimum and maximum throughputs,

 - maximum message loss rate (probability).

Let  be the average message delay in the element i (component or edge) 
of DFGraph;  the capacity needed by element i of DFGraph (further we say 
simple `the capacity of element i');  the m-th path of the m-th path in 
DFGraph.

Assume that a message can not be multiplied along a parth from the 
sender to the receiver (but can be combined with other messages in a 
mixer). Then the average message delay for m-th path

(3.1)

The minimum message delay for m-th path we get if buffer sizes in 
intermediate elements of the path are chose such that  is reached on 
condition that the loss rate caused by buffer overflow is less than . 
This is an optimization problem of buffer size choosing:

(3.2)

where  is probability that message is lost (due to buffer overflow) in 
the i-th element that uses buffer size .

Assume that a message delivered to the receiver with delay more than  
doesn't play out and we can consider such the message as a lost one. 
Then it is needed

(3.3)

To determine throughput let's consider a DFGraph as a communication 
network and take into account that more than one message is allowed to 
be on transit through the network at the same time. This message 
multiplexing is possible due to pipelining along a given path and to 
alternate routing along many paths. If a message can not be multiplied 
or lost along a parth we can calculate the average m-th path throughput 
associated with sink-side using the relation [Kleinrock, 76]

T0
m
( ) T m i n m
( ) Tmax m
( )
,
,

H0
m
( ) Hm i n m
( ) Hmax m
( )
,
,

R m
( )

T i
C i
pm

T m ( ) T i T 0 m
( )
?

i pm ?
?
=

T m i n m
( )

R m
( )

Tm i n m
( ) T i L i ( ) m i n fi

i pm ?
?
? ? ? ? ? ö =

R i L i ( ) R m ( )
?

i pm ?
"

Ri L i ( )

L i

Tmax

P tm Tmax m
( )
>
( ) Rm m ,
< 1 M ,
=


19

 (3.4)

where  is the average number of messages being in the network path m,  - 
length of message (bits), arrived to the receiver of m-th communicating 
pair. (Note that  and are interdependent parameters).

On other hand, if messages can not be multiplied and lost along the 
parth between sender and receiver then the message arrival rate  from 
source into m-th path and the message departure rate  must be equal.

Now consider when message may be lost into a path (caused, for example, 
by buffer overflow or by transmit error) with rate  . Let  be the 
average, minimum and maximum message arrival rates from source into the 
path of m-th communicating pair. Then:

(3.5)

The last relations are right on condition that there is no a bottleneck 
along the m-th parth. Otherwise when there is at least one resource i 
(node or link) with capacity  and resource i is used in m-th path, , 
then  or for more general case

 (3.6)

From (3.6) we get the necessary condition to meet delay and throughput 
requirements of DMMApplication

or else

 (3.7)

where N is the overall number of DFGraph elements (components and 
edges).

H m ( ) n m
( )
V
m
( )

T
m
( )
----------------------- =

n m
( ) V m ( )

n m
( ) T m ( )

l m
( )

H m
( ) V m ( )
?

R m
( ) l m ( ) lm i n m
( ) lmax m
( )
,
,

H
m
( )
l
m
( )
1 R m
( )
?
( )V m
( )
=

Hmin m
( ) lm i n m
( ) 1 R m ( )
?
( )V m
( )
=

Hmax m
( ) lmax m
( ) 1 R m ( )
?
( )V m ( )
=

Ci l m ( )
?
i pm ? Hmax m
( ) C i 1 R m ( )
?
( ) =

i pm ?
( ) C i l m ( )
?
( ) Hmax m
( )
fi
\
" 1 R m ( )
?
( )min i C i { } =

C i Hmax m
( ) 1 R m ( )
?
( ) ? i ,
? 1 N , m i pm ?
( ) ?
"
,
=

Ci ma x m i pm ?
( ) ? Hmax

m
( ) 1 R m ( )
?
( ) ? ) ( i ,
? 1 N ,
=


20

Thus QoS requirements of DMMApplication must be negotiated with each 
other so that relations (3.1) - (3.7) are right. (Note, further we will 
add the expression for jitter to these relations).

Supporting new kinds of properties and models of data streams in DFGraph 
we may get new relations between QoS requirements. But each time QoS 
requirement negotiation is needed.

3.3. Assignment of resource capacity requirements

There is the following problem of assignment of resource capacity 
requirements to the components and edges of DFGraph.

GIVEN:

-  - the average rates of message streams  (mes/sec) through every DFG 
element (components and edges). Here N is the overall number of DFGraph 
elements. Note, if arrival stream rates are given for every source then 
we can calculate stream rates for every elements of DFGraph for given 
modification factors (see, Section 2.2);

-  - the message length  (bits) for every edge i and number of computer 
operations needed for message processing  (op/sec) for every component 
i. (Further we name  simply message length);

- cost function S as a sum of all resource costs  , where  is the cost 
of resources needed for i-th element of DFG;

- negotiated QoS requirements of DMMApplication for every DFGraph path , 
.

IT IS NEEDED

to select the resource capacity requirements  (op/sec - rapidity) for 
every component i and  (bit/sec - bandwidth) for every edge j of DFGraph 
so that

(3.8)

under constraints for every corresponding pair path

(3.11)

,(3.12)

where  is (random) message delay in the m-th path.

li
( i , 1 N , ) =

V i
V i

S S i

i 1
=

N

?
= Si

T0
m
( ) Tmax m
( )
, R m ( ) m , 1 M ,
=

C i
C j

S Si C i ( ) min fi

i 1 =

N

?
=

T m ( ) Ti Ci ( ) T0 m
( ) m ,
?

i pm ?

? 1 M ,
= =

P tm Tmax m
( )
>
( ) Rm m ,
< 1 M ,
=

t m


21

Note, that computing Ci is not a trivial task when DFGraph elements (for 
example a component) are realized in DCSystem by a resource with a queue 
(a single CPU computer) shared between messages of the same and 
different streams.

Now we determine the cost function  and message delay  for DFGraph 
element i = 1,...,N. Note that we may be satisfied by a pessimistic 
engineering decision of this problem because the decision can be 
improved on the relaxing stage of reservation protocol.

We consider the case of linear capacity costs, namely  . Here  is the 
cost incurred for each unit of capacity needed for the function 
realization of ith element of DFGraph. In fact we can just as easily 
handle the case of a constant plus linear cost, namely, , where  is an 
extra constant cost. In this case we get the same decision of the 
optimization problem. This remark is right too for , where T is the 
duration of DMMApplication.

Note that the cost rate  may vary in an arbitrary way with respect to 
any parameter of the computer and channel except that it must be linear 
with capacity; for example, for channel  is often taken to be 
proportional to the physical length of the channel (specially, the 
distance between its two end points).

Now we are faced with solving for a message's average delay in a single 
component (placed on a computer) and edge (placed on a channel if 
adjacent components are mapped to different computers). First we will 
consider two types of models for element performance evaluation:

- multichannel model without queue allows to consider a communication 
and processing resources that support a simultaneously transmission or 
processing more than one messages (for example, X.25 public network with 
datagram mode);

- model of server with unlimited buffer that can be used for modelling 
message processing by computer or for modelling message transmission 
through network with unique channel (for example, LAN Ethernet). 
Assumption of unlimited buffer allows to get maximum of average delay 
that is pessimistic value which can be further improved by limitation of 
buffer capacity.

For first model .

For second model we will use the M/M/1 system with Poisson arrivals at a 
rate  and exponential service time of mean . As for assumption of 
Poisson arrivals of messages in network we refer to [Kleinrock,76]. We 
assume that a time of message's service has exponential distribution 
because

- if even the length of message is constant (not random variable) for 
each element of DFGraph the assumption of exponential distributed length 
gives a pessimistic performance parameters that is admissible for 
engineering design;

- this assumption allows us to get complete expressions for problem 
decision.

Thus for second model

S i Ci ( ) T i C i ( )

S i Ci ( ) a i C i = ai

aiC i a0 + a0

S i Ci ( ) a i CiT =

a i

ai

T i V i C i ?
=

li
V i C i ?

T i
V i

C i liV i ?
---------------------- =


22

Considering DFGraph as an exponential queueing network we can determine 
probability  for the m-th path using convolution integral of -th order, 
where  is the number of DFGraph elements in the m-th path. But this 
complete expression is very complex for further calculation and 
therefore we assume that the message delay  has exponential distribution 
with mean  , that for practice is often admissible. Then

.

Thus the problem of assignment of resource capacity requirements  (3.8) 
- (3.10) can be rewritten as following one

(3.11)

(3.12)

(3.13)

(3.14)

where the first sum in expression (3.12) is written for DFGraph elements 
associated with multichannel model and the second sum is written for 
ones associated with queue model mentioned above.

After logariphming equation (3.13) the optimization problem can be 
rewritten:

(3.15)

P t m Tmax m
( )
>
( ) Lm Lm

t m
T m
( )

P tm Tmax m
( )
>
( ) e

Tma x m
( )

T m
( )
----------- ?

=

C i

S a i C i min fi

i 1 =

N

?
=

T m ( ) V i

C i
-----
V j

C j l j V j ?
------------------------

j pm ?
?
+

i pm ?
? T0 m
( ) m , 1 M ,
= = =

P tm Tmax m
( )
>
( ) e

Tmax m
( )

T m
( )
----------- ?

R m ( ) m , 1 M ,
= = =

C i 0 i ,
? 1 N ,
=

S a i C i min fi

i 1 =

N

?
=


23

(3.16)

(3.17)

This problem is an optimization one with a nonlinear constraints. Using 
the Lagrangian method we get :

(3.18)

(3.19)

(3.20)

where  are determined from system of M nonlinear equations:

(3.21)

The system (3.20) can be decided by one of numerical methods.

To get not optimal but a rational decision of the problem (3.15) - 
(3.16) that can be often usable for practical application we offer 
following approach:

T m ( ) V i

C i
-----
V j

C j l j V j ?
------------------------

j pm ?
?
+

i pm ?
? min T 0 m
( ) Tmax m
( )

ln R m
( )
( )

---------------------- ?
,
? ? ? ? ? ö = =

m 1 M ,
=

C i 0 i ,
? 1 N ,
=

Ci
V i xi

ai
---------- =

C j
V j x j

a j
------------ l j V j +
=

x i bm i ,

m i pm ?
?
( )

? 1 N ,
= =

bm

V i ai

xi
-----------

i pm ?
? min T0 m
( ) Tmax m
( )

ln R m ( )
( )

---------------------- ? ? ? ? ? ö ?
,
? ? ? ? ? ö m 1 M ,
=
,
=


24

- to decide the optimization problem (3.15), (3.16) for every separate 
path m = 1,...,M and further to correct resource capacities so that all 
M QoS requirements (3.16) are satisfied. Note if paths of DFGraph don't 
intersect with each other then this approach get exact decision of 
original problem (3.15),(3.16).

Let's decompose the problem (3.15)-(3.16) into M subproblems. The m-th 
subproblem is formulated as

Using Lagrangian method we get the following decision for m-th 
subproblem:

(3.22)

(3.23)

And now we choose the capacities of all elements on overall M paths

(3.24)

and summary resource cost for time unit (sec) is calculated by using 
equation (3.15) and for the DMMApplication duration T equals to SxT .

S m ( ) a i Ci m
( ) min fi

i pm ?
?
=

T m ( ) V i

C i
-----
V j

C j l j V j ?
------------------------

j pm ?
?
+

i pm ?
? min T 0 m
( ) Tmax m
( )

ln R m
( )
( )

---------------------- ?
,
? ? ? ? ? ö = =

C i
m
( ) max 1

T 0
m
( )

----------- ln R m
( )
( )

Tmax m
( )
---------------------- ?
? ? ? ? ? ö ,
? ? ? ? ? ö Vi

a i
----- anVn

n pm ?
( ) ?
=

C j
m
( ) l j V j max 1

T 0
m
( )

----------- ln R m
( )
( )

Tmax m
( )
---------------------- ?
? ? ? ? ? ö ,
? ? ? ? ? ö V j

a j
------ anV n

n pm ?
( ) ?
+
=

C i max m i pm ?
( ) ? Ci

m
( )

? ? ? ? ? ü i 1 N ,
=
,
=


25

3.4. Stream synchronization parameters for basic schemes of DFGraph

In this section, we determine jitter and skew and get relations for its 
calculation.

3.4.1. Point-to-point scheme

In this case we deal with the subject of serial synchronization that 
determines the rate at which events must occur within a single data 
stream (intra-synchronization). In the wide sense of stands for all 
time-related issues a single medium stream has to deal with jitter. We 
define jitter as instantaneous difference between actual and desirable 
arrival time of message to receiver.

There are two approachs for jitter compensation:

- synchronization is required for every data unit (message) over all 
temporal stream,

- synchronization is required only between messages within a 
synchronization unit. The boundary of a synchronization unit is 
application-dependent, for example, the most common synchronization 
units are talkspurts for voice and frames for video. The using adaptive 
synchronization allows to divide the data (message) stream into smaller 
manageable units, and to consider the synchronization process only 
within a single synchronization unit.

Further we use the second model that was proposed by [Schulzrinne,92] 
and [Wang,93] and developed by [Stainov,94] for scheduling in sequence 
systems.

We differ two cases:

- recovery the regular data stream at the receiver-side, that is the 
receiver must get a regular data stream independent on temporal 
characteristics of an original stream,

- recovery the original data stream at the receiver-side, that is the 
receiver must get the reconstructed original data stream produced by 
receiver.

Let's investigate the first case.

3.4.1.1. Recovery a regular stream

We assume that all messages are of the same size and consider 
point-to-point scheme presented by sender - server - receiver where a 
server can represent a separate computer or communication link. We say 
the message has arrivied or departed only when its last bit has arrivied 
or departed.

Suppose T is an interval of synchronization unit, M be the number of 
messages generated by sender during the synchronization unit. We assume 
that M is constant and is related with size of burst generated by the 
sender.

Let  be the arrival time of th message and  - the number of messages 
arrived in the interval . Then  is the number of messages arrived before 
: .

Define an average rate of sender in interval , as

a i i A t 1 t2 ,
( ) t1 t 2 ) ,
[ A a1 am ,
( ) t am = A a1 am ,
( ) m 1 ?
=

a1 am ) ,
[


26

 (3.25)

and minimum average rate of sender in its active phase  of 
synchronization unit

 (3.26)

Define the maximum instantaneous rate of the sender

(3.27)

Let sender produces message stream with the rate  that can vary in the 
interval . Let  be the desirable constant (deterministic) message 
arrival rate to the

receiver for data presentation, J - the maximum admissible jitter,  - 
the server rate that can vary in the interval , V - the size of server 
buffer.

A possible task of calculation point-to-point scheme parameters can be 
following:

- The receiver demands a regular arrival data stream with constant rate 
for presentation , admissible deviation from this rate is characterized 
by maximum jitter J. The sender is characterized by minimum and maximum 
rates  so that . It produces the burst of M messages. It's necessary to 
calculate synchronization interval T (for realizing start-stop mode for 
sender), admissible rates  of the server and the size of server buffer 
V.

Obviously that

(3.28)

1. CONSTANT SERVER RATE

First, we consider the simple case when the server provides the 
desirable constant rate for data presentation by receiver, that is

In Figure 3.1a) the temporal behaviour of the point-to-point scheme is 
presented for the case when  so that there are not server starvation or 
buffer overflow, server produces a desirable regular arrival stream to 
the receiver, and jitter J=0 always. (In Figure 3.1  is denoted as `mu',  
is denoted as `lmax' and  is denoted as w).

For buffer size calculation we consider the worst case when the sender 
generate in a synchronization unit T all M message with maximum rate . 
Figures 3a) and 3b) explain together the behaviour of the system for 
this case. In Figure 3b) the line `lmax' shows the process of buffer 
filling up with rate  by sender on condition that server is stopped. The 
line

lm

A a1 am ,
( )

am a1 ?

------------------------ m 1 ?

am a1 ?
------------------ m , 2 M ,
= = =

a1 am ) ,
[

lm i n min lm m 2 M ,
=
,
{ } =

lmax max 1 am a1 ?
------------------ m 2 M ,
=
,
? ? ? ? ? ü =

l

lmin lmax ,
[ ] w

?

?m i n ?max ,
[ ]

w

lm i n lmax ,
[ ] lmax w lmin ? ?

?m i n ?max ,
[ ]

T M w ?
=

? w =

? w =
?
lmax w

lmax

lmax

27

`mu' shows the process of empting full buffer by server with rate  on 
condition that sender is stopped. And thik line `v' shows the result 
process (current number of messages in the buffer) when sender and 
receiver perform with rates  and  simultaneously.

From Figure 3.1 follows Ta = M/ . During the interval Ta -1/  = (M-1)/ 
server operates (M-1) /  messages. So at the time point Tfull there are 
not more than

(3.29)

messages in the buffer.

Relation (3.29) determines necessary buffer size. For our example in 
Figure 3.1 : = 2, M = 6 we get buffer size V =  = 4 that is less than 
burst size M = 6 in the synchronization unit T.

If synchronization unit is chosen so that  then at least to end of 
synchronization unit T we get the server starvation and regular stream 
will be destroyed (see Figure 3.2). For this case maximum jitter J = T - 
M/ .

?

lmax ?

lmax lmax lmax ? lmax

V M M 1 ?
( )?

lmax ----------------------- ?
=

lmax ? 6 2.5 ?

T M w ?
> M ? ?
=

?


28

Ta

Sender

Server

Tsource = T

Arrival stream to the server

Departure stream from the server Buffer

Tsink = T

t

t

1/lmax

1/mu

mu

0

2

4

v=M=6

v

v

t
Tfull

lmax

1/w

Figure 3.1. a) Time diagram for the point-to-point scheme,

b) Buffer behaviour for the worst case

a)

b)

Receiver

Desirable arrival stream to the receiver

29

2. VARIABLE SERVER RATE

Let's now the server has variable rate . In this case the maximum jitter 
(see Figure 3.2 for the jitter calculation when )

(3.30)

Hence using (3.28)

 (3.31)

If server succeeds to service all M messages to the end of 
synchronization unit (that is  and we have only positive jitter J = T - 
M/ ) then the needed buffer size is

 (3.32)

If  then there is no zero probability of buffer overflow because a 
remainder of unserviced messages in the buffer to the end of consequent 
synchronization units can be increased in time. Thus we get in this case 
probability task for buffer size calculation. (It will be considered 
further).

Probability of buffer overflow must be take into account for calculation 
of such the QoS parameter as data loss rate , see expressions (3.2).

?m i n ? ?max ? ? ? ?max =

J max T M ?max ------------ M ?min ------------ T ?
,
?
? ? ? ? ? ü =

Mw

M Jw +
------------------ M T J +
------------- ?m i n ? ?max ? ? M T J ?
------------ Mw M J ? w ---------------- = = = =

?m i n w ? ?max

V M M 1 ?
( )?m i n

lmax ------------------------------- ?
=

?m i n w <


30

3. ADAPTIVE SERVER RATE

4. SERVICE WITH ONE SYNCHRONIZATION UNIT DELAY

5. SEQUENCE OF SERVERS BETWEEN SENDER AND RECEIVER

3.4.1.2. Recovery an original stream

3.4.2. Collector scheme

Sender

Server

Tsource = T

Departure stream from the server

Tsink = T

t

t

1/lmax

Arrival stream to the server

J > 0

Figure 3.2. Time diagram for the incorrect synchronization unit T

Buffer

1/w

1/mu

Receiver Desirable arrival stream to the receiver

31

4. MAPPING PROBLEM

There are two basic approaches for mapping decision: static and 
adaptive. In the static approach, a mapping is made before a session is 
established and is fixed for lifetime of the session if it is 
successful. During mapping it's assumed that the DCSystem will be not 
changed. In this case the success of mapping decision depends also on 
relation between a time needed for mapping execution and an actual time 
of invariable system state or of insignificant system state changing 
doesn't influencing on mapping decision. This disadvantage of static 
approach can be sometimes overcome by development of effective fast 
mapping methods.

In the adaptive approach the mapping is made during the session 
establiment phase (by pattern step-by-step) and is adjustable depending 
on current states of system components (computers and communication 
subsystem). But in this case there are other difficulties, for example, 
deadlocks. Besides only one of possible (not optimal) decision can be 
reached.

There is a middle approach too - substatic one based on system domains.

Obviously, it is helpful to have different kinds of mapping algorithms 
that are choosed depending on temporal and other features of DCSystem 
and DMMApplications.

In this section, we consider the analytical foundations for static 
approach that allows given a particular topology, node and links 
capacities of DCSystem, to meet the QoS requirements of DMMA with 
significantly reduced resource demands by preliminary proper 
calculations.

4.1.System of methods and models for mapping decision

System of methods and models for mapping decision is represented in 
Figure 4.1.

32

Algorithms for Mapping of DMMApplication DFGraphs to DCSystem

Mapping of separate DFGraph

Mapping of more than one DFGraph

Models for DCSystem QoS evaluation

Routing (point-topoint and multipoint communications)

Cost functions for computers and communica-

Specifications of DFGraphs, QoS requirements of DMMApplication

Models for computer QoS (performance and reliability) evaluation

Models for intercomputer communication QoS (performance and reliability) 
evaluation

QoS partition among transport elements of the communication parth

Point-to-point Routing Models for network QoS evaluation

Cost function of communication resources

Models for data link QoS evaluation

Models for node QoS evaluation

Additional load (traffic) created by new DMMA

Current load (traffic) created by applications that are executing

Figure 4.1. Hierarchical system of methods and models for mapping 
decision

33

4.2. Mapping task statement

In Appendix, a general task statement of DFGraph mapping to DCSystem is 
represented. In this section, we formulate the particular mapping task 
as a mathmetical programming one using decision of assignment of 
resource capacity requierements to DFGraph elements (see, Section 3.3).

GIVEN:

- DFGraph with

CD - the set of components;

 - the set of directed edges connecting components with each other;

 - the set of needed resources (capacities) for components ( ) and for 
edges ( ). These data we get using the approach represented in Section 
3.3;

- DCSystem with

P - the set of computers (nodes);

 - the set of directed links connecting computers. Here a link is a 
logical element which can represent actual subnetwork(s) that's nodes 
and links are not accessible for CINEMA's management;

 - the set of available (vacant) resources (capacities) of computers ( ) 
and links ( ) . Let's explain. If, for example, computer has an origin 
capacity (servise rate ) Z and its utilization factor (by current 
processing tasks) equals to r < 1 then its available resource equals to 
A = (1-r) Z;

 - the set of resource cost functions for computers ( ) and links ( ). 
Here C is the volume of a needed resource.

-  - the set of admissible placing of components in DCSystem such that  
is a set of computers on which a component  may be placed (that means, 
does computer configuration have needed devices and resources to realize 
multimedia functions of certain component type?);

THE DECISION VARIABLES are  such that  if component i is placed onto 
computer j and  otherwise.

If  is defined as  if i = j and  otherwise then

MAPPING PROBLEM can be formulated as:

=

E i j ,
ß ? i j CD ?
, ,
{ } =

C Ci i CD ?
,
{ } C ij i j ,
ß ? E ?
,
{ } ,
{ } =

C i C i j

L i j ,
ß ? i j P ?
, ,
{ } =

A A i i P ?
,
{ } Ai j i j ,
ß ? L ?
,
{ } ,
{ } =

Ai Aij

a a i C ( ) i P ?
,
{ } aij C ( ) i j ,
ß ? L ?
,
{ } ,
{ } =

ai a i j

PL PLi i CD ?
,
{ } =
PLi j P ?
{ } = i CD ?

x i j xij 1 =

x i j 0 =

d i j dij 1 = d i j 0 =

F x i j { } ( )

34

(4.1)

(4.2)

(4.3)

(4.4)

(4.5)

In this formulation, the objective function F minimizes the summary 
resource cost. The first term in the objective function identifies the 
cost of resources of computers on which components are placed. The 
second term represents the cost of communication resources of links on 
which edges are placed. Note that multiplier  equals to 1 if and only if 
components i and k connected immediately with each other in DFGraph are 
placed on different computers j and n. In this case the edge connecting 
these both components ( i and k) must be mapping to the link connecting 
the computer j with the computer n.

Constraint set (4.2) guarantees that every component  must be placed 
into DCSystem and can be placed only onto one computer.

Constraint set (4.3) guarantees that resources used by components placed 
on a computer does not exceed the available resource of the computer. 
Constraint (4.4) is similar (4.3) but for edges and links.

The formulation (4.1) - (4.5) allows to search the placing for every 
component of DFGraph. If some components have to be placed on certain 
computers ( for example, sources and sinks) then corresponding variables  
must be fixed by 1 and constraint sets must be added by following kinds 
of equations:  if component i have to be placed on computer j.

The problem (4.1) - (4.5) can be generalized for mapping of a group of 
DMMApplications. Let's denote SA - the set of DMMApplication DFGraphs,  
- one of DFGraphs belonged the set SA, . Let's add identificator  of 
DFGraph as a high index to all previous nota-

min

xija j Ci ( ) ? +

j PL i ?
( ) ?
i CD ?
( ) ?

xij
n PLk ?
( ) ? xknd jna jn C i k ( )

j PLi ?
( ) ?
i k
,
ß ? E ?
( ) ?

? ? ? ? ? ? ? ? ? ? ? ? ? ü

x i j
j PLi ?
( )

? 1 i " CD ?
,
=

x i j C i A j j " P ?
,
?

i CD ?
( ) ?

x i j
n PLk ?
( ) ? xknd j nC i k A jn j n ,
ß ? " L ?
,
?

j PLi ?
( ) ?
i k
,
ß ? E ?
?

xij 0 1 ,
[ ] i CD j P ?
,
?
,
?

d jn

i C ?

xij
x i j 1 =

a
a SA ? a

35

tions associated with DFGraph and used in (4.1) - (4.5): . Then mapping 
problem for the set SA of DFGraphs of a DMMApplication group can be 
formulated as:

=

(4.6)

(4.7)

(4.8)

(4.9)

(4.10)

4.3. Approachs and algorithms for mapping decision

See [Norman, 93], [Ramanathan,92], [Narasimhan,94], [Dimitrijevic, 94], 
[Tindell, 92]

CDa Ea Ca PLa PL i a x i j a
,
, , , ,

F x i j a

? ? ? ? ? ü

? ? ? ? ? ö

min

x i j
a a j C i a
( ) ? +

j PLi a
?
( )

?

i CDa ?
( )

?
a SA ?
( ) ?

x i j
a

n PLk a
?
( )

? xkn a d j na j n Cik a
( )

j PL i a
?
( )

?

i k
,
ß ? Ea ?
( )

?
a SA ?
( ) ?

? ? ? ? ? ? ? ? ? ? ? ? ? ü

xi j
a

j PLi a
?
( )

? 1 i " CDa a SA ?
"
,
?
,
=

xi j
a C i a A j j " P ?
,
?

i CDa ?
( )

?
a SA ?
( ) ?

xij
a

n PL k a
?
( )

? xkn a d jnC i k a A j n j n ,
ß ? " L ?
,
?

j PL i a
?
( )

?

i k
,
ß ? Ea ?

?
a SA ?
( ) ?

x i j
a 0 1 ,
[ ] i CDa a SA j , P ? ? ,
?
,
?


36

5. MODELS for PERFORMABILITY and RELIABILITY EVALUATION of

DISTRIBUTED COMPUTER SYSTEM (DCSystem), its SUBSYSTEM and

ELEMENTS

5.1. Models for computer performance and reliability evaluation

See [Kapelnikov,89], [Cruz,91a], [Cruz,91b]

5.2. Models for evaluation of data stream

See [Cruz,91a], [Cruz,91b], [Stamoulis,94], [Stirpe,92], [Blum, 94], 
[Wang,94]

5.3. Models for data link performance and reliability evaluation

See [Hagin,94]

5.4. Models for network performance and reliability evaluation

See [Gagin, 91], [Hagin,94]

5.5. Models for DCSystem performance and reliability evaluation

See [Cruz,91a], [Cruz,91b], [Dimitrijevic, 94], [Kapelnikov,89], 
[Hagin,94]

5.6. Models for cost functions of computer and communication resources

6. EXAMPLE

Let's consider an example of tasks associted with mapping problem. The 
DFGraph of a DMMApplication is represented in Figure 6.2 using graphical 
symbol notations shown in Figure 6.1. Let's number DFGraph elements as 
in Figure 6.3. There are given following data:

- Numbers of computer operations needed for message processing by 
components:

 V1 = V2 = V3 = V7 = V8 = 2v, V4 = 3v, V5 = V6 = 4v;

Message lengths for edges:

V9 = V10 = V11 = V12 = V13 = V14 = V15 = V16 = v,

37

where v is multiplier, for example v= 2500 bytes for edges and v = 2500 
operations for components. (Note, we introduce multiplier only for 
calculation reduction. In general case all Vi may be different).

- Set of media paths:

 = (1-->5) = (1,9,4,11),  = (2-->5) = (2,10,4,11),

 = (1-->6) = (1,9,4,12),  = (3-->7) = (3,13,5,15,7),

 = (3-->8) = (3,14,6,16,8).

Note we get exact decision for the problem (3.15), (3.16) for this set 
of paths choosed so that there are not intersected ones.

- Loss rates for every paths:

R1 = R2 = R3 = 0.1,

R4 = R5 = 0.01;

- Average throughput for every path (in its last edge);

H1 = H2 = H3 = 160 KBit/sec = 8 mes/sec,

H4 = H5 = 20 Mbit/sec = 1000 mes/sec

- Average message delay for every path:

T1 = T2 = T3 = 0.3 sec, T4 = T5 = 0.01 sec;

- Average stream rate for every DFGraph element:

 =  =  =  = 4 mes/sec,

 =  =  =8 mes/sec,

 =  =  =  =  =  =  =  =  =1000 mes/sec,

- Costs of resource unit for every element of DFGraph:

Using equation (3.13) we get maximum message delays for every path (note 
if we take into account jitter requirements the maximum delays may be 
corrected):

T1max = T2max = T3max = 0.69 sec,

T4max = T5max = 0.046 sec.

p1 p2

p3 p4

p5

l1 l9 l2 l10

l4 l11 l12

l3 l13 l14 l5 l6 l15 l16 l7 l8

ai 2 i , 1 8 ,
= =

ai 1 i , 9 16 ,
= =

38

Using equation (3.22) for edges and equation (3.23) for components we 
get for every element of the first path  the needed capacity 
requirements:

 = 737 500 op./sec,  =  = 430 000bit/sec,

 = 123 750 op./sec,

for every elements of the forth path :

= 7 207 500 op./sec,  = 13 120 000 op./sec,

= = 17 660 000bit/sec.

and so on.

Then using equation (3.24) we get resource requirements for all elements 
of DFGraph

=  = 737 500 op./sec,

= 7 207 500 op./sec,

 = 123 750 op./sec,

 = 13 120 000 op./sec,

 = =  =  = 430 000 bit/sec,

 =  =  =  = 17 660 000 bit/sec.

Now we are ready to decide mapping task (4.1) - (4.5).

DCSystem shown in Figure 6.4 can be represented by complete (full) 
graph, in which every node (computer) is connected with all other nodes 
(computers). But taking into account given placements of sources and 
sinks and also the capabilities of computers to realiaze only particular 
types of components we can construct a relevant graph of DCSystem that 
simplifies the mapping problem decision. Such the relevant graph of 
DCSystem is presented in Figure 6.5. This graph is directed one and 
includes all possible placements of every component of DFGraph of 
particular DMMApplication in the DCSystem.

In Figures 6.6 - 6.8 possible mapping decisions are represented.

p1

C1
1( ) 29.5v = C9 1( ) C11 1
( ) 21.5v =

C4
1( ) 50.3v =

p4

C3
4() C7 4( ) 2883 = v = C5 4( ) 5248v =

C13
4() C15 4( ) 883v =

C1 C2 29.5v =

C3 C7 C8 2883 =
= v =

C4 50.3v =

C5 C6 5248 = v =

C9 C10 C11 C12 21.5v =

C13 C14 C15 C16 883v =


39

Audio-Video sink-component

Audio source-component

Video source-component

Audio-Video source-component

Audio sink-component

Audio mixer-component

Video mixer-component

Audio-video mixer-component

Video sink component

Audio source-computer Audio sink-computer

Video source-computer

Audio-Video source-computer

Video sink-computer

Audio-Video sink-computer

Audio mixer-computer

Video mixer-computer

Audio-video mixer-computer

GRAPHICAL SYMBOL NOTATIONS FOR COMPUTER TYPES

GRAPHICAL SYMBOL NOTATIONS FOR COMPONENT TYPES

Figure 6.1. Graphical symbol notations for component and computer types

40

C6

C7

C8

C1

C2

C3

C4

C5

Audio streams

Figure 6.2. Data flow graph

Video streams

Mixed streams

1

2

3

4

5

6

9

10
11

14

15

16

Figure 6.3. Numbered Data flow graph

Audio streams

Video streams Mixed streams

7

8

12

13


41

Global Network (GN)

1 2 3

9 10

13

14

Local Network 1 (LN1)

Local Network 2 (LN2)

Local Network 3 (LN3)

Local

(LN4)

C1
C2 4

C3

C7

6

7

8
Network 4

C8

12

11

5

shadow in symbol denotes that the computer is yet processing

Figure 6.4. Distributed computer system

other applications

42

7

C1

C2

C3

1

3

9

4

11

5

12

C7

C8

13

8

Figure 6.5. Relevant graph of DCSystem

Figure 6.6. One of possible mapping result

1

3

9

C4+C5+C6

5

LN1

LN1

C7

C8

LN1+GN+LN3

13

8

C1

C2

C3

LN1+GN+LN4 LN2+GN+LN1

43

1

3

9

C4

C5+C6 13

8

4

12

C7

C8

C1

C2

C3

LN1

LN1

LN2+GN+LN3

LN1+GN+LN3

LN3

LN3+GN+LN4

Figure 6.7. One of possible mapping result

1

3

LN1

LN1

C7

13
C1

C2 5

LN2+GN+LN1 C8

12

9

C3

LN1+GN+LN3

LN1+GN+LN3

LN2+GN+LN3

8
C6

C4+C5

Figure 6.8. One of possible mapping result

LN3+GN+LN4

44

7. CONCLUSION

In this paper, we examined problem of mapping of DMMApplication to 
DCSystem. We have formulated the problem and for some tasks got 
efficient solutions. But a set of models and solution procedures 
mentioned above must be yet developed.

For the support and for making this work possible for me I would like to 
thank Prof. K.Rothermel. I express my thanks to I.Barth, G.Dermler, 
T.Helbig for their useful comments and discussions. I thank research and 
administrative staff of Distributed Systems Department for their help in 
my work.

APPENDIX. GENERAL TASK STATEMENT of DFGraph MAPPING to DCSystem

Let's consider the statement of mapping task core that are shown by 
dotted line figure at the top of Figure 4.1.

THERE ARE GIVEN: A 4-tuple , where

FG specifies a DFGraph of DMMApplication,

Q specifies QoS requirements of DMMApplication,

 specifies a relevant part of DCSystem,

SF specifies relations between DFGraph components and DCSystem elements.

- , where

 is a directed weighted acyclic graph representing data flows between 
source(s) and sink(s) of a DMMApplication such that C is a set of  
components and E is a set of the  edges connecting components and 
representing a partial order on the components;

 is a set  of K media paths (or simply paths) in DFGraph (for each path 
QoS requirements are given). Here we use termin ?path? as it is defined 
in section 3.1;
 is a set of component types such that  is a type of component  of data 
flow graph ;  is a set of components requests of the computer resources. 
(for instance, , where  is number of CPU operations nedeed for 
DMMApplication program execuation,  is the size of nedeed main memory,  
is the size of needed disk memory,  is a number of input-output 
operations during CPU execution of DMMApplication program,  is average 
size of data trasmitted between main memory and disk memory per one 
input-output operation of DMMApplication program);  is a set of values  
indicating the number of bytes of data message

FG Q Gs SF , , , ( )

GS

FG GD W CT RC FD ,
,
, ,
( ) =

GD C E ,
( ) =
NC C =
NE E =

W pm m 1 K ,
=
,
{ } =

CT tc c C ?
,
{ } = tc c C ? GD RC RCc c C ?
,
( ) =
RCc NOc VMc VDc NI Oc VIOc ,
,
,
,
( ) = NOc

VMc VDc NI Oc VI Oc

FD de e E ?
,
{ } = de

45

(paket) that must be transmitted through the edge  from the precedent 
component to its successor . Here a message is a data unit associated 
with QoS requirement;

-  is a set of QoS application requirements for K paths such that  is a 
set of m-th subgroup QoS requriments namely delay , throughput , loss 
rate  and jitter  (the list of QoS parameters depends on 
DMMApplication);

-  is an directed weighted graph representing a DCSystem such that P is 
a set of  computers that are accessible for CINEMA's management and L is 
a set of the  links connecting computers. Here a link is a logical 
element which can represent actual subnetwork(s) that's nodes and links 
are not accessible for CINEMA's management;

-  , where  is a mapping function :  returning a computer  on which a 
source- or sink-component  is placed. (We assume assignment of source- 
and sinkcomponents to computers are given);  is a function :  that 
returns a set of component types  which are

able to be mapped to computer  (that means, does computer configuration 
have needed devices and resources to realize multimedia functions of 
certain component type?);  is a set of cost functions  for computers  to 
which components  are being mapped with a set of QoS parameters ,  for 
links  to which edges  are being mapped with a set of QoS parameters ,  
is a set of QoS parameter values accordingly for computer  to which 
component  is being mapped and for link  to which edge  is being mapped. 
For example , where t - message delay, h - throughput, r - loss rate and 
j - jitter in computer p to which component c is being mapped.

Note, that cost functions  are dinamic ones that are construct for 
available resources of a computer and a link and therefore must be 
corrected every time after placing any component or edge of DFG. If, for 
example, computer p doesn't have available resources then .

ASSUMPTIONS: 1. A cost functions of  must be tractable, that is 
monotonic, ... 2.

ADDITIONAL NOTATIONS Let  denote the function-pair that define the pair 
of precedent and successor components correspondingly that are connected 
by edge e in data flow graph .

Let  denote the set of all mapping double-functions, , such that :  in 
accordance with function : , and : . Function

returns the computer  on which a component  is executed in the mapping 
defined by  such that component type  belongs . (Assignment of

e

Q Qm Tm Hm Rm Jm , , , ( ) = m 1 K ,
=
,
( ) =

Qm Tm Hm Rm Jm

GS P L ,
( ) =
NP P =
NL L =

SF g c FS , ,
( ) =
g g W P fi g c ( ) p = P ?
c W ?

c c P tc c
?
fi c p ( )

p P ?

FS sp c qpc ,
( ) p P ?
, c C ?
,
{ } s l e qle ,
( ) l L e E ?
,
?
,
{ } ,
{ } =

sp c qpc ,
( ) p P ?
, c C ?
,
{ } p P ? c C ?

qpc
sl e q l e ,
( ) l L e E ?
,
?
,
{ } l L ? e E ?

q l e
qpc qle , p P ?
c C ? l L ? e E ?
qpc t h r j , , , ( ) =

sp s l ,

sp - =

FS

cp r e ( ) c s u e ( )
,

GD
M Y ,
( ) ? y ,
( ) ? C P fi c P tc c
?
fi y E L 0 ?
fi
? M ?

? c
( ) p P ?
= c C ?
? tc c p ( ) tc c p ( )
?
,


46

some components  to the same computer  is permitted). Function returns 
the link  between computer  and computer  in actual distributed system; 
edge  is mapped to the link . If some components (for example,  and ) 
are mapped to the same computer  (that is ), then a link of DCSystem is 
not needed and the function returns null-element 0, that is

DECISION PROBLEM Given an 4-tuple , find a mapping double-functions such 
that

subject to

,

where  are functions correspondingly of delay, loss rate, throughput and 
jitter, defined for path . A result of mapping problem decision may be 
presented by a subgraph  of  such that

. Graph  represents a transport graph from sources to sinks of group 
association  in actual distributed computer system. In particular, graph  
can be consist of only one node that represents a computer  to which all 
components  of data flow graph  are mapped. (Note that the question of 
possible cycles in , when source(s) and sink(s) are mapped to the same 
computer, must be considered.)

THE DECISION OF MAPPING PROBLEM NEEDS:

- to define delay , loss rate , throughput  and jitter  for every path .

-  to elaborate models for computing end-to-end QoS parameters;

- to construct models for computing QoS parameters of every separate 
computer  to which components  are being mapped, for different 
schedules. It is necessary to take into consideration such a fact if the 
computer executes already other applications then

c C ? p P ? y Y ?
y e
( ) l L ?
( ) = p1 ? = c1 e ( )
( ) p2 ? = c2 e ( )
( ) e E ? y e ( )
c1 c2 p P ?
? c1 ( ) ? c2 ( ) p =
= y Y ?

c1 c2 C ? c1 ( )
\
?
,
" ? c2 ( ) p e E c1 \
?
$
, cpr e ( ) c2 , csu e ( ) y e ( )
fi 0 = = = = =

FG Q Gs SF , , , ( ) ? y ,
( ) M Y ,
( ) ?

min ? y ,
( )

s? c ( ) c q? c ( )c ,
( )

c C ?
?

? sl c q l e ,
( )

l y e ( )
?
( ) ?
e E ?
( ) ?
+
? ? ? ? ? ? ? ? ? ? ? ö

Tm j c ( )
{ } c W ?
, m ( ) Tm m ,
? 1 K ,
=

Rm j c ( )
{ } c W ?
, m ( ) Rm m ,
? 1 K ,
=

Hm j c ( )
{ } c W ?
, m ( ) Hm m ,
? 1 K ,
=

J m j c ( )
{ } c W ?
, m ( ) Jm m ,
? 1 K ,
=

T m Rm Hm Jm , , , m 1 K ,
=
G P L ,
( ) =
GS P L ,
( ) =

W P ? ? c ( ) c C ?
,
{ } P ? L , l y e ( ) e E ?
,
( ) ?
{ } L ?
= = G W Wm ?
=
G
p P ? c C ? GS G

Tm Rm Hm Jm m 1 K ,
=

p P ?
c C ?


47

these applications will influence the parameters of a new application as 
well as a new application placed on the computer may change the 
parametersof already executed applications. The models must take into 
account multiprogramming and multiprocessor performance modes of 
computers, profiles of tasks, schedule algorithms and so on. Each time 
when the mapping problem must be decided for a new application it's 
necessary take into consideration the current load states of every 
computer of distributed system. The current load state of computer 
system is changed each time when one of DMMApplications is terminated, 
one new DMMApplication request is received, a failure happens and so on;

- to determine the cost functions  for computers and  for links  
depending on QoS requirements ;

- to develop algorithms for solving the division of QoS requirements 
among computers and links (communication resources) of multipoint route 
that should optimize the cost of DMMApplication. It is so named QoS 
requirement horizontal mapping problem;

- to elaborate a method for QoS requirement mapping between different 
protocol layers - QoS vertical mapping problem;

- to develop multipoint routing algorithms taken into account 
peculiarities of DMMApplications;

- to develop models such that fault tolerance can be taken into 
consideration.

sp c qpc ,
( ) p P ?
, c C ?
,
{ }

sl e qle ,
( ) l L e E ?
,
?
,
{ } qpc q l e ,


48

REFERENCES

[Anderson,93] D.P.Anderson, ?Metascheduling for Continuous Media?, ACM 
Trans. Computer Systems, Vol. 11, No. 3, August 1993, pp. 226 - 252. 
[Blum, 94] C.Blum, ?Synchronization of Live Continuous Media Streams?, 
Proc. The 4th Open Workshop on High Speed Networks, Brest, September 7 - 
9 ,1994: Universität Stuttgart, pp. 234 - 240. [Campbell,94] A.Campbell, 
G.Coulson, D.Hutchison, ?A Quality of Service Architecture?, Computer 
Communication Review, ACM SIGCOMM, Vol. 24, No 2, April 1994, pp. 6 - 
27.
[Cruz,91a] R.L.Cruz, ?A Calculus for Network Delay, Part 1: Network 
Elements in Isolation?, IEEE Trans. Information Theory, Vol. 37, No 1, 
January 1991, pp. 114 - 131. [Cruz,91b] R.L.Cruz, ?A Calculus for 
Network Delay, Part 2: Network Analysis?, IEEE Trans. Information 
Theory, Vol. 37, No 1, January 1991, pp. 132 - 141. [Dimitrijevic, 94] 
D.D.Dimitrijevic, B.Maglaris, R.R.Boorstyn, ?Routing in Multidomain 
Networks?, IEEE/ACM Trans. Networking, Vol. 2, No. 3, June 1994, pp. 252 
- 262. [Fuhrt,94] B.Fuhrt, ?Multimedia Systems: An Overwiew?, IEEE 
MultiMedia, Vol.1, No.1, Spring 1994, pp. 47-59. [Gagin, 91] A.A.Gagin, 
O.V.Klimovsky, ?A Method for Computing Steady-state Reliability Indexes 
of a Network with Limited Repair?, Microelectron. Reliab., R-31, No. 5, 
1991, pp. 985 - 999. [Hagin,94] A.A.Hagin, ?Performability, Reliability, 
and Survivability of Communication Networks: System of Methods and 
Models for Evaluation?, Proc. of the 14th International Conference on 
Distributed Computing Systems, Poznan, Poland June 21-24 1994, IEEE 
Computer Society Press, 1994, pp. 562 - 573. [Kapelnikov,89] 
A.Kapelnikov, R.R.Muntz, M.D.Ercegovac, ?A Modelling Methodology for the 
Analysis of Concurrent Systems and Computations?, J. Parallel and 
Distributed computing, No. 6, 1989, pp. 568 - 597. [Leopold,92] 
H.Leopold, A.Campbel, D.Hutchison, N.Singer, ?Towards an Integrated 
quality of Service Architecture (QoS-A) for Distributed Multimedia 
Communications?, High Performance Networking 92, IFIP, 1992,pp. D2-1 - 
D2-13. [Kleinrock,76] L.Kleinrock, ?Queueing Systems: Computer 
Applications?, Vol.2, N.Y.: John Wiley & Sons, 1976, p. 549. 
[Maisonnaux,94] H.Maisonnaux, P.Cocquet, M. Gagnaire ?New Concepts for 
Multipeer Communications?, Proc. 4th Open Workshop on High Speed 
Networks, Brest, September 7-9, 1994, pp.103-109. [Narasimhan,94] 
S.Narasimhan, ?Locating concetrators in a computer network with multiple 
coverage for terminals?, Computer Communication, Vol. 17, No. 2, 
February 1994, pp.94 -102. [Norman, 93] M.G.Norman, P.Thanisch, ?Models 
of Machines and Computation for Mapping in Multicomputers?, ACM 
Computing Surveys, Vol. 25, No. 3, September 1993, pp. 263 - 302. 
[Ramanathan,92] S.Ramanathan, P.V.Rangan, M.M.Vin, T.Kaeppner, ?Optimal 
Communication Architectures for Multimedia Conferencing in Distributed 
Systems?, Proc. The 12th International Conference on Distributed 
Computing Systems: Yokohama, Japan, June 9- 12,1992, pp. 46 -53. 
[Rothermel,94] K.Rothermel, I.Barth, T.Helbig, ?CINEMA- An Arhitecture 
for Config-

49

urable Distributed Multimedia Applications?, Tech. Report, 
Fakultaetbericht #3/1994, Universität Stuttgart, April 1994. p.20. 
[Schulzrinne,92] H.Schulzrinne, ? Issues in Designing a Transport 
Protocol for Audio and Video Conferences and other Multiparticipant 
Real-Time Applications?, Internet-Draft, Dec. 1992. [Stainov,94] 
R.Stainov, ?Betriebsystemaspecteb des Realzeitscheduling in 
multimedialen Systemen?, Tech. Report #12/1994, Universität Stuttgart, 
September 1994, p. 40. [Stamoulis,94] G.D.Stamoulis, M.E.Anagnostou, 
A.D.Georgantas, ?Traffic source models for ATM networks: a servey?, 
Computer Communications, Vol. 17, No 6, June 1994, pp. 428 - 438. 
[Stirpe,92] P.Stirpe, E.Pinsky, ?Performance Analysis of an Asynchronous 
Multi-rate Crossbar with Bursty Traffic?, Computer Communication Review, 
Vol. 22, No. 4, October 1992, pp. 150 - 160. [Tindell, 92] K.W.Tindell, 
A.Burns, A.J.Wellings, ?Allocating Hard Real-Time Tasks: An NP-Hard 
Problem Made Easy?, J. Real-Time Systems, No. 4, 1992, pp. 145 - 165. 
[Wang,94] Z.Wang, ?Analysis of Burstiness and Jitter in Real-Time 
Communications?, Proc. SIGCOMM'93 ?Communications Architectures, 
Protocols and Applications?, Computer Communication Review, Vol. 23, 
No.4, October 1993, pp. 13-19. [Woo,94] M.Woo, N.U.Qazi, A.Ghafoor, ?A 
Synchronization Framework for Communication of Pre-orchestrated 
Multimedia Information?, IEEE Network, January/February 1994, pp. 52 - 
61.