2022/03/18 by Josep M. Fàbrega, Josep Fàbrega, Jaume Martí-Farré +5
Computer Science · Mathematics · #05C20 #94C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Network Packet Processing and Optimization #math.CO #msc:05C20 #msc:94C15
paper · pdf · doi:10.48550/arxiv.2203.09918
31 pages
arxiv created 2022/03/18 · openalex publication_date 2022/03/18 · arxiv updated 2022/03/21 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28
In this paper, we present a detailed study of the reach distance-layer structure of the De Bruijn and Kautz digraphs, and we apply our analysis to the performance evaluation of deflection routing in De Bruijn and Kautz networks. Concerning the distance-layer structure, we provide explicit polynomial expressions, in terms of the degree of the digraph, for the cardinalities of some relevant sets of this structure. Regarding the application to defection routing, and as a consequence of our polynomial description of the distance-layer structure, we formulate explicit rational expressions, in terms of the degree of the digraph, for some probabilities of interest in the analysis of this type of routing. De Bruijn and Kautz digraphs are fundamental examples of digraphs on alphabet and iterated line digraphs. If the topology of the network under consideration corresponds to a digraph of this type, we can perform, in principle, a similar vertex layer description.