Information Technology Reference
In-Depth Information
4.3 Structured Topology Control
Frey and Murphy [Frey and Murphy, 2008] proposed a detailed mechanism
for maintaining a tree network architecture in the presence of peer churns.
Specifically, their proposed scheme can limit the maximum node degree, min-
imize the extent of tree topology changes resulting from peer dynamics, and
limit the number of nodes affected by each topology change. Figure 4.2 shows
a flow-chart of the topology control algorithm used by each peer whenever it
discovers that its parent has departed.
Detect Parent Departure
Determine
Candidate Parent
Not Found
Declare Self as Root
Send
PARENTREQUEST to
Candidate Parent
Update Caches
No
Request
Accepted?
Yes
Update Neighbor Set and
Cache
FIGURE 4.2: Algorithm for locating a new parent as a result of peer depar-
tures [Frey and Murphy, 2008].
As can be seen, the key step in the topology control algorithm is the
identification of a candidate parent. This parent selection step is achieved by
using the following strategies.
Regional Strategy. This topology control strategy is designed for repairing
the disruption in a localized manner. Specifically, each peer maintains a
cache of nearby (in a topological sense) peers, consisting of ancestors as
well as siblings. The cache contains a number of ancestor peers starting
from the parent continuing toward the root. The cache also contains
a set of siblings which are the other children of the parent. When a
candidate parent is to be determined, a peer from the cache is randomly
selected.
Downstream Strategy. Because repeated selection of ancestors as new par-
ents can lead to high degree values of such peers, violating the design
principle of keeping each peer's degree within a reasonable limit, the
downstream strategy of topology control works by randomly choosing a
Search WWH ::
Custom Search