E6998-02 Homework 2

Out: 18 September 2002


Due: 26 September 2002 at 3am EDT. You have more than a week. Start tonight, ask questions if you have problems.


The purpose of this homework is to familiarize you with forwarding lookups. The homework should implemented using a patricia tree for storing the FIB (forwarding information base, what BSD calls "routing table"), and, of course, any additional data structures you need to keep information about your interfaces. You may look at how your favorite flavor of BSD does it, but write your own code and your own data structures. You may write this homework in any language that I can be reasonably expected to have a compiler for (C, C++, Java, Common Lisp), and it should run on either Solaris or FreeBSD. I cannot test it on other BSD flavors, Linux, Windows, or any other OS. Your submission should include a makefile (I should be able to type "make" and have everything compile without errors). I will be testing the results automatically using a test file, so make sure you conform to the style of output I give in the examples. Make sure you handle syntax errors gracefully (just print "SYNTAX ERROR"). The only time your program should exit is when it encounters an end-of-file. Be careful in your assumptions about line lenghts and things like that; if I can crash your program via a buffer overflow or by feeding it random garbage, you will get no credit!

Write a stand-alone program, simrouted, that behaves in a manner similar to the unix routing code. The program reads commands from standard input, and outputs results on standard output and diagnostics on standard error. If standard input is a terminal (as opposed to a file, through redirection), it should print a prompt (to standard error, of course) specified in the environment variable SRPROMPT. For example:
$ SRPROMPT='sr> ' ./simrouted
sr>

It takes commands similar to the route(8) command, and additional commands to simulate interfaces and arp. Here is a complete list:

ifconfig ifname plumb
Creates a new interface named ifname. This is an ethernet-like interface, so your code should generate a random unique unicast MAC address for it. Hint: remember to have the unicast/multicast bit set correctly! If the interface already exists, complain:

sr> ifconfig xl0 plumb
sr> ifconfig xl1 plumb
sr> ifconfig dc3 plumb
sr> ifconfig dc3 plumb
"dc3" already exists, ignored.
sr>

ifconfig ifname unplumb
Removes the interface named ifname. Any entries in the forwarding table associated with it must also be removed. If the interface does not exist, complain:

sr> ifconfig dc3 unplumb
sr> ifconfig dc3 unplumb
"dc3" does not exist, ignored.
sr>

ifconfig ifname link MAC-address
Sets the link-level address of ifname, specified as six octets separated with colons; leading 0s of each octet may be omitted (i.e., 00:2c:44:01:02:01 may be written as 0:2c:44:1:2:1). The interface must already exist, and the MAC address should be a unicast address; if not, complain. :

sr> ifconfig xl0 link 0:0:c5:69:98:02
sr> ifconfig dc3 link 2:2:4:1:1:2
"dc3" does not exist, ignored.
sr> ifconfig xl0 link 09:0:0:32:11:14
Bad address: 09:00:00:32:11:14
sr>

ifconfig ifname inet ip-address [ netmask netmask ] [ broadcast bc-address ]
Sets the IP address of interface ifname to ip-address, setting the netmask to netmask and the broadcast address to bc-address. If the broadcast address is omitted, it is generated from the IP address and the netmask by setting the host part to all-ones. If the netmask is omitted, it defaults to the "class" of the address (A, B, or C). Addresses and netmasks may be dotted decimal or hex numbers prefixed by 0x (e.g.,128.59.16.20 or 0x803b1014). Evidently, the IP address must not be a class D or E address:

sr> ifconfig xl0 inet 128.59.16.20
sr> ifconfig xl1 inet 135.207.4.221 netmask 255.255.255.224
sr> ifconfig dc3 inet 192.4.13.134
"dc3" does not exist, ignored.
sr> ifconfig dc3 inet 224.0.0.4
"dc3" does not exist, ignored.
sr> ifconfig xl1 inet 224.0.0.4
Bad address: 224.0.0.4, ignored.
sr> ifconfig xl1 inet 0xe0000004
Bad address: 224.0.0.4, ignored.
sr>

ifconfig ifname
Shows the link- and IP addresses of interface ifname. If ifname does not exist, complain.
ifconfig
Shows the link- and IP addresses of all interfaces:

sr> ifconfig xl0
xl0:
    link 00:00:c5:69:98:02
    inet 128.59.16.20 netmask 255.255.0.0 broadcast 128.59.255.255
sr> ifconfig dc3
"dc3" does not exist, ignored.
sr> ifconfig hme9 plumb
sr> ifconfig hme9
hme9:
    link 02:24:48:c3:91:88
sr> ifconfig
xl0:
    link 00:00:c5:69:98:02
    inet 128.59.16.20 netmask 255.255.0.0 broadcast 128.59.255.255
xl1:
    link 08:00:09:12:33:11
    inet 135.207.4.221 netmask 255.255.225.224 broadcast 135.207.4.223
hme9:
    link 02:24:48:c3:91:88
sr>

arp ins ip-address MAC-address
Creates an entry for ip-address associating it with MAC-address. The ip-address must belong to a directly-connected network (i.e., it should belong to the same CIDR prefix as one of the already-ifconfiged interfaces).

sr> arp ins 128.59.18.16 0:0:c:32:11:17
sr> arp ins 10.0.0.89 2:4:6:8:10:12
Network is unreachable, ignored.
sr> arp ins 135.207.4.193 00:80:c8:ca:a2:79
sr>

arp del ip-address
Deletes the ARP entry for ip-address. If such an entry does not exist, complain:

sr> arp del 128.59.18.16
sr> arp del 128.59.18.16
Unknown address: 128.59.18.16
sr>

arp
Prints all known ARP entries, including, of course, addresses for our own interfaces:

sr> arp
128.59.16.20 at 00:00:c5:69:98:02 on xl0
128.59.255.255 at ff:ff:ff:ff:ff:ff on xl0
135.207.4.193 at 00:80:c8:ca:a2:79 on xl1
135.207.4.221 at 08:00:09:12:33:11 on xl1
135.207.4.223 at ff:ff:ff:ff:ff:ff on xl1
sr>

Note that hme9 does not appear since it does not have an IP address yet. Also note that the addresses are printed sorted by IP address, and that the corresponding interface is also printed. Also note the automatically-created broadcast address entries.

route add ip-address[/prefixlength] router-address
Adds an entry to the forwarding table for the prefix ip-address/prefixlength indicating router-address as the router. The router-address is an IP address on a directly-attached network, and it may or may not have an ARP entry. If the /prefixlength is omitted, it is assumed to be /32 (a "host route"). The string default can be used instead of 0/0:

sr> route add 192.20.225.14 135.207.4.193
sr> route add 192.20.225.14 135.207.4.193
Route exists, ignoring.
sr> route add 160.97.3.0/24 128.59.18.11
sr> route add 4.0.0.0/8 26.0.3.77
Network is unreachable, ignored.
sr> route add default 128.59.1.1
sr> route add default 128.59.3.4
Route exists, ignoring.
sr> route add 189.33.1.2/24 128.59.18.11
sr>

route delete ip-address[/prefixlength]
Deletes ip-address from the forwarding table. Complains if the route does not exist:

sr> route delete 192.20.225.14
sr> route delete 192.20.225.14
Route does not exist, ignoring.
sr>

route
Prints the contents of the forwarding table, including, of course, the MAC addresses that we know of:

sr> route
Destination        Gateway           Flags Netif
default            128.59.1.1        UG    xl0
128.59.0.0/16      link#1            U     xl0
128.59.16.20       00:00:c5:69:98:02 UHL   xl0
128.59.255.255     ff:ff:ff:ff:ff:ff UHB   xl0
135.207.4.192/27   link#2            U     xl1
135.207.4.193      00:80:c8:ca:a2:79 UHL   xl1
135.207.4.221      08:00:09:12:33:11 UHL   xl1
135.207.4.223      ff:ff:ff:ff:ff:ff UHB   xl1
160.97.3.0/24      128.59.18.11      UG    xl0
189.33.1.0/24      128.59.18.11      UG    xl0
192.20.225.14      135.207.4.193     UGH   xl1
sr>


lookup ip-address
Looks up ip-address in the forwarding table, and returns the interface the packet should go out on and the MAC address of the destination (the MAC address of the actual host if the host is directly connected, otherwise the MAC address of the router) if the MAC address is not known, print instead the IP address that should be ARP'ed for:

sr> lookup 128.59.16.20
128.59.16.20 xl0 00:80:c8:ca:a2:79
sr> lookup 128.59.16.21
128.59.16.21 xl0 ARPFOR 128.59.16.21
sr> lookup 160.97.3.22
160.97.3.22 xl0 ARPFOR 128.59.18.11
sr> lookup 80.0.3.2
80.0.3.2 xl0 ARPFOR 128.59.1.1
sr> lookup 135.207.4.223
135.207.4.223 xl1 ff:ff:ff:ff:ff:ff
sr> lookup 189.33.1.255
189.33.1.255 xl0 ARPFOR 128.59.18.11

Things you can do for extra credit:


Submit the homework via email to ji+hw2@cs.columbia.edu. Do not send to any other address, or your submission will be ignored.


$Id: index.html,v 1.3 2002/09/19 05:25:06 ji Exp ji $