---
# System prepended metadata

title: README.md

---

# README.md



## Team Members
Efkan Serhat
utorid: goktepee

Mohammad Anwar
utorid: anwarmo4

## Contributions
### Efkan
* Finding longest prefix match
* Building ICPM type-3 header
* Build IP headers for ICMP-T3 headers
* Decrement TTL of incoming packet
* Recalculate checksum after TTL Decrement
* sr_arpcache_sweepreqs & appropriate ICMP-T3 replies
* Find reply interface using eth address for ICMP-T3 replies

### Mohammad
* Handled echo replies
* Handled ARP requests
* Handled ARP replies 
* Sending ARP request when MAC not found in cache
* Sanity checks on various packets; checking packet length and checksum
* Forwarding packet after next hop address is determined
* Reducing request latency

## Documentation

### Requirements
In what follows we describe how we achieved the required functionality. Many of the function names indicate exactly what they do so we have interpolated the function names with text to indicate what order our logic is run in. Function names are interpolated `in this style`.

1. The router must successfully route packets between the Internet and the application servers.

This functionality is achieved by `sr_handlepacket` which determines whether the request is an IP request and calls `handle_ip_packet` if so. This function checks that the `ip_packet_has_minimum_length` and that the `checksum_is_correct`. If so, it checks if the `packet_is_for_us`, i.e. for one of our interfaces. For forwarding to occur the packet must not be for us.

In such a case we check that the TTL is greater than one (`ttl_gt_one`) and if sowe calculate the forwarding address using `get_lpm`. We then `decrement_ttl` and call `forward_packet` to handle the forwarding logic.

`forward_packet` resolves the outgoing interface for the packet and looks up the hardware address in the arp cache. If the destination hardware address does not exist, it queues the packet in the arp request queue and calls `handle_new_arpreq` to send out an arp request immediately.

Otherwise, it calls `update_eth_headers` to set the destination and source hardware addresses and then sends the packet. 

2. The router must correctly handle ARP requests and replies.

The ARP packet handler, `handle_arp_packet` is called by `sr_handlepacket` after it determines it has received an ARP packet. The handler checks if the `arp_packet_has_correct_length` and then ensures that the target ip of the packet is the current interface (`target_ip_is_current_interface`). 

Next it checks if the request `is_arp_request` type and if so ensures that the `source_ip_in_routing_table`. If this check passes it calls `handle_arp_request` which constructs an ARP reply and sends it back.

If the arp packet is not a request type, we check if it `is_arp_reply` type. If it is, we `handle_arp_reply` by updating the arp cache with the new IP -> MAC mapping. Finally, we send out all the queued packets on the arp request and then delete the entry from the cache.

3. The router must correctly handle traceroutes through it (where it is not the end host) and to it (where it is the end host).

This is accomplished by forwarding IP packets as normal. In our case, if we received a packet whose TTL is expired then we send out a time exceeded response.

4. The router must respond correctly to ICMP echo requests.
As mentioned above, during `handle_ip_packet` we check if the `packet_is_for_us`; this checks if the packet is destined to any of our interfaces. If so we then check if it `is_icmp_request`. In this case, we call the respective handler, `handle_icmp_packet`.

The handler checks if the packet `has_min_icmp_length` and ensures that `icmp_checksum_is_correct`. Finally it checks if the packet `is_icmp_ping` and then calls `send_echo_reply`. This function builds calls `build_eth_headers`, `build_ehco_icmp_response_headers` and `build_echo_ip_response_headers` to construct the response packet and sends it out.

5. The router must handle TCP/UDP packets sent to one of its interfaces. In this case the router should respond with an ICMP port unreachable.

If we find that a `packet_is_for_us` in the previously mentioned check during IP packet handling and that it is not an icmp request, then we check if it is a TCP/UDP packet. In the case that it is, we send out an ICMP port unreachable packet.

6. The router must maintain an ARP cache whose entries are invalidated after a timeout period (timeouts should be on the order of 15 seconds).

This functionality is implemented by the starter code.

7. The router must queue all packets waiting for outstanding ARP replies. If a host does not respond to 5 ARP requests, the queued packet is dropped and an ICMP host unreachable message is sent back to the source of the queued packet.

As previously mentioned, when handling IP packets if we don't know their next hop MAC address, we queue them in the ARP queue and send an ARP request. `sr_arpcache_sweepreqs` gets called every second and loops through all requests in the queue. It calls `handle_arpreq` on each request which checks if the `request_is_expired`, in such a case it sends type 3 icmp replies to each packets origin and then destroys the arp request.

8. The router must not needlessly drop packets (for example when waiting for an ARP reply)

As mentioned, all packets are queued on to ARP requests. When the ARP reply is receieved, we send out the queued packets to the respective destination.

9. The router must enforce guarantees on timeouts–that is, if an ARP request is not responded to within a fixed period of time, the ICMP host unreachable message is generated even if no more packets arrive at the router. (Note: You can guarantee this by implementing the sr arpcache sweepreqs function in sr arpcache.c correctly.)

This functionality was covered in 7 above.


### Functions
#### sr_router.c
`void sr_handlepacket(struct sr_instance* sr, uint8_t * packet, unsigned int len, char* interface)`
    
    Description: Determine whether packet is ARP or IP and call appropriate handler

    Params: 
    - router instance
    - packet
    - length of packet
    - incoming interface
    
    Returns: 
        - Nothing
<hr/>
#### sr_arprequest.c
`void handle_arp_packet(struct sr_instance* sr, uint8_t * packet, unsigned int len, char* interface)`
    
    Description: Checks arp packet length and ensures it's destined for us. Calls appropriate handler for ARP requests and responses.

    Params: 
    - router instance
    - packet
    - length of packet
    - incoming interface
    
    Returns: 
        - Nothing
<hr/>

`int arp_packet_has_correct_length( unsigned int len)`
    
    Description: Checks if arp packet meets minimum length

    Params: 
    - length of packet
    
    Returns: 
        - 1 if it meets criteria
        - 0 if it does not meet criteria
<hr/>

`int int target_ip_is_current_interface(struct sr_instance* sr, char* interface, sr_arp_hdr_t * header)`
    
    Description: Checks if arp packet meets minimum length

    Params: 
    - router instance
    - interface name
    - arp header
    
    Returns: 
        - 1 if packet was meant for the provided interface
        - 0 otherwise
<hr/>

`int is_arp_request(sr_arp_hdr_t *header)`
    
    Description: Check if arp packet is a request

    Params: 
    - arp header
    
    Returns: 
        - 1 if it is a request
        - 0 otherwise
<hr/>

`int is_arp_reply(sr_arp_hdr_t *header)`
    
    Description: Checks if arp packet is a reply

    Params: 
    - arp header
    
    Returns: 
        - 1 if it is a request
        - 0 otherwise
<hr/>

`int source_ip_in_routing_table(struct sr_instance * sr, sr_arp_hdr_t * header)`
    
    Description: Checks if arp packet source ip is in our routing table using LPM

    Params: 
    - router instance
    - arp header
    
    Returns: 
        - 1 if we can find a longest prefix match
        - 0 otherwise
        
<hr/>

`void handle_arp_request(struct sr_instance* sr, uint8_t * packet, unsigned int len, char* interface)`
    
    Description: Builds and sends an arp reply

    Params: 
    - router instance
    - packet
    - length of packet
    - incoming interface
    
    Returns: 
        - Nothing
   
           
 <hr/>
 
`void build_arp_headers(uint8_t * reply, uint8_t * packet, sr_if_t * current_interface)`
    
    Description: Builds the arp headers for an arp reply given a packet

    Params: 
    - reply packet
    - original packet
    - outgoing interface
    
    Returns: 
        - Nothing       
 <hr/>
 
`void handle_arp_reply(struct sr_instance* sr, uint8_t * packet, unsigned int len, char* interface)`
    
    Description: Caches result from arp reply and sends pending packets

    Params: 
    - router instance
    - packet
    - length of packet
    - incoming interface
    
    Returns: 
        - Nothing              
          
  <hr/>
 
#### sr_iprequest.c

 
`void handle_ip_packet(struct sr_instance* sr, uint8_t * packet, unsigned int len, char* interface)`
    
    Description: Validates IP packet and calls appropriate handlers, ex icmp handler, tcp hander or forwarding logic after calculating LPM

    Params: 
    - router instance
    - packet
    - length of packet
    - incoming interface
    
    Returns: 
        - Nothing              

  <hr/>
 
`int ip_packet_has_minimum_length(unsigned int length)`
    
    Description: Checks if IP packet has minimum length

    Params: 
    - length of ip packet
    
    Returns: 
        - 1, if it meets minimum length
        - 0, otherwise
  <hr/>
 
`int checksum_is_correct(uint8_t * packet)`
    
    Description: Checks if IP packet has correct checksum
    
    Params: 
    - IP packet
    
    Returns: 
        - 1, if checksum is valid
        - 0, otherwise
  <hr/>
 
`int packet_is_for_us(struct sr_instance *sr, uint8_t *packet, char * interface)`
    
    Description: Checks if IP packet is destined for any of our interfaces
    
    Params: 
    - router instance
    - packet
    - incoming interface
    
    Returns: 
        - 1, if destined for any of our interfaces
        - 0, otherwise

  <hr/>
 
`int is_icmp_request(uint8_t *packet)`
    
    Description: Checks if IP packet is an ICMP request
    
    Params: 
    - IP packet
    
    Returns: 
        - 1, if it is an ICMP packet
        - 0, otherwise

  <hr/>
 
`void handle_icmp_packet(struct sr_instance* sr, uint8_t * packet ,unsigned int len,char* interface)`
    
    Description: Handles ICMP packet for us by validating it and calling echo reply handler
    
    Params: 
    - router instance
    - packet
    - packet length
    - incoming interface    
    
    Returns: 
        - Nothing
  <hr/>
 
`int has_min_icmp_length(unsigned int length)`
    
    Description: Checks if ICMP packet has minimum length
    
    Params: 
    - packet length   
    
    Returns: 
        - 1, if it has minimum length
        - 0, otherwise
  <hr/>
 
`int icmp_checksum_is_correct(sr_icmp_hdr_t * header, unsigned int length)`
    
    Description: Validates ICMP checksum
    
    Params: 
    - icmp header
    - length of packet
    
    Returns: 
        - 1, if checksum is valid
        - 0, otherwise
        
  
<hr/>
 
`int has_tcp_or_udp_payload(uint8_t *packet)`
    
    Description: Checks if a packet has udp or tcp payload
    
    Params: 
    - IP packet
    
    Returns: 
        - 1, if it does have a UDP/TCP payload
        - 0, otherwise
<hr/>
 
`void forward_packet(struct sr_instance* sr, uint8_t * packet , unsigned int len, char* interface, struct in_addr forward_address)`
    
    Description: Forwards a packet to its next hop
    
    Params: 
    - router instance
    - packet
    - length of packet
    - incoming interface
    - address to forward to
    
    Returns: 
        - Nothing
<hr/>
 
`char * get_outgoing_interface(struct sr_instance *sr, in_addr_t gateway_address)`
    
    Description: Determine the outgoing interface of a packet that is being forwarded
    
    Params:
    - router instance
    - next hop address
    
    Returns: 
        - name of outgoing interface
        
<hr/>
 
`void update_eth_headers(struct sr_instance* sr , uint8_t * packet, char * outgoing_interface_name, unsigned char * dest_hardware_address)`
    
    Description: Update ethernet headers to reflect hardware address of next hop and source address of outgoing interface
    - router instance
    - outgoing packet
    - outgoing interface name
    - destination hardware address
    
    Returns: 
        - Nothing
<hr/>

#### sr_icmpreply.c

 
`int is_icmp_ping(sr_icmp_hdr_t * header)`
    
    Description: Checks if ICMP packet is icmp ping
    
    Params: 
    - icmp header
    
    Returns: 
        - 1, if it is echo request
        - 0, otherwise
<hr/>
 
`void send_echo_reply(struct sr_instance* sr, uint8_t * packet ,unsigned int len,char* interface)`
    
    Description: Builds an ICMP echo reply and sends it out
    
    Params: 
    - router instance
    - packet
    - packet length
    - incoming interface 
    
    Returns: 
        - Nothing

<hr/>
 
`void build_echo_icmp_response_headers(sr_icmp_hdr_t * reply_icmp_header, unsigned int icmp_header_length)`
    
    Description: Builds ICMP headers for echo reply
    
    Params: 
    - icmp header for reply
    - icmp header for request
    - length of icmp reply header
    
    Returns: 
        - Nothing
        
<hr/>
 
`void build_echo_ip_response_headers(sr_ip_hdr_t * reply_ip_header, sr_ip_hdr_t * req_ip_header, sr_if_t * current_interface, unsigned int len)`
    
    Description: Builds IP headers for echo reply
    
    Params: 
    - IP header for reply
    - IP header for request
    - incoming interface
    - length of packet
    
    Returns: 
        - Nothing
<hr/>

`void build_icmp_t3_response_headers(sr_icmp_t3_hdr_t * reply_icmp_header, unsigned int icmp_header_length, uint8_t icmp_type, uint8_t icmp_code)`

    Description: Initialize the ICMP headers of a response
    
    Params:
    - An ICMP_T3 header
    - The length of the ICMP_T3 header
    - The type of the ICMP response
    - The code of the ICMP response
    
    Returns:
    - Nothing
    
<hr/>

`void build_t3_ip_response_headers(sr_ip_hdr_t * reply_ip_header, sr_ip_hdr_t * req_ip_header, sr_if_t * current_interface, unsigned int len){`

    Description: Initialize the IP headers of a response
    
    Params:
    - The reply IP header
    - The request IP header
    - The current interface
    - The length of the entire response frame
    
    Returns:
    - Nothing

<hr/>

` void send_icmp_t3_reply(struct sr_instance *sr, uint8_t *dest, uint8_t icmp_type, uint8_t icmp_code, char* interface)`

    Description: Send an ICMP_T3 reply
    
    Params:
    - An sr_instance
    - The packet to be delivered
    - The appropriate ICMP type
    - The appropriate ICMP code
    - The destination interface
    
    Returns:
    - Nothing

#### sr_arpcache.c
 
`void handle_new_arpreq(struct sr_instance *sr)`
    
    Description: Called whenever we make an entry to or update the arp request cache. It's purpose is to reduce request latency so we don't have to wait 1s for sweepreqs to send out the arp request for destinations whose hardware address we don't have. It works by taking control of the lock and looping through the cache. It calls `handle_arpreq`  for any arp requests that have not been sent at least once.
    - router instance
    
    Returns: 
        - Nothing

<hr/>
 
`void make_eth_headers(uint8_t * arp_request, sr_if_t * outgoing_interface)`
    
    Description: Builds ethernet headers for APR request
    - Arp request
    - outgoing interface
    
    Returns: 
        - Nothing
<hr/>
 
`void make_arp_request_headers(uint8_t * arp_request, sr_if_t * outgoing_interface, uint32_t destination_ip)`
    
    Description: Builds ARP request headers for arp request
    - Arp request
    - outgoing interface
    - destination ip
    
    Returns: 
        - Nothing
<hr/>
 
`int request_is_expired(struct sr_arpreq *request)`
    
    Description: Checks if ARP request is expired due to being sent over 5 times
    - Arp request
    
    Returns: 
        - Nothing
                               
        
<hr/>

`int ttl_gt_one(uint8_t *packet);`
    
    Description: Get whether a packet has TTL > 1
    
    Params:
    - A packet
    
    Return:
    - If the TTL of the packet is >1, returns 1
    - Otherwise, returns 0

<hr/>

`uint32_t get_lpm(struct sr_instance *sr, uint8_t *packet);`
    
    Description: Get the gateway address of the interface with the longest prefix match against the destination IP of `packet`
    
    Params:
    - An sr_instance
    - A packet
    
    Return:
    - If at least one match is found, returns the gateway IP address of router table entry with the longest matching prefix
    - Otherwise, returns 0 

<hr/>

`char *get_reply_interface_from_arp_req_packet(struct sr_instance * sr, uint8_t *packet);`
    
    Description: Get the name of the interface that has the same MAC address as the destination MAC address of`packet`
    
    Params:
    - An sr_instance
    - A packet

    Returns:
    - The name of the interface with eth address that matches the packet's dest address

<hr/>

`void sr_arpcache_sweepreqs(struct sr_instance *sr)`
    
    Description: Iterate through arp cache and handle each request one-by-one
    
    Params:
    - An sr_instance
    
    Returns:
    - Nothing

<hr/>

`void handle_arpreq(struct sr_instance * sr, struct sr_arpreq * request)`
    
    Description: Check if the ARP request is expired, and if so, send "ICMP: Host Unreachable" reply and destroy it. Otherwise build an ARP request and broadcast it.
    
    Params:
    - An sr_instance
    - An ARP request
    
    Returns:
    - Nothing
    
<hr/>


### utils.c

<hr/>

 `sr_icmp_t3_hdr_t *get_icmp_t3_hdr(uint8_t *packet)`
 
    Description: Get the ICMP_T3 headers of a packet
    
    Params:
    - A packet
    
    Returns:
    - An ICMP_T3 header
<hr/>

 `sr_ethernet_hdr_t * get_eth_header(uint8_t * packet)`
 
    Description: Get the ethernet header of a packet
    
    Params:
    - A packet
    
    Returns:
    - An ethernet header
<hr/>

 `sr_arp_hdr_t * get_arp_header(uint8_t * packet)`
 
    Description: Get the arp header of a packet
    
    Params:
    - A packet
    
    Returns:
    - An arp header
<hr/>

 `sr_icmp_hdr_t * get_icmp_header(uint8_t *packet)`
 
    Description: Get the icmp header of a packet
    
    Params:
    - A packet
    
    Returns:
    - An icmp header
 <hr/>
 
`void build_eth_headers(uint8_t * reply, uint8_t * packet, sr_if_t * current_interface)`
    
    Description: Builds the eth headers for a reply given a packet

    Params: 
    - reply packet
    - original packet
    - outgoing interface
    
    Returns: 
        - Nothing    
## Test Cases and Results

Before running each test below, run `./sr -l log.pcap`
After running the test command, inspect the recorded network logs via Wireshark to reach the conclusions under each test.

We passed all tests below.

`mininet> client ping -c 1 192.168.2.2`
- Pings server1
- Checks that the correct LPM is being found
- Checks that packets are being forwarded properly
- Checks that packets with exhausted TTL are dropped
    - Checks that (ICMP_T3: TTL Exceeded) response is being sent when this occurs

<hr/>

`mininet> client ping -c 1 192.168.65.93`
- Attempts to ping a non-existent destination
- Checks that the edge case when no prefix match found is handled properly
- Checks that (ICMP_T3: Network Unreachable) response is being sent in this scenario

<hr/>

`mininet> client nping -c 1 --udp 10.0.1.1`
`mininet> client nping -c 1 --tcp 10.0.1.1`
- Attempts to ping a TCP/UDP payload destined for the router
- Checks that TCP/UDP payloads destined for the router are dropped
- Checks that (ICMP_T3: Network Unreachable) response is being sent in this scenario

<hr/>

`mininet> client traceroute 192.168.2.2`
- Checks that ICMP/ICMP_T3 responses are working properly
<hr/>

`mininet> client ping 10.0.1.100`
- Checks that router correctly responds to ping request

<hr/>

`mininet> client ping 192.168.2.2`
- Checks that router correctly responds to ping request on any of its interfaces


<hr/>

`mininet> client traceroute 10.0.1.100`
- Checks that traceroute to router works correctly

<hr/>

`mininet> client traceroute 192.168.2.2`
- Checks that traceroute to any of routers interfaces works correctly

<hr/>

`client nping --arp-type ARP 10.0.1.1`
- Checks that arp replies are correctly receieved from the router

<hr/>

`client curl 192.168.2.2/index.html`
- Checks that client can correctly download files over HTTP


<hr/>

We tested that the ARP cache correctly destroys ARP requests that have timed out by doing the following:

1. Disable ARP reply handling by commenting out line 49 of `sr_arprequest.c`
2. Add a print statement to line 58 of `sr_arpcache.c` which runs once an ARP entry is destroyed.
3. Ran the router and had the client ping a server.
