Columbia University Joint CS/EE Networking Seminar Series

Tunable Survivable Spanning Trees

Jose Yallouz

Electrical Engineering, Technion- Israel Institute of Technology

Monday, June 23rd, 2014  11-11:30AM

EE Conference Room Mudd 1300 Suite

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. Accordingly, in this study, we 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, typically, negligible reduction in the level of survivability results in major improvement in the QoS performance of the resulting spanning trees. Based on joint work with Ori Rottenstreich and Ariel Orda (ACM SIGMETRICS’14).

Bio: Jose Yallouz is a Ph.D. Student at the Department of Electrical Engineering, Technion - Israel Institute of Technology, under supervision of Prof. Ariel Orda. He is performing research in Computer Networks, specifically, in schemes for coping network failures. His area of interest are Survivability, Reliability and Fault-Tolerance, Routing Algorithms, Network on Chip and Computer Architecture.