CSE logo University of Washington Computer Science & Engineering
 CSE 461: Computer Communication and Networks (Winter 2007)
  CSE Home   About Us    Search    Contact Info 

Course home
 Home
Administrivia
 Overview
 Using course email
 Email archive
Schedule
 Lectures and readings
 Section and tutorials
 Midterms and exams
Assignments
 Homework
 Projects
Lab information
 Getting lab accounts
 Unix tutorials
   

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:
  1. Neighbor discovery. To determine your current set of neighbors. You will use the neighbor discovery code that you built in project 1.

  2. 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.

  3. 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.

  4. Forwarding. To send packets using the next-hops.
Here are your constraints:
  1. 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.

  2. 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.

  3. 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).

  4. 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.

  5. 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.

  6. 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.

  7. 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

  1. 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?

  2. 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?

  3. 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?

  4. What happens if link state packets are lost or corrupted?

  5. 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:

  1. 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.

  2. 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?

  3. 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.

  4. 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
 


CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX