******************************************************************************* * Simple Router * ******************************************************************************* i. Group Information - Group Number: 1 - Group Members: * Denny Chen Dai (cda18) * Nicholas Erho (nge2) - Default Topology: 26 ii. Work Division Note that all functions developed by a group member are clearly labeled in the function comments in the source code. Also note that subversion was not utilized to handle version management as it was more efficient to handle it ourselves. Finally, the individual that implemented the code was typically the one responsible for testing, although overall system testing was done by both individuals. - Denny: * Checksum * Router Echo Reply * Handling in coming ARP * Traceroute * ICMP Port Unreachable * ICMP Time Exceeded - Nicholas: * ARP Table * Packet Queue * Packet Forwarding * Packet Routing * Sending ARP Requests * Packet timeout * ICMP Host Unreachable iii. Known Bugs and Issues - ARP replies are received from hosts which have the same MAC address but different IP address and listed in the table. This is most likely a fault with the virtual network rather than the router, however it does not effect the packet handling of the system. - Since events are driven only packets entering the router, if the flow of packets is not fast enough, events that are scheduled at a give time may not execute at that exact time, but instead will be delayed till the next packet enters the system. This is not a issue in the virtual server environment as the router higher in the hierarchy sends enough ARP requests to keep the router almost always active. iv. Code Design - Data structures In addition to the interface table and the routing table, a linked list ARP table was added and a packet queue for each entry in the ARP table. The basic idea is that the routing table creates a mapping between destination IP addresses and interfaces, the interface table creates a mapping between interfaces and router MAC and IP addresses, while the ARP table makes a mapping between destination IP addresses and destination MAC addresses, where each ARP entry has a queue of packets waiting to be transmitted to that destination. It is easy to see there is a relationship between all the data structures. - Code Design There are two basic data flows in our router. Either we are receiving a packet for the router to process or we are receiving a packet to be passed through the router to its destination. Since threading was not used, packet handling only occurs when packets arrive at the router. This may cause the time when events expire to not be the exact time they are handled as there could be a case where not enough packets are entering the system to cause the event to trigger at the correct time, however this is not a big issue because the next router higher up in the virtual network hierarchy is sending enough ARP packets to keep our router always active. When packets are routed through the router, they are always queued in the queue listed in the ARP table whether they can be sent or not. This allows for a consistency in the packet pass through processing, where all packets are queue then sent if they have a valid ARP entry or an ARP request is sent on their behalf. Packets need to be queue because if no valid ARP entry is valid for the packets destination the packets must wait for the ARP request to be replied, during this time other packets must be proceed. Because of this design the ARP table will contain entries which are invalid, indicated with a negative expiry time. These invalid entries are never used to send packets until they are validated with an ARP reply but are necessary as the packet queue is associated with a destination address using the ARP table. It should be noted that as soon as an ARP entry is validated all the waiting packets in that queue will be sent to the destination. In the case that a packet is received and there is already a valid ARP entry, although the packet is queue it will be sent out right away. The packets in the queue are associated with an expiry time. This expiry time tells the system when to send the next ARP or how long to wait until a packet should be dropped after the last of the five ARP requests is sent. This expiry time is checked every time the router is active and if any of the queues have expired the ARP count of the first packet in the queue is checked. If this packet has some ARP request left the next ARP request is sent out, the packet ARP count is decreased, and the queue is schedule again for the next update. If it happens that the first queue packet has no ARP requests left then the packet is dropped and an ICMP host unreachable error is sent to the original sender of the packet. Using an expiry time in this manner allows the wait time for ARP requests to be adjusted and helps prevent the network from being flooded with ARP requests. After all the packets in the queue had been sent or dropped and the ARP entry expires becoming invalid then the ARP entry is dropped. This ensures a small current ARP table will persist. - ICMP Protocol Handling (sr_icmp.c) A common function named "sr_construct_ICMP" is used to construct ICMP data packet (struct sr_icmp_packet) from stracth. This structure includes Ehternet Header (struct sr_ethernet_hdr), IP header (struct ip) and ICMP header (struct sr_icmp). Three types of ICMP packets are used: ICMP Time Exceeded, ICMP Port Unreachable and ICMP Host Unreachable. The ICMP packet also includes the IP header of the original data packet and the first 8 bytes of the orginal UDP datagram. ICMP echo reply are handled differently by resuing the original echo request packet and modifying existing fields (MAC, IP address field, etc.). - Work Flow ( sr_router.c::sr_handlpacket() ) The workflow is briefly described below 1. ARP table update (for any ethernet packet) 2. Ethernet Protocol Handling *. ERP Protocol Handling (ETHERTYPE_ARP) reply to ARP request *. IP Protocol Handling (ETHERTYPE_IP) a. IP Checksum b. Time Out Handling (ip_ttl) Response with ICMP_Echo_Reply or Time_Exceed c. Queue Packet (if to be forwarded) d. Protocol Handling (Trans' Layer) * ICMP Protocol Handling (IPPROTO_ICMP) * UDP /TCP (Others) Handling Response with ICMP_Port_Unreachable 3. Update packet queue Forward packet / send ARP_Request / send ICMP_Host_Unreachable v. Test Plan Issuing command: ./sr -s vns-1.stanford.edu -t 26 1. Packet Pass Through * Ping 171.67.236.34 and ping 171.67.236.36 and make sure a ping is received back. * Access 171.67.236.34 using a web browser and make sure all pages and files are accessible. 2. Router Ping * Ping 171.67.236.32 and make sure a ping is received back. 3. Trace Route Pass Through * Traceroute 171.67.236.36 and make sure the router and host are displayed in the traceroute output. 4. Trace Router * Traceroute 171.67.236.32 and make sure the router is listed at the end of the traceroute output. 5. ICMP Port Unreachable * Access 171.67.236.32 with a web browser on a machine running Wire Shark, a ICMP port unreachable packet should be sent by the router and listed in Wire Shark. 6. ICMP Host Unreachable * Block access to 171.67.236.36 and ping 171.67.236.36 while running Wire Shark. Check to see if the ICMP host unreachable packet is listed in Wire Shark.