next up previous
Next: Diagnosing a Disconnect Up: Example: A Simple Line Previous: Example: A Simple Line

Monitoring the Line Segment

The main idea behind our monitoring algorithm is to establish a periodic wave that only runs on labelled procesors. If the connectivity of intermediate processors is broken, the wave algorithm will be unable to progress, thereby alerting processors that a problem exists.

We may also express this idea from an algorithmic point of view:

1.
Endpoint b broadcasts a message to its neighbors with an argument counter initially set to 0.
2.
Processors labelled with A-material rebroadcast this message to their neighbors, without changing the argument value. In addition, a timestamp of the message arrival is stored.
3.
When the other endpoint receives the message, it increments the argument modulo 4 and broadcasts the message.
4.
Processors labelled with A-material rebroadcast the incremented message to their neighbors, and record the interval of time between messages.
5.
Repeat 3 and 4.

Intermediate processors can estimate the amount of time they should wait before deciding that the segment is disconnected. The counter allows the intermediate processors to determine whether they have heard the message before, or if they are receiving new information. Furthermore by looking at the parity of the argument, each processor knows which direction the wave came from.


next up previous
Next: Diagnosing a Disconnect Up: Example: A Simple Line Previous: Example: A Simple Line
Jeremy Zucker
2000-06-10