Tunable Survivable Spanning Trees

June 23, 2014
11:00-11:30am
EE Conference Room
Speaker: Jose Yallouz, Department of Electrical Engineering, Technion - Israel Institute of Technology

Abstract

Coping with network failures has become a major networking challenge. The concept of tunable survivability provides a quantitative measure for specifying any desired level (0%-100%) of survivability, thus offering flexibility in the routing choice. Previous works focused on implementing this concept on unicast transmissions. However, vital network information is often broadcasted via spanning trees. We therefore investigate the application of tunable survivability for efficient maintenance of spanning trees under the presence of failures. 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 a negligible reduction in the level of survivability typically results in a major improvement in the QoS performance of the resulting spanning trees.

Based on joint work with Ori Rottenstreich and Ariel Orda (ACM SIGMETRICS'14).

Speaker Bio

Jose Yallouz is a Ph.D. student at the Department of Electrical Engineering, Technion - Israel Institute of Technology, under the supervision of Prof. Ariel Orda. His research focuses on the development of schemes for coping with computer network failures. His area of interests are survivability, reliability and fault-tolerance, routing algorithms, network-on-chip, and computer architecture.


500 W. 120th St., Mudd 1310, New York, NY 10027    212-854-3105               
©2014 Columbia University