In this puzzle you will implement a Link-state routing protocol. Before you start this assignment you should read chapter 11 in the textbook carefully, especially section 11.6 (Link-state routing).
We installed a new version of Entrapid. In includes some new features and some bug fixes. It is located in the same place as before and you use it the same way. There are three changes, one important and two minor.
In the network for the puzzle each virtual machine represents a router. On each virtual machine you will run your routing protocol (in this document we refer to the program that implements the routing protocol as the routing protocol). Normally routing protocols run in user-space, but the actual routing is done by the kernel. The purpose of the routing protocol is to detect changes in the network topology, tell others about the changes, and update the routing table in the kernel. In other words all the control is in the routing protocol but the kernel takes care of the actual IP forwarding. In high performance routers the forwarding is usually done in hardware but the control in software (for example on a normal PC running FreeBSD).
You should use the following topology for this assignment. The addresses in the image are subnet addresses.
The routing table contains information on where to route incoming IP packets. Since the forwarding of a packet depends completly on information from the routing table it must have complete information for each possible destination. In practice this means that on a real network you need a routing entry for each possible subnet reachable on the Internet. But fortunatelly the Internet has hierarchical structure and you access the rest of the Internet through some gateway router. You can set a default routing entry in your routing table toward that gateway. If there is no routing entry for a packet then the default route is used. It therefore reduces the size of the routing table dramatically. It is required in FreeBSD to have a routing entry for default route, but since we are dealing with such a small network here it is up to you if you update the default route entry (just set it as the address of one of the node's neighbor).
The routing table is a next-hop table. It basically only have information about to which interface (of its neighbor) it should forward a packet. Generally you want to get a packet to its destination in as few hops as possible. In this assignment you will implement a link-state protocol. Your routing protocol must therefore keep track of the current topology for the whole network. When the topology changes (e.g. when a link fails) your routing protocol must update the current topology and calculate shortest-path to all possible destinations. Then you update your routing table based on the shortest-path information. You do not tell the routing table the whole path but only the next-hop for each destination. This may sound simple but there are lots of problems. One is that if you do not have consistency in routing tables in the network you might get routing loops. See the textbook for more detailed description of problems with link-state routing.
In both Unix and NT we communicate to the network through something called interfaces. Usually an interface is a front-end of a device-driver for some network card, usually an Ethernet card. But there are other types of interfaces, such as the loopback interface (which sends all packets to the local machine) and the SLIP interface (Serial Line IP). You can attach a network address to interfaces (see ifconfig later in the document). For example the IP address 127.0.0.1 is usually attached to the loopback interface, and the IP address of the machine is attached to the Ethernet interface. If you have more than one Ethernet card in your machine then each of them needs its own IP address. It is therefore wrong to talk about an Ethernet address of a machine because it is in fact the interface that has the address. Routers have multiple interfaces and need therefore multiple IP addresses. When you want to send something to a machine that has multiple addresses you can send it to any of the interfaces it has. You may have noticed in previous puzzles that gethostbyname returns an array of addresses. Now you know the reason for that.
In the simulator we have full overview of all the traffic on the virtual network. We have modified the popular snooping utility tcpdump slightly such that it listens to all wires instead of only one. To snoop network traffic on the network do:
% tcpdump -h
tcpdump: listening on 15000 babbage
tcpdump: WARNING: compensating for unaligned libpcap packets
->m0:broadcast:w0:0:200:-14:-36:-44.000000 arp who-has m2 tell m0
->m2:m0:w0:200:400:-14:-36:-44.000000 arp reply m2 is-at 0:1:0:22:7a:88
->m0:m2:w0:400:600:-14:-36:-44.000000 m0 > m4: icmp: echo request
->m2:broadcast:w3:600:800:-14:-36:-44.000000 arp who-has m4 tell m2
->m4:m2:w3:800:1000:-14:-36:-44.000000 arp reply m4 is-at 0:1:0:24:d2:c8
->m2:m4:w3:1000:1200:-14:-36:-44.000000 m0 > m4: icmp: echo request
->m4:m2:w3:1200:1400:-14:-36:-44.000000 m4 > m0: icmp: echo reply
...
Because we are snooping multiple wires we need to add information at the beginning of each line about on which wire the packet is travelling (source,destination,wire). This is done by the -h option.
You can use the output of tcpdump to generate an animation of your network traffic. This is what you need to do:
You can see examples of generated animations at http://www.ensim.com/animate/.
Before you start implementing the routing protocol it is very wise to spend some time on getting to know the following utility. Read the man pages for them and try them out. You will find them all in /home/cs519/entrapid/bin.
The ifconfig utility is used to display and configure interfaces. To list all interfaces for a machine type:
% ifconfig -a
lo0: flags=8049<UP,LOOPBACK,RUNNING,MULTICAST> mtu 16384
inet 127.0.0.1 netmask 0xff000000
vx0: flags=8843<UP,BROADCAST,RUNNING,SIMPLEX,MULTICAST> mtu 1500
inet 128.1.0.2 netmask 0xffff0000 broadcast 128.1.255.255
ether 00:00:50:23:21:08
vx1: flags=8843<UP,BROADCAST,RUNNING,SIMPLEX,MULTICAST> mtu 1500
inet 128.3.0.1 netmask 0xffff0000 broadcast 128.3.255.255
ether 00:01:50:23:21:08
...
%
In this puzzle we take down links by taking down interfaces. You can use ifconfig to check for statuses of links while testing or to look up IP addresses for interfaces.
The netstat utility is used to display certain network information (such as routing tables) for a machine. For example to display the routing table do:
% netstat -rn
Routing tables
Internet:
Destination Gateway Flags Refs Use Netif Expire
default 128.3.0.2 UGSc 0 0 vx1
127.0.0.1 127.0.0.1 UH 0 0 lo0
128.1 link#2 UC 0 0
...
128.15 128.6.0.2 UGSc 0 2 vx3
128.16 128.5.0.2 UGSc 0 0 vx2
%
The route utility is used to modify the routing table for a machine. For example to add a route for subnet 128.14.0.0 and tell it to use gateway 128.5.0.2 (the next-hop) do:
% route add 128.14.0.0 128.5.0.2
add net 128.14.0.0: gateway 128.5.0.2
%
Ping is a useful tool to test reachability of a machine. It sends a packet to the destination machine and waits for some time for a reply. When the ping packet reaches its destination a reply is sent back. To send two ping packets to m8 type:
% ping -c 2 m8
PING m8 (128.14.0.2): 56 data bytes
64 bytes from 128.14.0.2: icmp_seq=0 ttl=253 time=10.130 ms
64 bytes from 128.14.0.2: icmp_seq=1 ttl=253 time=10.870 ms
--- m8 ping statistics ---
2 packets transmitted, 2 packets received, 0% packet loss
round-trip min/avg/max = 10.130/10.500/10.870 ms
%
Another useful tool is traceroute. It will not only test for reachability of a machine but also give you the path it took to reach the destination. This is very useful to test the routes you set up. To get the path to m8 type:
% traceroute m8
traceroute to m8 (128.14.0.2), 30 hops max, 40 byte packets
1 m4 (128.5.0.2) 12.316 ms 2.060 ms 8.263 ms
2 m7 (128.9.0.2) 8.485 ms 11.751 ms 2.773 ms
3 m8 (128.14.0.2) 9.905 ms 4.298 ms 9.185 ms
%
I wrote a simple perl script to take down links. It actually takes down all interfaces attached to a wire. The utility needs the topology file as an input because it needs to find out which intefaces are linked to given wire. To take down wire w3 type:
% linkconf puzzle4.top wire w3 down
%
To set a wire w3 up again type:
% linkconf puzzle4.top wire w3 up
%
Before you start implementing your routing protocol you should spend some time playing
with route and netstat. Setting up routes manually is called static routing, because the
routes do not change automatically when the topology changes. The puzzle4.routes file sets
up static routing for the topology used in this puzzle (the -netez_machine
The first step you should take in implementing the link-state routing protocol is to implement the Hello protocol. The purpose of this protocol is to find out when links fails or recover. The protocol is very simple. Each router sends all of its neighbors a Hello message and waits for a reply. If it receives the reply within some time limit you assume the link is up, otherwise you assume it is down. Because packets may get lost then a link is not assumed down except after some number of missing replies. Here you should send Hello packets every 5 seconds (in a real network this is usually much larger) and expect reply within next 5 seconds. You should assume that a link is down if you do not get an reply for two Hello packets in a row (It will therefore take 10 seconds to detect a link failure). Note that the Hello protocol is also used to detect link recovery, so you must keep on sending Hello packets even when you think the link is down. Upon receiving a reply you assume that the link has recovered. In this step you should just print out when you detects a link failure or recovery. Use the linkconf utility to take down links and set them up. While testing you might find it useful to increase the update time from 5 sec. to 30 sec.
In the hello protocol you are only interested in communicating with your neighbors. Originally you do not know who they are. But that is fine, because they must be connected to one of your interface (Ethernet card). Finding out what interfaces are connected to your machine is quite tricky and beyond the scope of this puzzle, therefore we provide a function that does this and stores the interface.
void init_broadcast_addr()
It initializes the gInterfaces array. The array contains an entry for each interesting interface (INET interfaces with broadcast capability). Each entry contains both the IP address of the interface and the broadcast address of the interface.
Generally we do not know the IP addresses of our neighbors, but we know that they are on the same subnet as we. We can therefore use broadcast to send packets to all machines on the same subnet. But we are not done yet. We want to send the Hello packets on specific wires, that means that we must bypass the routing table (broadcast packets are by default routed like other IP packets). This we can do by set an option on the socket, SO_DONTROUTE (we can also do this by setting the MSG_DONTROUTE flag in sendto). We provide a function to create a broadcast/don't route socket and a function to send a UDP packet to all neighbors. Note that you must have called init_broadcast_addr() before calling sendto_all_neighbors().
int construct_noroute_broadcast_socket( int port );
int sendto_all_neighbors( int s, int port, char *buf, int buflen );
You should use the alarm signal do set up timers in your program. You need two things for this to work. First you need a signal handler. And then you need to set the timer. When a signal occurs a signal handler is called if it has been set up. A signal handler takes in one argument, the signal id (you can use the same handler for multiple signals).
void sig_alrm_handler( int signum ) { ... }
You connects the signal handler using the signal system-call.
signal( SIG_ALRM, sig_alrm_handler );
To set the timer you use the alarm system-call. To set the timer to 5 seconds you do: alarm( 5 ); For more information see the man pages for the functions mentioned above. The program we provide has an example of how to handle timers.
You should compile and run the provided program on some subnet of the topology (for example for machines m0 - m3). It sends Hello packets (you probably want to change the format of the packet) to all neighbors. It also waits for packets. Upon receiving a packet it prints out information about the sender. You need only to add some state information into the provided program to complete this step. It should not take long.
The program is in /home/cs519/entrapid/puzzle4/.
When a router detects changes in the topology (i.e. on link failure/recovery or upon receiving a LSP packet that changes the topology) it needs to advertise this to its neighbors. This is done by controlled flooding. See pages 305-311 in the textbook for detailed information on how to do controlled flooding.
The LSP packet should include the following:
As the machine ID you can use the machine number from the name - for example m3 would have the ID 3. This way it will be easy for you to update the link array used for the Dijkstra algorithm. The exact format of the LSP is left to you.
You do not need to implement a complete controlled flooding protocol as described in the textbook but only a subset of it. Specfically:
You do not need these refinements because, in this assignment, routers never go down.
You should store the network topology in an 11x11 array, where each item in the array is the cost from one node to another. You should use the number in the hostname of each machine as index to the graph array. For example 'm0' will be index 0, 'm1' index 1, etc. In the graph array you can find the cost from machine 4 to machine 7 by looking either up entry [4][7] or [7][4] in the array. The cost between neighbors should be set as 1, the cost to self should be set to 0, and UNCONNECTED to others. Note that you are only storing the topology of the graph in this array, not how expensive it is to reach each machine. In other words, even if you can reach machine m4 from m0 in two hops you should not put 2 as the cost in entry [0][4] and [4][0]. It should be UNCONNECTED. In the code provided you will find an example of array like this.
If you store the topology like this you can use the implementation of the Dijkstra algorithm provided.
Whenever you get new information about the network topology you need to recalculate the next-hop table. Here the routes are based on shortest-path (i.e. cheapest-path). The algorithm we use to calculate the shortest-path is the well known Dijkstra algorithm. Last year most students had problems implementing the algorithm and therefore we apply an implementation of the algorithm you can use this year. The prototype for the Dijkstra function is:
void dijkstra( int source, int graph[GRAPH_SIZE][GRAPH_SIZE], int next_hop_table[GRAPH_SIZE] );
The function calculates a next-hop table from the source indexed by 'source', based on the topology stored in the array 'graph'. The results are stored in the array 'next_hop_table'. For example if the algorithm finds out that the first hop on the shortest-path from m0 to m4 is m1 then next_hop_table[4] contains 1 (for m1). Note that of course all the first-hops are to one of the source's neighbors.
When we set up the routing table we are actually setting up routes to subnets but not to specific machines (as one student pointed out this is not correct if the link between them is down. But since we take down the interfaces this does not matter here). In the topology each subnet has two members. You have to make sure that you create a route for every subnet in the network. You can pick the path to either of the two members of the subnet (if you want to pick the cheaper one then you need to modify the dijkstra function slightly so it returns the cost as well as the next-hop).
Each node has to advertise which subnets it is a member of. You can add some entries in the LSP packet along with the router ID with information about on which subnets the router is. Remember that an IP address is simply a long integer (4 bytes).
If you want to minimize the size of the routing table you can set the most popular next-hop as default route.
Now you should be ready to update the routing table. The routing table is in the kernel. When a routing protocol needs to update a routing table it does so by using RAW sockets (aka routing sockets). Instead of having you using RAW sockets (which is complicated and of limited use for you) you should use the 'route' program to alter the routing table.
There are many ways of starting up a program from inside another. The simplest way is to use the 'system' system call.
system( "route delete 128.5.0.0" );
For more information on how to use 'system' see the man pages.
Before you start implementing this step in your program be sure you understand completly how 'route' works. Read the man pages carefully and play with it for some time. Otherwise you will have lots of problem here.
Do not submit your program until you have tested it thoroughly. Take down and reestablish links. Use ping and traceroute to check paths. Design your testing methods. Test for certain things you may expect that might fail in your routing protocol.
Last year the routing assignment had the worst outcome. Most problems students had they should have been able to catch with proper testing.
In the previous puzzle we had some problems we had some problems with babbage. The most serious one was that it ran out of ptys (pseudo-terminals) and students could not log into the machine. For this assignment we are going to set up the simulator inside the CS firewall as well as on babbage. If you have an cs account (which most masters- and PhD-students have) you should be able to use the simulator from yodel or hoho. We hope this will distribute the load enough. We also asked adm to increase the maximum number of ptys on babbage.
One of the reason for the ptys problem is that many students had multiple windows open. This is fine, but you should also keep in mind that you can run processes in background by adding a '&' to the end of a command line:
% router &
One problem running processes in background is that sometimes you forget about them. I noticed in last assignment that some students did not clean up properly and had processes in infinite loops. This is very bad because it eats up all CPU cycles. You can see your processes by typing:
% ps -u <your userid>
You should also run top once in a while to see who is eating up most of the cycles.
% top
If you notice that some student doing the puzzle has a process that is eating up a lot (10%) of available cycles and has been running for a long time, then please notify them by e-mail.
If you want to kill a process of yours do:
% kill -9 <process id>
You get the process id by running top or ps.
I added a simple script that simplifies the cleanup task. The script is called quit_entrapid. It quits the simulator and all programs connected to it.
Note that even though the description of the assignment is quite long the assignment itself is fairly simple.
Additional documentation for the simulator is at http://www.ensim.com/documentation/. There you will find more detailed information on how to use the simulator and man pages for all supported system-calls. To get access to the online documentation you have to register (of course it is free) at http://www.ensim.com/support/register.html.
We will run your routing protocol on the same topology as above. We will take down and set up some numbers of links. After some quiet period (30 seconds so your protocol can converge) we will check for reachability from all nodes. If your protocol has set up the routes correctly you will get a full grade, otherwise you get 0.
Please first read the overall submission instructions. In addition, please follow these instructions:
Unlike in previous puzzles you will not submit only one file. You should submit all source files you use along with the Makefile. Before you send the sources you should tar the files.
% tar fvc puzzle4.tar <file1> <file2> ...
All the files you specified have been stored to the puzzle4.tar file. Test this before you mail it to me. To un-tar do. Do this in different directory, otherwise you might override some of your files.
% tar fvx puzzle4.tar
Do NOT add any binary files to the tar file. Check for the size of the tar file. If it is large (more than a few K) then something went wrong.
Your tar file should be flat do not tar the directory but only the content. The tar file must include Makefile. The executable created by the makefile must be named router.
Before you send it must uuencode it, otherwise some data might be spoiled while mailing. This you do by typing:
% uuencode puzzle4.tar < puzzle4.tar > puzzle4.tar.uu
The parameter (puzzle4.tar) is the name it will use when the file is uudecoded. Then mail the puzzle4.tar.uu as usual using mailx.
In the email you send me the subject line must be: CS519: Homework 4
Put a one line comment at the top of your code with your name and
Cornell ID (6 digits) with the prefixes "Student:" and
"CornellID:".
Example:
/* Student: John Doe CornellID: 123456 */