Exercise Package II (20 OEPs)

Schedule

Clarifications session: Friday 1.2.2013 at 14:15 in D122 (you ask questions about the questions)
Exercise deadline: Thursday 7.2.2013 at 16:00 (you return the answers by email)
Publication of the correct answers: Friday 8.2.2013 at 14:15 in D122 (we go through the correct answers together)

Submission Instructions

1. Create a document with your answers to the presented assignments.
2. Include names and student numbers of both participants in the document.
3. Produce a txt file or a pdf file for submission.
4. Name the file snumber1-snumber2-ex2.extension
   (where you replace
   snumber1 with the student number of one student in the pair,
   snumber2 with the student number of the other student in the pair, and
   extension with the correct file extension)
5. Send the file to toni.ruottu@cs.helsinki.fi with "Overlay Exercise II" as the subject

Assignment 5 (5 OEPs)

Chord is a distributed hash table (DHT) that assigns objects to nodes based on their identifiers.

In the provided file input.json you will find a json dictionary. The dictionary contains two lists of Chord identifiers. It has node identifiers stored under key "nodes" and object identifiers stored under key "objects". Your task is to write a computer program that computes the responsible node for each object.

You need to attach two additional files with your submission email:

1. snumber1-snumber2-ex2.json needs to contain the mapping as computed by your program. The file needs to be a valid json file with a json object (associative array) as the root element. The root element should contain all node identifiers as keys, and the value for each node should be a list of object identifiers that the corresponding node is responsible for. Nodes that are not responsible for any objects need to be included with an empty list of objects. The identifiers need to be five digit numbers presented as strings padded with leading zeros. See input.json for an example on the identifier format. The format is important because your answer will be checked by a computer.
   
   
2. snumber1-snumber2-ex2.zip needs to contain your programs source code. You may use tar instead of zip if you wish. In such case just replace the file extension with a more appropriate one.

You may pick any programming language you wish. Using a json library is recommended. For example, to get started in Python you might do something like...

#!/usr/bin/python

import json

input_handle = open('input.json')
json_data = input_handle.read()
input_data = json.loads(json_data)
nodes = input_data['nodes']
objects = input_data['objects']

Generating small inputs for testing your software during the development phase is highly recommended. You may familiarize yourself with json at http://json.org/.

Assignment 6 (5 OEPs)

Tapestry is a distributed hash table (DHT) that routes requests based on routing tables.

1. How are the routing tables constructed?
2. How are requests routed once the routing tables are in place?
3. How are new nodes introduced to the network?

Operation of Tapestry is explained in the journal article "Tapestry: A Resilient Global-scale Overlay for Service Deployment" by Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph and John D. Kubiatowicz. The article was published in the IEEE Journal on Selected Areas in Communications volume 22 issue 1 in 2004. When this exercise package was created it was available from http://www.cs.ucsb.edu/~ravenben/publications/pdf/tapestry_jsac.pdf

Assignment 7 (5 OEPs)

The Freenet Project is building and overlay with the goal of enhancing online privacy. Efficient operation of the system is based on a location swapping technique.

1. What kind of privacy guarantees is Freenet able to give?
2. How does Freenet achieve these guarantees?
3. What kind of correspondence do the locations used with Freenet's location swapping have to geographical location?

The basic operation of Freenet is described in the journal article "Protecting Free Expression Online with Freenet" by Ian Clarke, Scott G. Miller, Theodore W. Hong, Oskar Sandberg and Brandon Wiley. It was published in IEEE Internet Computing journal volume 6 issue 1 in 2002. When this exercise package was created it was available from https://freenetproject.org/papers/freenet-ieee.pdf.

The location swapping algorithm was later introduced as an addition to Freenet's basic model. Ian Clarke and Oskar Sandberg explained the changes in the talk "Routing in the Dark: Freenet's new design" that they gave in December 2005 at the 22nd Chaos Communication Congress in Berlin. The presentation was recorded and published on the Internet. When this exercise package was created it was available from http://vimeo.com/22488244.

Assignment 8 (5 OEPs)

Sometimes network researchers discuss mathematical network models such as small-world networks, scale-free networks and the power law.

1. What is the power law?
2. What are the differences and similarities between small-world networks and scale-free networks?
3. How is the study of these mathematical models relevant to overlay network research?

The video from assignment 7 should help you get started with the basic concepts, but finding other sources is required.

Turbo Challenge 2

Disclaimer: The turbo challenge presented below is extremely hard and does not grant you extra points. However a decent solution for the turbo challenge may award some compensation for lack of points in other assignments.

Some researchers have pointed out possible flaws in the location swapping technique employed by Freenet.

1. What are the presented concerns?
2. How do we know whether or not the presented problems are real?
3. What could be done to mitigate the problem?

Some possible problems are described in the scientific paper "Routing in the Dark: Pitch Black" published by Nathan S. Evans, Chris GauthierDickey and Christian Grothoff at the 23rd Annual Computer Security Applications Conference (ACSAC) in 2007. When this exercise package was created it was available from http://grothoff.org/christian/pitchblack.pdf.