Assignment #4 - Peer-to-Peer File Sharing Gnutella Style
Demo on Monday, November 17 or Tuesday, November18.
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. 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.
Every node should start up with the following input:
-
A directory containing local files intended to be shared through your protocol.
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.
-
IP addresses (or hostnames) of a few nodes already running in the system.
The starting node then contacts these nodes to establish them as neighbors. A
neighboring relationship between two nodes simply means they know each other's addresses (IP
addresses or hostnames). Of course, this input will be empty for the startup of the
first node. Note that this list may not contain all running nodes because that will
be infeasible when there are thousands or millions of nodes running in the system.
Below are the desired behaviors for peer-to-peer file searching through query flooding:
-
A search query can be initiated at any node with 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. 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 extremely rare in practice.
-
As long as all nodes in the system are connected, 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 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).
You will need a user interface for your system. A text-based interface is
sufficient, but a GUI would be most welcome :).
Your program should print out all activities including query
propagations and query hits at the runtime.
Testing:
You will need multiple machines in your testing. And others may do the same at the
same time. You may need to coordinate on using different port numbers so that your
programs don't to interfere with each other.
Turn-in:
This assignment will be primarily examined by a 20-minute demo with the TA.
The TA will send out information on how to set up a demo slot. The earlier you
sign up with the TA, the more available slots are there that you can choose from.
Once your demo slot is set, we will not be able to change it unless there is an
emergency.
You are also asked to prepare a README file which should serve as a high level
summary of your work, explain your design, what is and what is not realized in
your implementation. Moreover, it should describe the packet format for
neighborhood establishment and query propagation. The TA may (or may not) try to
run your program after the demo, so make sure your README file also describes
clearly how your program should be compiled and run.
Please make sure that you have a hard copy of the README
file ready at the beginning of your demo.
You should electronically turn in your source files, a makefile if needed, and the
README file before or right after the demo.
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:
At the absence of any emergency, you must make your arranged demo time. Otherwise
you will get no points for this assignment.