Bài tập lập trình lớp mạng máy tính

Thường là mỗi lần dạy lớp mạng máy tính tôi lại thiết kế một “bài tập lập trình mạng” khác nhau. Học kỳ này, bài tập là một phiên bản của BitTorrent protocol. Các sinh viên có 2 tháng để viết chương trình này. (Mấy lần trước thì là Gnutella và Kademlia, đều là các bài tập lập trình mạng tuyệt vời.)

1. Purpose and basic requirements

Project 1 hopefully have familiarized you with basic socket programming. Please check out my implementation (source) of project 1. I hope you can build on it or learn something from it. Project 2 is no longer “toyish.” You will implement a basic subset of the BitTorrent protocol, which is one of the (two) most popular P2P file sharing protocols on the Internet. BitTorrent traffic constitutes a large fraction of modern Internet traffic. If you implement the protocol correctly, your “client” should be able to download files from other BitTorrent clients “in the wild,” and there are millions of those peers.

The assignment is to be done in groups of size at most 2. You are responsible for finding your partner (if you need one), for finishing off the assignment in case your partner drops the class or backs out from completing the assignment for whatever reason. The program is to be written in C under a Unix platform such as Linux, SunOS, Solaris, or FreeBSD, or even Mac OS X. Under Windows, it is possible to develop your program with cygwin but you must make sure that:

• Your submission compiles and runs under both Linux and Solaris/SunOS. We will test your submission on both Linux and Solaris/SunOS machines.
• Except for C++ (which is still not at all recommended), no other language is allowed. I have good pedagogical reasons for this requirement.

For portability, please use the Makefile I provided in my Project 1 implementation, so that we can compile your program under these two platforms.

---

2. UBTorrent — overview of the protocol

Let’s refer to the subset of the BitTorrent protocol that we (i.e. you and I) will implement the UBTorrent protocol. It is BitTorrent with some advanced features stripped off. For simplicity, we will also name the program to be implemented ubtorrent, each instance of which is called a UBTorrent peer, or just a peer for short. For convenience, when we talk about the behavior of a particular peer, we will call it a (UBTorrent)client, to distinguish it from other peers.

The “official” BitTorrent protocol specification written by Bram Cohen is vague is some areas. Thus, I will copy materials from a more detailed specification of BitTorrent 1.0. You do not need to read the official specifications, because UBTorrent is (hopefully) simpler.

Peers collaborate to download files. Let’s say some client has a file to be shared named “Simon and Garfunkel – Sound of Silence.mp3“. Actually, let’s rename it “SS.mp3” for short. The client first needs to create a metainfo file containing information about SS.mp3. The metainfo file has the .torrent extension, and is often referred to as the “dot torrent” file of SS.mp3. The precise format of the metainfo file will be described below. Roughly, it contains the file name, keywords (if any), the URL of a program called a tracker, which is responsible for keeping track of all the peers who are collaborating in downloading SS.mp3.

2.1 Creating the metainfo file

In the wild, you will typically have to upload the metainfo file to some webserver, allowing others to search for it, and download it. But in Project 2, we will assume that every peer has the metainfo file already, bypassing the search step. (Feel free to implement a web search engine, in which case you should drop out of UB right about now.) In particular, we’ll just create the metainfo file for SS.mp3 and “give” it to each participating peer.

You can create the metainfo file using a command line utility that Bram Cohen wrote in Python a while back, named btmakemetafile. Here’s a directory containing the utility (and supporting files). Download, gunzip and untar it, you will get a directory named MMT containing the utility. To create a metafile for SS.mp3, you can type something like this:

UBTorrent/MMT/btmakemetafile SS.mp3 http://127.0.0.1:6969/announce

The first argument is the file name (or path to file name if you’re not running the utility in the directory where the file resides). The second argumenthttp://127.0.0.1:6969/announce is called the URL of the tracker, which basically consists of the IP address and the port number that the tracker is running and listening on. Note that the tracker will run the HTTP protocol, and hence there’s the http:// in the beginning.

Important note: you might need to edit the first line of btmakemetainfo to point to the right path of python for btmakemetainfo to work. Typewhich python to get the path.

2.2. The tracker

It would be nice if we wrote your own tracker, but that would be too easy to do in 2 months. So, let’s not do that. We will use probably the most well-known tracker out there: the opentracker written by Dirk Engling. It is (was?) used by PirateBay.com and even a Norwegian state TV broadcaster.

To download and compile opentracker, download these files, unzip and untar them, you’ll get two directories named libowfat and opentracker. You MUST put the two directories under the same parent directory for the compilation to work. Then, cd into libowfat and type make, and cd intoopentracker and type make. Alternatively, you can just follow Dirk Engling direction on his opentracker website:

cvs -d :pserver:cvs@cvs.fefe.de:/cvs -z9 co
libowfat
cd libowfat
make
cd ..
cvs -d:pserver:anoncvs@cvs.erdgeist.org:/home/cvsroot co opentracker
cd opentracker
make

There are two versions, opentracker and opentracker.debug, and you can run either of them. For instance,

hungngo@MYMACHINE:~/UBTorrent/opentracker$ ./opentracker.debug -i 127.0.0.1
Binding socket type TCP to address [127.0.0.1]:6969... success.
Binding socket type UDP to address [127.0.0.1]:6969... success.

will tell it to listen to port 6969 (default port) on the local interface.

Note: if make reports some error, please try gmake.

2.3. The protocols

Once the tracker is running (on the URL specified in the metainfo file for SS.mp3), peers can start collaborating on downloading this file. To get to know other peers, a client talks to the tracker using the Tracker HTTP Protocol, which is simply a tiny subset of the HTTP protocol. The tracker maintains and updates information about the torrent or the swarm, which is the set of participating peers. Every shared file corresponds to a swarm. A new peer can join the swarm by informing and querying the tracker.

Once knowing each other, peers can talk directly to each other using the Peer Wire Protocol over TCP to exchange pieces of SS.mp3. A swarm can be large, containing any where from tens to thousands of peers. Thus, a client only connects to a subset of those. The original client which had the file SS.mp3 to share is called a seeder. Peers who do not have the entire file yet are called leechers. There might be multiple seeders for the same file, because once a leecher has downloaded the entire file, it will become a seeder. Peers can leave a swarm at any time, on their own terms.

While the Tracker HTTP Protocol is very simple both conceptually and practically, the Peer Wire Protocol (PWP) is only conceptually simple: a client requests pieces of the file from other peers until it got the entire file. If everyone was as enlightened as Buddha, PWP would have been extremely simple and there would be no Nobel prize in economics. Unfortunately, in the wild PWP has to solve the free rider problem while keeping the download efficient.

For efficiency, PWP uses a simple strategy called rarest first in which, given the current list of missing pieces, the client requests a rarest one first (i.e. a piece which fewest — but non-zero — of its neighboring peers have). Typically, there are many pieces which are equally rare. In this case it is also important to randomly pick one of them to download. This way, the availability of pieces are spread out and thus even when all seeders go to heaven, chances are better that no piece goes extinct.

To solve the free rider problem, PWP uses something called choke algorithms. A client gives pieces to good guys and “chokes” guys who haven’t given the client much. This is also called a tit-for-tat strategy. However, to avoid peers choking each other to death, especially in the beginning, a client also randomly unchokes some (potentially) bad guy too. This is called optimistic unchoking.

Recent studies have shown that rarest first and choke algorithms are pretty good at solving both the free rider problem and the download efficiency problem. However, these mechanisms are far from perfect and there are a lot of potentials for further research and new protocol design. I hope some of you will get interested in this problem and start experimenting with new ideas. You could be the next Bram Cohen! (I’ll gladly accept a small stake in the new company.)

---

3. The ugly details

A large part of this section is copied (selectively) from the BitTorrent protocol specification. However, I have also stripped off many requirements. When in doubt, ask me (via the blog), don’t consult the official BitTorrent protocol specification. After all, we are implementing UBTorrent, not BitTorrent.

3.1 Bencoding

Bencoding is a way to specify and organize data in a terse format. It supports the following types: byte strings, integers, lists, and dictionaries.

3.1.1 Byte strings

Byte strings are encoded as follows: <string length encoded in base ten ASCII>:<string data>
Note that there is no constant beginning delimiter, and no ending delimiter.

Example: 4:spam represents the string “spam”

3.1.2 Integers

Integers are encoded as follows: i<integer encoded in base ten ASCII>e
The initial i and trailing e are beginning and ending delimiters. You can have negative numbers such as i-3e. You cannot prefix the number with a zero such as i04e. However, i0e is valid.

Example: i3e represents the integer “3″

3.1.3 Lists

Lists are encoded as follows: l<bencoded values>e
The initial l and trailing e are beginning and ending delimiters. Lists may contain any bencoded type, including integers, strings, dictionaries, and other lists.

Example: l4:spam4:eggse represents the list of two strings: [ "spam", "eggs" ]

3.1.4 Dictionaries

Dictionaries are encoded as follows: d<bencoded string><bencoded element>e
The initial d and trailing e are the beginning and ending delimiters. Note that the keys must be bencoded strings. The values may be any bencoded type, including integers, strings, lists, and other dictionaries. Keys must be strings and appear in sorted order (sorted as raw strings, not alphanumerics). The strings should be compared using a binary comparison, not a culture-specific “natural” comparison.

Example: d3:cow3:moo4:spam4:eggse represents the dictionary { “cow” => “moo”, “spam” => “eggs” }

Example: d4:spaml1:a1:bee represents the dictionary { “spam” => [ "a", "b" ] }

Example: d9:publisher3:bob17:publisher-webpage15:www.example.com18:publisher.location4:homee represents { “publisher” => “bob”, “publisher-webpage” => “www.example.com”, “publisher.location” => “home” }

3.1.5 You don’t have to implement a bendecoder

You can use a bendecoder written in C by Mike Frysinger here. Feel free to write your own. After downloading the entire directory, you can test the bendecoder by make and then try

hungngo@MYMACHINE:~/tmp/bencode$ ./test i1234e
DECODING: i1234e
int = 1234
hungngo@MYMACHINE:~/tmp/bencode$ ./test l4:spam4:eggse
DECODING: l4:spam4:eggse
list [
    str = spam (len = 4)
    str = eggs (len = 4)
]
hungngo@MYMACHINE:~/tmp/bencode$ ./test d3:cow3:moo4:spam4:eggse
DECODING: d3:cow3:moo4:spam4:eggse
dict {
    cow => str = moo (len = 3)
    spam => str = eggs (len = 4)
}

Obviously, you should look into the code to see how to use the functions. But the decoder is there, no coding needed. This decoder is the bulk of the metainfo command that you’re supposed to implement.

3.2. Metainfo file structure

All data in a metainfo file is bencoded. The content of a metainfo file (the file ending in “.torrent”) is a bencoded dictionary, containing the keys listed below. All character string values are UTF-8 encoded.

• announce: The announce URL of the tracker (string)
• info: a dictionary that describes the file(s) of the torrent. There are two possible forms: one for the case of a ‘single-file’ torrent with no directory structure, and one for the case of a ‘multi-file’ torrent (see below for details)
• a few other optional keys such as, creation date, comment, created by, and encoding. When you read the metainfo file, ignore these keys.

The info dictionary contains the following fields:

• length: length of the file in bytes (integer)
• name: the filename. This is purely advisory. (string)
• piece length: number of bytes in each piece (integer)
• pieces: string consisting of the concatenation of all 20-byte SHA1 hash values, one per piece (byte string, i.e. not urlencoded)

Notes:

• The piece length specifies the nominal piece size, with default value 256KB = 2¹⁸ bytes = 262144 bytes. In practice, the piece length is typically chosen based on the total amount of file data in the torrent, and is constrained by the fact that too-large piece sizes cause inefficiency, and too-small piece sizes cause large .torrent metainfo file. Historically, piece size was chosen to result in a .torrent file no greater than approx. 50 – 75 kB (presumably to ease the load on the server hosting the torrent files).
  • Current best-practice is to keep the piece size to 512KB or less, for torrents around 8-10GB, even if that results in a larger .torrent file. This results in a more efficient swarm for sharing files. The most common sizes are 256 kB, 512 kB, and 1 MB.
  • Every piece is of equal length except for the final piece, which is irregular. The number of pieces is thus determined by ‘ceil( total length / piece size )’.
• Each piece has a corresponding SHA1 hash of the data contained within that piece. These hashes are concatenated to form the pieces values in the above info dictionary. Note that this is not a list but rather a single string. The length of the string must thus be a multiple of 20.
• Look carefully at my implementation of Project 1 for how to compute SHA1 hashes. (After a piece is downloaded, you will need to compute its SHA1 hash to verify its integrity!)

3.3. Tracker HTTP Protocol

The tracker is an HTTP service which responds to HTTP GET requests. The requests include metrics from clients that help the tracker keep overall statistics about the torrent. The response includes a peer list that helps the client participate in the torrent. The base URL consists of the “announce URL” as defined in the metainfo (.torrent) file. The parameters are then added to this URL, using standard CGI methods (i.e. a ‘?’ after the announce URL, followed by ‘param=value’ sequences separated by ‘&’).

Note that all binary data in the URL (particularly info_hash and peer_id) must be properly escaped. This means any byte not in the set 0-9, a-z, A-Z, ‘.’, ‘-’, ‘_’ and ‘~’, must be encoded using the “%nn” format, where nn is the hexadecimal value of the byte. (See RFC1738 for details.) This is called the urlencoding of the data.

For a 20-byte hash of

\x12\x34\x56\x78\x9a\xbc\xde\xf1\x23\x45\x67\x89\xab\xcd\xef\x12\x34\x56\x78\x9a

the right encoded form is

%124Vx%9A%BC%DE%F1%23Eg%89%AB%CD%EF%124Vx%9A

3.3.1 Tracker Request Parameters

The parameters used in the client->tracker GET request are as follows:

• info_hash: urlencoded 20-byte SHA1 hash of the value of the info key from the metainfo file. Note that the value will be a bencoded dictionary, given the definition of the info key above.
• peer_id: urlencoded 20-byte string used as a unique ID for the client, generated by the client at startup. This is allowed to be any value, and may be binary data.
• port: The port number that the client is listening on.
• uploaded: The total number of bytes uploaded (since the client sent the ‘started’ event to the tracker) in base ten ASCII.
• downloaded: The total number of bytes downloaded (since the client sent the ‘started’ event to the tracker) in base ten ASCII.
• left: The number of bytes this client still has to download, encoded in base ten ASCII.
• compact: Setting this to 1 indicates that the client accepts a compact response. The peers list is replaced by a peers string with 6 bytes per peer. The first four bytes are the host (in network byte order), the last two bytes are the port (again in network byte order). It should be noted that some trackers only support compact responses (for saving bandwidth) and either refuse requests without “compact=1″ or simply send a compact response unless the request contains “compact=0″ (in which case they will refuse the request.)
• event: If specified, must be one of started, completed, stopped, (or empty which is the same as not being specified). If not specified, then this request is one performed at regular intervals.
  • started: The first request to the tracker must include the event key with this value.
  • stopped: Must be sent to the tracker if the client is shutting down gracefully.
  • completed: Must be sent to the tracker when the download completes. However, must not be sent if the download was already 100% complete when the client started. Presumably, this is to allow the tracker to increment the “completed downloads” metric based solely on this event.

A request from the (original) seeder looks something like this:

GET /announce?info_hash=_tWL%26%BD%C4%BDsEn%FD%7E1%2CJ3%40s%1B&peer_id=M3-4-2--5ffd511f4079&port=6881&key=585b8345&uploaded=0&downloaded=0&left=0&compact=1&event=started HTTP/1.1

A request from a leecher looks something like this:

GET /announce?info_hash=_tWL%26%BD%C4%BDsEn%FD%7E1%2CJ3%40s%1B&peer_id=M3-4-2--f8c7df8ee1b9&port=6882&key=a6fa9e7e&uploaded=0&downloaded=0&left=90112&compact=1&event=started HTTP/1.1

Note: 90112 is the size of SS.mp3. A GET request typically consists of the GET request line (as shown above) and an empty line. The last two characters of an HTTP request line must be \r\n. The “empty” line must consist of two characters \r\n. Those are “carriage-return” and “line-feed” characters.

3.3.2 Tracker Response

The tracker responds with “text/plain” document consisting of a bencoded dictionary with the following keys:

• failure reason: If present, then no other keys may be present. The value is a human-readable error message as to why the request failed (string).
• warning message: (new, optional) Similar to failure reason, but the response still gets processed normally. The warning message is shown just like an error.
• interval: Interval in seconds that the client should wait between sending regular requests to the tracker
• min interval: (optional) Minimum announce interval. If present clients must not reannounce more frequently than this.
• tracker id: A string that the client should send back on its next announcements. If absent and a previous announce sent a tracker id, do not discard the old value; keep using it.
• complete: number of peers with the entire file, i.e. seeders (integer)
• incomplete: number of non-seeder peers, aka “leechers” (integer)
• peers: (dictionary model) The value is a list of dictionaries, each with the following keys:
  • peer id: peer’s self-selected ID, as described above for the tracker request (string)
  • ip: peer’s IP address either IPv6 (hexed) or IPv4 (dotted quad) or DNS name (string)
  • port: peer’s port number (integer)
• peers: (binary model) Instead of using the dictionary model described above, the peers value may be a string consisting of multiples of 6 bytes. First 4 bytes are the IP address and last 2 bytes are the port number. All in network (big endian) notation.

The list of peers is length 50 by default. If there are fewer peers in the torrent, then the list will be smaller. Otherwise, the tracker randomly selects peers to include in the response. The tracker may choose to implement a more intelligent mechanism for peer selection when responding to a request. For instance, reporting seeds to other seeders could be avoided. Since we are not implementing the tracker, we just take whatever the tracker gives.

Clients may send a request to the tracker more often than the specified interval, if an event occurs (i.e. stopped or completed) or if the client needs to learn about more peers. However, it is considered bad practice to “hammer” on a tracker to get multiple peers.

A reply from the tracker may look something like this:

HTTP/1.0 200 OK
Content-Length: 27
Content-Type: text/plain
Pragma: no-cache

d8:intervali1800e5:peers0:e

In general, the reply from the tracker follows the format specified here. You should print out the first line of the response. If the status code (e.g. the number 200 above) is anything other than 2xx, then something is wrong, don’t read and parse the content. The content of the reply is everything after the blank line. Note: if you didn’t do anything special (like having a persistent-connection request along with the GET line), the tracker will close the connection right after sending the reply. Don’t be surprise! You should try telnet localhost 6969 after running opentracker, and then cut-and-paste a sample request shown in the previous section to see the tracker’s response. Important note: The readline() function provided in the sample codes can be used, but it has to be used with extreme care, because it can read past the EOL character (for efficiency). Please read the code before using it!

3.4. Peer Wire Protocol (over TCP)

3.4.1 Overview

The peer protocol facilitates the exchange of pieces as described in the metainfo file. To request a piece, a client will actually send multiple requests for parts of the piece, called blocks.  A block size is typically divisible by the piece size. It is recommended to set the default block size to be 16KB =  2¹⁴ = 16384 bytes. Feel free to set the default block size to be equal to the piece size if you want. However, since the last piece may not have full size, some block requests will inevitably have to be of small sizes.

A client must maintain state information for each connection that it has with a remote peer:

• choked: Whether or not the remote peer has choked this client. When a peer chokes the client, it is a notification that no requests will be answered until the client is unchoked. The client should not attempt to send requests for blocks, and it should consider all pending (unanswered) requests to be discarded by the remote peer.
• interested: Whether or not the remote peer is interested in something this client has to offer. This is a notification that the remote peer will begin requesting blocks when the client unchokes them.

Note that this also implies that the client will also need to keep track of whether or not it is interested in the remote peer, and if it has the remote peer choked or unchoked. So, the real list looks something like this:

• am_choking: this client is choking the peer
• am_interested: this client is interested in the peer
• peer_choking: peer is choking this client
• peer_interested: peer is interested in this client

Client connections start out as “choked” and “not interested”. In other words:

• am_choking = 1
• am_interested = 0
• peer_choking = 1
• peer_interested = 0

A block is downloaded by the client when the client is interested in a peer, and that peer is not choking the client. A block is uploaded by a client when the client is not choking a peer, and that peer is interested in the client. It is important for the client to keep its peers informed as to whether or not it is interested in them. This state information should be kept up-to-date with each peer even when the client is choked. This will allow peers to know if the client will begin downloading when it is unchoked (and vice-versa).

3.4.2 Data type

Unless specified otherwise, all integers in the peer wire protocol are encoded as four byte big-endian values. This includes the length prefix on all messages that come after the handshake.

3.4.3 Message flow

The peer wire protocol consists of an initial 2-way handshake. After that, peers communicate via an exchange of length-prefixed messages. The length-prefix is an integer as described above.

3.4.4 Handshake

The handshake is a required message and must be the first message transmitted by the client. It is (49+len(pstr)) bytes long.

handshake: <pstrlen><pstr><reserved><info_hash><peer_id>

• pstrlen: string length of <pstr>, as a single raw byte
• pstr: string identifier of the protocol.
  • In the UBTorrent protocol, as in the BitTorrent protocol, pstrlen = 19, and pstr = “BitTorrent protocol”.
• reserved: eight (8) reserved bytes. All current implementations use all zeros. Each bit in these bytes can be used to change the behavior of the protocol. An email from Bram suggests that trailing bits should be used first, so that leading bits may be used to change the meaning of trailing bits.
• info_hash: 20-byte SHA1 hash of the info key in the metainfo file. This is the same info_hash that is transmitted in tracker requests.
• peer_id: 20-byte string used as a unique ID for the client

The initiator of a connection is expected to transmit their handshake immediately. The recipient may wait for the initiator’s handshake, if it is capable of serving multiple torrents simultaneously (torrents are uniquely identified by their info_hash). However, the recipient must respond as soon as it sees the info_hash part of the handshake. If a client receives a handshake with an info_hash that it is not currently serving, then the client must drop the connection.

If the initiator of the connection receives a handshake in which the peer_id does not match the expected peer_id, then the initiator is expected to drop the connection. Note that the initiator presumably received the peer information from the tracker, which includes the peer_id that was registered by the peer. The peer_id from the tracker and in the handshake are expected to match.

3.4.5 Messages

All of the remaining messages in the protocol take the form of <length prefix><message ID><payload>. The length prefix is a four byte big-endian value. The message ID is a single decimal byte. The payload is message dependent.

keep-alive: <len=0000>

The keep-alive message is a message with zero bytes, specified with the length prefix set to zero. There is no message ID and no payload. Peers may close a connection if they receive no messages (keep-alive or any other message) for a certain period of time, so a keep-alive message must be sent to maintain the connection alive if no command have been sent for a given amount of time. This amount of time is generally two minutes.

choke: <len=0001><id=0>

The choke message is fixed-length and has no payload.

unchoke: <len=0001><id=1>

The unchoke message is fixed-length and has no payload.

interested: <len=0001><id=2>

The interested message is fixed-length and has no payload.

not interested: <len=0001><id=3>

The not interested message is fixed-length and has no payload.

have: <len=0005><id=4><piece index>

The have message is fixed length. The payload is the zero-based index of a piece that has just been successfully downloaded and verified via the SHA1 hash.

Implementer’s Note: That is the strict definition, in reality some games may be played. In particular because peers are extremely unlikely to download pieces that they already have, a peer may choose not to advertise having a piece to a peer that already has that piece. At a minimum “HAVE suppression” will result in a 50% reduction in the number of HAVE messages, this translates to around a 25-35% reduction in protocol overhead. At the same time, it may be worthwhile to send a HAVE message to a peer that has that piece already since it will be useful in determining which piece is rare.

A malicious peer might also choose to advertise having pieces that it knows the peer will never download. Due to this attempting to model peers using this information is a bad idea.

bitfield: <len=0001+X><id=5><bitfield>

The bitfield message may only be sent immediately after the handshaking sequence is completed, and before any other messages are sent. The bitfield needs not be sent if a client has no pieces.

The bitfield message is variable length, where X is the length of the bitfield. The payload is a bitfield representing the pieces that have been successfully downloaded. The high bit in the first byte corresponds to piece index 0. Bits that are cleared indicated a missing piece, and set bits indicate a valid and available piece. Spare bits at the end are set to zero. A bitfield of the wrong length is considered an error. Clients should drop the connection if they receive bitfields that are not of the correct size, or if the bitfield has any of the spare bits set.

request: <len=0013><id=6><index><begin><length>

The request message is fixed length, and is used to request a block. The payload contains the following information:

• index: integer specifying the zero-based piece index
• begin: integer specifying the zero-based byte offset within the piece
• length: integer specifying the requested length.

piece: <len=0009+X><id=7><index><begin><block>

The piece message is variable length, where X is the length of the block. The payload contains the following information:

• index: integer specifying the zero-based piece index
• begin: integer specifying the zero-based byte offset within the piece
• block: block of data, which is a subset of the piece specified by index.

cancel: <len=0013><id=8><index><begin><length>

The cancel message is fixed length, and is used to cancel block requests. The payload is identical to that of the “request” message. It is typically used during “End Game” (see the Algorithms section below).

3.5 Algorithms

3.5.1 Piece downloading strategy

Download pieces in rarest first order. The client can determine this by keeping the initial bitfield from each peer, and updating it with every havemessage. Then, the client can download the pieces that appear least frequently in these peer bitfields. Note that any Rarest First strategy should include randomization among at least several of the least common pieces, as having many clients all attempting to jump on the same “least common” piece would be counter productive.

3.5.2 Choking and Optimistic Unchoking

The choke algorithm was introduced to guarantee a reasonable level of upload and download reciprocation. As a consequence, free riders, i.e., peers that never upload, should be penalized. For the sake of clarity, we describe without loss of generality the choke algorithm from the point of view of the local peer. In this section, interested always means interested in the local peer, and choked always means choked by the local peer.

The choke algorithm difers in leecher and seed states. We describe first the choke algorithm in leecher state. At most 4 remote peers can be unchoked and interested at the same time. Peers are unchoked using the following policy.

1. Every 10 seconds, the interested remote peers are ordered according to their download rate to the local peer and the 3 fastest peers are unchoked.
2. Every 30 seconds, one additional interested remote peer is unchoked at random. We call this random unchoke the optimistic unchoke.

In the following, we call the three peers unchoked in step 1 the regular unchoked (RU) peers, and the peer unchoked in step 2 the optimistic unchoked (OU) peer. The optimistic unchoke peer selection has two purposes. It allows to evaluate the download capacity of new peers in the peer set, and it allows to bootstrap new peers that do not have any piece to share by giving them their first piece.

In seed state, the choke algorithm is the same as that in leecher state except that in seed state the ordering performed in step 1 is based on upload rates from the local peer.

---

4. What you are supposed to implement

You’re probably overwhelmed by the above description. However, keep in mind that you can use existing codes for many important functionalities have been implemented already: the SHA1 hash, the bendecoder, the tracker, etc. I will simplify things further by requiring you to implement clients which support only one single .torrent file, given as an input to the program ubtorrent. It is not difficult to extend the implementation to support multiple torrents, and you are encourage to do so in your spare time after this course is over. In fact, run your implementation “in the wild” to see how it measures up to other professional ones. Your ubtorrent is supposed to implement all of the above requirements though. The sequence of tasks looks something like this:

• Download and compile the opentracker program. Run it.
• Create the .torrent file for SS.mp3 (or any reasonably sized file). We will test your program with files up to 20MB in size, but not more. When you implement ubtorrent, you probably should write pieces down to disk, don’t keep everything in memory.
• Create several directories, perhaps name them 1, 2, 3, 4, 5 and so on. Then put SS.mp3 in one of them. And, put a copy of ubtorrent in each of them. Thus, the copy of ubtorrent running inside directory 1 will be the original seeder. Other copies of ubtorrent can write temporary files inside that local directory. Clean up the temp files after the downloading is done, or if the user types quit
• ubtorrent takes two parameters: the first argument is the .torrent file name, and the second argument is the port number that other peers can connect to. For example,

  ubtorrent SS.mp3.torrent 6881

• Note that the tracker information is contained in the metainfo file. Upon starting, a client checks the local directory to see if the file is there already. (Check the file name and file size.) If the file is there, the client is running in the seeder state. Otherwise, it is running in the leecher state. The client then issues a GET request to the tracker rightaway. If the tracker is not running, the client reports an error and quit.
• At this point, if the seeder was already started, or if other peers have downloaded some pieces, the current client can start requesting blocks and start downloading. It should fully implement the rarest first and choke algorithms. If you run only 5 peers in total, choke algorithms should not take effect, and thus the peers download blocks/pieces from each other until they are completed. The rarest first algorithm should still be in place though. I personally would recommend writing a function which tells you which piece(s) to request, given the current list of pieces that the peers have. Initially, the function would just return any missing piece (i.e. without the rarest first algorithm). Once this works, you can change the function to return a random rarest piece.

What follows is the list of commands to be implemented: ubtorrent takes commands from users. I will be more precise on the output formats of these commands in the next few days.

4.1. metainfo

This command asks the client to show the information about the metainfo file. The output format looks something like this:

ubtorrent> metainfo
  my IP/port    : 127.0.1.1/9999
  my ID         : bcd914c766d969a772823815fdc2737b2c8384bf
  metainfo file : Dan Hill & Rique Franks - Sometimes When We Touch.mp3.torrent
  info hash     : 4a060f199e5dc28ff2c3294f34561e2da423bf0b
  file name     : Dan Hill & Rique Franks - Sometimes When We Touch.mp3
  piece length  : 262144
  file size     : 1007616 (3 * [piece length] + 221184)
  announce URL  : http://test/abc
  pieces' hashes:
    0  064b493d90b6811f22e0457aa7f50e9c70b84285
    1  d17cb90e50ca06a651a84f88fde0ecfb22a90cca
    2  20e82d045341032645ebe27eed38103329281175
    3  568c8a0599a7c1e2b3c70d8b8c960134653d497a

ubtorrent>

Everything is in the metainfo file or available locally (IP/port), except for the info hash value which you have to compute. (This has to be computed anyhow in order to send tracker requests.) The value of info hash is the SHA1 hash of the value of the info key in the metainfo dictionary.

Like in Project 1, your program should handle errors graciously. If the input .torrent file does not exist or if there were some errors in reading the file, for example, please do not crash. You can assume that the metainfo file (that we will test) is not greater than 8KB = 8192 bytes. If the given metainfo file is larger than that, you can quit the program and complain (to the screen). In the wild, metainfo files are often kept small, not more than 50KB.

Now, sometimes for debugging purposes you might want to display the metainfo file to the screen. However, as there are hash values in it, many characters cannot be displayed, causing the terminal to behave in unpredictable manner (e.g., change to Korean or Chinese fonts or something). To be safe, you should use hexdump to display a metainfo file:

hungngo@MYMACHINE:~/tmp$ hexdump test.torrent -c
0000000   d   8   :   a   n   n   o   u   n   c   e   1   5   :   h   t
0000010   t   p   :   /   /   t   e   s   t   /   a   b   c   1   3   :
...

I cut the rest of the output. You may find the functions strtol() helpful when trying to get the value of the info key out.

4.2. announce

This command asks the client to send a GET request to the tracker. When the response comes back, update the information to be used later. It also prints out the status line of the response (the first line which looks something like HTTP1.0 200 OK). The output may look like this:

ubtorrent> announce
++++ Tracker responded: HTTP/1.0 200 OK
 complete | downloaded | incomplete | interval | min interval |
---------------------------------------------------------------
 1        | 0          | 0          | 1686     | 843          |
---------------------------------------------------------------
++++ Peer List :
 IP               | Port
-------------------------------
 127.0.0.1        | 9999
   ... Tracker closed connection

(I suggest you store the dictionary in some be_node. Remember to be_free the node the next time an announce is called. The be_node is used in processing the command trackerinfo.)

4.3. trackerinfo

Prints the information contained in the latest tracker response. This is a subroutine which should have been called when announce is typed. So, the output is just part of the (last sucessful) announce output, without the status line:

ubtorrent>trackerinfo
 complete | downloaded | incomplete | interval | min interval |
---------------------------------------------------------------
 1        | 0          | 0          | 1686     | 843          |
---------------------------------------------------------------
++++ Peer List (self included):
 IP               | Port
-------------------------------
 127.0.0.1        | 9999
 127.0.0.1        | 9998
 127.0.0.1        | 9997

4.4. show

Prints the status of all current peer connections, including the choked/interested states and upload/download rates. The format looks something like this:

ubtorrent> show
ID | IP address | Status | Bitfield         | Down/s   | Up/s     |
--------------------------------------------------------------------
 0 | 127.0.0.1  | 0101   | 1111111111111111 | 0        |  59271
 1 | 127.0.0.1  | 0101   | 1111111111111111 | 0        |  59271

Down/s is the number of bytes downloaded per second on that connection. The status field has 4 bits, corresponding to the status of that connection: iam_choking (peer), iam_interested (in peer), peer_choking (me), peer_interested (in me).

4.5. status

Prints the status of the current  download: which pieces have been downloaded, which pieces are missing, the number of downloaded, uploaded, and remaining bytes. The format is something like this:

 ubtorrent> status
 Downloaded | Uploaded | Left | My bit field
------------------------------------------------
 1007616    | 0        | 0    | 1111111111111111

or

ubtorrent> status
 Downloaded | Uploaded | Left    | My bit field
---------------------------------------------------
 0          | 0        | 1007616 | 0000000000000000