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.

Overlay Topology and Node ID

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 “202.120.95.36” as a node ID of 36.

Construction of an Overlay

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.

Neighbor Table

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

//neighbortable entry definition
//a neighbor table contains n entries where n is the number of neighbors

typedef struct neighborentry {
  int nodeID;       //neighbor’s node ID
  in_addr_t nodeIP; //neighbor’s IP address
  int conn;         //TCP connection’s socket descriptor to the neighbor
} nbr_entry_t;

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.

Simple Network Protocol (SNP) Packet Format

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.

//packet type definition, used for type field in the SNP header
#define ROUTE_UPDATE 1
#define SNP 2

//SNP packet format definition
typedef struct snpheader {
  int src_nodeID;               //source node ID
  int dest_nodeID;              //destination node ID
  unsigned short int length;    //length of the data in the packet
  unsigned short int type;      //type of the packet
} snp_hdr_t;

typedef struct packet {
  snp_hdr_t header;
  char data[MAX_PKT_LEN];
} snp_pkt_t;

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:

//A route update entry

typedef struct routeupdate_entry {
  unsigned int nodeID;  // destination nodeID
  unsigned int cost; // link cost between source (src_nodeID in header) and destination nodes
} routeupdate_entry_t;

//route update packet format

typedef struct pktrt{
  unsigned int entryNum;  // number of entries contained and in this route update packet
  routeupdate_entry_t entry[MAX_NODE_NUM];
} pkt_routeupdate_t;

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.

The ON process provides two function calls for the SNP process: overlay_sendpkt() and overlay_recvpkt().

// sendpkt_arg_t data structure is used in the overlay_sendpkt() function.
// overlay_sendpkt() is called by the SNP process to request
// the ON process to send a packet out to the overlay network.
//
// The ON process and SNP process are connected with a
// local TCP connection, in overlay_sendpkt(), the SNP process
// sends this data structure over this TCP connection to the ON process.
// The ON process receives this data structure by calling getpktToSend().
// Then the ON process sends the packet out to the next hop by calling sendpkt().

typedef struct sendpktargument {
  int nextNodeID;    //node ID of the next hop
  pkt_t pkt;         //the packet to be sent
} sendpkt_arg_t;

// overlay_sendpkt() is called by the SNP process to request the ON
// process to send a packet out to the overlay network. The
// ON process and SNP process are connected with a local TCP connection.
// In overlay_sendpkt(), the packet and its next hop’s nodeID are encapsulated
// in a sendpkt_arg_t data structure and sent over this TCP connection to the ON process.
// The parameter overlay_conn is the TCP connection’s socket descriptior
// between the SNP process and the ON process.
// When sending the sendpkt_arg_t data structure over the TCP connection between the SNP
// process and the ON process, use ’!&’  and ’!#’ as delimiters.
// Send !& sendpkt_arg_t structure !# over the TCP connection.
// Return 1 if sendpkt_arg_t data structure is sent successfully, otherwise return -1.

int overlay_sendpkt(int nextNodeID, pkt_t* pkt, int overlay_conn)

// overlay_recvpkt() function is called by the SNP process to receive a packet
// from the ON process. The parameter overlay_conn is the TCP connection’s socket
// descriptior between the SNP process and the ON process. The packet is sent over
// the TCP connection between the SNP process and the ON process, and delimiters
// !& and !# are used.
// To receive the packet, this function uses a simple finite state machine(FSM)
// PKTSTART1 -- starting point
// PKTSTART2 -- ’!’ received, expecting ’&’ to receive data
// PKTRECV -- ’&’ received, start receiving data
// PKTSTOP1 -- ’!’ received, expecting ’#’ to finish receiving data
// Return 1 if a packet is received successfully, otherwise return -1.

int overlay_recvpkt(pkt_t* pkt, int overlay_conn)

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.

// This function is called by the ON process to receive a sendpkt_arg_t data structure.
// A packet and the next hop’s nodeID is encapsulated in the sendpkt_arg_t structure.
// The parameter network_conn is the TCP connection’s socket descriptior between the
// SNP process and the ON process. The sendpkt_arg_t structure is sent over the TCP
// connection between the SNP process and the ON process, and delimiters !& and !# are used.
// To receive the packet, this function uses a simple finite state machine(FSM)
// PKTSTART1 -- starting point
// PKTSTART2 -- ’!’ received, expecting ’&’ to receive data
// PKTRECV -- ’&’ received, start receiving data
// PKTSTOP1 -- ’!’ received, expecting ’#’ to finish receiving data
// Return 1 if a sendpkt_arg_t structure is received successfully, otherwise return -1.

int getpktToSend(pkt_t* pkt, int* nextNode,int network_conn);

// forwardpktToSNP() function is called after the ON process receives a packet from
// a neighbor in the overlay network. The ON process calls this function
// to forward the packet to SNP process.
// The parameter network_conn is the TCP connection’s socket descriptior between the SNP
// process and ON process. The packet is sent over the TCP connection between the SNP process
// and ON process, and delimiters !& and !# are used.
// Send !& packet data !# over the TCP connection.
// Return 1 if the packet is sent successfully, otherwise return -1.

int forwardpktToSNP(pkt_t* pkt, int network_conn);

The ON process uses sendpkt() to send a packet to a neighbor and uses recvpkt() to receive a packet from a neighbor.

// sendpkt() function is called by the ON process to send a packet
// received from the SNP process to the next hop.
// Parameter conn is the TCP connection’s socket descritpor to the next hop node.
// The packet is sent over the TCP connection between the ON process and a neighboring node,
// and delimiters !& and !# are used.
// Send !& packet data !# over the TCP connection
// Return 1 if the packet is sent successfully, otherwise return -1.

int sendpkt(pkt_t* pkt, int conn);

// recvpkt() function is called by the ON process to receive
// a packet from a neighbor in the overlay network.
// Parameter conn is the TCP connection’s socket descritpor to a neighbor.
// The packet is sent over the TCP connection between the ON process and the neighbor,
// and delimiters !& and !# are used.
// To receive the packet, this function uses a simple finite state machine(FSM)
// PKTSTART1 -- starting point
// PKTSTART2 -- ’!’ received, expecting ’&’ to receive data
// PKTRECV -- ’&’ received, start receiving data
// PKTSTOP1 -- ’!’ received, expecting ’#’ to finish receiving data
// Return 1 if the packet is received successfully, otherwise return -1.

int recvpkt(pkt_t* pkt, int conn);

Overlay Process Implementation

  //start overlay initialization
  printf("Overlay: Node %d initializing...\n", topology_getMyNodeID());

  //create a neighbor table
  nt = nt_create();

  //initialize network_conn to -1, means no network layer process is connected yet
  network_conn = -1;

  //register a signal handler which is used to terminate the process
  signal(SIGINT, overlay_stop);

  //print out all the neighbors
  int nbrNum = topology_getNbrNum();
  int i;
  for(i=0;i<nbrNum;i++) {
    printf("Overlay: neighbor %d:%d\n",i+1,nt[i].nodeID);
  }

  //start the waitNbrs thread to wait for incoming connections
  //from neighbors with larger node IDs

  pthread_t waitNbrs_thread;
  pthread_create(&waitNbrs_thread,NULL,waitNbrs,(void*)0);

  //wait for neighboring nodes to start the overlay process

  sleep(OVERLAY_START_DELAY);

  //connect to neighbors with smaller node IDs

  connectNbrs();

  //wait for waitNbrs thread to return

  pthread_join(waitNbrs_thread,NULL);

  //at this point, all connections to the neighbors are created

  //create threads listening to all the neighbors

  for(i=0;i<nbrNum;i++) {
    int* idx = (int*)malloc(sizeof(int));
    *idx = i;
    pthread_t nbr_listen_thread;
    pthread_create(&nbr_listen_thread,NULL,listen_to_neighbor,(void*)idx);
  }

  printf("Overlay: node initialized...\n");
  printf("Overlay: waiting for connection from SNP process...\n");

  //waiting for connection from  SNP process

  waitNetwork();

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.

Testing the Overlay

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.

  printf("network layer is starting, pls wait...\n");

  //initialize global variables

  overlay_conn = -1;

  //register a signal handler which will kill the process

  signal(SIGINT, network_stop);

  //connect to overlay

  overlay_conn = connectToOverlay();
  if(overlay_conn<0) {
    printf("can’t connect to ON process\n");
    exit(1);
  }

  //start a thread that handles incoming packets from overlay

  pthread_t pkt_handler_thread;
  pthread_create(&pkt_handler_thread,NULL,pkthandler,(void*)0);

  //start a route update thread

  pthread_t routeupdate_thread;
  pthread_create(&routeupdate_thread,NULL,routeupdate_daemon,(void*)0);

  printf("network layer is started...\n");

  //sleep forever
  while(1) {
    sleep(60);
  }

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 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.

CS 60 Computer Networks

Lecture 17

DartNet: Simple Overlay Network (SON) Design