Corporate and Professional Publishing Group
ISBN 0-201-63442-2 * Hardcover * 688 pages * 1997
Book
Description · Preface
· Glossary
· Bibliography
· Solutions
· Slides
· Simulator
· Exercises
· Errata
· Cover
(73K) · Ordering
Information · C&P
Welcome Page.
Assignment designed by Snorri Gylfason.
The two fundamental routing algorithms in packet-switched networks are distance-vector and link-state. Your assignment is to implement link-state router in the REAL simulator (This is described in Section 11.6 in the textbook).
Before you start By now you should feel comfortable using the
REAL simulator. If that is not the case, you should read the
manuals for REAL. The are accessible online: http://www.cs.cornell.edu/home/skeshav/real/man.html.
You will not be able to do this assignment without
understanding REAL in some detail. If you have specific
questions about REAL, mail skeshav@cs.cornell.edu.
Please also check the REAL
FAQ.
Details
Each node in the network represents a router. It contains a next-hop
table for each node in the network. Each entry in the next-hop
table tells us which physical link to choose so the packet will
reach its destination at minimum cost.
For example, if we wanted to send packet from node 3 to 12, we
would look up in the next-hop table in node 3 and see that it is
best to send the packet to node 4. When the packet reaches node
4, that node does the same (using its own next-hop table) and
will find out that it is best to send the packet to node 11, etc.
In this assignment we will simulate one type of failure, link
failure (but not a failure of a router). A router must be able to
discover a failure and recovery of a link to its neighbor. For
example, if the link between node 3 and 4 fails, both nodes 3 and
4 must have some mechanism to discover the link failure. They
must as well discover when the link is up again.
The mechanism you should use in this assignment is a simple HELLO
protocol. Each router sends each of its neighbors a HELLO packet
every 10.0 time units (even if it thinks a link to that router is
down). When a router gets a HELLO packet it sends a HELLO_ACK
packet back. When the sender of a HELLO packet receives a
HELLO_ACK packet it knows that the link is alive. But if it
doesn't receive an ack it doesn't necessarily mean that the link
is down, maybe the ack packet was simply lost or corrupted.
Therefore a link isn't considered down except if for a series of
HELLO packets we didn't receive an ACK (here you should use 5
missing acks as a failed link).
Example:
Node 3 has two neighbors, 1 and 4. Note that 3 of course also
receives HELLO packets from 1 and 4). Note also that (a) you need
not print the following out when submitting the assignment: this
is only an example to show you how HELLO works (b) the times here
are indicative of the progress of time: they are not the times
you will actually see in the simulation.
Time 10.0: 3 sends HELLO to 1 and 4
Time 10.1: 3 receives a HELLO_ACK from 1 (therefore
link 3-1 is up)
Time 20.0: 3 sends HELLO to 1 and 4
Time 20.1: 3 receives a HELLO_ACK from 1 (therefore
link 3-1 is up)
...
Time 50.0: 3 sends HELLO to 1 and 4
Time 50.1: 3 receives a HELLO_ACK from 1 (therefore
link 3-1 is up)
Time 60.0: 3 noticed that it has sent 5 HELLO packets
to 4 without getting any ACKs so the 3-4 link is
considered down.
Time 60.0: 3 sends HELLO to 1 and 4 (note: 3
still tries to send HELLO packets to node 4)
Time 60.1: 3 receives a HELLO_ACK from 1 (therefore
link 3-1 is up)
...
Time 230.0: 3 sends HELLO to 1 and 4 (assume the 3-4 link
is still considered down)
Time 230.1: 3 receives a HELLO_ACK from 1
(therefore link 3-1 is up)
Time 230.2: 3 receives a HELLO_ACK from 4 (so link 3-4 is
also up again)
Whenever a router detects that a link is down it sends an LSP
with an infinite cost for the link to all other routers.
Similarly when a router detects that a link has recovered, it
sends an LSP with the link's cost to all other routers.
The LSP packets are not sent directly to all other routers but by
using controlled flooding (as described on page 305 in the
textbook). An LSP packet contains the router's ID, the neighbor's
ID (the node on the other end of the link), and the cost of the
link. When a router gets an LSP packet it stores it in its
LSP database. Then it recalculates its next-hop table using the
Dijkstra algorithm (Section 11.6.2 in the textbook).
How to do the assignment
Read Chapter 11 in the textbook. Read Section 11.6 very carefully and make sure you understand it.
In this assignment you use the REAL simulator as before. Your code should be in a file called "sim/sources/link_state_router.c". This files contains the control function for the router. The name of that function should be "link_state_router()" (similar to "ecn_dummy.c" and "ecn_dummy()").
Put the file "link_state_master.c" into the "sim/sources" directory (see below), and the file "link_state.l" into the "sim/ecn" directory.
Change the following lines in the two makefiles:
functions = link_state_master.c link_state_router.c functionobj = link_state_master.o link_state_router.o
sourceobj = sources/link_state_master.o sources/link_state_router.o
Note: you may have to do "make depend" to create necessary dependencies for the new files.
The "link_state_master.c" file contains a code for a
control node which at certain time changes the status (up/down)
of links in the network. The master notifies you on its actions
by printing information on the screen.
The "link_state_master.c" contains a table of link
state change events. Now it contains only a few events, but while
testing it you should add more events. You do that by simply
adding lines to the "link_changes" array near the top
of the "link_state_master.c" file. The format is
described in there. (Note: You may also need to change the
"end_simulation" parameter in the
"link_state.l" file, if you want your simulation to run
for longer time).
First implement the HELLO protocol. When a node x notices that
a link to node y is down, print out "<time>: Link
<x> - <y> is down". Use a similar printf when a
node x discovers that a link is up again. Test it and make sure
it works.
Both HELLO and HELLO_ACK packets should be a DATA packets. Use
the first byte of pkt->data to identify the type (HELLO or
HELLO_ACK).
Neighbors
This is a function which you can use to discover the neighbors
of node 'node'. The second parameter is an array of int (it
should be at least at size 12). The function puts the neighbors
into the array and returns the number of neighbors.
Example: For node 7 (which has 3 neighbors: 5, 8, 9), the
function should return 3 and the first 3 elements of the array
you past into the function should contain 5, 8 and 9.
int find_neighbors( int node, int neighbors[] ) {
gredgeptr edge;
int neighbors_cnt;
neighbors_cnt = 0;
edge = Graph->edges;
while ( edge != 0 ) {
if ( edge->node1->nodedata->nodeid == node ) {
neighbors[neighbors_cnt++] = edge->node2->nodedata->nodeid;
}
if ( edge->node2->nodedata->nodeid == node ) {
neighbors[neighbors_cnt++] = edge->node1->nodedata->nodeid;
}
edge = edge->next;
}
return neighbors_cnt;
}
Timer
It is easy to set up timers in REAL. Simply create a packet of
type TIMER and call set_timer() to activate it. You can actually
choose any type you want, as long as the type is defined in file
kernel/config.h.
make_pkt(pkt); pkt->type = TIMER; set_timer( 10.0, pkt ); /* The first argument is the time until the timer event
* (in seconds). This should be a float. */
After 10.0 time units the node receives a TIMER event.
switch (pkt->type) {
case DATA:
...
case TIMER:
/* You can now set another timer here if you want */
free(pkt); /* this frees the timer packet */ ... }
Next you should implement the LSP part. An LSP should be a DATA packet (like HELLO and HELLO_ACK). You should use the first byte of pkt->data to distinguish it from the HELLO packets. On link state change (and *only* on a link state change), create and send LSP packets to each of your neighbors. Implement a subset of the controlled flooding protocol described in the textbook. Specfically: (a) no need to ack LSPs (b) don't age LSPs (c) no need for a lollipop sequence space (d) no need to worry about network partitioning. You do not need these refinements because, in this assignment, routers never go down. You can use any data structure you want to store the LSPs, but it is most convenient to store the information in two parts: (a) an array that tells the latest sequence number received from each router (this tells you whether or not to forward the LSP when flooding), and (b) a Graph structure (defined in src/graph.h) that stores your notion of the topology (be sure that you make a local copy of this structure, instead of overwriting the global!). Storing the topology in the graph structure will allow you to use Dijkstra's routing algorithm already provided in file sim/kernel/routing.c.
When a router receives a LSP packet changing the current state, it must recalculate its next-hop table. To do that you should implement the Dijkstra algorithm (Section 11.6.2 in the textbook) or modify source for the algorithm from the Net. If you want to implement your own version of the algorithm, be careful to test it on a simple example. Even though the algorithm looks simple it is quite easy to make mistakes while coding it, and a tiny bug may cause the rest of the assignment to fail. It is essential to get it right. Make sure you understand it completely before you start coding it (I suggest you go through the algorithm by hand at least once). Implement it separately (not in the simulator) to begin with, test it carefully and make sure it works as it should. Then, plug it into the simulator.
Note: the description in the book is slightly imprecise. When it says 'pick' a node in step 2, that means remove it from set T. So, even if it is not added to P, it will still be removed from T. You will understand this better if you step through the example in Figure 11.11.
The next-hop table should be a global array (i.e. outside the "link_state_router()" function) defined as:
int g_next_hop_table[12][12];
g_next_hop_table[2][5] should contain the next hop information going from node 2 to 5. Since each router is an individual host, each router must only read/write its own row of the table.
When a router has recalculated its row of the g_next_hop_table
it must do two things.
First it should print out the next hop values in a single line of
the following format:
<time>: Next hop for <node> = 1:<hop to 1>, 2:<hop to 2>, ... , 12:<hop to 12>
Example
1321: Next hop for 3 = 1:1, 2:1, 3:3, 4:4, 5:1, 6:1, ... , 12:4
And secondly it must call a function named "sanity_check" defined as:
void sanity_check( int **table )
The sanity_check function checks whether the routing table is consistent. Essentially, it tests that (a) the next hop is actually a neighbor, and (b) for randomly selected source and destination, following the routing tables will let you reach the destination from the source. For instance, we may pick source 3 and destination 9. We will use g_next_hop_table [3][9] to find the next hop towards 9. We will then follow the hops indicated by your table and make sure we reach 9. You may want to write your own sanity check algorithm. We will plug in our own sanity check to test your implementation. Note that on a link failure, the routing table is INCONSISTENT. So, sanity check should and will fail until consistency is regained. Do not worry if sanity check fails!
Note that even though the description of the assignment is quite long the assignment itself is fairly simple.
What to submit (IMPORTANT) You should send in only one file "link_state_router.c" by email (to snorri@cs.cornell.edu).
Grading Your implementation will be tested on a different
network topology. It will be of the same, or smaller, size (so
your next-hop table can be of size 12), with the same assumptions
as above - like links of equal cost 1000, and no router failures.
We will test the sanity of the routing tables at the end of the
simulation.
The assignment will be binary graded, 0 or 1.