Project Assignment 2: Naming and Link-State Routing

Due: 13:00:00, May 27

Last update: Monday, 26-May-2003 14:03:25 PDT

Your assignment is to extend your Fishnet node with a naming service, so that you can ping hosts by their names, and a link-state routing protocol, so that messages are sent only to their destinations rather than being flooded.

Naming

Here are your constraints:

1. For the naming portion of this assignment you can use ONLY packets of type struct name_packet. These packets are designed for flooding information about naming entries throughout the network. Hostnames are named by you and null-terminated strings up to 12 characters including the null character. Empty strings should be taken to mean that the associated address is no longer alive in the Fishnet.

2. You should use sequence numbers to determine whether an entry is new. To do this, each entry should have its own sequence number, where a sequence number is a non-negative integer and higher values represent newer entries. The original sender of the entry writes the sequence number as well as an interval (specified in milliseconds) specifiying how long the entry should be considered valid. Hosts should check the time at which an entry is received and discard each entry after its interval expires. The interval should be at least thirty seconds to reduce the load on the network. Note: the purpose of the sequence number and the interval is to allow the network to recover from nodes failing and then rejoining the network.

A good design will keep the hostname to address listings at every node as up-to-date as possible, yet use very little bandwidth. You will probably want to modify your ping command so that it takes a hostname to ping as well as an address. You will probably want to add a new ls command that lists the nodes in the network. To see that your program is working, you might use the fishhead 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.

Link-State Routing

1. Neighbor discovery, to determine your current set of neighbors.

2. Link-state flooding, to tell all nodes about all neighbors.

3. Shortest-path calculation, to determine the next-hops for routes using Dijkstra's algorithm.

4. Forwarding, to send packets using the next-hops.

Here are your constraints:

1. You can ONLY use packets of type struct neighbor_packet to implement neighbor discovery. Conceptually, this is the same as using ping, but using a different type of packet produces a cleaner solution than overloading ping.

2. You can ONLY use packets of type struct link_state_packet to distribute link-state information. These packets are designed for flooding and are very similar to the naming packets. Each entry describes a directed link from node A to node B and has a sequence number and validity interval. Each entry also has a cost for the link, which is either 1 (one) if the link is up, or INFINITY if the link is down.

3. To run Dijkstra's algorithm, see the details in Peterson 4.2.3. Also note that you should not use the directed link AB in your database unless the directed link BA is also in your database and both have cost of less than INFINITY. The result of this algorithm should be a routing table containing the next-hop neighbor to send to for each destination address.

4. You should be able to forward any kind of packets defined in fish.h. You should forward them using the next-hops neighbors in the above routing table (rather than the broadcast to ALL_NEIGHBORS and flooding from assignment 1) except for the following packets: packets sent to the network broadcast address, which should be flooded as before; and packets of type struct neighbor_packet, which should only be used for neighbor discovery as described above.

You may assume the network size (the total number of currently running fish nodes) is no more than 500 nodes. Once you have completed all of the above, you should be able to ping any other node 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.

Discussion Questions

1. Why do we use a link for shortest paths only if it exists with cost less than INFINITY in our database in both directions? What would happen if we used a directed link AB in that direction regardless of whether there was a directed link BA with cost less than INFINITY?

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. How could you improve your naming protocol if you were designing it from scratch?

4. How could you improve your routing protocol if you were designing it from scratch?

Implementation

You can have a group up to four for this assignment. We provide skeleton source and a sample solution binary in ../public/cs123b-hw2.tar. This time you can implement the hw in multiple files, as the code size will be larger than the previous one. You can modify, add, delete the provided files. But we will compile your program by make hw2 command with the ieng9 gcc compiler and the original libfish.a and fish.h.

Please start early, the sample solution has over two thousand lines of code. If you have enough people, you can do parallel development. Some can work on the naming part and the others work on the routing part. Since naming service is on top of routing, you can use the previous flooding code to route name packets first. When you finish link-state routing, you can use naming service to test it. If you run into some problem, double check the documentataion in fish.h and this web page.

Testing

For a simple test, run a four node private fishnet (using your program only, not the sample solution), with each node running in a separate window. Make the nodes form a ring network (see ./fishhead -h and look for ring). 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. You can also try to specify a low background loss rate (e.g. 0.01), and see how the network handles lost packets.

Turnin

1. Login into ieng9.ucsd.edu

2. Make sure "make hw2" compiles your program at ieng9

3. Put all team member names and emails at the end of hw2.c

4. Answer the discussion questions in the end of hw2.c

5. Change to parent directory of the code, for example

   ~/hw2% cd ..
   

6. If you have core dump files, please erase them first. Then pack all files into a tarball called hw2.tar in the parent directory

   ~/% tar cvf hw2.tar hw2/
   

7. Turin the hw2.tar

   ~/% turnin -c cs123b hw2.tar
   

Grading

1. Program completeness, correctness and robustness (20 points)

2. Program structure (2 points)

3. Discussion Questions (8 points) - This part will NOT be graded if you did not write the code

(Potentially) Frequently Asked Questions

1. Do we need to check packet checksum?

   Yes, and you can use the provided checksum functions in cs123b-hw2.tar .

2. Should we use the provided dijkstra function

   No, and we encourage you to implement your own.

3. Should we assume the network size, address range, ttl etc?

   Different than hw1, this time you have to be more strict. The principle is, you are free to do things if fish.h or this page do not explicitly define the constraints. For example, the ttl limit is defined in fish.h as MaxTTL, so you should not accept packet with ttl larger than MaxTTL. If there are ambiguities and conflicts, contact us by posting on the message board (preferred) or by email.

4. Does the input/output formats have to be the same as the provided sample solution

   No, but please provide information about how to use your program. In particular, many of you are implementing based on observing the sample solution behaviours. The sample solution might not be perfect (so is any software) or the most efficient, although we will fix the bugs, it is provided to help you develop your own better solution, not to help you learn to clone software.

UCSD CSE123b Communications Software