Que 1 (i) A Gnutella topology looks like a balanced ternary tree with 4 levels o
ID: 3857428 • Letter: Q
Question
Que 1 (i) 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 the root node (Level 1) sends a Query message with TTL=2, then what are the number of nodes receiving the Query message, not including the originating node?
(ii) 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.
If a leaf (Level 5) node sends a Query message with TTL=2, then what are the number of nodes receiving this message, not including the originating node?
(iii) 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?
(iv) 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 one 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 the originating node of the Query is a leaf (Level 4 node), what is the minimum TTL to ensure all nodes in the system receive the Query?
Kindly provide the confirm solution of above question. thanks.
Explanation / Answer
Answer:
1) A message with TTL = 2 will go till level 3. At each level, TTL is decremented by 1. If TTL=1, it is not forwared further. Hence, it will go till level 3 only. There are 3 nodes at level 2 and 9 nodes at level 3. Hence, total nodes receiving the message are 3+9 = 12.
2) When a leaf node at level 5 sends a message, that message will first be transferred to its parent. Parent will again transfer it to its neighbours (its 2 other childern and its parent). As TTL = 2, message will not go beyond this. Hence, total nodes receiving the message will be 1+2+1 = 4.
3) A node at level 2 will send message to its 3 childern at level 3 and its parent at level 1. These nodes decrement TTL by 1 and will transfer the message to their respective childern (9 nodes at level 4 and 2 nodes at level 2 - rest two childern of root). Level 4 nodes will not tranfer message further. While level 2 nodes will transfer the message to their childern each having 3 childern. So, total nodes receiving the message will be 3+1+9+1+3+3 = 21.
4) In this case, TTL sholuld be such that the message should be able to reach to other leaf nodes. The number of hopes to a leaf node from one leaf node (on a path through root) is 5. So, minimum TTL in this case will be 5.