Broascasting in de Bruijn networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Congressus Numerantium Année : 1988

Broascasting in de Bruijn networks

Résumé

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of a network. To broadcast time of a vertex is the minimim number ot time units required to complete broadcasting from this vertex. Several previous papers have investigated methods to construct sparse networks in which this process can be completed in minimim time from any originator. But the graphs produced by these methods contain high degree vertices. If these graphs are to used in the design of actual communication networks (for example for parallel computers) other considerations can override the need for minimum broadcasting time. So we are interested in networks with a fixed maximum degree, in which every vertex can broadcast quickly. Here, we study the broadcasting time of the Bruijn and Kautz networks (which are among the best known families of interconnection networks for given degree and diameter). These networks have a simple broadcasting scheme and for small degree they have a very good broadcasting time of order log n. For example for maximum degree 4, we obtain networks on 2b or 2D + 2D-1 vertices, with broadcasting time at most 1.5 D, improving on carlier results.
Fichier principal
Vignette du fichier
79-BePe88.pdf (2.13 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03013393 , version 1 (18-11-2020)

Identifiants

  • HAL Id : hal-03013393 , version 1

Citer

Jean-Claude Bermond, Claudine Peyrat. Broascasting in de Bruijn networks. Congressus Numerantium, 1988, 66, pp.283-292. ⟨hal-03013393⟩
109 Consultations
20 Téléchargements

Partager

Gmail Facebook X LinkedIn More