Making Neighborhoods
In peer-to-peer networks such as gnutella, each host must search out other hosts. When a host finds another host, these hosts become neighbors. Often a host will continue to search for peers until a sufficient number of hosts have been found. Let's assume that a host will continue to search for hosts until it has N neighbors.
In this project, peer-to-peer neighborhoods are made and maintained. Each host maintains list of neighbors and sends hello packets to these neighbors every 10 seconds. If a host is on the neighbor list, and no hello packet is received from the host for 40 seconds, then this host is removed from the neighbor list. If a node does not have enough neighbors, then it selects an address (e.g., IP and port) at random and tries to become its neighbor.
Hosts
can be in two list: bidirectionalNeighbors list and unidirectionalNeighbors
list. Also temporaryNeighbor may hold a host ID. The lists are maintained
as follows.
- Every 10 seconds, each host sends a hello packet to the hosts listed in its bidirectionalNeighbors and unidirectionalNeighbors lists
and to its temporaryNeighbor, if it is searching for a new neighbor.
- Contained in the hello packet is a list of the Ids of the recently-heard-neighbors.
Recently-heard-neighbors are the bidirectionalNeighbors and unidirectionalNeighbors of the sending
host. A host's Id is its IP address and port. Note that the temporaryNeighbor
(if there is one) is not included in the list of recently heard neighbors.
- If a host receives a hello packet from a neighbor with its Id listed in
the list of recently-heard-neighbors, then this neighbor is listed as an bidirectionaNeighbor.
- If a host receives a hello packet from a neighbor and the host is not listed
in the list of recently-heard-neighbors, then this neighbor is put in the list
of unidirectionalNeighbors (if it is not already there).
- If a host does not get a hello packet from an bidirectionalNeighbor, unidirectionalNeighbor, or temporaryNeighbor (when there is one)
with the host's Id listed in the recently heard neighbors for 40 seconds,
then it assumes that it is not connected to the neighbor and removes the neighbor
from the active neighbor and semi-active neighbor lists.
- If the number of active neighbors is less than N and the SearchingForNeighborFlag
is false, then the host randomly searches for a neighbor. Searching for a neighbor
is as follows.
- Set SearchingForNeighborFlag = true.
- Select a host at random from the list of possible neighbors and set the the tempNeighbor to this neighbor's Id.
- Set the tempNeighbor's lastTimeAHelloWasReceived member variable to the current time.
- If the tempNeighbor replies, then it is put into either the bidirectional neighbor list or unidirectional neighbor list and SearchingForNeighborFlag is set to false (the search is done).
- On the other hand, if the time reaches 40 seconds past lastTimeAHelloWasReceived and SearchingForNeighborFlag is still true, then the SearchingForNeighborFlag
is set to false, indicating the the search is done (it has failed)
- Every now and then, print the status to the screen.
What to turn in
- Run the program with N equal to 1, 2, and 4.
- Turn in code, and output lists of active neighbors after the network has
stabilized.
- Collect active neighbor lists from other all other host. With these outputs
determine
- Draw the graph.
- For which N is the graph connected.
- For each N, what is the average degree of the hosts (make a plot).
- For each N, what is the diameter of the largest connected component
(make a plot).
- Extra credit (one point of the course grade)
- Add a feature that keeps the node from accepting too many neighbors
and redo the graph drawing for N=2, 4, and 7. Explain what happens.
Hints:
Useful C++ classes (This is just a .h function)
A couple of other useful functions
The .h file for a couple of other useful function
Initialization
A .h for the target platform
The above code uses the boost library. You can get the latest boost library from here. To include the boost library into your code, you jsut need to set your include path to include where ever you put the boost library. The end of these slides explain how to change you include path in MS Visual Studio.
Initialization code requires the port and a list of hosts to be set at the command line, e.g.,
neighbors.exe 10000 HostList.txt
where an example of listOfHosts.txt is here. Note that * means this host. So this files specifies that the application can probe this host on ports 10000-10005. If a host with ip 128.4.40.10 with port 10000 is also available to probe, then include the line 128.4.40.10 10000.
Here is a script that will open a bunch of MS Windows are run the program. This should be a bat script, so after you download it, rename it by removing the .txt. Also, you will likely need to edit the script to match your project name and fix the paths.
Here are some instructions on using Gephi to plot the graphs
These ppt slides are useful to understand this project.
Turn in screen shots that show the following
•Test that the system becomes stable
----•Turn in the time until stable
----•Stable: no node it search for a new neighbor, and it stays that way
----•Also, each node has at least the target number of neighbors
----•Do this for 10 nodes and N=3, N=7 (you select)
•Find a node A that has exactly N neighbors and B is one of the neighbors
----•Then close/kill B
----•Show that A finds a new neighbor
•Or Find node A where there are N+2 neighbors, B, C, D, …
--•Close B, C, D (so there is N-1 neighbors)
--•Show that A finds a new neighbor