Welcome [www.cs.uic.edu]

Welcome [www.cs.uic.edu]

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

Recently Viewed Presentations

  • Clashes and Collisions - an introduction to your poetry cluster.

    Clashes and Collisions - an introduction to your poetry cluster.

    Kamikaze. Objectives: To explore the poem Kamikaze focusing on how Garland has used poetic devices to portray the theme of power and conflict. To use MITSL to develop a response to the poem
  • Part One - CPIN

    Part One - CPIN

    When taking an in-depth look at a domain, one needs to keep in mind that, for young children, learning is a very integrated experience. The purpose of the foundations is to promote understanding of preschool children's learning and to guide...
  • mcgill.ca

    mcgill.ca

    Presumed fault = reversed burden of proof on the Defendant that there was no lack of maintenance of public utilities (CAA Versailles, 5 Feb. 2015, No14VE01553)
  • Chapter 1 - The Internet Has Arrived

    Chapter 1 - The Internet Has Arrived

    Chapter 8 - Internet: The Early Years The Desirability Of A Single Network The Department Of Defense Had Multiple Networks Connecting Disconnected Machines The Internet Emerges ARPA funded research to investigate ways to solve the problem of incompatible networks.
  • PHYSICAL AGING - Los Angeles Mission College

    PHYSICAL AGING - Los Angeles Mission College

    Goals of Biomechanics of Physical Activity To understand how basic laws of mechanical physics and engineering affect and shape the structure and function of the human body Mechanics: a branch of physics that documents motion (kinematics) and the causes of...
  • T-sql

    T-sql

    Jes Borland . Premier Field Engineer, Data & AI . Goals . Learn how SQL Server interprets queries . Learn strategies for making queries faster and less resource-intensive using T-SQL . Learn about aggregations, window functions, subqueries, views, and functions...
  • Teaching Senior-Level Instrumental Analysis Using QuickTime Movies and

    Teaching Senior-Level Instrumental Analysis Using QuickTime Movies and

    Teaching Senior-Level Instrumental Analysis Using QuickTime Movies and Flash Animations Tom Chasteen, Department of Chemistry Sam Houston State University
  • NCATE 2010 Update - Kean University

    NCATE 2010 Update - Kean University

    Philosophical statement rubric Contextual factors rubric Introduction to the TWS Portfolio rubric Writing Mechanics and Organization Rubrics EC 3300 EMSE 3123* EMSE 3210 EMSE 3220 EMSE 3230 EMSE 3240 EMSE 3250 EMSE 3410, 3403 (Bilingual or TESL) FA 3900 MUS...