is:
Due: 15 October 2003 at 3am EDT. You have more than two weeks. Start tonight, ask questions if you have problems. Work as if this homework were due on October 8th and you were to get a one week extension!
The purpose of this homework is to convince yourself (and me!) that you understand the essential elements of Distance-Vector routing protocols.
You will be writing a very simple routing daemon simulation. The
simulator reads a file describing the network being simulated. Each
line of the file represents a (simulated) router; the fields of each
line are the name of the router, the prefix it is advertising, and the
names of its neighbors. The name of the file containing the
description of the network is passed as the first argument to the
simulator. The second argument is the update period, in seconds, of
the simulated routing messages.
For example, the file describing the network in this picture:
is:
A 10.0.0.0/8 D E B B 128.59.0.0/16 A C E C 192.4.13.0/24 B F D 135.207.16.0/20 G A E E 12.103.123.48/27 A B G F H D F 209.128.64.0/20 C E H G 128.96.0.0/16 D E H 207.140.168.0/24 E FThe names of the nodes can be of arbitrary length, but I didn't feel like typing!
While the simulation is running, the simulator responds to the following commands:
p node1 [ node2 [ node3 [ ... ]]]
prints the current routing tables of the listed nodes.
p * prints the routing tables of all nodes.
p without an argument does nothing!
c node1 [ node2 [ node3 [ ... ]]]
prints the current routing tables of the listed nodes once every update period.If a c command is already active and another one is issued, only the new list of nodes will be printed from then on.
c * prints the routing tables of all nodes once every update period.
c without an argument stops the periodic printing of routing tables.
s node1 node2 "severs" the link between the two
nodes; that is, node1 will not "hear" messages from
node2 and vice versa. Invoking this command on a link that is already severed has no effect.
r node1 node2 "restores" the link between the two nodes. The r command cannot be used to add links that did not exist in the configuration file, only to restore links previously severed with the s command. Invoking this command on a link that has already been restored has no effect.
d nodetakes the node down (the node stops sending routing information). Invoking this command on a node that is already down has no effect.
u brings the node back up after a d. Invoking this command on a node that is already up has no effect. Again, this command cannot be used to insert new nodes into the topology, only to bring back up nodes that were taken down with a d.
q quits the simulation.
The routing table is the list of known routes, each route being a destination prefix, the next hop router, the cost to the destination, and how many update periods it has been since that route was heard. The names of nodes can be arbitrary strings, but I recommend that you keep them as single letters when testing things. To keep things even simpler, you may want to use the ASCII value of the first letter of the node name as the top-level octet of the prefix you are advertising, so that when you print routing tables to verify that your program is working you don't have to remember who originated a prefix! All links are to be of unit cost (i.e., the cost metric is the hop count. A hop count of 15 is infinity. Routes that have not been heard from for six update periods expire.
Verify that your simulation works at boundary conditions, such as single-node networks (no routes will be advertised, but please don't dump core!), or two-node networks linked by single link. Don't limit yourself to getting the network shown in the picture.
Now, for the deliverables:
1/2 credit: Implement a rudimentary simulation; don't worry about split horizon, poison reverse, etc. Let counting-to-infinity take care of unreachable routes. Verify that you are coming up with the right routing tables, and that taking routers or links down gets the simulation to converge to different routing tables.
1/4 credit: Add split horizon to the routing decisions. Is convergence any faster?
1/4 credit: Now add poison-reverse. Obviously you should not do this unless you've also done split horizon. What do you observe?
Extra credit (up to 1/2 credit): Implement additional features (such as holddown timers) that speed up convergence. Do they?
$Id: index.html,v 1.2 2003/10/03 05:41:22 ji Exp ji $