Distance Vector Routing for a Self-Organizing Peer-to-Peer Network

This assignment builds on Project 2. In Project 2, neighborhoods were found and maintained. In this assignment, routing for the topology is be computed.

We will assume that each link has an administrative cost of one. Thus, the routing will compute the shortest path in terms of hops. The objective is to determine the routing table. For each destination, the routing table has three entries: the destination HostId, the next hop HostId, and the cost.

To find the routing table there are 3 steps.

  1. Whenever a hello packet is sent, the node that is sending the packet must include its current routing table.
  2. When a hello packet arrives from a neighbor, the routing table form the neighbor is saved.
  3. The forwarding tables from the nodes in the bidirectionalNeighborList are used to determine the routing table.

We will refer to the node where the program is running as thisHost. The forwarding table must satisfy the following properties:

  1. Each destination reported in one or more neighbors' forwarding tables must be included in the forwarding table.
  2. The cost to reach thisHost is zero.
  3. The next hop to reach thisHost is recorded as thisHost
  4. The costs to reach other destinations besides thisHost is the minimum of the costs advertised in the received forwarding tables plus 1.
  5. The node that advertises the lowest cost to a destination is the next hop in the forwarding table.

Hint 1: The first step to making a new forwarding table is to put thisHost in the table with a cost of zero. Then loop through the destinations from each bidirectionalNeighbor's routing tables. Add to the forwarding table only those destinations that are not already in the routing table. If a destination appears in two or more neighbor's routing table, then only put the one with the least cost into the forwarding table.

Hint 2: From Project 2, add a function to compute the forwarding table every time a hello message arrives. Then make a few changes in how hello messages are made (i.e., include forwarding table information) and how a HostID is sotred and copied.

 

Function ideas:

Change sendHelloToAllNeighbors to include the routing table as argument, i.e.,

void sendHelloToAllNeighbors(bool searchingForNeighborFlag,
list<NeighborInfo> &bidirectionalNeighbors,
list<NeighborInfo> &unidirectionalNeighbors,
NeighborInfo &tempNeighbor,
HostId &thisHost,
UdpSocket &udpSocket,
RoutingTable &routingTable);

in addition to the functions used in project 2

void makeRoutingTable(RoutingTable &routingTable, list<NeighborInfo> &bidirectionalNeighbors, HostId &thisHost);

Also, there have been some slight modification to these files

helperClasses.cpp (this one has changed)

someFunctions.cpp (the same as in project 2)

someFunctions.h (the same as in project 2)

neighbors.cpp (this file has changed)

target.h (the same as in project 2)

What to turn in:

  1. Turn in your code.
  2. Turn in output (time and node stamped routing table and neighborhood advertisements) that shows the routing table as it takes SEVERAL steps to converge after it starts. Include a plot of the topology and verify that the tabel is correct.
  3. Turn in output that shows the count to infinity problem.
  4. Run your program for several sizes of networks and different number of desired number of neighbors. For each trial, record the average distance between node pairs and record the maximum distance between node pairs. Make a table or plot that shows these values for different network sizes and desired number of neighbors. (You might consider changing your program to generate a file that can be read from Matlab or python and then using a script to compute averages and maximums.)