Periodic Gossiping in Commuted Networks |
| |
Authors: | Email author" target="_blank">Dominique?BarthEmail author Email author" target="_blank">Pascal?BerthoméEmail author |
| |
Affiliation: | (1) Laboratoire PRiSM, Université Versailles Saint-Quentin, 45 av. des États-Unis, 78035 Versailles Cedex, France;(2) Laboratoire de Recherche en Informatique, UMR CNRS 8623, Bât. 490, Centre d Orsay, Université Paris-Sud, 91405 Orsay, France |
| |
Abstract: | In this paper we deal with global communication schemes such as broadcasting
or multicasting, in a packet (sub)network in which each node participates
in the same distributed application. We want the communication scheme to be performed
periodically as often as possible and with some bandwidth guarantee. Such
periodicity properties are needed, for example, by multimedia and grid computation
applications. We consider commuted switches in the network, i.e., each outgoing
link of the switch is assigned to at most one incoming link. Each switch avoids intermediate
buffering. Given a network G and a global communication scheme S, an
algorithm performing S in G consists in commuting each switch and in specifying
to each emitting node the infinite sequence of steps at which it will send a message.
The period of this algorithm is the greatest number of steps between two messages
emitted by a node. The window of the algorithm is the maximal number of steps
needed by a message to reach its destination(s).
We first give a general definition of the model of network we consider and of the
global communication schemes we study, i.e., the many-to-all scheme where many
nodes have one message to send to all the other ones. One well-known case of the
many-to-all scheme we especially focus on is gossiping. We present a general way
of periodically performing these communication schemes, by covering the graph by
substructures called octopuses. Then we show that optimizing the period and the
windoware two different problems.We end by giving some examples of applications
in the torus network. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|