OK, we have completed the Simple Reliable Transport. We have implemented the transport connection establishment, data transfer including go-back-n and checksum fucntions, and finally, connection teardown. Well done! Now we will move down the stack.

In Lab6 we will implement the overlay network (SON) layer (of the DartNet stack. We will also use a simple network driver (that will drive the overlay) to test our overlay layer implementation. At the end of this lab you will have good sense of how DartNet’s overlay layer works. In Lab7 we will implement the Simple Network Protocol (SNP) and put the complete stack together: SRT, SNP, and SON

The overlay network layer is implemented as a process. Each node in the overlay network will have an SON process running. The SON process maintains TCP connections to all the neighboring nodes in the overlay network. The SON process also maintains a local TCP connection to the SNP layer. The SNP layer is also implemented as a process. Each node in the overlay network will have a SNP process running. See the design notes for more details.

The SON process contains multiple threads. For each TCP connection to a neighbor, there is a listen_to_neighbor thread. The listen_to_neighbor thread keeps receiving packets from a neighbor and forwarding the received packets to the local SNP process. For the TCP connection to the local SNP process, another thread (the main thread) keeps receiving sendpkt_arg_t structures which contain packets and the next hops’ nodeIDs and sending these packets to the next hops in the overlay network.

The overlay network’s topology information is contained in topology.dat file. To use the topology information in SON process, you need to write code to parse the topology.dat file. Some APIs for parsing the topology file is provided in topology.h. You can implement those APIs or you can define your own APIs. You should implement these topology parsing APIs in topology.c. A SON process also maintains a neighbor table to record all the TCP connections to its neighboring nodes. To use the neighbor table, you need to implement the neighbor table APIs defined in neighbortable.h. The SON process sends and receives data in packets. The APIs to send and receive packets are defined in pkt.h. You also need to implement these APIs.

After you have implemented all these APIs you can start implementing the overlay layer in overlay.c. Some helpful functions for implement overlay layer are defined in overlay.h. You can implement them and use them in your SON process implementation.

After you have implemented your overlay layer, you need to implement a simple SNP layer. The SNP process will connect to the local SON process and test the overlay by periodically requesting the local SON process to send an empty route update packet to to all its neighbors. The SNP process should be able to receive these route update packets sent from its neighbors.

Before you read another line of this programming assignment please read or re-read the Lecture notes on Overlay Network Design . The description in this assignment is fairly brief and the context for understanding it is found in the design notes.

While quite a lot of information is given on APIs, data structures, connection management, you will need to think about how to implement the implement these required APIs by overlay network layer.

The following sequence of Linux commands should be used to submit your work by the deadline:

Change to your labs directory cd ~/cs60/labs This directory contains your lab6 directory where your solutions are found.

Please make sure that the lab6 directory contains a simple text file, named README, describing anything “unusual” about how your solutions should be located, executed, and considered; and a Makefile to build the source.

Important source and header files - read them

OK, now you have read the overlay network design notes, look at these important files - browse them for now, we will get back to them.

Note, all the files listed below plus other files (e.g., Makefile, README, etc.) needed for this lab can be found in this tarball file: lab6handout.tar.gz . Save this and work from this tarball for your assignment.

Topology directory: topology.dat contains the topology information of the overlay network. We will use four nodes to form the overlay network in this lab. You should replace the host1, host2, host3, host4 with real hostnames in topology.dat.

Topology directory: topology.h contains the APIs to parse the topology.dat file. It is up to you to determine if want to implement these APIs or not. You can pick the ones you feel useful to implement. You can also define your own APIs to impement. You need to implement your APIs in the topology.c file.

Currently there are 3 port numbers defined in constants.h:
CONNECTION_PORT
OVERLAY_PORT NETWORK_PORT

Please assign a random port number to each of them. You can use random port numbers from 2000 through 5000.
Do not use the Well Known Ports which are from 0 through 1023.

If you do not do this and run the code with the default settings for ports in constants.h,
you will run into situations of the port being already allocated by a classmate.
So set your own values to minimize the likelihood of this happening.

Common directory: pkt.h defines the packet format for the packet APIs you need to implement. You need to write your pkt.c file to implement these APIs.

Overlay directory: neighbortable.h defines the neighbor table data structure and APIs you need to implement. You need to write your neighbortable.c to implement these APIs.

Overlay directory: overlay.h defines the functions used by overlay. You need to implement these functions in overlay.c

Network directory: network.h defines the functions used by network layer. You only need to implement a simple network layer to drive and test the overlay functionality (note, this is not the full functional Simple Network Protocol that we will implement in the next lab but a simple set of drivers to run the overlay). Your test code should be implemented in network.c

The Simple Network Protocol (SNP) Packet APIs

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 SON process. The local SON process uses getpktToSend() to receive this sendpkt_arg_t structure. The local SON process then sends the packet out by calling sendpkt().

The SON 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 SON 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 SON process.

The SON 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 SON 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 SON process to send a packet out to the overlay network.
//
// The SON 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 SON process.
// The SON process receives this data structure by calling getpktToSend().
// Then the SON 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 SON
// process to send a packet out to the overlay network. The
// SON 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 SON process.
// The parameter overlay_conn is the TCP connection’s socket descriptior
// between the SNP process and the SON process.
// When sending the sendpkt_arg_t data structure over the TCP connection between the SNP
// process and the SON 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 SON process. The parameter overlay_conn is the TCP connection’s socket
// descriptior between the SNP process and the SON process. The packet is sent over
// the TCP connection between the SNP process and the SON 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 SON 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 SON process uses forwardpktToSNP() to forward a packet to the SNP process.

// This function is called by the SON 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 SON process. The sendpkt_arg_t structure is sent over the TCP
// connection between the SNP process and the SON 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 SON process receives a packet from
// a neighbor in the overlay network. The SON 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 SON process. The packet is sent over the TCP connection between the SNP process
// and SON 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 SON 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 SON 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 SON 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 SON 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 SON 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);

The Neighbor Table APIs

Each Node has a Overlay Network (SON) process running. Each SON process maintains the neighbor table for the node on which the process is running. The neighbor table APIs are defined in neighbortable.h.

//This function first creates a neighbor table dynamically.
//It then parses the topology/topology.dat file and fills in the
//nodeID and nodeIP fields for all entries, initialize the conn field as -1
//return the created neighbor

tablenbr_entry_t* nt_create();

// This function destroys a neighbortable. It closes all the connections
// and frees all the dynamically allocated memory

void nt_destroy(nbr_entry_t* nt);

//This function is used to assign a TCP connection to a neighbor table entry
//for a neighboring node.
//if the TCP connection is successfully assigned, return 1,
//otherwise return -1

int nt_addconn(nbr_entry_t* nt, int nodeID, int conn);

The Overlay Network Functions

The overlay process uses the following functions. They are defined in overlay.h and should be implemented in overlay.c.

// This thread opens a TCP port on CSONNECTISON_PORT and waits for the incoming
//connections from all the neighbors that have a larger node ID than my nodeID,
// After all the incoming connections are established, this thread terminates.

void* waitNbrs();

// This function connects to all the neighbors that have a smaller node ID than my nodeID
// After all the outgoing connections are established, return 1, otherwise return -1.

int connectNbrs();

//This function opens a TCP port on OVERLAY_PORT, and waits for the incoming
//connection from local SNP process. After the local SNP
//process is connected, this function keeps getting sendpkt_arg_t structures
//from SNP process, and sends the packets to the next hop
//in the overlay network. If the next hop’s nodeID is BROADCAST_NODEID, the packet
//should be sent to all the neighboring noddes.

void waitNetwork();

//Each listen_to_neighbor thread keeps receiving packets from a neighbor.
//It handles the received packets by forwarding the packets to the SNP process.
//all listen_to_neighbor threads are started after all the TCP connections
//to the neighbors are established.

void* listen_to_neighbor(void* arg);

//This function stops the overlay
//it closes all the connections and frees all the dynamically allocated memory
//It is called when receiving a signal SIGINT.

void overlay_stop();

The Network Layer Functions

The network layer process uses the following functions. They are defined in network.h and should be implemented in network.c.

/This function is used to for the SNP process to connect to
//the local SON process on port OVERLAY_PORT.
//connection descriptor is returned if success, otherwise return -1.

int connectToOverlay() {
}

//This thread sends out route update packets every ROUTEUPDATE_INTERVAL time
//In this lab this thread only broadcasts empty route update packets to all
//the neighbors, broadcasting is done by set the dest_nodeID in packet header
//as BROADCAST_NODEID

void* routeupdate_daemon(void* arg) {
}

//This thread handles incoming packets from the SON process.
//It receives packets from the SON process by calling overlay_recvpkt().
//In this lab, after receiving a packet, this thread just outputs the packet
//received information without handling the packet.
//You can use this code directly.

void* pkthandler(void* arg) {
  pkt_t pkt;

  while(overlay_recvpkt(&pkt,overlay_conn)>0) {
    printf("Routing: received a packet from neighbor %d\n",pkt.header.src_nodeID);
  }
  close(overlay_conn);
  overlay_conn = -1;
  pthread_exit(NULL);
}

CS 60 Computer Networks

Lab6

DartNet: Simple Overlay Network (SON)

Important source and header files - read them

The Simple Network Protocol (SNP) Packet APIs

The Neighbor Table APIs

The Overlay Network Functions

The Network Layer Functions