Now we have implemented the SRT protocol for DartNet. Let’s look at the overlay network layer design in the protocol stack. DartNet operates on an overlay network, the topology of which is defined by a file topology.dat. We are using an overlay because we can not run our Simple Network Protocol (SNP) - which, we design and implement in Lab7 - on real routers in the Internet. So like P2P applications we use the overlay concept to build network nodes - routers - at end systems. In essence, we implement the Internet routers on edge machines and then create a network of these overlay nodes in terms on a routing graph. This allows us to implement SNP on edge overlay nodes - this is a very cool way to get around the restriction of not being able to change router code. This is how we get to build the complete DartNet stack - the overlay network provides the “clue”.
The overlay network layer is implemented in a process. We will call the overlay network layer the overlay network (ON) process. The ON process maintains TCP connections with all of its neighbors and a local TCP connection with the SNP layer (which is also implemented as a process). We will call the SNP layer the SNP process. The ON process has multiple threads. For each TCP connection to a neighbor, there is a listen_to_neighbor thread which keeps receiving packets from that neighbor and forwarding the received packets to the SNP process. For the TCP connection between the ON process and the SNP process, the main thread keeps receiving sendpkt_arg_t structures which contain packets and the next hops’ nodeIDs from the SNP process and sending these packets to the next hop nodes.
In this lecture, we will discuss the design of overlay network layer in details. Much of the information presented in this lecture is important in completing Lab6 on the implementation of the overlay network.
We plan to learn the following from this lecture:
OK, let’s get going
DartNet is built on an overlay network. This overlay network’s topology is defined in a file called
topology.dat. Each line in topology.dat has the following format:
host1 host2 link cost
where host1 is the hostname of a computer, host2 is the hostname of another computer, and link cost is the cost of the direct link between these two hosts which will be used in SNP routing protocol. For example, a line “spruce.cs.dartmouth.edu bear.cs.dartmouth.edu 4” in topology.dat means there is a link which has link cost of 4 between host spruce and host bear in our overlay network. The topology used in lab6 is shown in Fig. 1
In DartNet, we use nodeID to identify a host. nodeID has the similar role as an IP address in TCP/IP. The nodeID is an integer represented by the last 8 digit of the host’s IP address. For example, a host with IP address “126.96.36.199” as a node ID of 36.
The ON process diagram is shown in Fig. 2. There are 4 nodes in our overlay network. On each node, there is an ON process running. On each node, there is also a SNP process running. The ON process and SNP process is connected with a local TCP connection. Each ON process maintains TCP connections to all the neighboring nodes. For example, the upper left node have 3 neighboring nodes in the overlay network. There is a TCP connection to each of the neighboring nodes.
The thread diagram for the ON process of the upper left node is shown in Fig. 3. The upper left node have 3 neighboring nodes in the overlay network. For each TCP connection to a neighbor, there is a listen_to_neighbor thread. The listen_to_neighbor thread keeps receiving packets from that neighbor and forwarding the received packets to the SNP process. For the TCP connection between the ON process and SNP process, the main thread keeps receiving the sendpkt_arg_t structures which contain packets and the next hops’ nodeIDs from SNP process and sending these packets to the next hop nodes.
he ON process running on a node maintains a neighbor table. The neighbor table contains the neighboring nodes’ information for the node on which the ON process is running. The neighbor table is defined in overlay/neighbortable.h
The neighbor table has n entries where n is the number of the neighbors in the overlay. n can be retrieved by parsing topology.dat file. Each entry in the neighbor table contains a neighbor’s nodeID, the neighbor’s IP address and the TCP connection’s socket descriptor to the neighbor..
The neighbor’s nodeID and IP address are retrieved from topology.dat. The TCP connection’s socket descriptor to the neighbor is added when the TCP connection to that neighbor is established.
The ON process receives SNP packets from the overlay network and forwards these SNP packets to SNP layer. The ON process also receives SNP packets from SNP layer and forwards these SNP packets to the overlay network. The SNP packet format is defined in common/pkt.h and shown in Fig. 4.
If a packet type is equal to SNP, The data contained in the packet will be a segment(including segment header and data). If a packet’s type is ROUTE_UPDATE, the node’s distance vector is contained in data field of the packet. The node’s distance vector is stored in a pkt_routeupdate_t structure defined as below:
The format of a route update packet is shown in Fig. 5.
The Overlay Network are shown in Fig. 6
In what follows, we discuss the control flow of the overlay network. The SNP process calls overlay_sendpkt() to send a packet to the next hop according to the routing table. When the SNP process calls overlay_sendpkt(), a sendpkt_arg_t structure (see below) which contains the next hop’s nodeID and the packet itself is sent to the local ON process. The local ON process uses getpktToSend() to receive this sendpkt_arg_t structure. The local ON process then sends the packet out by calling sendpkt().
The ON process has one thread for each TCP connection to its neighboring nodes. In each thread, recvpkt() function is used to receive the packets from a neighboring node. After a packet is received by recvpkt(), the ON process forwards the packet to the local SNP process by calling forwardpktToSNP(). The local SNP process calls overlay_recvpkt() to receive the packets forwarded from the ON process.
The ON process and the SNP process are connected with a local TCP connection. The nodes in the overlay network are interconnected with TCP connections too. To send data over the TCP connections, we use delimiters as we did for segments. We use “!&” to indicate the starting of data transferring and use “!#” to indicate the end of data transferring. So when the data is sent over a TCP connection, “!&” is sent first, followed by the data and then “!#” is sent. When receiving the data at the other end of the TCP connection, a simple finite state machine can be used.
Here are the detailed descriptions of these APIs
The ON process provides two function calls for the SNP process: overlay_sendpkt() and overlay_recvpkt().
The ON process uses getpktToSend() to get a sendpkt_arg_t data structure which contains a packet and the next hop’s nodeID from the SNP process. The ON process uses forwardpktToSNP() to forward a packet to the SNP process.
The ON process uses sendpkt() to send a packet to a neighbor and uses recvpkt() to receive a packet from a neighbor.
The code for ON process is shown below
When a ON process starts, it creates a neighbor table dynamically and initialize the neighbor table using the information from topology/topology.dat. The ON process also initialize the connection to the SNP process to -1 as invalid. The ON process then registers the signal handler overlay_stop() for signal SIGINT so that when SIGINT signal is received, the overlay_stop() is called to terminate the ON process.
The TCP connections to all the neighbors in the overlay network are then established. The neighboring nodes information can be retrieved from topology.dat file. In our design, if there is a link between two nodes, the node with a smaller node ID will open a TCP port on CONNECTION_PORT and the node with a larger node ID will connect to it. To do this, the ON process starts a waitNbrs thread and then after a while calls a connectNbrs() function. The waitNbrs thread opens a TCP port on CONNECTION_PORT and waits for incoming connections from all neighbors that have a larger node ID than “my” nodeID. After all the incoming connections are established, the waitNbrs thread returns. After starting the waitNbrs thread, the main thread waits for OVERLAY_START_DELAY time to wait for neighboring nodes in the overlay network to start their ON processes. The main thread then calls connectNbrs() which connects to all the neighbors that have a smaller node ID than “my” nodeID. After the connectNbr() function returns, the main thread waits for waitNbrs thread to return. After the waitNbrs thread returns, all the TCP connections with neighbors are established.
For each TCP connection with neighbors, the ON process starts a listen_to_neighbor thread. Each listen_to_neighbor thread keeps receiving packets from a neighbor using recvpkt() and forwarding the packets to the SNP process using forwardpktToSNP().
Once all the listen_to_neighbor threads are started, the ON process calls waitNetwork() function. This function opens a TCP port on OVERLAY_PORT and waits for an incoming TCP connection from the local SNP process. After the connection is established, waitNetwork() function keeps receiving sendpkt_arg_t structures from the SNP process. Each sendpkt_arg_t contains a packet and the next hop’s nodeID. After a sendpkt_arg_ strcture is received, waitNetwork() sends the packet to the next hop in the overlay network using sendpkt(). When a SNP process is disconnected, waitNetwork() closes the connection and waits for the next incoming connection from local SNP process.
The ON process terminates when it receives a SIGINT signal. When a SIGINT signal is received, the signal handler function called overlay_stop() to stop the overlay by closing all the TCP connections, freeing all the dynamically allocated memory and terminating the ON process.
You need to test your overlay since it will be used in lab7. For this lab, the SNP process is used to test the overlay functionality. The SNP process connects to the local ON process and requests the local process to broadcast route update packets periodically. The SNP process should be able to receive the route update packets from its neighbors. By sending and receiving route update packets, we can verify if the overlay is working properly. You will implement the SNP routing and forwarding in the next lab. You will also integrate the SRT layer and SNP layer and use the application layer (app_simple_client/app_simple_server and app_stress_client/app_stress_server) to test your code in the next lab.
The code for SNP process is given shown below. You need to implement the functions used by SNP process in network.c.
The SNP process maintains a connection to the ON process. The SNP process should be started after the local ON process is started (after waitNetwork() is called in ON process).
When the SNP process starts, the SNP process first initializes the global variable by setting connection to the local ON process to -1 as invalid. The SNP process then registers the signal handler network_stop() to signal SIGINT so that when SIGINT signal is received, the network_stop() is called to kill the SNP process.
Then SNP process calls a function called connecToOverlay() to connect to the ON process on port OVERLAY_PORT. After the TCP connection to the ON process is established, the SNP process starts a pkthandler thread. The pkthandler thread handles incoming packets from the ON process. The pkthandler thread receives packets from ON process by calling overlay_recvpkt(). Currently, the pkthandler thread only shows that a packet is received without handling the packets.
Following this, the SNP process starts a routeupdate_daemon thread. The routeupdate_daemon thread is the route update broadcasting thread which broadcasts route update packets every ROUTEUPDATE_INTERVAL time. Currently, an empty route update packets is broadcast. The broadcasting is done by setting the dest_nodeID in SNP packet header as BROADCAST_NODEID and send the route update packet to the broadcasting address - BROADCAST_NODEID using overlay_sendpkt().
The SNP process then goes into a while loop and sleeps forever.
The SNP process terminates when it receives a SIGINT signal. When a SIGINT signal is received, the signal handler function network_stop() stops the overlay by closing all the TCP connections, freeing all the dynamically allocated memory and terminating the SNP process.