Que.1 (a). A Gnutella topology looks like a balanced ternary tree with 5 levels
ID: 3857265 • Letter: Q
Question
Que.1
(a). A Gnutella topology looks like a balanced ternary tree with 5 levels of nodes, i.e., peers. Thus, there is 1 root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4, which in turn each have 3 children at Level 5 - thus, there are a total of 121 nodes.
(b). If the root node (Level 1) sends a Query message with TTL=3, then what are the number of nodes receiving the Query message, not including the originating node?
(c). A Gnutella topology looks like a balanced ternary tree with 4 levels of nodes, i.e., peers, as shown in the picture below. Thus, there is 1 root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4 - thus, there are a total of 40 nodes.
(d). If one of the leaf nodes (Level 4 nodes in the tree) sends a Query message with TTL=3, then what are the number of nodes receiving the Query message, not including the originating node?
(e). A Gnutella topology looks like a balanced ternary tree with 4 levels of nodes, i.e., peers, as shown in the picture below. Thus, there is 1 root at Level 1, which has 3 children at Level 2, which each have 3 children at Level 3, which in turn each have 3 children at Level 4 - thus, there are a total of 40 nodes.
If a child of the root (i.e., a Level 2 node in the tree) sends a Query message with TTL=3, then what are the number of nodes receiving the Query message, not including the originating node?
Explanation / Answer
a) No question present in this part.
b) TTL stands for "Time To Live". It is the time that tells how many hops a packet can travel before dying. For TTL=3, it will go till level 4. No. of nodes at level 2 = 3, no. of nodes at level 3= 3*3 = 9, no. of nodes at level 4 = 9*3 = 27. Hence, total no. of nodes receiving message = 3+9+27 = 39
c) No question present in this part.
d) Since in a tree, a leaf node is connected to nodes on path to its ancestors, a query message sent by a leaf node will be received by these nodes as well as by there corresponding childern. Therefore, a message with TTL=3 from a leaf node will be received by 1 (parent of leaf node that is at level 3 ) +1 (parent of parent, that is at level 2) +1(parent of parent of parent, that is root node)= 3 nodes.
e) If a node at level 2 sends a message with TTL=3, that message will be transmitted to its 3 childern at level 3, then to their childern at level 4 and its parent i.e. root node. Total nodes will be = 3+3*3+1 = 3+9+1 =13.