Figure 1: An DartNet Example
We have implemented SRT directly on the DartNet overlay network (ON) layer. Now we need to add routing and packet forwarding to DartNet. The lecture covers the design of the DartNet network layer. We will implement the Simple Network Protocol (SNP) in Lab7 to provide forwarding and routing support akin to the IP protocol and routing algorithms that run on Internet routers.
Goals
We plan to learn the following from this lecture:
OK, let’s get going.
____________________________________________________________________________
First, let’s look at an example of the complete DartNet implementation shown in Fig. 1. In this example, DartNet is formed by 4 nodes: bear, spruce, gile, and green. DartNet is an overlay network. The topology of the overlay is defined in topology.dat file. In DartNet, there is a TCP connection between each pair of neighboring nodes. On each node, there is an overlay network (ON) layer, a simple network protocol (SNP) layer, a simple reliable transport (SRT) layer and an application layer.
The ON layer is implemented as a process called the ON process. The ON process contains n+1 threads where n is the number of the neighboring nodes. With respect to these ON threads, one is the main thread and the other n threads are listen_to_neighbor threads. We have discussed the design of the ON process in detail in the ON design notes - and, indeed, we have implemented it. The SNP layer is implemented as a process called SNP process. This process contains 3 threads: a main thread, a pkthandler thread and a routeupdate_daemon thread. We will discuss the design of these therads in detail in this lecture. The SRT layer and the application layer are implemented in a process. We call this process the SRT process. The SRT process contains two threads: a main thread and a seghandler thread. We have discussed the SRT process implementation in detail in SRT design notes - and, indeed, we have implemented it.
On a DartNet node, the ON process and the SNP process are connected by a local TCP connection. The SNP process and the SRT process are also connected by a local TCP connection. The data transferred between these processes are sent through the local TCP connections. The complete DartNet APIs between DartNet layers are shown in Fig. 2
Let’s look at how a segment can be sent from the source node to the destination node using these DartNet APIs.
At the source node, the SRT process calls snp_sendseg() to send a segment to a destination node. When the SRT process calls snp_sendseg(), a sendseg_arg_t structure which contains a segment and the segment’s destination nodeID is sent to the local SNP process. The local SNP process uses getsegToSend() to receive this sendseg_arg_t structure. The local SNP process then encapsulates the segment into a packet and sends the packet to the local ON process using overlay_sendpkt(). The next hop’s nodeID is retrieved from the routing table maintained by the SNP routing protocol. When the SNP process calls overlay_sendpkt(), a sendpkt_arg_t structure which contains a packet and the “next hop nodeID” of the packet 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 to the next hop by calling sendpkt().
At an intermediate node, the ON process receives the packet by calling recvpkt(). The ON process forwards the packet to the local SNP process at that node by calling forwardpktToSNP(). The local SNP process calls overlay_recvpkt() to receive the packet forwarded from the ON process. Then the SNP process gets the next hop’s node ID from the routing table and calls overlay_sendpkt() to send a sendpkt_arg_t structure to the local ON process. The local ON process uses getpktToSend() to receive this sendpkt_arg_t structure and sends the packet to the “next hop” node by calling sendpkt().
At the destination node, the ON process calls recvpkt() function to receive the packet from a neighboring node. After a packet is received, the ON process forwards the packet to the local SNP process by calling forwardpktToSNP(). The local SNP process calls overlay_recvpkt() to receive the packet forwarded from the ON process. After a packet is received by the SNP process, the SNP process extracts a segment from the packet’s data field and forwards a sendseg_arg_t structure to the local SRT process. This sendseg_arg_t contains the source nodeID of the segment and the segment itself. The local SRT process calls snp_recvseg() to receive this sendseg_arg_t structure.
OK. Now let’s focus on the SNP process. As we mentioned before, the SNP process is responsible for routing and forwarding packets. The SNP layer maintains a routing table which is constructed by the SNP routing protocol (the SNP routing protocol = the distributed implementation of the Distance Vector algorithm discussed in these notes and in the course textbook in Section 4.5.2) - please read both. The SNP process also provides SNP APIs to the SRT process as we mentioned above. In this lecture, we will discuss the design of SNP process - its APIs, forwarding mechanism, distance vector routing algorithm (and the SNP routing protocol that implements the distance vector algorithm). Much of the information presented in this lecture is important in completing Lab7 on the implementation of the SNP.
The end results of completing Lab7 is the implementation of the complete DartNet stack - this is a very cool achievment.
The SNP process provides two functions to the SRT process - snp_sendseg() and snp_recvseg(). In lab4 and lab5, we have implemented these two SNP APIs. However, at that time, these SNP APIs are implemented using a direct TCP connection between two nodes. Here, we will re-implement these APIs using the ON layer we implemented in lab6.
We have seen the flow control of SNP APIs in Fig. 2. Let’s go through that again. The SRT process calls snp_sendseg() to send a segment to a destination node. When the SRT process calls snp_sendseg(), a sendseg_arg_t structure (see below) which contains the segment’s destination’s nodeID and the segment itself is sent to the local SNP process. The local SNP process uses getsegToSend() to receive this sendseg_arg_t structure. The local SNP process then encapsulates each segment into one packet and sends the packet to the next hop using overlay_sendpkt(). The next hop’s nodeID is retrieved from the routing table maintained by the SNP routing protocol.
The SNP process receives packets from the local ON process by calling overlay_recvpkt() function. After a packet is received by the SNP process, the SNP process extracts a segment from the packet’s data field (each packet contains a segment) and forwards a sendseg_arg_t structure to the local SRT process. This sendseg_arg_t structure contains the source node ID of the segment and the segment itself. The local SRT process calls snp_recvseg() to receive this sendseg_arg_t structure.
The sendseg_arg_t is defined in seg.h.
The SRT process and the SNP process are connected with a local TCP connection. To send data over the TCP connections, we use delimiters as we did for ON APIs. 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.
To use the new SNP APIs, we need to make some changes to our SRT implementation. Recall that in SRT, both client and server TCBs have a client node ID field and a server node ID field. We did not use them in lab4 and lab5. Now we will modify the SRT implementation to uses these fields.
For a SRT client, in srt_client_sock(), when a TCB is created, the client_nodeID field is set to its own node ID. When connecting to a server, the client passes a new parameter - server node ID to srt_client_connect(). In srt_client_connect(), the TCB’s svr_nodeID field is set as the given server node ID.
For a SRT server, in srt_server_sock(), when a TCB is created, the svr_nodeID field is set to its own node ID. In seghandler(), when the TCB is in CLOSED state, and the server receives a SYN segment, the client_nodeID field in TCB is set to the source node ID of this SYN segment and the TCB’s state transitions to CONNECTED.
When the SRT process calls SNP APIs - snp_sendseg() and snp_recvseg(), the client_nodeID or the svr_nodeID is passed to the API. For example, when a SRT server calls snp_sendseg(), the client node ID is passed to snp_sendseg() function as the destination nodeID of the segment to be sent.
Another change we need to make is to replace the old overlay_start() and overlay_stop() functions in application source files (app_simple_client, app_simple_server, app_stress_client, app_stress_server)with the new functions to connect to the local SNP process and disconnect from the local SNP process. Because now, The SRT process is working on the SNP process instead of the overlay directly.
SNP routing protocol is a Distance Vector (DV) routing protocol. SNP routing protocol uses link cost as the routing metric. Link cost is a link quality metric. A link with high link cost will have higher packet loss rate, higher packet error rate, and longer delays. When multiple paths between two nodes exist, a path with a smaller overall link cost should be chosen.
We will discuss SNP routing protocol in detail below. Let’s first look at the data structures used by the SNP routing protocol. Then we will discuss the SNP routing algorithm.
SNP routing protocol uses 3 tables: a neighbor cost table, a distance vector table and a routing table. We will discuss them one by one. Note: each node in the overlay has a SNP process running on it and each SNP process maintains a neighbor cost table, a distance vector table and a routing table for the node it is running on.
A node’s neighbor cost table contains the direct link costs to all its neighbors. A neighbor cost table has n entries where n is the number of neighbors of the node. The neighbor cost table entry is defined in network/nbrcosttable.h.
Each neighbor cost table entry contains a neighbor’s node ID and the direct link cost to that neighbor. A neighbor table is dynamically created when the SNP process starts. The neighbor cost table is initialized by parsing the topology information contained in topology.dat. After a neighbor cost table is created, its contents will not change over time.
SNP routing protocol is a DV routing protocol. A distance vector contains a source node and the estimated link costs from the source node to all the nodes in the network. The distance vector structure is defined in network/dvtable.h
Each dv_t entry is a distance vector which contains a source nodeID and an array of N dv_entry_t structures where N is the total number of nodes in the overlay. Each dv_entry_t contains a destination nodeID and the estimated link cost from the source node to the destination node.
Each node’s SNP process maintains a distance vector table. The distance vector table contains n+1 distance vectors (each distance vector is contained in a dv_t structure) where n is the number the node’s neighbors. In these n+1 distance vectors, n distance vectors are for neighboring nodes (one for each) and the other distance vector is for the node itself.
The distance vector table is dynamically created when SNP process starts.
When the distance vector table is created, the distance vector for the node itself is initialized using the direct link cost information from topology.dat file. For a destination node, if the destination node is the node itself, the estimated link cost is 0. If the destination node is a neighboring node, the estimated link cost is the direct link cost. Otherwise, the estimated link cost is INFINITE_COST.
The other n distance vectors for the neighboring nodes in the distance vector table are initialized with INFINITE_COST.
Each node’s SNP process maintains a routing table. The routing table’s structure is shown in Fig. 3. The routing table is a hash table which has MAX_ROUTINGTABLE_SLOTS slots. Each slot contains a linked list of routingtable_entry_t structures.
The routingtable_entry_t structure and the routing table itself is defined in network/routingtable.h.
Each routing_entry_t structure contains a destination node ID and the next hop’s nodeID for this destination node. The routing table is a hash table. It uses a hash function makehash() which takes the hash key - destination node ID as input, and returns the hash value - slot number for this destination node ID. Each slot in routing table contains a linked list of routing entries. This is because conflicting hash keys (different hash keys (destination node IDs) may have same hash values (slot entry numbers)).
To add an routing entry to the routing table, you should first use the hash function makehash() to get the slot number in which this routing entry should be stored. You should then append the routing entry to the linked list in that slot. To find a routing entry for a destination node, you should first use the hash function makehash() to get the slot number and then go through the linked list in that slot to search the routing entry.
The routing table is dynamically created when the SNP process starts. The routing table is initialized by adding routing entries for all the neighboring nodes. For each neighboring node as the destination node, the next hop node is set as the neighboring node itself.
The SNP routing protocol uses the distance vector routing algorithm. Please read chapter 4.5.2: The Distance-Vector (DV) Routing Algorithm in your textbook (p. 375 - p. 382), which contains the DV algorithm descriptions in detail, carefully.
SNP routing protocol uses 3 tables: a neighbor cost table, a distance vector table and a routing table. Each node in the overlay has a SNP process running on it and each SNP process maintains a neighbor cost table, a distance vector table and a routing table for the node it is running on.
When the SNP process starts, all three tables are created and initialized. The neighbor cost table is initialized using the direct link cost retrieved from topology.dat. The distance vector table has n+1 distance vectors where n is the number of neighbors. In the distance vector table, one distance vector is for the node itself and n distance vectors are for n neighboring nodes. The distance vector for the node itself is initialized using the direct link cost information from topology.dat file. The distance vectors for the neighboring nodes are initialized by setting all the estimated link costs to INFINITE_COST. The routing table is initialized by adding routing entries for all the neighboring nodes. For each neighboring node as the destination node, the next hop node is set as the neighboring node itself.
When the SNP process starts, it also starts a routeupdate_daemon thread. The routeupdate_daemon thread broadcasts a route update packet every ROUTEUPDATE_INTERVAL. A route update packet contains the distance vector of the source node. This distance vector is retrieved from the source node’s distance vector table.
A received route update packets will not be forwarded by the receiver, so a route update will only be received by the source node’s direct neighbors. After receiving a route update packet, the receiver updates the receiver’s distance vector table and the receiver’s routing table.
The receiver’s distance vector table and routing table are updated in 2 steps. Let’s denote the source node of the route update packet as S and the receiver as X. Note that we are update X’s distance vector table and routing table here. In step 1, X updates the distance vector for S using the distance vector contained in the route update packet. In step 2, the distance vector for X is recalculated and the X’s routing table is updated. To recalculate the distance vector for X, for each destination node Y, the new estimated link cost from node X to node Y is DX(Y ) = minv{cost(X,V ) + DV (Y )} where V is any neighboring nodes of X, cost(X,V) is the direct link cost from X to neighbor V which is retrieved from the neighbor cost table. DV (Y ) is the estimated link cost from V to Y in the distance vector table. X’s routing table is also updated at step 2. For each node Y, if the estimated link cost from X to Y is not INFINITE_COST and Y!=X, the next hop’s node ID for destination node Y is set as V with which the minimum estimated link cost is found.
Let’s take the DartNet topology in Fig. 4 as an example. The neighbor cost tables for nodes bear, spruce, gile and green are shown in Fig. 5. They are initialized with the direct link costs and will not change over time.
After initialization, the nodes’ distance vector tables and routing tables are shown on the left side of Fig. 6 and Fig. 7. The distance vector table contains the distance vectors for all the neighbors and the node itself. The distance vector for the node itself is initialized using the node’s direct link costs to its neighbors. The routing table is initialized by adding the direct neighbors. For example, node bear has distance vectors for bear, spruce, gile and green, because spruce, gile and green are all bear’s neighbors. Bear’s distance vector is initialized using its direct link costs to spruce, gile and green (bear also has direct link cost 0 to itself). Bear’s routing table is initialized by adding all three neighbors (for each neighbor, the next hop node is the neighbor itself).
After all the nodes received all the first route update packets from their neighbors, the distance vector tables and routing tables are updated and shown on the right side of Fig. 6 and Fig. 7.
Let’s take a close look at node bear. Bear receives route update packets from all the other three nodes because all the other three nodes are bear’s neighbors. The distance vectors for node gile, spruce and green in bear’s distance vector table are updated using the distance vectors contains in the route update packets from these three nodes. Then the distance vector for bear itself in bear’s distance vector table is updated by DX(Y ) = minv{cost(X,V ) + DV (Y )}. For example, the new estimated link cost from bear to green is computed as below:
Dbear(green) = min{cost(bear,spruce)+Dspruce(green),cost(bear,gile)+Dgile(green),cost(bear,green)+Dgreen(green)}
= min{5 + 3,4 + 2,7 + 0} = 6
Bear’s routing table is updated also. For example, because with gile, the minimum value for Dbear(green) is found, for destination node green, the next hop is set to gile in bear’s routing table.
Because the topology is defined in topology.dat and does not change over time. The routing tables shown on the right side in Fig. 7 will not be changed any more. After all the nodes received the second route update packets from their neighbors, the distance vector tables are updated as shown in Fig. 8. After that, the distance vector tables will not change any more.
The packet forwarding is done in pkthandler thread in the SNP process. The pkthandler thread handles incoming packets from the ON process. The pkthandler thread receives packets from the ON process by calling overlay_recvpkt(). If the received packet is a SNP packet and the destination node is this node, the pkthandler thread forwards the packet to the SRT process. If the packet is a SNP packet and the destination node is not this node, the pkthandler thread forwards the packet to the next hop according to the routing table. If this packet is an route update packet, the pkthandler thread updates the distance vector table and the routing table using the SNP routing algorithm we described above.
The SNP runs as a process. Each node in the overlay has a SNP process running on it. The SNP process’s code is shown as below:
When the SNP process starts, it first creates a neighbor cost table, a distance vector table and a routing table and initializes these tables. The SNP process also creates and initializes two mutex: one for distance vector table and the other for routing table. The SNP process maintains a TCP descriptor overlay_conn for the connection with the local ON process and a TCP descriptor transport_conn for the connection with the local SRT process. When the SNP process starts, the SNP process initializes overlay_conn and transport_conn 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.
After that, SNP process calls function connectToOverlay() to connect to the local 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 the ON process by calling overlay_recvpkt(). If the received packet is a SNP packet and the destination node is this node, the pkthandler thread forwards the packet to the SRT process. If the packet is a SNP packet and the destination node is not this node, the pkthandler thread forwards the packet to the next hop according to the routing table. If this packet is an route update packet, the pkthandler thread updates the distance vector table and the routing table using the SNP routing algorithm.
Following this, the SNP process starts a routeupdate_daemon thread. The routeupdate_daemon thread is the route update broadcasting thread which broadcasts a route update packet every ROUTEUPDATE_INTERVAL time.
The SNP process then waits for a while for the routing paths in the overlay network to be established by the SNP routing protocol. The SNP process then calls waitTransport() function to wait for the TCP connection from the local SRT process. waitTransport() function opens a port on NETWORK_PORT and waits for the TCP connection from the local SRT process. After the local SRT process is connected, waitTransport() function keeps receiving sendseg_arg_t structures which contains the segments and their destination nodeIDs from the SRT process. The received segments are then encapsulated into packets (one segment in one packet), and sent to the next hop using overlay_sendpkt. The next hop’s node ID is retrieved from routing table. When a local SRT process is disconnected, this function waits for the next SRT process to connect.
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.
