依然是来自《计算机网络:自顶向下》的实验,要求在实验中模拟网络层中路由算法的实现。至于一些准备工作嘛,和实现一个可靠的运输层协议实验一样。实验中需要使用相对简单的Distance Vector路由算法。由于一共有四个节点需要编写程序,如果把每一个节点的实现都解释一遍也没必要,所以以0节点为例。

初级部分

模拟节点数据结构的设计

首先要设计每个节点的存储的数据,实验的设计者强烈建议用一个4×4的二维数组distance[i][j]来保存当前节点经过i节点到达j节点需要的路径长度,其中用999来表示无法到达(无穷)。如果当前结点无法到达节点i,那么第i行的数据都为无穷。 除了距离向量表外,我们还需要一个路由表来保存前往各个节点的最佳路由路线的下一个节点,所以需要定义这两个数组:

static int cost[TOTAL][TOTAL];	/* distance table: cost[i][j] represent the cost to j through i */
static int routing[TOTAL];		/* rounting table: the best path to node i */

节点的初始化

初始化需要做以下工作:

  1. 初始化路径距离向量,其中本节点到邻居节点的距离是已知的,可以直接设置好,然后把其余的全部设为无穷大;

  2. 初始化路由表,把每个通向每个节点的入口全部指向那个节点,因为此时0节点并不知道是否可以通过邻居节点到达非邻居节点。

  3. 把自己的路由信息传播出去。

rtinit0()
{
	int i, j;
	/* Init distance table */
	for (i = 0; i < TOTAL; i++)
		for (j = 0; j < TOTAL; j++)
			cost[i][j] = INFINITY;
	/* Init routing table */
	for (i = 0; i < TOTAL; i++)
		routing[i] = i;
	/* Count costs to neighbor */
	cost[ME][ME] = 0;
	cost[1][1] = 1;
	cost[2][2] = 3;
	cost[3][3] = 7;
	/* Broadcast */
	broadcast();
}

在初始化完成之后,节点0需要通知邻居节点来更新路由信息,为了复用代码,编写了broadcast函数,函数的工作就是把自己的路由表中到达每个节点的距离发出去。

/* broadcast: broadcast routing packet to neighbor */
static broadcast()
{
	int i, j;
	for (i = 0; i < TOTAL; i++)
		if (i != ME && cost[i][i] != INFINITY) {
			/* Construct routing packets */
			struct rtpkt packet;
			packet.sourceid = ME;
			packet.destid = i;
			for (j = 0; j < TOTAL; j++)
				packet.mincost[j] = cost[routing[j]][j];
			/* Send packet */
			tolayer2(packet);
		}
}

节点间的信息传递

邻居节点初始化完成之后,会陆续发来路由信息,我们接收到这些信息之后需要按照一定规则来更新自己的路由表。当一个新的数据包到达时,如果通过这个邻居节点,我们可以找到更短的路径,那么久可以更新本节点的路由表。如果更新了路由表,我们选哟重新向邻居节点传播路由信息。

rtupdate0(rcvdpkt)
struct rtpkt *rcvdpkt;
{
	int i, source = rcvdpkt->sourceid, changed = 0;
	for (i = 0; i < TOTAL; i++) {
		/* Save distance */
		int new_cost = cost[source][source] + rcvdpkt->mincost[i];
		/* Update routing table */
		int old_cost = cost[routing[i]][i];
		if (new_cost < old_cost) {
			changed = 1;
			routing[i] = source;
		}
		/* Update distance table */
		cost[source][i] = new_cost;
	}
	/* If rouitng table changed, notify neighbors */
	if (changed)
		broadcast();
}

执行算法,得到以下的结果,正确无误。

The distance table of node 0:
 0 999 999 999
 2 1 2 4
 5 4 3 5
 11 10 9 7
The distance table of node 1:
 1 2 3 5
 999 0 999 999
 3 2 1 3
 999 999 999 999
The distance table of node 2:
 3 4 5 7
 2 1 2 4
 999 999 0 999
 6 5 4 2
The distance table of node 3:
 7 8 9 11
 999 999 999 999
 4 3 2 4
 999 999 999 0

高级部分

开始高级模式后,路径0-1的长度会在第1秒变为20,然后又在第2秒重新变回1。

高级部分与初级部分在实现上的区别

高级部分与初级部分有着很大的区别。上面的路由表更新算法里面,是每次找到一个更短的路径才会更新路由表,并不能处理距离变长的情况,所以我们还需要在处理的时候重新计算并判断原来的路径长度是不是发生了改变。好在实验中的设定比较简单,这种改进还是有效的。在残酷的现实世界里面,由于Distance Vector算法本身固有的缺点,这种改进并没有什么卵用。

路径信息变动处理

在得到路径长度变化这个悲伤的消息之后,首先需要更新距离向量,把经过1节点的所有路径全部加上长度的变化量。然后更新路由表。

linkhandler0(linkid, newcost)
int linkid, newcost;
{
	/* Update distance table */
	int cost_diff = newcost - cost[linkid][linkid], i, j;
	for (i = 0; i < TOTAL; i++)
		cost[linkid][i] += cost_diff;
	/* Rebuild routing table */
	for (i = 0; i < TOTAL; i++)
		/* Path through linkid need to be rebuild */
		if (i != ME && routing[i] == linkid) {
			/* Find the best new path */
			int best = linkid;
			for (j = 0; j < TOTAL; j++)
				if (j != ME && cost[j][i] < cost[best][i])
					best = j;
			routing[i] = best;
		}
	/* Broadcast */
	broadcast();
}

路由表更新方法的改进

路由表更新算法需要做一些改进:当路由表中路径的长度发生变化的时候,需要重新找到最佳的路径。

rtupdate0(rcvdpkt)
struct rtpkt *rcvdpkt;
{
	int i, j, source = rcvdpkt->sourceid, changed = 0;
	for (i = 0; i < TOTAL; i++) {
		/* Compute new cost */
		int new_cost = cost[source][source] + rcvdpkt->mincost[i];
		/* Save old cost */
		int old_cost = cost[routing[i]][i];
		/* Update distance table */
		cost[source][i] = new_cost;
		/* Update routing table */
		if (new_cost < old_cost) {
			changed = 1;
			routing[i] = source;
		} else if (routing[i] == source && new_cost > old_cost) {
			/* Find the best path */
			int best = source;
			for (j = 0; j < TOTAL; j++)
				if (j != ME && cost[j][i] < cost[best][i])
					best = j;
			changed = 1;
			routing[i] = best;
		}
	}
	/* If rouitng table changed, notify neighbors */
	if (changed)
		broadcast();
}

现在我们检查一下第一次改变路径长度后程序运行结果是否正确,是对的。

The distance table of node 0:
   0 999 999 999
  24  20  21  23
   6   4   3   5
  12  10   9   7
The distance table of node 1:
  20  24  23  25
 999   0 999 999
   4   2   1   3
 999 999 999 999
The distance table of node 2:
   3   7   6   8
   5   1   2   4
 999 999   0 999
   7   5   4   2
The distance table of node 3:
   7  11  10  12
 999 999 999 999
   5   3   2   4
 999 999 999   0

在路径0-1变回1之后,距离表重新变成了下面这个样子,和初级部分的是一样的,所以运行结果正确。

The distance table of node 0:
   0 999 999 999
   2   1   2   4
   5   4   3   5
  11  10   9   7
The distance table of node 1:
   1   2   3   5
 999   0 999 999
   3   2   1   3
 999 999 999 999
The distance table of node 2:
   3   4   5   7
   2   1   2   4
 999 999   0 999
   6   5   4   2
The distance table of node 3:
   7   8   9  11
 999 999 999 999
   4   3   2   4
 999 999 999   0

其他节点的源代码在这里:node0.cnode1.cnode2.cnode3.c