Name: Jason Ruan
PID: A09988265
Email: jruan@ucsd.edu
Not Participating in the Espresso Prize


Introduction: 

In this project, we are suppose to implement some of the basic functionalities of a router. This list includes:
	1) The router must successfully route packets between the Internet and the application servers.
	2) The router must correctly handle ARP requests and replies.
	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).
	4)The router must respond correctly to ICMP echo requests.
	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.
	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).
	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.
	8)The router must not needlessly drop packets (for example when waiting for an ARP reply)
	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.)

In the remaining part of this documentation, I will go over how I have successfully implemented each aspect of my router.


Implementations:

	Routing packets between the internet and application servers. The code that handle most of this is in the sr_handlepacket function in sr_router.c file. In this function, I first had to distinguish whether or now it is an ARP packet or an IP packet. To do this, I look at the protocol type of the ethernet header. Next, once we figure out what type of packet it is, we will do two things depending on what type of packet it is. So, I will first explain what to do if it is an ARP packet taking care of require number 2 listed above. If it is an ARP packet, we must first distinguish if it is an ARP request packet or ARP reply packet. To do this, there is an arp_op field in the arp packet that we can check. If it is an 1, it is an request. Else, if it is a two, it is a reply. For request ARP packets, we must check the ar_tip field of the ARP request packet to see which interface of our router is the device asking for. Then call the construct_arpreply_packet function which i define so i can reuse the method later if i need to create anymore arp reply packets. What the construct_arpreply_packet function does is that it will take in the headers of the old packet, the sr_if struct corresponding to the requested interface and build a arp reply packet to send back to the requesting device. So, in order to do that, the construct_arpreply_packets function will first take the ar_sha and ar_sip of the original arp request packet and assign it ask our reply packet's new destination so our reply will be sent to them. Next, we will assign the ar_sha and ar_sip to the requested ip and mac address that we get by simply accessing the fields from our sr_if interface struct. When these are done, our arp reply is finish and we will send it back to the requester and the requester will proceed to send us the ip packet. 

	Next, what to do if it is an ARP reply. Then what we do is we will call sr_arpcache_insert which was already define for us to fist insert into our mac address cache the newly discover mac address. The mac cache maps the mac address to its corresponding ip so if we need to use that mac address later on, it will be quick for us to just look in the cache instead of sending out a request for mac address. Next, because sr_arpcache_insert returns a request struct, we traverse through each packet pending on that request and send them out to its proper destination now we know the destination ip mac address. To send it out, I called the construct_ip_forward_packets function which takes in the original packet and its length. Then all it does is modify the ethernet source address to the interface mac address that we will be sending out the packet to and modify the ethernet dest address to our newly discovered mac address. Same with ip src address. Change that to our the interface that we are sending out of ip address and recalculate the ip check sum. Finally, decrement the TTL of the packet and recalculate the icmp checksum. The rest of the packet should remain the same and finally, we call sr_send_packets to send this packet out.

	Now that we have taken care of what to do with ARP packets, it is time to take care of what to do with IP packets. With IP packets, we must also make two distinctions. First, before doing anything, we must check that the checksum is correct and the IP headers are correct. To do that, I have define the function check_ip_hdr_correctness that bassically checks to see if the packet has the correct ip version number, the correct header length, and the correct packet length. Also, I have also defined a function perform_cksum_check which basically recalculates the checksum of the header by calling the define cksum function in sr_utils.c file and comparing it with the checksum header of the ip header. If it matches, then everything is fine and we can proceed to handling the IP packet. Next, we must check if the IP packet is for the router or not by checking if the destination ip on the packet is one of our routers interfaces. If it is, we then check if the protocol is icmp protocol or some other protocol. To do this, we just need to look at the ip_p field in the ip header. If the protocol is an icmp protocol, then we will create a ping response back to the requester of the ping. To do so, I have defined a construct_icmp_response_packet that will take the original packet, switch the ip source field with the ip dest field, switch the ethernet src address with the ethernet dest address, reset the TTL field for the icmp packet, change the type to a response type, and create this new icmp response packet to send back to the requester. On the other hand however, if the IP packet is not an icmp protocol but a UDP/TCP protocol, then what I did was called construct_icmp_error_packets which i passed in the original packet again so we can switch src addresses with dest addresses, set the type to the correct type, code to correct code, create the icmp error response packet and send it back to the requester. The two methods construct_icmp_response_packets and construct_icmp_error_packets are defined in the sr_router.c file which allows us to reuse these two functions whenever we need to construct either a response packet or an error packet.

	So far, we have taken care of handling IP packets that are for the router. Next, we will handle packets that are not for the router. If a packet is not for the router, then we must first check our routing table and perform the longest prefix matching to see if there is a server that is connected to this router that the packet can reach. To perform the longest prefix matching functionality, I defined a perform_LMP function which again allows for reuse later on. What this method does is that it will take a destination ip and AND mask it with the mask of each entry in our routing table. Then it will take each destination ip in our routing table and AND it with its proper match. We will next compare the two and if it is equal, then we have a match meaning the destination that the IP packet is going to is alive. If it is alive, we will again call construct_ip_forward_packet to construct a new packet to send to the requested destination. Now, before all of this however, I have missed to talk about one very important check. That is the TTL check. We must check that the TTL is large enough to even make it to the next destination. If it is, we will proceed and do everything described above. If not, we will call construct_icmp_error_packets and construct the proper icmp error response corresponding to handling TTL and send it back to the sender. 
	
	Now that forwarding packets to some server that is alive is impelemented, its time to take care of what if there is not longest prefix match for the destination ip. If this happen, we will again call construct_icmp_error_packets to construct the proper error response with the proper type and code to send back to the sender.

	So far, we have taken care of most functionalities a router should have. The last thing to take care of is sending arp requests and what to do if more than 5 arp requests have been sent. This scenario can occur if we ping to some ip that is specified to be connected to one of our interface but is acutally not there. Thus, when we send and ARP request to this non existent ip address, no response will ever be replied back. So, what we do is in sr_arpcache.c file, there is this function sr_handlearp that will be called every second. When it is called, it will check if a request have been sent more than 5 times. If not, it will resend that request and increment the number of times sent by one. If the number of times is sent more than 5 times, then again, call construct_icmp_error_packet to send the proper icmp error response back to each sender of each packet waiting for that request and destroy that request entirely at the end. With this last implementation, we have done everything needed to be done for this project.