Gossiping Project
This page gives a description of a programming project under the
direction of Jop Sibeyn. Please first have a look at the description
of the
gossiping problem.
The task is to animate the series of actions that is taking place:
-
The program should have a user interface that allows to create
a network. This is easy, java has standard routines for this.
-
The network must be rearranged such that it can be nicely drawn.
A condition is that the nodes are positioned in contiguous grid
positions, the best is a rectangle with at most one missing
corner. The search for the lay-out should improve on the one
given by the user, not completely discard it. One may choose a
standard program and adapt it for the special requirement or
write something new.
-
The exisiting heuristic for computing gossiping schedules is
applied to the input graph and the schedule is computed, including
a specification of which packets are transferred in each of the
steps. Possibly for the mostly small graphs under consideration
the heuristic can be further improved.
-
The computed schedule is shown in an appealing way. Either user
controlled or free running, the schedule is demonstrated round
by round and step by step. The edges that are selected in a round
are drawn bald in red. At the beginning of a step, the packets that
are copied and then transferred are flashing for a second before
they start their way over the connections to their destinations.
-
A histogram shows status parameters for the round: one bar for
each of the steps showing the number of transferred packets,
together with the average cost per transferred packet. A second
histogram gives an overview of the rounds: for each round a bar
with the number of transferred packets together with the average
cost per transferred packet.
-
There should be a module that allows to save and print the
situations at the beginning of each round after the edges have
been selected.
Actually step 3 and step 4 are interleaved: the heuristic computes
a round, then shows it, and so on. The program should also allow
the user to prescribe a matching, overruling the suggestion of the
heuristic. In this way the program becomes a tool for the
development of gossiping schedules. The precise order is
thus: the program suggests a matching, the ruler either confirms or
modifies it, the program suggests the number of steps it wants to
perform, the user either confirms or modifies it, the program suggests
a selection of packets to transfer, the user either confirms or
modifies it. There should be two back-buttons for going back stepwise
or roundwise.
The static gossiping pattern can be replaced by a dynamic
situation in which every now and then a new broadcasting task is given
to a node (for sake of the representation we impose that this can
happen only after a previous task for this node has finished).
This page was created by Jop Sibeyn.
Last update Tuesday, 16 April 02 - 11:28.
