Computer Networking • CS 514

Test 6, 3 December 2014

This test has six questions. The test runs the entire class period, starting at 4:30 and ending at 6:20. When you finish the test, you may leave.

Always justify answers unless the question explicitly states it’s not necessary. Some questions require reasonable assumptions in order to be answered. In such cases the answer should clearly state the assumptions made. Answers should be no longer than 75 to 100 words.
  1. Keeping in mind that giving an example of X is not defining X, briefly (in one or two sentences, 25 to 30 words total) define:

    • hypercube routing

    • iterative deepening

    • heuristic forward

    • hybrid architecture

    • distributed hash table

    Keeping in mind that giving an example of X is not defining X, briefly (in one or two sentences, 25 to 30 words) define:

    • hypercube routing:
    A routing technique used in a network organized as a hypercube. Routing is local and based on bit differences between neighbors.

    • iterative deepening:
    A technique for controlling graph search by sending out queries with successively longer time-to-live values.

    • heuristic forward:
    A guideline used by a node to determine how to forward a query in a peer-to-peer network.

    • hybrid architecture:
    A peer-to-peer network arrangement combining unstructured and structured network architectures, usually using the unstructured component for storage and the structured component for indexing and navigation.

    • distributed hash table:
    A hash table over the address space of a peer-to-peer network. Each network node is responsible for implementing a section of the hash table.

  2. Does the difference between unstructured and structured architectures significantly change the way peer-to-peer networks in each category assign addresses to peers? Justify your answer.

    Yes, the difference is important. Unstructured networks don’t use any particular scheme to assign addresses to nodes. Structured networks get their structure in part by assigning particular addresses to nodes to impose some organization on the network.

  3. One way to optimize performance of a search-based peer-to-peer network is to relocate resources closer to where they are being requested. Assume there are two ways to relocate resources: 1) physically move the bits so there’s only ever one copy of the resource in the network, or 2) copy the bits. Under what circumstances is it better to move bits than to copy them? Under what circumstances is it better to copy bits than to move them?

    Moving is essentially a copy with some coordination to delete the original after the copy. From that point of view, there’s no difference between moving and copying. Making a copy increases reliability and availability in the network, while moving the resource does not. Moving a resource closer to the demand improves performance, at a cost of using extra space. If the resources are writable, then copying raises the problem of maintaining consistency among the copies, which can be a difficult and expensive problem to solve.

  4. Two nodes in an unstructured, Gnutella-like network have the same address. Describe how non-unique addresses effect network operation.

    Non-unique peer-to-peer addresses are not likely to cause problems in unstructured networks. First, unstructured addressing places little weight on particular node address, unlike structured addressing schemes. Second, unstructured addressing is based on resource queries rather than specific addresses, which usually aren’t available in any case. Third, nodes deal with peers in terms of links rather than addresses, although addresses are used to establish links.

  5. Given the way finger tables in Chord improve search from linear to logarithmic time, a colleague of yours thinks that doubling the size of the finger table will improve search time at least as much as using finger tables did in the first place. What is your opinion of your colleague’s idea? Justify your answer.

    My colleague is chasing moonbeams. Doubling the size of a finger table increases the number of pointers into the network, but does so linearly (doubling). In the best case this may eliminate the hop after the hop, but there still will be hops proportional to the log of the number of nodes.

  6. Noticing how fabulously wealthy Google has become mapping Internet content, Grumble Ltd. has decided to try the same with peer-to-peer network content. After the Grumble Ltd. founders completed an initial round of venture-capital funding, they hire you as chief search architect to implement the proposed searching capabilities. Your task is to figure out how to adapt one of the standard network-layer routing algorithms to map resources in the network.

    Describe your plan. Keep in mind that the founders have already done all the vague hand-waiving. Your job is to provide specific details on how search will work.

    A link-state algorithm requires flooding, which doesn’t recommend itself for this problem. A modified distance-vector algorithm would have nodes send resource lists to neighbors instead of routing tables. Each node would combine neighbor resource lists into a neighborhood resource list, which would be forwarded in the next round.

    Rounds would be triggered periodically, or in response to peers entering or leaving the network, or both. Resource lists could get large, which could be handled by compressive encodings or dividing the network into areas and maintaining one resource list per area.

This page last modified on 2014 December 15.