On hardware for generating routes in Kautz digraphs
Smit, Gerard J.M. and Havinga, Paul J.M. and Jansen, Pierre G. and Boer de, F. and Molenkamp, Bert (1991) On hardware for generating routes in Kautz digraphs. Microprocessing and Microprogramming, 32 (1-5). pp. 593-599. ISSN 0165-6074
|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).
|Copyright:||© 1991 Elsevier Science|
Electrical Engineering, Mathematics and Computer Science (EEMCS)
|Link to this item:||http://purl.utwente.nl/publications/57554|
|Export this item as:||BibTeX|
Daily downloads in the past month
Monthly downloads in the past 12 months
Repository Staff Only: item control page
Metis ID: 119229