Masaryk University
Faculty of Informatics
}w¤§¨!"#$%&123456789@ACDEFGHIPQRS`ye|
Self-organizing Collaborative
Environments
Miloš Liška
A thesis submitted in partial fulfillment
of the requirements for the degree of
Doctor of Philosophy.
January 2010
Brno, Czech Republic
Except where otherwise indicated, this thesis is my own original work.
Miloš Liška
Brno, January 2010
Acknowledgements
My thanks and gratitude go first to prof. Ludˇek Matyska and especially to Petr Holub, my
advisors, whom I owe much and without whom I would not be able go through this work.
It was my pleasure to work with Hana Rudová who contributed with her expertise to the
theoretical part of this work. I would also like to thank to Eva Hladká for her support.
On my way I have met many other people whom I was working with and whose contribution
needs to be highlighted here. It was a pleasure to work with the staff and students
I met in the Laboratory of Advanced Networking Technologies. In no particular order
I would like to thank especially to David Antoš, Lukáš Hejtmánek, Jirka Matela, Jirka Denemark,
Tomáš Rebok and Dalibor Klusáˇcek. Thanks guys, I really appreciate having the
opportunity working with you.
I have also to mention the great opportunity to work with a number of people elsewhere
who have contributed to various aspects of this work. An invaluable experience was my stay
at the Louisiana State University and the MCNC. Here I have to mention especially Andrei
Hutanu, Ravi Paruchuri, prof. Gabrielle Alen, prof. Thomas Sterling, Yufeng Xin and Gigi
Karmous-Edwards. My thanks go also to folks from Internet2, especially to Andy Lake and
John Vollbrecht. I appreciate the contributions and advices from all of you really a lot.
I am deeply grateful also to my parents who have never given up to support me on all
my journeys even though it was not always easy. Last but not least I would like to express
my special thanks to my wife Terka. She would know what for.
M. L.
This work has also been kindly supported by a research intent `Optical Network of National
Research and Its New Applications" (MŠM 6383917201) and "Mathematical and Engineering
Approaches to Developing Reliable and Secure Concurrent and Distributed Computer
Systems" (GA CR GD102/09/H042).
Abstract
This thesis deals with issues of collaborative environments orchestration. We show that manual
orchestration of collaborative environments is not only extremely cumbersome but also
fails to address especially the needs for robustness and resiliency. We present a middleware
called CoUniverse, designed for automated user-empowered building and orchestration of
real-time collaborative environments to work primarily on high-speed networks with true
high-bandwidth applications such as uncompressed high-definition video. The system is designed
for unreliable experimental infrastructures and therefore its operation relies heavily
on self-organizing principles.
Latency-sensitive data distribution and media streaming is a part of many networkcentric
applications. When bitrate of media streams is comparable to capacity of the links,
the implicit additive assumption no longer holds and the system needs to feature sophisticated
planning of the media streams transmissions over individual network links. Based on
our previous experience with interactive high-quality media distribution and orchestration
of collaborative environments, we are proposing an automated planning of media streams
distribution in environments where bandwidth of streams is comparable to network link
capacities. We have successfully adopted methods of constraint programming to deal with
this problem. We provide an algebraic description of the media streams planning problem
and show its complexity. Based on the algebraic description of the problem we propose a
comprehensive constraint model. To formulate the model, a new variant of the link based
model for traffic placement problem is applied. An evaluation of the implemented solver is
presented on a number of experimental problems to show effectiveness of the formulation
and proposed constraints.
In this thesis we also address the problem of automated user-empowered control of dynamic
network infrastructures to satisfy the demands of orchestrated collaborative environments.
To do so we take advantage of the advanced features of Internet2 Dynamic Circuit
Networks (DCN) and the CoUniverse self-organizing application middleware. We augment
the CoUniverse middleware capabilities by interfacing with DCN enabled network infrastructures
and automatically control the circuit allocation, deallocation and modifications
based on collaborative environments and application needs.
We have carried out a proof of the concept implementation of the CoUniverse middleware
to verify the above mentioned concepts. We provide an evaluation of the most important
concepts of the CoUniverse middleware with respect to its ability to establish and provide
self-organization features (especially self-healing) to the collaborative environments.
We also evaluate the scalability of the CoUniverse middleware analysing the size of the collaborative
environments it is able to orchestrate taking into the account the interactive nature
of the collaborative environments in question. More importantly, we have already used the
prototype implementation of the CoUniverse middleware to orchestrate various types of col-
v
laborative environments and applications in a number of demonstrations and events. Most
of these demonstrations we also discuss in this thesis featured CoUniverse deployment on a
network infrastructures spanning USA and Europe.
Contents
1 Introduction and Motivation 1
1.1 Motivational Use Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Thesis Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Related Work 7
2.1 Self-organization in Data Networks . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.1.1 Self-organization and Collaborative Environments . . . . . . . . . . . . 9
2.1.2 Tools and Environments for Synchronous Collaboration . . . . . . . . 10
2.1.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1.4 Media Streams Routing and Placement in Collaborative Environments 12
2.1.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Advanced Networks Orchestration . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 OptiPuter LambdaGrid . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Enlightened and G-lambda . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.3 Internet2 DCN and ION . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.4 AutoBAHN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2.5 User Controlled Lightpaths . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2.6 MANTICORE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.7 ARGON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.8 DRAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2.9 Phosphorus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.2.10 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 CoUniverse Design and Architecture 25
3.1 CoUniverse Design Key Concepts . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Self-organization in CoUniverse . . . . . . . . . . . . . . . . . . . . . . 26
3.1.2 Separation of the Collaborative Environment and Networking Infrastructure
Orchestration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.3 Decomposition of Collaborative Environments Orchestration Problem 27
3.2 CoUniverse Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2.1 Multiverse and Collaborative Universes . . . . . . . . . . . . . . . . . . 28
3.2.2 Control Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.3 Data Planes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3 Collaborative Universe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3.1 Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
vi
CONTENTS vii
3.3.2 Network Topology Representation . . . . . . . . . . . . . . . . . . . . . 31
3.3.3 Media Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3.4 Application Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.5 Security Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4 Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.1 Nodes and Media Applications Monitoring . . . . . . . . . . . . . . . . 40
3.4.2 Network Monitoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Dynamics of the CoUniverse Middleware . . . . . . . . . . . . . . . . . . . . . 44
3.6.1 CoUniverse Peer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6.2 Application Group Controller . . . . . . . . . . . . . . . . . . . . . . . . 45
4 Media Streams Planning Problem 51
4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.1 Network Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.2 Lambda Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1.3 Media Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.1.4 Media Distributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.1.5 Stream Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.2 Media Streams Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3 Media Streams Planning Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4 Media Streams Planning Problem Expressed Using Constraints . . . . . . . . 59
4.5 Complexity of Media Streams Planning Problem . . . . . . . . . . . . . . . . . 63
4.5.1 0­1 Multiple Knapsack problem . . . . . . . . . . . . . . . . . . . . . . 63
4.5.2 Relaxed Media Streams Planning Problem with Streams Quality Maximization
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5.3 Relaxed Media Streams Planning Problem with Network Links Latency
Minimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.6 Simplifying the Media Streams Planning Problem . . . . . . . . . . . . . . . . 67
4.6.1 Simplified Media Streams Planning Problem with Reflector Type Media
Distributors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.6.2 Simplified Media Streams Planning Problem with Precomputed Matching
of Consumers and Producers . . . . . . . . . . . . . . . . . . . . . . 70
4.6.3 Network Links Elimination . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.7 Plan Deployment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5 Evaluation of the CoUniverse Concepts 76
5.1 Control Plane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.1.1 Implementation Details . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.1.2 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.1.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.2 Media Streams Planning Problem Solver . . . . . . . . . . . . . . . . . . . . . . 80
5.2.1 Simplified MSPP as a Constraint Satisfaction Problem . . . . . . . . . . 80
5.2.2 Search Heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.2.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.2.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
viii CONTENTS
5.3 Network Orchestration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3.1 Implementation details . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.3.2 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.3.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6 Applications and Demonstrations 98
6.1 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.1.1 Advanced Multi-party Videoconferencing . . . . . . . . . . . . . . . . 98
6.1.2 High-Quality Immersive Multi-Party Distant Learning . . . . . . . . . 99
6.1.3 Stereoscopic Video Transmissions for Medical Applications . . . . . . 101
6.1.4 Interactive Remote Visualizations of Large Data Sets . . . . . . . . . . 102
6.1.5 Collaborative Film Postprocessing . . . . . . . . . . . . . . . . . . . . . 103
6.2 Demonstrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.2.1 GLIF 2007 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6.2.2 SuperComputing'07 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6.2.3 Winter 2009 ESCC/Internet2 Joint Techs . . . . . . . . . . . . . . . . . . 106
6.2.4 Spring 2009 Internet2 Member Meeting . . . . . . . . . . . . . . . . . . 107
7 Conclusions 109
7.1 Thesis Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
7.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
A Correctness of the CSP Formulation of the MSPP 112
List of Abbreviations 116
Bibliography 118
Vita 129
Author's Selected Publications 130
List of Figures
2.1 Internet2 DCN infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.2 GÉANT2 AutoBAHN infrastructure. . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1 CoUniverse architecture overview. . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Network topology representation in the CoUniverse architecture. . . . . . . . 33
3.3 Lambda link state diagram. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4 Dynamics and signaling in collaborative universe. . . . . . . . . . . . . . . . . 46
4.1 Nodes, interfaces and network links example. . . . . . . . . . . . . . . . . . . . 52
4.2 Example of end-to-end network links over shared network infrastructure. . . 53
4.3 Lambda links and physical network infrastructure example . . . . . . . . . . 54
4.4 Stream link. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5 Media streams distribution tree. . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.6 Network topology for the relaxed MSPP . . . . . . . . . . . . . . . . . . . . . . 65
5.1 Match Maker evaluation topologies . . . . . . . . . . . . . . . . . . . . . . . . 87
6.1 HPC class setup at Laboratory of Advanced Networking Technologies, Masaryk
University . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
6.2 Network topology scheme for the Spring 2007 HPC class run. . . . . . . . . . 101
6.3 Stereoscopic video projection at Laboratory of Advanced Networking Technologies,
Masaryk University . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
6.4 Remote interactive color grading session. . . . . . . . . . . . . . . . . . . . . . 104
6.5 Visualisation of media streams transmissions planned for the GLIF 2007 videoconferencing
environment. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
6.6 Visualisation of media streams transmissions planned for the SuperComputing'07
distant learning environment. . . . . . . . . . . . . . . . . . . . . . . . . 106
6.7 Network topology scheme for Winter 2009 ESCC/Internet2 Joint Tech demonstration
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.8 Network topology scheme for the Spring 2009 Internet2 Member Meeting
CoUniverse demonstration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
A.1 Types of nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
ix
List of Tables
5.1 JXTA based control plane performance. All times are measured from t0 = 0 ms
being the start of the CoUniverse peer. . . . . . . . . . . . . . . . . . . . . . . . 78
5.2 P2Ps based control plane performance. All times are measured from t0 = 0 ms
being the start of the CoUniverse peer. . . . . . . . . . . . . . . . . . . . . . . . 79
5.3 JXTA message passing performance. . . . . . . . . . . . . . . . . . . . . . . . . 79
5.4 P2Ps message passing performance. . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5 Properties of evaluated topologies. . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.6 Evaluation of different variable and value ordering heuristics. . . . . . . . . . 89
5.7 Evaluation for 1:n-s topologies with runtime in milliseconds. . . . . . . . . . . 90
5.8 Evaluation for 1:n-rm topologies with runtime in milliseconds. . . . . . . . . . 90
5.9 Evaluation for 1:n-r topologies with runtime in milliseconds. . . . . . . . . . . 91
5.10 Evaluation for m:n-r topologies with runtime in milliseconds. . . . . . . . . . 91
5.11 Starlight ­ TAMU circuit allocation request processing times. . . . . . . . . . . 96
x
Chapter 1
Introduction and Motivation
Contemporary computer networks featuring high bandwidth links and low data transmission
latencies provide infrastructures allowing to build advanced interactive collaborative
environments and distributed applications in an ad-hoc manner. In our work in the field of
collaborative environments we have been pursuing especially for highly interactive multipoint
environments [69] and also component based design allowing for flexibility and variety
of different applications of such environments [67,69,72,73].
To provide the desired level of interactivity and limit end-to-end latencies of the user
communication these environments often build upon streams of high-definition uncompressed
media [51, 105, 119] or media with low-compression ratios [118]. Bitrate of such a
media streams however becomes comparable even to capacities of current highest-speed
network links. Thus a careful planning of media streams transmissions over individual network
links is necessary in order to achieve reasonable performance of the whole system or
even to make it work at all.
A component based architecture [21,62] is a usual concept of collaborative environments.
The component based architecture becomes important and useful especially in case of highend
collaborative environments where each component performs its limited but resources
intensive task. On the other hand setting up and orchestrating such component based collaborative
environment is cumbersome when done manually and the number of components
being high. Also, when such an collaborative environment is orchestrated manually it is virtually
impossible to achieve any adaptivity to changing networking conditions, robustness
or resilience.
The process of collaboration among peer-humans itself involves some element of selforganization
[7]. Thus it is not surprising that the self-organization principle has also been
followed by many virtual collaborative environments and distributed applications to some
extent. Majority of the systems is however fairly static in a sense of reacting to different
events occurring both inside and outside of the system. For example media tools, that are
relying on multicast, are depending on its availability. H.323 tools are usually able to react to
changing available network bandwidth by adjusting media compression parameters--but if
the central interconnecting multipoint control unit (MCU) breaks, there is usually not much
to do except for terminating the call.
Recent development of systems like VRVS/EVO or Skype (see Related work in Chapter
2) introduces another level of autonomous behavior. Users can either influence some
system parameters manually which is followed by some automatic reconfiguration, or the
1
2 CHAPTER 1. INTRODUCTION AND MOTIVATION
system attempts to react automatically to some events, e.g., by choosing another reflector for
data distribution among participants of a videoconference.
These approaches are however insufficient for high-end interactive collaborative environments
and distributed applications, where the bandwidth required by media streams
transmissions is comparable with the capacity of the network links and thus where implicit
additive assumption ("sending one more stream on a link does no harm to the whole system")
is no longer valid. The number of components and the desiderata for robustness and
resilience of the environment which is based on naturally error-prone components and network
call for self-organization of the whole environment. We have already argued for the
necessity of careful automated planning of media streams transmissions over network links
to address both deployment of media streams transmissions over particular network links
and the self-organization aspect of the collaborative environment.
Another aspect of the self-organizing collaborative environments and applications is
how much power should be given to their users. Holub, Hladká et al. (e.g., [67]) have
argued in favor of user-empowered approach to the largest extent that is possible. Proposed
self-organizing system should also follow this paradigm and utilize various schemes
of organization that do not require any administrative privileges over nodes, application
components or network infrastructure components. This approach can be extended further
in a way that allows users to modify behavior of the system.
The next major challenge is to configure, administrate and orchestrate the network infrastructure
based on existing networking resources to fulfill the demands of particular advanced
collaborative environment or application. Traditional network infrastructures are
rigidly configured by their administrators and support only applications that are aware of
the network environment. Especially with deployment of optical networks and optical circuits
in the network environment, it is necessary to reconfigure optical network components
for specific purposes of end user applications. The reconfiguration involves physical optical
circuits, switches, machines and last but not least the application components and its parameters.
The traditional approach requires coordination among users and all network administrators,
who are usually responsible for just their local part of the whole infrastructure,
via e-mails, phones or videoconferences. Obviously, the management task quickly becomes
very complicated with large network infrastructure, multiple administrative domains and
number of involved local administrators.
The user empowered approach helps to reduce the number of persons involved in the
network infrastructure configuration and orchestration as well as it makes the end users
work independent of the local network infrastructure components administrators. A possible
solution for the use empowered approach is a virtualization of the network infrastructure.
The virtualization helps to deal with concurrent conflicting user demands on the
network infrastructure configuration and functionality as well as to deal with possible misconfigurations.
To provide the necessary level of network infrastructure virtualization and
allow for the user empowered approach to the network infrastructure orchestration an advanced
networking features like lambda-services [133] are needed. In recent years several
initiatives emerged to create a new network services which introduces a necessary flexibility
and "programmability" to the traditional network infrastructures. Such initiatives may be
utilized to allow for dynamic changes of service, resources allocation and reconfigurations
of the network infrastructure according to the user (and his applications) demands to create
a single and coherent environment.
1.1. MOTIVATIONAL USE CASES 3
1.1 Motivational Use Cases
At the iGrid workshop held during the GLIF'05 meeting we have demonstrated an advanced
ad-hoc high-definition low-latency multi-party videoconferencing environment [69]. To provide
both high-quality and high level of interactivity the videoconferencing system was built
upon transmissions of uncompressed high-definition media. To accommodate the high demands
posed by processing of the uncompressed high-definition streams (acquisition, distribution
and displaying) we have designed the videoconferencing application to be based
on components doing just limited tasks. This approach however quickly leads to necessity
for controlling large number of components. A multi-party videoconferencing environment
with three participants would be built on at least a dozen of components when considering
just the acquisition, distribution and displaying of video streams. Each component has
to be properly configured so that the data distribution between the components provide
a reasonable functionality (i.e., the participants of the videoconference can see and talk to
each other). Also, the configuration of the components has to be done carefully so that the
bandwidth demands of uncompressed high-definition streams distribution do not exceed
the capacity of the underlying network infrastructure. With rising number of components of
the application it is very hard to configure and control them manually in a reasonable time
scope. Manual configuration and control of the components can be indeed solved by scripting
of the process. This approach is however extremely inflexible and does not provide any
level of resiliency. In case of any failure of the underlying network infrastructure or some of
the components a new script must be created which is equivalent to the manual orchestration
of the whole environment. For an interactive application like videoconference a delay
(lag) in order of minutes imposed by the manual reconfiguration of the environment may be
hard to accept.
Our iGrid experiment comprised three participating sites spanning USA and Europe:
iGrid premises at University of California, San Diego (UCSD) campus, Masaryk University/CESNET
in Brno, Czech Republic, and Louisiana State University (LSU) in Baton Rouge.
All sites were connected using three dedicated optical circuits meeting at StarLight, Chicago,
each coming from one participating site: Optiputer1 circuit from UCSD in San Diego, circuit
from LSU in Baton Rouge over Louisiana Optical Network Initiative (Loni)2 and National
LambdaRail (NLR)3 and a circuit from Brno spanning CzechLight4 and NetherLight5 networks.
The network infrastructure spanning five administrative domains was provisioned
statically and configured manually for the purposes of our iGrid demonstration. The provisioning
of such a network infrastructure required coordination of number of network administrators
in each administrative domain. The coordination was done over phone calls, instant
messaging, and videoconferencing. In this way the provisioning of network resources was a
matter of at least weeks. This is obviously extremely inconvenient especially when considering
that we have demonstrated an ad-hoc built videoconferencing environment. Finally,
the network infrastructure provisioned manually also lacks any resiliency.
The motivation of the work presented in this thesis are not confined only to the above
described videoconferencing scenario but includes interactive collaborative environments
1http://www.optiputer.net/
2http://www.loni.org/
3http://www.nlr.net/
4http://czechlight.cesnet.cz/
5http://www.netherlight.net/
4 CHAPTER 1. INTRODUCTION AND MOTIVATION
in other areas such as telemedicine or distant learning. In [73] we have described an experiment
utilizing the above described videoconferencing environment to create a distributed
virtual classroom. The experiment showed that high-definition uncompressed media or media
featuring low compression ratios can provide a basis for interactive and immersive collaborative
environments. On the other hand, as we have attempted to provide a production
level distant learning class service, this experiment also highlighted the need for automatically
configured and orchestrated collaborative environments and also measures to provide
resilience to such environments.
1.2 Thesis Contributions
The main goal of this thesis is to study ad-hoc collaborative environments and present benefits
which can be brought by employment of self-organization principles into the area. In
these terms we study especially possibilities of automated orchestration of component based
collaborative environments. Since we consider collaborative environments featuring uncompressed
or low-compression media with high-bandwidth demands we also study possibilities
of automated network infrastructures configuration and orchestration for the specific
purposes of the collaborative environments. In this context we focus on advanced network
infrastructures providing lambda-services and propose benefits of their integration with collaborative
environments. Based on our findings we propose a theoretical framework to address
these issues. As our work is strongly motivated by the needs of real-world collaborative
environments, we present a novel collaborative environments middleware named
CoUniverse and its architecture which is based on above mentioned framework to demonstrate
its features and benefits. We claim the CoUniverse middleware to provide the following
features:
* Automated establishing and orchestration of ad-hoc collaborative environments and applications
­ Ad-hoc in this context means that users are about to establish and use the
environment or application immediately. Establishing such environments can not be
planned in advance, thus also the usage of resources to satisfy the demands of the
environment or application must rely on actual state of the infrastructure.
* Mechanisms for self-organization of the application components ­ To provide the desired
self-organization for the orchestrated environments and applications CoUniverse employs
mechanisms which allows for automated orchestration of the application components
as well as automated orchestration of the underlying network infrastructure.
* Self-organizing overlay network for data transmissions ­ We design the environments orchestrated
by CoUniverse to provide multipoint to multipoint data distribution. We
deal with multipoint data distribution and data placement between the components
of the collaborative environments or applications using virtual overlay networks on
top of existing network infrastructures. Solving the problem of data placement in the
overlay network in an automated way provides a basis for automated orchestration of
the environment components.
* Support of legacy applications and components ­ To allow for as much flexibility of terms
of what functions are provided by the environments orchestrated by the CoUniverse
1.3. THESIS STRUCTURE 5
middleware CoUniverse is able to orchestrate components of the collaborative environments
or applications regardless if the components are aware of being controlled
by the middleware or not. In other words, CoUniverse is able to encapsulate thirdparty
applications and tools being the components of the orchestrated environments.
Such a claim holds for both software and hardware based components as real collaborative
environments can be based on variety of hardware devices.
* Support of data transmissions with bitrates close to the network links capacity ­ To provide
as high level of interactivity within the orchestrated collaborative environments
and applications, we suppose the collaboration being built upon transmissions of uncompressed
media streams or media streams featuring low compression ratios. Such
streams transmissions may demand bandwidth close to the capacity of individual links
of the network infrastructure and thus require careful planning. To address this issue
we formulate a new media streams planning problem. We also show different variants
of this problem in order to address different aspects of the media streams planning in
context of collaborative environments we consider.
* Network orchestration based on the application demands ­ In the CoUniverse middleware
we opt for automated user empowered control of the network infrastructures based
on the demands of orchestrated collaborative environment or application. The aim
of this approach is to overcome the complications of manual management of network
infrastructures spanning multiple administrative domains and traditionally necessary
involvement of the network administrators.
* Resilience ­ CoUniverse provides resilience (i.e., ability to recover from failures of both
application and network infrastructure components) to the orchestrated environments
and applications. Since we claim to support legacy environments and applications
we also do not require them to provide any features in terms of their resiliency (e.g.,
components of the collaborative environments or applications do not have to provide
any interfaces for their instrumentation).
* User empowered approach to applications and network orchestration ­ CoUniverse is designed
so that the orchestration of applications and their components as well as the
orchestration of the network infrastructure does not rely on the users having any administrative
rights or not. Such a claim has a number of consequences which are discussed
throughout the thesis.
* A number of pilot applications ­ We also propose a number of applications to demonstrate
the contributions of both concepts and the prototype implementation of the CoUniverse
middleware.
1.3 Thesis Structure
The rest of this thesis is organized as follows: In Chapter 2 we provide an overview of the
state-of-the art in the areas related to this thesis topic. We present an overview of existing
collaborative environments and applications especially looking on their self-configuration
and resilience (ability to recover after infrastructure or environment component failure) capabilities.
We also present state-of-the art methods and systems for network infrastructure
6 CHAPTER 1. INTRODUCTION AND MOTIVATION
orchestration namely those dealing with control and configuration of circuit based optical
networks. Last but not least we touch the area of self-organization in networks as a general
concept.
In Chapter 3 we provide the key concepts of the CoUniverse design followed by a discussion
of the details of CoUniverse middleware architecture, describing its building blocks,
functionality and also limitations.
Chapter 4 provides a theoretical model of collaborative environments and applications
orchestration using CoUniverse middleware. In this chapter we also discuss the media
streams planning problem in CoUniverse and provide details on its complexity. Since the
media streams planning in CoUniverse is a fairly complex problem we discuss possible
methods to simplify it in order to be able to implement and to deploy its solution for a
real world collaborative environments and applications.
In Chapter 5 we evaluate a proof of concept implementation of CoUniverse while deploying
a collaborative environments (e.g., videoconferencing systems) and distributed applications
(e.g., remote distributed visualizations) on a real networking infrastructures.
Chapter 6 presents number of applications which may benefit from being orchestrated by
the CoUniverse middleware. In this chapter we also describe real CoUniverse deployment
scenarios and the demonstrations where we have showcased and verified the CoUniverse
capabilities and properties.
The thesis ends with conclusions and discussion of future work presented in Chapter 7.
Finally, the last chapter is followed by list of bibliography referenced through the thesis,
summary of authors achievements, a list of selected publications and references to the author's
publications.
Chapter 2
Related Work
In this chapter we deal with the contributions of our work we have claimed in the introduction
to this thesis from the perspective of related work and projects. We first provide an
explanation of the term "self-organizing" as we claim the CoUniverse to be self-organizing
and providing self organization properties to the orchestrated collaborative environments.
We thus provide in-depth discussion of these properties.
Later in this chapter we deal with existing collaborative environments and their components
looking at their features in terms of self-organization and automated orchestration. In
terms of automated orchestration of the components, we aim especially on solving the problem
of media streams distribution between the components of the environment in an automated
manner. In this context we also take into the account distribution of media streams
with bandwidth demands close to the capacity of individual network links as well as the
latency constraints imposed by the fact that we are dealing with interactive collaborative
environments. This leads us from traditional schemes such as multicast or overlay networks
to the area of explicit planning of traffic placement in data networks.
Finally, we deal with existing approaches to automated orchestration of network infrastructures.
Demands introduced by the collaborative environments we deal with (high bandwidth
utilization and low network latencies demands) and the fact that we opt for the userempowered
approach where possible means that the collaborative environments should be
built upon network infrastructures providing advanced lambda-services such as on-demand
provisioning of optical circuits with dedicated bandwidth. We thus discuss orchestration of
network infrastructures which provide such advanced features.
2.1 Self-organization in Data Networks
The concept of self-organization has been studied to a great extent especially in the context
of sensor and actor networks (SANETs) and wireless sensor networks (WSN) [13, 40, 100].
However, the self-organization concepts discussed for the SANETs are generic and thus may
be also successfully exploited for self-organization of the collaborative environments. Moreover,
when considering self-organization in the context of collaborative environments we do
not have to take into the account the limitations of the SANET components (usually very low
computational performance) and thus we do not have to limit ourselves only to the methods
considered to achieve self-organization in SANETs.
7
8 CHAPTER 2. RELATED WORK
Dressler [40] provides a revision of self-organization properties and methods as well
as a discussion of limitations which are inherent to the self-organization in many systems.
According to Dressler the self-organizing systems show especially the following properties:
* Absence of external control ­ One of the most important characteristics of the selforganizing
systems is completely distributed control. Each component participating
on the control acts based on local decisions only (i.e., autonomous components collaborate
on the global goal).
* Adaptation to changing conditions ­ A feature inherent to all self-organizing systems is
their ability to adapt to changing environmental conditions. Components of the selforganizing
system incorporate interactions with the environment and the system behavior
is changed in accordance with the actual state of the environment.
* Global order and local interactions ­ The development of a global order (i.e., the functionality
the self-organizing system provides) from a local information and interactions is
another feature that renders the process of controlling the system self-organizing. Local
interactions between the components replace especially coordination and control
paradigms such as global state information.
* Complexity ­ Dressler argues that complexity is not only an inherent property of selforganizing
systems but also arises from the global demands and goals as in the selforganizing
systems usually multiple objectives are to be met simultaneously.
* Control hierarchies ­ Control in the self-organizing systems is often arranged in multiple
nested levels manner. Such hierarchic arrangement allows for more efficient specification
and description of methods and techniques used for self-organization. The centralized
control paradigm utilization is not allowed at any level of the control hierarchy
(even on the top level).
* Dynamic operations ­ Self-organization of the system evolves dynamically over a period
of time. In this context any self-organization process can be seen as a search algorithm
which looks for the best system state with respect to the current state of the environment
which are subject to change over time.
* Redundancy ­ The inherent resistance to faults of the self-organizing systems also introduces
the need of system components redundancy. If the system components become
unavailable due to their failures, other components take over their functionality.
* Self-maintenance ­ Self-maintenance is in direct relation with the redundancy of the
self-organizing systems. However, the redundancy means the ability of the system to
tolerate the faults of its components while the self-maintenance refers to the system
being able to repair its global order (i.e., maintain the global goal the self-organizing
system is designed to meet).
The properties that enable self-organization were also summarized by Heylighen [63] in
a similar manner:
* Global order from local interactions which also imposes the necessity of the collaboration
between individual components and subsystems of the self-organizing system to
achieve the global goal.
2.1. SELF-ORGANIZATION IN DATA NETWORKS 9
* Distributed control together with absence of any external or internal agent responsible
for directing or controlling the system.
* Robustness and resilience which represent general characteristics of the self-organizing
system.
* Non-linearity which refers to the fact that that the effects and outputs of self-organizing
systems can not be described by simple cause and effect relations and may be hard to
predict.
* Organizational closure referring to the fact that the system is closed against any influence
from the outside. Heylighen also argues that a pure self-organizing system must not
show any level of organizational hierarchy which is common in complex distributed
systems. Interestingly enough these requirements seem to be in contradiction with the
control hierarchy property of the self-organizing systems given by Dressler.
Self-organization and other self-* properties such as self-configuration, self-adaptation or
self-healing is also being studied in context of autonomic computing systems. The work in
this area has been pioneered by IBM's autonomic computing initiative [47,82]. The research
done in this area has been eventually surveyed e.g., by Dobson et al. in [38].
The following provides a general overview of autonomic systems architecture as discussed
in [38]. The architecture of autonomic self-organizing system, in general consists of
autonomic elements, each performing a fixed function and interacting with other elements,
possibly in a very dynamic environment. An autonomic element is commonly viewed as
being comprised of one or more managed elements (also referred to as functional units) that
perform the element's operational function and an autonomic manager (management unit)
that controls the managed elements' configuration, inputs, and outputs.
Autonomic systems form a feedback loop. The system collects information from a variety
of sources including traditional network sensors and reporting streams but also including
higher-level device and user context. These are analyzed to construct a model of the evolving
situation faced by the network and its services with this model used as a basis for adaptation
decisions. The impact of the decisions can then be collected to provide a basis for the next
control cycle.
2.1.1 Self-organization and Collaborative Environments
Although the conjunction of self-organizing system properties and ad-hoc collaborative environments
seems to be well-founded and valid, not much can be found in the literature
concerning this topic. Balakrishnan [9] in his position paper pinpointed especially the necessity
of introducing self-organization properties to collaborative environments and outlined
some goals of collaborative environments self-organization which are similar to those we
have specified in the introduction to this work.
A preliminary notion of self-organizing collaborative environment is presented by Tianfield
in [128]. Tianfield proposes a multi-agent virtual collaboration environment (MAVICE)
aimed on collaborative decision making in the e-medicine area. Architecture of the MAVICE
system is based on a network of autonomic agents which form decision loops based on
provided medical evidence eventually providing the diagnosis or asking the users for new
10 CHAPTER 2. RELATED WORK
inputs. However the architecture of the environment is presented only at conceptual level
without providing details on how is the self-organization of the system carried out.
LaCOLLA provides a fully decentralized middleware for building collaborative applications
that enables general purpose collaborative functionality based on the resources provided
by group participants only [97, 98]. The LaCOLLA middleware follows the peerto-peer
paradigm for the data and message distribution and pays special attention to the
self-organization of its components. The components are being controlled by a user agent
(UA) which is a part of so called LaCOLLA peer. Each UA controls the applications using
functions and from ApplicationSideAPI. This however means that the applications to be orchestrated
with LaCOLLA have also to implement the methods of the ApplicationsSideAPI.
Therefore LaCOLLA can not encapsulate and control legacy applications which in our case
we claim to do. Examples of applications orchestrated by the LaCOLLA environment include
especially instant messaging, internet forums of file sharing. The biggest drawback of
LaCOLLA when considering our needs is thus the fact that LaCOLLA was designed for orchestration
of collaborative environments which feature asynchronous communication only.
In [24] the authors present an architecture for coordinating multiple self-management
systems. The architecture builds upon a Rainbow framework which is a dynamic selfadaptation
framework that monitors and incrementally adapts a target running system using
the system's architectural model [22, 23, 50]. The architectural model basically specifies
the components of the system, interactions between the components, methods of component
monitoring and constraints related to the components which must hold to achieve the
integrity of the system. The presented approach is evaluated on collaborative environment
comprised of videoconferencing system which supports the users with different videoconferencing
applications such as MBone tools1 or NetMeeting across heterogeneous network
infrastructure. The Rainbow framework provides mechanisms for the collaborative environment
to adapt at run time in order to accommodate varying resources and system errors. The
Rainbow framework however addresses especially the placement of collaborative environment
components on the nodes and communication dependencies between them in terms
of types of media streams which are individual components able to process. The bandwidth
aspect of media streams remains not addressed.
2.1.2 Tools and Environments for Synchronous Collaboration
Video and audio are essential means of effective collaboration experience [88]. A traditional
concept of collaborative environments thus among other services includes videoconferencing
[120]. Videoconferencing is basically built upon controlled distribution of video and
audio streams transmissions. According to our experiences and understanding the same
video and audio transmissions may be basis for many distributed applications which include
some form of human collaboration (e.g., remote distributed visualizations, remote imagery
for medical purposes or distributed color grading in the movie industry). Thus, we
consider the same sort of tools, applications and systems to be usable in both cases.
A comprehensive overview of videoconferencing tools and systems can be found e.g.,
in [135] by VVC (Voice, Video and Collaboration) Task Force of TERENA. Among these tools
we would furthermore consider just those not violating the user empowered approach (i.e.,
1http://mediatools.cs.ucl.ac.uk/nets/mmedia/
2.1. SELF-ORGANIZATION IN DATA NETWORKS 11
a local administrator is not necessary to manage the tools or systems for the end users). We
aim the discussion of the systems especially at their self-organization and resilience abilities.
As mentioned in the introduction, some extent of self-organization is usually built into
the all but the simplest collaborative tools. H.323 and SIP tools [53, 129], which are considered
a sort of industrial standard as a videoconferencing platform, can accommodate
changes in available link capacity by changing compression parameters of the media streams.
One of the most advanced environments to deal with these problems is VRVS/EVO [45,
46]. EVO is a closed source system allowing to orchestrate a real-time, component based
collaborative environments while trying to achieve reliability and robustness through monitoring
of the environment and reacting to the detected changes. To address the stream
distribution between the components EVO uses an overlay network with software agents
which provide monitoring of the environment, route the media streams and reroute them in
case of network failure.
Similar features in terms of streams distribution, resiliency and robustness are provided
also e.g., by Skype2. Skype builds upon transmissions of low-bandwidth streams distributed
using a peer-to-peer network. Utilisation of the peer-to-peer paradigm allowed by handling
only low-bandwidth media streams solves the streams distribution problem and provides
both self-organization and reliability. Unfortunately Skype itself is not intended to provide
multipoint collaboration.
Another well-established platform is provided by AccessGrid [26,123] which allows for
automated orchestration of its components. The components necessary to build videoconferencing
environment are configured and invoked automatically when a user enters some
AccessGrid venue. The distribution of media streams is addressed again using multicast or
an overlay network with packet reflectors that route the media streams between the components
of the environment. In terms of resiliency AccessGrid however provides only limited
capabilities which moreover have to be initiated manually e.g., by selecting unicast media
streams transport instead of multicast. Isabel, an application for real time collaboration with
a flexible floor control [34, 110, 111] has a similar properties in terms of streams distribution
between the components of the environment using either multicast of overlay network
using flow servers (multipoint control units). Very similar features are provided also by
the ConferenceXP3 project aimed at creating collaborative environments for distant learning
purposes [5].
There is also a host of standalone tools available that may be employed as components
building up collaborative environments and applications. Examples include tools and systems
such as UltraGrid [69,106] or iHDTV4 that provide both high-quality and low end-toend
latency transmissions of video and audio. A more general purpose tools such as the
VideoLan Client (VLC)5 with wide range of capabilities in terms of audio and video transmissions
may be also considered in the context of collaborative environments. The range
of the tools and systems to be employed to build the collaborative environments is not limited
to the domain of video transmissions. We may also consider high-quality audio transmissions
such as Jacktrip6, tools for desktop sharing such as Virtual Network Computing
(VNC) [113] and others.
2http://www.skype.com/
3http://cct.cs.washington.edu/
4iHDTV, University of Washington, http://www.washington.edu/ihdtv/
5http://www.videolan.org/
6https://ccrma.stanford.edu/groups/soundwire/software/jacktrip/
12 CHAPTER 2. RELATED WORK
2.1.3 Discussion
A common feature of all these mentioned environments and tools (namely VRVS/EVO,
Skype and Isabel) and the major difference in comparison with our approach is that they
are not intended to work with high-bandwidth media streams. Using low-bandwidth usually
highly compressed media streams provides inferior collaboration experience in terms of
interactivity in comparison to the collaboration based on streams of uncompressed media or
media featuring low compression ratios. However, more important from the point of view
of our aims, is the fact that for low-bandwidth media streams it is not necessary to consider
planning of the media streams transmissions over the network links as the additive assumption
still holds. Thus the streams distribution in above mentioned environments can rely
either on multicast or peer-to-peer paradigm.
Moreover the above mentioned environments have no or just very limited capabilities
in terms of supporting legacy application components to build the collaborative environments.
With these environments it is not possible to modify or augment their functionality
by simply changing the utilized tools as the tools are either directly built in or very tightly
coupled with the environment. This is another major difference to our approach as we claim
to support legacy applications and tools to build the functionality the collaborative environments.
In this context the only exception out of the discussed environments is AccessGrid.
AccessGrid allows to encapsulate other tools as its components and invoke them when entering
some AccessGrid venue. In this way it is possible to augment AccessGrid with a new
functionality. For example low-latency videoconferencing using the UltraGrid tool may be
encapsulated within the AcceessGrid environment [52].
Interesting features in terms of the collaborative environments we consider are provided
by tools we have mentioned at the end of Section 2.1.2. These tools and systems provide
a range of features unmatched by the previously mentioned environments. These are especially
high-definition video transmissions and low latency communications in case of the
UltraGrid of iHDTV systems or broad range of audio and video processing features in case
of the VLC tool. These tools are however stand alone usually providing only point-to-point
transmissions of audio, video or other data. As such these tools do not provide any selforganization,
automated orchestration or features towards resiliency which are to some extent
provided by the above discussed complex collaborative environments.
Generally we understand that users of the collaborative environments may require functionality
and properties unmatched by existing collaborative environments. Therefore we
opt for support of legacy tools and applications to be encapsulated in the collaborative environment,
providing them with automated orchestration and resiliency. In this way the
functionality of the collaborative environment is not limited just to what is provided by the
built-in and usually tightly integrated tools as in the case of traditional collaborative envi-
ronments.
2.1.4 Media Streams Routing and Placement in Collaborative Environments
A paramount aspect of earlier discussed collaborative environments and tools is the problem
of streams distribution between components of the environment. If this problem is solved
automatically and the information on streams routing is known for each component it is
possible to orchestrate the components in an automated way. In the context of collaborative
2.1. SELF-ORGANIZATION IN DATA NETWORKS 13
environments the problem of multipoint streams distribution is traditionally tackled using
multicast, overlay networks with application level routers or peer-to-peer networking.
Media streams placement then refers to the fact that the distribution of multiple media
streams between the components of the collaborative environments may pose significant
demands with respect to especially available bandwidth of shared network links. Also, to
create an interactive collaborative environment the media streams have to be transmitted
along network links with as low latency as possible. Taking these two constraints into the
account leads us to the area of traffic placement planning.
Multicast
In a multicast communication a single data source transmits user data (media streams in our
case) to multiple receivers [140,141]. The major feature of the multicast is that the stream is
transmitted from the source to all receivers over any link at most once.
Multicast is a service provided at a network layer in the traditional ISO/OSI model [76].
Multicast-capable routers create distribution trees that control the path the stream takes
through the network to be delivered to all receivers. The two basic types of multicast distribution
trees are source trees and shared trees. The simplest form of a multicast distribution
tree is a source tree whose root is at the source producing the stream and whose branches
form a spanning tree through the network infrastructure to the receivers. Because this tree
uses the shortest path through the network, it is also referred to as a shortest path tree (SPT).
Shared trees unlike the source trees that have their root at the source, use a single common
root placed at some chosen point in the network. Both SPT and shared trees do not contain
loops and the streams are replicated only where the tree branches.
The multipoint to multipoint communication scheme we are pursuing can be emulated
through simultaneous use of several multicast communications. A multicast communication
is then established for each component of the environment which is producing some stream.
There are basically two reasons why multicast may not be suitable for media streams
distribution in the environments we propose. First of all multicast is a service provided by a
network layer (i.e., a layer­3 service). That means the deployment and control of multicast
enabled infrastructure depends on network administrators who usually consider multicast
being of lesser importance in comparison with the routing of unicast traffic 7. This however
disqualifies multicast to be used for multipoint routing in our environments as we are pursuing
an user-empowered solutions. Further discussion on why network-native multicast is
not a user-empowered solution and why its virtualization, e.g., using overlay networks, is
needed, can be found in [67].
Second, availability of multicast in large networks is often problematic [39]. The issues of
multicast deployment and its limited availability were summarized e.g., by Diot et. al in [37].
The main issues presented by Diot et al. are the complexity of multicast management, limited
multicast availability in multiple domain networks which are often built using diverse
technologies and its very limited availability in high speed networks.
Except for the previously presented issues, a discussion on multicast performance can
be also found in the literature [41]. Authors of the study analyzed the performance of the
7This is also evidenced by shift to overlay networks using multicast emulation based on application level
routers (packet reflectors) in many collaborative communities using AccessGrid, ResearchChannel iHDTV, or
Microsoft ConferenceXP. There are also other good reasons to implement overlay networks, e.g., for userempowered
NAT traversal for collaborative environments [68] or per-user processing.
14 CHAPTER 2. RELATED WORK
multicast for small conferences and suggested that supporting latency-sensitive applications
may not be feasible using plain multicast.
Overlay Networks
The overlay networks are based on traditional unicast routing and transmissions inherent to
the IP networks. Other functionality provided by the overlay networks (such as the multipoint
routing or resiliency) is implemented on application level of the ISO/OSI model. This
approach has been pioneered by the Resilient Overlay Networks (RON) [3,4] architecture.
The RON architecture proposes an application-level packet routing allowing the endhosts
and applications to create path through the network that traditional Internet routing
cannot make use of, thus improving their end-to-end reliability and performance. The RONs
are built upon application-level software routers, tools to measure the quality of paths between
the participating nodes (including available bandwidth, latency or packet loss rate)
and mechanisms interpreting these measurements in order to make decisions on routing of
the data between the end-hosts. Andersen et al. argued in [4] that end-host controlled Resilient
Overlay Networks provide a good framework for distributed applications to transmit
data with greater robustness and higher performance over the wide-area Internet.
A number of similar approaches based on the general idea of the overlay networks providing
features and services not available in the underlying physical network infrastructure
or improving its performance can be found through the literature. The following examples
demonstrate the several possible usages of the overlay networks:
* MBone overlay network [93] emulates multicast functionality in underlying network
infrastructures without multicast support,
* Virtual Private Networks (VPN) [43] are built to allow for confidential communication
over non-private networks,
* Content Delivery Networks (CDN) such as Akamai8 use the principles of overlay networks
to improve the performance of content delivery for specific applications such as
video streaming,
* projects such as Detour [117], X-Bone [130] or Violin [79] provide tools for creating
general purpose overlay networks over the Internet infrastructure.
Issues of advanced network services deployment (like those of the Multicast we have
discussed in the previous section) show that building collaborative environments on top of
application level routers based overlay networks may be an appropriate scheme [27,78]. This
has been also evidenced by a number of collaborative environments and applications using
this approach. We have already mentioned AccessGrid, iHDTV, or Microsoft ConferenceXP.
Other examples include MBone Tools as used with the overlay networks principles based
user-empowered virtual multicast in [65]. In our previous work we have also exploited the
advantages of the overlay networks to provide efficient media streams distribution [69, 73]
or secure communication [68] for the collaborative environments we have been dealing with.
8http://www.akamai.com/
2.1. SELF-ORGANIZATION IN DATA NETWORKS 15
Peer-to-peer Model
Using the peer-to-peer (P2P) model for self-organization of the environment components
and automation of the traffic routing between the components is widespread and generally
accepted paradigm [1,6,91]. The peer-to-peer paradigm is used to build an overlay network
above the physical networking infrastructure. In comparison to earlier discussed approach
to build the overlay network the P2P paradigm does not require the existence of dedicated
application level routers and servers.
Many systems and environments based on the P2P paradigm were proposed and implemented
for a number of applications. The traditional applications using the peer-to-peer
based overlay networks are file sharing featuring systems and environments such as Napster9,
Gnutella [114], Pastry [116], Freenet10 Kazaa11 or BitTorrent [109].
In the area of collaborative environments the most blatant example is perhaps the earlier
discussed videoconferencing system Skype. However, due to its closed source and obfuscated
nature not much can be said about how the peer-to-peer paradigm is used to provide
the automated routing and traffic placement between the Skype clients [16,18].
Several other examples could be found in literature utilizing peer-to-peer networks in
the area of collaborative environments. Civanlar et al. present a P2P architecture for multipoint
videoconferencing [28, 29]. In their architecture an heuristic approach is used to find
minimal spanning trees which are used for media streams distribution between the videoconferencing
components. The spanning trees are further optimized minimizing the latency
of the streams distribution. Unfortunately the heuristic proposed by Civanlar et al. does not
guarantee to find a solution of the streams distribution even if such a solution exists.
A completely different method of solving the media distribution in the collaborative environment
using the P2P architecture is presented by Horiuchi et al. in [70]. Their approach
to the media streams distribution is based on construction of a single stream distribution tree
over the P2P network. In such tree the peers with higher available bandwidth are moved
close to the root of the tree and the tree is periodically updated as the peers connect and
disconnect. The multipoint streams distribution is achieved so that the stream produced by
each speaker is first to the root of the tree and then to the other peers in the tree (cf. the multicast
shared tree). Authors claim their approach to be highly scalable. This is true in terms
of number of peers which can connect and be organized within the P2P network. However
routing of all streams through the root of the tree clearly introduces an unbridgeable bottleneck
when considering streams with bandwidth demands close to the capacity of network
links in our case.
ZIGZAG is a P2P system developed for single source media streaming to a potentially
very large group of participants on the Internet [131]. It proposes an efficient failure recovery
and control protocol for maintaining the streams distribution tree against network failures
and unpredictable client behaviors. In addition ZIGZAG addresses the minimization of the
end-to-end latency between the source of the stream and the clients while building the distribution
tree.
There is a number of other works utilizing the P2P model for media streams routing
for the purposes of media streaming e.g., [134], [104] or [61]. The major difference of these
works in comparison to our needs is however that we need to cope with basically multipoint
9http://www.napster.com/
10http://freenetproject.org/
11http://www.kazaa.com/
16 CHAPTER 2. RELATED WORK
to multipoint streams distribution as there are more stream sources and more receivers in our
scenarios and media streams featuring bandwidth demands comparable to the capacity of
network links.
Traffic Placement Planning
The environments and systems mentioned earlier in this section basically tackle only the
routing aspect of the traffic placement (i.e., methods to find the mere routes between the
components of the environment). Our approach however requires transmissions of media
streams with bandwidth demands close to the capacity of individual network links. Therefore
the capacity constraints must be considered together with the routing problem. This
leads us to the area of data transfers planning in the networks with respect to capacity constraints
and bandwidth utilization. Since we are not aware of other works concerning explicit
planning of media streams transmissions in collaborative environments we provide an
overview of works dealing with planning of data transmissions over the network infrastructure
in other areas.
The base model for planning of data transmissions was formalized by Ahuja et al. [2].
In their work they deal with multi-commodity flow problem which concentrates on flow
of different commodities over the network. A comprehensive survey on variety of planning
problems and approaches to their solutions in the area of computer networks was also
provided by Simonis in [121]. Except for the application placement problem which deals with
planning of batch-jobs over nodes in the network, Simonis studies the path placement, bandwidth
on demand and network design and capacity planning problems which deal with planning
and assigning paths over a network infrastructure to a demands (data transmissions) under
the capacity constraints of the network. As for the path placement problems Simmonis considers
two of its variants. A demand acceptance problem variant deals with choosing which
demands to satisfy using limited network resources and a very closely related traffic placement
problem where a whole fixed set of demands has to be planned over available network
resources. There are three basic models formulated for the path placement problem and its
variants:
* link-based model where the demands are being planned over individual network links,
* path-based model where each demand is being planned over an end-to-end path between
two nodes,
* node-based model where a set of succeeding nodes in the network is being sought for
each demand (data transmission).
A number of approaches and methods was identified to solve the problems summarized
by Simonis. These approaches and methods are mostly being based on heuristics based on
paths searching in graphs [92, 138], operations research methods [2], constraint programming
[138, 148, 149] or even resolving of workflows [85]. Also various hybrid approaches
combining constraint programming or integer programming with local search [80,87] or Lagrangian
relaxations [102,103] are being considered in the literature.
All these problems are somewhat related to automated building of overlay networks
for media stream transmissions in collaborative environments we are considering. However,
Simonis in his categorization of planning problems in data networks does not consider
2.1. SELF-ORGANIZATION IN DATA NETWORKS 17
multipoint distribution of the demands (media streams produced by components the environments
in our case) which is an important aspect of collaborative environments.
In the rest of this section we provide several examples of the above discussed problems
and models emerging in various application areas. While the path placement problem considers
ad-hoc planning data transfer demands over the network links, the goal of the bandwidth
on demand problems is to schedule data transfers in some given time period [121].
This problem is sometimes decomposed to planning and scheduling stage, where the planning
stage is not taking the time domain into the account. In this way the bandwidth on
demand problem becomes related to the path placement problem and its variants. Such a
decomposition is considered e.g., by Zerola et al. [148,149]. In their work a link-based model
of the path placement problem is considered for scheduling of transfers of large data sets
produced by Relativistic Heavy Ion Collider12. In [84] and [85] a closely related problem
is solved in the context of data transfers scheduling for the Digital Palomar Sky Survey13,
video processing, or large data transfers in computational Grid environments. Still, in all
these works only the path placement problem is being considered without taking any multipoint
data distribution into the account.
A problem of multipoint streams distribution appears in the area of building overlay networks
to emulate the native multicast [145]. In this context the authors solve the application
placement problem [121] where the goal is to place a set of applications on severs in the
network. In combination with path searching algorithms, the authors are able to schedule
the placement of multicast trees over the network infrastructure. However, this work again
does not consider bandwidth constraints posed by transmissions of streams with bandwidth
demands close to the capacity of the network links.
2.1.5 Discussion
A number of collaborative environments (e.g., AccessGrid, Isabel, ConferenceXP and others)
is built upon utilization of multicast media streams distribution scheme as it provides sort of
a natural mean of synchronous media distribution. We have however shown that using multicast
for the collaborative environments we consider is problematic. Therefore we consider
other media distribution schemes based on overlay networks.
Two different approaches to building overlay networks that overcome the issues of native
multicast exist, one built on dedicated application level routers while the other on peer-topeer
paradigm. The overlay networks based approach generally provides a robustness and
higher performance for media streams distribution in the collaborative environments. Although
utilization of the peer-to-peer model may seem most beneficial in order to solve the
media streams distribution and placement in the collaborative environments we opt for the
approach based on using dedicated software routers to build the overlay networks. The reason
is that the collaborative environments we consider are built upon transmissions of highbandwidth
media streams. Even distribution of such streams between the components of the
collaborative environments may be a task requiring high computing performance and therefore
the dedicated application level routers approach seems to be more reasonable. Also,
working with environments featuring streams with bandwidth demands are close to the capacity
of the network links generally limits redundancy in such environments. Therefore the
12http://www.bnl.gov/rhic/
13http://www.astro.caltech.edu/~george/dposs/
18 CHAPTER 2. RELATED WORK
peer-to-peer paradigm is not suitable for such environments as the peer-to-peer paradigm
generally relies on high redundancy of resources available in the environment.
A general issue of all these distribution schemes is that they rely on the additive assumption
holding implicitly. I.e., it is not necessary to consider the bandwidth demands of
the media streams because sending one more stream on a link does no harm to the whole
environment as capacity of all environment components is larger than the demands of a
single streams by an order of magnitude. On the other hand distribution of media streams
with bandwidth demands close to the capacity of individual network links is inherent to
the collaborative environments we consider. In such case the additive assumption clearly
no longer holds. Thus we consider the overlay networks approach combined with the explicit
traffic planning. Explicit traffic planning provides answer to automated placement of
media streams transmissions with bandwidth demands close to the capacity of individual
network links. In context of the explicit traffic planning it is necessary to note that the above
mentioned works and methods consider planning of streams transmissions creating isolated
communication paths while the collaborative environments we consider require planning of
streams transmissions over the network infrastructure creating multipoint communication
along set of distribution trees.
2.2 Advanced Networks Orchestration
Advanced network infrastructures have become available to support the bandwidth and
low-latency demands of many applications including collaborative environments. We further
describe such demanding collaborative environments and applications in Chapter 6.
Although much progress has been made in both network technologies and collaborative environments
areas the area which is still underdeveloped and not much studied is the link
between the collaborative environments and the underlying network technologies which
can make usage of the network infrastructures really effective.
We have claimed the network orchestration to be an integral feature of our approach to
overcome the issues of manual orchestration of the network infrastructures based on demands
of the collaborative environments and to provide the link between the collaborative
environments and the underlying network infrastructures14. Orchestration of network components
in order to provide advanced lambda-services (i.e., automated on demand provisioning
of network circuits with dedicated bandwidth) has been studied in context of many
international projects. These projects generally provide an abstraction and encapsulation of
network infrastructures and their resources into manageable, configurable and dynamically
provisioned entities in order to meet the demands of the applications and to optimize the
overall network utilization [126]. In this section we provide an overview of these projects
and discuss their outputs, properties and capabilities.
14Note that this approach has been also fostered by researchers working in the area advanced network infrastructures
(see e.˙,g., [126, 146]) in the context of the collaborative environments and applications we have
been working on [69, 73]. Similar conclusions can be also found e.g., in [96] for applications of the OptiPuter
infrastructure.
2.2. ADVANCED NETWORKS ORCHESTRATION 19
2.2.1 OptiPuter LambdaGrid
The OptiPuter15 is an infrastructure that tightly couples computational resources and optical
networks to support large scale of advanced applications such as collaborative data visualization
environments [107,112,125]. The goal of the OptiPuter research initiative is to enable
advanced applications with novel network infrastructures and control planes [96]. The OptiPuter
enabled infrastructure currently spans the networks across the USA (University of
California and Starlight) and Netherlands (NetherLight).
To link the applications and their demands together with the underlying network infrastructures
the OptiPuter software architecture was developed. A core of the OptiPuter
architecture is provided by the Distributed Virtual Computer (DVC) [25] which provides
an resources abstraction of so called "lambda-grid". The term lambda-grid denotes in context
of the OptiPuter infrastructure a combination of computational resources together with
lambda-services. In this context the goal of the DVC is to provide a co-allocation [11, 12,
31, 124, 127] of the resources according to the application demands. The interface between
the applications and the DVC is provided through an DVC API and DVC-ISL which is an
integrated specification language describing application resource requirements, including
traditional end resource specification and explicit high-level description of communication
resources [25,124].
2.2.2 Enlightened and G-lambda
The Enlightened [12] project together with the G-lambda16 initiative focussed on developing
a middleware for co-allocation of network and computing resources [126, 127]. The
activities of both teams were spanning resources within two administrative domains: one
being the network spanning KDDI R&D labs, NTT, NICT, and AIST controlled by the Glambda
project while the one controlled by Enlightened spanned MCNC17, Louisiana State
University (LSU), North Carolina State University (NCSU) and Renaissance Computing institute
(RENCI) networks. Both initiatives developed independent resource manager middleware
to allow applications to dynamically request (in-advance or on-demand) any type
of resource: computers, storage, instruments, and deterministic, high-bandwidth network
circuits [146]. The Enlightened team developed the Highly-Available Robust Co-allocator
(HARC) [94, 95] allowing to allocate the required resources for the selected time range by
using the HARC Compute Resource Managers (CRMs) and Network Resource Manager
(NRM). The CRM manages the computational resources and wraps existing job schedulers
like OpenPBS to provide the advance resources reservation capability. The NRM does the
network resource allocation by interfacing with the specific control plane, i.e., each domain
may have its own control middleware such as DRAGON or UCLP.
Users can interface HARC using either provided command line client or a Java client
API. The client API allows the users to discover resources and their descriptions from CRMs
or NRM, compose the resources requirements and query HARC to see if and when these
resources are free and most importantly overlay the results of multiple resource allocations
from different CRMs and NRM to see when all resource allocations are met.
15http://www.optiputer.net/
16http://www.g-lambda.net/
17http://www.mcnc.org/
20 CHAPTER 2. RELATED WORK
2.2.3 Internet2 DCN and ION
DCN ­ Dynamic Circuit Network ­ is a general term used to refer to any network that provides
on-demand lambda-services18. Internet2 is part of the DICE group, a collaboration
of international research and education networks including Internet2, GEANT2, ESNet and
CANARIE, that has developed an Inter-domain Controller Protocol (IDCP)19 that allows
users to automatically provision ad-hoc lambda services over networks spanning multiple
administrative and technology domains. A number of networks have already implemented
this protocol and are participating in a global infrastructure of interconnected networks that
can provide connections across each other. The Internet2 provides a production level network
service called ION (Intenet2 On-demand Network)20 built on top of the Internet2 DCN
infrastructure that supports IDCP. A picture showing the IDCP connected networks as of
SC08 in November 2008 is shown at Figure 2.1.
Figure 2.1: Internet2 DCN infrastructure
The IDCP protocol is Service Oriented Architecture (SOA) [42] based and allows thirdparty
applications that implement the IDCP to request resources from the network. In particular,
applications can request VLAN connections with dedicated bandwidth from a port
on any network to a port on any other connected network.
Note that the term DCN does not imply a particular network technology type or mechanism
for controlling a network. Projects to control DCN other than IDCP have also been implemented.
Efforts to standardize DCN protocols are underway at OGF and work to create
interoperability between existing implementations is taking place at GLIF (Global Lambda
Integrated Facility).
18Note that we use term DCN in the rest of this thesis as a general term describing dynamic network infrastructures
providing lambda-services. If we refer to the Internet2 implementation of DCN infrastructures we use
a term Internet2 DCN.
19http://www.controlplane.net/
20http://www.internet2.edu/ion/
2.2. ADVANCED NETWORKS ORCHESTRATION 21
The following provides a background on the IDCP for ION (see [139] for more details).
ION uses the open source OSCARS21 and DRAGON22 software to implement the IDCP.
Internet2 has collaborated together with Energy Science Network (ESnet) on providing a
suite of tools based on the OSCARS software [59,60] ­ especially an InterDomain Controller
(IDC) ­ used to handle the processing of IDCP application requests and interactions between
domains as needed. An important property of the IDC is the fact that it is being
deployed within each administrative domain to handle the orchestration of the domain using
the DRAGON software and to interact with IDCs in other domains on providing lambda
services across multiple domains. It also provides an API that can be used by application developers
wishing to integrate their software with a network using the IDCP. The DRAGON
software, developed by MAX, USC ISI East, George Mason University and Internet2, handles
the configuration of network hardware within a domain to meet the needs of the original
request. DRAGON creates a Generalized MultiProtocol Label Switching (GMPLS) [14,15] capable
optical core network within each domain. Network components which are not GMPLS
capable are integrated through their virtualization and the concept of Virtual Label Switch
Router (VLSR) which acts as a proxy and translates the GMPLS protocols into device specific
protocols allowing dynamic reconfiguration of non-GMPLS aware devices.
As shown in the diagram above, Internet2 ION peers with networks such as the U.S.
Department of Energy's (DOE) ESnet, GEANT2 in Europe, and various regional research
and education networks in the USA that have similar DCN capabilities. This allows for
on-demand network resources to be provisioned into sites around the globe.
2.2.4 AutoBAHN
AutoBAHN stands for the Automated Bandwidth Allocation across Heterogeneous Networks
developed by the GEANT223. AutoBAHN provides a dynamic circuit service which
addresses provisioning of circuits featuring dedicated bandwidth across different administrative
domains. The AutoBAHN enabled domains in Europe are depicted at Figure 2.2.
The features and architecture of the AutoBAHN service is in many of its aspects similar
to Internet2 DCN. The AutoBAHN infrastructure is based on Inter-Domain Manager
(IDM) responsible for operations related to circuit reservation across multiple administrative
domains. This includes especially inter-domain communication, negotiations on resources
availability between different domains and maintenance of the network topology. The IDM
provides a user interface in a form of web service and its description using the Web Service
Description Language (WSDL) [30]. In this way the IDM can be accessed using the
Simple Object Access Protocol (SOAP)24 which renders it usable to a wide range of applications.
Intra-domain resources used to build the end-to-end circuits are handled by the
Domain Manager (DM). The most important functionality of each DM is intra-domain path
finding, managing local domain network topology abstraction, monitoring or network resources
and handling resources reservation in time. The DMs are capable of orchestrating
either GMPLS, Multi-protocol Label Swithichg (MPLS) [8,33] or Carrier-grade Ethernet [83]
enabled network infrastructures within its respective administrative domains.
21http://www.es.net/oscars/
22http://dragon.east.isi.edu/
23http://www.geant2.net/
24SOAP W3c website: http://www.w3.org/TR/soap/
22 CHAPTER 2. RELATED WORK
Figure 2.2: GÉANT2 AutoBAHN infrastructure.
Also a close collaboration between the AutoBAHN and Internet2 and ESNet was established
enabling AutoBAHN to create circuit reservations with end points located in the
Internet2/ESnet domains in the USA, utilizing the combination of OSCARS and DRAGON
software.
2.2.5 User Controlled Lightpaths
User Controlled Lightpaths (UCLP) [144,150] is a Canarie25 configuration and provisioning
tool for fiber networks using web services. Third parties can concatenate cross connects
using variety of network links, routers and switches creating potentially very large network
which is fully under their control. The UCLP system design is based on Service Oriented
Architecture (SOA).
The primary purpose of the UCLP is the partitioning of the lightpaths and switches so
that they can be managed by third parties to create multiple virtual private networks sharing
a common network infrastructure. The outcome of this partitioning may eventually result in
an end-to-end lightpath. The defining characteristic of UCLP is that the user can reconfigure
the partitioned lightpaths and cross connects at each node resulting in an Articulated Private
Network (APN) [56]. The concept of APN can be extended beyond the physical network to
instrument devices, sensors, computers, and so on.
The UCLP model does not adhere to the user empowered paradigm. There are three
layers in the UCLP security model. A Physical Network Administrator is responsible for
provisioning the network and creating network resources (lightpath and interface Web Ser-
25http://www.canarie.ca/
2.2. ADVANCED NETWORKS ORCHESTRATION 23
vices) for the Articulated Private Network (APN) administrator. The APN administrator is
then responsible for creating the network configuration workflow for the users and/or subleasing
the resources or created network configuration to other APN administrators. The
users are allowed just to use the workflow created by the APN administrator but not to
modify the network topology or change the network configuration workflow.
In terms of interfacing with the UCLP infrastructure UCLP provides a graphical interface
with which the users can manipulate the resources managed by the UCLP system [101].
Although the primary UCLP user interface is based on GUI application its SOA based architecture
should allow the users to integrate the UCLP infrastructure control directly with
their own applications applications and tools.
2.2.6 MANTICORE
The MANTICORE [57] is a project carried out as part of the activities of the FEDERICA
FP7 European Project26 aimed at providing of a Web Services based Resource Management
System which offers a logical IP network. To achieve this goal MANTICORE uses an UCLP
based IaaS Framework (Infrastructure as a Service Framework) which enhances the original
UCLP framework adding especially the logical routing feature.
Generally MANTICORE pursues similar network provisioning use cases as the other
projects (UCLP, DCN, AutoBAHN). However, while these projects aim to provisioning of
low layer services i.e., on demand point-to-point circuits, the MANTICORE project aims to
provide multipoint-to-multipoint (IP) connectivity while guaranteeing the routing integrity.
2.2.7 ARGON
ARGON [10,11] a project of the German VIOLA testbed27 stands for Allocation and Reservation
in Grid-enabled Optic Networks. ARGON employs the GMPLS and MPLS protocols to
control the underlying network infrastructure in order to achieve dynamic allocation of circuits
with dedicated bandwidth. ARGON itself lacks the ability of multiple domains reservations.
To enable this functionality interfacing with other resources management systems
like UCLP, G-Lambda and DRAC is considered.
The interface to the ARGON system is provided through ARGON UI. The ARGON UI
is implemented as a web service and can be accessed using the SOAP protocol. Thus it
is possible to interface with the ARGON system in a way similar to interfacing with e.g.,
AutoBAHN.
2.2.8 DRAC
DRAC28 ­ the Dynamic Resource Allocation Controller is a commercial-grade system developed
by NORTEL29. DRAC provides a network abstraction and mediation middleware
platform, acting as an agent for network clients (users, applications, compute resource managers)
to negotiate and reserve appropriate network resources on their behalf. DRAC uses
26http://www.fp7-federica.eu/
27http://www.viola-testbed.de/
28http://www.nortel.com/drac/
29http://www.nortel.com/
24 CHAPTER 2. RELATED WORK
client's QoS requirements and pre-defined policies to negotiate end-to-end connectivity across
heterogeneous in support of ad-hoc or scheduled computing workflows.
2.2.9 Phosphorus
The aim of the Phosphorus project is to deliver advanced network services to Grid users
and applications interconnected by heterogeneous infrastructures [44]. Phosphorus, likewise
as the other projects, addresses the issues of enabling on-demand end-to-end network
services across multiple administrative and technological domains. Phosphorus leverages
existing network resources provisioning systems to provide policy based on-demand network
resources provisioning across different domains. To do so Phosphorus interfaces with
ARGON, DRAC and UCLP.
2.2.10 Discussion
All discussed projects and systems featuring network resources provisioning and network
components orchestration share some common features:
* Orchestration of the physical networking infrastructure is based on usage of MPLS or
GMPLS protocols and MPLS/GMPLS enabled network components. Some systems
allow for orchestration of other components through proxies.
* Interoperability across the systems and projects is also provided in order to allow for
orchestration of large network infrastructures across different administrative and technological
domains.
* User interfaces are provided through the means of Service Oriented Architecture and
web services. Some of the discussed systems also provide an API hiding the SOA
details.
From this point of view all these systems are theoretically interchangeable. There are however
two issues to be considered. The state of the implementation of these systems substantially
varies. Also, an important consideration is the span of the network infrastructures
over multiple administrative and technical domains which can be orchestrated using the discussed
systems. The later consideration becomes important especially when building large
collaborative environments over such network infrastructures. See Chapter 6 for illustration
of the collaborative environments we have been considering and the span of the network
infrastructures the environments have been built upon.
During a period of our work on applications of the collaborative environments we are
discussing in Section 6.1.2, we have been relying on manual provisioning of the network
resources using the Enlightened HARC co-allocator. Unfortunately the Enlightened project
is no longer facilitated and operational.
Chapter 3
CoUniverse Design and Architecture
To address the issues and problems discussed in the introduction and motivation of this
thesis we propose an application middleware called CoUniverse. In this chapter we first
discuss the key concepts and provide a theoretical framework for the CoUniverse middleware
design. We also provide a discussion and comparison with the concepts and methods
described in Chapter 2. Later in this chapter we provide an overview of CoUniverse middleware
architecture and discussion of its features. We first describe the CoUniverse logical
organization from a networking and application point of view. Afterwards, we focus on
monitoring and visualization aspects and finally we give an overview of operations and a
life cycle of environments or applications orchestrated by the CoUniverse middleware.
3.1 CoUniverse Design Key Concepts
A high-level overview of the CoUniverse architecture is illustrated at Figure ??. CoUniverse
architecture design focuses on the following major areas:
* providing self-organization and automated orchestration for collaborative environ-
ments,
* extensibility through incorporation/encapsulation of legacy applications and tools (even
those which do not support the middleware directly),
* support for collaborative environments featuring media streams with bandwidth demands
comparable to capacity of links (including advanced planning of data streams
transmissions over individual network links),
* automated control of the network infrastructure based on the needs of the orchestrated
collaborative environments,
* continuous adaptation on changing conditions based on built-in monitoring of nodes,
applications, and network infrastructure and mechanisms to deal with detected events,
* visualization of the environment for the users to make it understandable.
25
26 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
CoUniverse
Network infrastructure
Collaborative environment
Network
API
Encapsulated
application
Encapsulated
application
Encapsulated
application
{ Media streams
transmissions planning
Application
encapsulation
and
orchestration
Application
monitoring
Node
monitoring
Network link
monitoring
DCN
monitoring
Network
orchestration
Figure 3.1: CoUniverse architecture overview.
3.1.1 Self-organization in CoUniverse
Taking into the account the discussion of self-organization in data networks provided in Section
2.1 in the last chapter rigorously, CoUniverse does not represent a pure self-organizing
system. In terms discussed by e.g., Dressler [40] or Heylighen [63], we design CoUniverse
as a distributed system with dynamically chosen control instances, which on the other hand
provides many features of the pure self-organizing systems. These are namely:
* adaptation to changing environment conditions for both CoUniverse middleware and
the collaborative environments CoUniverse orchestrates,
* global order based on local interactions and information,
* dynamic operations,
* robustness and resilience,
* redundancy (i.e., no bottlenecks and single point of failures in the CoUniverse architecture
design),
* self-maintenance.
We follow and utilize the rest of the features of pure self-organizing systems in CoUniverse
only to some extent. Here, we refer especially to the centralized control that is present
to some extent in the CoUniverse architecture design. Therefore the CoUniverse has to be
seen as a distributed system rather than a purely self-organizing system. We however understand
CoUniverse to provide self-organizing capabilities to the orchestrated collaborative
environments.
Self-organization of the collaborative environments encapsulated by the CoUniverse middleware
is based on automated orchestration of the collaborative environment components.
Automated orchestration of such components, encapsulated by the CoUniverse middleware,
is based on the planning of the media streams which are transmitted over the network links
between individual components of the environment. As CoUniverse encapsulates ad-hoc
3.1. COUNIVERSE DESIGN KEY CONCEPTS 27
collaborative environments, the planning of the media streams transmissions does not include
time domain. I.e., we especially do not consider in advance planning network resources
for the media streams transmissions. Ad-hoc character of the orchestrated collaborative
environments requires the media streams transmissions to be planned based on actual
state and properties of the underlying networking infrastructure.
Also the need for resiliency and adaptation to dynamically changing environment implies
that media streams transmissions must be planned and scheduled based on actual
knowledge of the orchestrated environment components and network infrastructure state.
With this expectation, each change in the collaborative environment or the underlying infrastructure
triggers new planning of media streams transmissions. Such re-planning is currently
processed in our approach by planning from scratch which necessitates application of
near real-time planning approaches.
3.1.2 Separation of the Collaborative Environment and Networking Infrastructure
Orchestration
In CoUniverse architecture we opt for decomposition of collaborative environments orchestration
problem separating orchestration of collaborative environment components and orchestration
of network infrastructure if applied. We design CoUniverse to directly orchestrate
encapsulated components of the collaborative environments by agents running on the
network nodes participating within the environment.
We understand the underlying network infrastructure to be either statically provisioned
and configured or based on Dynamic Circuit Networks (DCN). In the first case the users do
not have any means how to configure and orchestrate the network infrastructure. In the later
case CoUniverse interfaces with the DCN middleware through provided API to offload the
network infrastructure orchestration to the DCN middleware.
3.1.3 Decomposition of Collaborative Environments Orchestration Problem
As we have discussed in the previous section, the self-organization and automated orchestration
of the collaborative environments relies on automated planning of media streams
transmissions between the components of the environment over network links. This approach
can be decomposed into three interdependent subproblems: (a) planning of resources
for the components running on nodes connected to the environment, (b) planning of network
resources for the media streams transmissions within the network representation in CoUniverse
and finally (c) planning of physical network resources in order to provide lambdaservices
to be used by the media streams transmissions.
Co-allocation of the application and network components -- in other words combined
planning of application and network resources -- is however a very complex problem [25,
126]. Therefore we decompose the planning problem into three above mentioned subproblems
and treat them separately in the context of planning. We leave the problem of planning
resources for the media applications running on the environment nodes to be solved by the
users, as discussed in Section 3.3.3. Such an approach is possible thanks to the fact that the
nodes are usually dedicated to run certain components in the collaborative environments we
consider. Planning of the media streams transmissions over the network links of the CoUniverse
network representation is the hard problem we tackle in this work and is described in
28 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
the following chapters of this thesis. The problem of physical network infrastructure planning
is again not solved directly within the CoUniverse middleware. If it is necessary to
cover demands of some media streams transmission planned by the CoUniverse using a
network link which is associated with some lambda-service in the CoUniverse network infrastructure
representation then we leave planning of the network resources to create such
lambda-service to respective DCN middleware.
Decomposition of the collaborative environment orchestration reduces dramatically the
computational complexity of solving the whole co-allocation problem. Without a decomposition,
the processing time can be in order of minutes [25], which is clearly unacceptable
for the real-time interaction as expected in the collaborative environments. This becomes
obvious especially in case that re-planning of media streams transmissions and respective
resources is necessary in order to mitigate some failure within the environment in the middle
of an interactive collaborative session.
The rest of the key concepts of the CoUniverse (especially the monitoring and visualization)
are discussed separately later in this chapter as they are discussed closely in context of
the CoUniverse architecture.
Although our work is primarily motivated by the needs of real-world collaborative environments,
the concepts, we have discussed so far, are more generally applicable. The collaborative
environments we are considering can be easily substituted for any other component
based network-centric application based on data transmissions with real-time characteristics
and bandwidth demands comparable to the capacity of the network links.
3.2 CoUniverse Organization
3.2.1 Multiverse and Collaborative Universes
Using the top-down perspective the CoUniverse is organized as one Multiverse and a number
of affiliated Collaborative Universes. A Multiverse provides basically a control plane which
serves for the purposes of creating and managing of individual collaborative universes.
Through the Multiverse the users are also able to look up and connect to the collaborative
universes.
Collaborative universe is an entity which provides the core functionality of the CoUniverse.
The task of collaborative universe is to encapsulate, automatically set up, monitor
and orchestrate the users collaborative environments or generally distributed data stream
transmissions centric applications. Each collaborative universe is intended to orchestrate a
single collaborative environment or application (naturally each environment may consist of
number of components, applications and devices).
From the networking point of view, each collaborative universe consists of a control plane
used to manage the communication and signaling between components of the collaborative
universe and one or more data planes used for actual data exchange between components of
orchestrated collaborative environments. Both control plane and data planes are based on
overlay networks on top of the actual physical network infrastructure.
3.3. COLLABORATIVE UNIVERSE 29
3.2.2 Control Plane
The Control plane is used for message passing and signaling between the components of the
CoUniverse middleware. In the CoUniverse architecture the control plane has to provide
the following functionality:
* identification and description of the CoUniverse components and their addressing,
* advertising and lookups of the resources provided by these components,
* reliable transfers of control messages between components of the middleware.
Control planes of collaborative universes are based on a peer-to-peer (P2P) architecture.
The choice of the P2P architecture provides a self-organization, robustness and resiliency
within the CoUniverse middleware at least in the context of the signalization between the
components of the middleware. This property of the control plane is not to be confused with
the self-organization CoUniverse provides for the orchestrated collaborative environments.
3.2.3 Data Planes
Data planes of the collaborative Universes are based on available physical networking infrastructure.
The data planes are optimized for maximum performance and minimum latency
when transmitting data between the components of the Universe. As data planes are based
on virtual overlays over the physical networking substrate, they exist only in case when
there is an Application Group (see bellow) to utilize it.
The system is designed with user-empowered paradigm in mind and thus it naturally
relies on using application-level media "routers" and distributors for multipoint data distribution
instead of being dependent on network-native multicast.
3.3 Collaborative Universe
The nodes, each running CoUniverse Peer agent, are furthermore organized into collaborative
universes. CoUniverse peers are providing a base for communication among the
Universe components, managing underlying node configuration and steering media applications
configured on the very node. CoUniverse peers also provide the rest of the functionality
of the collaborative environment through their modules. This means especially planning
of media streams transmissions over the network infrastructure within a collaborative
universe, monitoring and visualization.
The first CoUniverse peer trying to connect to non-existing collaborative universe at a
particular time establishes the collaborative universe and makes it available for lookups and
connection for other CoUniverse peers. A particular collaborative universe exist if there is
at least one CoUniverse peer connected. Once all CoUniverse peers disconnect from the
collaborative universe, such an universe ceases to exist. This means that lookups of such
collaborative universe fail within the Multiverse.
To ensure a consistent planning of media streams over individual network links we require
the sets of peers connected to collaborative universes be disjunct for each two different
universes. This also means that just a single CoUniverse peer controlling local resources
must be running on each node. This rule does not have to hold for CoUniverse peers acting
as proxy controllers (see below). I.e., a single CoUniverse peer may be running on one
30 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
node together with arbitrary number of CoUniverse peers which act as proxy controllers
and control external resources.
3.3.1 Nodes
Network nodes are the building elements of each collaborative universe. Network node is
a representation of a physical node with its network interfaces connected to various physical
networks and applications configured to be running on the node. Each network node
must run an instance of CoUniverse peer in order to participate in any of the collaborative
universes. The CoUniverse peer -- among other tasks -- maintains the node configuration,
orchestrates the applications configured on the node and monitors the network links related
to the network interfaces configured on the node. The operations of the CoUniverse peer are
further described in Section 3.6.
The node configuration is then involved in the processes of establishing and updating
of the network topology and planning of the media streams transmission over particular
network links within respective Universe. Each network node is configured by specifying
1. node identification,
2. geographical location of the node for visualization purposes,
3. a list of its physical network interfaces and their parameters,
4. a list of Media Applications which are installed on the node and their configuration,
5. a network site the node belongs to,
6. proxy controller configuration if applied.
Network node is identified usually by its hostname. We however use this identification
of the network node just for purposes of logging events in the CoUniverse and for
debugging purposes. We identify the network nodes internally using Universally Unique
Identifier (UUID) [86] and address them via the CoUniverse peers running on the nodes and
connected to a common control plane. For the purpose of visualization of CoUniverse operations
we require each node to be configured with its location. The location of the node can
be expressed using a coordinate system such as geographical latitude and longitude. The
most important part of the node configuration are the lists of node network interfaces and
media applications configured on the node. Both concepts of network interfaces and media
applications are discussed in details later in this chapter.
Network Sites
Nodes within the Universe are aggregated into network sites, usually representing all nodes
of a single site participating in the collaborative universe. A network site represents a logical
locality of the network node within the network organization of a collaborative universe.
To give more precise definition, a network site is a set of collocated nodes, where each site
may have one or more users participating. The network site usually corresponds with a real
world site the network node is placed in (e.g., laboratory, department, faculty, university
or institution). However, any network node may be also configured to be a part of purely
virtual network site. The concept of network sites plays an important role in the process
3.3. COLLABORATIVE UNIVERSE 31
of self-organization in the CoUniverse. Using network sites the users are able to influence
the distribution of media streams in the collaborative universe to build their environment
or application. In other words, network sites are used to specify/request media streams
sources for media stream consumers (see Section 3.3.3 for reference). Expressed using the
terminology defined further in this chapter, a typical property of all nodes within one site
is that there are no media application consumers consuming data from media application
producers from the same site (this definition doesn't include media distributors). For further
reference to the network sites concept see discussion of the media applications configuration
in Section 3.3.3 and discussion of the definitions of collaborative universe network
organization for the purposes of media streams planning problem formulation in Chapter 4.
Proxy Nodes
In the CoUniverse architecture we consider that the media applications configured on some
network node must not necessarily be running on the same network node. CoUniverse
peer running on the network node and orchestrating such applications then acts as a proxy
controller. In such case the proxy controller information must be a part of the network node
configuration specifying/implementing (i.e., CoUniverse needs to support specific control
protocol) how to control the application running on a remote node (e.g., using telnet or ssh).
Network Interfaces Configuration
Network interfaces represent a physical interface of a respective network node. Network
interfaces are identified by their names. A network interface is further configured with its
IP address, network mask of the IP address, network interface throughput, and information
whether the network interface is full duplex or half duplex. In addition to the usual settings
of a network interface, we configure the network interface with a subnetwork identification.
We use the subnetworks concept to create full-mesh, end-to-end network topology as further
discussed in Section 4.1. If there is a connection between the network interface and some
endpoint in the underlying lambda-services enabled physical network infrastructure, we
also add the identification of the endpoint to the network interface configuration.
The following example shows a network interface of a node couniverse.muni.cz
with configured IP address and network mask. The interface is capable of full duplex
transmissions up to 10 Gbps. The network interface interfaces with a lambda link endpoint
sitola.fi.muni.cz indicating that the hypothetical DCN endpoint is located in
the Laboratory of Advanced Networking Technologies at Faculty of Informatics, Masaryk
University.
3.3.2 Network Topology Representation
For each collaborative universe and its data plane we consider a virtual network topology
which creates an overlay above the physical networking infrastructure. The network
topology of a collaborative universe consists of end-to-end network links between network
interfaces of individual network nodes. This approach well corresponds with the userempowered
paradigm we are following through the whole CoUniverse architecture design.
With the user-empowered paradigm in mind, we assume the users to know only their local
32 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
Configuration 1 Network interface configuration example.
nodeInterface {
nodeInterfaceName = "eth1";
ipAddress = 172.80.30.1;
netMask = 255.255.0.0;
bandwidth = 10000;
fullduplex = true;
subnet = "10GE Subnetwork";
lambdaLinkEndpoint = {sitola.fi.muni.cz};
parentNode = "couniverse.muni.cz";
}
nodes configurations but not necessarily the topology and configuration of the network interconnecting
the nodes. With two or more users participating with their nodes in the same
collaborative environment such an assumption is met easily especially when considering the
Internet to be the network interconnecting the nodes. Even in case of some private optical circuit
based network the end users usually do not know its topology, e.g., because the network
can span a number of administrative domains and its physical topology may be concealed
to the end-users for confidentiality reasons. Revealing the physical network topology to the
users would also present a breach of abstraction level as in general case administrators of the
network are able to reconstruct the network on the fly to mitigate various failures without
having to notify the users with the potential network topology change. However, in case of
such circuit based network the end-users usually know how their nodes (network interfaces
of the nodes) interface with such optical network.
In the CoUniverse architecture we thus consider a full-mesh of end-to-end network links
to exist between network interfaces of all network nodes within a collaborative universe.
The full-mesh network topology is limited by the subnetwork property of each network
interfaces. We consider the network links to exist only between interfaces connected to the
same subnetwork.
Another option would be to build the network topology consisting of full-mesh of network
links existing between network interfaces of the nodes belonging to each of the network
sites and full-mesh of links interconnecting the sites. This approach is implied by the
fact that the number of sites is usually much smaller than the number of nodes (and their
network interfaces) in our model. Thus incorporating the sites into the network topology
might decrease the number of network links while planning the media streams transmissions
and simplify the planning problem. The advantage of the first approach is on the other
hand the fact that it is possible to obtain the configuration for the media applications running
on the nodes directly from the planned media streams transmissions over network links between
the interfaces of the nodes. Both variants of the network topologies we consider are
illustrated at Figure 3.2.
3.3.3 Media Applications
Media Application are the basic components of the collaborative environment or application
orchestrated by CoUniverse. A general property of all media applications is that they
produce (send) or consume (receive) a media stream or streams. Producing a stream means
that the media application acquires the stream of data and sends it through the network to a
3.3. COLLABORATIVE UNIVERSE 33
(a) (b)
Figure 3.2: Network topology representations: (a) full-mesh topology, (b) full-mesh topology
between the sites. The clouds depict network sites. To simplify the schemes the network
interfaces at the nodes are omitted from both figures.
given target media application. A media application consuming a media stream listens for
an incoming stream, receives and processes it. Each media application is also characterized
by a set of stream types it is able to produce/consume. An example of a media application
would be e.g., general purpose video streaming tools like UltraGrid1 or VideoLan Client
(VLC)2, videoconferencing clients like VIC, audioconferencing clients like RAT3 or data distributing
Active Elements (AE) [64]. Our understanding of media application is not limited
only to software clients and tools but also covers hardware devices. A hardware based media
applications could be Polycom4 or Lifesize5 H.323 videoconferencing devices and similar
ones. These are typical media applications to be orchestrated by CoUniverse peer acting as
a proxy controller.
Media Stream Types
Before proceeding with description of media applications we first discuss a concept of Media
Stream Types in CoUniverse. Media stream type describes a stream of data produced,
consumed and distributed by media applications. For each media stream type we define its
properties as follows:
1. stream description,
2. minimum bandwidth of the stream in bps,
3. maximum bandwidth of the stream in bps,
4. stream latency in ms,
5. maximum burst of the stream in bps,
1http://ultragrid.sitola.cz/
2http://www.videolan.org/
3http://mediatools.cs.ucl.ac.uk/
4http://www.polycom.com/
5http://www.lifesize.com/
34 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
6. stream quality.
Stream description identifies the stream for the purposes of debugging. We define minimum
and maximum bandwidth to describe streams with variable bitrate. For a constant
bitrate stream both minimum and maximum bandwidth are equal. Latency of the media
stream denotes the time necessary for processing of the stream (e.g., latency of uncompressed
video media stream type would be definitely lower than a latency of HDV MPEG2
stream). Maximum burst denotes a maximum bandwidth used when transmitting the media
stream over the network. When maximum burst of a media stream is equal to its maximum
bandwidth the media stream is considered to be smooth. The maximum burst is also used
for allocation of lambda links with hard limits on bandwidth to ensure that the network link
associated with the allocated lambda link is actually able to transmit such a bursty media
stream. Media stream quality is an integer number denoting a subjective quality of the media
stream. It is designed for being able to compare different media streams when building
the collaborative environment and for example optimize the media streams distribution for
quality when more stream types are available at the same time.
Configuration examples 2 and 3 show definitions of uncompressed HDTV video stream
produced by UltraGrid and HDV MPEG2 video stream produced by VideoLan Client, re-
spectively:
Configuration 2 Uncompressed video stream definition.
UncompressedHDTVStream {
description = "Uncompressed 1080i 10b HDTV stream";
bandwidth_min = 1500000000L;
bandwidth_max = 1500000000L;
latency = 80;
bursts_max = 6000000000L;
quality = 8.0f;
}
Configuration 3 Compressed video stream definition.
HDVMPEG2Stream {
description = "HDV MPEG-2 TS stream";
bandwidth_min = 25000000L;
bandwidth_max = 25000000L;
latency = 1000;
bursts_max = 30000000L;
quality = 7.0f;
}
Configuration of Media Applications
Each media application is identified by its name which is similarly to the network interface
name used primarily for the purposes of fast identification of the media application when debugging
the behavior of the CoUniverse middleware. All media applications are internally
again identified using their UUIDs. More important part of the configuration is a collection
3.3. COLLABORATIVE UNIVERSE 35
of media streams supported by the application. To be able to invoke the media application,
we furthermore specify a path of its executable and its command line parameters.
In CoUnvierse we distinguish three basic media application types:
1. Media Application Producers,
2. Media Application Consumers,
3. Media Distributors.
Media application producer is generally any application which produces stream of data
with given type and parameters and sends it to target IP address. As we have proposed
CoUniverse to orchestrate primarily collaborative environments we usually work with media
applications producing streams of audio or video. An example of such application would
be the above mentioned UltraGrid, VideoLan Client or Polycom videoconferencing device.
Media application consumer is again any application which consumes a stream of data
of given type and parameters. Media application producer pairs with media application
consumer. Thus, an example of media application consumer would be again UltraGrid or
VideoLan Client.
In addition to the basic configuration of a media application we define for each media
application producer its target. The target denotes the target media application of the media
stream eventually produced by the media application producer. The target media application
may be a media application consumer for a simple 1:1 media stream distribution (i.e.,
the media stream is being transmitted directly between the media application producer and
respective media application consumer) or a media distributor for any other media stream
distribution. Analogically, for each media application consumer we define its source. The
source denotes a media application producer which is producing a media stream received
by the media application consumer in question. Both media application producer target
and media application source are subject of the media streams planning (see Section 3.6 and
Chapter 4 for reference) and thus are not set as a part of media application configuration on
a local node.
Next major difference between media application producer and media application consumer
is the source network site which is configured for each media application consumer.
The purpose of the source network site is to meaningfully bind the distribution of media
streams between media application producer and media application consumers to create
collaborative environments based on user specifications. Source network site of media application
consumer confine the set of possible media application producers which may be
selected as a source application for a media stream received by the consumer. I.e., the source
network site for each media application producer receiving some media stream and site of
the parent node hosting the respective source media application producer must be the same.
The following example shows an initial configuration of media application producer and
consumer.
Media distributor is a generalized concept covering any software application or hardware
device able to distribute media streams from media stream producers to one or more
media stream consumers. Media distributors in the CoUniverse architecture cover applications
like software packet reflectors which are able to create multipoint data distribution
while keeping the advantages of the point-to-point unicast communication scheme (see Section
2.1.4 for reference). Such packet reflectors are also used for example in videoconferencig
36 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
Configuration 4 Producer configuration example.
UltraGridProducer {
applicationName = "UltraGrid HD video producer";
mediaStreams = {UncompressedHDTVStream};
applicationPath = "/usr/local/bin/uv";
applicationOptions = "-t hdtv -m 8500";
parentNode = senderNode;
target = nil;
}
Configuration 5 Consumer configuration example.
UltraGridConsumer {
applicationName = "UltraGrid HD video consumer";
mediaStreams = {UncompressedHDTVStream};
applicationPath = "/usr/local/bin/uv";
applicationOptions = "-d gl"
parentNode = receiverNode;
sourceSite = siteTheSenderNodeBelongsTo;
source = nil;
}
environments like Virtual Room Videoconferencing System (VRVS) [46] or AccessGrid [26].
Our understanding of media distributors is again not limited to software clients only. Media
distributors can also represent e.g., hardware Multipoint Control Unit (MCU) devices
commonly used to create multipoint videoconferences for H.323 tools. Note, that media distributor
could be theoretically expressed as a combination of a single consumer and one or
more producers. However, we induct the concept of media distributors explicitly to simplify
the formulation of media streams planning problem in Chapter 4 and further work with the
model in this thesis.
Media Applications Properties
We consider the media applications and media distributors be a legacy applications, which
means that the media applications are completely unaware they are being controlled by any
application middleware like CoUniverse. The advantage is that we can encapsulate virtually
any software application and hardware equipment to be controlled by the CoUniverse
middleware. Also, we have to consider just two different approaches to the orchestration
of the media applications: one for the software applications and one for hardware devices.
Treating media applications as legacy ones on the other hand introduces some limitations to
their configuration, orchestration and monitoring. Generally we presume only that all media
applications can be controlled as processes of operating system (e.g., UNIX/Windows process)
and configured using command line based parameters passing. Also, the monitoring
of media applications is thus limited just to observing of their behaviour (e.g., by periodic
observation of the respective UNIX process state).
Media applications and media distributors we have discussed above use primarily stateless
UDP and RTP protocols for media streams transmissions. However, orchestration of
the media applications in the CoUniverse is designed so that it is also possible to properly
3.3. COLLABORATIVE UNIVERSE 37
control applications sending the media streams using generic transmission regardless of the
protocol used6 and manage connections between media applications by careful deployment
of planned media streams transmissions (see Section 4.7 in Chapter 4 for reference).
Moreover, we consider that all media application producers are sending media streams
using unicast7. We furthermore restrict sending of the media streams considering that real
world media applications are able to send only one media stream to a specified target at a
time. Using the terms of CoUniverse architecture we define Media Application producers
being able to produce exactly one media stream which is then sent to exactly one media
application consumer or media distributor.
Furthermore, receiving media streams by media applications running on a single node
is restricted by the possibilities of addressing individual media applications running on the
same node8. The problem is that with a legacy media application, it might be completely
impossible, e.g., to change the port the media application (media application consumer in
this case) is listening on for incoming UDP traffic. Thus, it is not generally possible to run
more than one media application consumer of the same media application on a single node at
the same time. This constraint can be covered by careful definition of the media applications
list in the node configuration.
Another constraint emerges from the fact that CoUniverse was designed especially for
applications built on transmissions of high-bandwidth streams (even comparable to the
bandwidth of network links). Handling of such streams by a media application may be
very resources demanding (CPU performance, available amount of memory, GPU performance
in case of video streams, etc.). Thus it might be reasonable to limit the number of
media applications running on a single network node at the same time. Solving this issue
is again left on the users who have to carefully configure the media application available on
the nodes connected to the collaborative universe.
3.3.4 Application Groups
Media applications are organized into Application Groups (AG). The purpose of AGs is to
generalize a particular functionality of the collaborative environment or application. For
some particular collaborative environment we may consider distinct application groups for
audio or video conferencing, desktop sharing and so on. The purpose of the AG is to coordinate
the media streams distribution among the media applications belonging to the AG.
The basic concept of media streams distribution within an environment based on interactive
network-centric applications is that media streams are being produced by the producers,
possibly distributed using one or more distributors, and finally delivered to one or more consumers.
The streams are transmitted along a set of media distribution trees, where the goal
is to assign a distribution tree to each stream, given the capacity constraints of the components
and requirements of applications (and thereby users). Each media distribution tree is
constructed so that the producers are running at the root node, all consumers that are about
to receive the stream distributed from the producer at the leaf nodes and the distributors at
the internal nodes (except for the root node). The core of the problem we solve is to ensure
the media streams distribution be fulfilling the following requirements:
6So far we have dealt only with IP protocol based transmissions while orchestrating real-world collaborative
environments using the CoUniverse middleware.
7For discussion on why only unicast is considered for sending of media streams see Section 2.1.4.
8The media applications are addressed using the traditional IP address and port scheme.
38 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
1. The media streams distribution has to satisfy the requirements imposed by the user
(consumers have to be served by producers running on some node belonging to the
requested site).
2. The bandwidth demands of the media streams distribution must not exceed the capacity
of any of the network links as well as the capacity of any network interface on
the nodes (relying on the end-to-end network topology means that several links may
begin or end in a single network interface).
3. To provide for as interactive collaboration as possible, we minimize the overall latency
of the media streams distribution. I.e., network paths with the lowest latency possible9
should be used for media streams distribution.
Each AG is orchestrated by Application Group Controller (AGC) which is the key component
of the CoUniverse architecture. In the following we describe its functionality, features
and properties.
Application Group Controller
The purpose of the AGC is to collect node configurations from all CoUniverse peers within
the collaborative universe, assemble a network topology of universe data planes, invoke
a scheduler to plan transmissions od the media streams of corresponding media applications
over the network links, create a configuration for each media application based on
planned media streams transmissions and finally deploy the configuration together to respective
universe peer. The universe peer in charge then adjusts the configuration of steered
media application so that it corresponds to respective planned media stream transmission.
The scheduler within the AGC is invoked automatically as a reaction to a change of the network
topology state within respective collaborative universe. The change of the network
topology may be caused for example by new node appearing in the topology or a change of
a state of some network link or interface.
The AGCs within the application groups are dynamically elected to avoid them being
single point of failures. Any CoUniverse peer can serve as AGC. The application group is
unable to provide any functionality without a CoUniverse peer providing the AGC service.
Therefore the CoUniverse peers have to monitor that the AGC service is being advertised
through the control plane which means that there is some CoUniverse peer running and providing
the AGC service. Organization of the CoUniverse peers to provide the AGC service
involves utilization of election mechanisms usual in distributed computing systems [19,48].
Utilisation of these mechanisms also provide reorganization and electing new CoUniverse
peer after a failure of the AGC service was detected. In this way we mitigate the above mentioned
potential single point of failure introduced by the system critical AGC service in the
CoUniverse architecture. Note that introducing a "leader" AGC service is the reason why
the CoUniverse middleware has to be considered being a distributed rather than pure selforganizing
system. On the other hand we opt for this approach in order not to have to deal
with synchronization of several AGCs trying to orchestrate the same AG.
To provide the above mentioned functionality AGC consists of two essential modules,
the Match Maker and the Lambda Links Factory. In the following we provide an overview
of their functionality.
9The global requirements on the media streams distribution within AG must be still met.
3.3. COLLABORATIVE UNIVERSE 39
Match Maker The purpose of the Match Maker module is to provide planning of the media
streams transmissions over the network infrastructure to allow for automated orchestration
of the components of the collaborative environments. In connection with the monitoring
features in the CoUniverse, the Match Maker also provides dynamics and resiliency for
the orchestrated environments and in a sense also the self-organization abilities to encapsulated
collaborative environments. Planning of the media streams transmissions with its
constraints and objectives is in detail described in Chapter 4 and also in Section 5.2.1 where
we evaluate the Match Maker module prototype implementation.
Except for ensuring proper media streams distribution between the components of the
collaborative environment, the planning objectives may vary: for simple interactive applications
with fixed quality, it usually includes minimization of media distribution latency and
possibly minimization of number of nodes involved in the network. For more complex applications
where quality is an adjustable parameter, maximization of the quality may also be
included. We discuss these objectives in detail in Section 4.3. Output of the scheduler has
to include not only the plan itself, but also an implicit workflow describing how to deploy
and implement the plan, as there are many functional dependencies. For instance, lambda
links need to be allocated prior to starting media applications that will send data over them;
also the applications have to be invoked in certain order to ensure properly working media
streams distribution. This is discussed in depth in Section 4.7.
Lambda Links Factory The Lambda Link Factory provides an interface between the network
representation in the CoUniverse middleware and the DCN middleware providing the
lambda-services which may be associated with certain network links. Basic operations over
the lambda-services include allocation of the lambda links and their deallocation. Moreover
Lambda Links Factory should be able to modify an existing lambda link allocation. Allocation
request for a certain lambda link includes identification of the lambda link using its both
lambda link endpoints, requested bandwidth and a time span of the lambda link allocation.
The lambda-services are usually being allocated ahead in time by the DCN middleware.
We however need the lambda-services to be allocated in ad-hoc manner. A minor problem
here is to distinguish a time span of an ad-hoc allocations of lambda-services as we are not
able to predict the duration of an existence of ad-hoc collaborative environments. As the
lambda-services are based on shared network resources, we had to leverage the time span
of the lambda links allocation in order not to occupy the shared network resources for other
potential users. We therefore specify rather short time spans for the lambda links allocation
and then modify the existing allocations if they are still needed10.
We suggest the Lambda Link factory to be designed as a rather centralized control entity.
In the current CoUniverse architecture the Lambda Link Factory is designed as a module of
the AGC. We opt for this approach because it is reasonable to have a quite strict control over
the requests being sent by the Lambda Link factory to the DCN middleware in order not to
overwhelm the DCN middleware with a number of requests. Also, using this approach we
do not have to deal with synchronization between the Lambda Link Factories as if they were
modules of the CoUniverse peers.
10The time span of lambda link allocation also depends on the concrete DCN middleware used to provide the
lambda-services. Based on our experiments with the DCN middleware we currently tend to allocate the lambda
links with a time span in order of tens of minutes. Note that this decision is also based on the times necessary to
process the allocation request for a lambda link (See Section 5.3.2 for more details.).
40 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
3.3.5 Security Considerations
A not yet mentioned function of the collaborative universe is to provide authentication, authorization
and accounting (AAA) mechanisms. Designing the AAA as a collaborative universe
functionality allows to deploy different schemes and mechanisms on per-universe basis.
Authentication and authorization of the users connecting to the collaborative universe
is be based either on traditional username/password scheme or on the federated security
approach [36,99].
The limited size of the Collaborative universes also allows us to assume that the users
would behave intentionally and in a collaborative manner. Thus we do not anticipate issues
connected with intentional cheating and users misbehavior (e.g., intentional breaching of
the collaborative universe by intentional advertising of misconfigured nodes or advertising
a misbehaving AGC service). These issues might be however addressed by utilising reputation
and trust based mechanisms [32,137] to ensure reliability of the resources provided by
the users within the collaborative universe.
3.4 Monitoring
Monitoring is a key component of the CoUniverse architecture. Self-organization of the
collaborative environments and orchestration of their components by the CoUniverse middleware
relies on its ability to obtain timely and precise information on the state of the collaborative
environment components and the underlying network infrastructure.
We propose a monitoring module being a part of each CoUniverse peer to undertake the
monitoring within the CoUniverse architecture. The module is periodically monitoring the
node the universe peer is running on, the media applications steered on the respective node
and both incoming and outgoing network links. We consider two modes for the monitoring
of all these entities. One monitoring mode is based on polling of the monitored entities while
the other one is based on the publisher­subscriber mode [147].
3.4.1 Nodes and Media Applications Monitoring
Monitoring of the network node provides information on its overall load and utilization of
its network interfaces. As for the node load we monitor the load of all CPUs and the global
memory usage. Monitoring of the network interfaces returns their current inbound and
outbound load as well as status of the interfaces.
Because of the legacy character of the media applications in our architecture the possibilities
of their monitoring are quite limited. It is basically possible to monitor just behavior of
the media applications as seen by the operating system running on the node. We are limited
by the user-empowered approach to the CoUniverse design, thus we are able make use of
only those monitoring methods which do not require having administrative rights on the
node. Concerning the media applications we monitor those applications which are planned
to be running and producing or consuming some media streams at a particular time. For
each such media application we monitor its state (i.e., if the application is running or not)
and their CPU and memory usage.
3.4. MONITORING 41
3.4.2 Network Monitoring
Monitoring of the network infrastructure underlying to orchestrated collaborative environments
is based on monitoring of the network links as represented in the network topology of
each data plane. We use different approaches for monitoring of network links which might
be used to build a data plane for media applications and network links that are actually part
of some data plane. Monitoring of the data planes network links is more aggressive than
monitoring of network links of generally available physical networking substrate links since
the links of data planes are actually used for media applications data exchange. At the same
time, the links that are not used in any of the Universe data planes need to be monitored less
frequently just so that the AGC eventually has a notion of their state when some event in the
Universe occurs and those links might be needed for some newly planned media streams
transmissions. The approach to the network monitoring also differs depending on if we
monitor network links or circuit based lambda links.
Network Links Monitoring
There are three measures to be obtained by the monitoring of the network links: state of
the link, latency induced by the link to the transmissions of media streams and the real
available bandwidth. The most important is the fact that the link is up (able to transmit
some data) or down. Besides of that, it is important to monitor the latency induced by
transmitting media streams over particular network links in order to allow for optimization
of the media streams distribution latencies for the orchestrated collaborative environments.
We measure both state and latency induced by the network links by means of TCP and
UDP ping. Monitoring the latency of network links using TCP or UDP ping corresponds
with the latencies induced to the real transmissions of the media streams between the media
applications.
Finally, monitoring of the network links is used to obtain their real available bandwidth.
The rationale behind this approach is the fact that the capacity (available bandwidth) of each
network link is statically determined as minimum of the capacities of respective network
interfaces once the network link is created and added to the network topology. The available
bandwidth determined for each network link in this way is however only theoretical. Since
we create the network links as end-to-end links, the links may actually consist of number
of links and components of the physical network infrastructure. The maximum available
bandwidth of the end-to-end link may be completely different than the statically determined
one. The physical network infrastructure may either introduce some bottleneck in terms of
available bandwidth by its physical configuration or by the fact that it is shared and loaded
by some other traffic outside of the CoUniverse scope. Therefore we introduce active probing
of available bandwidth [71, 142, 143] for each network link to the monitoring framework of
the CoUniverse middleware. Note, that passive monitoring of the network infrastructure in
order to obtain available bandwidth is in contradiction with the user-empowered approach
we are pursuing as the users have no means how to monitor the network infrastructure
which is basically concealed from them.
42 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
Lambda Links Monitoring
Status of the lambda links is obtained through polling of the DCN middleware. CoUniverse
starts to monitor the lambda link as soon as the allocation request for the lambda link is
accepted by the DCN middleware. Lambda links may be found in one of the following
states11:
* SUBMITTED ­ lambda link reservation request has been submitted and a reply sent to
the requester,
* ACCEPTED ­ lambda link reservation request has been accepted and the reservation
is scheduled to be processed,
* INCREATE ­ lambda link reservation creation is in process,
* PENDING ­ lambda link reservation processing is complete and resources have been
reserved, but the scheduled start time has not arrived yet,
* INSETUP ­ the underlying circuits are being provisioned,
* ACTIVE ­ lambda link is currently provisioned and active,
* INMODIFY ­ a modification requested by the user is in process,
* INTEARDOWN ­ lambda link is in the process of being torn-down,
* FINISHED ­ end time has past, and the lambda link has been torn down,
* CANCELLED - reservation was canceled, lambda link is not active,
* FAILED ­ lambda link may have failed to be setup because the required resources
were not available, or a link that the circuit uses is down and the circuit may still be
provisioned.
* UNKNOWN ­ lambda link allocation was not yet requested from the DCN middleware
(i.e., there exists just a representation of the lambda link in the network topology
of some collaborative universe in the CoUniverse middleware).
Figure 3.3 depicts a reservation state diagram of a lambda link represented within the
CoUniverse middleware. Note that the transitions between the lambda link states in CoUniverse
are again based on the Internet2 DCN lambda links state diagram.
We suggest the lambda links monitoring to be realized by a separate monitoring module
being a part of the Lambda Links factory within the scope of the AGC. We opt for this approach
because of the fact that polling of lambda links from all monitoring modules of the
CoUniverse peers would potentially introduce a large number of requests towards the DCN
middleware. Thus monitoring of the lambda links states by the CoUniverse peers monitoring
modules is an impractical scenario.
11Note that the states of the lambda links are based on the Internet2 DCN representation of the lambda links.
See https://oscars.es.net/OSCARS/docs/API.html for more details.
3.5. VISUALIZATION 43
UNKNOWN
ACCEPTED
RESERVED
INSETUP
ACTIVE
FAILED
INTEARDOWN
FINISHED
CANCELLED
INMODIFY
Figure 3.3: Lambda link state diagram.
3.5 Visualization
Visualisation gives an overview of actual collaborative universe state to the end users. The
components to be visualized for a particular collaborative universe are:
* network nodes,
* network node interfaces,
* media applications,
* planned media streams transmissions deployed over particular network links.
A seemingly missing component to be visualized within a collaborative universe is its
network topology. However, the fact that we use a full-mesh of end-to-end network links
to represent the network topology means that we would have to visualize potentially very
large number of network links. Moreover, visualization of the network links would become
more complex and probably confusing in case when the nodes of the collaborative universe
are connected to more than one isolated physical network through their network interfaces.
Visualisation of planned and deployed media streams transmissions is extremely useful
especially when incorporating data from network and applications monitoring. Moreover
users can also easily find out whether the media streams transmission planned over a given
network topology has the desired effect (i.e., users can see, talk to, or collaborate with each
other in the way it was intended in a particular collaborative universe).
44 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
3.6 Dynamics of the CoUniverse Middleware
So far we have described the basic building blocks of the CoUniverse middleware. In this
section we provide an overview of CoUniverse utilization for setting up and orchestration
of collaborative universe. To give an overview of the collaborative universe dynamics, we
describe the operations of CoUniverse peer and its most important modules (i.e., the Application
Group Controller, Monitoring and Lambda Links Factory) and the communication
between them to in order to establish and orchestrate a collaborative environment.
3.6.1 CoUniverse Peer
The life cycle of the CoUniverse peer is depicted as Algorithm 1. Immediately after its invocation
the CoUniverse peer connects to the collaborative universe. This involves as a first
step connecting to the P2P control plane of the collaborative universe. If the user configured
the CoUniverse peer statically to provide the AGC service, the AGC module is instantiated
immediately after the CoUniverse peer starts and is periodically advertised through
the control plane as a service of the CoUniverse peer. CoUniverse peer then instantiates
the representation of the local node and loads the node configuration we have described in
Section 3.3.1.
CoUniverse peer then registers callbacks to be invoked after some message is received
over the control plane and starts listening for the incoming messages. In current version of
the CoUniverse architecture we consider these messages to be received and processed by the
CoUniverse peer:
* Start Media Application ­ message which includes identification of the media application
and its parameters. The callback registered with the CoUniverse peer then invokes
the media application and passes the parameters obtained from the AGC. This message
is received for each media application which produces or consumes some of the media
streams planned to be transmitted over the network links as a result of the plan
deployment performed by the AGC.
* Stop Media Application ­ message including identification of the media application. Respective
callback within the CoUniverse peer then terminates such media application
running on the node. This message is received for each application which was a part
of the previously deployed plan before the new plan is deployed.
* Network Topology Update ­ message containing the actual state of the network topology
representation within the collaborative universe. This message is used to update
the monitoring module of the CoUniverse peer with an information what (e.g., which
network links) is to be monitored. This message is received after each change of the
network topology representation which basically means always when some node is
added to or removed from the network topology or when a state of some network link
is being changed from up to down or vice versa in the network topology representa-
tion.
* Active Links ­ message containing identification of the network links which are used
for currently deployed media streams transmissions. This message is being received
3.6. DYNAMICS OF THE COUNIVERSE MIDDLEWARE 45
immediately after a new plan is deployed by the AGC. Based on this message the actively
used network links are being monitored more aggressively as we have discussed
in Section 3.4.2.
CoUniverse peer then searches for the AGC service advertisement which already has to
be advertised through the control plane. The search for the AGC advertisement is periodical
as all CoUniverse peer within and collaborative universe have to maintain connection to
at least one AGC. If the AGC is not found within some timeout then the CoUniverse peer
instantiates the AGC module on its own. AGC service is then again being periodically advertised
through the control plane. Once the AGC service is found the CoUniverse starts to
send its own node configuration to the AGC periodically (i.e., the CoUniverse peer advertises
its node configuration).
Finally, before entering the main loop, the CoUniverse peer instantiates the monitoring
module and registers subscribers (callbacks) for events reported by the monitoring module
in the publisher-subscriber mode. An example would be subscribers for the "network link
up" and "network link down" events reported by the monitoring, where the subscribers
registered within the CoUniverse peer reports these events to the AGC.
After all above mentioned steps were undertaken, the CoUniverse peer enters its main
loop where it waits for the signal to be terminated. Meanwhile all the processes initiated by
the CoUniverse peer (listening for and processing of incoming messages, advertising of the
node configuration and monitoring) are running in their own threads.
After the termination signal is received, the CoUniverse peer leaves the collaborative universe.
This step involves especially notifying the AGC of the fact that the CoUniverse peer
(and the underlying node) is leaving the collaborative universe and the node and respective
network links beginning and ending in the node interfaces should be removed from the representation
of the network topology which is maintained by the AGC. The life cycle of the
CoUniverse peer together with the life cycle of the AGC is partially also illustrated at Figure
3.4. This illustration depicts signaling between the CoUniverse peer and the AGC within
a Collaborative universe; especially the mechanism of node configuration advertising, network
topology maintenance, re-planning of media streams transmissions as a reaction to
some messages passed between the CoUniverse peer and the AGC and deployment of the
plan.
Before the CoUniverse peer terminates, it stops all media applications left running on the
respective node and stops the monitoring and potential AGC modules previously instantiated
by the CoUniverse peer.
3.6.2 Application Group Controller
Dynamics of the Application Group Controller (AGC) is depicted as Algorithm 2. Initialization
of the AGC involves especially creating a new network topology representation for
the collaborative environment, registering callbacks to be invoked after some message is received
over the control plane and starting to listen for the incoming messages. In current
version of the CoUniverse architecture we consider these messages to be received and processed
by the AGC:
* Node Advertisement ­ message which includes configuration of a network node sent
by respective CoUniverse peer. If the Collaborative universe network topology representation
does not include the node included within the node advertisement message,
46 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
CoUniverse peer AGC
topologyRepresentationMaintenance
localNodeAdvertising
monitoring
NodeAdvertisement Msg
...
NetworkTopologyUpdate Msg
mediaStreamsPlanningplanDeployment
appOrchestration
......
StartMediaApplication Msg
monitoring
ActiveLinks Msg
topologyRepresentationMaintenance
mediaStreamsPlanningplanDeployment
appOrchestration
StopMediaApplication Msg
monitoringmonitoring
NetworkTopologyUpdate Msg
planDeployment
appOrchestration
......
monitoring
topologyRepresentationMaintenance
mediaStreamsPlanningplanDeployment
appOrchestration
StopMediaApplication Msg
StartMediaApplication Msg
monitoring
ActiveLinks Msg
monitoring
plan
plan
networktopologysnapshotnetworktopologysnapshot
Collaborative
environment
components
Collaborative
environment
components
NetworkLinkDown Msg
NetworkLinkUp Msg
Control plane
Network
infrastructure
network monitoring
application monitoring
network monitoring
application monitoring
Network
infrastructure
network monitoring
network monitoring
Figure 3.4: Dynamics and signaling in collaborative universe.
Bold lines illustrate the messages sent between the CoUniverse peer and the AGC. Dashed
lines represent other interactions.
3.6. DYNAMICS OF THE COUNIVERSE MIDDLEWARE 47
Algorithm 1 Life cycle of CoUniverse Peer
peer.joinUniverse();
if isAGC then
agc = new ApplicationGroupController();
agc.startAGC();
end if
localNode = new NetworkNode();
peer.initializeNodeConfiguration();
peer.registerIncommingMessagesCallbacks();
peer.listenForIncommingMessages();
peer.maintainAGCConnection();
peer.startLocalNodeAdvertising();
peer.networkMonitor.startMonitoring();
peer.mainLoop();
peer.leaveUniverse();
for all nodeApplication : localNode.getNodeApplications() do
nodeApplication.stopApplication();
end for
peer.networkMonitor.stopMonitoring();
if isAGC then
agc.stopAGC();
end if
then the AGC adds the node into the network topology representation and creates
respective network links which begin or end in network interfaces of the node. We
provide more detailed description of how the network links are added to the network
topology in Sections 3.3.2 and 4.1. If both network interfaces of some of the network
links just added to the network topology interface with some DCN endpoint, then we
also create a new lambda link representation, associate it with respective network link
and add it to be monitored by the Lambda Links Factory monitoring module.
* Node Removed ­ message including identification of the network node to be removed
from the network topology because of the fact that the respective CoUniverse peer
disconnected from the Collaborative universe. Based on this message AGC removes
also all network links beginning or ending in the network interfaces of the node in
question.
* Network Link Up ­ message containing an identification of a network link which was
determined by a monitoring module of some CoUniverse peer to change its state and
be again capable of transmitting data. Such a network link is then qualified to be active
within the network topology representation.
* Network Link Down ­ similarly a message which contains an identification of a network
link which was determined by a monitoring module of some CoUniverse peer to
change its state from being up to down (i.e., no data can be transmitted over such link).
These network links are then being qualified as inactive within the network topology
representation.
48 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
Initialization of the AGC is finished by the AGC instantiating the Lambda Links monitoring
module of the Lambda Links Factory. As we have mentioned earlier, monitoring of
the lambda links is performed by polling the DCN middleware on their state as we have
discussed in Section 3.4.2.
After finishing all the initialization steps, AGC enters its main loop. In the main loop
AGC waits for change of the network topology representation status. In order not to perform
re-planning of the media streams transmissions after each change of the network topology
the AGC waits for the network topology status to settle down (i.e., last change of the network
topology status has to occur before a specified timeout). We use this approach in order
to avoid media streams planning when larger number of events occurs in a short period of
time, e.g., due to link flaps. Also deploying a new plan after each change in the still not
settled down network topology may result in rapidly changing state of the collaborative
environment and worsened user experience. This becomes important especially during establishing
of the collaborative environments when CoUniverse peers start to advertise the
configurations of respective nodes and AGC composes the network topology representation
based on this advertisements.
Once the network topology is settled or AGC decides that there was a significant change,
the Match Maker module is initialized on a snapshot of actual network topology. It is necessary
to obtain the snapshot atomically in order to perform the media streams planning on
a network topology with a consistent state. Also the network topology status is subject to
changes during the process of the media streams planning. Eventually, the Match Maker
module is initiated to perform the media streams planning (See Chapter 4 and Section 5.2
for detailed description of the media streams planning problem and implementation and
evaluation of the Match Maker module.).
After the Match Maker manages to find a feasible plan for the media streams transmissions
based on the network topology representation snapshot, AGC checks if the new plan
differs from the previously deployed plan. We perform this step in order not to deploy the
same plan again which would result in restarting of involved media applications and possibly
worsened user experience during a running session within the orchestrated collaborative
environment.
If the plan obtained from the Match Maker module differs from the previously deployed
plan, the AGC proceeds with processing and deployment of the new plan within the collaborative
environment. We describe deployment of the plan in Section 4.7 in the context
of the collaborative environment model provided to formulate the media streams planning
problem in Chapter 4. From the AGC point of view, the plan is being deployed in four steps:
1. The previous plan is being decomposed to a list of media applications. AGC then
sends Stop Media Application message to the CoUniverse peer of the parent node of
each media application. A result of this step is obviously that the media applications
stop sending their media streams over the network links. In this way AGC terminates
the effects of the previous plan.
2. A set of network links to be used for some media stream transmission is obtained from
the new plan. If some of the network links are associated with some lambda link then
AGC adds such lambda link to a list of lambda links to be allocated within the DCN
infrastructure. These lambda links are then passed to the Lambda Links Factory for
allocation. During the process the Lambda Links Factory passes an allocation request
to the DCN middleware for each lambda link which is not recently marked as ACTIVE
3.6. DYNAMICS OF THE COUNIVERSE MIDDLEWARE 49
by the monitoring module of the Lambda Links Factory (which means that the lambda
link in question was already allocated and is working). We further discuss details of
this process also in Section 5.3.
3. New plan is being decomposed into a list of media applications and respective network
links which are planned to be used for media streams transmissions between the
media applications. A configuration for each media application is created basically
from the network link (i.e., especially the IP address of the network link end network
interface is used as a target address for the media application to send the media stream
to) and the planned media stream type which may further influence the parameters
needed to invoke the media application properly. AGC then sends Start Media Application
message to the CoUniverse peer of the parent node of each media application
containing the parameters for the media application.
4. Finally, a set of all network links planned to be used for some media stream transmission
is obtained from the plan. For each network link its source node is determined
as a parent node of its beginning network interface. AGC then sends the Active Links
message containing the network link identification to the CoUniverse peer of the node
in question.
It is clear that the status of the network topology may have changed based on the results
of monitoring on individual CoUniverse peers which may result in the just deployed plan
not being feasible and viable. If such a network topology status is detected than ACG starts
to re-plan the media stream transmissions immediately. Once the network topology settles
status settles down, the eventually deployed plan becomes viable.
50 CHAPTER 3. COUNIVERSE DESIGN AND ARCHITECTURE
Algorithm 2 Life cycle of Application Group Controller
agc.initializeAGC();
agc.registerIncommingMessagesCallbacks();
agc.listenForIncommingMessages();
agc.lambdaMonitor.startMonitoring();
while !shouldExit do
networkTopologyStatus = networkTopology.getStatus();
if networkTopologyStatus.isChanged() then
networkTopologySnapshot = networkTopology.getWorkignSnapshot();
end if
agcMatchMaker = new MatchMaker(networkTopology)
agcMatchMaker.doMatch();
agcPlan = agcMatchMaker.getPlan();
if agcPlan != previousPlan then
for all planElement : previousPlan do
targetNode = planElement.getMediaApplication.getParentNode();
mediaApp = plan.Element.getMediaApplication();
agc.sendMessage(targetNode, STOP_APP, mediaApp);
end for
for all planElement : agcPlan do
for all networkLink : planElement.getNetworkLinks() do
for all lambdaLink : networkLink.getAssociatedLambdas() do
lambdaLinkFactory.allocate(lambdaLink);
end for
end for
end for
for all planElement : agcPlan do
targetNode = planElement.getMediaApplication.getParentNode();
mediaApp = planElement.getMediaApplication();
mediaAppParams = MediaAppParametersFactory.getAppParams(planElement);
agc.sendMessage(targetNode, START_APP, mediaApp, mediaAppParams);
end for
for all planElement : agcPlan do
for all networkLink : planElement.getNetworkLinks() do
targetNode = networkLink.getSourceNode();
agc.sendMessage(targetNode, MONITOR_LINKS, networkLink);
end for
end for
previousPlan = agcPlan.clone();
end if
end while
Chapter 4
Media Streams Planning Problem
The goal of our work is to provide self-organization capabilities for advanced collaborative
environments and distributed network-centric applications. The self-organization relies
among other concepts on explicit planning of media streams transmissions between components
of the collaborative environment using available network resources. Based on the
planned media streams transmissions it is possible to orchestrate the components of the environment
automatically even when media streams bandwidth demands are comparable to
the capacities of network links. In this chapter we formalize the description of the network
organization and components used for media streams planning. We further state the Media
streams planning problem (MSPP) and discuss the constraints and optimization criteria for the
media streams transmissions. Later in this chapter we prove the MSPP to be NP-hard and
show a number of possible preprocessing techniques to reduce the size of the MSPP state
space so that it is possible to obtain exact solutions of its instances in a reasonable time.
4.1 Definitions
4.1.1 Network Organization
Let V be a set of all nodes in the Universe and v  V be a particular node. Let SI be set of all
sites and s  SI be a particular site. Each node v  V belongs to a particular site s  SI if
site(v) = s.
Each node v  V has one or more configured network interfaces. Let I be a set of all
network interfaces and i  I be a network interface. Then node(i) = v where v  V is a
node v with configured network interface i. We define SN being a set of all subnetworks
and net  SN a particular subnetwork. Then for each i  I exists just one net  SN such that
subnet(i) = net. For each network interface i  I, cap(i) denotes its throughput.
Let e = (i, j) be an oriented network link from i to j where i, j  I. Then E = I × I denotes
a set of all network links and we denote a particular (directed) network link as e  E. For
each e  E such that e = (i, j) where (i, j)  I holds subnet(i) = subnet(j). We can define
following properties of a network link e  E: begin(e) = i such that e = (i, j)  i, j  I is
the originating interface i  I of the link e  E, end(e) = j such that e = (i, j)  i, j  I is
the terminating interface j  I of the link e  E. cap(e) denotes the link capacity and lat(e)
denotes the latency of the network link.
51
52 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
Figure 4.1 depicts a sample network of four different nodes with configured network interfaces.
node2 has two distinct network interfaces configured. Each i  I can be configured
as full-duplex or half-duplex. If both i, j  I are configured as full duplex then for e(i,j) = (i, j)
and e(j,i) = (j, i) holds e(i,j) = e(j,i). For each network link e  E, e = (i, j) its capacity cap(e)
is determined from the respective node interfaces configuration as min(cap(i), cap(j)) or
further from the monitoring.
A network link e = (i, j) where i, j  I exists iff both network interfaces belong to the
same subnetwork net  SN (i.e., subnet(i) = subnet(j) = net). Within a particular subnet all
possible network links (i, j)  I × I such that i = j may exist. That means we are considering
a full-mesh network links topology between interfaces of all nodes belonging to a particular
subnetwork.
Discussion
Subnetwork concept naturally describes a physical network infrastructure. An example
would be a node in a private network with a Native Address Translation (NAT) connected
to the rest of the network via a gateway. This situation is depicted in Figure 4.1 where node3
is the node behind NAT and node2 is the gateway. The network topology features two different
subnetworks net1 and net2. For the node interfaces hold subnet(ij) = subnet(ik) =
subnet(in) = net1 and subnet(im) = subnet(il) = net2. Both subnetworks are physically
separated and thus it is not possible for example to send any data from node3 directly to
node1 or node4.
Subnetworks as defined in our model may also be used to create logical networks over
a physical infrastructure. This is useful for example for limiting transmissions of media
streams over particular node interfaces and nodes.
Figure 4.1: Nodes, interfaces and network links example.
The network links are comprehended as end-to-end links between node interfaces and
thus they do not reflect the structure of real physical network topology. Each end-to-end
network link e  E in our model may be built using a number of physical network links,
switches and routers. The end-to-end network links model is built using only local information
about the configuration of the nodes (node interfaces and local media applications)
which is always available to the user even without having any administrative privileges.
This approach is also based on the fact that users running their nodes do not need to know
anything about the topology of the physical network interconnecting their nodes. In reality
4.1. DEFINITIONS 53
the physical network is usually spanning across several administrative domains which effectively
conceals any details of its topology. On the other hand an obvious disadvantage is
that the end-to-end network links model is not able to cover the situation when a number of
network links share a part of the physical network topology which is unknown within the
framework of the model. The Figure 4.2 depicts an example of two network links e1 and e2
sharing a common physical network infrastructure. Parameters of those network links (especially
their capacity) relying just on the local information known from the end interfaces
may not be necessarily correct in such case. If both links share a common physical infrastructure,
the capacity of one link may be obviously influenced by the data being transmitted over
the second link. Therefore parameters of the links must also rely on their active monitoring
(e.g., by means of probing the capacity of the links).
node1
ij
node2
ik
node1
ii
Shared network infrastructure
e1
e2
Figure 4.2: Example of end-to-end network links over shared network infrastructure.
The concept of sites allows us to arrange the media streams distribution so that some
application with a user defined functionality can be built on top of it. Sites, as defined in our
model, usually delimit nodes belonging to one particular real-world site (e.g., nodes configured
in the Laboratory of Advanced Networking Technologies, Masaryk University, Brno or
all nodes configured at CESNET). A straightforward example of such usage of sites would
be a videoconference between two sites (Brno and Baton Rouge). Such a videoconference
requires that some applications running on nodes at Brno site receives a video stream from
some application running on some node in Baton Rouge. Our concept takes into the account
a fact that there may be two users running their nodes, one for each site, who do not have
any exact idea about the configuration of the other site. In such situation the user running
the nodes (and applications) in Brno simply configures the video receiving application to
require a stream from the Baton Rouge site.
Sites may also be used to to arrange the media streams distribution in a more specific way.
Users can configure their nodes to be a part of a virtual sites within a real site and thus refine
the media streams distribution. An example would be a large scale multi-party videoconference
where multiple cameras are maintained to allow multiple views on the videoconference
participants. The cameras are connected to nodes running media stream producers. These
nodes may be attributed with different sites specifying where the camera is pointed to. In a
conference room site connected to the videoconference the sites could be site1.speaker_camera
and site1.audience_camera. Using these virtual sites the users configuring the media stream
consumers at their remote sites may specifically configure which media streams they want
to receive on the particular media stream consumers.
54 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
4.1.2 Lambda Links
Let L denote a set of lambda links. We can define L = I × I and l = (i, j) where i, j  I such
that i and j are configured to interface with some Lambda link endpoint. Lambda links are
associated with network links through the network interfaces. associated_lambdas(e)  L
then gives a set of lambda links l  L which are associated with a network link e  E.
Discussion
There are two main objectives to be achieved by introduction of lambda links associated
with network links. Firstly, lambda links exist in the real world and provide users with real
services for controlling and configuring a physical network infrastructure without having a
direct access to the network elements and administrative rights. Also, based on the lambda
links allocation it is possible to obtain a real physical network topology and use it as an input
for media streams planning.
Figure 4.3: Lambda links and physical network infrastructure example
From the perspective of scheduling of the media streams over lambda based network
links there is however quite an important issue remaining. To be able to employ the physical
network topology learned from the lambda links allocation (see Figure 4.3) we would have
to allocate all available lambda links before we proceed to the media streams scheduling.
Doing so is however complicated because of two reasons. The lambda links based network
is almost always shared among many users who have to allocate their lambda links. Consequently,
in advance allocation of all lambda based links would lead to wasting of network
resources in case that network links based on the allocated lambda links are in the end not
used for transmission of any media streams. Also, allocation of a single lambda link may
be a time consuming process (see Section 5.3.2 for reference) which can take time in order of
minutes. Although the lambda links allocation may be parallelized to a great extent, allocation
of all lambda links in advance would lead to longer times necessary for media streams
scheduling and deployment of the plan than in case when we allocate just those lambda
links which provide a base for network links over which some media streams transmissions
are actually scheduled.
4.1.3 Media Applications
Let P be a set of producers where p  P is a media application producer, C a set of consumers
where c  C is a media application consumer. Producers and consumers are running on nodes
4.1. DEFINITIONS 55
v  V. We define node(p) = v where v  V  p  P and node(c) = v where v  V  c  C
as a parent nodes of producer p and consumer c.
Media applications are capable of producing and consuming streams of particular types.
We denote the set of all stream types ST. Let st  ST be a media stream type produced by
a particular producer p  P. For each media stream type st  ST we define a minimal
bandwidth min_b(st) and maximal bandwidth max_b(st) functions returning positive integer
maximal and minimal bandwidth necessary to transmit the stream over a network link
e  E. Moreover, for each st  ST we can define a quality function qual(st)  [qmin, qmax]
which is used to distinguish a subjective quality of the media stream types.
Each producer p  P can produce a set of streams of particular types stypes(p)  ST.
Each consumer c  C is capable of consuming a set of stream types stypes(c)  ST. We
denote S as a set of all actual media streams (i.e., the real streams of data) and s  S an
actual media stream. The function stype(s) = st returns the stream type st  ST for each
media stream s  S. For each stream s  S we define begin(s)  P  D as a source media
application and end(s)  D  C as a target media application1.
We furthermore define a function requested_site(c) = si which for each media application
consumer c  C returns a site si  SI. si = requested_site(c) is a site within which
a media streams producer with compatible media stream types is sought and eventually a
stream between this media streams producer and consumer is planned.
Discussion
A media application producer can be an arbitrary application (e.g., UltraGrid, VideoLan
client (VLC), VIC or other) which is able to produce media streams. The media stream can
be any stream of data (e.g., stream of video data) of given type. An example of stream types
for video stream would be uncompressed HDTV video, HDV MPEG2 video, HDV MPEG4
video or CIF H.261 video. For each stream type produced by the media application we can
tell the min_b(st) and max_b(st). For a constant bitrate stream holds min_b(st) = max_b(st)
while min_b(st) < max_b(st) for a variable bitrate or bursty stream. qual(st) could be easily
demonstrated for example on st1 being a HDV MPEG2 stream produced by VLC and st2
being a CIF H.261 stream produced by VIC. For such streams definitely holds qual(st2)
qual(st1). Media application consumer can be again an application like UltraGrid or VLC.
4.1.4 Media Distributors
Let D be a set of media distributors. d  D is then a particular media distributor. Typically
an Active Element (AE) can be used as a media distributor. Each media distributor d  D is
running on a node v  V. We define node(d) = v where v  V  d  D being a parent node
of a media distributor d in the same way as for media producers and consumers.
For each media distributor d  D we define its transcoding capability as transcode(d) 
ST × ST where transcode(d) = {(stin, stout) | stin, stout  ST} is a set of input and output
stream types a particular media distributor is able to transcode between. For a reflector type
media distributor without transcoding capabilities we define transcode(d) = {(st, st) | st 
ST}. I.e., such a media distributor can consume a stream of any type and produce some
number of exact copies of the consumed stream.
1See definition of D in Section 4.1.4.
56 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
Discussion
Each media distributor consumes exactly one stream and is able to proliferate this stream
to one or more consumers. For a reflector type media distributor the capability to proliferate
the incoming stream further to the media stream consumers is limited only by the
interfaces capacity of the node on which the media distributor is running. The capability
to proliferate the consumed media stream may be considerably limited for media distributor
with transcoding capabilities. Let us consider a media distributor d  D capable of
transcoding between uncompressed HDTV video, HDV MPEG2 video and HDV MPEG4
video. I.e., transcode(m) = {(HDTV, HDVMPEG2), (HDTV, HDVMPEG4)}. Now let
us assume that this media distributor is scheduled to consume a stream of uncompressed
HDTV video type and proliferate this stream to two consumers where one of those is able to
consume a stream of HDV MPEG2 type while the other one is able to consume a stream of
HDV MPEG4 type. Such a transcoding and distribution of media streams however imposes
heavy load on the node where such a media distributor was configured and scheduled. We
do not support scheduling of media applications or media distributors scheduling based on
nodes performance and the applications or distributors load in our model. The configuration
of media distributors transcoding capabilities is completely left on the users and users have
to decide if the node where the media distributor is configured has performance reserves for
its transcoding capabilities.
Media stream distributors can be also used as bridges between different subnetworks.
In such case the media distributor may produce even just a single copy of the consumed
stream. This mode of operation of the media stream distributor can be exploited for example
to traverse NATs.
4.1.5 Stream Links
Stream links are the basic entity to be scheduled in our model. A stream link is a tuple
(e, s)  E × S. We denote the set of all stream links as SL. A stream link is an abstraction of
a fact that a stream s is being transmitted over particular network link e.
Figure 4.4: Stream link.
4.2 Media Streams Distribution
The input for media streams distribution planning is the set of all nodes V and its network
interfaces I. The set of network links E is generated based on the properties of the network
interfaces (interface capacity, subnetwork2). Properties of all network links may be obtained
2Note that a full-mesh network links topology is created between all interfaces belonging to a particular
subnetwork.
4.2. MEDIA STREAMS DISTRIBUTION 57
from the properties of respective network interfaces except the latency which is an output of
the network link monitoring3. The nodes together with the network links create a directed
graph G = (V, E). Furthermore, the media streams planning input includes all media applications
P  C  D available on the nodes v  V. For each producer p  P and consumer
c  C the planning relies on stypes(p) and stypes(c) (i.e., the types of the streams the producers
and consumers are able to transmit and receive). For each d  D the media streams
planning input includes transcode(d) (i.e., set of stream types pairs the media distributor is
able to transcode between). Finally, for each c  C the requested site requested_site(c) is
used as an input information for the media streams planning.
Based on this input the goal is to find a set of media stream distribution trees ideally for
all consumers c  C covering producers p  P so that c  C holds requested_site(c) = p.
In a real world a partial set of distribution trees not covering all producers and consumers is
also sufficient especially in case where covering all consumers is not feasible. We can break
down each distribution tree into a set of paths between single media stream producer and
single media stream consumer. Lets denote such path as p c = {(e1, s1), (e2, s2) . . . (en, sn)}
where ei  E, si  S and p = begin(s1), c = end(sn). If a stream link (e, s)  SL is a part of a
path p c we use a notation (e, s)  p c.
node
appp
appdappc1
appc2
e1
e2 e3
s1
s1 s2
Figure 4.5: Media streams distribution tree.
Figure 4.5 shows a single media streams distribution tree with a stream s1 being produced
by media streams producer appp and distributed by media distributor appd to two media
streams consumers appc1
and appc2 . Media distributor appd is capable of media streams
transcoding such that
transcode(appd) = {(stype(s1), stype(s1)), (stype(s2), stype(s2)), (stype(s1), stype(s2))}.
The above mentioned media streams distribution tree can be broken down to a set of paths
{appp appc1
, appp appc2 } where appp appc1
= {(e1, s1), (e2, s1)} and appp
appc2 = {(e1, s1), (e3, s2)}. Note that network interfaces are omitted to simplify the diagram.
There are three main goals to meet which describe our requirements on the media streams
distribution in the collaborative environment. The cardinality of the set of all paths p c
3Note, that for the purposes of the Media Streams Planning Problem description we understand the set of
all network links E to contain only those network links which were qualified as active based on the monitoring.
Refer to Sections 3.4.2 and 3.6 for more details.
58 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
has to be maximal which means that our goal is to cover as much media stream consumers
by media streams produced by producers from requested sites as is feasible. Our second goal
is to minimize the latency of such media streams distribution and last but not least we want
to maximize its quality. A number of other rules hold for the media streams distribution.
These rules are described in the next sections.
4.3 Media Streams Planning Problem
The problem of many applications in networks is to decide which path to use for satisfying
certain demands. A control algorithm is responsible for assigning paths for individual
demands under the constraints posed by the application and the network. Such a problem
may be expressed as a path placement. Simonis [121] considers three alternative models for
solving this problem:
* link-based ­ For each demand there is one decision variable per link which states if the
link is used to satisfy the demand or not.
* path-based ­ For each demand there is one decision variable considered per possible
path between the source and the target of the demand. Exactly one path may be chosen
per demand.
* node-based ­ For each demand there is one decision variable considered for each node
in the network. The value of the decision variable states if the node is used to satisfy
the demand or not.
Simonis furthermore presents two variants of the path placement problem. The demand
acceptance problem is based on a set of demands which are to be satisfied without exceeding
the capacity limits of the network. The interesting point is to find a solution which maximizes
the value of accepted demands. Furthermore, the traffic placement problem is based on
a fixed set of demands. All of the demands have to be satisfied in the network. With the traffic
placement problem a solution is sought such that a maximal utilization over all network
links is minimized.
The Media Streams Planning Problem (MSPP) is new media streams routing and placement
problem. We formulate the MSPP based on the demand acceptance problem in the linkbased
model using the classification by Simonis. Let us first quote Simonis formulating the
demand acceptance problem in link-based model:
The network consists of a set of nodes N and a set of directed edges E. The set
OUT(n) consists of all edges leaving node n, the set IN(n) of all edges leading
to node n. The capacity of an edge is given by cap(e). The source of an edge is
denoted as source(e), the sink as sink(e). For every demand in the set D, we have
a source (orig(d)) and a destination (dest(d)), a bandwidth requirement bw(d)
and a value val(d) which indicates the benefit of accepting demand d.
The {0, 1} variable Xde denotes whether demand d is routed over edge e of
the network. For every demand d we also have one {0, 1} decision variable Zd
which indicates if the demand is accepted or not. The following model gives a
mixed-integer linear programming formulation:
4.4. MEDIA STREAMS PLANNING PROBLEM EXPRESSED USING CONSTRAINTS 59
max
Zd,Xde

dD
val(d)Zd (4.1)
s.t.
d  D, v  V 
eOUTn
Xde - 
eINn
Xde =



-Zd n = dest(d)
Zd n = orig(d)
0 otherwise
(4.2)
e  E : 
dD
bw(d)Xde  cap(e) (4.3)
The path constraint 4.2 states that there is a single path for each accepted
demand, linking the Zd and Xde variables. Equation 4.3 states the capacity constraint,
that for each link the amount of traffic routed over it must be smaller than
the link capacity. The objective 4.1 is to maximize the value of accepted demands.
The essence of the MSPP is to find a mapping of media streams (demands) on network
links (with limited capacity) to create a set of media stream distribution trees for producers
p  P covering the consumers c  C. Formally we are looking for set of stream links SL =
E × S. We plan the stream links so that (e, s) = 1 where (e, s)  SL for a stream link that is
planned to be actively used for data distribution and (e, s) = 0 where (e, s)  SL for unused
stream link. For sake of brevity in the text below, we say that stream link (e, s) exists iff
(e, s) = 1. It is also necessary to note that the MSPP does not consider a time domain to be
a part of the planning problem. As we are considering the MSPP in the context of ad-hoc
collaborative environments we always plan the transmissions of the media streams taking
into the account an actual state of the underlying network infrastructure.
The model described by Simonis and the MSPP share many common properties. The
link-based model of the demand acceptance problem does not cover the MSPP in its entirety.
The link-based model proposed by Simonis especially for example precludes media streams
distribution in the network by using the path constraint 4.2 whereas the media streams distribution
is an important part of the MSPP.
4.4 Media Streams Planning Problem Expressed Using Constraints
We formulate and solve the MSPP as a Constraint Satisfaction Problem (CSP) [35]. Speaking
in terms of network model given in previous sections the constraints and objectives put on
the MSPP look as follows:
Stream links constraints
* (e, s)  SL, (e, s) = 1. max_b(stype(s))  cap(e)
Parent network link e of the stream link must have sufficient capacity to transmit the
media stream s.
* i  I, (e, s)  SL. 
((e,s)=1)((i=begin(e))(i=end(e))
max_b(stype(s))  cap(i)
All streams transmitted over a any single network interface must not exceed its capacity.
This requirement emerges from the fact that relying on the end-to-end network
topology means that several links may begin or end in a single network interface.
60 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
* (e, s)  SL, (e, s) = 1. p  P such that (node(p) = node(begin(e)))  (begin(s) = p)
or d  D such that (node(d) = node(begin(e)))  (begin(s) = d)
Each stream link must have producer or media distributor on its beginning node.
* (e, s)  SL, (e, s) = 1. c  C such that (node(c) = node(end(e)))  (c = end(s)) or
d  D such that (node(d) = node(end(e)))  (d = end(s))
Each stream link must have a consumer or media distributor receiving data using the
stream link.
Producer constraints
* p  P. {c  C | requested_site(c) = site(node(p))} > 1 implies (e, s)  SL such
that begin(s) = p  end(s) = c and (e, s) = 1
More than one consumer for a particular producer means that there cannot be any direct
stream link between consumers and respective producer as the producer has to send the
media stream through at least one media distributor.
Consumer constraints
* c  C. {(e, s)  SL | ((e, s) = 1)  (c = end(s))} = 1
Media stream for each consumer is received using exactly one stream link.
* c  C such that (requested_site(c) = )  (requested_site(c)  SI). (e, s)  SL such
that (e, s) = 1 and c = end(s)
There are no media streams for any of inactive consumers (i.e., those that have not
requested any data from any producer).
* If {(p, c) | p  P, c  C, p c} = {c  C | (requested_site(c) = )  (requested_site(c) 
SI)} then one of the following constraints holds:
c  C. p  P such that (e, s)  SL where (e, s) = 1, (begin(s) = p)  (end(s) = c)
and requested_site(c) = site(node(p))
or
c  C. d  D such that (e, s)  SL where (e, s) = 1, (begin(s) = d)  (end(s) = c)
If there exists a feasible solution covering all media stream consumers then each active
consumer has to be covered by the requested producer either directly or through some
media distributor. If this is not the case such a constraint would preclude a possible
partial results where e.g., not all consumers are covered by some producer. Therefore
the cardinality of set of all paths p c maximization criterion is more appropriate for
this case (see Objectives and Optimization criteria).
Data distribution tree constraints
* p  P, {c  C | requested_site(c) = site(node(p))} = 1 implies
{(e, s)  SL | (e, s) = 1}  1, D + 1
Number of used stream links for producers with only one consumer is greater or equal
to number of producers. That means data may go either directly, or through some
forwarding or transcoding media distributor (typically in case that direct sending is
not available for one reason or another). Number of stream links obviously must not
exceed number of all the media distributors in the network plus one.
4.4. MEDIA STREAMS PLANNING PROBLEM EXPRESSED USING CONSTRAINTS 61
* Let CP = {c  C | requested_site(c) = site(node(p))}. Then p  P, CP > 1 implies
{(e, s)  SL | (e, s) = 1}  CP + 1, D + CP
Minimal number of used stream links is greater or equal to number of consumers for
given producer plus one for multipoint data distribution. Upper bound is a number of
consumers for given producer plus number of all the media distributors.
* c  C, p c implies requested_site(c) = site(node(p))
If there is a path of stream links scheduled, the producer must be configured on a node
within a site that was requested in the media stream consumer configuration.
* c  C, (e, s)  SL such that (e, s) = 1 and c = end(s) implies stype(s)  stypes(c)
Each active consumer must receive an appropriate stream.
Media distributor constraints
* d  D such that (e, s)  SL, (e, s) = 1 and d = end(s). {p  P | (p = begin(s)) 
(d = end(s))} = 1 or {dp  D | (dp = begin(s))  (d = end(s))} = 1
A single media distributor instance can only serve for distribution of data from a single
producer or another media distributor.
* d  D. (e, s)  SL such that ((e, s) = 1)  (d = end(s)) implies c  C such that
(node(d) = node(c))  (c = end(s))
Media distributor is not scheduled together with another consumer for the same media
stream on a single node. There are basically two reasons for introducing of such
constraint. The first being that we do not consider network links such that e = (i, i)
(i.e., loopback links). If the media consumer were scheduled on the same node as the
consumer there exists no network link to schedule the stream from the media distributor
to the consumer on. The second reason is a general addressing problem as we
have no means how to distinguish between e.g., a consumer and a distributor to receive
the stream running on a single node. A real-world example equals to considering
addressing of any media application using just IP address (IP address configured on
the end interface of the network link scheduled to transfer the stream). Thus it is also
not practical to run both media distributor and the consumer on the same node.
* d  D holds {(e, s)  SL | ((e, s) = 1)  (d = begin(s))}
 {(e, s)  SL | ((e, s) = 1)  (d = end(s))}
There has to be at least the same number of egress media streams as ingress media
streams for particular media distributor.
* (ei, si), (ej, sj)  SL, (ei, si) = 1, (ej, sj) = 1 where d  D such that d = end(si)  d =
begin(sj) holds (stype(si), stype(sj))  transcode(d)
For each pair of stream links such that (ei, si) ends in media distributor d and (ej, sj)
originates from the very media distributor holds that media distributor d is able to
transcode stream si to stream sj.
Link capacity constraint
* e  E, (e, s)  SL holds 
sS
max_b(stype(s))  (e, s)  cap(e) where (e, s) = {0, 1}
Maximal bandwidth requirements of all the scheduled stream links (e, s)  SL must not
62 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
exceed capacity of the link e  E the stream links are bound to. Using maximal bandwidth
requirements of each stream type is straightforward for variable bitrate stream
types. For constant bitrate stream types maximal bandwidth requirements can conceal
a bursty character of such stream. E.g., setting max_b(stype(s)) = 6 Gbps for stream s
of uncompressed HDTV video stream type which has a constant bitrate of 1.5 Gbps and
bursty character guarantees that even the bursts will be accommodated by the link e.
Objectives and Optimization criteria
* p  P and c  C, {(p, c) | p  P, c  C, p c} has to be maximal.
Our goal is to cover as much media stream consumers by media streams produced by
media stream producers from requested sites as is feasible.
Moreover the following optimization functions can be used to fine tune the latency and
quality aspects of the media streams distribution.
* Global latency minimization

(e,s)SL(e,s)=1
lat(e)  (e, s) has to be minimal.
If multiple network links could be used for the media streams distribution, we use those
with lower latency to minimize the global latency of all media streams distribution.
* Global quality maximization

(e,s)SL(e,s)=1
qual(stype(s))  (e, s) has to be maximal.
Where multiple stream types might be used at least for some portions of the media
streams distribution trees we use those with maximal quality available.
* Path latency balancing
max{lat(e)  (e, s) | (e, s)  SL} - min{lat(e)  (e, s) | (e, s)  SL} has to be minimal.
Path latency balancing criterion guarantees that all media streams are received by the
media stream consumers with as equal latency as possible. This is an important criterion
especially for videoconferencing where all parties have equal chance to interrupt
and enter an ongoing conversation or in gaming environment to avoid getting competitive
advantage.
* Weighted path latency minimization
For a path p c we can define its latency as lat(p c) = 
(e,s)p c
lat(e)  (e, s). Moreover,
for each c  C we define a weight wc = [0, 1]. Then 
pP,cC,p c
wc  lat(p c) has
to be minimal.
For some applications it might be useful to stress an importance of a particular media
steam consumer and respective media stream distribution path. The example would be
a case where two types of media streams are distributed over a shared infrastructure.
One stream type is distributed and used for interactive collaboration over the stream
content while the other stream type is used for supportive videoconference. In this
case the first mentioned stream type distribution is clearly more important which can
be expressed using different weights with the media stream consumers used for the
interactive collaboration and the videoconference. If there are multiple network links
4.5. COMPLEXITY OF MEDIA STREAMS PLANNING PROBLEM 63
available for the media streams distribution, those with lower latency would be used
to distribute the streams used for the interactive collaboration.
* Weighted path quality maximization
For a path p c we define its quality as qual(p c) = 
(e,s)p c
qual(stype(s))  (e, s).
Then using the same weight as defined for previous optimization we can define the
weighted path quality maximization so that 
pP,cC,p c
wc  qual(p c) has to be max-
imal.
Using Weighted path quality maximization we can distinguish media stream consumers
(and respective media distribution paths) where the stream type quality of the received
stream is more important in comparison to other streams distribution paths. The example
is quite similar as in the case of Weighted path latency minimization criterion. Let us
imagine an application where users collaborate over a high-quality streams with medical
content and are using videconference to support the collaboration at the same time.
In such case it might be beneficial to stress the importance of the media stream receivers
configured to process the streams with medical contents. If multiple stream types are
available for distribution of both medical content and videoconference streams, those
with higher quality are used for the streams distributing the medical content.
The latency and quality optimization criteria are intended to be used together. It is meaningful
to use only one of the latency optimization criteria together with single quality optimization
criterion out of those available at a time. For distinct applications built on the
media streams distribution only a single optimization criterion or a distinct combination
of optimization criteria may be selected. An example would be an interactive high-quality
multi-party videoconference where a combination of Global quality maximization and Path
latency balancing criteria is most beneficial.
4.5 Complexity of Media Streams Planning Problem
To show the complexity of the MSPP we formulate a relaxed media streams planning problem
as a simplified version of the full MSPP. To show its complexity we use a Linear-time
reduction technique [49, 55] to reduce the 0­1 Multiple Knapsack problem (MKP) [81, 108]
with well known properties onto our relaxed media streams planning problem.
4.5.1 0­1 Multiple Knapsack problem
The family of knapsack problems generally considers some items attributed with a profit pj
and weight wj which are packed into one or more knapsacks while taking into the account
the capacity of the knapsack W. If we have n items to pack into m knapsacks with (possibly
different) capacity Wi the 0­1 MKP is stated as follows:
64 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
maximize
m

i=1
n

j=1
pjxij
subject to
n

j=1
wjxij  Wi, for all 1  i  m
m

i=1
xij  1, for all 1  j  n
xij  {0, 1}, for all 1  j  n and all 1  i  m
If item j is packed into the knapsack i then holds xij = 1 else holds xij = 0. The constraint
n
j=1 wjxij  Wi guarantees that the capacity of the knapsack i is not exceeded. Moreover, the
constraint m
i=1 xij  1 enforces that each item is chosen to be put into the knapsack at most
once. The above stated 0­1 MKP problem is recognized to belong to the class of NP-hard
problems [81].
4.5.2 Relaxed Media Streams Planning Problem with Streams Quality Maximiza-
tion
Let us assume a relaxed variant of the MSPP with two network nodes node1, node2 and m network
links e, e = 1, . . . , m between these two nodes. There are n media distributors d1 . . . dn
available on both node1 and node2. Furthermore, we have n producers p1 . . . pn available on
their own nodes and n consumers c1 . . . cn available on another set of their own nodes. All
nodes belong to the same site site. For each ci  {c1 . . . cn} holds requested_site(ci) = site.
Each node with producer pi is connected by a single network link with node1. Likewise, each
node with consumer ci is connected via a network link with node2. There are m network links
available between node1 and node2. No other network links than those explicitly described
above are considered4. Each network link has assigned its capacity CAPe. The topology of
above described network is illustrated at Figure 4.6.
The producers p1 . . . pn are producing media streams s, s = 1, . . . , n. For each stream
we can tell its quality quals. The quality of the stream is in fact the profit in the MKP sense.
Moreover each media stream has its maximal bandwidth max_bs defined. Speaking in terms
of the MKP the maximal bandwidth of the stream is the weight of the stream. The streams
produced by producers p1 . . . pn can be received just by the media distributors running on
node1, further transmitted to media distributors running on node2 and finally received by
the consumers. The relaxed media streams planning problem now lies in planning of the
transmission of these n streams over the m network links between node1 and node2.
The only constraint of the relaxed MSPP is the link capacity constraint which is paramount
for the media streams distribution. A number of constraints of the original planning problem
hold trivially for its relaxed variant described above. Without loss of generality we can ignore
the rest of the constraints of the original MSPP to formulate its relaxed variant5. Doing
so, any solution of the original problem still remains a valid solution of the relaxed media
streams planning problem.
When considering only the global quality maximization objective described with the
MSPP, the problem can be reformulated as follows:
4This can be achieved by the means of subnetworks suitably assigned to respective network interfaces.
5This is equivalent to setting stypes(p) = stypes(c) = ST p  P, c  C and transcode(m) = ST × ST
d  D.
4.5. COMPLEXITY OF MEDIA STREAMS PLANNING PROBLEM 65
p1 p2 p3 pn
c1 c2 c3 cn
d , ...1 dn
d , ...1 dn
e ,1 em...
node1
node2
Figure 4.6: Network topology for the relaxed MSPP. Note that the diagram is simplified.
maximize
m

i=1
n

j=1
qualjxij
subject to
n

j=1
max_bjxij  CAPi, for all 1  i  m
m

i=1
xij  1, for all 1  j  n
xij  {0, 1}, for all 1  j  n and all 1  i  m
In this case xij = 1 represents a fact that a media stream j was planned to be transmitted
over a network link i and xij = 0 otherwise. In terms used for the MSPP statement the xij is
actually the stream link (i, j)  SL, where i  E and j  S.
4.5.3 Relaxed Media Streams Planning Problem with Network Links Latency
Minimization
Let us consider another similar variant of the relaxed MSPP. The topology of the network
remains the same as in the previous case (see Figure 4.6 and its description in the previous
section for reference). Again we have to plan the transmission of n media streams transmitted
between media distributors on node1 and node2 over m network links between these
nodes. Equally as in the previous case each network link has assigned its capacity CAPe.
For each network we can distinguish its latency late. The latency of the network links can be
seen as its quality. Identically to a previous case each for each media stream we define its
maximal bandwidth max_bs which in terms of the Knapsack problem is its weight.
66 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
Let us take into the account only the global network latency minimization objective as
was defined for the MSPP. To show the complexity of this variant of the MSPP we again
show its reduction to 0­1 MKP problem.
To be able to do so we have to convert the network links latency minimization objective
(quality minimization) into a maximization objective. The conversion is fortunately straightforward.
Let us define LAT = 2  eE late being a double of sum of all stream links latencies.
LAT is a finite positive integer as the latency of a single network link late is naturally a positive
integer and we deal with a finite set of network links E. Also, naturally holds that
LAT - late > 0 for each e  E.
Now, we can formulate the Relaxed Media Streams Planning Problem with global latency
minimization as traditional 0­1 MKP problem:
maximize
m

i=1
n

j=1
(LAT - lati)xij
subject to
n

j=1
max_bjxij  CAPi, for all 1  i  m
m

i=1
xij  1, for all 1  j  n
xij  {0, 1}, for all 1  j  n and all 1  i  m
xij = 1 represents a fact that a media stream j was planned to be transmitted over a
network link i and xij = 0 otherwise. Again, xij is actually the stream link (i, j)  SL, where
i  E and j  S.
4.5.4 Discussion
We have shown that it is possible to reformulate the NP-hard 0­1 MKP problem as the
relaxed MSPP even with different objectives to achieve (quality maximization and latency
minimization of the media streams distribution). The transformation is quite straightforward
and in fact involves merely renaming of the variables used to state the 0­1 MKP problem.
Moreover, for any relaxed variant of the MSPP there is a reduction which generates an
instance of the original MSPP.
The reduction involves the following two steps:
* p  P, c  C. stypes(p) = stypes(c) = ST
* d  D. transcode(d) = ST × ST
In this way any algorithm solving the original MSPP would also provide a valid solution
to both of its relaxed variants. Thus finding an exact and optimal solution for the MSPP is
also an NP-hard problem. In reality the instances of the original MSPP are more complicated
as they involve usually tens of nodes. Moreover, there are additional constraints to meet, e.g.,
those involving matching of media types.
As we have proved that the MSPP is NP-hard there is no other known exact solution
technique than a complete enumeration of its state space. On the other hand it is possible
to save quite a lot of effort by using techniques extensively described by Ibaraki in [74, 75]
and summarized for example by Pisinger in [108]. Out of these techniques we have used
especially the preprocessing of the media streams planing problem state space. The basic idea
4.6. SIMPLIFYING THE MEDIA STREAMS PLANNING PROBLEM 67
of the preprocessing technique is to fix the values of as much variables as possible to their
optimal values by using bounding tests which exclude those values which are known not to
lead to a feasible solution. In this way it is possible to obtain exact solutions for Knapsack
instances of considerable size in a reasonable time.
Concerning the MSPP we have identified a number of possibilities for preprocessing of
the planning state space. The first technique involves precomputation (matching) of media
stream producers and media stream consumers in the way that media stream producer and
respective media stream consumers are fixed prior to the media streams scheduling. The
second technique is based on specific properties of the network links which induce that no
feasible media streams distribution may incorporate a stream link based on the network link
in question. Both techniques are in details discussed in the following sections.
4.6 Simplifying the Media Streams Planning Problem
In order to reduce the size of MSPP state space we first reformulate the planning problem using
reflector type media distributors instead of media stream distributors with transcoding
capabilities. I.e., for any simplified version of the MSPP we consider only media distributors
without any transcoding capabilities. Based on this relaxation of the original planning problem
we can implement matching of media stream producers and media stream consumers as
a preprocessing of the planning problem state space. Using the pre-matched sets of media
stream consumers and respective media stream producers we are able to further relax the
planning problem by dropping some of the constraints of the original one. Finally, we will
show preprocessing of the MSPP state space based on the properties of the network links.
4.6.1 Simplified Media Streams Planning Problem with Reflector Type Media
Distributors
Reflector type media distributor d  D is not capable of media streams transcoding and
is used just to distribute the stream produced by media stream producer p  P to one or
more media stream consumers c  C. For a reflector type media distributor d  D holds
transcode(d) = {(st, st) | st  ST}. In such case the type of any stream will not change for
any distribution tree between the media streams producer and respective media stream consumers.
This means that we can work with each path as p c = (e1, s), (e2, s) . . . (en, s)
where s  S is the stream produced by p  P. Thus there is a direct mapping of the
stream s and the producer p and we can simplify the planning model by substituting the
stream with its producer. Taking this into the account for any path p c holds p c =
(e1, p), (e2, p) . . . (en, p). Again, if a stream link (e, p)  SL is a part of a path p c we
use a notation (e, p)  p c. Also, we can now define the quality, minimal and maximal
bandwidth directly as a function of media streams producer p  P (i.e., media streams producer
is producing a media stream with quality qual(p), minimal bandwidth min_b(p) and
maximal bandwidth max_b(p)).
The input for the simplified MSPP with reflector type media distributors remains the
same as in the case of previously discussed generic MSPP. The only difference is that we do
not consider transcode(d) for each d  D as a part of the input in this case.
68 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
The output in case of the simplified planning problem with reflector type media distributors
is again a set of stream links. Taking into the account that we have omitted the transcoding
capabilities of media distributors we can denote a set of all stream links SL = E × P
where (e, p)  SL is a particular stream link. Scheduler plans the stream links so that
(e, p) = 1 where (e, p)  SL for a stream link that is planned to be actively used for data
distribution in the Universe and (e, p) = 0 where (e, p)  SL for unused stream link. For
sake of brevity in the text below, we say that stream link (e, p) exists iff (e, p) = 1.
Introduction of reflector type media distributors allows us to omit all constraints related
to the media streams transcoding capabilities of the media distributors and furthermore provides
a basis for formulating the simplified MSPP with precomputed matching of consumers
and producers. The set of constraints for the simplified MSPP with reflector type media distributors
is then defined as follows:
Stream links constraints
* (e, p)  SL, (e, p) = 1. max_b(p)  cap(e)
Parent network link e of the stream link must have sufficient capacity to transmit the
media stream p.
* i  I, (e, p)  SL. 
((e,p)=1)((i=begin(e))(i=end(e))
max_b(p)  cap(i)
All streams transmitted over a any single network interface must not exceed its capacity.
* (e, p)  SL, (e, p) = 1. node(p) = node(begin(e))  d  D such that node(d) =
node(begin(e))
Each stream link must have producer or media distributor on its beginning node.
* (e, p)  SL, (e, p) = 1. c  C such that node(c) = node(end(e)) or d  D such that
node(m) = node(end(e))
Each stream link must have a consumer or media distributor receiving data using the
stream link.
Producer constraints
* p  P. {c  C | requested_site(c) = site(node(p))} > 1 implies (e, p)  SL such
that node(p) = node(begin(e))  node(c) = node(end(e)) and (e, p) = 1
More than one consumer for a particular producer means that there cannot be any direct
stream link between consumers and respective producer as the producer has to send the
media stream through at least one media distributor.
Consumer constraints
* c  C. {(e, p)  SL | ((e, p) = 1)  (node(c) = node(end(e)))} = 1
Media stream for each consumer is received using exactly one stream link.
* c  C such that requested_site(c) =   requested_site(c)  SI. (e, p)  SL such
that (e, p) = 1 and node(c) = node(end(e))
There are no media streams for any of inactive consumers (i.e., those that have not
requested any data from any producer).
4.6. SIMPLIFYING THE MEDIA STREAMS PLANNING PROBLEM 69
* c  C. p  P such that (e, p)  SL where (e, p) = 1, (node(p) = node(begin(e))) 
(node(c) = node(end(e))) and requested_site(c) = site(node(p))
or
c  C. d  D such that (e, p)  SL where (e, p) = 1, (node(d) = node(begin(e))) 
(node(c) = node(end(e)))
Each active consumer has to be covered by the requested producer either directly or
through some media distributor.
Data distribution tree constraints
* p  P, {c  C | requested_site(c) = site(node(p))} = 1 implies
{(e, p)  SL | (e, p) = 1}  1, D + 1
There is at least one stream link existing for all producers with only one consumer.
That means data may go either directly, or through some forwarding media distributor
(typically in case that direct sending is not available for one reason or another). Number
of stream links obviously must not exceed number of all the media distributors in the
network plus one.
* Let CP = {c  C | requested_site(c) = site(node(p))}. Then p  P, CP > 1 implies
{(e, p)  SL | (e, p) = 1}  CP + 1, D + CP
Minimal number of existing stream links is greater or equal to number of consumers
for given producer plus one for multipoint data distribution. Upper bound is a number
of consumers for given producer plus number of all the media distributors.
* c  C, (e, p)  SL such that (e, p) = 1 and node(c) = node(end(e)) implies
requested_site(c) = site(node(p))
Each active consumer has to be covered by a producer from the requested site.
* c  C, (e, p)  SL such that (e, p) = 1 and node(c) = node(end(e)) implies
stypes(c)  stypes(p) = 
Each active consumer must receive an appropriate stream.
Media distributor constraints
* d  D, (e, p)  SL such that (e, p) = 1 holds
{p  P | (node(p) = node(begin(e)))  (node(d) = node(end(e)))} = 1
A single media distributor instance can only serve for distribution of data from a single
producer.
* d  D. m distributes data from p implies c  C such that node(d) = node(c)
Media distributor is not scheduled together with another consumer for the same producer
on a single node.
* d  D holds {(e, p)  SL | ((e, p) = 1)  (node(d) = node(begin(e)))}
 {(e, p)  SL | ((e, p) = 1)  (node(d) = node(end(e)))}
There has to be at least the same number of egress media streams as ingress media
streams for particular media distributor.
70 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
Link capacity constraint
* e  E, (e, p)  SL holds 
pP
max_b(p)  (e, p)  cap(e) where (e, p) = {0, 1}
That is bandwidth requirements of all the scheduled stream links (e, p) must not exceed
capacity of the link e the stream links are bound to.
Objectives and Optimization criteria
* p  P and c  C, {(p, c) | p  P, c  C, p c} has to be maximal.
Our goal is to cover as much media stream consumers by media streams produced by
media stream producers from requested sites as is feasible.
All optimization criteria stated with the original MSPP can be reformulated as follows6:
* Global latency minimization

(e,p)SL(e,p)=1
lat(e)  (e, p) has to be minimal.
* Global quality maximization

(e,p)SL(e,p)=1
qual(p)  (e, p) has to be maximal.
* Path latency balancing
max{lat(e)  (e, p) | (e, p)  SL} - min{lat(e)  (e, p) | (e, p)  SL} has to be minimal.
* Weighted path latency minimization
For a path p c we can define its latency as lat(p c) = 
(e,p)p c
lat(e)  (e, p).
Moreover, for each c  C we define a weight wc = [0, 1]. Then 
pP,cC,p c
wc  lat(p c)
has to be minimal.
* Weighted path quality maximization
For a path p c we can define its quality as qual(p c) = 
(e,p)p c
qual(p)  (e, p).
Then using the same weight as defined for previous optimization we can define the
weighted path quality maximization so that 
pP,cC,p c
wc  qual(p c) has to be max-
imal.
4.6.2 Simplified Media Streams Planning Problem with Precomputed Matching
of Consumers and Producers
Let producer(c)  P is the requested producer for consumer c  C. For each c  C we define
producer(c) = p such that requested_site(c) = site(node(p)) and stypes(c)  stypes(p) =
. The output of producer(c) is not unambiguous as there may be more suitable producers
in the site requested by the consumer in question. In such case we get producer(c) simply as
a first match. If there is no suitable producer found for some consumer then such a consumer
cannot be covered by any media streams distribution tree.
6See Section 4.3 for the description of the optimization criteria and for reference.
4.6. SIMPLIFYING THE MEDIA STREAMS PLANNING PROBLEM 71
In the opposite direction, let consumers(p)  C, where p  P, be a set of consumers for
the particular producer p. Using the previously defined notation the set consumers(p) can
be defined for a producer p  P as follows: consumers(p) = {c  C | (requested_site(c) =
site(node(p)))  (stypes(c)  stypes(p) = )}.
pP
consumers(p)  C is a set of all active
consumers, i.e., those that have requested a data stream from some producer.
The result of consumers and producers matching is a list of consumer and producer pairs
where each consumer has exactly one producer assigned. We add the consumer ­ producer
pairs list as a part of the input of this simplified planning problem. The rest of the input is
exactly the same as in case of the MSPP with reflector type media distributors. The output of
this planning problem remains again the same as in the case of the planning problem with
reflector type media distributors.
Using the precomputed sets of consumers for all producers the constraints are defined
as follows:
Stream links constraints
* (e, p)  SL, (e, p) = 1. max_b(p)  cap(e)
Parent network link e of the stream link must have sufficient capacity to transmit the
media stream p.
* i  I, (e, p)  SL. 
((e,p)=1)((i=begin(e))(i=end(e))
max_b(p)  cap(i)
All streams transmitted over a any single network interface must not exceed its capacity.
* (e, p)  SL, (e, p) = 1. node(p) = node(begin(e))  d  D such that node(d) =
node(begin(e))
Each stream link must have producer or media distributor on its beginning node.
* (e, p)  SL, (e, p) = 1. c  consumers(p) such that node(c) = node(end(e)) or
d  D such that node(d) = node(end(e))
Each stream link must have a consumer or media distributor receiving data using the
stream link.
Producer constraints
* p  P. {c  C | c  consumers(p)} > 1 implies (e, p)  SL such that node(p) =
node(begin(e))  node(c) = node(end(e)) and (e, p) = 1
More than one consumer for a particular producer means that there cannot be any direct
stream link between consumers and respective producer as the producer has to send the
media stream through at least one media distributor.
Consumer constraints
* c 
pP
consumers(p) holds
{(e, p)  SL | ((e, p) = 1)  (node(c) = node(end(e)))} = 1
Media stream for each active consumer is received using exactly one stream link.
* c 
pP
consumers(p) holds
{(e, p)  SL | ((e, p) = 1)  (node(c) = node(end(e))))} = 0
72 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
There are no media streams for any of inactive consumers (i.e., those that have not
requested any data from any producer).
* c 
pP
consumers(p). p  P such that (e, p)  SL where (e, p) = 1, node(p) =
node(begin(e))  node(c) = node(end(e)) and p = producer(c).
or
c 
pP
consumers(p). d  D such that (e, p)  SL where (e, p) = 1, node(d) =
node(begin(e))  node(c) = node(end(e))
Each active consumer has to be covered by the requested producer either directly or
through some media distributor.
Data distribution tree constraints
* p  P. {c  C | c  consumers(p)} = 1 implies
{(e, p)  SL | (e, p) = 1}  1, D + 1
There is at least one stream link existing for all producers with only one consumer.
That means data may go either directly, or through some forwarding media distributor
(typically in case that direct sending is not available for one reason or another). Number
of stream links obviously must not exceed number of all the media distributors in the
network plus one.
* p  P. {c  C | c  consumers(p)} > 1 implies
{(e, p)  SL | (e, p) = 1}  consumers(p) + 1, D + consumers(p)
Minimal number of existing stream links is greater or equal to number of consumers
for given producer plus one for multipoint data distribution. Upper bound is a number
of consumers for given producer plus number of all the media distributors.
Media distributor constraints
* d  D, (e, p)  SL such that (e, p) = 1 holds
{p  P | (node(p) = node(begin(e)))  (node(d) = node(end(e)))} = 1
A single media distributor instance can only serve for distribution of data from a single
producer.
* d  D. m distributes data from p implies c  consumers(p) such that node(d) =
node(c)
Media distributor is not scheduled together with another consumer for the same producer
on a single node.
* d  D holds
{(e, p)  SL | ((e, p) = 1)  (node(m) = node(begin(e)))}
 {(e, p)  SL | ((e, p) = 1)  (node(d) = node(end(e)))}
There has to be at least the same number of egress media streams as ingress media
streams for particular media distributor.
Link capacity constraint
* e  E, (e, p)  SL holds 
pP
max_b(p)  (e, p)  cap(e) where (e, p) = {0, 1}
That is bandwidth requirements of all the scheduled stream links (e, p) must not exceed
capacity of the link e the stream links are bound to.
4.6. SIMPLIFYING THE MEDIA STREAMS PLANNING PROBLEM 73
Objectives and Optimization Criteria
Precomputation of the consumer and producer pairs fixes the maximal size of the set of
paths (there can be at most one path for each producer from the consumer ­ producers pairs
planned) for any instance of the simplified media stream planning problem with matching of
consumer and producers. Therefore the cardinality of set of all paths maximization criterion
does not make sense anymore and thus is omitted from this simplified model.
Out of the rest of the optimization criteria stated for the general MSPP we consider only the
Global latency minimization criterion which is formulated identically as for the simplified
media streams planning problem with reflector type media distributors.
4.6.3 Network Links Elimination
Elimination of network links from the MSPP input further reduces the size of the MSPP
state space to a considerable extent. Based on properties of the network links, its associated
lambda links and media applications producing and consuming media streams we can
isolate particular network links which are not usable for transmission of any media stream
before the media stream scheduling. Regarding the MSPP, elimination of a single network
link e  E induces fixing the value of all respective stream links. Formally for all e  E which
are eliminated trivially holds s  S, (e, s) = 0. Similarly, when considering reflector type
media distributors for all e  E which are eliminated holds p  P, (e, p) = 0.
Loopback Links Elimination
We do not consider network links e = (i, i) where i  I (i.e., simple loopback links) to be
generated within the network topology. Such an elimination has some implications regarding
the MSPP. Using this network links elimination prohibits certain media applications to
be planned on a single node. Let us consider an example of just a single node belonging
to a site si  SI with a producer p  P and a consumer c  C. For the consumer c holds
requested_site(c) = si. In such case there is no way how to plan the media stream produced
by the producer p and consumed by the consumer c because the set of network links
E =  and thus there exists no stream link to be planned. Similarly, using this elimination
renders impossible to plan a transmission of a media stream between a producer and media
distributor or media distributor and consumer running on the same node.
Capacity Based Network Links Elimination
Let Q = {min_b(st) | st  ST} and min_stream_bw be the least element of (Q, ). We
eliminate each e  E such that cap(e) < min_stream_bw since such network link is not
usable for transmission of media stream with any stream type.
We can alternatively reformulate the elimination rule for the simplified media streams
planning problem with reflector type media distributors. Let Q = {min_b(p) | p  P} and
min_app_bw be the least element of (Q, ). We eliminate each e  E such that cap(e) <
min_app_bw since such network link is not usable for transmission of any media stream
produced by any media stream producer p  P.
74 CHAPTER 4. MEDIA STREAMS PLANNING PROBLEM
Intra-site Network Links Elimination
Omitting links e  E, where site(node(begin(e))) = site(node(end(e))), from the set of links
can speed up scheduling up to 10 times for many scenarios. On the other hand omitting such
links may also disable useful solution, e.g., those where media distributors are located in the
same site with producers and/or consumers. In case of need, this can be circumvented by
virtually moving media distributors to a separate site.
Links Elimination and Lambda Links
Link e  E can be omitted from planning of stream links (e, s)  SL based on monitoring
of particular links. Link e  E is omitted if it is reported to be down by the monitoring
and there is no l  L such that l  associated_lambdas(e). Based on the monitoring of the
lambda link l we can eliminate e  E such that associated_lambdas(e) =  iff the state of
each l  associated_lambdas(e) is FAILED (i.e., it is not possible to allocate the lambda link
for some reason).
More on Network Links Elimination
Let VP = {v  V} such that c  C where v = node(c) and d  D where v = node(d) be
a set of nodes with no consumer media application or media distributor configured. Since
producer media applications can not consume any media stream, for each (e, s)  SL such
that node(end(e))  VP holds (e, s) = 0. Thus we can omit links e  E where node(end(e)) 
VP from the constraint based planning.
Alternatively, we can formulate a similar rule for nodes with just media stream consumers
configured. Let VC = {v  V} such that p  P where v = node(p) and d  D
where v = node(d) be a set of nodes with no producer media application or media distributor
configured. Since consumer media applications can not produce any media stream, for
each (e, s)  SL such that node(begin(e))  VC holds (e, s) = 0. Thus we can omit links
e  E where node(begin(e))  VC from the constraint based planning.
Both network links elimination rules can be restated for the Reflector type media distributors
model and the model with pre-matched media stream producers and consumers where
the only difference is that we consider stream links (e, p)  E × P instead of (e, s)  E × S
which has no impact on the elimination idea itself.
4.7 Plan Deployment
The result of the MSPP is a mapping of media streams on particular network links which
creates a set of media stream distribution trees for producers p  P covering the consumers
c  C. We call such a mapping the plan. Deployment of the plan involves creating configurations
for all media applications (producers, consumers and media distributors) and
eventually invoking them. For generic media applications it is safe to invoke them only in a
well specified order. The safest way is to invoke all media application consumers prior to all
media application distributors and finally the media application producer along each path
p c. Invocation of media applications in this way ensures that the target media application
is already invoked and ready to receive the media stream, e.g., the distributor is always
ready to receive and distribute a media stream from a producer.
4.7. PLAN DEPLOYMENT 75
Thus two more steps are undertaken in advance of the plan deployment. All nodes
v  V for which (e, s)  SL such that v = begin(e)  n = end(e) are eliminated from the
plan. When working with the simplified model with reflector type media distributors we
are looking for nodes v  V for which (e, p)  SL such that v = begin(e)  n = end(e) to
be eliminated. There is no stream link planned for any application potentially running on
such node and thus it makes no sense to configure/run such applications to send or receive
any data.
Finally, a topological search is used to sort each media streams distribution trees so that
an order of configuring and invoking each media application is given. Such a sorting of
media applications guarantees that invocation of any media stream producer which starts
sending the scheduled media stream also means that respective media stream consumers
are already invoked and well configured at that time and the users can immediately see
the media stream at their sites. To do that we perform a topological sort for each active
media stream producer (i.e., p  P such that exists (e, s)  SL where begin(s) = p) on its
inverted distribution tree. The inverted distribution tree of a media stream producer p  P
is an oriented graph G = (V, EP). V is a set of all nodes and EP is a set of edges such
that e  EP if exists (e, s)  SL such that (e, s) = 1 and (e, s)  p ci for some ci 
{c  C | requested_site(c) = site(node(p))}. To get the desired order of media applications
after the topological sort we reverse the direction of all edges in the set EP.
A nice property of the plan resulting from the proposal of the MSPP as a link-based
model is that we are able to derive the configuration for each media application directly
from the individual elements of the plan (i.e., the stream links such that (e, s) = 1). Recall
that each network link e consists of two network interfaces i = begin(e) and j = end(e)
and these interfaces are configured with their network addresses as we have discussed in
Section 4.1 and Section 3.3.1, respectively. Hence, we can directly obtain the target address
for a producer p = begin(s) or distributor d = begin(s) from the network interface j and
a source address for a distributor d = end(s) or consumer c = end(s) from the network
interface i.
Chapter 5
Evaluation of the CoUniverse
Concepts
In this chapter we aim at evaluation of the previously discussed concepts we have implemented
in the CoUniverse middleware. The evaluation shows the scalability of these concepts
and their viability in terms of seamless orchestrate ad-hoc collaborative environments.
From both points of view we see the following concepts used in the CoUniverse architecture
to have the biggest impact on both measures:
1. usage of the control plane and especially performance of the control plane in terms of
its establishing and ability to transmit control messages between CoUniverse compo-
nents,
2. solving the Media Streams Planning Problem in order to provide self-organization for
orchestrated collaborative environments,
3. using DCN to orchestrate the network infrastructures used by the collaborative envi-
ronments.
In the following we thus provide details on rendering of these three mentioned concepts
in the CoUniverse middleware. We also evaluate the performance of their implementation
with respect to practical use of the CoUniverse middleware for orchestration of ad-hoc collaborative
environments. Note that the implementation of the CoUniverse middleware presented
in this chapter is a proof-of-concept which should show viability of above mentioned
concepts and the qualities and behaviour of CoUniverse under conditions of deployment for
orchestration of real world collaborative environments. As such, the implementation is not
fully optimized, which is fully acceptable for evaluation purposes.
5.1 Control Plane
5.1.1 Implementation Details
Our prototype implementation of the CoUniverse middleware uses the JXTA [132] peer-topeer
(P2P) framework to implement CoUniverse control plane. JXTA provides a generic P2P
76
5.1. CONTROL PLANE 77
framework designed to be used for different applications1. Both Multiverse and collaborative
Universes are implemented as user name and password authenticated private JXTA
peer groups separated from public JXTA P2P network. Note that current implementation of
Multiverse features just Universe registration and static lookup.
We have also experimented with a control plane implementation based on Peer-to-peer
Simplified (P2Ps) framework [136]. As its name suggests, the P2Ps aims at providing a
lightweight peer-to-peer framework hiding the complexity of similar P2P architectures such
as JXTA. P2Ps was directly inspired by the JXTA architecture and its functionality is a subset
of that provided by JXTA in many ways. Both P2Ps and JXTA provide namely peer group
management, service discovery and pipe based communication among the peers. These
functions are basically sufficient to implement the rudimentary functions of the control plane
in the CoUniverse middleware2. On the other hand the P2Ps framework promised a better
performance in comparison to JXTA which was our primary motivation to implement the
control plane using also P2Ps.
5.1.2 Evaluation
To evaluate the performance of the control plane we have observed the ability of CoUniverse
to establish a new fully functional collaborative universe (i.e., a collaborative universe which
is actually able to orchestrate some collaborative environment).
The evaluation was performed using a network consisting of two nodes both running
CoUniverse peers. One of the CoUniverse peers was statically configured to provide the
AGC service (we call this CoUniverse peer simply AGC in the rest of the section to distinguish
between both peers). In such a network the control plane is established once the
CoUniverse peer successfully establishes connection to the AGC.
In order to connect to AGC the CoUniverse peer must connect to given JXTA superpeer,
authenticate into Universe peer group, obtain AGC service advertisement containing
AGC identification within the JXTA network. Eventually the CoUniverse peer sends the
local node configuration to the AGC which processes the node configuration into its view of
the network topology and responds to the CoUniverse peer sending the updated network
topology information.
We observed three different cases where in the first one the Universe Peer was connecting
to AGC running on a local machine, second a Universe Peer was connecting to an AGC
running in a local network and finally we measured a time necessary to connect to AGC
running on a node at Faculty of Informatics, Masaryk University (FI MU) for a Universe
Peer running on a network node at Louisiana State University (LSU). We have measured
the Round Trip Time (RTT) between the nodes in a local network to be minimum = 0.11ms,
maximum = 0.30ms and average = 0.22ms. We have used the commodity Internet to conduct
the experiment between FI MU and the LSU. The RTT between the node in the FI MU
network and the node at LSU was measured to be minimum = 149 ms, maximum = 455ms
and average = 153.97ms.
1For efficiency reasons, JXTA uses hybrid P2P organization instead of pure P2P: there are super-peers in the
network which are holding and maintaining the P2P network for other peers. JXTA utilizes loosely consistent
distributed hash table (DHT) for indexing and lookup the accessible resources in the network.
2We have used the P2Ps to implement only the Collaborative universe as the implementation of P2Ps framework
does not support peer groups and associated security concepts, although these concepts are integral part
of the P2Ps design.
78 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
Under these conditions we have measured time necessary for the Universe Peer to establish
connection to the remote AGC. We have also measured the time necessary for the
Universe peer to receive first response from AGC which illustrates the time needed to pass
a single message between different universe peers. This ability of the control plane to pass
messages between CoUniverse peers then also influences the ability of CoUniverse to react
to any events detected by the monitoring or deploy the plans based on the media stream
planning problem on individual nodes. All measurements were taken 10 times.
The results of these measurements are presented in Table 5.1. Longer connection times
in later two cases were caused by longer time needed to lookup the AGC in the Universe
using the JXTA control plane. All measurements were obtained using version 2.4.1 of JXTA
protocol implementation3.
Table 5.1: JXTA based control plane performance. All times are measured from t0 = 0 ms
being the start of the CoUniverse peer.
local node local net remote net
AGC [ms] AGC [ms] AGC [ms]
establish control plane 22,500100 22,91090 32,13060
connect to AGC 25,400600 26,22090 35,30060
send config to AGC 25,90090 26,29090 35,86060
response from AGC 26,600200 27,100200 38,400100
Results of the P2Ps based control plane evaluation are provided in Table 5.2. The results
show especially a substantial improvement of performance in terms of establishing the control
plane in comparison with the JXTA based implementation. This result can be attributed
to the simplified architecture of the P2Ps framework in comparison to JXTA and basically
confirms the claims on P2Ps performance in [136]. On the other hand, in terms of the times
necessary to pass the node configuration between the CoUniverse peer and the AGC and
to receive the network topology update the JXTA based control plane performed better in
comparable scenarios.
Note that the peer group management in P2Ps relies on native multicast support. We
have previously argued for not using multicast in the design of CoUniverse middleware.
It also showed up that multicast is not available between the nodes at FI MU and LSU.
Therefore the results for the remote net AGC scenario are not provided for the P2Ps based
control plane.
The evaluation of the P2Ps based control plane also revealed an improvement of the
control plane performance when caching of the routing information between the P2Ps peers
was allowed. The difference can be seen between in Table 5.2 between the warm-start and
cold-start columns. The measurements for the warm-start scenario were performed so that
the CoUniverse peer providing the AGC service was running continuously while the other
peer has been restarted. In the cold-start scenario we have started both peers from scratch
for each measurement.
3JXTA version 2.6 which was in its development phase during development of CoUniverse should significantly
improve startup times from seconds to sub-second using multiple techniques like avoidance of repeated
opening and closing of configuration files, indices and caching.
5.1. CONTROL PLANE 79
Table 5.2: P2Ps based control plane performance. All times are measured from t0 = 0 ms
being the start of the CoUniverse peer.
warm-start cold-start
local node local net local node local net
AGC [ms] AGC [ms] AGC [ms] AGC [ms]
establish control plane 41010 1,02020 40010 1,0037
connect to AGC 49020 1,14020 51020 1,25050
send config to AGC 56030 1,23030 61030 1,24060
response from AGC 1,500100 2,700100 2,52060 3,200100
Contrary to the P2Ps framework performance claims in comparison to JXTA we have observed
that JXTA based control plane actually performs better in terms of passing messages
between CoUniverse peers as can be seen in Tables 5.3 and 5.4. These measurements depict
the average times needed for a CoUniverse peer to send the node configuration to AGC and
immediately receive the updated network topology back from AGC4.
Table 5.3: JXTA message passing performance.
local node local net remote net
AGC [ms] AGC [ms] AGC [ms]
700200 800200 2,530100
Table 5.4: P2Ps message passing performance.
warm-start cold-start
local node local net local node local net
AGC [ms] AGC [ms] AGC [ms] AGC [ms]
1,000100 1,50090 1,90070 1,96080
5.1.3 Conclusions
The results of the control plane evaluation show the limitations of the control plane in terms
or establishing of the collaborative environment using the CoUniverse middleware. Ability
of CoUniverse to establish the orchestrated collaborative environment is directly influenced
by its ability to establish the control plane between the CoUniverse peers. The presented
results are generally acceptable, as the phase of establishing of the collaborative environment
does not imply any interactions between the users of the collaborative environment.
4The presented measurements actually correspond to Round Trip Time between the CoUniverse peers using
JXTA or P2Ps messages.
80 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
The results of the control plane performance in terms of message passing between the
CoUniverse peers also provide some hints on CoUniverse behavior in terms of resiliency. Let
us suppose that an event concerning some network link is being detected by the monitoring
on some CoUniverse peer. The CoUniverse peer then notifies AGC. If the event was detected
on some network link actually used for media streams distribution in the collaborative universe,
then it is necessary to perform new planning of the media streams transmissions using
the actual state of the network topology (we provide details on this process in Section 5.2).
AGC then sends messages back to CoUniverse peers involved in deployment of the plan.
From the control plane point of view this scenario is virtually the same as when CoUniverse
peer sends the node configuration to AGC and receives back the updated network topology
information. The ability of both JXTA and P2Ps control planes to pass messages between
the CoUniverse peers and the AGC in these scenarios is summarized in Tables 5.3 and 5.4,
respectively.
The performance of the control plane in terms of passing messages between CoUniverse
peers together with the performance of the media streams planning as presented in Section
5.2.3 then present the performance of the CoUniverse middleware in terms of resiliency
provided for the orchestrated collaborative environments. The results presented in both sections
imply that the CoUniverse middleware is able to recover the orchestrated collaborative
environment from some failure in times in order of seconds for moderate sized environments.
In general these results however show, that the control plane has to be based on
a P2P substrate featuring substantially lower message passing times than those presented
above in order to provide resiliency for interactive collaborative environments.
5.2 Media Streams Planning Problem Solver
In Chapter 4 we have provided a simple algebraic description of the media streams planning
problem which we have formulated in order to solve the automated orchestration of
component based collaborative environments. The orchestration of the components is based
upon solving the simplified media streams planning problem with precomputed matching
of consumers and producers (simplified MSPP) as we have described in Section 4.6.2. In the
following sections we describe transformation of the simplified MSPP into a Constraint Satisfaction
Problem (CSP) [35] and provide an evaluation of its solver we have implemented
as a part of the CoUniverse middleware.
5.2.1 Simplified MSPP as a Constraint Satisfaction Problem
Definitions
The notation used to formulate the CSP is basically consistent with the definitions we have
provided in Section 4.15. In contrast with the previous chapter we use a notation app 
v meaning that media application (producer, consumer or media distributor) app  P 
C  D is configured and eventually invoked on a node v  V. In the previous chapter we
have used less formal but more intuitive notation node(app) = v. For the definition of the
5Note again, that for the purposes of formulating the CSP we understand the set of all network links E to
contain only those network links which were qualified as active based on the monitoring. Refer to Sections 3.4.2
and 3.6 for more details.
5.2. MEDIA STREAMS PLANNING PROBLEM SOLVER 81
CSP we formulate the output of consumers and producers matching precomputation (see
Section 4.6.2 for reference) as follows:
Each media stream is produced by one producer producer(s)  P and the following must
hold:
s1, s2  S : producer(s1) = producer(s2) ,
sS
producer(s) = P ,
s  S : producer(s) = 1.
For each stream s produced by a producer producer(s) we can find a set of its consumers
denoted as consumers(s)  C as we have described earlier. It must hold that:
s1, s2  S : consumers(s1)  consumers(s2) =  ,
sS
consumers(s) = C ,
s  S : consumers(s)  1.
To specify the MSPP as a CSP we introduce a boolean domain variable sl(e, s) for each
stream link as defined in Chapter 4. The semantics of the sl(e, s) values is analogical with
the values we attributed to the streams links:
sl(e, s) =
1 if e is used to transmit s
0 otherwise
Constraints
Individual constraints formulated for the CSP basically follow the description of the simplified
MSPP we have provided earlier. Therefore we provide only short descriptions of the
meaning of individual constraints and let the reader to refer to the discussion of the MSPP
in Section 4.6.2 of Chapter 4.
* Capacity constraints
Capacity of each interface i must be sufficient to transmit the media streams over respective
links.
i  I : 
sS

e  E :
((i = beginI(e))  (i = endI(e)))
sl(e, s)  max_b(s)  cap(i) (5.1)
Capacity of each link e must be sufficient to transmit all media streams bound to the
link e.
e  E : 
sS
sl(e, s)  max_b(s)  cap(e) (5.2)
Each link e of a stream link sl(e, s) must have sufficient capacity to transmit the stream
s. This constraint is actually redundant.
s  S e  E (max_b(s) > cap(e)) : sl(e, s) = 0 (5.3)
82 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
* Stream links constraints
The following two equations (5.4) and (5.5) take care of the links ending at each node.
All these links must satisfy constraints given by existence of a consumer (or possibly
of a distributor) at the end of each link
Each consumer c receives just a single stream s using one link e.
c  C s  S (c  consumers(s)) : 
(eE)(cend(e))
sl(e, s) = 1 (5.4)
If there is neither a consumer for the stream s nor a distributor at the node v, then any
of the links e such that v = end(e) is not used to transmit the stream s.
s  S e  E (( c  C ((c  end(e))  (c  consumers(s))))
( d  D (d  end(e)))) : sl(e, s) = 0
(5.5)
The following two equations (5.6) and (5.7) take care of the links beginning at each
node. All these links must satisfy constraints given by existence of a producer (or
possibly of a distributor) at the beginning of each link.
Producer p sends the stream s using just a single link e.
p  P s  S (p = producer(s)) : 
(eE)(pbegin(e))
sl(e, s) = 1 (5.6)
If there is neither the producer for the stream s nor a distributor at the node v, then any
of the links e such that v = begin(e) is not used to transmit the stream s.
s  S e  E (( p  P ((p  begin(e))  (p = producer(s))))
( d  D (d  begin(e)))) : sl(e, s) = 0
(5.7)
* Media distributor constraints
Let us first introduce an additional notation to simplify the definitions of media distributor
constraints. indeg(v, s) called indegree of the node v wrt. the stream s corresponds
to (eE)(v=end(e)) sl(e, s). Symmetrically outdeg(v, s) called outdegree of the node v wrt.
the stream s corresponds to (eE)(v=begin(e)) sl(e, s).
Each distributor d can be used for distribution of at most one media stream produced
by one producer only, i.e., the distributor receives just a single stream over one link at
most.
d  D v  V (d  v) : 
sS
indeg(v, s)  1 (5.8)
Corresponding to Eqn. (5.8), there are two types of distributors with respect to the
stream s. Distributor d running at a node v and transmitting the stream s has indeg(v, s) =
1 and it is called an active distributor of the stream s. Distributor d not transmitting it has
indeg(v, s) = 0 and it is called a non-active distributor of the stream s.
5.2. MEDIA STREAMS PLANNING PROBLEM SOLVER 83
Each distributor is capable of distribution of the received media stream into several
links (and it cannot distribute any other incoming streams).
s  S d  D v  V (d  v) :
if indeg(v, s) = 0 then outdeg(v, s) = 0
if indeg(v, s) = 1 then outdeg(v, s)  1
s  S d  D v  V (d  v) : if outdeg(v, s) = 0 then indeg(v, s) = 0
The first equation for indeg(v, s) is implemented as
s  S d  D v  V (d  v) : indeg(v, s) × outdeg(v, s) = outdeg(v, s) (5.9)
while the second equation for outdeg(v, s) is implemented using the following con-
straint
s  S d  D v  V (d  v) : indeg(v, s) + outdeg(v, s) = 1 (5.10)
Considering the Eqn. (5.8) when outdeg(v, s) = 0 also indeg(v, s) = 0 must hold.
* Cycle elimination
In Chapter 4 we have claimed the solution of the MSPP to be a set of distribution trees.
To avoid existence of cycles among the nodes with distributors, the cycle elimination
among nodes with distributors must be applied for each stream6.
Let us denote n = D and expect a fixed ordering between distributors d1, . . . dn. Also
we denote vj  V the node with dj  vj. For each stream s and for each k smaller or
equal than the total number of distributors, the following constraint ensures that cycles
among k nodes each running a distributor are prohibited.
s  S k (2  k  n) i (1  i  (n
k)) : 
j1, j2  C(n,k)(i) :
(vj1 = begin(e))  (vj2 = end(e))
(sl(e, s) = 1)
sl(e, s) < (k - 1) (5.11)
This constraint is posted after processing of all other constraints to achieve the smallest
number of domain variables in such constraints (edges corresponding to domain
variables sl(e, s) equal to 0 are not included). As can be seen from Table 5.5 the number
of constraints (5.11) posted to eliminate cycles in the media stream distribution trees
is reasonable for our problem instances.
* Producer and consumer constraints
The stream between a producer and its consumer can not be sent directly over one link
if there is more than one consumer for this producer.
p  P c  consumers(P)
(( consumers(p) > 1)  (p  begin(e))  (c  end(e))) : sl(e, s) = 0
(5.12)
6Note that such a constraint need not to be considered at all for the classical path placement problems.
84 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
Each producer p with only one consumer c must send data through one link at least
and there are D links between them at most (each such stream is produced by a
producer p, distributed by several distributors and consumed by the consumer c).
p  P s  S ((p = producer(s))  ( consumers(p) = 1)) :
1  
eE
sl(e, s)  ( D + 1) (5.13)
At least one multi-point data distribution is necessary for a producer p with more than
one consumers. In such case the number of planned stream links used for the media
stream distribution is at least consumers(p) + 1 and consumers(p) + D at most.
p  P s  S ((p = producer(s))  ( consumers(p) > 1)) :
( consumers(p) + 1)  
eE
sl(e, s)  ( consumers(p) + D ) (5.14)
* Objectives and optimization criteria
We have considered just the Global latency minimization for the simplified MSPP with
matching of consumers and producers as we have stated in Section 4.6.2.
minimize 
sS

eE
sl(e, s) × lat(e) (5.15)
* Links elimination
The following summarizes the idea of the network links elimination as we have described
in the Section 4.6.3. We denote the set of links which cannot be used for planning
of any media stream transmissions Eelim. These links are eliminated from the network
to obtain a CSP a smaller number of sl(e, s) boolean variables (sl(e, s) variables
are not created for eliminated links e). We define the set Eelim as:
Eelim = E\{Ecap  Ec  Ep  Esite}
Capacity based network links elimination.
Ecap = {e  E | cap(e) < min
sS
(max_b(s))} (5.16)
Elimination of links which begins at nodes where is neither producer nor distributor
(consumers cannot send any stream out of the node).
Ec = {e  E | (p  begin(e))  (d  begin(e))} (5.17)
Elimination of links which ends at nodes where is neither consumer nor distributor
(producers cannot receive any streams).
Ep = {e  E | (c  end(e))  (d  end(e))} (5.18)
Elimination of intra-site network links.
Esite = {e  E | site(begin(e)) = site(end(e))} (5.19)
5.2. MEDIA STREAMS PLANNING PROBLEM SOLVER 85
Constraint Satisfaction Problem
Let us consider the network representation N = (V, E), applications P  C  D and streams
S. The base constraint satisfaction problem (CSP) [35] P = (X , D, C) we work with has the
domain variables X = {sl(s, l) | s  S, l  E}, with domain of variables D = {0, 1} and
constraints C which consist of Equations (5.1), (5.2), (5.4)­(5.11). A solution of P = (X , D, C)
denoted by  is a complete assignment of all sl(s, l) variables satisfying all constraints in C.
Set of all solutions of P is denoted .
To allow for more efficient solving of the MSPP we consider an extended CSP P+ =
(X , D, C+) with additional constraints (5.3) and (5.12)­(5.14). The optimal solution and the
set of all its solutions of the P+ = (X , D, C+) are denoted by + and +, respectively.
We consider the network links elimination to further simplify the MSPP. A CSP taking the
network links elimination is denoted P+
elim = (Xelim, D, C+). P+
elim takes variables Xelim =
{sl(s, l) | s  S, l  Eelim} of the same domain D = {0, 1} and all constraints C+ defined
by Eqn. (5.1)­(5.14) which are applied on the reduced set of variables Xelim. We denote the
optimal solution of P+
elim as +
elim while all solutions of P+
elim as +
elim. The P+
elim problem is the
one we actually solve in the context media streams planning in the CoUniverse middleware.
Finally, we are looking for solutions of each such problem where the overall latency is
minimized using Eqn. (5.15).
5.2.2 Search Heuristics
To improve the efficiency of the CSP solutions search we have implemented custom variable
and value ordering heuristics [35,115]. As the CSP works with boolean domain variables the
value ordering includes choice between increasing (solver default) and decreasing order.
We have implemented both static and dynamic variable ordering heuristics. Static variable
ordering involves sorting of variables according to rules we describe below prior to
the search for the CSP solution while the dynamic ordering computes the variables to be assigned
during the CSP solution search process. We have implemented the following variable
ordering heuristics:
* leftmost: static ordering with simple linearization of sl(e, s) array over link e (outer
loop) and stream s (inner loop). (solver default)
* stream: static ordering with simple linearization of sl(e, s) array over stream s (outer
loop) and link e (inner loop).
* dfs: static ordering with DFS node traversal consecutive from each producer. The DFS
traverses nodes from each producer, adding all the outgoing edges from current node.
After all the nodes reachable from one node running a producer are traversed, new
DFS traversal is started from another node running a different producer until all the
producers are exhausted.
* bfs: static ordering according to BFS traversal of the nodes beginning from each node
running a producer. Otherwise is the bfs heuristic the same as in the dfs case.
* degree: classical dynamic variable ordering with variable selection based on the maximum
number of constraints related with each variable.
86 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
According to the evaluation of these variable and value ordering heuristics the best performance
is provided by the degree ordering as demonstrated in Table 5.6 and discussed in
the next section.
5.2.3 Evaluation
We have implemented a solver for the P+
elim problem as the MatchMaker module of the
CoUniverse middleware. The implementation is based on Java constraint solver Choco
1.2.057. To evaluate our prototype implementation we have implemented parameterized
version of the MatchMaker module which allows to study its features with respect to various
aspects of the media streams planning problem and different network topologies.
We have evaluated the MatchMaker module properties using three basic network topologies
(one of those in two variants) which correspond to the most usual ways of media
streams distribution in collaborative environments:
1. 1:n topology with a single distributor having sufficient capacity, further denoted as 1:ns.
This scenario is somewhat artificial especially when considering distribution of highbandwidth
media streams (see below) between the components of the collaborative
environment. However, it serves us well as a comparison to topologies featuring more
realistic media streams distribution schemes.
2. 1:n topology with several distributors creating a distribution network, further denoted
as 1:n-r. The 1:n topology was generated so that so called master site comprised an UltraGrid
producer node and UltraGrid consumers node for all other remote sites in the
topology, every other site comprised one UltraGrid producer node and one UltraGrid
consumer node. In this scenario we have generated a number of distributors equal to
the number of remote sites. This scenario is realistic, e.g., for multi-party distant learning
environment, where the lecturer gives his talk to multiple remote sites. We also
consider a variant of the 1:n-r topology where the number of distributors is minimized
with respect to the number of remote sites and the fact that one media on a node with
10 Gbps network interface available can replicate 1.5 Gbps media stream (see below)
from a single UltraGrid producer to at most 6 UltraGrid consumers. We further denote
this variant as 1:n-rm. To avoid intra-site links elimination each node with distributors
belonged to its own virtual network site in both variants of the 1:n topology.
3. m:n-r full-mesh topology with a number of distributors further denoted as m:n-r. The
m:n-r topology was generated so that each site had one node with an UltraGrid producer
and a node with UltraGrid consumer for each other site. The number of distributors
was generated to cover a full-mesh collaboration of users in the individual
sites taking into the account the same properties of the media streams and network infrastructure
as in the 1:n-rm case. To avoid intra-site links elimination each node with
media distributors again belonged to its own virtual network site.
Each node in all considered topologies was generated having a 1 Gbps and 10 Gbps network
interfaces, each interfacing with a distinct network. The topologies thus comprised
2(n2 - n) links where n is a number of nodes generated in the topologies. To describe the
7http://choco.emn.fr/
5.2. MEDIA STREAMS PLANNING PROBLEM SOLVER 87
...
...
(a) (b)
(c) (d)
Figure 5.1: Topologies used for experimental evaluation: (a) 1:n-s, (b) 1:n-r, (c) 1:n-rm, (d)
m:n-r. Black represent are producers, white nodes represent consumers and grey nodes represent
distributors. The clouds depict network sites. Arrows model example media stream
transmissions resulting from the P+
elim solutions.
size of the topology we introduce its parameter SID = SI - D which is defined as a
number of sites of the topology excluding the virtual sites of nodes with distributors. Media
applications deployed in these topologies imitated distribution of uncompressed 10 b 4:2:2
high-definition 1920×1080 video with 1.5 Gbps per stream se have been using for many applications
sucha as those in [69] or [73].
We have evaluated the MatchMaker module based on times necessary for finding the
first feasible solution for the media streams distribution within selected topologies and the
optimal solution for such media streams distribution (i.e., media streams distribution featuring
the lowest overall latency). We have also evaluated the efficiency of the media streams
planning problem simplifications. To do so we have evaluated the MatchMaker module removing
each redundant constraint (especially those posed by network links elimination) at
a time.
88 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
The evaluation was performed using the quark cluster of MetaCentrum8. The cluster
comprises of nodes with Intel Xeon 5160 @ 3.00 GHz CPUs and 10 GB RAM, running Linux
2.6.22.17 x86_64 and Java SDK 1.6.0.
The measured results of MatchMaker module evaluation may be influenced by dynamic
behavior of the Java Virtual Machine (JVM) (e.g., HotSpot Just In Time compilation) [54] and
garbage collection [17]. In order to minimize effects of such behavior onto the evaluation
results, we have made the following arrangements:
1. the evaluation of the MatchMaker module was run with -server option, which maximizes
the amount of compilation prior to run-time,
2. at most two instances of the MatchMaker were running on a single node at a time,
3. each measurement was preceded by a warm-up phase (i.e., for 7 sample measurements,
20 consecutive runs were performed and only the last 7 time measurements
were taken into the account),
4. to eliminate the negative effects of garbage collection caused by a number of consecutive
runs of the evaluation [54] on its performance we have further omitted the smallest
and largest time measurements out of the last 7 runs (i.e., leaving 5 time measurements
for further analysis),
5. the MatchMaker module features rich logging capabilities which may on the other
hand influence its performance, thus we have disabled the logging.
Results and Discussion
Properties of the 1:n-s, 1:n-r, and m:n-r topologies used to evaluate the MatchMaker module
with respect to the solution of the CSP P+
elim are illustrated in Table 5.5. Note that the
maximum number of sites evaluated for each topology was limited by the practical limit
of approximately less than 10 s that is acceptable from the perspective of planning media
streams transmissions for an ad-hoc environment. The properties of selected topologies also
approximately corresponds to the size and complexity of real-world ad-hoc collaborative
environments we have been building and deploying (see Chapter 6 for reference). Also note
the dramatically rising number of solutions for more complex 1:n-r topologies which may
seem erroneous in comparison to the number of solutions of other considered topologies.
This is due to the fact that in these topologies up to SID = 7 just one distributor is actually
necessary for the optimal solution. Including the remaining distributors in the media
streams distribution trees between producers and consumers can build large numbers of
different valid but suboptimal solutions.
As the efficiency of the solution search is influenced by the variable and value ordering
heuristics, we have evaluated these heuristics using selected instances of all generated
topologies. Results of this evaluation are summarized in Table 5.6 and further discussed below.
Based on these results (and according to our expectations) we have selected the degree
variable ordering with increasing value ordering to be used for all other evaluations of the
MatchMaker module.
8http://meta.cesnet.cz/
5.2. MEDIA STREAMS PLANNING PROBLEM SOLVER 89
Table 5.5: Properties of evaluated topologies.
Configuration parameter SID gives the number of sites with virtual distributor sites
excluded. unass(Xelim) denotes the number of unassigned domain variables prior to search.
(5.11) is the number of constraints posted to eliminate the cycles among the distributors.
Fo is the value of the objective function for the optimal solution of P+
elim.
topology- SID V D E Eelim Xelim unass(Xelim) (5.11) +
elim Fo
1:n-s-2 5 1 40 10 20 6 0 3 22
1:n-s-4 11 1 220 44 176 13 0 1 77
1:n-s-8 23 1 1,012 184 1,472 29 0 1 165
1:n-s-16 47 1 4,324 752 12,032 61 0 1 341
1:n-s-32 95 1 17,860 3,040 97,280 125 0 1 693
1:n-rm-2 5 1 40 10 20 6 0 3 22
1:n-rm-4 11 1 220 44 176 13 0 1 77
1:n-rm-6 17 1 544 102 612 21 0 1 121
1:n-rm-8 24 2 1,104 216 1,728 67 8 238 176
1:n-rm-10 30 2 1,740 330 3,300 85 10 672 220
1:n-rm-12 36 2 2,520 468 5,616 103 12 924 264
1:n-r-2 5 1 40 10 20 6 0 3 22
1:n-r-3 9 2 144 36 108 22 3 12 55
1:n-r-4 13 3 312 78 312 57 16 375 77
1:n-r-5 17 4 544 136 680 116 55 25,192 99
1:n-r-6 21 5 840 210 1,260 205 156 3,008,925 121
m:n-r-2 6 2 60 18 36 14 2 11 22
m:n-r-3 12 3 264 60 180 45 12 6 99
m:n-r-4 20 4 760 140 560 112 44 24 176
m:n-r-5 30 5 1,740 270 1,350 225 130 120 275
m:n-r-6 42 6 3,444 462 2,772 396 342 720 396
Table 5.6: Evaluation of different variable and value ordering heuristics.
Computational results for different variable and value ordering heuristics for selected
topologies. leftmost­degree denote variable ordering heuristics as described in Section 5.2.2.
dec and inc mean decreasing and increasing value ordering. Note, that the topologies were
selected with respect to the unacceptably long times needed to find respective solutions
using the worst variable and value ordering heuristic (i.e., the leftmost one).
1:n-s-32 1:n-r-5 m:n-r-4
dec [ms] inc [ms] dec [ms] inc [ms] dec [ms] inc [ms]
leftmost 15,600200 15,200200 103,900200 95,400100 261,200600 232,200300
stream 15,300300 14,600200 1,72020 1,70010 2802 2722
dfs 16,700200 16,300200 1,6322 1,59020 161.20.8 153.80.4
bfs 17,100300 16,500200 1,66020 1,59020 164.20.4 1551
degree 15,10020 15,100300 1,37010 1,3753 58.60.5 56.00.4
90 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
Table 5.7: Evaluation for 1:n-s topologies with runtime in milliseconds.
SID 2 4 8 16 32
first 1.60.5 6.20.4 421 67010 15,500200
min 2.00.4 6.00.4 41.60.5 6606 15,500100
(5.12) 2.00.4 6.20.4 41.60.8 68020 15,400200
(5.3,5.13,5.14) 2.20.4 5.20.4 43.00.6 67020 15,500200
(5.16) 2.20.4 9.60.5 784 1,35030 31,400300
(5.17) 2.20.4 10.00.6 1111 2,22090 53,3001,100
(5.18) 2.20.4 10.40.5 1061 2,26050 54,800300
(5.19) 2.00.4 6.00.4 44.60.5 71010 16,000200
(5.16­5.19) 3.00.4 18.00.4 2525 5,200200 136,800900
Table 5.8: Evaluation for 1:n-rm topologies with runtime in milliseconds.
SID 2 4 6 8 10 12
first 1.60.5 6.00.4 15.20.4 51.80.4 1141 2222
min 2.00.4 5.00.4 16.40.5 741 2243 76516
(5.12) 2.00.4 5.40.5 16.60.5 805 2353 7138
(5.3,5.13,5.14) 2.40.5 5.40.5 14.80.4 91.40.5 2316 7636
(5.16) 2.00.4 8.00.4 26.60.5 1435 79020 2,76020
(5.17) 2.60.5 9.00.4 35.00.6 1906 1,17060 3,89020
(5.18) 2.00.4 9.00.4 34.20.4 19010 1,25020 4,90050
(5.19) 2.40.5 7.00.6 17.40.5 866 2516 86020
(5.16­5.19) 3.40.5 19.40.5 802 83010 4,800300 10,26020
Results of MatchMaker module runtime measurements while evaluating its different features
using the above described topologies are given in Tables 5.7, 5.8, 5.9 and 5.10. For the
evaluation of the MatchMaker module we have measured the times needed for the solver to
find the first solution (presented in the "first" row of the tables) and optimal solution (the
"min" row of the tables) of the P+
elim problem.
We have performed the measurements for all topologies, taking in mind the fact that the
search for either the first or the optimal solution of the CSP should not exceed times in order
of seconds as we discuss below. The measurements for the 1:n-s topology are provided up
to SD = 32 where the solver still yields a good performance. However, the 1:n-s topology
assumes existence of an artificial distributor with virtually unlimited capacity and thus it is
used just for a comparison.
The performance of the search for the 1:n-rm topology is important as this media distribution
scenario is used for example in the Multi-party Distant Learning application we
describe in Section 6.1.2. We have been able to perform the experiments for 1:n-rm topology
up to SD = 12 in still reasonable times as can be seen from the results. However, we have
minimized the number of involved distributors in the 1:n-rm topologies in order to simplify
the CSP. The consequence of this simplification is the fact that the 1:n-rm topologies do not
5.2. MEDIA STREAMS PLANNING PROBLEM SOLVER 91
Table 5.9: Evaluation for 1:n-r topologies with runtime in milliseconds.
SID 2 3 4 5 6
first 2.00.4 4.00.6 9.20.4 254 412
min 2.00.4 5.60.5 28.60.5 1,36010 211,5001,200
(5.12) 1.80.4 5.60.5 30.00.6 1,35020 209,500400
(5.3,5.13,5.14) 1.80.4 6.60.5 27.80.4 1,3039 207,700400
(5.16) 2.20.4 7.60.5 39.20.4 2,02010 383,100800
(5.17) 2.00.4 7.20.4 381 1,9049 330,0002,000
(5.18) 2.00.4 7.60.5 39.80.4 1,99020 338,7008,700
(5.19) 2.00.4 5.80.4 30.00.4 1,3983 217,000700
(5.16­5.19) 2.60.5 11.00.4 59.60.8 3,38050 1,291,0001,900
Table 5.10: Evaluation for m:n-r topologies with runtime in milliseconds.
SID 2 3 4 5 6
first 2.00.4 5.60.5 17.40.5 43.40.8 1073
min 2.60.5 7.80.4 55.60.5 9595 29,28090
(5.12) 2.00.4 9.80.4 93.20.4 1,92020 59,600100
(5.3,5.13,5.14) 2.40.5 7.40.5 51.80.4 8856 27,63070
(5.16) 3.00.4 11.40.5 73.60.5 1,2622 63,0001,000
(5.17) 2.80.4 11.00.4 82.80.8 1,67020 142,200700
(5.18) 3.00.4 11.60.5 82.60.5 1,70020 159,900900
(5.19) 2.60.8 8.00.4 57.00.6 9644 30,000100
(5.16­5.19) 3.60.5 19.00.4 132.60.5 6,10090 430,200200
provide virtually any redundancy and if for example some network link beginning or ending
in the network interface on a node running a distributor fails then it would be hard to find
any other valid solution for the media streams distribution with the same parameters (i.e.,
with the same quality and demanding the same bandwidth). Therefore we have performed
the same evaluation for the 1:n-r topologies where redundant nodes running distributors
are available. In comparison to the 1:n-rm topologies the 1:n-r topologies are more complex
and the number of possible solutions skyrockets with increasing number of involved distributors.
The price for the added redundancy is thus the fact that we have been able to
find solutions for the associated CSPs in reasonable times only up to SD = 6 for the 1:n-r
topologies. To illustrate the significance of the provided results it should be noted that the
environment described in Section 6.1.2 featured the 1:n-r topology used for media streams
distribution with D = 5 and three nodes running distributors.
The m:n-r topology is used, e.g., for generic Advanced Multi-party Videoconferencing environments
we describe in Section 6.1.1. The results show that with the proof of concept implementation
of the CoUniverse middleware we are able to orchestrate such environments
up to 6 sites. Adding 7th site to the m:n-r topology requires creation of two distributors for
92 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
each site, which doubles the size of D and the complexity of the problem. In such case the
search especially for the optimal solution of the CSP exceeds any reasonable time.
We have analysed the efficiency of the redundant constraints defined for the extended
CSP P+ by disabling the (5.3) and (5.12)­(5.14) constraints. As disabling of individual constraints
(5.3), (5.13) and (5.14) did not yield any measurable improvement of the search times
we have measured the aggregated impact of all three constraints. The results show that the
impact of these redundant constraints on the search times is only marginal. On the other
hand the redundant constraint (5.12) yields quite significant positive impact on the measurement
results.
We have also analysed the significance of the network links elimination defined by constraints
(5.16)­(5.19). According to our expectations these additional constraints should have
a very significant impact on the times needed to find the optimal solution of the P+
elim problem.
Our experiments confirmed this expectation as can be seen from the presented results.
The results also show that these additional constraints yield increasing impact on the times
needed to find the optimal solution of the P+
elim problem with more complicated topologies.
The somewhat artificial intra-site link elimination (5.19) has marginal impact on the results
for the evaluated topologies. However, it has good reason in more elaborate topologies
where it allows users to avoid some solutions (e.g., by putting all distributors into single site
where those distributors may not form a distribution tree among themselves, which simplifies
solution in small m:n-r topologies).
5.2.4 Conclusions
The results presented in this section show that the performance of the MatchMaker module
is directly influenced by the size and complexity of the topologies for which we seek
the solution of media streams distribution. This observation is not surprising with respect
to the character of the media streams planning problem and the constraint programming
method used to solve it. The results may indicate a limited performance and scalability of
the MatchMaker module. However, it is necessary to note that in terms of the collaborative
environments and applications discussed in Chapter 6, scenarios and topologies used for the
MatchMaker module evaluation present small to medium sized environments.
The evaluation of the MatchMaker module might also substantially differ in case that we
solve the MSPP in order to establish a new ad-hoc collaborative environment or the MSPP is
being solved to recover the environment after some network infrastructure of environment
component failure. In the first case are the times necessary to find both first and optimal
solution of the MSPP generally acceptable for all observed topologies. In other words, establishing
of the collaborative environment may be delayed when searching for an optimal
media streams distribution in case of more complex topologies and the user experience with
the collaborative environment should not be harmed. On the other hand if the MSPP is being
solved in order to find a new media streams distribution after failure of some network or
environment component the users may find hard to accept delays in order of seconds caused
by searching for an optimal solutions for complex topologies. If we accept the first solution
of the MSPP as a basis for the automated orchestration of collaborative environments, then
the performance of the MatchMaker module for the observed topologies9 becomes acceptable
in both discussed cases.
9This includes the 1:n-rm, 1:n-r and m:n-r topologies.
5.3. NETWORK ORCHESTRATION 93
5.3 Network Orchestration
In order to address the problem of automated user-empowered control of dynamic network
infrastructures we have integrated orchestration of lambda links based network infrastructures
into the CoUniverse architecture. Automated orchestration of individual lambda links
is based on network links which are planned to be used for transmission of some media
streams between the components of orchestrated collaborative environments.
To implement the orchestration of lambda links based network infrastructure, we have
taken advantage of the advanced features of Internet2 Dynamic Circuit Networks (DCN).
Our choice of the Internet2 DCN was fostered primarily by the readily available Inter-domain
Controller Protocol (IDCP) implementation which allows to automatically provision lambda
links in an ad-hoc manner. Also Internet2 provides an API which allows for third parties
to easily integrate their applications (e.g., the CoUniverse middleware) with IDCP enabled
network infrastructures. The choice of Inernet2 DCN has been further supported by the universities
and institutions we have been working with on building of various collaborative
environments and applications and the fact that their networks interface with the Internet2
DCN infrastructure.
As we have mentioned earlier the term dynamic circuit network does not imply a particular
network technology type or mechanism for controlling a network. Projects to control
dynamic circuit networks other than Internet2 DCN (through the IDCP protocol) have also
been implemented. Efforts to standardize dynamic circuit network protocols are underway
at Open Grid Forum (OGF)10 and at work to create interoperability between existing implementations
is taking place at Global Lambda Integrated Facility (GLIF)11. Both these are
developing capabilities similar to those of the IDCP protocol, so the work we have done integrating
CoUniverse with Internet2 DCN should be easily transferable to future standard
interfaces. CoUniverse has also taken its experience with Internet2 DCN to the standards
groups to help shape them to the needs of the sorts of applications we further discuss in
Chapter 6.
5.3.1 Implementation details
To incorporate the Internet2 DCN infrastructure into our networking model, we made the
following assumption. If any of the network interfaces configured on the nodes interfaces
with the DCN infrastructure (i.e., interfaces with associated DCN endpoint), the connection
between such network interface and the DCN endpoint is transparent. Thus we consider the
DCN endpoint being a property of the network interface. In our extended network model
it is possible to allocate a circuit between any two DCN endpoints associated with network
interfaces. We furthermore associate the network link between two network interfaces connected
to DCN endpoints with the respective circuit and vice versa. A difference between a
network link with an associated circuit and a plain network link is that we suppose the network
link with an associated but unallocated circuit to be inherently down while the plain
links on top of statically configured networking infrastructure are assumed to be in an up
state.
Introduction of DCN into CoUniverse involved several steps and modifications of the
original planning model and methods for controlling of network links. The basic premise
10http://www.gridforum.org/
11http://www.glif.is/
94 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
however was to use the original media streams planning model and allow only such modifications
that would not introduce any additional constraints and make the media stream
planning problem more complex. The original media streams planning problem in CoUniverse
is formulated so that we are looking for a mapping of media streams to be transmitted
over a set of network links with given properties (also called match making). Should any
media stream be transmitted over any network link, it means that the network link in question
must be up. That means the link is working and actually able to transmit some data at
the time of the planning. The ability of a link to transmit some data is reported by periodic
monitoring of the link in question. A network link with associated but not allocated DCN
circuit is however reported to be down by the monitoring.
CoUniverse architecture offers two openings for the circuits allocation: the first one being
before the match making process while the other one right after the match making process
finished. The advantage of the first approach is that all network links (even those with associated
circuits) are potentially up at the time of match making at the cost of asking for
allocation of many circuits out of which some need not to be used for any media streams
transmission. The number of circuits to allocate can be in order of n2 where n is the number
of nodes in the orchestrated collaborative environment. That is why we tend to stick with
the second approach where we allocate just those circuits associated with network links determined
by the match making process to be used for actual media streams transmissions.
Using the second approach to DCN circuits allocation also means that we had to create an
exception stating that a network link which is down but backed by an unallocated DCN circuit
may still be used for media streams transmission. Otherwise the original media streams
planning algorithm is left untouched. Thus the complexity of the media streams planning
over DCN based infrastructure is increased by at most O(n) where n is a number of all network
links between the nodes of the environment in case that all these network links are
associated with some DCN circuit. Note, that the this complexity increase is considered only
in terms of complexity of the media streams planning problem in CoUniverse12 . As we have
previously shown, the media streams planning problem in CoUniverse belongs to the class
of NP-hard problems (see Chapter 4 for reference). Therefore additional processing of the
list of network links introduces only marginal complexity increase in comparison with the
complexity of solving the media streams planning problem.
5.3.2 Evaluation
We have evaluated the ability of the CoUniverse middleware to orchestrate different collaborative
environments built on top of Internet2 DCN enabled network infrastructure during
ESCC/Internet2 Joint Techs Workshop and another two occasions at Spring 2009 Internet2
Member Meeting (see Section 6.2 for details on the demonstrations).
In the following we provide details on an example allocation of a DCN circuit with endpoints
at Starlight Chicago and Texas A&M university (TAMU) 13 used for the demonstration
at the ESCC/Internet2 Joint Techs Workshop. Listings 1 and 2 provide details on the topology
of the circuit in question as seen from the Starlight and TAMU administrative domain.
Except for the Starlight and TAMU domain the circuit furthermore spans over the Lonestar
12Allocation of a single DCN circuit is a completely separate problem from the perspective of the media
streams planning in CoUniverse.
13http://www.tamu.edu/
5.3. NETWORK ORCHESTRATION 95
Education and Research Network (LEARN)14 administrative domain. The circuit is further
illustrated at Figure 6.7 as a part of the network topology used for the ESCC/Internet2 Joint
Techs Workshop demonstration.
Circuit 1 The Starlight ­ TAMU circuit as seen from the Starlight administrative domain.
Created time 2009/01/31 16:23
Bandwidth (Mbps) 1000
Source
urn:ogf:network:domain=dcn.internet2.edu:node=CHIC:port=S28415:link=10.100.100.33
Destination
urn:ogf:network:domain=tamu.edu:node=tamu-sw1:port=1-0-24:link=*
Intradomain hops
urn:ogf:network:domain=dcn.internet2.edu:node=CHIC:port=S28415:link=10.100.100.33
urn:ogf:network:domain=dcn.internet2.edu:node=CHIC:port=DTL9:link=10.100.90.65
urn:ogf:network:domain=dcn.internet2.edu:node=KANS:port=DTL1:link=10.100.90.66
urn:ogf:network:domain=dcn.internet2.edu:node=KANS:port=DTL2:link=10.100.90.110
urn:ogf:network:domain=dcn.internet2.edu:node=HOUS:port=DTL2:link=10.100.90.109
urn:ogf:network:domain=dcn.internet2.edu:node=HOUS:port=S26879:link=10.100.90.85
Interdomain path
urn:ogf:network:domain=dcn.internet2.edu:node=CHIC:port=S28415:link=10.100.100.33
urn:ogf:network:domain=dcn.internet2.edu:node=HOUS:port=S26879:link=10.100.90.85
urn:ogf:network:domain=tx-learn.org:node=learn-sw:port=1-10-2:link=*
VLAN 3440
Tagged true
As can be seen in Table 5.11, the time needed to allocate a single end-to-end circuit (and
bring the respective network link up) may be a matter of 2 or 3 minutes depending on the
complexity of the circuit and DCN Inter Domain Controller (IDC) which processes the allocation
request. The table depicts times necessary for allocation of the above discussed Starlight
­ TAMU circuit using both Starlight and TAMU IDCs. The ACCEPTED time presents the delay
between sending of the circuit allocation request from the CoUniverse midlleware and
its accepting by the IDC. The ACCEPTED state does not indicate the requested resources
were already reserved. The status of INCREATE means that IDC schedules utilization of
the resources necessary for the whole circuit allocation. A status of INSETUP means he circuit
is being built E.g., the IDC contacts DCs in its own administrative domain and IDCs of
other administrative domains to issue commands configuring the network components in
question to bring the circuit up. Finally the status ACTIVE presents means that the circuit is
up and ready to transmit data. All times were measured beginning from sending the circuit
allocation request from the CoUniverse middleware to the IDC in question.
Presented results are still acceptable when establishing any collaborative environment
although the time necessary to establish the collaborative environment prolong from the
order of seconds to the order of minutes when using lambda links based network infrastructures.
On the other hand the times necessary to allocate a new circuits may introduce a very
significant delay when it is necessary to respond to some network failure by reallocation of
the circuit. A good example of such situation would be an interactive videoconferencing
14http://www.tx-learn.org/
96 CHAPTER 5. EVALUATION OF THE COUNIVERSE CONCEPTS
Circuit 2 The Starlight ­ TAMU circuit as seen from the TAMU administrative domain.
Created time 2009/02/01 01:01
Bandwidth (Mbps) 1000
Source
urn:ogf:network:domain=tamu.edu:node=tamu-sw1:port=1-0-24:link=*
Destination
urn:ogf:network:domain=dcn.internet2.edu:node=CHIC:port=S28415:link=10.100.100.33
Intradomain hops
urn:ogf:network:domain=tamu.edu:node=tamu-sw1:port=1-0-24:link=*
urn:ogf:network:domain=tamu.edu:node=tamu-sw1:port=1-0-25:link=*
Interdomain path
urn:ogf:network:domain=tamu.edu:node=tamu-sw1:port=1-0-24:link=*
urn:ogf:network:domain=tamu.edu:node=tamu-sw1:port=1-0-25:link=*
urn:ogf:network:domain=tx-learn.org:node=learn-sw:port=1-0-49:link=*
VLAN 3440
Tagged false
Starlight IDC TAMU IDC
ACCEPTED 5.459 s 8.007 s
INCREATE 17.411 s 32.989 s
INSETUP 63.864 s 81.144 s
ACTIVE 164.301 s 229.964 s
Table 5.11: Starlight ­ TAMU circuit allocation request processing times.
environment which transmits the media stream over a DCN circuit based network link. Any
failure of the network link (and the allocated circuit) leads to planning of the media streams
transmission over a different network link and probably new allocation of respective DCN
circuit. In the middle of the interactive videoconferencing session a delay (lag) in order of
minutes induced by reallocation of the failed network link may be unacceptable.
5.3.3 Conclusions
The novel approach we have used in context of collaborative environments (i.e., automated
allocation of DCN circuits based on the environment needs using CoUniverse middleware)
proved to be a feasible answer to user-empowered network orchestration. However unimpressive
the results presented in the previous section may look, it is necessary to realize the
difference between automated orchestration of lambda links based infrastructure we have
presented and the previously used manual approach discussed in the introduction of this
thesis. This difference is apparent both in terms of time and manpower necessary to establish
the network infrastructure for the collaborative environments we consider. Our experiments
also showed some practical issues with the current implementation of both CoUniverse and
DCN and raised new questions which are still to be solved.
In some real-world scenarios allocation of point-to-point circuits might not be a sufficient
tool to control the network optimally. Applications that involve some sort of multi-
5.3. NETWORK ORCHESTRATION 97
point data distribution (e.g., multipoint videoconferencing or distributed data visualization)
would definitely profit from being able to ask for allocation of the whole network interconnecting
all the nodes at once using CoUniverse. The rationale behind such desiderata is
that the application has virtually no knowledge about the underlying network capabilities
and only the network middleware is able to provide an optimal network topology interconnecting
the nodes. In the ideal case the application should be also able to put additional
constraints to the multipoint allocation request (e.g., maximum allowed latency or bandwidth
necessary between particular nodes). Finally, the topology of such network would be
returned back to the CoUniverse middleware to plan transmissions of the media streams.
Alternatively, allocation of multipoint connections could be offloaded to the application
middleware like CoUniverse provided that there is a mechanism which would allow the
middleware to ask for the topology of all links available between the nodes to interconnect at
some particular time. We however understand that providing a complete network topology
to an application or application middleware may be seen as a security threat and a breach of
abstraction level. Thus this scenario is not very likely to be implemented.
It would be possible to simulate such a scenario by polling all individual circuits and
compose the network topology from the information obtained from the DCN. In terms what
we have done with CoUniverse and DCN this would mean requesting allocation of all individual
circuits with maximum parameters from the DCN middleware. This method is
however extremely unpractical as for n network interfaces the polling could result in actually
allocating full mesh network topology comprising of O(n2) circuits.
There is also an outstanding issue of interfacing with the Interent2 DCN based network
infrastructure using third party applications such as the CoUniverse middleware caused by
the way of allocation of individual circuits using the IDCP and the security model of the
Internet2 IDCP implementation. In order to allocate a single circuit one must request the
allocation through the InterDomain Controller (IDC) which belongs to the same administrative
domain as the beginning DCN endpoint of the circuit. As the security model of the
Internet2 IDCP is based on X.509 public-key infrastructure [77] it is necessary to guarantee
that the CoUniverse middleware has the X.509 certificate of each ICD that may be potentially
involved in provisioning of the network infrastructure for the orchestrated collaborative environment.
Vice versa it is also necessary to guarantee that all these IDCs have an X.509 certificate
of the CoUniverse middleware. It is necessary to ensure that the keys are distributed
accordingly between all IDCs and CoUniverse peers that might be running the AGC service
to interface with the IDCs before the first circuit allocation attempt.
Chapter 6
Applications and Demonstrations
The CoUniverse middleware provides a general framework for orchestration of networkcentric
applications. In this context, it should be noted that the applications we describe in
this chapter are only examples selected either because they provided direct motivation for
CoUniverse design or are applications we have been working on and can benefit from being
orchestrated by CoUniverse. All these applications are built on component based environments
providing high-quality interactive collaboration and/or require orchestration of the
network infrastructure based on the application demands. All applications discussed later
in this chapter share some common properties. The applications are built using a number
of independent components which transmit data (usually media) streams over a network
infrastructure. As the data streams have high bandwidth demands and low transmission
latencies are required for the applications, the network infrastructure is based on optical
networks and lambda services. The number of components the applications consist of, very
complex configuration of optical links based network infrastructure and necessity to rapidly
respond to changes and outages of the networking infrastructure as well as to the faults of
the environment components make the use of CoUniverse middleware beneficial.
We have showcased the CoUniverse middleware during several occasions in the past.
Each demonstration showed some particular CoUniverse feature (e.g., orchestration of component
based collaborative environments or ability to orchestrate lambda link based network
infrastructure). We describe these demonstrations together with a discussion of lessons
learned during the showcases in the second part of this chapter.
6.1 Applications
6.1.1 Advanced Multi-party Videoconferencing
High-quality videoconferencing requires usage of a high-resolution video and high-quality
audio. Besides of that it is necessary to provide a low latency audio and video distribution
so that the communication in a multi-party videoconference can be truly interactive.
The high-quality video requirement can be met when using HDTV video. The latency of
the video distribution perceived by the videoconference participants is induced especially
by processing of the video and audio and by transmission of the media over the network
infrastructure.
98
6.1. APPLICATIONS 99
The latency introduced by processing of video and audio can be minimized to a large
extent by using uncompressed media. We have used the uncompressed HDTV digital video
as defined in the SMPTE 292M standard [122]. The bandwidth for such a video-stream with
resolution of 1920×1080 pixels, 60 interlaced fields per second, 10 bits per color plane, and
4:2:2 color space sampling is 1,485,000,000 bits per second or 1.485 Gbps. This payload is
further encapsulated into UDP/IP stream (44 bytes per packet), leading to around 1.5 Gbps
bandwidth requirement when transmitted over the network. The bandwidth requirements
of a single uncompressed HDTV video stream can be met utilizing a dedicated network
circuits over 10 GE fiber optic network. Using such network links also minimizes the latency
of the media transmission.
We have first proposed such a videoconferencing system in [69] and used it since in a
number of cases to build ad-hoc videoconferencing environments. Our experiences show
that this videoconferencing system has a number of properties which make utilization of
CoUniverse to orchestrate the videoconferencing environment beneficial.
Our videoconferencing environment is component based, with a specific component configured
and invoked for each specific task such as media acquisition, media displaying or
media distribution. Even for a moderate size videoconferencing environment this presents
a number of nodes and components to configure, invoke and monitor. Doing so manually
takes excessive amounts of time which is inadequate especially when establishing ad-hoc
videoconferencing environments.
Manual orchestration of the videoconferencing environment becomes even more problematic
when dealing with the underlying physical network infrastructure configuration.
Videoconferencing environment built using transmissions of uncompressed HDTV video
assume using high-bandwidth 10 Gbps optical network links. Such network infrastructure
is shared among many users and usually configured for their applications and may require
reconfiguration for each ad-hoc videoconferencing event. Also, since the network infrastructure
is usually spanning across several administrative domains, its each reconfiguration
involves a number of network administrators who must cooperate with each other.
Last but not least, in a real world situations we do not work with a faultless components
and networking infrastructure. A faulty component (e.g., UDP packet reflector or a
node running the reflector) may render whole video or audio distribution worthless. A SW
component may be simply restarted manually. However, in case of any node or networking
infrastructure failure it is necessary to find some backup solution which also involves
manual and tedious reconfiguration and re-invocation of the environment components.
6.1.2 High-Quality Immersive Multi-Party Distant Learning
A straightforward application of advanced multi-party videoconferencing described in the
previous section is a distant education. Using CoUniverse to orchestrate such multi-party
distant learning environment is also very straightforward as the properties of such an environment
are the same as in the case of underlying videoconferencing environment. The only
difference, which makes usage of CoUniverse further beneficial, is the fact that the videoconferencing
environment is being established, configured and orchestrated repeatedly on a
regular basis. A clear benefit of using CoUniverse is in this case the fact that it is necessary
to configure the videoconferencing environment just once.
In 2007 we have developed a concept of distributed classroom and carried out an experimental
run of "Introduction to High Performance Computing" course (also known as the
100 CHAPTER 6. APPLICATIONS AND DEMONSTRATIONS
HPC class) taught at Louisiana State University by Prof. Thomas Sterling and distributed to
four other universities in the US and Czech Republic [73]. In 2007 Louisiana State University
in Baton Rouge ­ LSU, Masaryk University in Brno, Czech Republic ­ MU, University
of Arkansas in Fayetteville ­ UARK, Louisiana Tech University in Ruston ­ LATECH and
later joined by North Carolina State University in Raleigh (through MCNC, North Carolina)
participated in the first HPC class experiment.
Figure 6.1: HPC class setup at Laboratory of Advanced Networking Technologies, Masaryk
University
The experiment highlighted especially the necessity of automated allocation of lambda
links based network, its monitoring and monitoring of all components of the multi-party
videoconferencing environment. During the first run of the HPC class the allocation of
lambda based network links was solved by utilizing HARC1 [94] developed by the Enlightened
project2. The allocation of lambda links based infrastructure as well as the monitoring
of the network infrastructure was however done completely manually. Since a largely experimental
network infrastructure and bleeding edge computer equipment was used to build
the distributed classroom environment, we were experiencing a number of stability issues
which usually led to difficult and time consuming manual reconfiguration of at least parts
of the components of the environment.
The experiences and lessons learned during our maintaining of the HPC class environment
led directly to prototyping of the CoUniverse middleware. Since 2007 two another
1http://www.cct.lsu.edu/~maclaren/HARC
2http://www.enlightenedcomputing.org/
6.1. APPLICATIONS 101
Figure 6.2: Network topology scheme for the Spring 2007 HPC class run.
runs of the HPC class were held with increasing number of participants. The next run of the
HPC class is expected to be transmitted over Dynamic Circuit Network infrastructure which
even more justifies the utilization of CoUniverse to orchestrate the class environment.
6.1.3 Stereoscopic Video Transmissions for Medical Applications
We have first described component based transmission of stereoscopic video over IP networks
in [90]. The common characteristics of previously described applications and stereoscopic
video transmissions is that there are specific components used for both video sending
and receiving. As we are sending the stereoscopic video as two separate streams (one stream
of video being sent for each eye), the number of components (senders and receivers) doubles
for each one way end-to-end transmission. Moreover, a paramount prerequisite for a
coherent perception of the stereoscopic video is that both streams of video for each eye are
received, processed and displayed with possibly the same latency. We have tackled this
issue by enforcing the synchronization of both streams utilizing a synchronizing packet reflector
[66]. Any multi-point distribution of the stream pair needed for the stereoscopic video
would add another components to the environment. Thus, for more complex applications
involving larger number of stereoscopic video transmissions the number of components to
orchestrate increases quite quickly.
We have originally designed the stereoscopic video transmissions using a rather lowbandwidth
Digital Video (DV)3. The bandwidth necessary for transmission of a single DV
stream is 25 Mbps (i.e., 50 Mbps for one way stereoscopic video transmission). Such a bandwidth
is no match for present day 10 GE networks. However, when considering Fast Ethernet
networks, the bandwidth necessary for one way stereoscopic video transmission becomes
comparable to the capacity of the network links. The idea of using standalone specific
3http://www.dv.com/
102 CHAPTER 6. APPLICATIONS AND DEMONSTRATIONS
components for sending and receiving separate streams of video for each eye works however
in a general way. This allows us for example to replace the components originally used
for video sending and receiving with UltraGrid and use uncompressed HDTV video instead
of DV. This is obviously a major enhancement in terms of the quality of the video at the
cost of the fact that we have again to deal with streams of video demanding a bandwidth
comparable to the capacity of even the highest bandwidth network links.
Figure 6.3: Stereoscopic video projection at Laboratory of Advanced Networking Technologies,
Masaryk University
With recent advances in computer networks the interactive stereoscopic video transmissions
became an important tool in a variety of medical areas such as general surgery [58],
urology [20] or opthalmology [89] for both patient treatment and distant learning. As these
medical applications are potentially mission critical they can benefit especially from the selfhealing
abilities provided by the CoUniverse middleware.
6.1.4 Interactive Remote Visualizations of Large Data Sets
The study of complex scientific problems may involve a large scale sets of data, computer
simulations and overseas collaboration of experts from different fields. The researchers need
tools to collaboratively visualize, analyze and discuss the large amounts of data their simulations
create. We have participated in development of component based interactive remote
visualization environment (providing a means of advanced videoconferencing and visualization
distribution) that satisfies such a needs.
The collaborative visualization is built on several components:
6.2. DEMONSTRATIONS 103
1. data visualization,
2. distribution of images to participating sites,
3. tools for remote control of the visualization.
The visualization component has a rendering front-end and distributed back-end which
consisting of multiple processes running on separate remote supercomputer nodes. The
rendered images are in real time distributed by the means of above described multi-party
videoconferencing technology to the participants taking part in the collaborative session.
We took part in a demonstration of the technology during the iGrid 2005 workshop [72].
For the demonstration LSU (Louisiana), CESNET/MU (Czech Republic) and Calit2 (California)
participated in a distributed collaborative session visualizing a binary black hole
simulation. The overall size of the visualized data set was 120 GB. The set was processed in
real time by a visualization back-end consisting of 144 processors and 384 GB RAM.
The visualization images are rendered in real time and both high quality and interactivity
is required the distribution of the visualization has a character of the above described videoconferencing
environment. Thus it is reasonable and straightforward to deploy CoUniverse
to orchestrate the distribution of rendered images to the participants of the collaborative visualization
session. Orchestration of the interactive remote visualization as whole would
require especially co-allocation of network resources necessary for the distribution of the
rendered visualization and computing resources needed for the visualization rendering itself.
This is however out of the scope of this work.
6.1.5 Collaborative Film Postprocessing
Another example of application that could benefit from being orchestrated by the CoUniverse
is the remote collaborative postprocessing for the film industry. Together with our
partner Cinepost4 we have been pursuing to build an environment that would allow for
collaboration over remote digital color grading session. During the session an operator controls
a remote color grading console producing a video which is then distributed to the film
company management or director of the movie and back to the operator in order to provide
him a feedback. Such a scenario comprises a point-to-multipoint distribution of uncompressed
movie material together with a multipoint videoconference. We have implemented
a support for uncompressed 2K, 10 bit RGB, 24 fps video using the UltraGrid system to allow
for low-latency video transmissions in quality suitable for the film industry. Such a transmission
again requires approximately 1.5 Gbps of bandwidth. Therefore it is necessary to
employ network infrastructures providing advanced lambda services to build such a film
prostprocessing environment allowing collaboration across studios in Europe and USA.
6.2 Demonstrations
We have demonstrated the above mentioned applications a number of times during various
events. The first and one of the most notable demonstrations took place at the iGrid workshop
held during the 2005 GLIF meeting. We have demonstrated the advanced multi-party
videoconferencing and took part in a demonstration of interactive remote visualizations.
4http://www.cinepost.cz/
104 CHAPTER 6. APPLICATIONS AND DEMONSTRATIONS
Figure 6.4: Remote interactive color grading session.
Since than we have demonstrated especially the advanced multi-party videoconferencing
and variety of its applications including immersive distant learning a number of times (see
e.g., iGrid 20055, SuperComputing'056 , SuperComputing'067 or Fall 2008 Internet2 Member
Meeting8). Our experiences and lessons learned during these demonstrations confirmed
the necessity and usefulness of the CoUniverse middleware to orchestrate above mentioned
applications and environments. In this section we describe selected demonstrations where
CoUniverse was directly involved in orchestration of some application. In the following sections
we will also pinpoint the features introduced for the described demonstration and discuss
the lessons learned during real-world deployment of the theoretical concepts described
in this thesis.
6.2.1 GLIF 2007
The prototype implementation of CoUniverse was demonstrated and evaluated for the first
time during the GLIF annual meeting in 2007. The CoUniverse was used to orchestrate a
network of twelve nodes using a high quality, high bandwidth HDTV video transmissions
and audioconferencing to create a multipoint-to-multipoint videoconferencing environment
connecting three sites (Louisiana State University, USA with Charles University, Czech Re-
5http://www.igrid2005.org/
6http://sc05.supercomputing.org/
7http://sc06.supercomputing.org/
8http://events.internet2.edu/2008/fall-mm/
6.2. DEMONSTRATIONS 105
public and Academia Sinica, Taiwan). Figure 6.5 shows the visualization of planned and
deployed transmissions between the nodes building the videoconferencing environment.
Figure 6.5: Visualisation of media streams transmissions planned for the GLIF 2007 videoconferencing
environment.
The demonstration showed especially the usability of CoUniverse concept as a whole.
During this demonstration we have showcased the ability of the CoUniverse middleware to
provide self-healing abilities to orchestrated collaborative environments. The network infrastructure
used for this demonstration featured a 10 GE and 1 GE subnetworks. We have
demonstrated the ability of CoUniverse to re-plan the uncompressed high-definition video
distribution demanding 1.5 Gbps per stream to distribution of compressed video demanding
250 Mbps per stream once we intentionally tore down part of the 10 GE network infrastructure.
After we restored the 10 GE infrastructure, the CoUniverse then again re-planned
and re-deployed the distribution of uncompressed video between the components of orchestrated
collaborative environment. Moreover, we utilized the concept of virtual sites (see
Section 3.3.1 for reference) to rearrange and fine tune the distribution of media streams for
the videoconference participants. Although the concept of virtual sites was not entirely in-
106 CHAPTER 6. APPLICATIONS AND DEMONSTRATIONS
tentional, but rather a natural feature implied by the CoUniverse design, it proved to be one
of the most useful concepts of CoUniverse.
6.2.2 SuperComputing'07
During the demonstration at 2007 Supercomputing event we have showcased CoUniverse
orchestrating a high-quality immersive distant learning environment connecting Masaryk
University, Louisiana State University and the showfloor in Reno, Texas. The goal of the
demonstration was to show that distant learning can benefit from being built on advanced
high-definition multi-party videoconferencing where the high-definition video and setup of
the classrooms in sense of both video and audio acquisition and playback provides a feel of
a local classroom for both students and lecturers. For this demonstration CoUniverse was
orchestrating an environment similar to that one brought up for the GLIF 2007 demonstra-
tion.
Figure 6.6: Visualisation of media streams transmissions planned for the SuperComputing'07
distant learning environment.
6.2.3 Winter 2009 ESCC/Internet2 Joint Techs
Together with CESNET, Lonestar Education and Research Network (LEARN)9, and Texas
A&M University (TAMU)10 we have demonstrated orchestration of Dynamic Circuit Networks
(DCN) using the CoUniverse middleware to enable an UltraGrid high-definition videoconferencing
application. The aim of this demonstration was especially to showcase the
9http://www.tx-learn.org/
10http://www.tamu.edu/
6.2. DEMONSTRATIONS 107
ability of CoUniverse to dynamically set up, monitor and tear down lambda circuits across
several administrative domains including TAMU, LEARN, and Internet2.
The network topology scheme is depicted at Figure 6.7. Since this showcase was the first
time showing the ability of CoUniverse to orchestrate Dynamic Circuit Networks based infrastructure,
the network setup was actually quite simple and involved just a single dynamic
lambda circuit.
I2 IDC
I2 Ciena
Houston
I2 Ciena
Chicago
VLANs: 3440/3441
for switch addressing:
10.34.40.0/24
to be used on vlan3440
for debug and test
Memorial
Student Center
College Station,
Texas
Wehner Building
College Station,
Texas
128.194.0.10
tamu-idc
128.194.197.114/29
learn-idc
74.200.185.12
128.194.0.155
coUniverse
tamu-sw
c3750
10.192.130.226/29
learn-sw
c3750E
74.200.185.11
DCN Workshop
LEARN POP
Houston, Texas
10.192.25.6/29
tamu-sw
c3750
hds.fi.muni.cz
Prague,
Czech Republic
Brno,
Czech Republic
Starlight
E1200
10GE
eth2
gig1/0/24
eth0
Internet
gig1/0/26
gig1/0/25
gig1/0/27
gig1/0/28
128.194.0.10
gig1/0/49
gig1/0/50
LEARN:https://74.200.185.12:8443/OSCARS/
TAMU:https://128.194.197.114:8443/OSCARS/
1Gig
Cu
10GE
Te1/0/1
vlan3440
vlan3441
LEARN Domain
TAMU Domain
1
2
3
Internet2
Dynamic Circuit Network
gig1/0/23
Force10
E300
20
195.113.205.230
C15454
Transponder
C15454
Transponder
147.251.9.130
Force10
S2410
21
HP5412
22
147.251.54.18
DWDM
Backbone
OC192
Figure 6.7: Network topology scheme for Winter 2009 ESCC/Internet2 Joint Tech demon-
stration
The demonstration showed that interfacing Dynamic Circuit Networks (Internet2 DCN)
from CoUniverse is a possible and feasible answer to network infrastructure orchestration.
On the other hand we have learned about some aspects of the Internet2 DCN utilization
which are influencing orchestration of any application or environment using Internet2 DCN
as base network infrastructure. These are namely authentication and authorization issues
and long times needed to set up any Internet2 DCN based lambda link.11
6.2.4 Spring 2009 Internet2 Member Meeting
We have demonstrated CoUniverse during another two occasions at Spring 2009 Internet2
Member Meeting held in Arlington, VA. Both demonstrations were medical-oriented. The
first demo connected the meeting showfloor with National Library of Medicine in Bethesda,
11These issues are discussed in detail in Sections 5.3.2 and 5.3.3.
108 CHAPTER 6. APPLICATIONS AND DEMONSTRATIONS
MD while the second one demonstrated a collaboration with Memorial Hermann Texas
Medical Center in Houston, TX. The aim of both demonstrations was to show how a "user"
can request a capability without understanding the technical details of what needs to be
setup and how.
Ultragrid
Receiver
DCN
IP
I2 DCN
Houston
I2 DCN
Washington
DRAGON
clpk-raptor
Switch
MAX
clpk-6509
Switch
I2 Router
Washington
MAX
clpk-t640
Router
Hotel
HP2848
Switch
production
IP VLANs:
246,247,248
LEARN DCN
Switch
Ultragrid
Sender
NLM
darma-sw2
Switch
Memorial Hermann
Texas Medical Center location
Houston, TX
National LIbrary of Medicine
Bethesda, MD
Crystal Gateway Marriott
Arlington, VA
DCN - CoUniverse Presentation
With "Just-In-Time" Medical demos
Wed Apr 22 2009
Polycom
Polycom
VLAN 3105 - Ultragrid Video (10.1.1.0/24)
VLAN 3205 - Monitoring (10.10.10.0/24)
VLAN 3305 ­ Polycom/Ultragrid (10.20.20.0/24)
29
21
30
20
4
vlan3305
vlan 3305
vlan 3305
MAX
lvl3-t640
Router
DRAGON
mcln-raptor
Switch
NLM
darma-sw1
Switch
51
52
Internet2
Ann Arbor
monitoring
1
vlan 3205
IDC circuit endpoints:
nlm.nih.gov or urn:ogf:network:domain=dragon.maxgigapop.net:node=CLPK:port=1-3-3:link=*
smm09.internet2.edu or urn:ogf:network:domain=dragon.maxgigapop.net:node=CLPK6509:port=0-4-16:link=*
utest.anna.internet2.edu or urn:ogf:network:domain=anna.internet2.edu:node=raptor1:port=UTEST:link=*
static
VLAN
config
static
VLAN
config
memorialhermann.org or urn:ogf:network:domain=gigapop.gen.tx:node=switch1:port=0-1-22:link=*
static
VLAN
config
MAX/DRAGON IDC URL: https://idc.dragon.maxgigapop.net/axis2/services/OSCARS
tagged
tagged
untagged
untagged
Figure 6.8: Network topology scheme for the Spring 2009 Internet2 Member Meeting CoUniverse
demonstration
During the meeting we have successfully demonstrated that CoUniverse is able to initialize
and handle a Dynamic Circuit Network based infrastructure and setup and orchestrate
an environment consisting of multi-party videoconference and distribution of medical images
among the session participants. The biggest contribution of the demonstration from the
users point of view was that we have showed how effortless is to operate any application
environment orchestrated by CoUniverse (provided that the configurations of all CoUniverse
nodes in question are already prepared). Also, this demonstration was the first time
we have showed the flexibility of the CoUniverse middleware to orchestrate not only a SW
components of the environment but also HW devices (H.323 videoconferencing equipment).
Chapter 7
Conclusions
7.1 Thesis Summary
Motivated by real-world need for self-organization, automated orchestration and resilience
provided for collaborative environments including applications featuring high-definition,
high-bandwidth multimedia transmissions, we have studied the concepts of self-organizing
systems and properties of the collaborative environments and tools to build collaborative
environments upon towards their self-organization, self-configuration, automated orchestration
and self-healing capabilities. To address the issues of collaborative environments,
we have been building and deploying, we have described the problem of real-time media
streams distribution for collaborative environments and automated orchestration of the collaborative
environment components, based on explicit planning of media streams transmissions.
Explicit planning of media streams distribution is a novel concept in the context of
collaborative environments. Also in the area of traffic placement planning in the data networks,
our approach introduces a rather novel planning of media streams transmissions
along data distribution trees rather than isolated paths as considered traditionally. One of
the key requirements was that the media streams distribution has to work even for real-time
transmissions of media streams with bandwidth demands comparable to capacities of network
links. In order to deal with the media streams planning, we have modeled the collaborative
environments we are typically working with, defined entities of the environments,
and eventually formulated the Media Streams Planning Problem (MSPP) and its variants
formally using constraint model. The presented constraint model has been implemented
as a part of presented self-organizing CoUniverse middleware, designed for dynamic orchestration
of advanced multimedia applications and collaborative environments based on
them. Although performance limitations of the current implementation limit its operation
to medium sized environments, the whole framework has been successfully demonstrated
number of times during international events and deployed on a testbed spanning USA and
Europe. In this context it is also necessary to note that the size of most common collaborative
environments is within the order of magnitude of the environments we are able to
orchestrate using CoUniverse. The important aspect is that even with limited scalability, it
automates orchestration of the collaborative environment components that would have to be
undertaken manually otherwise and improves both times needed to establish the collaborative
environment and to resolve any failure within the collaborative environment by several
orders of magnitude.
109
110 CHAPTER 7. CONCLUSIONS
To address and overcome the issues of manual network infrastructure configuration and
orchestration for the purposes of collaborative environments we have also shown utilization
of the Dynamic Circuit Networks (DCN). DCN generally allow for automated provisioning
of the network infrastructure, its orchestration and automated configuration. Automated
allocation of DCN circuits based on collaborative environments demands as rendered in
the CoUniverse middleware proved to be a feasible answer to user-empowered network orchestration
for the collaborative environments and for real-time media streams distribution
in general. The CoUniverse middleware tightly integrating the DCN features also presents
a rather novel approach being one of the first third party systems doing so in context of the
DCN1.
While we have designed the CoUniverse middleware primarily with the advanced multiparty
videoconferencing systems in mind, it can be very useful beyond this domain. Any
component-based applications with real-time orchestration requirements can be supported.
For example, if a scientific instrument, that is generating real-time data, is needed to be incorporated
into the large networking infrastructure and the data is supposed to be distributed
to one or more locations in real-time, the CoUniverse can be used to control the data distribution,
including the components along the path: data source (i.e., some component that is
a direct interface from the instrument to the computer network), data distributors, as well as
data receivers (be it storage or real-time visualization systems).
7.2 Future Work
Even though we have already designed, theoretically studied, implemented and successfully
deployed and demonstrated the CoUniverse middleware during a number of occasions and
proved the concepts of collaborative environments self-organization to be viable, there is
still space for improvements. We have implemented the Match Maker module addressing
the media streams planning problem to provide deterministic (and optimal) results. One
big issue of such approach is optimization of the media streams planning problem and its
implementation in order to support larger infrastructures. An interesting research towards
the planning and scheduling algorithms would be introducing planning methods with better
scalability to the detriment of yielding probabilistic results. The media streams planning
problem should also better incorporate and utilize knowledge of network structure, even if
it is only partial. We want also to include planning of media streams transmissions for native
multipoint applications. Furthermore, in context of resiliency provided by the CoUniverse
middleware to the orchestrated collaborative environments, we would like to introduce dynamics
into the media streams planning problem as well as incremental behavior of the
Match Maker module that would allow us to react to various events occurring in the environment
more efficiently than re-planning a new media streams transmissions from scratch
each time some major event occurs.
Our experiments with the Dynamic Circuit Networks and their utilization in the CoUniverse
middleware showed some practical issues with the current implementation of both
CoUniverse and DCN and raised new issues which are still to be solved. An interesting
and potentially useful area to explore remains the possibility to allocate circuits creating
multipoint connections between several nodes for the orchestrated applications2. Because
1Refer to Internet2 DCN research http://www.internet2.edu/network/dc/.
2P. Holub is involved in OGF NSI-WG for this reason.
7.2. FUTURE WORK 111
of knowledge of the orchestrated applications, that CoUniverse has, hints can be provided
about planned media streams transmissions in the network. Multi-point connections can be
combined with alternative paths, thus allowing for more flexible network allocation.
Appendix A
Correctness of the CSP Formulation of
the MSPP
Introduction
Proof of the correctness of the CSP presented in Section 5.2.1 was given by Dr. Rudová and
is to appear in P. Holub, M. Liška, H. Rudová: Data Transfer Planning with Tree Placement for
Collaborative Environments, which was submitted to Special issue of Constraints Journal on
Constraint Satisfaction for Planning and Scheduling.
The notation used in the following is consistent with the notation used elsewhere in
this thesis. See Chapter 4, Section 4.1 and Section 5.2.1 for reference and explanation of the
notation used.
Proof of CSP Correctness
We will consider four types of nodes v  V in our network N = (V, E) with respect to
each stream s  S and solution  and show that it is possible to partition all nodes with
respect to the stream s and the solution  such that V = IN(s, )  OUT(s, )  DIS(s, ) 
NO(s, ). We will actually see that nodes in IN(s, ) corresponds to nodes with consumers
of the stream s, OUT(s, ) contains one element corresponding to the node with producer(s),
DIS(s, ) are nodes with active distributors of the stream s and NO(s, ) has nodes with
non-active distributors of the stream s together with consumers and producers of different
streams. Figure A.1 demonstrates communication for each node type.
v v v v
IN(s, ) OUT(s, ) DIS(s, ) NO(s, )
Figure A.1: Types of nodes v  V. Black arrows correspond to links being used by s and
gray lines correspond to unused links by s.
Consider nodes v in IN(s, )  V. Here we have indeg(v, s) = 1 and outdeg(v, s) = 0.
For a node v in OUT(s, )  V, it holds indeg(v, s) = 0 and outdeg(v, s) = 1. Each node v
112
113
in the set DIS(s, )  V has indeg(v, s) = 1 and outdeg(v, s)  1. And finally, a node v in
NO(s, )  V has indeg(v, s) = 0 and outdeg(v, s) = 0.
Lemma 1 Each node with an active distributor d  D of the stream s and solution  belongs to the
set DIS(s, ). Nodes with non-active distributors for s belong to the set NO(s, ).
Proof of this lemma trivially follows from (5.10) for active distributors of the stream s since
indeg(v, s) = 1 for the node v running d. For non-active distributors of the stream s, it follows
from (5.9) since indeg(v, s) = 0.
Lemma 2 For a stream s and solution , the set OUT(s, ) contains the node with producer(s).
Proof 1 The node v with producer(s) certainly belongs to OUT(s, ) due to Eqn. (5.6) meaning
that outdeg(v, s) = 1, and due to Eqn. (5.5) meaning that indeg(v, s) must be 0 (recall that two
applications of the same stream cannot be placed on the same node).
Lemma 3 Consider the stream s and solution . The set IN(s, ) contains all nodes with consumers
c  consumers(c).
Proof is similar as for Lemma 2 with Eqns. (5.4) and (5.7) applied.
Lemma 4 Consider the stream s, solution  and node which contains an arbitrary number of consumers
and producers all of them for a different stream than s. All such nodes belong to the set
NO(s, ).
Proof 2 Each such node v must have indeg(v, s) = 0 since Eqn. (5.5) holds. Also, outdeg(v, s) = 0
since Eqn. (5.7) holds.
Corollary 1 For each stream s and solution , all nodes in V can be split to partitions using V =
IN(s, )  OUT(s, )  DIS(s, )  NO(s, ).
Corollary 2 The set DIS(s, ) contains only nodes with active distributors of the stream s for the
solution . The set OUT(s, ) contains the node with producer(s) only. The set IN(s, ) contains
only nodes with consumers c  consumers(c). The set NO(s, ) contains only nodes with nonactive
distributors of the stream s and nodes which contains an arbitrary number of consumers and
producers all of them for a different stream than s.
Both statements follows from Lemmas 1­4 taking into considerations all possible nodes in
the network. Each node must contain one application active for the stream s at most. These
are covered by Lemma 1­3. Other nodes containing either non-active distributor or a combination
of consumers and producers for different streams than s are covered by Lemma 1
and 4, respectively.
Before proving the main correctness theorem, it is necessary to show that Eqn. (5.11) does
not allow to have any cycle in the graph induced for each stream s by the solution  of the
problem P. First consider a directed graph G(s, ) wrt. each stream s such that G(s, ) =
(V, {l  E | sl(e, s) = 1}).
Lemma 5 Eqn. (5.11) ensures that there is no cycle in G(s, ) among nodes with distributors.
114 APPENDIX A. CORRECTNESS OF THE CSP FORMULATION OF THE MSPP
Proof 3 Denote G(s, ) = (VG, EG) and consider its subgraph GD = (VD, ED) containing k nodes
with distributors corresponding to nodes selected by C(n,k)(i) in Eqn (5.11). We also use indegD(v, s)
to denote indeg(v, s) in GD. Each node v  VD must have indegD(v, s) equal to 1 or 0:
* indegD(v, s) cannot be higher than 1 for any node;
* indegD(v, s) = 1 means that there is a link ending at v and beginning at some node from VD;
* indegD(v, s) = 0 means that either v  NO(s, ) holds or there is a link ending at v and
beginning at some node from VG\VD.
Eqn. (5.11) prohibits to have k links in GD because each of them would need to end in just one of the
k nodes which would mean a cycle. Certainly Eqn. (5.11) can prohibit more than k links in GD since
these links do not have enough ending nodes.
Finally, we must prove that we cannot have a cycle in GD if there are (k - 1) links at most as
allowed by Eqn. (5.11). By induction, we know that graph with one node cannot form a cycle and
we can expect that a graph with (k - 1) nodes cannot have cycles. Certainly we can take a graph
G = (V , E ) as a subgraph of GD containing only the (k - 1) nodes where those (k - 1) links end.
The last remaining node u must have indegD(u, s) = 0, i.e., it cannot be included in any cycle. Since
the graph G = (V , E ) has a smaller number of nodes, we proved the statement.
Theorem 1 Each solution  of the CSP P is correct, i.e.,
1. this solutions defines for each stream s a graph which is an oriented tree
T(s, ) = (V\NO(s, ), {l  E | sl(e, s) = 1})
such that each edge is oriented corresponding to the link l, its root node contains producer(p),
leafs corresponds to particular consumers c  consumers(s) and remaining nodes contain
active distributors of the stream s;
2. capacity of each interface and link is sufficient to transfer all streams which uses this interface
(or link) for the data transfer.
To present a proof of Theorem 1, we first prove the following lemma.
Lemma 6 There is no cycle in T(s, ).
Proof 4 Since the nodes from IN(s, )  OUT(s, ) have degree 1 they cannot be included in any
cycle. Also, remaining nodes from DIS(s, ) cannot form cycles either. Eqn. (5.11) prohibits cycles
among these nodes due to Lemma 5 since T(s, ) is a subgraph of G(s, ) and there is a distributor on
each node from DIS(s, ).
Proof 5 (Theorem 1) The item 2 is trivially satisfied by Eqns. (5.1) and (5.2). Consider the first
item for each stream s in detail. Certainly NO(s, ) nodes and its interconnecting links l cannot be
a part of T(s, ) since all corresponding variables sl(e, s) are equal to 0.
Root of the tree must be the only node in OUT(s, ) where the producer of s is placed. Leafs of the
tree are certainly nodes in IN(s, ) where consumers of s are running.
There must be a path from the node with the producer of s to each node v  IN(s, ) leading
possibly through some nodes from DIS(s, ). To find this path, we will repeat iteratively the following
step. There is just one link l ending at v and having sl(e, s) = 1 since indeg(v, s) = 1 holds for
115
all v  IN(s, )  DIS(s, ). Beginning of this link begin(l) must be either directly the node from
OUT(s, ) or some node from DIS(s, ). In the first case, the path to the node with the producer is
completed. In the other case, we are in a node with an active distributor of the stream s and we can
continue with another iterative step. Since there is a finite number of distributors and importantly,
there are no cycles due to Lemma 6, there must be a finite path to the node with producer(s).
Denote the constructed graph by T (s, ). Since it is connected and there are no cycles in T (s, )
due to Lemma 6, it must be a tree.
Finally, it must be proved that all nodes of T(s, ) are included in T (s, ). Certainly all nodes in
IN(s, )  OUT(s, ) are included in T (s, ). It remains to show that all nodes from DIS(s, ) are in
T (s, ). By contradiction, take all nodes W from T(s, )\T (s, ). Each path beginning at w  W
by the link l  T(s, ) leading possibly through other nodes from W would need to lead to a node from
IN(s, ) since there are no cycles due to Lemma 6. However, all u  IN(s, ) nodes together with
their links l ending at u and having sl(e, s) = 1 are already part of T (s, ) and cannot be used.
Since Theorem 1 and corresponding lemmas do not apply Eqns. (5.3) and (5.12)­(5.14),
the additional constraints of the CSP P+ are redundant. As they only restrict the set of
solution of P, any solution of P+ remains to be correct.
Now consider links elimination in Eqns. (5.16)­(5.18). Since all these eliminations remove
domain variables which are always equal to 0 in both P and P+ (for Eqn. (5.16) see Eqn. (5.2),
for Eqn. (5.17) see Eqn. (5.7) and for Eqn. (5.18) see Eqn. (5.5)), each solution of the problem
with added links elimination Eqns. (5.16)­(5.18) corresponds to an original solution in either
P or P+.
The last links elimination by Eqn. (5.19) removes domain variables concerning the data
transfer within the same site. Since data transfer between nodes with producers and consumers
in the same site has no sense (recall that each distributor is placed in a different
virtual site), these domain variables can be neglected. Since all other constraints in P hold,
any solution of the problem with added Eqn. (5.19) is correct. And to conclude, solution of
the problem P+
elim is also correct.
List of Abbreviations
AAA Authentication, Authorization and Accounting
AE Active Element
AG Application Group
AGC Application Group Controller
APN Articulated Private Network
CDN Content Delivery Network
CRM Compute Resource Manager
CSP Constraint Satisfaction Problem
DCN Dynamic Circuit Networks
DHT Distributed Hash Table
DM Domain Manager
DVC Distributed Virtual Computer
DV Digital Video
ESnet Energy Science Network
GLIF Global Lambda Integrated Facility
GMPLS Generalized Multi-Protocol Label Switching
HARC Highly-Available Robust Co-allocator
IDC Inter-domain Controller
IDCP Inter-domain Controller Protocol
IDM Inter-Domain Manager
IP Internet Protocol
JVM Java Virtual Machine
LEARN Lonestar Education and Research Network
LSU Louisiana State University
MCU Multipoint Control Unit
MKP Multiple Knapsack Problem
MPLS Multi-protocol Label Switching
MSPP Media Streams Planning Problem
MU Masaryk University
NCSU North Carolina State University
NLR National Lambda Rail
NRM Network Resource Manager
OGF Open Grid Forum
RENCI Renaissance Computing Institute
RON Resilient Overlay Network
RTP Real-time Transport Protocol
116
117
RTT Round Trip Time
SANET Sensor and Actor Network
SIP Session Initiation Protocol
SOAP Simple Object Access Protocol
SOA Service Oriented Architecture
SPT Shortest Path Tree
SSH Secure SHel
TAMU Texas A&M University
TCP Transmission Control Protocol
UA User Agent
UCLP User Controlled LightPaths
UCSD University of California, San Diego
UDP User Datagram Protocol
UUID Universally Unique Identifier
VLC VideoLan Client
VLSR Virtual Label Switch Router
VNC Virtual Network Computing
VRVS Virtual Room Videoconferencing System
WSDL Web Service Description Language
WSN Wireless Sensor Network
Bibliography
[1] K. Aberer, P. Cudré-Mauroux, A. Datta, Z. Despotovic, M. Hauswirth, M. Punceva,
and R. Schmidt. P-Grid: a self-organizing structured P2P system. SIGMOD Rec.,
32(3):29­33, 2003.
[2] R. K. Ahuja, T. L. Magnati, and J. B. Orlin. Network Flows. Prentice-Hall, 1993.
[3] D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris. Resilient overlay networks.
In SOSP '01: Proceedings of the eighteenth ACM symposium on Operating systems principles,
pages 131­145, New York, NY, USA, 2001. ACM.
[4] D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris. The Case for Resilient
Overlay Networks. In 8th Workshop on Hot Topics in Operating Systems, Elmau/Oberbayern,
Germany, May 2001.
[5] R. Anderson, R. Anderson, N. Linnell, M. Pervaiz, U. Saif, and F. Videon. Collaborative
technologies in international distance education. In CSCWD, pages 522­527, 2009.
[6] S. Apel and K. Bohm. Self-Organization in Overlay Networks. In Proceedings of 1st
CAISE'05 Workshop on Adaptive and Self-Managing Enterprise Applications, 2005.
[7] H. Arrow, J. E. McGrath, and J. L. Berdahl. Small Groups as Complex Systems. Sage
Publications, 2000.
[8] D. Awduche. MPLS and traffic engineering in IP networks. IEEE Communications
Magazine, 37:42­47, 1999.
[9] H. Balakrishnan, S. Seshan, P. Bhagwat, and F. Kaashoek. Self-Organizing Collaborative
Environments. In Proceedings of the NSF/DARPA/NIST Workshop on Smart Environments,
Atlanta, GA, USA, 1999.
[10] C. Barz, U. Bornhauser, P. Martini, M. Pilz, C. de Waal, and A. Willner. ARGON: Reservation
in Grid-enabled Networks. In P. Müller, B. Neumair, and G. Dreo Rodosek,
editors, DFN-Forum Kommunikationstechnologien, volume 130 of LNI, pages 75­84. GI,
2008.
[11] C. Barz, T. Eickermann, M. Pilz, O. Wäldrich, L. Westphal, and W. Ziegler. CoAllocating
Compute and Network resources - Bandwidth on Demand in the VIOLA
Testbed. In T. Priol and M. Vanneshi, editors, Towards Next Generation Grids, CoreGRID
Series, pages 193­202. Springer, 2007.
118
BIBLIOGRAPHY 119
[12] L. Battestilli, A. Hutanu, G. Karmous-Edwards, D. S. Katz, J. MacLaren., J. Mambretti.,
J. H. Moore, S. Park, H. G. Perros, S. Sundar, S. Tanwir., S. Thorpe, and Y. Xin. Enlightened
computing: An architecture for co-allocating network, compute, and other grid
resources for high-end applications. In High Capacity Optical Networks and Enabling
Technologies, 2007. HONET 2007. International Symposium on, pages 1­8, Nov. 2007.
[13] D. Bein. Self-Organizing and Self-Healing Schemes in Wireless Sensor Networks. In
S. C. Misra and I. Woungang and S. Misra, editor, Guide to Wireless Sensor Networks,
Computer Communications and Networks. Springer London, 2009.
[14] L. Berger. Generalized Multi-Protocol Label Switching (GMPLS) Signaling Functional
Description, 2003. RFC 3471. http://tools.ietf.org/html/rfc3471.
[15] L. Berger. Generalized Multi-Protocol Label Switching (GMPLS) Signaling Resource
ReserVation Protocol-Traffic Engineering (RSVP-TE) Extensions, 2003. RFC 3473.
http://tools.ietf.org/html/rfc3473.
[16] P. Biondi and F. Desclaux. Silver Needle in the Skype. Presentation at Black Hat
Europe'06, Amsterdam, the Netherlands, Mar. 2006.
[17] S. M. Blackburn, P. Cheng, and K. S. McKinley. Myths and realities: the performance
impact of garbage collection. In SIGMETRICS '04/Performance '04: Proceedings of the
joint international conference on Measurement and modeling of computer systems, pages 25­
36, New York, NY, USA, 2004. ACM.
[18] D. Bonfiglio, M. Mellia, M. Meo, D. Rossi, and P. Tofanelli. Revealing skype traffic:
when randomness plays with you. SIGCOMM Comput. Commun. Rev., 37(4):37­48,
2007.
[19] N. Bowen, J. Antognini, R. Regan, and N. Matsakis. Availability in parallel systems:
automatic process restart. IBM Syst. J., 36(2):284­300, 1997.
[20] J. Bowersox and R. L. Cornum. Remote operative urology using a surgical telemanipulator
system: preliminary observations. Urology, 52(1):17­22, 1998.
[21] R. Bramley, K. Chiu, S. Diwan, D. Gannon, M. Govindaraju, N. Mukhi, B. Temko,
and M. Yechuri. A Component Based Services Architecture for Building Distributed
Applications. High-Performance Distributed Computing, International Symposium on, 0:51,
2000.
[22] S. Cheng, D. Garlan, B. Schmerl, J. Pedro Sousa, B. Spitznagel, and P. Steenkiste. Using
Architectural Style as a Basis for System Self-repair. In The Working IEEE/IFIP Conference
on Software Architecture, pages 45­59. Kluwer, B.V, 2002.
[23] S. Cheng, A. Huang, D. Garlan, B. Schmerl, and P. Steenkiste. Rainbow: Architecturebased
self-adaptation with reusable infrastructure. IEEE Computer, 37:46­54, 2004.
[24] S. Cheng, H. A. Huang, D. Garlan, B. Schmerl, and P. Steenkiste. An Architecture for
Coordinating Multiple Self-Management Systems. In IEEE/IFIP Conference on Software
Architecture, pages 12­15. Kluwer Academic Publishers, 2004.
120 BIBLIOGRAPHY
[25] A. Chien and N. Taesombut. Integrated resource management for lambda-grids: The
Distributed Virtual Computer (DVC). Future Gener. Comput. Syst., 25(2):147­152, 2009.
[26] L. Childers, T. Disz, R. Olson, M. E. Papka, R. Stevens, and T. Udeshi. Access Grid:
Immersive Group-to-Group Collaborative Visualization. In Proceedings of Immersive
Projection Technology, Ames, IA, USA, 2000. Iowa State University.
[27] Y. Chu, S. Rao, S. Seshan, and H. Zhang. Enabling conferencing applications on the
internet using an overlay muilticast architecture. In SIGCOMM '01: Proceedings of
the 2001 conference on Applications, technologies, architectures, and protocols for computer
communications, pages 55­67, New York, NY, USA, 2001. ACM.
[28] M. R. Civanlar, O. Ozkasap, and T. Celebi. Peer-to-peer multipoint videoconferencing
on the internet. SP:IC, 20(8):743­754, September 2005.
[29] M.R. Civanlar, O. Ozkasap, and T. Celebi. Peer-to-peer multipoint videoconferencing.
In ICIP04, pages 2039­2042, 2004.
[30] F. Curbera, M. Duftler, R. Khalaf, W. Nagy, N. Mukhi, and S. Weerawarana. Unraveling
the web services web: An introduction to soap, wsdl, and uddi. IEEE Internet
Computing, 6(2):86­93, 2002.
[31] K. Czajkowski, I. Foster, and C. Kesselman. Resource Co-Allocation in Computational
Grids. In HPDC '99: Proceedings of the 8th IEEE International Symposium on High Performance
Distributed Computing, page 37, Washington, DC, USA, 1999. IEEE Computer
Society.
[32] E. Damiani, S. De Capitani di Vimercati, S. Paraboschi, P. Samarati, and F. Violante. A
reputation-based approach for choosing reliable resources in peer-to-peer networks. In
CCS '02: Proceedings of the 9th ACM conference on Computer and communications security,
pages 207­216, New York, NY, USA, 2002. ACM.
[33] B. Davie and Y. Rekhter. MPLS: technology and applications. Morgan Kaufmann Publishers
Inc., San Francisco, CA, USA, 2000.
[34] T. P. De Miguel, S. Pavon, J. Salvachua, and J. Quemada. ISABEL--experimental distributed
cooperative work application over broadband networks. Lecture Notes in Computer
Science, 868:353­362, 1994.
[35] R. Dechter. Constraint Processing. Morgan Kaufmann Publishers, 2003.
[36] S. De Capitani di Vimercati and P. Samarati. Access control in federated systems. In
NSPW '96: Proceedings of the 1996 workshop on New security paradigms, pages 87­99, New
York, NY, USA, 1996. ACM.
[37] C. Diot, B. N. Levine, B. Lyles, H. Kassem, and D. Balensiefen. Deployment issues for
the ip multicast service and architecture. Network, IEEE, 14(1):78­88, 2000.
[38] S. Dobson, S. Denazis, A. Fernández, D. Gaiti, E. Gelenbe, F. Massacci, P. Nixon, F. Saffre,
N. Schmidt, and F. Zambonelli. A survey of autonomic communications. ACM
Trans. Auton. Adapt. Syst., 1(2):223­259, 2006.
BIBLIOGRAPHY 121
[39] F. Dressler. Availability Analysis in Large Scale Multicast Networks. In 15th IASTED
International Conference on Parallel and Distributed Computing and Systems (PDCS2003),
volume I, pages 399­403, November 2003.
[40] F. Dressler. Self-Organization in sensor and actor networks. John Wiley & Sons, 2007.
[41] S. Egger and T. Braun. Performance Evaluation of Multicast for Small Conferences.
In Group Communications and Charges; Technology and Business Models, volume 2816 of
Lecture Notes in Computer Science, pages 226­233, 2003.
[42] T. Erl. Service-Oriented Architecture: Concepts, Technology, and Design. Prentice Hall PTR,
Upper Saddle River, NJ, USA, 2005.
[43] P. Ferguson and G. Huston. What is a VPN? In OPENSIG'98 Workshop on Open Signalling
for ATM, Internet and Mobile Networks, 1998.
[44] S. Figuerola, N. Ciulli, M. Leenheerc, Y. Demchenko, W. Ziegler, and A. Binczewski.
Phosphorus: Single-step on-demand services across multi-domain networks for escience.
In J. Wang, G. Chang, Y. Itaya, and H. Zech, editors, APOC 2007, volume
6784, page 67842X, Wuhan, China, 2007. SPIE.
[45] P. Galvez. EVO: Enabling Virtual Organizations. In CHEP'07, Victoria, Canada, 2007.
[46] P. Galvez and H. Newman. Networking, Videoconferencing and Collaborative Environments.
Comput. Phys. Commun., 110:43­50, 1998.
[47] A. Ganek and T. Corbi. The dawning of the autonomic computing era. IBM Syst. J.,
42(1):5­18, 2003.
[48] H. Garcia-Molina. Elections in a Distributed Computing System. IEEE Trans. Comput.,
31(1):48­59, 1982.
[49] M. R. Garey and D. S. Johnson. Computers and Intractability : A Guide to the Theory of
NP-Completeness (Series of Books in the Mathematical Sciences). W. H. Freeman, January
1979.
[50] D. Garlan, S. Cheng, and B. Schmerl. Increasing system dependability through
architecture-based self-repair. Architecting Dependable Systems, pages 61­89, 2003.
[51] L. Gharai, T. Lehman, A. Saurin, and C. Perkins. Experiences with High Definition
Interactive Video Conferencing. Multimedia and Expo, IEEE International Conference on,
0:433­436, 2006.
[52] L. Gharai and C. S. Perkins. High Definition Conferencing: Present, Past and Future.
In Proceedings of the 6th Annual AccessGrid Retreat, Ann Arbor, MI, USA, 2006.
[53] J. Glasmann, W. Kellerer, and H. Müller. Service Architectures in H.323 and SIP: A
Comparison. IEEE Communications Surveys and Tutorials, 5(2), 2003.
[54] B. Goetz. Java theory and practice: Dynamic compilation and performance measurement,
2004. http://www.ibm.com/developerworks/library/j-jtp12214/.
122 BIBLIOGRAPHY
[55] O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University
Press, 1 edition, April 2008.
[56] E. Grasa, S. Figuerola, A. López, G. Junyent, M. Savoie, B. St. Arnaud, and M. Lemay.
Articulated private networks in UCLP. Internet Research, 17(5):535­545, 2007.
[57] E. Grasa, X Hesselbach, S. Figuerola, V. Reijs, D. Wilson, J. Uzé, L Fischer, and
T. de Miguel. The MANTICORE project: Providing users with a Logical IP Network
Service. In TERENA Networking Conference, Brugges, Belgium, 2008.
[58] G. Graschew, S. Rakowsky, P. Balanou, and P. Schlag. Interactive telemedicine in the
operating theatre of the future. J Telemed Telecare, (6):20­24, 2000.
[59] C. Guok, D. Robertson, E. Chaniotakis, M. Thompson, W. Johnston, and B. Tierney.
A User Driven Dynamic Circuit Network Implementation. In Proceedings of 2008 IEE
GLOBECOM Workshops, pages 1­5, New Orleans, LA, USA, 2008.
[60] C. Guok, D. Robertson, M. Thompson, J. Lee, B. Tierney, and W. Johnston. Intra and
Interdomain Circuit Provisioning Using the OSCARS Reservation System. In BROADNETS,
2006.
[61] M. Hefeeda, A. Habib, B. Botev, D. Xu, and B. Bhargava. Promise: peer-to-peer media
streaming using collectcast. In MULTIMEDIA '03: Proceedings of the eleventh ACM
international conference on Multimedia, pages 45­54, New York, NY, USA, 2003. ACM.
[62] G. T. Heineman and W. T. Councill. Component-Based Software Engineering: Putting the
Pieces Together (ACM Press). Addison-Wesley Professional, June 2001.
[63] F. Heylighen. The Science of Self-Organization and Adaptivity, 1999.
[64] E. Hladká, P. Holub, and J. Denemark. An Active Network Architecture: Distributed
Computer or Transport Medium. In Proceedings of 3rd International Conference on Networking
(ICN 2004), pages 338­343, Gosier, Guadeloupe, March 2004.
[65] E. Hladká, P. Holub, and J. Denemark. User Empowered Virtual Multicast for Multimedia
Communication. In Proccedings of 3rd International Conference on Networking,
Colmar, France, 2004. University of Haute Alsace.
[66] E. Hladká, M. Liška, and T. Rebok. Stereoscopic video over IP networks. In Proceedings
of the International Conference on Networking and Services 2005, page 6, Papeete, Tahiti,
2005. Institute of Electrical and Electronics Engineers.
[67] P. Holub, E. Hladká, and L. Matyska. Scalability and Robustness of Virtual Multicast
for Synchronous Multimedia Distribution. In Networking ­ ICN 2005: 4th International
Conference on Networking, Reunion Island, France, volume 3421/2005 of Lecture Notes
in Computer Science, pages 876­883, La Réunion, France, April 2005. Springer-Verlag
Heidelberg.
[68] P. Holub, E. Hladká, M. Procházka, and M. Liška. Secure and pervasive collaborative
platform for medical applications. Studies in Health Technology and Informatics, 126:229­
238, 2007.
BIBLIOGRAPHY 123
[69] P. Holub, L. Matyska, M. Liška, L. Hejtmánek, J. Denemark, T. Rebok, A. Hutanu,
R. Paruchuri, J. Radil, and E. Hladká. High-definition multimedia for multiparty lowlatency
interactive communication. Future Generation Computer Systems, 22(8):856­861,
2006.
[70] H. Horiuchi, N. Wakamiya, and M. Murata. Proposal and Evaluation of a Network
Construction Method for a Scalable P2P Video Conferencing System. In Information
Networking. Towards Ubiquitous Networking and Services: International Conference,
ICOIN 2007, Estoril, Portugal, January 23-25, 2007. Revised Selected Papers, pages 669­
678, Berlin, Heidelberg, 2008. Springer-Verlag.
[71] N. Hu and P. Steenkiste. Evaluation and Characterization of Available Bandwidth
Probing Techniques. IEEE Journal on Selected Areas in Communications, 21:879­894, 2003.
[72] A. Hutanu, G. Allen, S. D. Beck, P. Holub, K. Hartmut, A. Kulshrestha, M. Liška, J. MacLaren,
L. Matyska, R. Paruchuri, S. Prohaska, E. Seidel, B. Ullmer, and S. Venkataraman.
Distributed and collaborative visualization of large data sets using high-speed
networks. Future Generation Computer Systems, 22(8):1004­1010, 2006.
[73] A. Hutanu, Y. Xin, S. Thorpe, P. Holub, R. Paruchuri, D. Eiland, and M. Liška. Uncompressed
HD video for collaborative teaching - an experiment. In The 3rd International
Conference on Collaborative Computing: Networking, Applications and Worksharing, pages
253­261, White Plains, NY, USA, 2007. ICST.
[74] T. Ibaraki. Enumerative approaches to combinatorial optimization, part i. Annals of
Operations Research, 10(1-4):3­342, 1987.
[75] T. Ibaraki. Enumerative approaches to combinatorial optimization, part ii. Annals of
Operations Research, (11):376­388, 1987.
[76] International Telecommunication Union. ITU-T X.200 Data Network and Open System
Communications. Open Systems Interconnection ­ Model and Notation., July 1994.
[77] International Telecommunication Union. ITU Recommendation X.509. Information
technology ­ Open systems interconnection ­ The directory: Authentication framework,
2000. http://www.itu.int/rec/T-REC-X.509/en.
[78] J. Jannotti, D. Gifford, K. Johnson, F. Kaashoek, and J. O'Toole. Overcast: Reliable
Multicasting with an Overlay Network. In Usenix OSDI Symposium 2000, pages 197­
212, October 2000.
[79] X. Jiang and D. Xu. Violin: Virtual internetworking on overlay infrastructure. In ISPA,
pages 937­946, 2004.
[80] O. Kamarainen and H. El Sakkout. Local probing applied to network routing. In
CPAIOR 2004, pages 173­189. Springer-Verlag LNCS 3011, 2004.
[81] H. Kellerer, U. Pferschy, and D. Pisinger. Knapsack Problems. Springer, Berlin, Germany,
2004.
[82] J. Kephart and D. Chess. The vision of autonomic computing. Computer, 36(1):41­50,
2003.
124 BIBLIOGRAPHY
[83] A. Kirstädter, C. Gruber, J. Riedl, and T. Bauschert. Carrier-Grade Ethernet for Packet
Core Networks. In 2006 International Conference Asia Pacific Optical Communications
(APOC), Gwangju, Korea, 2006.
[84] G. Kola, T. Kosar, and M. Livny. A Fully Automated Fault-tolerant System for Distributed
Video Processing and Off-site Replication. In Proceedings of the 14th ACM
International Workshop on Network and Operating Systems Support for Digital Audio and
Video (NOSSDAV 2004), Kinsale, Ireland, June 2004.
[85] T. Kosar and M. Livny. A framework for reliable and efficient data placement in distributed
computing systems. J. Parallel Distrib. Comput., 65(10):1146­1157, 2005.
[86] P. Leach, M. Mealling, and R. Salz. A Universally Unique IDentifier (UUID) URN
Namespace, 2005. RFC 4122. http://tools.ietf.org/html/rfc4122.
[87] J. Lever. A local search/constraint propagation hybrid for a network routing problem.
International Journal on Artificial Intelligence Tools, 14(1­2):43­60, 2005.
[88] G. J. Lewis, S. M. Hasan, V. N. Alexandrov, M. T. Dove, and M. Calleja. Collaborative
Virtual Environment for Advanced Computing. Computers and Artificial Intelligence,
24(1), 2005.
[89] H. K. Li. Telemedicine and ophthalmology. Surv Ophthalmol, 44(1):61­72, 1999.
[90] M. Liška. Design and Implementation of Capturing, Transmission, and Display of
Stereoscopic Video in DV Format. Master's thesis, Faculty of Informatics, Masaryk
university, jan 2005.
[91] K. Lua, J. Crowcroft, M. Pias, R. Sharma, and S. Lim. A survey and comparison of peerto-peer
overlay network schemes. Communications Surveys & Tutorials, IEEE, pages
72­93, 2005.
[92] Q. Ma and P. Steenkiste. On path selection for traffic with bandwidth guarantees. In
IEEE International Conference on Network Protocols, pages 191­202, 1997.
[93] M. Macedonia and D. Brutzman. Mbone provides audio and video across the internet.
Computer, 27(4):30­36, 1994.
[94] J. MacLaren. HARC: The highly-available resource co-allocator. In On the Move to
Meaningful Internet Systems 2007: CoopIS, DOA, ODBASE, GADA, and IS, volume 4804
of Lecture Notes in Computer Science, pages 1385­1402. Springer Berlin / Heidelberg,
2009.
[95] J. MacLaren and M. Mc Keown. HARC: A Highly-Available Robust Co-scheduler. In
Proceedings of the 5th UK e-Science All Hands Meeting, 2006.
[96] J. Mambretti. OptIPuter: Enabling advanced applications with novel optical control
planes and backplanes. Future Gener. Comput. Syst., 25(2):137­141, 2009.
[97] J. M. Marqus and L. Navarro. Autonomous and Self-sufficient Groups: Ad Hoc Collaborative
Environments. In CRIWG, pages 57­72, 2005.
BIBLIOGRAPHY 125
[98] J. M. Marqus, X. Vilajosana, T. Daradoumis, and L. Navarro. LaCOLLA: Middleware
for Self-Sufficient Online Collaboration. IEEE Internet Computing, 11(2):56­64, 2007.
[99] R. L. Morgan, S. Cantor, S. Carmody, W. Hoehn, and K. Klingenstein. Federated security
: The shibboleth approach. EDUCAUSE Quarterly, 27(4), 2004.
[100] M. F Munir and F. Filali. A novel self organizing framework for SANETs. In in Proc, of
the 12th European Wireless Conference EW'06, 2006.
[101] B. Nandy, D. Bennett, I. Ahmad, S. Majumdar, and B. St Arnaud. User controlled
lightpath management system based on a service oriented architecture. White paper,
Carleton University, 2006. http://www.solananetworks.com/UCLP/files/
UCLPv2-SOA.pdf.
[102] W. Ouaja and B. Richards. A hybrid multicommodity routing algorithm for traffic
engineering. Networks, 43(3):125­140, 2004.
[103] W. Ouaja and B. Richards. Hybrid lagrangian relaxation for bandwith-constrained
routing: Knapsack decomposition. In 20th Annual ACM Symposium on Applied Computing,
pages 383­387, 2005.
[104] V. Padmanabhan, H. Wang, P. Chou, and K. Sripanidkulchai. Distributing streaming
media content using cooperative networking. In NOSSDAV '02: Proceedings of the 12th
international workshop on Network and operating systems support for digital audio and video,
pages 177­186, New York, NY, USA, 2002. ACM.
[105] C. Perkins and L. Gharai. Real-time Collaborative Environments and the Grid. In
Proceedings of the Workshop on Advanced Collaborative Environments (WACE'04), Nice,
France, 2004.
[106] C. Perkins, L. Gharai, T. Lehman, and A. Mankin. Experiments with Delivery of
HDTV over IP Networks. In Proceedings of the 12th International Packet Video Workshop,
Pittsburgh, PA, USA, 2002. http://ultragrid.east.isi.edu/publications/
pv2002.pdf.
[107] G. Pieper, T. DeFanti, Q. Liu, M. Katz, P. Papadopoulos, J. Keefe, G. Hidley, G. Dawe,
I. Kaufman, B. Glogowski, K. Doerr, J. Schulze, F. Kuester, P. Otto, R. Rao, L. Smarr,
J. Leigh, L. Renambot, A. Verlo, L. Long, M. Brown, D. Sandin, V. Vishwanath,
R. Kooima, J. Girado, and B. Jeong. Visualizing Science: The OptIPuter Project. SciDAC
Review, pages 32­41, 2009.
[108] D. Pisinger. Algorithms for Knapsack Problems. PhD thesis, University of Copenhagen,
1995.
[109] J. Pouwelse, P. Garbacki, D. Epema, and H. Sips. The bittorrent p2p file-sharing system:
Measurements and analysis. Peer-to-Peer Systems IV, pages 205­216, 2005.
[110] J. Quemada, T. Miguel, S. Pavón, G. Huecas, T. Robles, J. Salvachúa, M.J. Perea,
E. Moro, D.A. Acosta, J.A. Fernández, F. Escribano, A. Diaz, J.L. Fernández, Juan A.
Sánchez, J. Sedano, and M. Gómez. Isabel: An Application for real time Audience
Interconnection over the Internet. In Proc. Terena Networking Conference (TERENA '04),
June 2004.
126 BIBLIOGRAPHY
[111] J. Quemada, T. De Miguel, S. Pavón, G. Huecas, T. Robles, J. Salvachúa, D. Andres
Acosta Ortiz, V. Sirvent, F. Escribano, and J. Sedano. Isabel: an application for
real time collaboration with a flexible floor control. In CollaborateCom, 2005.
[112] L. Renambot, B. Jeong, H. Hur, A. Johnson, and J. Leigh. Enabling high resolution
collaborative visualization in display rich virtual organizations. Future Gener. Comput.
Syst., 25(2):161­168, 2009.
[113] T. Richardson, Q. Stafford-Fraser, K. Wood, and A. Hopper. Virtual Network Computing.
IEEE Internet Computing, 2(1):33­38, 1998.
[114] M. Ripeanu. Peer-to-peer architecture case study: Gnutella network. In Peer-to-Peer
Computing, 2001. Proceedings. First International Conference on, pages 99­100, August
2001.
[115] F. Rossi, P. van Beek, and T. Walsh, editors. Handbook of Constraint Programming. Elsevier,
2006.
[116] A. Rowstron and P. Druschel. Pastry: Scalable, Decentralized Object Location, and
Routing for Large-Scale Peer-to-Peer Systems. In Middleware '01: Proceedings of the
IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, pages
329­350. Springer-Verlag, 2001.
[117] S. Savage, T. Anderson, A. Aggarwal, D. Becker, N. Cardwell, A. Collins, E. Hoffman,
J. Snell, A. Vahdat, G. Voelker, and J. Zahorjan. Detour: a Case for Informed Internet
Routing and Transport. IEEE Micro, 19:50­59, 1999.
[118] T. Shimizu, D. Shirai, H. Takahashi, T. Murooka, K. Obana, Y. Tonomura, T. Inoue,
T. Yamaguchi, T. Fujii, N. Ohta, S. Ono, T. Aoyama, L. Herr, N. van Osdol, X. Wang,
M. D. Brown, T. A. DeFanti, R. Feld, J. Balser, S. Morris, T. Henthorn, G. Dawe, P. Otto,
and L. Smarr. International real-time streaming of 4K digital cinema. Future Generation
Computer Systems, 22(8):929­939, October 2006.
[119] D. Shirai, T. Kawano, T. Fujii, K. Kaneko, N. Ohta, S. Ono, S. Arai, and T. Ogoshi.
Real time switching and streaming transmission of uncompressed 4K motion pictures.
Future Gener. Comput. Syst., 25(2):192­197, 2009.
[120] G. Simco. Internet 2 Commons: a collaborative environment . The Internet and Higher
Education, 5(4):373­376, 2002.
[121] H. Simonis. Constraint Applications in Networks. In F. Rossi, P. van Beek, and
T. Walsh, editors, Handbook of Constraint Programming, chapter 25. Elsevier, 2006.
[122] Society of Motion Picture and Television Engineers. Bit-serial digital interface for highdefinition
television systems. SMPTE 292M-1998.
[123] T. L. Suarez. Access Grid technology in classroom and research environments. J. Supercomput.,
41(2):133­145, 2007.
[124] N. Taesombut. Coordinated resource management for guaranteed high performance and efficient
utilization lambda-grids. PhD thesis, University of California, San Diego (UCSD),
2007.
BIBLIOGRAPHY 127
[125] N. Taesombut, X. Wu, A. Chien, A. Nayak, B. Smith, D. Kilb, T. Im, D. Samilo, G. Kent,
and J. Orcutt. Collaborative data visualization for earth sciences with the OptIPuter.
Future Gener. Comput. Syst., 22(8):955­963, 2006.
[126] S. Tanwir, L. Battestilli, H. Perros, and G. Karmous-Edwards. Dynamic scheduling
of network resources with advance reservations in optical grids. Int. J. Netw. Manag.,
18(2):79­105, 2008.
[127] S. R. Thorpe, L. Battestilli, G. Karmous-Edwards, A. Hutanu, J. MacLaren, J. Mambretti,
J. H. Moore, K. S. Sundar, Y. Xin, A. Takefusa, M. Hayashi, A. Hirano,
S. Okamoto, T. Kudoh, T. Miyamoto, Y. Tsukishima, T. Otani, H. Nakada, H. Tanaka,
A. Taniguchi, Y. Sameshima, and M. Jinno. G-lambda and EnLIGHTened: wrapped in
middleware co-allocating compute and network resources across Japan and the US. In
GridNets '07: Proceedings of the first international conference on Networks for grid applications,
pages 1­8, ICST, Brussels, Belgium, Belgium, 2007. ICST (Institute for Computer
Sciences, Social-Informatics and Telecommunications Engineering).
[128] H. Tianfield. Multi-agent autonomic architecture and its application in e- medicine. In
IAT '03: Proceedings of the IEEE/WIC International Conference on Intelligent Agent Technology,
page 601, Washington, DC, USA, 2003. IEEE Computer Society.
[129] J. Toga and J. Ott. ITU-T standardization activities for interactive multimedia communications
on packet-based networks: H.323 and related recommendations. Comput.
Netw., 31(3):205­223, 1999.
[130] J. Touch, Y. Wang, V. Pingali, L. Eggert, R. Zhou, and G. Finn. A global x-bone for
network experiments. In TRIDENTCOM '05: Proceedings of the First International Conference
on Testbeds and Research Infrastructures for the DEvelopment of NeTworks and COMmunities,
pages 194­203, Washington, DC, USA, 2005. IEEE Computer Society.
[131] D. A. Tran, K. Hua, and T. Do. Zigzag: An efficient peer-to-peer scheme for media
streaming. In In Proc. of IEEE Infocom, 2003.
[132] B. Traversat, A. Arora, M. Abdelaziz, M. Duigou, C. Haywood, J. Hugly, E. Pouyoul,
and B. Yeager. Project JXTA 2.0 super-peer virtual network. https://jxta.dev.
java.net/.
[133] F. Travostino, J. Mambretti, and G. Karmous-Edwards. Grid Networks: Enabling Grids
with Advanced Communication Technology. John Wiley & Sons, 2006.
[134] Y. Tu, J. Sun, M. Hefeeda, and S. Prabhakar. An analytical study of peer-to-peer media
streaming systems. ACM Trans. Multimedia Comput. Commun. Appl., 1(4):354­376, 2005.
[135] E. Verharen and E. Dobbelsteijn. Recommendations on real-time group communication
and collaboration services in support of international projects for TERENA, dec
2005.
[136] I. Wang. P2PS (Peer-to-Peer Simplified). In Proceedings of 13th Annual Mardi Gras Conference
- Frontiers of Grid Applications and Technologies, pages 54­59. Louisiana State University,
February 2005.
128 BIBLIOGRAPHY
[137] Y. Wang and J. Vassileva. Trust and Reputation Model in Peer-to-Peer Networks. In
P2P '03: Proceedings of the 3rd International Conference on Peer-to-Peer Computing, page
150, Washington, DC, USA, 2003. IEEE Computer Society.
[138] Z. Wang. Internet QoS: Architectures and Mechanisms for Quality of Service. Morgan
Kaufmann Publishers Inc., San Francisco, CA, USA, 2001.
[139] L. Winkler, E. Boyd, and C. Robb. Internet2 DCN Pilot Service: Background, Goals,
Use Cases and Definitions, 2009. https://spaces.internet2.edu/download/
attachments/10659/Internet2+DCN+Pilot+Service+Definition+v1.0.
pdf.
[140] R. Wittmann and M. Zitterbart. Multicast Communication: Protocols and Applications.
Academic Press, 1999.
[141] R. Wittmann and M. Zitterbart. Multicast Communication: Protocols, Programming, and
Applications. Morgan Kaufmann Publishers, Los Altos, CA, USA, 2001.
[142] R. Wolski. Dynamically forecasting network performance using the network weather
service. Cluster Computing, 1(1):119­132, 1988.
[143] R. Wolski, N. Spring, and J. Hayes. The Network Weather Service: A Distributed Resource
Performance Forecasting Service for Metacomputing. Future Generation Computing
Systems, 15:757­768, 1999.
[144] J. Wu, H. Zhang, S. Campbell, M. Savoie, G. Bochmann, and B. St. Arnaud. A Grid Oriented
Lightpath Provisioning System. In Proceedings of the 47th IEEE Global Telecommunications
Conference (Globecom'04), Workshop on High Performance Global Grid Networks,
pages 395­399, Dallas, TX, USA, 2004.
[145] M. Wu, Y. Zhu, and W. Shu. Placement of proxy-based multicast overlays. Comput.
Netw., 48(4):627­655, 2005.
[146] Y. Xin, L. Battestilli, and G. Karmous-Edwards. Generic optical network provisioning
services to support emerging grid applications. In BROADNETS, pages 131­140, 2007.
[147] S. Zanikolas and R. Sakellariou. A taxonomy of grid monitoring systems. Future Gener.
Comput. Syst., 21(1):163­188, 2005.
[148] M. Zerola, J. Lauret, R. Barták, and M. Šumbera. Using constraint programming to
resolve the multi-source/multi-site data movement paradigm on the grid. In XII Advanced
Computing and Analysis Techniques in Physics Research, 2008.
[149] M. Zerola, M. Šumbera, R. Barták, and J. Lauret. Using constraint programming to
plan efficient data movement on the grid. In 21st IEEE International Conference on Tools
with Artificial Intelligence, 2009.
[150] H. Zhang, M. Savoie, J. Wu, S. Campbell, G. Bochmann, and B. St. Arnaud. Serviceoriented
Layer 1 Virtual Private Network for Grid Applications. In Proceedings of the
2005 International Conference on Grid Computing and Applications (GCA'05), pages 106­
111, Las Vegas, NV, USA, 2005.
Vita
Personal Information
RNDr. Miloš Liška, doctoral student at Faculty of Informatics, Masaryk University and
junior researcher with CESNET z.s.p.o.
Scientific and Research activities
Applications of advanced computer networks, high-definition media processing, videoconferencing
technologies, self-organizing collaborative environments.
Professional Development Including Academical Stays
* 2007: 1 week research visit at MCNC, Research Triangle Park, NC, USA
* 2007: 4 months full-time internship at Center for Computation & Technology, Louisiana
State University, Baton Rouge, LA, USA
* 2006­2008: employed as junior researcher on EuroCareCF and Ithanet projects (Telenetworking
work package), CESNET
* 2004­up to now: junior researcher working on the "Virtual collaborative environment"
project, CESNET
* 2003: collaboration on the "Multimedia transmissions" project, CESNET
* 2003­up to now: Lectures recording project at Faculty of Informatics, Masaryk Univer-
sity
Pedagogical Activities
* 2006­2009: PV188 Principles of Multimedia Processing and Transmissions
* 2004: PB156 Computer Networks
Membership in Program Committees of International Conferences
* ICN 2010: The Ninth International Conference on Networks, program committee mem-
ber
Other Achievements
Participation on more than a dozen of successful major demonstrations of the technologies
and applications in the area of advanced multi-party videoconferencing, immersive
multi-party distant learning environments, collaborative remote visualizations,
high-definition collaborative imagery in various areas and advanced network infrastructures
orchestration.
129
Author's Selected Publications
Journal Papers
* Petr Holub, Eva Hladká, Michal Procházka, and Miloš Liška. Secure and pervasive
collaborative platform for medical applications. Studies in Health Technology and Informatics,
126:229­238, 2007.
* Petr Holub, Ludˇek Matyska, Miloš Liška, Lukáš Hejtmánek, Jiˇrí Denemark, Tomáš
Rebok, Andrei Hutanu, Ravi Paruchuri, Jan Radil, and Eva Hladká. High-definition
multimedia for multiparty low-latency interactive communication. Future Generation
Computer Systems, 22(8):856­861, 2006.
IF: 1.377
* Andrei Hutanu, Gabrielle Allen, Stephen D. Beck, Petr Holub, Kaiser Hartmut, Archit
Kulshrestha, Liška Miloš, Jon MacLaren, Ludˇek Matyska, Ravi Paruchuri, Steffen
Prohaska, Ed Seidel, Brygg Ullmer, and Shalini Venkataraman. Distributed and collaborative
visualization of large data sets using high-speed networks. Future Generation
Computer Systems, 22(8):1004­1010, 2006.
IF: 1.377
* Petr Holub and Miloš Liška. High-definition video transmissions for medical applications
and education. Technol. Health Care, 13(5):398­400, 2005.
International Reviewed Papers
* Miloš Liška, Petr Holub, Andrew Lake, and John Vollbrecht. CoUniverse Orchestrated
Collaborative Environments with Dynamic Circuit Networks. In The Ninth International
Conference on Networks ICN 2010, Menuires, France, 2010. To appear.
* Miloš Liška. On Media Streams Planning Problem in CoUniverse. In 5th Doctoral
Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2009),
pages 126­135, Znojmo, Czech Republic, 2009.
* Miloš Liška and Petr Holub. CoUniverse: Framework for building self-organizing
collaborative environments using extreme-bandwidth media applications. In Lecture
Notes in Computer Science vol. 5415 Euro-Par 2008 Workshops ­ Parallel Processing, pages
339­351, Las Palmas de Gran Canaria, Spain, 2008. Springer Berlin / Heidelberg.
130
BIBLIOGRAPHY 131
* Ludˇek Matyska, Eva Hladká, and Miloš Liška. High quality large scale virtual classroom.
In Proceedings of the 14th International Conference of European University Information
Systems (EUNIS 2008), page 4, Arhus, Denmark, 2008. Aarhus University.
* Andrei Hutanu, Yufeng Xin, Steven Thorpe, Petr Holub, Ravi Paruchuri, Daniel Eiland,
and Miloš Liška. Uncompressed HD video for collaborative teaching - an experiment.
In The 3rd International Conference on Collaborative Computing: Networking, Applications
and Worksharing, pages 253­261, White Plains, New York, 2007. ICST.
* Miloš Liška, Eva Hladká, and Vít Rusˇnák. Automated hypermedia authoring for individualized
learning. In Proceedings of the 8th International Technology Based Higher
Education and Training, pages 131­135, Kumamoto, Japan, 2007. Kumamoto University.
* Jan Vejvalka, Petr Holub, Michal Procházka, Miloš Liška, Eva Hladká, Michael Angastiniotis,
and Marina Kleanthous. Ithanet ­ developing en infrastructure of electronic
communication for thalassaemia research. In I. Moisil, M. Teseleanu, and F. Sicurello,
editors, Conference Proceedings of EMMIT 2007, Euro-Mediterranean Medical Informatics
and Telemedicine, 3rd International Conference, pages 181­186, Mangalia, Romania, 2007.
* Michal Procházka and Miloš Liška. Scalable and robust active element network.
In CESNET Conference 2006, pages 107­114, Prague, Czech Republic, 2006. CESNET
z.s.p.o.
* Eva Hladká, Miloš Liška, and Tomáš Rebok. Stereoscopic video over ip networks.
In Proceedings of the International Conference on Networking and Services 2005, page 6,
Papeete, Tahiti, 2005. Institute of Electrical and Electronics Engineers.
* Eva Hladká, Miloš Liška, and Ludˇek Matyska. Multimedia support for individualized
learning. In Fifth International Conference on Information Technology Based Higher Education
and Training, pages 4­9, Istanbul, Turkey, 2004. IEEE Catalog Number 04EX898.
National Reviewed Papers
* Eva Hladká, Petr Holub, and Miloš Liška. Modulární komunikaˇcní reflektor s DV
pˇrenosem. In Vysokorychlostní sítˇe 2004, pages 42­46, Praha, Czech Republic, 2004.
Talks and Presentations
* Petr Holub, Miloš Liška, Andrew Lake, Chris Tracy, Tom Lehman, John Vollbrecht,
and Brian Cashman. Interfacing CoUniverse & Internet2 DCN. Demonstration and
presentation at Spring 2009 Internet2 Member Meeting, Washington, USA, 2009.
* Petr Holub, Ravi Paruchuri, Stacey Simmons, Tomáš Rebok, Andrei Hutanu, Daniel
Eiland, and Miloš Liška. Enabling technologies for teaching an hpc class as a distributed
course. Lecture at SURA/ViDe, 2005. SPR2007 - The 9th Annual SURA/ViDe
Conference Atlanta GA, USA, mar 2007.
* Miloš Liška. Stereoscopic video using DV format. Presentation at Fall 2005 Internet2
Member Meeting, Philadelphia, USA, sep 2005.
132 BIBLIOGRAPHY
* Petr Holub and Miloš Liška. Lecture recording, processing, archiving, and streaming.
Lecture at SURA/ViDe, 2005. SPR2005 - The 7th Annual SURA/ViDe Conference
Atlanta GA, USA, 2005.
References to Selected Publications12
* Petr Holub, Ludˇek Matyska, Miloš Liška, Lukáš Hejtmánek, Jiˇrí Denemark, Tomáš
Rebok, Andrei Hutanu, Ravi Paruchuri, Jan Radil, and Eva Hladká. High-definition
multimedia for multiparty low-latency interactive communication. Future Generation
Computer Systems, 22(8):856­861, 2006.
1. Y. Xin, L. Battestilli, and G. Karmous-Edwards. Generic optical network provisioning
services to support emerging grid applications. In BROADNETS, pages
131­140, 2007.
Source: GSch
* Andrei Hutanu, Gabrielle Allen, Stephen D. Beck, Petr Holub, Kaiser Hartmut, Archit
Kulshrestha, Miloš Liška, Jon MacLaren, Ludˇek Matyska, Ravi Paruchuri, Steffen
Prohaska, Ed Seidel, Brygg Ullmer, and Shalini Venkataraman. Distributed and collaborative
visualization of large data sets using high-speed networks. Future Generation
Computer Systems, 22(8):1004­1010, 2006.
1. P. Coveney, G. Giupponi, S. Jha, S. Manos, J. MacLaren, S. Pickles, R. Saksena,
T. Soddemann, J. Suter, M. Thyveetil and S. Zasada. Large scale computational
science on federated international grids: The role of switched optical networks.
Future Generation Computer Systems, 26(1):99­110, 2010.
Source: WOS, GSch
2. Q. Wu, J. Gao, Z. Chen and M. Zhu. Pipelining parallel image compositing and
delivery for efficient remote visualization. Journal of Parallel and Distributed Computing,
69(3):230­238, 2009.
Source: WOS, GSch
3. J. MacLaren. HARC: The highly-available resource co-allocator. In On the Move
to Meaningful Internet Systems 2007: CoopIS, DOA, ODBASE, GADA, and IS, volume
4804 of Lecture Notes in Computer Science, pages 1385­1402. Springer Berlin /
Heidelberg, 2009.
Source: WOS, GSch
4. Y. Zhao, D. Ma, C. Hu, M. Liu and Y. Huang. SOCOM: A service-oriented collaboration
middleware for multi-user interaction with web services based scientific
resources. In Proceedings of ISPDC 2007: Sixth International Symposium on Parallel
and Distributed Computing, pages 195­202. 2007.
Source: WOS, GSch
1WOS: ISI Web of Science, GSch: Google Scholar
2The references include only journal papers and papers in proceedings of international conferences. Also,
self citations (if only partial by any of the authors of the original paper) are excluded.
BIBLIOGRAPHY 133
5. S. Tanwir, L. Battestilli, H. Perros, and G. Karmous-Edwards. Dynamic scheduling
of network resources with advance reservations in optical grids. Int. J. Netw.
Manag., 18(2):79­105, 2008.
Source: GSch
6. Y. Xin, L. Battestilli, and G. Karmous-Edwards. Generic optical network provisioning
services to support emerging grid applications. In BROADNETS, pages
131­140, 2007.
Source: GSch
7. M. Nino-Ruiz, C. Stock, I. Bishop and C. Pettit. Service oriented support for
heterogeneous software tools in environmental modelling and visualisation. In
Proceedings of the 18th World IMACS / MODSIM Congress, Cairns, Australia, 2009.
Source: GSch
* Michal Procházka and Miloš Liška. Scalable and robust active element network.
In CESNET Conference 2006, pages 107­114, Prague, Czech Republic, 2006. CESNET
z.s.p.o.
1. A. ˇCervenka. Encapsulation of a Communication Reflector into a Virtual Machine.
In CESNET Conference 2008, pages 123­130, Prague, Czech Republic, 2008.
CESNET z.s.p.o.
Source: WOS
* Miloš Liška. Design and Implementation of Capturing, Transmission, and Display of
Stereoscopic Video in DV Format. Master's thesis, Faculty of Informatics, Masaryk
University, 2005.
1. N. Kamnoonwatana, A. Kuprianov, P. Saengudomlert, T. Sanguankotchakorn, K.
Kanchanasut. DVTS Video Frame Rate Adjustment Based on Motion Detection.
In Second International Conference on Automated Production of Cross Media Content
for Multi-Channel Distribution AXMEDIS '06, pages 229­235, 2006.
Source: GSch