Symmetric flows and broadcasting in hypercubes

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

Annales de l'institut Fourier (1999)

  • Volume: 49, Issue: 3, page 787-807
  • ISSN: 0373-0956

Abstract

top
In this paper, we propose a method which enables to construct almost optimal broadcast schemes on an n -dimensional hypercube in the circuit switched, Δ -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.

How to cite

top

Bermond, Jean-Claude, et al. "Symmetric flows and broadcasting in hypercubes." Annales de l'institut Fourier 49.3 (1999): 787-807. <http://eudml.org/doc/75363>.

@article{Bermond1999,
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.},
author = {Bermond, Jean-Claude, Bonnecaze, A., Kodate, T., Pérennes, Stéphane, Solé, Patrick},
journal = {Annales de l'institut Fourier},
keywords = {circuit switched model; broadcasting; hypercube; connectivity; (symmetric) flow networks; error correcting codes},
language = {eng},
number = {3},
pages = {787-807},
publisher = {Association des Annales de l'Institut Fourier},
title = {Symmetric flows and broadcasting in hypercubes},
url = {http://eudml.org/doc/75363},
volume = {49},
year = {1999},
}

TY - JOUR
AU - Bermond, Jean-Claude
AU - Bonnecaze, A.
AU - Kodate, T.
AU - Pérennes, Stéphane
AU - Solé, Patrick
TI - Symmetric flows and broadcasting in hypercubes
JO - Annales de l'institut Fourier
PY - 1999
PB - Association des Annales de l'Institut Fourier
VL - 49
IS - 3
SP - 787
EP - 807
AB - 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.
LA - eng
KW - circuit switched model; broadcasting; hypercube; connectivity; (symmetric) flow networks; error correcting codes
UR - http://eudml.org/doc/75363
ER -

References

top
  1. [1] C. BERGE, Graphes et hypergraphes, Dunod, Paris, 1970. Zbl0213.25702MR50 #9641
  2. [2] N. BIGGS, Algebraic Graph Theory, Cambridge University Press, 1974. Zbl0284.05101MR50 #151
  3. [3] J.A. BONDY, U.S.R. MURTY, Graph theory with applications, McMillan Press, 1976. Zbl1226.05083
  4. [4] A.E. BROUWER, A.M. COHEN, A. NEUMAIER, Distance regular graphs, Springer Verlag, 1989. Zbl0747.05073MR90e:05001
  5. [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. [6] O. DELMAS, Communications par commutation de circuits dans les réseaux d'interconnexion, Thèse, Université de Nice, Sophia Antipolis, 1997. 
  7. [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. [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. [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. [10] P. FRAIGNIAUD, E. LAZARD, Methods and problems of communication in usual networks, Discrete Applied Math., 53 (1994), 79-133. Zbl0818.94029MR95f:68015
  11. [11] C.D. GODSIL, Connectivity of minimal Cayley graphs, Arch. Math., 37 (1981), 437-476. Zbl0476.05049MR83a:05089
  12. [12] A.V. GOLDBERG, R.E. TARJAN, A new approach to the maximum flow problem, J. ACM, 35 (1988), 921-940. Zbl0661.90031MR92c:90050
  13. [13] G. HAHN, G. SABIDUSSI, Graph symmetry, Nato ASI Series, vol. 497, Kluwer Academic Publishers, 1996. Zbl0868.00039
  14. [14] Y.O. HAMIDOUNE, Quelques problèmes de connexité dans les graphes orientés, Thèse, Université Pierre et Marie Curie, Paris VII, 1978. Zbl0475.05039
  15. [15] Y.O. HAMIDOUNE, On the connectivity of Cayley digraphs, Eur. J. Comb., 5 (1984), 309-312. Zbl0561.05028MR86d:05053
  16. [16] S.M. HEDETNIEMI, S.T. HEDETNIEMI, A.L. LIESTMAN, A survey of gossiping and broadcasting in communication networks, Networks, 18 (1988), 319-349. Zbl0649.90047MR89h:90087
  17. [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. [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. Zbl0840.68088
  19. [19] T. KODATE, Communications structurées dans les réseaux d'interconnection, Thèse, Université de Nice-Sophia Antipolis, 1996. 
  20. [20] F.J. MACWILLIAMS, N.J.A. SLOANE, The Theory of Error-Correcting Codes, North-Holland, 1977. Zbl0369.94008
  21. [21] W. MADER, K minimal n-fach kantensuzammenhangenden, Math. Annal., 191 (1971), 21-28. Zbl0198.29202
  22. [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. [23] J.G. PETERS, M. SYSKA, Circuit switched broadcasting in torus networks, IEEE Transactions on Parallel and Distributed Processing, 7 (3) (1996), 246-255. Zbl0851.90041
  24. [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. [25] J. DE RUMEUR, Communication dans les réseaux de processeurs, Masson, Paris, 1994. 
  26. [26] J.H. VAN LINT, Introduction to Coding Theory, Springer Verlag, Berlin, 1982. Zbl0485.94015MR84e:94001
  27. [27] M.E. WATKINS, Connectibity of transitive graphs, J. Comb. Theory, 8 (1970), 23-29. Zbl0185.51702MR42 #1707

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.