Configuring Protection Routing via Completely Independent Spanning Trees in Dense Gaussian On-Chip Networks
Kung-Jui Pai, Jinn‐Shyong Yang, Guanyu Chen, Jou–Ming Chang
Abstract
Dense Gaussian networks (DGNs) are suitable topology candidates for network-on-chip (NoC) architectures because they provide favorable network properties such as symmetry, regularity, lower diameter, and shorter average hop distance. In particular, DGNs can accommodate more nodes in the same chip area compared with other grid-like structures. A set of spanning trees in the underlying graph of a network is called completely independent spanning trees (CISTs for short) if, for each pair of vertices <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$x$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$y$</tex-math></inline-formula> in the graph, the paths joining <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$x$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$y$</tex-math></inline-formula> in any two spanning trees have neither vertex nor edge in common, except for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$x$</tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$y$</tex-math></inline-formula> . Although the problem of determining whether a graph admits a dual-CIST (i.e., two CISTs) is NP-complete, the existence of multiple CISTs in a network has applications in fault-tolerant routing and secure message distribution. A recent result showed that a network possessing a dual-CIST suffices to configure a protection routing. A protection routing is a multi-path routing scheme for integrating route discovery and route maintenance mechanisms such that there is a loop-free alternate path for packet forwarding when a single link or node failure occurs. Accordingly, this paper develops linear-time algorithms for constructing a dual-CIST in DGNs. Furthermore, we provide simulation results to evaluate the performance of the efficiency of protection routing in DGNs.