28 - STUDENT - Media Streams Planning for Larger Groups

Pavel Troubil (Masaryk University)

High-end virtual collaborative environments frequently transmit multiple simultaneous streams, each of them in an 1:n scheme. Their bandwidth is close to capacities of current network links, hence special routing approaches are required to avoid congestion. Unfortunately, multicast is currently not suitable for the purpose due to possible congestion and deployment issues. The problem has been de ned as the Media Streams Planning Problem (MSPP). Problem components include data producers, distributors (application-level multicast substitution), consumers, and network links. The aim is to nd a distribution tree for each of the streams, such that capacities of the links are not exceeded by transferred bandwidth. Collaborative applications require reaction within seconds from initial request. Originally, the MSPP has been introduced together with constraint programming solver, capable of solving medium-sized instances of the problem in the given time limit of ve seconds.
We have implemented a mixed integer programming (MIP) solver based on a model from the constraint programming solver. The MIP solver brought an improvement of performance for two types of input topologies, which are typical cases for distant teaching and videoconferencing.
Further performance analyses have shown great performance impact of constraints, which avoid cycles in routing schemes. We have proposed and examined several alternative methods for coping with cycles, which further increase performance and allow larger topologies to be solved quickly. Compared to the constraint programming solver, number of handled communicating sites rises from 6 to 20 for one topology type and from 5 to 7 for
another, more complicated one.

Download file