Link State Routing Fundamentals

Due Wednesday, March 4, 1998. Note that you will have other stuff to do in the meantime (mainly reading), so don't dawdle.

In this cnet assignment, you will implement a part of the 1980 ARPANET link state packet mechanism, but you will do no actual routing of data packets. Thus, you should not enable any of the application layers of your nodes. You should assume a reliable data link layer by using CNET_write_physical_reliable for all transmissions.

Your program's goal will be to make sure each node builds a complete picture of the network in the form of link state packets for each other node. This will, of course, involve flooding LSP's from each node. But before a node can flood its own LSP, it must build the LSP in the first place. This requires that each node come to know the identity of its neighbors. Thus, the first phase of your development should focus on the problem of...

Neighbor Discovery

When a node is booted, it knows how many links it has. This may be detectable by the hardware, or it may be part of the software configuration. In any case, your cnet nodes have the information (in nodeinfo.nlinks). What a node does not know, however, is the identity of the node on the other end of each link. "Neighbor discovery" refers to the process of finding out who's on the other end of each link.

Here is the neighbor discovery protocol you should implement:

• At reboot, each node should send some kind of "hello" message out on each of its links. The message should include the node's address (which is stored in nodeinfo.address, and can be set in the topology file by including the line "address = someinteger" inside the node's curly braces). For debugging purposes, you might also want to include the node's name (nodeinfo.nodename) in the hello message.

  Also at reboot, each node should initialize its own LSP to show no neighbors.

• When a node receives a hello message on link L, it should update its own LSP to include the neighbor at the other end of link L. It is common for this update to not represent a change in the LSP.
• Every 10 seconds, each node should say hello on each of its links. The ARPANET was a friendly place.
• If 20 seconds have passed with no packets arriving on link L, the node should consider L or the corresponding neighbor to be down, and it should update its LSP accordingly.

Flooding

• An LSP contains the address of the node whose LSP it is, a 6-bit sequence number, a 3-bit "time-to-live," and a list of addresses of the neighbors of the node in question (as well as the link costs for each link--you may consider all link costs to be 1 for this assignment).
• Each node sends out its own LSP to each of its neighbors at least once every 60 seconds. When doing this, a node will first set the LSP's time-to-live field to 7, and its sequence number to one greater than the previous sequence number. (If the previous sequence number was 63, the next sequence number is 0.)
• At reboot, each node should wait 90 seconds before sending its LSP to its neighbors. (It does, however, engage the neighbor discovery process by saying hello to its neighbors every 10 seconds.) Note that 90 seconds should be enough time for a new node to discover its neighbors and receive the LSP's from all the nodes in the network. Of course, at initial startup of the network, all nodes will wait 90 seconds, after which there will be a flurry of LSP flooding.
• Whenever the node changes its LSP (either because it receives a hello from a new neighbor or because 20 seconds have passed since an old neighbor sent any packets, hellos or otherwise), the node should flood its LSP immediately rather than waiting for 60 seconds to pass. If, however, the node is still waiting for the 90 second startup time limit to expire, don't flood the LSP when hellos or LSP
• When a node (e.g. node A) receives an LSP (e.g. for node B), node A compares the received LSP with the node-B-LSP, if any, that it has stored. If either of the following are true,
  1. The stored LSP has time-to-live 0.
  2. The sequence number of the received LSP is "greater than" the sequence number of the stored LSP. Here, M is considered to be greater than N if (M > N and M - N <= 32) or (M < N and N - M > 32).
  then node A
  1. discards the stored LSP for node B,
  2. stores the received LSP, and
  3. forwards the received LSP to each of A's neighbors except the neighbor that sent this LSP to A.
  Otherwise, A does nothing with the received LSP. (Note, by the way, that I was mistaken on 2/20 when I said that each forwarding operation includes a decrementation of the time-to-live field.)
• Every 8 seconds after an LSP is stored at a node, the LSP's time-to-live field is decremented until it reaches 0. LSP's whose time-to-live fields are 0 are not discarded (they are needed for routing data packets), but as described in the previous rule, they are considered "old" regardless of sequence number.

Some notes

Perhaps this is obvious, but I want to mention it anyway. You'll want to have a many-node topology file to test your program. Write your own, or use mine

Extra credit: Simulating October 27, 1980

Have fun. Keep in touch.