×

Symmetric flows and broadcasting in hypercubes. (English) Zbl 0928.68133

Summary: 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.

MSC:

68W10 Parallel algorithms in computer science
90B18 Communication networks in operations research
94B05 Linear codes (general theory)
05E20 Group actions on designs, etc. (MSC2000)
90B10 Deterministic network models in operations research
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] [1] , Graphes et hypergraphes, Dunod, Paris, 1970. · Zbl 0213.25702
[2] [2] , Algebraic Graph Theory, Cambridge University Press, 1974. · Zbl 0284.05101
[3] [3] , , Graph theory with applications, McMillan Press, 1976. · Zbl 1226.05083
[4] [4] , , , Distance regular graphs, Springer Verlag, 1989. · Zbl 0747.05073
[5] [5] , , , Gossiping in torus with wormhole-like routing, in Proceedings of the 7-th IEEE Symposium on Parallel and Distributed Processing, San-Antonio, 1995.
[6] [17] , , Quantum Mechanics and Path Integrals, McGraw-Hill, New-York, 1965 · Zbl 0176.54902
[7] [7] , , 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] [8] , , 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] [9] , Communication, routage et architectures des machines à mémoires distribuées — autour du routage wormhole, Thèse, École normale supérieure de Lyon, 1996.
[10] [10] , , Methods and problems of communication in usual networks, Discrete Applied Math., 53 (1994), 79-133. · Zbl 0818.94029
[11] [11] , Connectivity of minimal Cayley graphs, Arch. Math., 37 (1981), 437-476. · Zbl 0476.05049
[12] [12] , , A new approach to the maximum flow problem, J. ACM, 35 (1988), 921-940. · Zbl 0661.90031
[13] [13] , , Graph symmetry, Nato ASI Series, vol. 497, Kluwer Academic Publishers, 1996. · Zbl 0868.00039
[14] [14] , Quelques problèmes de connexité dans les graphes orientés, Thèse, Université Pierre et Marie Curie, Paris VII, 1978. · Zbl 0475.05039
[15] [15] , On the connectivity of Cayley digraphs, Eur. J. Comb., 5 (1984), 309-312. · Zbl 0561.05028
[16] [16] , , , A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988), 319-349. · Zbl 0649.90047
[17] [17] , , Optimal broadcast in all-port wormhole-routed hypercubes, IEEE Transactions on Parallel and Distributed Systems, 6 (2) (1995), 200-204.
[18] [18] , , , , 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.0369.94008 · Zbl 0369.94008
[21] W. MADER, K minimal n-fach kantensuzammenhangenden, Math. Annal., 191 (1971), 21-28.0198.29202 · 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.0851.90041 · Zbl 0851.90041
[24] [24] , , , , 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] [26] , Introduction to Coding Theory, Springer Verlag, Berlin, 1982. · Zbl 0485.94015
[27] [27] , Connectibity of transitive graphs, J. Comb. Theory, 8 (1970), 23-29. · Zbl 0185.51702
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.