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 each N you try, note whether the graph is connected or not connected.
- For each N you try, what is the average degree of the hosts.
- For each N you try, compute the diameter of the largest connected component
Extra credit (one point of the course grade)
- Add a feature that keeps the node from accepting too many neighbors and 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

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, …