Information Technology Reference
In-Depth Information
to this cycle avoidance problem. Specifically, the key idea is that each peer
uses a real number as its depth value, as shown in Figure 4.3.
1
1.2
2
1.1
2.5
2.1
3.1
2.7
3
2.6
3.5
4
4.1
4.2
FIGURE 4.3: All shaded nodes are considered as candidate parents for node
with depth 3, including the one with depth 3.1 if it reduces its depth value
[Frey and Murphy, 2008].
As can be seen from Figure 4.3, the only rule is that each peer's depth
value is greater than its parent's. Now, consider the case where a node (e.g.,
the node with depth value 3) needs to find a new parent. If only integer depth
values are allowed, the node with depth value 3.1 is not eligible. However,
under a real-valued depth scheme as shown in the figure, such a node (with
depth 3.1) can also be a new parent provided it decreases its depth value, say
to 2.9 (still larger than its own parent's). Indeed, to guarantee that the tree
depth values are consistent, the updating rule is that a peer can only decrease
its depth value (while still larger than its parent's) but never increase it. There
are two overhead-reducing implications. First, when a peer decreases its depth
value, it does not need to coordinate with its descendants. Second, each peer
does not need to accurately record the depth value of its parent (which may
be updated from time to time without notice). Instead, it only needs to record
one correct value (e.g., at the time when the parent is first connected) and can
use it afterward. The reason is that the depth value of the parent can only
decrease but never increase, so that the peer only needs to make sure that
its new depth value (whenever it updates it) is larger than this cached parent
depth value.
Figure 4.4 shows a semi-structured P2P network architecture that we dis-
cussed in Chapter 3. The major feature of this architecture [Ohnishi et al.,
2007] is that each Super Node can make use of its own network (i.e., a load
Search WWH ::




Custom Search