Compact Routing Messages in Compact Self-Healing Trees

24^th November 2015, 13:00 Ashton Lecture Theater
Dr. Amitabh Trehan
School of Electronics, Electrical Engineering and Computer Science
High Performance and Distributed Computing
Queen's University Belfast

Abstract

Efficient routing is critical in current networks, and will be even more so in future networks especially with low memory devices in the future IOT (Internet of Things). Existing compact routing schemes, e.g., Thorup and Zwick [SPAA 2001] and Chechik [PODC 2013], often have no means to tolerate failures, once the system has been setup and started. We present, to our knowledge, the first self-healing compact routing scheme. This scheme needs only O(log^2 n) memory, and is thus, 'compact'.

We introduce two algorithms of independent interest:

i) CompactFT: a novel compact version (using only O(log n) local memory) of the self-healing algorithm Forgiving Tree of Hayes et al. [PODC 2008].

ii) CompactFTZ: a compact self-healing routing scheme that is a combination of CompactFT with Thorup-Zwick’s tree-based compact routing scheme [SPAA 2001].

(Joint work with Armando Castaneda and Danny Dolev).