Network Programming
Assignment 4 (Tour with ARP)

Last updated April 24 (stable version).

Due Monday, May 12th.
Please note that this is a hard deadline. No extensions will be granted, period. If your submission is not in on time, it simply will not be graded.

You are to work on this assignment in groups.

As I get feedback from students and realize that parts of this write-up  need to be extended, corrected, and/or further clarified, I shall update the contents and the Last Updated date. Updated / modified parts will be in bold blue for easy identification. Please check this web page periodically to make sure you have the latest version.

Overview

For this assignment you will be developing an application that uses raw IP sockets to ‘walk’ around an ordered list of nodes (given as a command line argument at the ‘source’ node, which is the node at which the tour was initiated), in a manner similar to the IP SSRR (Strict Source and Record Route) option. At each node in the tour, the application pings the source node. However, unlike the ping code in Stevens, you will be sending the ping ICMP echo request messages through a SOCK_RAW-type PF_PACKET socket and implementing ARP functionality to find the Ethernet address of the destination node. Your code will thus consist of two process modules, a ‘Tour’ application module and an ARP module.

The following should prove to be useful reference material for the assignment:

The  VMware  environment

You will be using the same vm1 , . . . . . , vm10 nodes you used for Assignment 3. However, unlike Assignment 3, you should use only interfaces eth0 and their associated IP addresses and ignore the other Ethernet interfaces that nodes might have (interfaces eth0 make vm1 , . . . . . , vm10 look as if they belong to the same Ethernet LAN 192.168.1.0/24). Note that, apart from the primary IP addresses associated with interfaces eth0, some nodes might also have one or more alias IP addresses associated with their interface eth0.

Tour application module specifications

  1. The application creates two IP raw sockets, which we shall call the rt (‘route traversal’) and pg (‘ping’) sockets. The rt socket should have the IP_HDRINCL option set. You will only be receiving ICMP echo reply messages through the pg socket (and not sending echo requests), so it does not matter whether it has the IP_HDRINCL option set or not.

    The pg socket should have protocol value (i.e., protocol demultiplexing key in the IP header) IPPROTO_ICMP.

    The rt socket should have a protocol value that identifies the application - i.e., some value other than the IPPROTO_XXXX values in  /usr/include/netinet/in.h. However, remember that you will all be running your code using the same root account on the vm1 , . . . . . , vm10 nodes. So if two of you happen to choose the same protocol value and happen to be running on the same vm node at the same time, your applications will receive each other’s IP packets. For that reason, try to choose a protocol value for your rt socket that is likely to be unique to yourself.

  2. The application also creates a third socket, a PF_PACKET socket of type SOCK_RAW (not type SOCK_DGRAM). This socket should have a protocol value of  ETH_P_IP = 0x0800 (IPv4).

  3. As with the ping code of Section 28.5, when your application is evoked it should be able to accept the verbose ‘-v’ option as the first (and possibly only) command line option. If this option is enabled, the application prints out details of all IP packets that are mis-delivered to the rt and pg sockets (cf. lines 28-31 of Figure 28.8,  p. 748. But note that this code corresponds to ICMP echo reply arriving on the pg socket. You will also have to do something similar with respect to misdirected IP packets arriving on the rt socket).

  4. Your application will, of course, have to be running on every vm node that is included in the tour. One such node has to be distinguished as the source node. When evoking the application on this particular node, and after the -v command line option if present, the user supplies a sequence of vm node names (not IP addresses) to be visited in order. This sequence starts with the next node to be visited from the source node (i.e., it does not start with the source node itself). The sequence can include any number of repeated visits to the same node (including the source node). For example, suppose that the source node is vm3 and the executable is called badr_tour :

    [root@vm3/root]# badr_tour [-v] vm2 vm10 vm4 vm7 vm5 vm2 vm6 vm2 vm9 vm4 vm7 vm3 vm6 vm5 vm1 vm10 vm8 vm3

    (but note that the tour does not necessarily have to visit every vm node, and does not necessarily have to end at the source node).

    The application turns the sequence into a list of IP addresses for source routing. It also adds the IP address of the source node itself to the list, but in such a way that this particular entry is distinguished as the identification of the source node, and not part of the sequence of nodes to be visited. The list thus produced will be carried as the payload of an IP packet, not as a SSRR option in the packet header. It is our application which will ensure that every node in the sequence is visited in order, not the IP SSRR capability.

    The application then fills in the header of an IP packet, designating itself as the IP source, and the next node to be visited as the IP destination. The packet is sent out on the rt socket. Note that on Linux, all the fields of the packet header must be in network byte order (Stevens, Section 28.3, p. 737, the fourth bullet point).

    When filling in the packet header, you should explicitly fill in the identification field (recall that, with the IP_HDRINCL socket option, if the identification field is given value 0, then the kernel will set its value). Try to make sure that the value you choose is likely to be unique to yourself (for reasons similar to those explained with respect to the IPPROTO_XXXX in 1. above).

  5. When a node receives an IP packet on its rt socket, it should first check that the identification field carries the right value (this implies that you will hard code your choice of identification field value determined in 4. above in your code). If so, it should print out a message along the lines of:

    <time>   received source routing packet from <hostname>.
    <time> is the current time in human-readable format (see lines 19 & 20 in Figure 1.9,  p. 14, and the corresponding explanation on  p. 14f.), and <hostname> is the host name corresponding to the source IP address in the header of the received packet. Note that if the identification field value does not check out, and the -v option is enabled on this node, then you have to print out a message as per 2. above. Otherwise, the packet is ignored.

    For a valid packet, the application updates the list in the payload, so that the next node in the tour can easily identify what the next hop from itself will be when it receives the packet. How you do this I leave up to you. You could, for example, include as part of the payload a pointer field into the list of nodes to be visited. This pointer would then be updated to the next entry in the list as the packet progresses hop by hop (see Figure 27.1 and the associated explanation on  pp. 711-712). Other solutions are, of course, possible. The application then fills in a new IP header, designating itself as the IP source, and the next node to be visited as the IP destination. The identification field should be set to the same value as in the received packet. The packet is sent out on the rt socket.

  6. If this is the first time the node is visited, it should also initiate pinging to the source node (the IP address of which it should pick up from the payload of the received packet). However, unlike the Stevens ping code, it will be using the SOCK_RAW-type PF_PACKET socket of 2. above to send the ICMP echo request messages.

    Before it can echo request messages, the application has to call on the ARP module you will implement to get the Ethernet address of the source node; this call is made using the API function areq which you will also implement (see sections ARP module specifications & API specifications below).Note that ARP has to be evoked every time the application wants to send out an echo request message, and not just the first time.

  7. An echo request message has to be encapsulated in a properly-formulated IP packet, which is in turn encapsulated in a properly-formulated Ethernet frame transmitted out through the PF_PACKET socket ;  otherwise, ICMP at the source node will not receive it. You will have to modify Stevens’ ping code accordingly, specifically, the send_v4 function. In particular, the Ethernet frame must have a value of  ETH_P_IP = 0x0800 (IPv4 – see <linux/if_ether.h>) in the frame type / ‘length’ field ;  and the encapsulated IP packet must have a value of  IPPROTO_ICMP = 0x01 (ICMPv4 – see <netinet_in.h>) in its protocol field.

    You should also simplify the ping code in its entirety by stripping all the ‘indirection’ IPv4 / IPv6 dual-operability paraphernalia and making the code work just for IPv4. Also note that the functions host_serv and freeaddrinfo, together with the associated structure addrinfo (see Sections 11.6, 11.8 & 11.11), in Figures 27.3, 27.6 & 28.5 ( pp. 713, 716 & 744f., respectively) can be replaced by the function gethostbyname and associated structure hostent (see Section 11.3) where needed.

  8. When a node is ready to start pinging, it first prints out a ‘PING’ message similar to lines 32-33 of Figure 28.5,  p. 744. It then builds up ICMP echo request messages and sends them to the source node every 10 seconds through the PF_PACKET socket. It also reads incoming echo response messages off the pg socket, in response to which it prints out the same kind of output as the code of Figure 28.8,  p. 748. If the node has been visited before during the tour, then pinging would have already been initiated in response to the first visit, and nothing further need be done.

    In light of the above, note that once a node initiates pinging, it needs to read from both its rt and pg sockets, necessitating the use of the select function. Also note that if the source node itself is part of the tour, then it will initiate pinging to itself.

ARP module specifications

Your executable is evoked with no command line arguments. Like the Tour module, it will be running on every vm node.

  1. It uses the get_hw_addrs function of Assignment 3 to explore its node’s interfaces and build a set of  <IP address , HW address>  matching pairs for all eth0 interface IP addresses (including alias IP addresses, if any).

    Write out to stdout in some appropriately clear format the address pairs found.

  2. Creates a PF_PACKET of type SOCK_RAW (not type SOCK_DGRAM) with a protocol value of your choice (but not one of the standard values defined in <linux/if_ether.h>) which is, hopefully, unique to yourself. This value effectively becomes the protocol value for your implementation of ARP. Because this protocol value will be carried in the frame type / ‘length’ field of the Ethernet frame header (see Figure 4.3 of the ARP & RARP handout), the value chosen should be not less than 1536 (0x600) so that it is not misinterpreted as the length of an Ethernet 802.3 frame.

    Creates a Unix domain SOCK_STREAM-type (not SOCK_DGRAM) listening socket bound to a ‘well-known’ sun_path file.

    The ARP module then sits in an infinite loop, monitoring these two sockets.

  3. As ARP messages arrive on the PF_PACKET socket, the module processes them, and responds with ARP reply messages as appropriate.

    The protocol builds a ‘cache’ of matching  <IP address , HW address>  pairs from the replies (and requests – see below) it receives. For simplicity, and unlike the real ARP, we shall not implement timing out mechanisms for these cache entries.

    A cache entry has five parts: (i) IP address ;  (ii) HW address ;  (iii) sll_ifindex (the interface to used for reaching the matching pair <(i) , (ii)>) ;  (iv) sll_hatype ;  and (v) a Unix-domain connection-socket descriptor for a connected client (see the section API specifications below for the latter three). When an ARP reply is being entered in the cache, the ARP module uses the socket descriptor in (v) to send a reply to the client, closes the connection socket, and deletes the socket descriptor from the cache entry.

    Note that, like the real ARP, when an ARP request is received, the sender’s (see Figure 4.3 of the ARP & RARP handout) <IP address, HW address> matching pair should be entered into the cache if it is not already there (together, of course, with (iii) sll_ifindex &  (iv) sll_hatype).

  4. ARP request and reply messages have the same format as Figure 4.3 of the ARP & RARP handout, but with an extra 2-byte identification field added at the beginning which you fill with a value chosen so that it has a high probability of being unique to yourself. This value is to be echoed in the reply message, and helps to act as a further filter in case some other student happens to have fortuitously chosen the same value as yourself for the protocol parameter of the ARP PF_PACKET. Values in the fields of our ARP messages must be in network byte order.

  5. Your code should print out on stdout, in some appropriately clear format, the contents of the Ethernet frame header and ARP request message you send. As described in Section 4.4 of the ARP & RARP handout, the node that responds to the request should, in its reply message, swap the two sender addresses with the two target addresses, as well as, of course, echo back the extra identification field sent with the request. The protocol at this responding node should print out, in an appropriately clear format, both the request frame it receives and the reply it sends. Similarly, the node that sent the request should print out the reply frame it receives. Finally, recall that the node issuing the request sends out a broadcast Ethernet frame, but the responding node replies with a unicast frame.

API specifications

  1. The API is for communication between the application process and the ARP process. It consists of a single function, areq, implemented in the Tour module. areq is called by send_v4 function of the application every time the latter want to send out an ICMP echo request message : 
    int areq (struct sockaddr *IPaddr, socklen_t sockaddrlen, struct hwaddr *HWaddr);
     IPaddr contains the primary or alias IPaddress of a node on the LAN for which the corresponding hardware address is being requested, including an IP address for the very node at which the Tour and ARP modules are running.

    hwaddr is a new structure (and not a pre-existing type) modeled on the sockaddr_ll of PF_PACKET; you will have to declare it in your code. It is used to return the requested hardware address to the caller of areq : 
    structure hwaddr {
		     int             sll_ifindex;	 /* Interface number */
		     unsigned short  sll_hatype;	 /* Hardware type */
		     unsigned char   sll_halen;		 /* Length of address */
		     unsigned char   sll_addr[8];	 /* Physical layer address */
};
  2. areq creates a Unix domain socket of type SOCK_STREAM and connects to the ‘well-known’ sun_path file of the ARP listening socket. It sends the IP address from parameter IPaddr and the information in the three fields of parameter HWaddr to ARP. It then blocks on a read awaiting a reply from ARP. This read should be backed up by a timeout since it is possible that no reply is received for the request. If a timeout occurs, areq should close the socket and return to its caller indicating failure (through its int return value).

    Your application code should print out on stdout, in some appropriately clear format, a notification every time areq is called, giving the IP address for which a HW address is being sought. It should similarly print out the result when the call to areq returns (HW address returned, or failure).

  3. When the ARP module receives a request through its Unix domain listening socket, it first checks if the required HW address is already in the cache. If so, it can reply immediately and close the connection socket. Else, it makes an ‘incomplete’ entry in the cache, consisting of parts (i), (iii), (iv) and (v) ;  sends an ARP request message out on its PF_PACKET socket; and starts monitoring the client connection socket for readability :  if the client closes the connection, the ARP module deletes the corresponding incomplete entry from the cache.

Hand-in

Submit your code on the minix node using the  electronic hand-in  procedure provided. Your submission must absolutely include :

a Readme file which identifies the members of the group;
a Makefile which

Valid HTML 4.01! Valid CSS!