Title :
An algorithm for generating node disjoint routes in Kautz digraphs
Author :
Smit, Gerard J M ; Havinga, Paul J M ; Jansen, Pierre G.
Author_Institution :
Dept. of Comput. Sci., Twente Univ., Enschede, Netherlands
fDate :
30 Apr-2 May 1991
Abstract :
The authors focus on a particular class of interconnection networks: Kautz networks. These networks have nice properties: a network with degree d and N=dk+dk-1 nodes (for any cardinal d, k>0), has a diameter of at most dlog N, the degree d is fixed and independent of the network size. The network is fault-tolerant and the connectivity is d. There is a straightforward mapping from standard computation graphs such as a linear array, a ring and a tree to a Kautz network. The network allows for a simple routing algorithm, even when nodes or links are faulty. There exists d node disjoint paths between any pair of vertices. The paper presents an algorithm to generate these node disjoint routes. The routes are delivered with increasing length and are free of loops. It proves that these routes are node disjoint and as short as possible
Keywords :
computational complexity; directed graphs; multiprocessor interconnection networks; parallel algorithms; Kautz digraphs; Kautz networks; cardinal; computation graphs; connectivity; fault-tolerant; interconnection networks; linear array; links; node disjoint paths; node disjoint routes; ring; routing algorithm; tree; vertices; Bidirectional control; Communication networks; Computer science; Fault tolerance; Graph theory; Hardware; Intelligent networks; Multiprocessor interconnection networks; Routing; Tree graphs;
Conference_Titel :
Parallel Processing Symposium, 1991. Proceedings., Fifth International
Conference_Location :
Anaheim, CA
Print_ISBN :
0-8186-9167-0
DOI :
10.1109/IPPS.1991.153763