Symmetric flows and broadcasting in hypercubes

Bermond, Jean-Claude ; Bonnecaze, A. ; Kodate, T. ; Pérennes, Stéphane ; Solé, Patrick

Annales de l'Institut Fourier, Tome 49 (1999), p. 787-807 / Harvested from Numdam

Résumé

Dans cet article nous proposons une méthode pour construire des protocoles de diffusion quasi optimaux dans l’hypercube, ceci dans le modèle commutation de circuits et diffusion simultanée sur tous les ports. Dans ce modèle un sommet initiateur doit informer tous les autres nœuds du réseau en un minimum d’étapes. Durant une étape les communications ont lieu via des chemins arc-disjoints Notre construction utilise des séquences de codes binaires emboîtés les uns dans les autres avec la propriété que les sommets de chaque code peuvent informer ceux du code suivant en une étape. Cette dernière condition est assurée à l’aide d’outils venant de la théorie des flots en particulier des flots symétriques. Nous appliquons la méthode pour concevoir des protocoles optimaux ou quasi optimaux améliorant ainsi les résultats précédemment connus.

Abstract

In this paper, we propose a method which enables to construct almost optimal broadcast schemes on an $n$-dimensional hypercube in the circuit switched, $\Delta $-port model. In this model, an initiator must inform all the nodes of the network in a sequence of rounds. During a round, vertices communicate along arc-disjoint dipaths. Our construction is based on particular sequences of nested binary codes having the property that each code can inform the next one in a single round. This last property is insured by a flow technique and results about symmetric flow networks. We apply the method to design optimal schemes improving and generalizing the previous results.

Détail

Publié le : 1999-01-01

MR 2000g:90014 | Zbl 0928.68133

DOI : https://doi.org/10.5802/aif.1692

Bibliographie

[1] C. Berge, Graphes et hypergraphes, Dunod, Paris, 1970. | MR 50 #9641 | Zbl 0213.25702

[2] N. Biggs, Algebraic Graph Theory, Cambridge University Press, 1974. | MR 50 #151 | Zbl 0284.05101

[3] J.A. Bondy, U.S.R. Murty, Graph theory with applications, McMillan Press, 1976.

[4] A.E. Brouwer, A.M. Cohen, A. Neumaier, Distance regular graphs, Springer Verlag, 1989. | MR 90e:05001 | Zbl 0747.05073

[5] C. Calvin, S. Pérennes, D. Trystram, Gossiping in torus with wormhole-like routing, in Proceedings of the 7-th IEEE Symposium on Parallel and Distributed Processing, San-Antonio, 1995.

[6] O. Delmas, Communications par commutation de circuits dans les réseaux d'interconnexion, Thèse, Université de Nice, Sophia Antipolis, 1997.

[7] O. Delmas, S. Pérennes, Diffusion par commutation de circuits dans les tores de dimension k/Circuit switched broadcasting in the k-th dimentional torus networks, Technique et science informatique, RAIRO, AFCET, 16 (5) (1997), 563-581.

[8] O. Delmas, S. Pérennes, Circuit-Switched Gossiping in 3-Dimentional Torus Networks, in Proceedings of the Euro-Par'96 Parallel Processing, Second International EURO-PAR Conference, Lyon, Lecture Notes in Computer Science, Springer Verlag, vol. 1123, 1996, 370-373.

[9] E. Fleury, Communication, routage et architectures des machines à mémoires distribuées — autour du routage wormhole, Thèse, École normale supérieure de Lyon, 1996.

[10] P. Fraigniaud, E. Lazard, Methods and problems of communication in usual networks, Discrete Applied Math., 53 (1994), 79-133. | MR 95f:68015 | Zbl 0818.94029

[11] C.D. Godsil, Connectivity of minimal Cayley graphs, Arch. Math., 37 (1981), 437-476. | MR 83a:05089 | Zbl 0476.05049

[12] A.V. Goldberg, R.E. Tarjan, A new approach to the maximum flow problem, J. ACM, 35 (1988), 921-940. | MR 92c:90050 | Zbl 0661.90031

[13] G. Hahn, G. Sabidussi, Graph symmetry, Nato ASI Series, vol. 497, Kluwer Academic Publishers, 1996. | Zbl 0868.00039

[14] Y.O. Hamidoune, Quelques problèmes de connexité dans les graphes orientés, Thèse, Université Pierre et Marie Curie, Paris VII, 1978. | Zbl 0475.05039

[15] Y.O. Hamidoune, On the connectivity of Cayley digraphs, Eur. J. Comb., 5 (1984), 309-312. | MR 86d:05053 | Zbl 0561.05028

[16] S.M. Hedetniemi, S.T. Hedetniemi, A.L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988), 319-349. | MR 89h:90087 | Zbl 0649.90047

[17] C.-T. Ho, M.-Y. Kao, Optimal broadcast in all-port wormhole-routed hypercubes, IEEE Transactions on Parallel and Distributed Systems, 6 (2) (1995), 200-204.

[18] J. Hromkovic, R. Klasing, B. Monien, R. Peine, Combinatorial Network Theory, Chap. 'Dissemination of information in interconnecting networks (Broad-casting and Gossiping)', 125-212, Kluwer Academic Publishers, 1995. | Zbl 0840.68088

[19] T. Kodate, Communications structurées dans les réseaux d'interconnection, Thèse, Université de Nice-Sophia Antipolis, 1996.

[20] F.J. Macwilliams, N.J.A. Sloane, The Theory of Error-Correcting Codes, North-Holland, 1977. | Zbl 0369.94008

[21] W. Mader, K minimal n-fach kantensuzammenhangenden, Math. Annal., 191 (1971), 21-28. | Zbl 0198.29202

[22] P.K. Mickinley, C. Trefftz, Efficient broadcast in all-port wormhole-routed hypercubes, in 'International Conference on Parallel Processing (ICPP'98)', vol. II, St. Charles, IL, USA, 1993.

[23] J.G. Peters, M. Syska, Circuit switched broadcasting in torus networks, IEEE Transactions on Parallel and Distributed Processing, 7 (3) (1996), 246-255. | Zbl 0851.90041

[24] D.F. Robinson, D. Judd, P.K. Mickinley, B.H.C. Cheng, Effective collective data distribution in all-port wormhole-routed hypercubes, in 'Proceedings Supercomputing'93', 1993, 792-780.

[25] J. De Rumeur, Communication dans les réseaux de processeurs, Masson, Paris, 1994.

[26] J.H. Van Lint, Introduction to Coding Theory, Springer Verlag, Berlin, 1982. | MR 84e:94001 | Zbl 0485.94015

[27] M.E. Watkins, Connectibity of transitive graphs, J. Comb. Theory, 8 (1970), 23-29. | MR 42 #1707 | Zbl 0185.51702