Next: Diagnosing a Disconnect
Up: Example: A Simple Line
Previous: Example: A Simple Line
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: Diagnosing a Disconnect
Up: Example: A Simple Line
Previous: Example: A Simple Line
Jeremy Zucker
2000-06-10