Topology Control - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 59

candidate parent from the descendants of peers that already have high
degree values.
Upstream Strategy. While it is desirable to keep each peer's degree value
within a reasonable limit, it is equally important to avoid having a long
chain of peers connected in a line. This undesirable situation can hap-
pen if leaf nodes are repeatedly selected as candidate parents under the
Downstream Strategy. Thus, in this Upstream Strategy topology control
action, each peer whose current degree value is lower than a pre-defined
lower bound (e.g., in the case of a leaf node), can decline to serve as a
candidate parent.
BreakMaxDegree and BreakMinDegree Strategies. While the Down-
stream and Upstream strategies can help maintain the peer degree values
within range, they should not be applied too frequently to the extent
that the tree needs to be reconstructed. Thus, the BreakMaxDegree
and BreakMinDegree topology control actions are designed for forcing
a candidate parent to accept the request if such a parent has declined a
previous request due to degree contraints.
Global Strategy. This topology control action is designed to work under a
pathological situation where all regional potential parents are unreach-
able. Specifically, a Global cache is maintained to record some other
peers that can be anywhere in the current overlay. Such peers are con-
tacted if all regional strategies fail.
It is obvious that the above topology control actions are by and large
independent and therefore, can be combined in any order in consideration.
However, in practice it makes more sense to try one strategy (e.g., Regional)
first before considering the other (e.g., Global). The above strategies have
to be executed in an order such that the tree can be maintained with a low
overhead (i.e., relatively fewer nodes are involved) while keeping the shape
reasonable (i.e., peer degree values are within range). For example, a sensible
order (i.e., a protocol) is: Regional, Upstream, BreakMinDegree, Downstream,
Global, and then finally BreakMaxDegree.
One key aspect of tree topology maintenance is to avoid inadvertently
forming a cycle. Indeed, each potential candidate parent needs to evaluate
whether a request would lead to a cycle in the tree. Indeed, a simple solution
is that each peer records precisely its depth (i.e., hop count distance from
the root). When a candidate parent is needed, only those with depth values
strictly smaller than the current peer are considered. However, while this
simple solution is correct, its scalability is poor. For instance, just to maintain
correct depth values, the root needs to periodically send a message down the
tree so as to update all depth values. Furthermore, after a peer successfully
changes its parent, it needs to immediately update the depth values of all its
descendants.
Frey and Murphy [Frey and Murphy, 2008] described an ingenious solution