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) no. 3, pp. 787-807.

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.

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.

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

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

[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 | Zbl

[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 | Zbl

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

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

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

[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

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

[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 | Zbl

[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

[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

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

[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

[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 | Zbl

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