|
|
|
|
Project 2: Routing
Your assignment is to extend your Fishnet node to support efficient
routing. In project 1, you were able to send packets from a source to
a destination using flooding. In this project, you will route packets
hop-by-hop through the network, having packets propagate through a
path, only involving nodes enroute to the destination.
Link State Routing
Your node must implement link-state routing to contruct a routing
table, and use this routing table to forward packets towards their
destination. You should read about link-state routing in Peterson
4.2.3. Note that we are not implementing OSPF, but a different
and simpler link-state protocol. A link-state protocol generally
involves four steps:
- Neighbor discovery. To determine your current set of
neighbors. You will use the neighbor discovery code that you built in
project 1.
- Link-state flooding. To tell all nodes about all
neighbors. You will use the flooding code that you build in project 1
to disseminate link-state packets.
- Shortest-path calculation using Dijkstra's algorithm.
To build and keep up-to-date a routing table that allows you to
determine the next-hop to forward a packet towards its
destination. Bulk of this code will be provided to you.
- Forwarding. To send packets using the next-hops.
Here are your constraints:
- You should use the LinkState class to format link-state
information. A LinkState object contains a list of neighbors for a
given node. Note that the link state information is the "payload"
(packet contents) of a packet with a normal packet header. The pack
method of the LinkState class should be used to turn the LinkState
object into a byte array before putting it into a packet that uses the
Protocol.LINK\_INFO\_PKT protocol.
- You should use your solution from assignment 1 to flood
the link state information throughout the network, so that all nodes
know which nodes are neighbors of which other nodes. A key design
choice is when to send out a LinkState packet periodically?
Immediately after the neighbor list changes? A key design criterion is
to distribute link state information using as few packets as possible,
while keeping nodes as up to date as possible.
- See the details in Peterson for a good suggestion on how
to implement Dijkstra's algorithm. (We will be providing much of
the code for this module.) The result of this algorithm should be
a routing table containing the next-hop neighbor to send to for each
destination address. Note that you should not use a link in your routes
unless both ends of the link agree that it is available (that they are
neighbors).
- You should forward packets using the next-hop neighbors in
your calculated routing table. The exception is packets sent to the
network broadcast address (e.g., for neighbor discovery or sending link
state information); these should be flooded. Note, then, that when your
node receives a packet, it may perform one of three actions: (1) if the
packet is destined for the node, it will "deliver" the packet locally;
(2) if the packet is destined for another node, it will "route" the
packet; (3) if the packet is destined for the broadcast address, it
will both deliver packet locally, and continue flooding the packet,
subject to the TTL and "floods do not propagate forever" constraints
from the last project.
- Add two commands to your node: "dump linkstate" to dump
all of the link state advertisements used to compute the routing table,
and "dump table" to dump the contents of the routing table. You may
find this more convenient than logging the entire routing table after
every change.
- In a separate packet, but transmitted in the same way
(i.e., flooded, and sent at similar times) as the link state packet,
you should transmit a short text name to more easily identify your
node. The protocol should be Protocol.NAME\_PKT. The packet contents
should be the name of source node. For example, this allows you to
associate the node address 16 with the hostname "brian-node" . You
should also keep track of the names advertised by other nodes.
- Modify your ping command so that it can take a hostname to
ping instead of an address. Also, add a new "ls" command that lists the
nodes in the network. To see that your protocol is working, you might
use the simulator or trawler to set up a small network and see that
your "ls" command at one node tracks the fishnet membership as you stop
and start nodes.
Once you have completed all of the above, you should be able to ping
any other node (by name!) in the network, and have a packet travel to
that node and back without being unnecessarily flooded throughout the
network. To see that your protocol is working, you might set up a
small ring network, use ping to test whether you can reach remote
nodes, and then break reachability by stopping a node on the path so
that ping no longer receives a response. Your routing protocol should
detect this and repair the situation by finding an alternative
path. When it does, ping will work again. This is the turn-in
exercise. Congratulations! You have a real, working network!
Discussion Questions
- Why do we use a link for the shortest path computation
only if it exists in our database in both directions? What would happen
if we used a directed link AB when the link BA does not exist?
- Does your routing algorithm produce symmetric routes (that
follow the same path from X to Y in reverse when going from Y to X)?
Why or why not?
- What would happen if a node advertised itself as having
neighbors, but never forwarded packets? How might you modify your
implementation to deal with this case?
- What happens if link state packets are lost or corrupted?
- What would happen if a node alternated between advertising
and withdrawing a neighbor, every few milliseconds? How might you
modify your implementation to deal with this case?
Write only a few short sentences for each of these questions!
Turn-In
For this and future assignments, you need to demonstrate that your
node works in the class network as well as turn in both electronic and
paper material as follows.
For the due date, Wednesday, January 24:
- Run a four node fishnet simulation or emulation. Make the
nodes form a ring network. From one node, ping the other node that is
not directly connected, observing which way it travels around the ring.
Stop the intermediate node the messages passed through. Repeat the ping
when routing has repaired paths and it travels along an alternate path.
Capture the entire output using, for example, the script command. Make
sure that we can see what packets are being sent and received during
the exchange of linkState messages and as the ping goes across the
network. Mark the printout to tell us what is going on.
- Make your node join our Trawler to be able to talk to our
node (details on where the Trawler is running will be emailed out
later). Make sure your node is exchanging neighbor and routing packets
with our node. What is the name of our node?
- Use the turnin program on the Linux servers to
electronically submit one or more java files containing the entire
contents of the proj directory in other words, all the files
containing the source code for your solution. The code you send us
should run correctly if we invoke lib/Fishnet in the class
distribution.
- Also hand in a soft copy, with both partners' names on it,
containing:
- A brief write-up (probably less than a page) of your
design decisions.
- Any output we have asked you to capture.
- Short answers to the discussion questions.
Have Fun!
Grading guidelines
Each part of the project is graded on a 5 point (0-4) scale, multiplied
by the
weight of the part. The weighted grades from all parts of the project
are added
together to produce the final grade.
The five point scale is based on how well you show your understanding
of the
problem, and in case of code how well your implementation works:
0 - nothing turned in
1 - show minimal understanding of the problem / most things don't work
2 - show some understanding of the problem / some things work
3 - show a pretty good understanding of the problem / most things work
4 - show excellent understanding of the problem / everything works
The weights for the parts of project 2 are:
Link state routing implementation: 1/2 of total grade
Write-up of your design decisions: 1/4 of total grade
Answers to discussion questions: 1/8 of total grade
Output of the test runs: 1/8 of total grade
|