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

Preview

PDF
653Kb

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:	Computer Architecture for Embedded Systems (CAES) Pervasive Systems (PS)
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