简单网络协议(SNP)

在前面的文章中，我们在DartNet覆盖网络（ON）层上直接实现了SRT。现在我们需要添加路由和分组转发到DartNet。本篇文章将介绍DartNet网络层的设计，并实现简单网络协议（SNP），以提供类似于在互联网路由器上运行的IP协议和路由的转发。

本篇文章的具体内容：

SNP API

SNP路由协议

SNP数据包转发

SNP过程实现

DartNet

在DartNet中，在每对相邻节点之间存在TCP连接。在每个节点上，存在覆盖网络（ON）层，简单网络协议（SNP）层，简单可靠传输（SRT）层和应用层

ON进程包含n + 1个线程，其中n是相邻节点的数目。对于这些ON线程，一个是主线程，另外n个线程是listen_to_neighbor线程。实现覆盖网络（ON）层

SNP进程包含3个线程：主线程，pkthandler线程和routeupdate_daemon线程。实现简单网络协议（SNP）层

SRT进程包含两个线程：主线程和seghandler线程。实现SRT层和应用层。

DartNet实现图

SNP API

DartNet API调用图

SNP进程向SRT进程提供两个函数：snp_sendseg（）和snp_recvseg（）。我们之前实现了这两个SNP API。然而在那时，这些SNP API是使用两个节点之间的直接TCP连接来实现的。在这里我们将使用ON层重新实现这些API

SRT进程调用snp_sendseg（）将段发送到目标节点。当SRT进程调用snp_sendseg（）时，sendseg_arg_t结构被发送到本地SNP进程。本地SNP进程使用getsegToSend（）接收此sendseg_arg_t结构。然后，本地SNP进程将每个分段封装到一个分组中，并使用overlay_sendpkt（）将分组发送到下一跳。

SNP进程通过调用overlay_recvpkt（）函数从本地ON进程接收数据包。在SNP过程接收到分组之后，SNP过程从分组的数据字段中提取分段，并且向本地SRT过程转发sendseg_arg_t结构。本地SRT进程调用snp_recvseg（）接收此sendseg_arg_t结构。

sendseg_arg_t在seg.h中定义

//This is the data structure exchanged between the SNP process and the SRT process.
//It contains a node ID and a segment.
//For snp_sendseg(), the node ID is the destination node ID of the segment.
//For snp_recvseg(), the node ID is the source node ID of the segment.

typedef struct sendsegargument {
  int nodeID;   //node ID
  seg_t seg;    //a segment
} sendseg_arg_t;

SNP路由协议

SNP路由协议是距离矢量路由协议。SNP路由协议使用链路成本作为路由度量。当两个节点之间存在多条路径时，应选择总链路成本较小的路径。我们先看看SNP路由协议使用的数据结构。然后讨论SNP路由算法。

SNP路由协议使用3个表：邻居成本表，距离向量表和路由表。我们将一一讨论它们。覆盖中的每个节点都有一个SNP进程在其上运行，每个SNP进程维护一个邻居成本表，一个距离向量表和一个路由表，用于运行它的节点。

邻居链路成本表

节点的邻居成本表包含到其所有邻居的直接链路成本。邻居成本表具有n个条目，其中n是节点的邻居的数量。邻居成本表项在network / nbrcosttable.h中定义。

//neighbor cost table entry definition

typedef struct neighborcostentry {
  unsigned int nodeID;  //neighbor’s node ID
  unsigned int cost;    //direct link cost to the neighbor
} nbr_cost_entry_t;

当SNP过程开始时，动态创建邻居表。邻居成本表通过解析topology.dat中包含的拓扑信息来初始化。

距离向量表

距离向量表包含从源节点到网络中所有节点的估计的链路成本。距离向量结构在network / dvtable.h中定义

//distance vector entry definition

typedef struct distancevectorentry {
  int nodeID;         //destination nodeID
  unsigned int cost;  //estimated link cost to the destination
} dv_entry_t;

//distance vector definition

typedef struct distancevector {
  int         nodeID;   //source nodeID
  dv_entry_t  *dvEntry; //an array of N dv_entry_ts, each of which contains the
                //destination node ID and the estimated link cost to the destination
                //from the source node. N is the total number of nodes in the overlay.
} dv_t;

dv_t是一个距离向量，其包含源nodeID和N个dv_entry_t结构的数组，其中N是覆盖中的节点总数(表中的横坐标)。dv_entry_t包含目的节点ID和到目的地节点的链路成本。距离向量表包含n + 1个距离向量 (表中的纵坐标)，其中n是节点的邻居的数目，另一个为节点本身。

当SNP过程开始时，动态创建距离向量表。使用来自topology.dat文件的链路成本信息来初始化节点自身的距离向量。目的地节点为节点本身，则链路成本为0。目的地节点是相邻节点，链路成本是直接链路成本。否则，估计的链接成本为INFINITE_COST。距离向量表中的相邻节点的其他距离向量用INFINITE_COST初始化。

路由表

路由表是具有MAX_ROUTINGTABLE_SLOTS个元素的散列表。每个元素指向一个routingtable_entry_t链表。使用链表解决冲突。routingtable_entry_t结构和路由表本身在network/routingtable.h中定义。

路由表

//routingtable_entry_t is the routing entry contained in the routing table.

typedef struct routingtable_entry {
  int destNodeID;                   //destination node ID
  int nextNodeID;                   //next node ID to which the packet should be forwarded
  struct routingtable_entry* next;  //pointer to the next routingtable_entry_t in the same routing table slot
} routingtable_entry_t;

//A routing table is a hash table containing MAX_ROUTINGTABLE_SLOTS slots.
//Each slot is a linked list of routing entries.

typedef struct routingtable {
  routingtable_entry_t* hash[MAX_ROUTINGTABLE_SLOTS];
} routingtable_t;

routing_entry_t结构包含此目标节点的ID和下一跳的nodeID。路由表是一个哈希表。makehash（）是哈希表的散列函数，键值为目标节点ID，散列值为目标节点在哈希表的槽号

要将路由entry添加到路由表，首先使用散列函数makehash（）来获取应存储此路由entry槽号。然后将路由entry插入该槽中的链表中。要查找一个目标路由entry，过程与添加类似

通过为所有相邻节点添加路由entry来初始化路由表，对于作为目的地节点的每个相邻节点，将下一跳节点设置为相邻节点本身。

SNP路由算法

SNP路由协议使用距离向量路由算法。具体原理与实现，可以自行阅读《计算机网咯：自顶向下方法》中的距离矢量（DV）路由算法。

当SNP进程启动时，它启动一个routeupdate_daemon线程。routeupdate_daemon线程每ROUTEUPDATE_INTERVAL时间间隔广播一个路由更新包。该路由更新包的内容是源节点的距离向量。接收方的距离向量表和路由表根据此距离向量信息更新相应的表项。接收方不会转发接收到的路由更新包，路由更新只会被源节点的直接邻居接收。

SNP路由算法实现过程中，用图片的形式，表示各表内容的变化。

DartNet拓扑

邻居链路成本表

初始化后，节点的距离向量表和路由表显示在图的左侧。
在所有节点接收到来自它们的邻居的所有第一路由更新分组之后，距离向量表更新并且在图的右侧示出

在所有节点从其邻居接收到第二路由更新分组之后的距离向量表和路由表

数据包转发

在SNP过程中，分组转发在pkthandler线程中完成。pkthandler线程通过调用overlay_recvpkt（）从ON进程接收数据包。

如果接收的分组是SNP分组，并且目的地节点是该节点，则pkthandler线程将分组转发到SRT进程。
如果分组是SNP分组，并且目的地节点不是该节点，则pkthandler线程根据路由表将分组转发到下一跳。
如果该分组是路由更新分组，则pkthandler线程使用我们上面描述的SNP路由算法来更新距离向量表和路由表。

SNP过程实现

SNP作为进程运行。覆盖层中的每个节点都有一个SNP进程在其上运行。SNP进程的代码如下所示：

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

  //initialize global variables
  nct = nbrcosttable_create();
  dv = dvtable_create();
  dv_mutex = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t));
  pthread_mutex_init(dv_mutex,NULL);
  routingtable = routingtable_create();
  routingtable_mutex = (pthread_mutex_t*)malloc(sizeof(pthread_mutex_t));
  pthread_mutex_init(routingtable_mutex,NULL);
  overlay_conn = -1;
  transport_conn = -1;

  nbrcosttable_print(nct);
  dvtable_print(dv);
  routingtable_print(routingtable);

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

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

  //start a thread that handles incoming packets from ON process
  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");
  printf("waiting for routes to be established\n");
  sleep(NETWORK_WAITTIME);
  routingtable_print(routingtable);

  //wait connection from SRT process
  printf("waiting for connection from SRT process\n");
  waitTransport();

当SNP过程开始时，首先建表并初始化这些表。SNP过程还创建和初始化两个互斥：一个用于向量表，另一个用于路由表。

overlay_conn为SNP进程与本地ON进程的连接的TCP描述符和transport_conn为SNP进程与本地SRT进程的连接的TCP描述符。当SNP过程开始时，SNP过程将overlay_conn和transport_conn初始化为-1作为无效。

然后，SNP进程将信号处理程序network_stop（）注册到信号SIGINT，使得当接收到SIGINT信号时，调用network_stop（）以终止SNP进程。SNP进程调用函数connectToOverlay（）连接到端口OVERLAY_PORT上的本地ON进程

在建立与ON进程的TCP连接之后，SNP进程启动pkthandler线程。接着启动routeupdate_daemon线程。然后，SNP过程等待一段时间，以便路由表更新完成

SNP进程然后调用waitTransport（）函数在NETWORK_PORT上打开一个端口来等待来自本地SRT进程的TCP连接。连接本地SRT进程后，waitTransport（）函数接收sendseg_arg_t结构，其中包含来自SRT进程的段及其目标nodeID。将接收的段封装重新封装，并使用overlay_sendpkt发送到下一跳。从路由表中检索下一跳的节点ID。

SNP过程在接收到SIGINT信号时终止。当接收到SIGINT信号时，信号处理器函数network_stop（）通过关闭所有TCP连接，释放所有动态分配的内存并终止SNP进程来停止覆盖