On hardware for generating routes in Kautz graphs

Gerard J.M. Smit, Paul J.M. Havinga, Pierre G. Jansen, Fokke de Boer, Bert Molenkamp

    Research output: Contribution to journalConference articleAcademicpeer-review

    1 Citation (Scopus)
    134 Downloads (Pure)


    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 languageEnglish
    Pages (from-to)593-600
    Number of pages8
    JournalMicroprocessing and Microprogramming
    Issue number1-5
    Publication statusPublished - Aug 1991
    EventEuromicro Conference on Hardware and Software Design Automation 1991 - Vienna, Austria
    Duration: 2 Sept 19915 Sept 1991


    • Interconnection networks
    • Kautz graphs
    • Routing algorithms
    • Routing hardware
    • VHDL


    Dive into the research topics of 'On hardware for generating routes in Kautz graphs'. Together they form a unique fingerprint.

    Cite this