On hardware for generating routes in Kautz digraphs

Share/Save/Bookmark

Smit, Gerard J.M. and Havinga, Paul J.M. and Jansen, Pierre G. and Boer, F. de and Molenkamp, Bert (1991) On hardware for generating routes in Kautz digraphs. Microprocessing and Microprogramming, 32 (1-5). pp. 593-599. ISSN 0165-6074

open access
[img]
Preview
PDF
669kB
Abstract:In this paper we present a hardware implementation of an algorithm for generating node disjoint routes in a Kautz network. Kautz networks are based on a family of digraphs described by W.H. Kautz[Kautz 68]. A Kautz network with in-degree and out-degree d has N = dk + dk¿1 nodes (for any cardinals d, k>0). The diameter is at most k, the degree is fixed and independent of the network size. Moreover, it is fault-tolerant, the connectivity is d and the mapping of standard computation graphs such as a linear array, a ring and a tree on a Kautz network is straightforward.
The network has a simple routing mechanism, even when nodes or links are faulty. Imase et al. [Imase 86] showed the existence of d node disjoint paths between any pair of vertices. In Smit et al. [Smit 91] an algorithm is described that generates d node disjoint routes between two arbitrary nodes in the network. In this paper we present a simple and fast hardware implementation of this algorithm. It can be realized with standard components (Field Programmable Gate Arrays).
Item Type:Article
Copyright:© 1991 Elsevier Science
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/57554
Official URL:http://dx.doi.org/10.1016/0165-6074(91)90407-K
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 119229