Homework 3

Total points 14

Question 1 Napster servers, as discussed in lecture, do not store which of the following? 1 point

• File pointers, i.e., (filename, peer address) pairs

• Files

• Addresses of other Napster servers

• Addresses of some of the peers (clients)

SOLUTION-Files

RHJUY

Question 2 Which of the following Gnutella messages are flooded out and TTL restricted? 1 point

• QueryHit

• Pull

• Giv

• Query

SOLUTION-Query

Question 3 In BitTorrent, a newly joined leecher X is trying to download a file with 6 blocks B1–B6. X has 3 neighbors: A, B, and C. These neighbors are storing the following blocks of the file: A: {B1, B2, B4, B5}; B:{B2, B3, B4, B5, B6}; C:{B1, B2, B6}. Then X will prefer downloading which block first? 1 point

• B3

• B1

• B5

• B2

SOLUTION-

Question 4 A Pastry DHT has a peer P with the following neighbors. P currently has to route a query to key 101001011010. Which of the following neighbors is the best next-hop for this query? 1 point

• 111001011010

• Cannot tell because P’s node id is not given

• 101001011000

• 101011001110

SOLUTION-101001011000

Question 5 In a Pastry DHT that is locality-aware, the path of a query is very likely to: (1 point) 1 point

• Take long network jumps in its early hops and short network jumps in later hops

• Take short network jumps in its early hops and long network jumps in later hops.

• None of the above.

• Take random-sized network jumps throughout its path

SOLUTION-Take short network jumps in its early hops and long network jumps in later hops.

Question 6 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 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? Enter your answer as a numeric value in the text box below. 1 point

SOLUTION-39

Question 7 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? Enter your answer as a numeric value in the text box below. 1 point

SOLUTION-4

Question 8 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 child of the root (i.e., a Level 2 node) sends a Query message with TTL=5, then what are the number of nodes receiving the Query message, not including the originating node? Enter your answer as a numeric value in the text box below. 1 point

SOLUTION-120

Question 9 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? Enter your answer as a numeric value in the text box below. (1 point)