Programming Assignment #3: Building your own Internet Router

Frequently Asked Questions

Plus some less frequently asked ones that are deemed potentially helpful

Last updated: 11/10/2003



Questions in this FAQ:
  1. How do I know that my topology is set up and working?
  2. I'm having trouble connecting to my topology
  3. What is the best methodology for debugging my router?
  4. What are good references for dealing with protocol headers?
  5. I tried running the skeleton code and then accessing one of the webservers, however it doesn't work. Is there something wrong?
  6. How do I write and test a function that calculates the IP Checksum
  7. Do I have to handle Muticast in my Router
  8. What ARP functionality do I have to handle?
  9. Do I have to deal with fragmented packets?
  10. If I generate an ICMP message, what is the right TTL to use?
  11. How do we implement the arp queue timeout? Should we use multiple threads or a timer?
  12. Do I have to handle ping packets aka ICMP Echo packets?
  13. Which types of checksums (TCP/UDP/ICP/IP) do we have to verify/calculate??
  14. What types of ICMP messages do I have to generate
  15. Does the client have to reply to ICMP Echo Requests on all four interfaces or just on the primary interface?
  16. Do I have to be able to handle IP Options
  17. How do I implement the ARP cache? Is a static table sufficient? Do I need a hash table?
  18. What kind of sanity checks should I perform on the packer header?
  19. Do I have to deal with the ethernet preamble/crc?
  20. Why are the arp packets I get from sr_send_packet( .. ) 60 bytes instead of 42?
  21. Every once in awhile my router fails with the error, "Error: could not read full command length from server"
  22. When exactly should I generate a timeout ICMP message?
  23. Ethereal reports that the ICMP checksums generated by the unix ping application are wrong. What is going on!?
  24. Why do I keep getting a segfault when attempting to access memebers of struct ip?
  25. So EXACTLY how many ARP requests must I send to a host withouth a response before I send an ICMP host unreach packet back to the sending host?
  26. Which files in the stub code can I modify?
  27. What sort of routing entries do we need to support in the routing table?
  28. Do I have to check/decrement the TTL in the IP header if the packet is addressed to me?
 How do I know that my topology is set up and working?

The very first thing you are going to want to do when ready to start playing around with the skeleton code is connect to the VN server and verify that your topology exists. Once the code is compiled, run ./sr with your topology number (using the -t command line option to specify the topology number. A session using topology number 17 might look as follows:

elaine15:~/tmp/sr_skel> ./sr -t 17
Destination: 0.0.0.0
Gateway : 172.24.74.17
Mask : 0.0.0.0
Interface : eth0
Client pepe connecting to Server vr-server-b:12345
Requesting topology 17
Sending c_open (type=1 len=108)
Received Hardware Info with 19 entries
Fixed IP: 172.24.74.17
INTERFACE: eth0
Speed: 10
ardware Address: 70:00:00:11:00:01
Ethernet IP: 172.24.74.40
Subnet: 0.0.0.0
Mask: 0.0.0.0
INTERFACE: eth1
Speed: 0
Hardware Address: 70:00:00:11:00:02
Ethernet IP: 172.24.74.241
Subnet: 0.0.0.0
Mask: 0.0.0.0
INTERFACE: eth2
Speed: 0
Hardware Address: 70:00:00:11:00:06
Ethernet IP: 172.24.74.242
Subnet: 0.0.0.0
Mask: 0.0.0.0
Interface: eth0
ip address 172.24.74.40
Interface: eth1
hardware address 70:00:00:11:00:02
ip address 172.24.74.241
Interface: eth2
hardware address 70:00:00:11:00:06
ip address 172.24.74.242


You can ignore most of this information, but do verify that the IPs on the router's interfaces do match those on the router of topology assigned to you.
To verify that your router does, in fact, receive packets, try pinging one of the interfaces. Your router should print the following:
    *** -> Received packet of length 60 
*** -> Received packet of length 60
*** -> Received packet of length 60

What packet do you think this is? If you are able to connect to the server and see packets, you are correctly set up to start the assignment.

I'm having trouble connecting to my topology, the error I'm getting is:

client casado connecting to Server 171.67.71.18:12345
Requesting topology 122
Sending c_open (type=1 len=108)
vns server closed session.
Reason: reservehost failed
sr_destroy_INSTANCE leaking memory
The most likely cause for this error is that there is already a router connected to your topology. Typically this happens when students forget to properly kill their routers (often using ctrl^z which only suspends them). You determine if a router is connected to your topology by going to the following web page: http://vns-1.stanford.edu/summary. If there is a router on your topology then it is already in use. The page gives an indication of the user doing the connection as well as the connecting IP address. If the router is yours, kill the process and it will free up. If another student has mistakingly connected to your topology you'll have to contact them directly or your Prof/TA.

What is the best methodology for debugging my router?

Debugging the source code for logic errors, crashes and memory leaks should not be any different than any other program. The use of purify and gdb is encouraged

In order to facilitate debugging of network traffic handled by your router, the sr stub code supports tcpdump compatible packet logging for all packets sent from and coming to the router. It is highly recommended that you get comfortable logging packets and viewing the logfiles in tcpdump as soon as possible.

To log packets, use the -l command line option for sr to specify a log file. All packets will then be written to this log file.

elaine15:~/tmp/sr_skel> ./sr -t 17 -l logfile 
To view the log file using tcpdump use the -r command. It is also recommended that you use the -e command to print out headers, the -vvv command for verbose output and the -x command to print out the hex values of the packets. Output should look as follows:
elaine15:~/tmp/sr_skel> /usr/class/cs244a/bin/tcpdump -e -vvv -x -r logfile
19:51:31.809693 0:e0:81:3:fd:9e Broadcast arp 84: arp who-has 172.24.74.40 tell vr-firewall.Stanford.EDU
0001 0800 0604 0001 00e0 8103 fd9e ac18
4a11 0000 0000 0000 ac18 4a28 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
000a 0000 0260 0000 0000 0002 92d0 0000
0000 0000 0000
Another very useful tool you may want to play around with is ethereal.


What are good references for dealing with protocol headers?


I tried running the skeleton code and then accessing one of the webservers, however it doesn't work. Is there something wrong?

No, that is how it should be .The skeleton code currently does pretty much nothing. It sits there, waits for packets and just drops them. With the skeleton code you can't access any web page. You will see the ARP requests from the first hop, but since the stub code does not reply, the first hop does not know which hardware address to send the first TCP packet (SYN) to. To access the web pages you will have to write code. Actually if you can access a web page you have completed significant portions of the assignment!


How do I write and test a function that calculates the IP Checksum

The algorithm as well as sample source code is in Peterson & Davie, page 95. Be careful what parts of the package you calculate the checksum over. TCP and ICMP for example need to be treated differently. A great way to test if your function is working is to run it on arriving packets. If you get the same checksum that is already contained in the packet it looks like your algorithm is working. If you use this test, make sure not to include the old checksum (the one that is in the packet when it arrived) in your checksum calculation. In the original calculation this checksum was zero! A good way to check if you've calculated the correct checksum is to use ethereal which will indicate if the checksum values are correct.


Do I have to handle Muticast in my Router

No, you don't.


What ARP functionality do I have to handle?

You have to handle both ARP requests and replies.


How do I have to deal with fragmented packets?

Just ignore fragmentation. Today on the internet fragmentation is actually pretty rare. Treat fragmented packets as normal packets and you should be fine.


If I generate an ICMP message, what is the right TTL to use?

There is no "right" value, however 64 is a good choice. You can easily test what your current operating system uses:

[root@gadshome appenz]# /usr/sbin/tcpdump -x &
[1] 1435
tcpdump: listening on wlan0
[root@gadshome appenz]# ping 171.64.64.64
PING 171.64.64.64 (171.64.64.64) from 192.168.1.104 : 56(84) bytes of data.
64 bytes from 171.64.64.64: icmp_seq=0 ttl=238 time=33.461 msec
11:23:03.258943 192.168.1.104 > CS.Stanford.EDU: icmp: echo request (DF)
4500 0054 0000 4000 4001 8d18 c0a8 0168
ab40 4040 0800 dbaa 9c05 0000 1703 703c
0a0d 0400 0809 0a0b 0c0d 0e0f 1011 1213
1415 1617 1819 1a1b 1c1d 1e1f 2021 2223
2425 2627 2829 2a2b 2c2d 2e2f 3031 3233
3435

Byte 9 ist the TTL. Linux uses the TTL to 64 (Hex 40) as well, at least for PING messages.

How do we implement the arp queue timeout? Should we use multiple threads or a timer?

You actually can take the simple solution and only check the arp queue timeout whenever another packet is received. This is not entirely correct behaviour as a packet could be in the arp queue for a very long time. But usually retransmits will arrive soon after the first packet, it performs pretty well in reality.


Which types of checksums (TCP/UDP/ICMP/IP) do we have to verify/calculate??

There are three types of checksums:

IP Checksums - All IP packets have these and for any forwarded/generated IP packet you have to verify/calculate it.

TCP/UDP checksum - this is an end-to-end checksum that you don't have to worry about. Due to the way it is calculated IP header modifications won't change its value.

ICMP Checksum - You should verify/calculate this for ICMP messages that you receive/send (but *NOT*for icmp message that you forward, these should be treated as IP packets only). For infos how to do this see RFC 792.

What types of ICMP messages do I have to generate

You should support the following:


All other ICMP message that you receive you can ignore, however you should forward any icmp message that is not for the virtual router itself.


Does the client have to reply to ICMP Echo Requests on all three interfaces or just on the primary interface?

The client has to reply to all ICMP requests destined to IPs owned by the router's interfaces


Do I have to be able to handle IP Options


No, other than that your client may not crash if it receives a packet with ip options, you don't have to do anything  with them. You don't have to parse them and it is acceptable to drop such packets or generate incorrect checksums for them. 


How do I implement the ARP cache? Is a static table sufficient? Do I need a hash table?

A static, hard-coded ARP cache is NOT acceptable. You should have a sufficiently sized (e.g. 100) entry table that is dynamically filled with values when ARP replies are received. You do NOT have to implement any sophisticated search alogrithm such as hashing or RB Trees, a linear search is perfectly acceptable.

What kind of sanity checks should I perform on the packer header?

Your code must be stable (e.g. not crash) with any packet it receives. You should also discard packets that are obviously corrupted e.g. if the IP version is not IPv4, if the packet length is negative or above the Ethernet MTU etc.

Do I have to deal with the ethernet preamble/crc?

No, sr_handlepacket( .. ) delivers ethernet packets without the preamble and without the CRC. Likewise, sr_send_packet(..) expects an ethernet packet without the preamble and CRC. All packets to/from these functions have the following header format:

  DST     SRC     FRAME      DATA
  MAC     MAC     TYPE
 +-------+-------+-------+-------------------+
 |6 bytes|6 bytes|2 bytes|  46 - 1500 bytes  |
 +-------+-------+-------+-------------------+

Why are the arp packets I get from sr_send_packet( .. ) 60 bytes instead of 42?

The minimum size for the data segment of an ethernet packet is 46 bytes, whereas an ARP packet is 28 bytes. The OS pads an extra 18 bytes on to the end of ARP packets to meet this minimum length requirement. You don't have to worry about adding padding when generating arp packets it will be added by the OS.

Every once in awhile my router fails with the error, "Error: could not read full command length from server"

Download the latest version of the stub code (the fix is in sr_vns_comm.c).

When exactly should I generate an ICMP timeout message?

ICMP timeout should be generated when the TTL field in the IP header of an incoming packet is one or zero before it is decremented. Only generating an ICMP message if the TTL of the packet is zero after decrementing will lead to strange traceroute output and won't get full credit.

Ethereal reports that the ICMP checksums generated by the unix ping application are wrong. What is going on!?

The stub code only saves the first 96 bytes of the packets it receives and the generated ICMP packets are 98 bytes, hence Ethereal's checksum does not take into account the last 2 bytes. The latest version of the stub code has the packet dump length increased to 100 bytes. You may also modify sr_router.h to increase PACKET_DUMP_SIZE yourself.

Why do I keep getting a segfault when attempting to access memebers of struct ip?

An older version of the stub code did not have the "packed" attribute appended to the struct definition in sr_protocols.h. You can either add this by hand or replace your sr_protocols.h with the sr_protocols.h in the current release of the stub code.

So EXACTLY how many ARP requests must I send to a host withouth a response before I send an ICMP host unreach packet back to the sending host?

5 or 6. There have been conflicting answers to this so either is fine.

What sort of routing entries do we need to support in the routing table?

You have to support two cases:

Which files in the stub code can I modify?

The only files in the provided source that you may modify are sr_router.h and sr_router.c (this does not include bugfixes). You may, however, add your own files and update the Makefile to support them.

Do I have to check/decrement the TTL in the IP header if the packet is addressed to me?

No you don't.

Section 4.2.2.9 of the router rfc (1812) states:

"Note in particular that a router MUST NOT check the TTL of a packet except when forwarding it."