|
|
|
|
Project 2: Routing
- out: Wednesday October 12
- due: Wednesday October 26, at the beginning of class
- grading guidelines
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.
- 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. 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 you 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!
Efficient Routing (optional for extra credit)
Note that grades for the course are established without considering
extra credit. We then add any extra credit points. Doing EC is
entirely optional, and not doing them will in no way harm your grade,
even if everyone else in the class does the EC problems. We offer EC
problems as a way of providing challenges for those students with both
the time and interest to pursue certain issues in more depth.
Link state routing is a "mechanism" for controlling routes; it does
not specify the "policy" used for selecting which routes to use and
which ones to avoid. Clearly, the end user performance can vary
dramatically based on the route selection. For example, what if
certain wireless hops were very lossy? Shortest path routing might
choose those routes, even though the end user might be happier with
another path through more reliable links.
Part 2 is to design and implement a routing algorithm that chooses
better routes than the default selected by link state shortest
path. Better is of course in the eyes of the beholder - lower loss
rates, lower latency, higher bandwidth are all reasonable
choices. Note that your design can and should make use of the
facilities defined above (link state advertisements), but it need not
interoperate with the code from other student projects (e.g., you can
define extra protocol messages or carefully modify existing ones as
needed). As a first step, for example, you'll probably want to
implement something that measures the properties of a hop or a path,
so that you can use that information in setting link weights for the
shortest path computation or in choosing source routes for virtual
circuits.
Be sure to add to your turn in: a short description of your
design and a simple illustrative test case.
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, October 26:
- 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. You must do this before class on
the day that it is due. The code you send us should run correctly
if we invoke lib/Fishnet in the class distribution.
- In class on the due date, hand in one stapled
hard copy write up, with both partners' names on it, containing:
- A printout of the source code you submitted
electronically.
- A brief write-up (probably less than a page) of your design
decisions.
- A printout of 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. There is an extra credit component to this
project.
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
Print-out of captured output: 1/8 of total grade
Efficient routing (Extra credit)
|