Computer Networks, CS 514

Homework 6, 6 November 2013

This assignment is due no later than 6:20 p.m. on Tuesday, 3 December.

This homework assignment has six questions; answer all of them. Answers should no longer than half a page, or around 100 to 150 words. Please site references you use to answer your questions, including the textbooks you’re using.

Your homework may turned-in on paper or via rclayton@monmouth.edu by email. If you mail your assignment, please submit a printable document — a PostScript .ps or PDF .pdf document, for example — and not a source document — a Word .docx or Latex .tex document, for example. Make sure you mail a printable document by the deadline.

1. Your network consulting firm has been contracted to build an unstructured peer-to-peer network with a topology following a power-law relation. The network consists of two nodes classes: expensive, capable nodes and less expensive, less capable nodes; capability is measured in throughput and storage capacity. Explain how you would use the different node classes to build a capable network as cheaply as possible, where cost involves only the cost of the nodes. A capable network is one in which every node is able to handle the offered load most of the time (that is, “use the cheapest nodes everywhere” is not a good answer).
2. You want to store an object O in a Gnutella network of 1000 nodes such that 50% of the searches for O have an expected hop count of at most 2. What is the smallest number of copies of O you should store? Assume O is a shareable resource, so there's no advantage to storing more than one copy of O at a node.
3. Networks A and B are both unstructured peer-to-peer networks. One of the networks A and B has a topology that satisfies the small-world relation, the other doesn't. Explain how you would distinguish the networks by topology.
4. A colleague of yours believes that objects located at low-addressed nodes in a Chord network will be found more quickly in searches than objects located a high-addressed nodes. What is your analysis of your colleague's belief?
5. Many structured peer-to-peer networks are based on a distributed hash table (DHT). One of the tricky aspects of normal (undistributed) hash-table data structures is making them dynamic so they can grow and shrink in capacity as needed. Pick a DHT-based structured peer-to-peer network and describe how it handles increases and decreases in capacity.
6. Assume an Edutella-like hybrid peer-to-peer network in which the structured part of the network is an N-dimensional hypercube and the hosts in the unstructured part of the network are directly attached to a hypercube node. What is the maximum hop count between two nodes in the unstructured part of the network?