Research projects in Systems and Networks
A.A. 2007-2008
Docente coordinatore: Roberto Battiti
Inaugurazione del corso:
MAR 3 Marzo, ore 17:00 (aula 204)
Orario lezioni in classe
Saranno inoltre definiti incontri periodici di gruppo ed incontri
individuali con il docente titolare del corso
e con i docenti tutor dei singoli studenti.
Progetti disponibili: (lista in corso di definizione)
- Prof. Montresor
Distributed network analysis
Network is a heavily overloaded term used to describe physical artifacts
like electrical circuits, transportation systems, and communication
networks, as well as more ``virtual'' phenomena like
social networks, food webs, and protein networks. Network analysis refers
to the analysis of (potentially large) networks through graph theory, with
the purpose of identifying their structural properties and features. While
social sciences have a long tradition in this field, it is only in recent
years that network analysis has emerged as a multi-disciplinary paradigm
for the study of complex systems in areas as diverse as computer science,
physics, epidemiology, biology, bibliometrics, etc.
The design of efficient algorithms for the computation of such properties
over large networks is an active area of research. Almost all of the
proposed algorithms are based on a completely natural, but very
strong assumption: data describing the network to be analyzed are
concentrated in a single location, where one or more computing units
operate on them based on a "global view" of the entire network.
We believe that it would be possible, and useful, to go beyond the
centralization assumption, and design algorithmic techniques for the
decentralized analysis of large-scale networks.
Decentralization means that a distributed collection of machines cooperate
to evaluate network-wide properties without each single node having access
to a global, complete view of the analyzed network.
Task of the student will be to design and implement distributed
protocols for decentralized network analysis.
- Prof. Lo Cigno
Frame-based video scheduling in P2P TV
Description
TV and movie video is divided for compression and encoding into frames (25/s in EU, 30/s in US), so that every playout system the unit of information is considered the frame. In modern compressed video (for example the MPEG family) frames are further organized in GOPs (Groups of Pictures) where correlation exists between the frames of the same GOP.
Goals
The first goal of this project is to evaluate through simulations the improvements that can be achieved by using some media awareness in chunk generation. Such simulations will be based on existing tools, which need to be extended for this project.
As a second goal, the student can design more advanced media-aware algorithms for dividing the media stream in chunks.
Finally, a theoretical analysis of the chunk generation strategies (not based on simulations) can be performed.
Markov-Decision-Process based peer selection
in P2P streaming systems
Description
Given a perfect knowledge of the state of a streaming P2P system, i.e., knowing the topology of the system as well as the state of each peer, it is possible to find deterministic scheduling decisions (possibly also optimal) that provide upper bounds on the diffusion delay of the stream.
Unfortunately, knowing perfectly the topology of an overlay and the state of each neighboring peer is not feasible, so that schedulers that are good (optimal) in ideal situations, often prove fragile in real life, performing very poorly. If perfect knowledge is unfeasible, however, some stochastic information about the system itself is normally available and also easy to gather. Based on this information it is possible to use a technique, known as Markov Decision Process (MDP) to develop robust and performing (if not optimal) scheduling strategies, moving from the deterministic guarantee provided by optimal schedulers working on global perfectly correct knowledge, to a probabilistic guarantee.
Goals
The first step of this project is understanding the amount and quality of information required to support MDP techniques in P2P streaming systems. After this first step, the project can take a theoretic twist, designing and analyzing an MDP based on models of the available information at peers, or a pragmatic twist, implementing and MDP scheduler into a simulator and evaluating its performance as the information available to support the decision changes.
Media-Aware P2P streaming
Description
A multimedia stream is a sequence of correlated and intertwined video and audio frames. Most P2P TV/Streaming systems simply ignore this fact and divide the stream in chunks without considering the stream nature (video frames, audio frames, the frame headers, etc...).
It can be argued that a more appropriate division of a media stream in chunks (which, for example, tries to begin a chunk with the beginning of a frame as much as possible) and the repetition of some important frame headers in multiple chunks can improve the streaming performance when some chunks are lost, and can decrease the diffusion delay even if no chunks are lost.
Goals
The first goal of this project is to evaluate through simulations the improvements that can be achieved by using some media awareness in chunk generation. Such simulations will be based on existing tools, which need to be extended for this project.
As a second goal, the student can design more advanced media-aware algorithms for dividing the media stream in chunks.
Finally, a theoretical analysis of the chunk generation strategies (not based on simulations) can be performed.
Chunks and Peers selection and scheduling
in pull-based P2PTV systems
Description
In order to support live streaming in P2P systems the application must guarantee
a low distribution delay of the information to all peers.
This is strictly related to the overlay characteristics and
the scheduling that distribute chunks to peers.
We consider an overlay of peers connected
with a general mesh topology. The total number of peers is N. Each
peer is connected to NN other peers which constitute
its neighborhood. A special case is NN=N-1, which define a
fully connected mesh. The stream is divided into equal-time pieces of information (chunks) of duration T, called a slot. In each slot every peer tries to pull one chunk from another peer.
Constraints can be added on the number of chunks that can be transmitted (either in uplink or downlink) at the same time, on the available bandwidth, on the size and distribution of the neighborhood, on the amount of information available at each peer and the delay with which this information is available.
Goals
Using a simulator developed in our university (SSSim) as well as theoretical analysis, the aim of this project is exploring the existence (or not) of optimal schedulers and the conditions under which they remain optimal.