CS 352 Spring 2006

Theory of Operation

The second project will expand upon what you did for the first. Your client must now open a .torrent file, contact the tracker as well as multiple peers and be able to upload and download to the peers simultaneously. This means you will have to manage the state of several connections and work with multiple threads. Your client should also accept incoming connections from the peers at IP addresses listed above.

If your code for project 1 was well thought-out, it should be easy to expand your program for multiple downloads, and uploading should not be much more difficult than listening for more types of packets and sending new ones. You will not have to worry about choking any peers, but like the first project, you will have to make sure to unchoke them and keep them up to date on what pieces your client has downloaded.

Assignment Specifics

Your assignment should basically do the following:

Files Available

The files below are intended to help you concentrate on the networking portion of the project and not have to worry about how to bencode or "unbencode" the torrent file and some of the communication.

Programming Style

Writing maintainable code is just as important as writing correct code. Consequently, you will be graded on your style. Below is a list of suggestions to make your code easier to understand and maintain:

• Conditions - All of your methods must have clearly specified preconditions and postconditions. A precondition is what you assume to be true before your method is called, and a postcondition is what you can show to be true after your method has returned. Trivial preconditions (such as "int a is an integer") should be omitted. The best place to put the pre and postconditions is in a comment before the first line of each method.
  Example:

  			/*
  			Precondition: b is non-zero.
  			Postcondition: returns a / b.
  			*/
  			double divide(double a, double b)
  			{
  				return (a / b);
  			}
  		

• Comments - Comments for variables and for sections of code that does not have an obvious purpose. Please do not comment obvious statements or sections of code. For example,

  				int i = 0;	//i is an integer and the initial value is 0
  		

  is not useful and unnecessarily clutters the code.
• Naming - Names of classes, methods, and variables should be descriptive. For example, if a class has a field containing its hash value, naming the field hash_value is much better than naming it hv .
• Exceptions - Catch exceptions and do something useful with them. For example, print a statement describing what went wrong to System.err.
• Easy to understand loops/recursion. When possible, it's best to avoid break statements whenever possible. When using recursion, tail-recursion is often preferable because "smart" compilers can often translate it into a loop. Return statements within an if/else clause should be avoided whenever possible.
• Efficiency - Avoid being terribly inefficient. For example, if you have to sort 10M objects, it's better to sort them with a O(n*lg(n)) algorithm than a O(n²) algorithm.
• Encapsulation/Objects - Encapsulation is a useful feature of object-oriented languages, and because you are writing your program in an OO language, your program must separate the functionality into multiple classes. This way you can change the implementation of a class without affecting the rest of your program. An example of separation would be to have separate FileHandler, PeerInterface, and TrackerInterface classes to manipulate files, interface with peers and interface with the tracker, respectively. If you do not separate your program into functional units, you will lose points on the Style portion of the grading.

Bencoding (Pronounced "Bee Encoding")

Communication With the Tracker

Communicating With the Peer

Handshaking between peers begins with character nineteen (decimal) followed by the string 'BitTorrent protocol'. After the fixed headers are 8 reserved bytes which are set to 0. Next is the 20-byte SHA-1 hash of the bencoded form of the info value from the metainfo (.torrent) file. The next 20-bytes are the peer id generated by the client. The info_hash should be the same as sent to the tracker, and the peer_id is the same as sent to the tracker. If the info_hash is different between two peers, then the connection is dropped.

• All integers are encoded as 4-bytes big-endian. e.g. 1,234 should be encoded as (hex) 00
• The peer_id should simply be random numbers.

• keep-alive: <length prefix> is 0. There is no message ID and no payload. These should be sent around once every 2 minutes to prevent peers from closing connections. These only need to be sent if no other packets are sent within a 2-minute interval.
• choke: <length prefix> is 1 and message ID is 1. There is no payload.
• unchoke: <length prefix> is 1 and the message ID is 2. There is no payload.
• interested: <length prefix> is 1 and message ID is 2. There is no payload.
• uninterested: <length prefix> is 1 and message ID is 3. There is no payload.
• have: <length prefix> is 5 and message ID is 4. The payload is a zero-based index of the piece that has just been downloaded and verified.
• request: <length prefix> is 13 and message ID is 6. The payload is as follows:
  <index><begin><length>
  Where <index> is an integer specifying the zero-based piece index, <begin> is an integer specifying the zero-based byte offset within the piece, and <length> is the integer specifying the requested length. <length> is typically 2^14 (16384) bytes. A smaller piece should only be used if the piece length is not divisible by 16384. A peer may close the connection if a block larger than 2^14 bytes is requested.
• piece: <length prefix> is 9+X and message ID is 7. The payload is as follows:
  <index><begin><block>
  Where <index> is an integer specifying the zero-based piece index, <begin> is an integer specifying the zero-based byte offset within the piece, and <block> which is a block of data, and is a subset of the piece specified by <index> .

During the first project, a lot of people were confused about the order of messages after the handshake. Below is an example of what would take place between two peers setting-up a connection and starting sharing.

1. The local host opens a TCP Socket to the remote peer and sends the handshake packet. The local host then listens for the remote peer to respond.
2. Upon receiving the handshake packet and verifying the info_hash, the remote peer responds with a similar handshake packet (except with its peer_id). The remote peer then listens for the local host to send a bitfield or other packet. The remote host can send a bitfield packet to the local host at this time.
3. Upon receiving the handshake and verifying the info_hash, the local host then (optionally) sends a bitfield packet which tells the remote peer which pieces it has downloaded and verified so far.
4. If the local host is interested in what the remote peer has downloaded, then it sends an interested packet, otherwise it sends an uninterested packet. If the remote peer is interested in what the local host has downloaded, then it sends an interested packet, otherwise it sends an uninterested packet.
5. When the local host, or the remote peer, is ready to download/upload to the other, it will send an unchoke packet.

Please note that clients will, and your client should, ignore any request packets received while a remote peer is choked. A client should only upload to another client if the connection is unchoked AND the remote peer is interested. This means that a remote peer will not reply to the local hosts's request packets unless you have expressed interest AND the remote peer has sent an unchoke packet. If the remote peer sends a choke packet during data transfer, any outstanding requests will be discarded and unanswered - they should be re-requested after the next unchoke packet.

The Write-Up

• Include your name as it appears on the roster and your student ID.
• A high-level written description of how your program works. Specifically, describe the high-level interactions between the classes. This is a good way to make sure that your program doesn't have any classes depending on the implementations of other classes. You may include diagrams or illustrations if you feel it would aid your explanation or if you have a hard time explaining how your program works. However, you MUST include some written description of your program. If you know how to use LaTeX, this should be fairly easy to diagram. Also, OpenOffice.org's Draw program has an Export to PDF feature that is very simple to use. This section should be around 100 words, or 2 paragraphs.
• A brief (about 50 words or 1 paragraph) description of each class in the program. Describe what it does in general, the main public methods it provides, and any public fields it exposes. Note that classes should generally NOT have public fields unless they are Static (e.g. constants).
• Optionally, you may include a section on feedback about the program. Please only provide constructive/useful comments or insights. What parts of the project were the most challenging and which were the easiest? Did you have trouble finding resources for the project? Were any parts confusing to you? Including feedback will help shape the direction of the next project as well as help in pointing-out trouble spots to look at during grading.

Submitting the Project

Grading

• Programming Style: 15%
• Correctly interfacing with the tracker (retrieving peer list, periodic updates, after completing download): 10%
• Correctly interfacing with the peers (handshaking, maintaining state, keep-alive): 10%
• Correctly downloading from at least 2 peers simultaneously: 20%
• Correctly uploading to at least 2 peers simultaneously: 20%
• Correctly downloading and verifying the file: 15%
• Write-up 10%

Resources

Frequently Asked Questions

I've been getting a lot of similar questions lately, so I'll post general forms of them as well as advice on how to solve the underlying problems. As a bit of general advice, if you aren't sure what a packet is supposed to look like, you can always fire up a working client (the mainline BitTorrent client, for example) and then use a network packet sniffing tool like Ethereal to capture the traffic and analyze it.