Distance Vector Assignment, due 10/27/95

Your assignment is to write a cnet implementation of a simple distance vector routing algorithm.

Simplifying assumptions

Unless you specify otherwise in your topology file using the address option, nodeinfo.address == nodeinfo.nodenumber. Furthermore, these numbers are consecutive integers starting at 0, so they are easily used as indices for an array. Go with the default, so addresses handed to you by the application layer can be used to index your distance vector.
Assume your network has no more than 20 nodes.
You might find it convenient to know at runtime the number of nodes in your network. If you call cnet with the -N flag, your code will have access to the global integer NNODES.
Each node knows the address of every other node. In particular, the addresses are 0, 1,...,NNODES-1.
Links never crash. Nodes might crash, but not links.

Distance vectors

Each node will have a distance vector, which is a list of distance vector entries, one for each node in the network. The distance vector entry for B stored at A should contain A's best guess at:

the number of hops from A to B
the address of the first node to which A should send packets bound for B
the link along which A should send packets bound for B
the time at which this entry was last updated.

When node A reboots, it should initialize its distance vector. Its initial entry for itself is easy (0 hops, hand to A, use link 0, time is nodeinfo.time_in_ms). Other entries should say hops = infinity.

Updates

Every once in a while (you are free to decide how often), each node should send an update along each of its links. An update sent by node A should contain A's entire distance vector. An update could contain other information if you want it to.

Before A sends an update, it should check its distance vector for old entries. Any entry that has not been updated for a while (again, you decide how long) should be eliminated. That is, the entry's guess at the number of hops between A and the node in question should be set to infinity.

Upon receiving an update from a neighboring node B, node A should compare each entry in the update with the corresponding entry in A's distance vector. Node A should change its entry for destination C if either

(the hops from B to C) + 1 < (the hops from A to C), and the first node on the route from B to C is not A,
OR
the first node on the route from A to C is B

I'll leave it to you to figure out what needs changing when A decides to change one of its distance vector entries.

Sending data packets

When node A receives a packet destined for node C (A could receive this entry from either its application layer or its physical layer),...well, what do you think should happen?

Advice

Use CNET_write_physical_reliable() and CNET_read_physical() as your data link layer.

You should develop your code in stages. For example,

Stage 1. Assume no nodes crash. Do not enable any application layers. Only send updates, and watch the distance vectors evolve from initial values to correct values. After debugging and thorough testing, save a copy of your code and never touch it again.
Stage 2. Allow one node to crash. Do not enable any application layers. After debugging and thorough testing, save a copy of your code and never touch it again.
Stage 3. Allow any node to crash. Keep those application layers disabled. After debugging and thorough testing, save a copy of your code and never touch it again.
Stage 4. Turn off crashing again. Enable the application layer of one node. Include in your Packet data structure a way to distinguish between updates and data packets, and modify your response to EV_PHYSICALREADY so as to forward data packets according to the advice of the distance vector. What do you do if the distance vector says the destination is infinity hops away? (See hotpotato.c for a reminder of how to use one random number generator.) Do not perform a CHECK on your call to CNET_write_application(), since that will terminate the program if packets arrive out of order, which they might. After debugging and thorough testing, save a copy of your code and never touch it again.
Stage 5. Leave crashing off. Enable all application layers. After debugging and thorough testing, save a copy of your code and never touch it again.
Stage 6. Leave crashing off. Enable all application layers. Restore the CHECK on your calls to CNET_write_application(), and arrange for the delivery of packets in order. After debugging and thorough testing, save a copy of your code and never touch it again.
Stage 7. How can you tell whether a node is still there on the other end of your link? Unfortunately, CNET_write_physical_reliable doesn't return an error when the node at the other end of the link is dead. This is getting ugly. We need a real data link layer here.

Grading

A good job on stage 3 is worth a B or B-. A good job on stages 3 and 5 is worth an A. Stage 6? A+. Stage 7? Good luck.

Jeff Ondich, Department of Mathematics and Computer Science, Carleton College, Northfield, MN 55057
(507) 663-4364, jondich@carleton.edu