Assignment #4 - Peer-to-Peer File Sharing Gnutella Style
Due Friday, December 4, 11:59 PM.
Assignment overview:
In this assignment, you will implement the query flooding protocol used in Gnutella
(a peer-to-peer file sharing technology). It is
said that the two Gnutella inventors spent 14 days to design and implement a
prototype system. It should take you much less time in simply following their
ideas and implementing a small part of the complete protocol. You do not need to
add a file retrieval mechanism into the search system, which would be needed for a
complete file sharing system.
Requirements in detail:
A specification of the Gnutella query flooding protocol can be found
here.
For your relief, you are asked to implement a small part of the protocol, which will
be explained below. You will not need to read the Gnutella specification to complete
this assignment. You can simply consult it for inspiration.
The requirements we give below are not always specific. You can
design your own packet format and so on as long as systems running your protocol behave
as we specify. So your system may not work with Gnutella-compatible nodes, but nodes
implementing your protocol should be able to inter-operate. Your protocol should run
on top of a transport-layer protocol, e.g. TCP.
A key concept behind peer-to-peer technologies is that all the nodes are
functionally equal to each other. In particular, all the nodes will run the same code,
implementing the following:
-
Every node receives on its command line parameters a list of hostname:portnumber identifiers.
The node listens and accepts connections on the first port and treats the others in the list as neighbors in the flooding algorithm.
-
Every node examines its current working directory (once at startup) to discover a list of files to be shared.
You will need to gather the names of all files in the designated directory for later
searching. If you use Java,
File::listFiles() may do the trick. If
you use C/C++, you might need to use opendir(), readdir(),
and closedir() (see sample code here).
These are just hints to help you. You are certainly free to use anything you are
comfortable with.
-
Every node reads its standard input; each line of input defines an input filename prefix that is used to compose a search query, as described below. Note: If you think that listening to your network port and monitoring your stdin file descriptor (e.g. with the
select system call) is too hard, you may have each node split itself into two processes or tasks: one listens to the network port, one reads stdin and creates queries that it sends to the node's network port.
-
All events are logged to stdout in the following common format:
timestamp node {RECV|SEND} detail
where timestamp is in the format yyyy/mm/dd hh:mm:ss,
node is the node's hostname:portnumber identifer (from the command line),
RECV or SEND indicates whether something is being received or sent, and
detail is more information on the query or response being received or sent, including originator or destination, query string detail, etc.
Below are the desired behaviors for peer-to-peer file searching through query flooding:
-
A search query can be initiated at any node; the input is an input filename prefix. The
initiating node will examine local file storage for files with matching prefixes.
Then it will propagate the query to all its neighbors.
-
Every node, when receiving a propagated search query, will examine the local file
storage for matching files. Any matches will be returned directly to the query
initiator. It may (see exceptions later) then propagate the query to all its
neighbors except the one that it received the query from.
-
Obviously it is undesirable to have a node searching for a single query more than
once. You should be convinced that this can happen if there are loops in the system.
So you might need to let each query carry a query ID number such that each node
can ignore a query that it already handled before. Note that it is important to
let each query to have a unique ID number. This might sound easy but it really
isn't since queries can be initiated at different nodes independently. To simplify
your work, you can just use a random number for this purpose. There is a chance
to have multiple queries with the same ID, but it should be rare enough not to
happen when you demo it to the TA :).
-
As long as all nodes in the system are connected, you should be convinced that each
query should eventually reach every node in the system. However, this might not be
desired behavior when the system contains thousands or millions of nodes. A common
way to address this is to use a time-to-live (TTL) field in the query to limit the scope of query
flooding. The TTL field is set to an initial value at the query initiating node,
then it is decremented by one after every propagation. The node receiving a query
with TTL=0 will not propagate it any further. We will ask you to set the initial
TTL value at the demo.
Here is an illustration of what query flooding
looks like (with an initial TTL=2).
Turn-in:
Use the turn-in script to submit your source files, a makefile if needed, and a
README file describing:
- Known shortcomings of your implementation
(so the TA doesn't have to find them the hard way; he might miss something).
- Explanation of your design: At the least, it should describe the packet
format for neighborhood establishment and query propagation.
Grading:
-
50% for for basic query flooding implementation (without loop avoidance
and TTL control).
-
20% for loop avoidance.
-
20% for TTL control.
-
10% for the clarity of the README file in describing your design and implementation.
Late turn-in policy:
You may turn it in up to 3 days late; you lose 10% for each day late.