Exercise Package I (20 OEPs)

Schedule

Clarifications session: Friday 18.1.2013 at 14:15 in D122 (you ask questions about the questions)
Exercise deadline: Thursday 24.1.2013 at 16:00 (you return the answers by email)
Exercise deadline: Friday 25.1.2013 at 12:00 (you return the answers by email)
Publication of the correct answers: Friday 25.1.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-ex1.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 I" as the subject

Assignment 1 (4 OEPs)

Your friend who has not taken the overlay course wants to know whether or not overlays are useful. He is really stubborn and wants to use the bare Internet. You of course have taken the course and happen to know that overlay networks are the perfect match for all the use cases your friend keeps going on about.

1. Why are some software projects using overlays instead of just using the bare Internet?
2. Why do they not fix the Internet if it indeed is not suitable for their needs?
3. What is the cost they pay for using overlays instead of using the bare Internet?

The book and the lectures contain some spoilers, but you could do some Googling as well if you wish.

Assignment 2 (4 OEPs)

The TCP/IP stack contains some loose layering where protocols are assigned to different layers. Similar layer models have been presented for overlay networks.

1. What are the different functions performed by the different layers of an overlay network stack?
2. How might one combine the two stack pictures to explain the relation between overlay networks and TCP/IP?
3. What kind of similarities does the overlay network stack have with the TCP/IP stack?

Check lecture slides for stack pictures.

Assignment 3 (4 OEPs)

BitTorrent uses torrent files as the main method for addressing content. Some of the information available in the torrent file is contained in a structure named info, while some information is kept outside the info structure. The specification mentions info_hash in multiple places. It is a hash value over the info structure.

1. How does BitTorrent make use of the info_hash?
2. Why are some elements of a torrent file contained in the info structure?
3. Why are some elements of a torrent file contained outside the info structure?

The specification at http://wiki.theory.org/BitTorrentSpecification might help you.

Assignment 4 (8 OEPs)

There are two key strategies that affect the operation of BitTorrent content dissemination. One of the strategies is used to manage connections between nodes. The algorithm implementing the default connection strategy is called "choke". The other strategy is used to decide the order for retrieving parts of the content. The algorithm implementing the default download order strategy is called "rarest first". One goal of such strategic algorithms is to ensure that actions taken by misbehaving nodes do not harm the network, but rather contribute to efficient operation instead.

1. How does the choke algorithm manage to guarantee fairness?
2. Why does the rarest first algorithm use multiple modes instead of using the end game mode all the time
3. How does the new seed state modification done to the choke algorithm in BitTorrent 4.0.0 improve performance?

You can find descriptions for the rarest first and choke algorithms in the scientific paper "Rarest first and choke algorithms are enough" published by Arnaud Legout, G. Urvoy-Keller and P. Michiardi at ACM SIGCOMM conference in 2006. At the time of writing it was available from http://conferences.sigcomm.org/imc/2006/papers/p20-legout.pdf.

The Turbo Challenge

We have decided to accept submissions for the turbo challenge as separate submissions until 16:00 on Thursday 31.1.2013.
Just name your answer file to match the following pattern snumber1-snumber2-ex1-tc.extension and use "Overlay Exercise I TC" as the email subject line.
We will go through the turbo challenge answer during the Exercise Package II clarifications session on Friday 1.2.2013 at 14:15 in D122.

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.

You have managed to convince your friend. He is now all into overlay networks. He works day and night to build his own start-up. Together with the other founder they have decided to build a content delivery network (CDN) based on content dissemination techniques used in BitTorrent. Your friend fell in love with the performance of the new seed state modification (lets call it nssm) done to the choke algorithm in BitTorrent 4.0.0, but he still has some trouble with the specifics of the algorithm.

1. Explain in detail how choke nssm operates
2. Draw a diagram that shows what happens at what time when choke nssm operates
3. Explain in text what you have drawn

The material from assignment 4 might help you.