Programa de Verão 2016

Para o Programa de Verão de 2016, o Instituto de Matemática da UFRJ está oferecendo os seguintes cursos:

Autor: Jose Yallouz (Technion - Israel Institute of Technology, Bell Labs Israel)
Resumo/ementa: Coping with network failures has been recognized as an issue of major importance in terms of social security, stability and prosperity. It has become clear that current networking standards fall short of coping with the complex challenge of surviving failures. The need to address this challenge has become a focal point of networking research. In particular, the concept of tunable survivability offers major performance improvements over traditional approaches. Indeed, while the traditional approach is to provide full (100%) protection against network failures through disjoint paths, it was realized that this requirement is too restrictive in practice. Tunable survivability provides a quantitative measure for specifying the desired level (0%-100%) of survivability and offers flexibility in the choice of the routing paths. In this mini-course, we will focus on several aspects of this novel metric under two important transmission methods, namely unicast and broadcast. We will establish efficient algorithmic schemes for optimizing the level of survivability under two classes of QoS requirements, namely ``bottleneck'', e.g. bandwidth, and ``additive'', e.g. delay and cost. For the unicast method we aim to find a pair of paths such that maximizes the survivability level under the desirable QoS requirement. First, we establish some (in part, counter-intuitive) properties of the optimal solution. Then, we establish efficient algorithmic schemes for optimizing the level of survivability under additive end-to-end QoS bounds. Subsequently, through extensive simulations, we show that, at the price of negligible reduction in the level of survivability, a major improvement (up to a factor of 2) is obtained in terms of end-to-end QoS performance. Finally, we exploit the above findings in the context of a network design problem, in which we need to best invest a given ``budget'' for improving the performance of the network links. For the brodcast method we aim to find a set of spanning trees such that maximizes the survivability level under the desirable QoS requirement. We establish efficient algorithmic schemes for optimizing the level of survivability under various QoS requirements. In addition, we derive theoretical bounds on the number of required trees for maximum survivability. Finally, through extensive simulations, we demonstrate the effectiveness of the tunable survivability concept in the construction of spanning trees. Most notably, we show that, typically, negligible reduction in the level of survivability results in major improvement in the QoS performance of the resulting spanning trees. The minicourse we will include topics from the following fields: graph theory, approximation algorithm and convex optimization.
Cronograma: O curso será divido em 4 aulas de 90 minutos, de 25 a 29 de janeiro.
Bibliografia:
1) Ron Banner and Ariel Orda. The power of tuning: A novel approach for the efficient design of survivable networks. 15(4):737 --749, 2007.
2) Reinhard Diestel. Graph Theory, 4th Edition, volume 173 of Graduate texts in mathematics. Springer, 2012.
3) J.Tapolcai, Pin-Han Ho, P.Babarczi, and L.Rónyai. Internet Optical Infrastructure - Issues on Monitoring and Failure Restoration. Springer, 2014.
4) VijayV. Vazirani. Approximation Algorithms. Springer-Verlag New York, Inc., New York, NY, USA, 2001.
5) Jose Yallouz and Ariel Orda. Tunable qos-aware network survivability. Proceedings of the {IEEE} {INFOCOM} 2013, Turin, Italy, April 14-19, 2013, pages 944--952, 2013.
6) Jose Yallouz, Ori Rottenstreich, and Ariel Orda. Tunable survivable spanning trees. In {\em {ACM} {SIGMETRICS} / International Conference on Measurement and Modeling of Computer Systems, {SIGMETRICS} '14, Austin, TX, {USA} – June 16 - 20, 2014}, pages 315--327, 2014.

Topo