A Fault-Tolerant Routing Strategy for Fibonacci-Class Cubes Xinhua Zhang1 and Peter K. K. Loh2 Department of Computer Science National University of Singapore, Singapore 2 School of Computer Engineering Nanyang Technological University, Singapore 1 20/1/31 1

Merits Applicable to all Fibonacci-class Cubes in a unified fashion, with only minimal modification of structural representation The maximum number of faulty components tolerable is the networks node availability: min(deg n) where n is a node For a n-dimensional Fibonacci-class Cube, each node of degree deg maintains and updates at most n(deg + 2) bits vector information Generates deadlock-free and livelock-free routes Can be implemented almost entirely with simple and practical routing hardware requiring minimal processor control

20/1/31 2 Road Map Introduction Generic approach to cycle-free routing (GACR) Fault-tolerant Fibonacci routing (FTFR) Experimental results Conclusion and future work 20/1/31

3 Road Map Introduction Generic approach to cycle-free routing (GACR) Fault-tolerant Fibonacci routing (FTFR) Experimental results Conclusion and future work 20/1/31

4 Introduction 1. Fibonacci-class cubes: FC definition 1. Fibonacci Cubes (FCn) f n f n 1 f n 2 f0 = 0, f1 = 1, f2 = 1, f3 = 2, f4 = 3, f5 = 5, f6 = 8 20/1/31 5 Introduction 1. Fibonacci-class cubes: FC example

1. Fibonacci Cubes Example 20/1/31 6 Introduction 1. Fibonacci-class cubes: FC equivalent definition 1. Fibonacci Cubes: equivalent recursive definition Vn 0 || Vn 1 10 || Vn 2 V3 {1, 0}

n 5 V4 {01, 00, 10} Edge: Hamming distance = 1 20/1/31 7 Introduction 1. Fibonacci-class cubes: EFC definition

2. Enhanced Fibonacci Cubes (EFCn) f n 2 f n 2 2 f n 4 Vn 00 || Vn 2 10 || Vn 2 0100 || Vn 4 0101|| Vn 4 V3 {1, 0} n 7 V4 {01, 00, 10} V5 {001, 101, 100, 000, 010} V6 {0001, 0101, 0100, 0000, 0010, 1010, 1000, 1001} Edge: Hamming distance = 1

20/1/31 8 Introduction 1. Fibonacci-class cubes: EFC example 2. Enhanced Fibonacci Cubes Examples 20/1/31 9 Introduction 1.

Fibonacci-class cubes: XFC definition 3. Extended Fibonacci Cubes XFCk(n) Vk (n) 0 || Vk (n 1) 10 || Vk (n 2) n k 4 k Vk (k 2) {0, 1} Vk (k 3) {0, 1}k 1 Edge: Hamming distance = 1 20/1/31

10 Introduction 1. Fibonacci-class cubes: XFC example 3. Extended Fibonacci Cubes XFCk(n) 20/1/31 11 Introduction 1. Fibonacci-class cubes: summary

In sum: FCn : Vn 0 || Vn 1 10 || Vn 2 EFCn : Vn 00 || Vn 2 10 || Vn 2 0100 || Vn 4 0101|| Vn 4 n 5 n 7 XFCk n : Vk (n) 0 || Vk (n 1) 10 || Vk (n 2) n k 4

Edge: Hamming distance = 1 20/1/31 12 Introduction 2. General Property Proposition. In a fault-free Fibonacci Cube, Enhanced Fibonacci Cube or Extended Fibonacci Cube: there is always a preferred dimension available at the packets present node before the destination is

reached. Implication: the use of a spare dimension can be boiled down to the encounter of faulty components (now or before). 20/1/31 13 Road Map Introduction Generic approach to cycle-free routing (GACR) Fault-tolerant Fibonacci routing (FTFR)

Experimental results Conclusion and future work 20/1/31 14 Generic approach to cycle-free routing (GACR) Purpose: 1. avoid cycles in routing by checking the traversal history 2. generality and efficiency

20/1/31 15 Generic approach to cycle-free routing: history vector history: 1210121 20/1/31 16

Generic approach to cycle-free routing: cycle check Equivalent condition for a route to contain cycle: there exists a way of inserting ( and ) into the sequence such that each number in the parenthesis appears for an even number of times. 875865632434121 a 875865632434(121 2) 875865(632434121 6) 875865632434121 4 20/1/31 17

Generic approach to cycle-free routing: Cost Cost: Overhead length: O(Lmax log n) = O(n log n) if O(Lmax) = O(n) Time complexity: To check whether string s has a single 1: O(1) To find all forbidden dimensions: O(Lcur) = O(n) 20/1/31 18

Road Map Introduction Generic approach to cycle-free routing (GACR) Fault-tolerant Fibonacci routing (FTFR) Experimental results Conclusion and future work 20/1/31 19

Fault-tolerant Fibonacci routing: Auxiliary vectors The main framework of the algorithm Auxiliary vectors First filter out following dimensions All the dimensions that are masked by GACR, including the incoming dimension Dimensions which are faulty or non-existent by the definition of Fibonacci-class cubes (this makes the algorithm applicable to all Fibonacci-class cubes) Setting a mask vector, M, with 0 for dimensions meeting either of the conditions above, and 1 otherwise (adoptable).

20/1/31 20 Fault-tolerant Fibonacci routing: Overview 20/1/31 21 Fault-tolerant Fibonacci routing: Choosing from preferred dimensions

If there are adoptable preferred dimensions Look at neighbors on these dimensions Pick the neighbor which has the largest number of preferred dimension (relative to the neighbor) If tie, then pick the neighbor with the largest number of spare dimensions If still tie, choose 0->1 dimension 20/1/31 22 Fault-tolerant Fibonacci routing:

Choosing from spare dimensions If there is NO adoptable preferred dimension Look at neighbors on spare dimensions Pick the neighbor which has the largest number of preferred dimension If tie, then pick the neighbor with the largest number of spare dimensions If still tie, choose 1->1 dimension 20/1/31 23

Fault-tolerant Fibonacci routing: control of using spare dimension One caveat, control of using spare dimension All dimensions can be used as a spare dimension for at most once This is attained by using a mask vector DT: 20/1/31 Set DT to straight 1 at the start/source. If one spare dimension is chosen to be used Check if the corresponding bit in DT is 1 If 1, then OK. If 0, then forbid using it and try

other dimensions. After using the dimension, set the corresponding bit in DT to 0 24 Fault-tolerant Fibonacci routing: speed up two heuristics: If the neighbor is the destination, then go to it. If the neighbor is on dimension d, and the destination has a (imagined) link on dimension d, then add the network availability to the score

# prefer n # spare node _ availability 20/1/31 25 Road Map Introduction Generic approach to cycle-free routing (GACR) Fault-tolerant Fibonacci routing (FTFR) Experimental results Conclusion and future work

20/1/31 26 Experimental Results Check false abortion enumerated all possible locations of faulty components and (source, destination) pairs for three kinds of Fibonacci-class Cubes with dimensionality lower than 7. No false abortion occurs. For higher dimensional cases, we can only

randomly set faults and pick (source, destination) pairs. After one months simulation on a 2.3 GHz CPU, still no false abortion occurs. 20/1/31 27 Experimental Results Experimental settings location of faults, source and destination are all randomly chosen by uniform distribution a node is faulty when all of its incident links are faulty

fixed packet-sized messages source and destination nodes must be non-faulty eager readership is employed when packet service rate is faster than packet arrival rate 20/1/31 28 Experimental Results Comparison on various network sizes 20/1/31

29 Experimental Results Comparison on various numbers of faults 20/1/31 30 Experimental Results Comparison on various numbers of faults 20/1/31

31 Road Map Introduction Generic approach to cycle-free routing (GACR) Fault-tolerant Fibonacci routing (FTFR) Experimental results Conclusion and future work 20/1/31

32 Conclusion and future work Applicable to all Fibonacci-class cubes in a unified fashion. Although the Fibonacci-class cubes may be very sparsely connected, the algorithm can tolerate as many faulty components as the network node availability. The space and computation complexity as well as message overhead size are all moderate. Future: increase the number of faulty components tolerable, physical implementation.

20/1/31 33 Thank you ! Questions are welcomed. 20/1/31 34