# CSE 123 Project 2 - Router

Name: Godwin Pang

I will be competing for the Espresso Prize!
If there are any problems testing(regarding espresso functionality), please reach out!

[TOC]

# Overview
I mainly followed the flowchart diagrams as presented in discussion section to implement my router.

Entry point of packets is in *sr_handlepacket*, and from there it delegates to *sr_handle_arp* and *sr_handle_ip* respectively.

At a high level, *sr_ip.c* handles all things regarding IP packet handling, delegating to *sr_icmp.c* as appropriate (handling ICMP packets). **sr_arp.c** handles all things regarding ARP packet handling.

## ARP
On receiving ARP packet, we first check if it is a request or a reply.

If it is an ARP request, then we simply reply with a response IF the interface is on the router.

If it is an ARP reply we delegate to *forward_single_arpreq* in **sr_arpcache.c** to forward out all the packets in the ARP cache associated with the IP/MAC combo addressed by the ARP reply.

Note that *handle_cached_arpreq* delegates to *handle_single_arpreq* to send ICMP host unreachable packets when 5 ARP requests have gone out without a reply. This is due to the packets for a single arpreq being queued up as a LIFO stack as opposed to a FIFO queue, and thus the decision was made to recursively handle the packet queue backwards. A similar thing is done on receiving ARP replies.

## IP

On receiving an IP packet, we validate the IP packet by checking the IP version and checking the checksum by delegating to *is_valid_ip*.

If the packet is destined to router, then we handle ICMP packets by delegating to *sr_handle_icmp* and drop IP packets with a reply of ICMP port unreachable.

Else, we check if the ttl is equal to 1. If yes, then we reply with ICMP time exceeded. If no, then we forward the IP packet by delegating to *forward_ip_packet*.

*forward_ip_packet* sends ICMP net unreachable if there is no corresponding route in the routing table. Else, it checks the ARP cache to find the MAC address for the dst IP. If there is one, then it forwards it out and immediately broadcasts an arp for it by delegating to *handle_cached_arpreq*.

### ICMP
As mentioned above, if an ICMP packet is received, then we validate the ICMP header by delegating to *is_valid_icmp*, which checks the checksum and ensures that the ICMP header meets the minimum length. If yes, then we check that the ICMP type is of type 8 - echo. If the ICMP type is not echo, then the packet is dropped. Else, we send an echo reply to the sender.

## Design Decisions
Conversion of packets to the header structs appeared to be a common task, so I made helper functions in **sr_utils.c**

Due to the many different ICMP packets being sent, each ICMP type has its own function that delegates to *send_icmp_packet* to actually send the packet.

## Tradeoffs

Note that the ARP cache queues the packet storing the incoming interface instead of the outgoing interface of the packet. This choice was made to facilitate the sending of ICMP host unreachable packets on ARP timeout. A packet can come in on an interface from a host without a corresponding entry on the routing table. In that case then there is loss of information if the outgoing interface is stored as there is no way of reverse engineering the inbound interface. This adds lag to the forwarding of packets upon receiving ARP replies as the outbound interface has to be computed for each packet on forwarding instead of being precomputed.

# Espresso Prize

As mentioned above, I will be competing for the Espresso Prize.

For the Espresso Prize, I have implemented the following additional functionality for my router.
- Firewall
- Virtual Router Redundancy Protocol (VRRP)

I followed the suggestions for project ideas to implement a packet filter the firewall whereas I chose to implement VRRP as I was interested in distributed systems.

Out of the two, implementing the Virtual Router Redundancy Protocol was far more complicated and took a lot longer to implement.

This was due to a couple of reasons:
1. Having to understand how POX communicates with **sr** using VNS and how POX communicates with Mininet using Openflow.
2. Having to modify the pox_module and the mininet topology.
3. VRRP has a dependency on IP multicast so I had to 'hack' around it.

Most of the time was spent on the first two points and refactoring **srhandler** and **ofhandler** in pox_module where I had to read up on documentation for POX and Mininet.

## How to Test

I recommend running tests using my modified network topology which may be found in the **vrrp_test** folder in my repository. To run the modified network please run

cd vrrp_test
./run_pox.sh
./run_mininet.sh

There is a large file (~300kb) hosted by server1 for your convenience.

***IMPORTANT NOTE***
Please wait 2-3 seconds after starting up sr to send packets. This is due to a 1.5s hardcoded delay to wait for receipt of rotuer interface information from mininet.

To run the firewall and/or VRRP, please check the corresponding usage instructions sections.

I kindly ask that you terminate the **sr** binary by using Ctrl-C as there is a signal handler attached to **SIGINT**. In the unfortunate event that Ctrl-C does not work, please use `ps aux | grep sr` with `kill` to kill the runaway process.

If run_pox.sh or ./sr crashes for any reason, please follow the following instructions.

Kill all processes by using Ctrl-C.

./run_mininet.sh
./run_pox.sh

# wait for a couple seconds for pox to load interfaces from mininet

./sr (with options)

### Modified Topology

The new topology keeps the same client + 2 servers, but there are two routers (sw0, sw1) with *eth4* being the dedicated 'multicast' interface for inter-router communication.

### Testing Ideas

Here are some testing ideas for my Firewall and VRRP. Please keep in mind that there is a large file served on server1 so `wget server1` will give you sufficient time to modify firewall rules / kill routers.

Also, looking at the VRRP packets in wireshark is cool as you can see how the virtual routers only reply with their virtual mac address :)

- Firewall
- Verify that firewall can correctly allow and deny TCP/UDP traffic (for specified ip and ports) by modifying the firewall file.
- Verify that firewall file is loaded properly within 1 second by changing firewall rule from **allow** to **deny** while transferring.
- Changing from allow to deny is recommended as you can see the change happen quickly. With deny to allow, the router goes into slow start and thus the rule loading will lag.
- VRRP
- **Note that there's a printf on virtual router state transition which will help 'visualize' I hope**
- Given both routers are up, ping and wgets work without any duplicates.
- Given both routers are up, killing either router will not result in disruption to service.
- Given one router is up and the other one is down, firing up the down router will not result in duplicate packets the **vast majority** of the time. (VRRP has at least one delivery semantics)

## Firewall

### Usage Instructions

./sr -f path_to_firewall_file

### Specifications
This firewall supports packet filtering for **TCP/UDP** packets with support for ip/port specification (any is supported as well).

### Modifications
On inputting an IP with a optional port, the grammar has been modified from

<ip_block> <optional_port>

to

<ip_block>:<optional_port>

(Replacing space delimiter with :)

Also, the flow grammar (in/out) will be ignored.

### Implementation
All firewall related functionality is implemented in the **sr_firewall.c** and **sr_firewall_utils.c** files.

Each firewall rule is stored in *struct sr_firewall_rule*, which is a linked list stored in *struct sr_firewall*.

Note that there is a *last_updated* timestamp stored within the firewall struct. This is updated when the firewall is first loaded.

Everytime a non-ICMP packet not destined towards the router is received by the router, then *can_pass_firewall* is called to check if the packet is allowed to pass.

*can_pass_firewall* first checks when the file has last been updated with a syscall. If the system file last updated time is greater than the *last_updated* timestamp in your *struct sr_firewall* struct, then we clear all the firewall rules then load from file again. It then checks the packet against the firewall rules. If the packet does not pass the rules, the packet is dropped. Else the packet is forwarded.

## VRRP

### Usage Instructions

./sr -i vr_id

# i.e. ./sr -i 1

Accepted vr_ids include 1 or 2.

### Specifications
I followed [RFC 3768](https://tools.ietf.org/html/rfc3768) with the following omissions and settings.
- VRRP packets are not sent to the VRRP IP multicast group. They are sent through the designated VRRP interface *eth4* to the other router.
- On receiving invalid VRRP packets, the packet is just dropped without logging.
- VRRP routers are setup with no authentication required.

#### Mininet Topology
Note that the router with VR id 1 is the default master router with priority 255 connecting to pox running on port 8888, and the router with VR id 2 is the backup router with priority 100 connecting to pox running on port 8889.

### Implementation

All functionality may be found to be implemented in the **sr_vr.c**, **sr_vr_utils.c**, and **sr_vr_file_utils.c** files. The exact packet struct may be found in **sr_vr_protocol.h**.

In the interest of time, I will not attempt to list all the details/tradeoffs of implementation.

The *router shutdown* event described in the RFC is sent via a SIGINT handler (hence Ctrl-C).

The biggest annoyance with implementing broadcasting ad on setup(in *sr_main.c*) since the router does not have any interfaces configured yet. Therefore the initialization of the virtual router state is delegated onto another thread which first sleeps for 1.5s.

Handling of ***all*** packets also had to be modified to take into consideration the VRRP packets. This was not something that I planned for enough, and thus sr_vr_utils.c is not exactly the cleanest code.

When the router is in master mode, there is an *ad_thread* that sends out advertisements periodically.

When the router is in backup mode, there is an *is_master_down* thread that constantly polls the master_down_timer to see whether or not the master is down.

#### Config Files
- **VR_IP_CONFIG**
- First 3 lines contain a mapping from interface to IP that the virtual router is responsible for.
- Last 2 lines contain the IPs for the designated VRRP interfaces so that the virtual routers know where to send out VRRP advertisements.

- **VR_PRIORITY_TABLE**
- First line is ignored (just there so I remember what the file represents)
- Lines are mappings from virtual router id to port to priority. The port is meant to the POX controller is running on.

### Tradeoffs
VRRP packets cannot be sent while there is only one router up, but there will be a lot of ad packets queued up for it (depending on ad interval). Thus VRRP advertisements are not queued into arpcache more than once for the same IP.