Communication Networks - HW1

Asavoae Cosmin-Stefan, 321CD

• Solution Overview
  • Forwarding
  • ARP
  • ICMP
  • Efficient Longest Prefix Match
  • Utilities
• Personal Notes (Feedback)

Solution Overview

Forwarding

The task of forwarding was pretty simple. Just recreate the 4th lab using the provided routing tables and ARP table.

Key steps:

• Parse packet
• Checksum
• TTL
• Perform table lookup
• Modify original packet
  • Decrement TTL
  • Update checksum
  • Change Ethernet header for the next hop
• Forward the packet to the next hop

There was a crucial mistake I made that caused me to lose half a day debugging though. The LPM algorithm.

Simple enough to implement, but I forgot to also check the masks' lengths when two prefixes are equal, causing all packets that have to go from r1 to r0 to be lost.

ARP

This one was easy to implement, just read the provided docs and make sure to fill the packet with the correct options.

My implementation has this flow:

• Try to find the hardware address of the next hop

  • If found, good. Send the packet

• Address not found

  • Store the packet as pending inside a queue
  • Create an ARP request for the required IP address

• ARP reply received

  • Save the reply inside the ARP table
  • Process any pending packets from the queue with the provided address

• ARP request received

  • Modify original packet
    • Set my own address as the source
    • Reverse Ethernet header
  • Send back reply

One thing I did which I consider a dirty hack (but the router_arp_request wouldn't pass without) is to also add the incoming packet's IP and hardware address to my ARP table.

I know that the source address might not be from the sending machine (e.g. r0->r1) but the lookup happens only for addresses directly connected to the router. So any addresses not belonging to a directly connected host just sit there.

One problem encountered here was that I wasn't updating an entry if it already was there. I was just adding another element to my table, which caused some not so pretty debugging sessions.

ICMP

This one was the easiest:

• Create buffer for the packet
• Copy most of the original packet's headers and the first 8 bytes if it's a bad response
• Set the type and code accordingly
• Calculate checksum for the entire packet
• Send it back to the source address

The only problem here was actually calculating the checksum. I didn't know that it included the whole packet, not just the header like IP

Efficient Longest Prefix Match

Here I'll be straight forward: I took inspiration from the web (mainly ChatGPT), but I also tried to understand how the trie works:

• The mask becomes the height of the prefix branch in the current entry
• Inserting a prefix just means taking every bit of the prefix and going left or right in the tree based on it
• Finding the longest prefix match means going bit by bit in the given IP address
  • When a route is found, save it and continue
  • If a leaf node is hit, the last match is the longest

Because the maximum height of the tree is the number of bits in a mask or IP address, the maximum number of steps to take is the number of bits of the longest prefix. Because of this, the time complexity of the search goes from O(N) down to O(32) which is constant.

Utilities

Throughout this homework you will see that I've used numerous LOG statements. They came in handy for debugging, because of my setup. Most of the errors were caught while going through these logs inside the output files.

To enable them just uncomment the define from utils.h

NOTE: I know that there are memory leaks, mostly coming from ip_to_str and mac_str which call strdup, but freeing those when logging, would've made the code pretty ugly. They are only called if logging is enabled though.

Also, the trie is never freed, because that would need the while loop to end.

Personal Notes (Feedback)

Please note that these are just things I found annoying while solving this assignment and can be skipped

Some comments in the checker scripts would be greatly appreciated. I often found myself looking inside tests.py for clues as to why a certain test failed, only to stare at the screen for a good minute.

For example:

# tests.py:302

if (hs in {0, 1} and hr in {2, 3}) or (hs in {2, 3} and hs in {0, 1}): 
   nr_pkts += 2

What's this supposed to mean ?? I spent around 2 hours trying to understand why I was getting excess packets on my tests.

Another thing I found annoying was using the mininet. I understand that the homework was made to work with the provided VM, but my laptop needs to run my IDE, the checker and at least a browser with only 5GB of available RAM (which CLion kindly takes about 3.5GB from)

My problem is that the checker expects an X11 backend, which my machine has, but my main compositor only uses Wayland with an X11 emulator. So when I run topo.py, the script tries to launch xterm but it's not compatible with Wayland. In the labs I got around this by launching termite manually from the mininet console, but here that didn't appear to work.

This was solved by switching to an older compositor I still had installed. (I use arch btw)

While on the topic of mininet, I hope that in the next years this method of manually testing will get less tedious. Due to my bigger desktop monitor, I chose to work on this homework through SSH because my machine runs Windows and a VM would put a lot of strain on it. Because of this I had to go back and forth to my laptop to do the mininet tests, because I couldn't multiplex my terminal.

On a positive note, this assigment was pretty helpful in better understanding the inner workings of the devices we use daily and which we take for granted. If I had to grade this assignment, I would give it a solid 8/10.

The deduction comes from the aforementioned points and from the vague error messages given by the checker when something went terribly wrong.