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