This assignment builds on Part 1. In Part 1, neighborhoods were found and
maintained. In this part, 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 Part 1, 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 part 1.
void makeRoutingTable(RoutingTable &routingTable, list<NeighborInfo>
&bidirectionalNeighbors, HostId &thisHost);
Also, there have been some slight modification to these files. (See Hints)
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.)
