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).
Original language | English |
---|---|
Pages (from-to) | 593-600 |
Number of pages | 8 |
Journal | Microprocessing and Microprogramming |
Volume | 32 |
Issue number | 1-5 |
DOIs | |
Publication status | Published - Aug 1991 |
Event | Euromicro Conference on Hardware and Software Design Automation 1991 - Vienna, Austria Duration: 2 Sept 1991 → 5 Sept 1991 |
Keywords
- Interconnection networks
- Kautz graphs
- Routing algorithms
- Routing hardware
- VHDL