Paper Info
Title
An improved fault-tolerant routing algorithm for a Network-on-Chip derived with formal analysis
Abstract
A fault-tolerant routing algorithm in Network-on-Chip (NoC) architectures provides adaptivity for on-chip communications. Adding fault-tolerance adaptivity to a routing algorithm increases its design complexity and makes it prone to deadlock and other problems if improperly implemented. Formal verification techniques are needed to check the correctness of the design. This paper describes the discovery of a potential livelock problem through formal analysis on an extension of the link-fault tolerant NoC architecture introduced by Wu et al. In the process of eliminating this problem, an improved routing architecture is derived. The improvement simplifies the routing architecture, enabling successful verification using the CADP verification toolbox. The routing algorithm is proven to have several desirable properties including deadlock and livelock freedom, and tolerance to a single-link-fault. Redundant fault-tolerance causes livelocks in the presence of multiple faults.Avoiding multiple diversions removes livelocks on the NoC architecture.Deadlock and livelock freedom is formally verified on the improved NoC architecture.Single link-fault tolerance and packet delivery are verified.
Year
DOI
Venue
2016
10.1016/j.scico.2016.01.002
Science of Computer Programming
Keywords
Field
DocType
Fault-tolerant routing,Formal methods,Model checking,Network-on-chip,Process calculus
Link-state routing protocol,Multipath routing,Triangular routing,Static routing,Computer science,Enhanced Interior Gateway Routing Protocol,Routing domain,Theoretical computer science,Distance-vector routing protocol,Distributed computing,Routing protocol
Journal
Volume
Issue
ISSN
118
C
0167-6423
Citations 
PageRank 
References 
2
0.39
28
Authors
6
Name
Order
Citations
PageRank
Zhen Zhang117311.04
Wendelin Serwe241122.55
Jian Wu320.39
Tomohiro Yoneda435341.62
Hao Zheng59513.32
Chris J. Myers660775.73