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

Course home
 Using course email
 Email archive
 Lectures and readings
 Section and tutorials
 Midterms and exams
Lab information
 Getting lab accounts
 Unix tutorials

Project 2: Routing

  • out: Monday February 4
  • due: Friday February 22 (midnight)

In this phase, you will explore flooding and routing using the link state routing protocol. In order to accomplish this, we are going to first clarify the values to be used for the identifier field of the UDP packets that you used in the previous phase. If the identifier field is BEACON_MSG = 42 (a value inspired by Douglas Adams), it is a beacon message. If the value is BROADCAST_MSG = 43, then it is a packet that needs to be flooded. Further, if it is a BROADCAST_MSG, the packet format is as follows: Identifier = 43, TTL value (integer), Sequence number of message (integer), Source MAC address (12 byte string), Size of message (integer), Payload (sequence of bytes).


Your node "floods" packets with the identifier field set to BROADCAST_MSG so that it is sent to all other nodes. You must decide exactly how your flooding function will work (there is probably more than one choice) but it must be accomplished subject to the following constraints:

  • Flooding must deliver a copy of every packet that is sent by any node to all of the other nodes.

  • Flooding will fail to deliver a copy of a packet to all other nodes that will process it in a couple of situations. First, packets can be lost during transmission, e.g., corrupted due to noise on the wireless link. Second, as part of the flooding, you must implement functionality to update the TTL field when packets are forwarded. This will cause packets to be discarded without being forwarded if their TTL reaches zero.

  • Your flooding design must prevent packets from circulating indefinitely. This requires that your node works out when it has already performed its flooding work for a given packet and not flood it again.

Link State Routing

Your node must then 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 out of beacon messages.

  2. Link-state flooding. To tell all nodes about all neighbors. You will use the flooding code from the first part 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.

Here are your constraints:
  1. You should use the following format for link-state information. A LinkState packet is sent as a BROADCAST_MSG. The payload of the packet is: a packet identifier field indicating it is a linkstate packet filled with the value LINK_STATE_PKT=1 (integer) the MAC address of the node sourcing the link state packet (sequence of 12 bytes), the node's IP address (integer), number of neighbors (integer), and for each neighbor, a tuple of values containing the neighbors's MAC address (sequence of 12 bytes), the neighbor's IP address (integer), and a link metric (integer = 1 for now).

  2. 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.  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. Each node picks a random IP address. If it sees a link state packet sourced by a different node (indicated by its MAC address) who has picked the same IP address, the node simply chooses a new IP address to avoid conflict, if its MAC address is larger (i.e. the node whose MAC address is smaller retains the IP address it chose). You can think of this as randomized DHCP. (Define MAC address A to be smaller than B if strcmp(A,B) < 0).

  5. Introduce two new UDP packet types: Ping (identifier = 44) and PingReply (identifier = 45). Each of them carries the following payload: Source IP address (integer), Destination IP address (integer). The Ping and PingReply packets need to be forwarded based on the routing tables computed by the link state routing algorithm. When the Ping and PingReply reaches the appropriate destination, emit some indication that the message was received (through a debug statement, a pop-up window, or by an audible sound).

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?


Turn in your code and answers to the above set of question. Write only a few short sentences for each of these questions!


The slides from the help session are available in PDF format here.

Extra Credit

Use the code that you developed above to actual route the TCP connections though which you can issue the file directory listing and file fetch commands. Here are some hints to get you started with this part of the assignment. (This part is just to get you acquainted with the practical aspect of networking.)
  • Setup the interface IP with the following command that ensures there are no default routes:
    ifconfig wlan0 netmask

  • Setup the kernel route tables to make sure that all of your transmissions go out on the wireless interface:
    route add default wlan0

  • Enable packet forwarding on every device:
    echo 1 > /proc/sys/net/ipv4/ip_forward

  • If neighbor IP neigh is the next hop to the destination IP dest, you can install a route in the routing table using:
    route add -host dest gw neigh

  • After every link state update, you need to remove/update the route table entries. Take a look at man pages for how route works.

If you got the above steps to work, you can transparently create TCP connections that go through other intermediate nodes.

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