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 part, 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.
o Set SearchingForNeighborFlag = true.
o Select a host at random from the list of possible neighbors and set the
the tempNeighbor to this neighbor's Id.
o Set the tempNeighbor's lastTimeAHelloWasReceived member variable
to the current time.
o 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).
o 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
o Draw the graph.
o For which N is the graph connected.
o For each N, what is the average degree of the hosts (make a plot).
o For each N, what is the diameter of the largest connected component
(make a plot).
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.
