Top

Computing

Published in:

01-06-2015

A Light-weight fault-tolerant routing algorithm tolerating faulty links and routers

Authors: Masoumeh Ebrahimi, Masoud Daneshtalab

Published in: Computing | Issue 6/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Faults at either the link or router level may result in the failure of the system. Fault-tolerant routing algorithms attempt to tolerate faults by rerouting packets around the faulty region. This rerouting would be at the cost of significant performance loss. The proposed algorithm in this paper is able to tolerate both faulty routers and links with negligible impact on the performance. In fact, the proposed algorithm avoids taking unnecessary longer paths and the shortest paths are always taken as long as a path exists. On the other hand, fault-tolerant routing algorithms might be based on deterministic routing in which all packets use a single path between each pair of source and destination routers. Using deterministic routing, packets reach the destination in the same order they have been delivered from the source so that no reordering buffer is needed at the destination. For improving the performance, fault-tolerant algorithms might be based on adaptive routing in which packets are delivered through multiple paths to destinations. In this case, packets should be reordered at the destinations demanding reordering buffers. The proposed algorithm can be configured in both working modes, such that it can be based on deterministic or adaptive routing.

previous article System on chip failure rate assessment using the executable model of a system

next article TurboLock: increasing associativity of lock table in transactional memory

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Palesi M, Daneshtalab M (2014) Routing Algorithms in Networks-on-Chip. Springer, BerlinCrossRef

Ni LM, McKinley PK (1993) A survey of wormhole routing techniques in direct networks. Computer 26(2):62–76CrossRef

Daneshtalab M, Ebrahimi M, Liljeberg P, Plosila J, Tenhunen H (2010) A low-latency and memory-efficient On-chip network. In: proceedings of the Fourth ACM/IEEE international symposium on networks-on-Chip (NOCS), pp 99–106

Ebrahimi M, Daneshtalab M, Liljeberg P, Plosila J, Tenhunen H (2012) “CATRA- congestion aware trapezoid-based routing algorithm for on-chip networks”. In: Proceedings of the design, automation test in Europe conference exhibition (DATE), pp 320–325

Ebrahimi M, Daneshtalab M, Liljeberg P, Plosila J, Tenhunen H (2012) “LEAR - A low-weight and highly adaptive routing method for distributing congestions in On-chip networks”, In: Proceedings of 20th euromicro international conference on parallel, distributed and network-based processing (PDP), pp 520–524

Wang X, Mak T, Yingtao Jiang MY, Daneshtalab M, Palesi M (2013) On self-tuning networks-on-chip for dynamic network-flow dominance adaptation. In: proceedings of seventh IEEE/ACM international symposium on networks on chip (NoCS), pp 1–8

Daneshtalab M, Ebrahimi M, Liljeberg P, Plosila J, Tenhunen H (2013) A systematic reordering mechanism for on-chip networks using efficient congestion-aware method. J Syst Archit (JSA-elsevier), 59(4–5):213–222

Ebrahimi M, Daneshtalab M, Sreejesh NP, Liljeberg P, Tenhunen H (2009) Efficient network interface architecture for network-on-chips. In: proceedings of NORCHIP, pp 1–4

Fick D, DeOrio A, Hu J, Bertacco V, Blaauw D, Sylvester D (2009) Vicis: A reliable network for unreliable silicon. In: 46th ACM/IEEE design automation conference (DAC), pp 812–817

10.

Boppana RV, Chalasani S (1995) Fault-tolerant wormhole routing algorithms for mesh networks. IEEE Trans Comput 44(7):848–864CrossRefMATH

11.

Sui P-H, Wang S-D (1997) An improved algorithm for fault-tolerant wormhole routing in meshes. IEEE Trans Comput 46(9):1040–1042CrossRefMathSciNet

12.

Zhang Z, Greiner A, Taktak S (2008) A reconfigurable routing algorithm for a fault-tolerant 2D-mesh network-on-Chip. In: proceedings of 45th ACM/IEEE design automation conference (DAC), pp 441–446

13.

Valinataj M, Mohammadi S, Plosila J, Liljeberg P, Tenhunen H (2011) A reconfigurable and adaptive routing method for fault-tolerant mesh-based networks-on-chip. AEU - Int J Electron Commun 65(7):630–640CrossRef

14.

Wu J (2003) A fault-tolerant and deadlock-free routing protocol in 2D meshes based on odd–even turn model. IEEE Trans Comput 52(9):1154–1169CrossRef

15.

Chiu G-M (2000) The odd-even turn model for adaptive routing. In: IEEE transactions on parallel and distributed systems 11(7):729–738

16.

Tsai W-C, Zheng D-Y, Chen S-J, Hu Y-H (2011) A fault-tolerant NoC scheme using bidirectional channel. In: proceedings of 48th ACM/EDAC/IEEE design automation conference (DAC), pp 918–923

17.

Koibuchi M, Matsutani H, Amano H, Mark Pinkston T (2008) A Lightweight Fault-Tolerant Mechanism for Network-on-Chip. In: proceedings of the second ACM/IEEE international symposium on networks-on-Chip (NoCS), pp 13–22

18.

Ebrahimi M, Daneshtalab M, Plosila J, Tenhunen H (2012) MAFA: adaptive fault-tolerant routing algorithm for networks-on-chip”, In: proceedings of 15th euromicro conference on digital system design (DSD), pp 201–207

19.

Fick D, DeOrio A, Chen G, Bertacco V, Sylvester D, Blaauw D (2009) A highly resilient routing algorithm for fault-tolerant NoCs. In: proceedings of design, automation test in Europe conference exhibition (DATE), pp 21–26

20.

Ebrahimi M, Daneshtalab M, Plosila J, Farhad Mehdipour (2013) MD: minimal path-based fault-tolerant routing in on-chip networks”, In: proceedings of the IEEE/ACM 18th Asia and South Pacific design automation conference (ASP-DAC), pp 35–40

21.

Ebrahimi M, Daneshtalab M, Plosila J, Tenhunen H (2013) Minimal-path fault-tolerant approach using connection-retaining structure in networks-on-chip”, In: proceedings of 7th international symposium on networks-on-Chip (NOCS), pp 1–8

22.

Ebrahimi M, Daneshtalab M, Plosila J (2013) High performance fault-tolerant routing algorithm for NoC-based many-core systems”, In: proceedings of 21th IEEE euromicro conference on Parallel, Distributed and network-based computing (PDP), pp 463–469

23.

Glass CJ, Glass CJ, Ni LM, Ni LM (1992) Maximally fully adaptive routing in 2D Meshes. In: proceedings of international conference on parallel processing, pp 101–104

24.

Glass CJ, Ni LM (1992) “The Turn Model for Adaptive Routing”. In proceedings of the 19th, annual international symposium on computer architecture pp 278–287

25.

Wang ZL, Yang M, Jiang Y, Daneshtalab M, Mak T (2013) A low cost, high performance dynamic-programming-based adaptive power allocation scheme for many-core architectures in the dark silicon Era. In: proceedings of the 11th IEEE symposium on embedded systems for real-time multimedia (ESTImedia)

26.

Carabano J, Dios F, Daneshtalab M, Ebrahimi M (2013) An exploration of heterogeneous systems. In: 2013 8th international workshop on reconfigurable and communication-centric Systems-on-Chip (ReCoSoC), pp 1–7

Title: A Light-weight fault-tolerant routing algorithm tolerating faulty links and routers
Authors: Masoumeh Ebrahimi
Masoud Daneshtalab
Publication date: 01-06-2015
Publisher: Springer Vienna
Published in: Computing / Issue 6/2015
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-013-0362-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 6/2015

Energy reduction in 3D NoCs through communication optimization

Decentralized task scheduling for a fixed priority multicore embedded RTOS

System on chip failure rate assessment using the executable model of a system

Design and implementation of counting networks

Using constraint programming for the design of network-on-chip architectures

TurboLock: increasing associativity of lock table in transactional memory

Premium Partner