We have completed the Simple Reliable Transport (SRT) and the Overlay Network (ON) implementation. Now we will move on the the network layer in DartNet and design and implement its Simple Network Protocol (SNP). The SNP layer connects the SRT layer and the ON layer in the stack. After this lab, you will have the completed the implementation of the DartNet stack. To test your DartNet stack you will run the stress test application between nodes as in Lab5 but this time it will excerise all the layers you have coded.

This culminating lab puts it all together: your reliable transport sets up connections and gurantees delivery of data segments in the face of packet loss and bit courruption, your network protocols routes and forwards network packets (datagrams) between nodes in your overlay.

This is a challenging lab because it pulls are the pieces together both in terms of the concepts taught in class (applications, transport and network layers) and as a culminating lab for DartNet. Note, that you should use your own DartNet component code (i.e., SRT, ON) and not any of the code returned as part of the solutions (i.e., the code we return to you as solution and not the code given out as part of the labs) handed out. If you do use any solution code (other than the checksum) in this lab then your lab will be graded out of 70%. The idea is to get you to use your own code for this final lab.

Completing this series of labs really brings home the core set of mechanisms (in a watered down sense) used in Internet everyday, reinforcing the knowledge learnt in class through implementation skills.

Your DartNet Demo: You should set a time up with the TA to demo your DartNet code running. Note, we will not give a grade for this lab unless you have demoed your Lab7 to the TA. Please set a time up with the TA once you have sumbmitted your code. You will have to demo within 48 hours of submitting the code.

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

Getting Started - Some Background Notes

The SNP layer is implemented as a process. Each node in the overlay network will have an SNP process running. The SNP process maintains a TCP connection to the ON process and a TCP connection to the SRT process. The SNP process provides APIs to the SRT process to send segments to destination nodes in the overlay network. The SNP process uses the SNP routing algorithm/protocol (SNP is made up of a routing algorithm and forwarding mechanism all implemented in SNP as a protocol and forwarding mechanism, respectively) to construct the routing table. The SNP process encapsulates received segments sent by the SRT process into SNP packets (one SRT segment in each SNP packet - no fragmentation here) and uses the ON APIs to forward SNP packets to “next hop nodes” toward the destination node. The design notes design provide lots of details on the construction of SNP and its relation to the other DartNet layers; in addition, detailed examples of the routing algorithms is given.

In the lab you need to first implement all the data structures used by the SNP routing protocol, which are: the neighbor cost table, distance vector table and routing table. You then need to implement the SNP routing algorithm as part of the SNP process. Again, we described SNP routing algorithm (which is the Distance Vector Algorithm) in detail in the design notes, please read them before you start. The Distance Vector algorithm is also described in the course book in the Section 4.5.2 - so read that first.

Finally, You need to implement the SNP forwarding mechanism/function. After all these SNP components are implemented, you need to implement the SNP APIs so that your SRT process can use these APIs to send and receive packets over the network. Once you have done that you have completed the DartNet stack - but to prove that your code base works you have to sucessfully run the stress test application between two nodes on your overlay. Then you are done!

However, before you read another line of this programming assignment please read or re-read the Lecture notes on Simple Network Protocol 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, algorithms/mechanisms, you will need to think about how to implement these required components in some detail. To some degree you need to hold the complete design of the application, transport, network and overlay in your mind before writing a line of code. If you do that then the coding phase will fall out nicely. If you don’t conceptual problems may bite you!

So read, study, think, abtract, then code. Don’t code, ..... study, read. That would be perhaps more expedient initially but a risky strategy. This is a difficult one so - think first before engaging the compiler.

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

Please make sure that the lab7 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.

network:
network.c network.h nbrcosttable.c nbrcosttable.h dvtable.c dvtable.h routingtable.c routingtable.h

client:
app_simple_client.c app_stress_client.c srt_client.c srt_client.h send_this_text.txt

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 needed for this lab can be found in this tarball file: lab7handout.tar.gz . Save this and work from this tarball for your assignment.

SNP layer data structures and prototypes needed to implement for the SNP protocol:

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

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.

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.

constants - we increase the SRT timeout values because the packet processing delay is incrased with the full DartNet stack:

Note, please update the topology.dat to run your overlay on any machines you wish e.g., green.cs.dartmouth.edu. Please put the names of the overlay nodes in the file and not explicit IP addresses.

Currently, there are 3 port numbers defined in constants.h:

CONNECTION_PORT
OVERLAY_PORT NETWORK_PORT

\textbf{Important, 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.

Neighbor Cost Table Functions

The Neighbor cost table function prototypes are defined in nbrcosttable.h. You need to implement these function prototypes in nbrcosttable.c.

//nbrcosttable_create() creates a neighbor cost table dynamically
//and initialize the table with all its neighbors’ node IDs and direct link costs.
//The neighbors’ node IDs and direct link costs are retrieved from topology.dat file.

nbr_cost_entry_t* nbrcosttable_create();

//nbrcosttable_destroy() destroys a neighbor cost table.
//It frees all the dynamically allocated memory for the neighbor cost table.

void nbrcosttable_destroy(nbr_cost_entry_t* nct);

//nbrcosttable_getcost() is used to get the direct link cost from a neighbor.
//The direct link cost is returned if the neighboring node is found in the table.
//INFINITE_COST is returned if the node is not found in the table.

unsigned int nbrcosttable_getcost(nbr_cost_entry_t* nct, int nodeID);

//nbrcosttable_print() prints out the contents of a neighbor cost table.

void nbrcosttable_print(nbr_cost_entry_t* nct);

Distance Vector Table Functions

The distance vector table function prototypes are defined in dvtable.h. You need to implement these function prototypes in dvtable.c. Read the design notes and the course book section on distance vector for more context. This is a hard part of the lab - the more knowledge the better.

//dvtable_create() creates a dvtable(distance vector table) dynamically.
//A distance vector table contains n+1 entries, where n is the number of the neighbors of this node,
//and the rest one is for this node itself.
//Each entry in distance vector table is a dv_t structure which contains a source node ID and an array
//of N dv_entry_t structures where N is the number of all the nodes in the overlay.
//Each dv_entry_t contains a destination node address and the destimated link cost from the source node
//to this destination node.
//The dvtable is initialized in this function too.
//The link costs from this node to its neighbors are initialized using direct link cost retrieved from topology.dat.
//Other link costs are initialized to INFINITE_COST.
//The dynamically created dvtable is returned.

dv_t* dvtable_create();

//dvtable_destroy() destroys a dvtable.
//It frees all the dynamically allocated memory for the dvtable.

void dvtable_destroy(dv_t* dvtable);

//dvtable_setcost() sets the link cost between two nodes in dvtable.
//If those two nodes are found in the table and the link cost is set, return 1.
//Otherwise, return -1.

int dvtable_setcost(dv_t* dvtable,int fromNodeID,int toNodeID, unsigned int cost);

//dvtable_getcost() returns the link cost between two nodes in dvtable
//If those two nodes are found in dvtable, return the link cost.
//otherwise, return INFINITE_COST.

unsigned int dvtable_getcost(dv_t* dvtable, int fromNodeID, int toNodeID);

//dvtable_print() prints out the contents of a dvtable.

void dvtable_print(dv_t* dvtable);

Routing Table Functions

The routing table function prototypes are defined in routingtable.h. You need to implement these function prototypes in routingtable.c.

//makehash() is the hash function used the by the routing table
//It takes the hash key - destination node ID as input,
//and returns the hash value - slot number for this destination node ID.

//You can copy makehash() implementation below directly to routingtable.c:
//int makehash(int node) {
// return node%MAX_ROUTINGTABLE_ENTRIES;
//}

int makehash(int node);

//routingtable_create() creates a routing table dynamically.
//All the entries in the table are initialized to NULL pointers.
//Then for all the neighbors with a direct link, create a routing entry using the neighbor
//itself as the next hop node, and insert this routing entry into the routing table.
//The dynamically created routing table structure is returned.

routingtable_t* routingtable_create();

//routingtable_destroy() destroys a routing table.
//All dynamically allocated data structures for this routing table are freed.

void routingtable_destroy(routingtable_t* routingtable);

//routingtable_setnextnode() updates the routing table using the given destination node ID and next hop’s node ID.
//If the routing entry for the given destination already exists, update the existing routing entry.
//If the routing entry of the given destination is not there, add one with the given next node ID.
//Each slot in routing table contains a linked list of routing entries due to conflicting hash keys
//(differnt hash keys (destination node ID here) may have same hash values (slot entry number here)).
//To add an routing entry to the hash table:
//First use the hash function makehash() to get the slot number in which this routing entry should be stored.
//Then append the routing entry to the linked list in that slot.

void routingtable_setnextnode(routingtable_t* routingtable, int destNodeID, int nextNodeID);

//routingtable_getnextnode() looks up the destNodeID in the routing table.
//Since routing table is a hash table, this operation has O(1) time complexity.
//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.
//If the destNodeID is found, return the nextNodeID for this destination node.
//If the destNodeID is not found, return -1.

int routingtable_getnextnode(routingtable_t* routingtable, int destNodeID);

//routingtable_print() prints out the contents of the routing table

void routingtable_print(routingtable_t* routingtable);

The SNP Functions

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

//connectToOverlay() is used to for the SNP process to connect to the local ON process on port OVERLAY_PORT.
//TCP descriptor is returned if success, otherwise return -1.

int connectToOverlay();

//The routeupdate_daemon thread sends out route update packets every ROUTEUPDATE_INTERVAL.
//The route update packet contains this node’s distance vector.
//Broadcasting is done by set the dest_nodeID in packet header as BROADCAST_NODEID
//and use overlay_sendpkt() to send the packet out using BROADCAST_NODEID address.

void* routeupdate_daemon(void* arg);

//The pkthandler thread handles incoming packets from the ON process.
//It receives packets from the ON process by calling overlay_recvpkt().
//If the packet is a SNP packet and the destination node is this node, forward the packet to the SRT process.
//If the packet is a SNP packet and the destination node is not this node, forward the packet to the next hop
//according to the routing table.
//If this packet is an Route Update packet, update the distance vector table and the routing table.

void* pkthandler(void* arg);

//network_stop() stops the SNP process.
//It closes all the connections and frees all the dynamically allocated memory.
//It is called when the SNP process receives a signal SIGINT.

void network_stop();

//waitTranport() opens a port on NETWORK_PORT and waits for the TCP connection from local SRT process.
//After the local SRT process is connected, this function keeps receiving sendseg_arg_ts which contain
//the segments and their destination node IDes 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 nodeID is retrieved from routing table.
//When a local SRT process is disconnected, this function waits for the next SRT process to connect.

void waitTranport();

The SNP APIs

The SNP APIs are defined in seg.h and they should be implemented in seg.c. The seglost(), checksum() and checkchecksum() functions are not listed. You can reuse your implementation of these function from lab5.

//SRT process uses this function to send a segment and its destination node ID in a sendseg_arg_t
//structure to SNP process to send out.
//Parameter network_conn is the TCP descriptor of the connection between the SRT process and the SNP process.
//Return 1 if a sendseg_arg_t is successfully sent, otherwise return -1.

int snp_sendseg(int network_conn, int dest_nodeID, seg_t* segPtr);

//SRT process uses this function to receive a sendseg_arg_t structure which contains a segment and
//its src node ID from the SNP process.
//Parameter network_conn is the TCP descriptor of the connection between the SRT process and the SNP process.
//When a segment is received, use seglost() to determine if the segment should be discarded and introduce the error
//by flipping a bit. checkchecksum() is used to check the checksum. This is same as what you did in lab5.
//Return 1 if a sendseg_arg_t is successfully received, otherwise return -1.

int snp_recvseg(int network_conn, int* src_nodeID, seg_t* segPtr);

//SNP process uses this function to receive a sendseg_arg_t structure which contains a segment and
//its destination node ID from the SRT process.
//Parameter tran_conn is the TCP descriptor of the connection between the SRT process and the SNP process.
//Return 1 if a sendseg_arg_t is successfully received, otherwise return -1.

int getsegToSend(int tran_conn, int* dest_nodeID, seg_t* segPtr);

//SNP process uses this function to send a sendseg_arg_t structure which contains a segment and
//its src node ID to the SRT process.
//Parameter tran_conn is the TCP descriptor of the connection between the SRT process and the SNP process.
//Return 1 if a sendseg_arg_t is successfully sent, otherwise return -1.

int forwardsegToSRT(int tran_conn, int src_nodeID, seg_t* segPtr);

CS 60 Computer Networks

Lab7

DartNet: Simple Network Protocol (SNP) Implementation - Putting it all together!