这个实验要求我们实现一个可靠的运输层协议(也可以理解为链路层协议,反正算法什么都是类似的)。做实验的第一步当然是阅读实验说明了。实验的源文件是用K&R C写的,看起来很奇怪,但是不必担心,GCC是可以完美编译的(不需要加什么特殊的参数)。按照实验的说明修改好随机数最大值、把文件里 的exit()改成exit(0)就可以开始做正事了。

Checksum

校检和是保证数据正确无误到达接收端的关键,当然采用最为流行的UDP校检方式了。校检码的计算方式就是:将整个packet里的数据按照每16位相加,如果得到的和的数值超过16位,那么把超出的部分右移16位,加到校检和中。

/* Compute checksum */
int compute_check_sum(packet)
struct pkt packet;
{
	int sum = 0, i = 0;
	sum = packet.checksum;
	sum += packet.seqnum;
	sum += packet.acknum;
	sum = (sum >> 16) + (sum & 0xffff);
	for (i = 0; i < 20; i += 2) {
		sum += (packet.payload[i] << 8) + packet.payload[i+1];
		sum = (sum >> 16) + (sum & 0xffff);
	}
	sum = (~sum) & 0xffff;
	return sum;
}

Stop-and-Wait

这个部分的操作就是,发送端每次只发送一个数据包,在收到ACK后,才发送下一个数据包。为了让发送端和接收端正常工作,不妨做好约定,第一个数据包的seq为0。

Sender(A Side)

初始化的时候,初始化好下一个期望收到的数据包的seq。

/* the following rouytine will be called once (only) before any other */
/* entity B routines are called. You can use it to do any initialization */
B_init()
{
	seq_expect_recv = 0;
}

接收数据包的时候,首先查看数据包的seq是不是期待的,如果是的话进行校检,校检失败就返回NAK,结束函数调用,校检成功就把数据发给上层。最后,无论是什么数据包,接收端都要返回ACK,这一点真的很难注意到。(因为ACK也可能丢失,那么发送方会发生重复的包,这时也是要返回ACK的)。

/* called from layer 3, when a packet arrives for layer 4 at B*/
B_input(packet)
struct pkt packet;
{
	if (packet.seqnum == seq_expect_recv) {
		/* If corruption occurs, send NAK */
		if (compute_check_sum(packet)) {
			struct pkt nakpkt;
			nakpkt.acknum = -1;
			tolayer3(1, nakpkt);
			return;
		}
		/* Pass data to layer5 */
		struct msg message;
		memcpy(message.data, packet.payload, sizeof(packet.payload));
		tolayer5(1, message);
		seq_expect_recv = 1 - seq_expect_recv;
		/* Debug output */
		if (DEBUG)
			print_pkt("Accpeted", packet);
	}
	/* Send ACK to A side */
	struct pkt ackpkt;
	ackpkt.acknum = packet.seqnum;
	tolayer3(1, ackpkt);
}

Reciever(B Side)

初始化的时候把等待状态设为0,把将要发送(等待ACK)的数据包的seq设为0。

/* the following routine will be called once (only) before any other */
/* entity A routines are called. You can use it to do any initialization */
A_init()
{
	seq_expect_send = 0;
	is_waiting = 0;
}

发送数据包的时候,首先确定发送方是否处于等待状态,如果在等状态,就取消发送。接着发送数据包,开启计时器,开始等待。

/* called from layer 5, passed the data to be sent to other side */
A_output(message)
struct msg message;
{
	/* If A is waiting, ignore the message */
	if (is_waiting)
		return;
	/* Send packet to B side */
	memcpy(waiting_packet.payload, message.data, sizeof(message.data));
	waiting_packet.seqnum = seq_expect_send;
	waiting_packet.checksum = 0;
	waiting_packet.checksum = compute_check_sum(waiting_packet);
	tolayer3(0, waiting_packet);
	starttimer(0, TIME_OUT);
	is_waiting = 1;
	/* Debug output */
	if (DEBUG)
		print_pkt("Sent", waiting_packet);
}

 接收ACK或NAK的时候,立刻停止计时器,如果是ACK,就结束等待状态,准备发送下一个数据包,如果是NAK,就重新发送。

/* called from layer 3, when a packet arrives for layer 4 */
A_input(packet)
struct pkt packet;
{
	stoptimer(0);
	if (packet.acknum == seq_expect_send) {	/* ACK */
		seq_expect_send = 1 - seq_expect_send;
		is_waiting = 0;
	} else if (packet,acknum == -1) {		/* NAK */
		tolayer3(0, waiting_packet);
		starttimer(0, TIME_OUT);
	}
}

超时需要重发数据包。

/* called when A's timer goes off */
A_timerinterrupt()
{
	tolayer3(0, waiting_packet);
	starttimer(0, TIME_OUT);
}

在运行的时候,一次传输需要的时间均匀分布在1-10单位之间,所以我把超时时间设置为24单位。消息数量为12,损坏率为0.1,丢包率为0.3,发送间隔为1000单位,测试结果如下:

Sent: seq = 0, ack = 0, checksum = 3232, aaaaaaaaaaaaaaaaaaaa
Accpeted: seq = 0, ack = 0, checksum = 3232, aaaaaaaaaaaaaaaaaaaa
Sent: seq = 1, ack = 0, checksum = 2827, bbbbbbbbbbbbbbbbbbbb
Accpeted: seq = 1, ack = 0, checksum = 2827, bbbbbbbbbbbbbbbbbbbb
Sent: seq = 0, ack = 0, checksum = 1e1e, cccccccccccccccccccc
Accpeted: seq = 0, ack = 0, checksum = 1e1e, cccccccccccccccccccc
Sent: seq = 1, ack = 0, checksum = 1413, dddddddddddddddddddd
Accpeted: seq = 1, ack = 0, checksum = 1413, dddddddddddddddddddd
Sent: seq = 0, ack = 0, checksum = a0a, eeeeeeeeeeeeeeeeeeee
Accpeted: seq = 0, ack = 0, checksum = a0a, eeeeeeeeeeeeeeeeeeee
Sent: seq = 1, ack = 0, checksum = f5f4, gggggggggggggggggggg
Accpeted: seq = 1, ack = 0, checksum = f5f4, gggggggggggggggggggg
Sent: seq = 0, ack = 0, checksum = ebeb, hhhhhhhhhhhhhhhhhhhh
Accpeted: seq = 0, ack = 0, checksum = ebeb, hhhhhhhhhhhhhhhhhhhh
Sent: seq = 1, ack = 0, checksum = e1e0, iiiiiiiiiiiiiiiiiiii
Accpeted: seq = 1, ack = 0, checksum = e1e0, iiiiiiiiiiiiiiiiiiii
Sent: seq = 0, ack = 0, checksum = d7d7, jjjjjjjjjjjjjjjjjjjj
Accpeted: seq = 0, ack = 0, checksum = d7d7, jjjjjjjjjjjjjjjjjjjj
Sent: seq = 1, ack = 0, checksum = cdcc, kkkkkkkkkkkkkkkkkkkk
Accpeted: seq = 1, ack = 0, checksum = cdcc, kkkkkkkkkkkkkkkkkkkk

Go Back N

Stop-and-wait协议每次只能发送一个数据包,是对带宽巨大的浪费,因此需要一种可以批量发送接收的协议来提高带宽利用率。

多重计时器的实现

在回退N步协议中,每一个发送的数据包都需要计时,然而只有一个计时器,我们需要想办法来利用一个计时器实现多重计时。不过这里的需求要更简单一些,因为这里的开启计时器和停止计时器的操作都是严格按照顺序的。

开启计时器之前,检查是否已经有计时器在计时。如果没有计时器,那么直接开始计时,否则根据全局变量time计算出计时器预计结束的时间,然后将这个时间加入队列。

关闭计时器的时候,停止当前的计时器。如果队列中还有计时器,那么根据保存的结束时间计算出increment,开启计时器。

当然在计时器中断之后,需要告诉多重计时器计时中断。

/* multitimer: 
 * start a timer for each packet using one timer 
 */
float timers_expire[NODE][MAX_WINDOW];
int timers_seqs[NODE][MAX_WINDOW];
int timers_seq[NODE] = {0, 0};
int timers_running[NODE] = {0, 0};
int timers_head[NODE] = {0, 0};
int timers_tail[NODE] = {0, 0};
float time = 0.0;

/* call this function after the first timer goes off or was be closed */
interrupt_multitimer(AorB)
int AorB;
{
	timers_running[AorB] = 0;
}

/* start a timer for a packet */
start_multitimer(AorB, seqnum)
int AorB, seqnum;
{
	/* bound check */
	if (timers_head[AorB] == timers_tail[AorB] + 1) {
		printf("Warning: you can't create more than %d timers.\n", MAX_WINDOW);
		return;
	}
	if (timers_running[AorB] == 0) {	/* if timers isn't running, start the timer right now */
		timers_running[AorB] = 1;
		timers_seq[AorB] = seqnum;
		starttimer(AorB, TIME_OUT);
	} else {					/* else, add this timer into the queue */
		timers_expire[AorB][timers_tail[AorB]] = time + TIME_OUT;
		timers_seqs[AorB][timers_tail[AorB]] = seqnum;
		timers_tail[AorB] = INC(timers_tail[AorB]);
	}
}

/* stop the first timer */
stop_multitimer(AorB, seqnum)
int AorB, seqnum;
{
	/* bound check */
	if (timers_running[AorB] == 0) {
		printf("Warning: you are trying to stop a timer isn't running.\n");
		return;
	}
	/* stop the first timer */
	stoptimer(AorB);
	timers_running[AorB] = 0;
	/* if there is more timer, run it right now */
	if (timers_head[AorB] != timers_tail[AorB]) {
		timers_running[AorB] = 1;
		float increment = timers_expire[AorB][timers_head[AorB]] - time;
		timers_seq[AorB] = timers_seqs[AorB][timers_head[AorB]];
		timers_head[AorB] = INC(timers_head[AorB]);
		starttimer(AorB, increment);
	}
}

队列的实现

在发送窗口满了以后,随后到达的数据需要保存到队列之中,等到窗口的减小后再加入窗口,队列的数据结构没有啥难度。

/* queue:
 * when message is out of the sender's window, put the messge in queue
 */
int queue_head[NODE] = {0, 0};
int queue_tail[NODE] = {0, 0};
struct msg queue_buffer[NODE][MAX_BUF];

/* check if queue is empty */
#define empty(AorB) (queue_head[AorB] == queue_tail[AorB])

/* put message in queue */
push(AorB, message)
int AorB;
struct msg message;
{
	/* bound check */
	if (queue_head[AorB] == queue_tail[AorB] + 1) {
		printf("Warning: there is no avaliable space in queue.\n");
		return;
	}
	queue_buffer[AorB][queue_tail[AorB]] = message;
	queue_tail[AorB] = INC(queue_tail[AorB]);
}

/* get messsage out of queue */
struct msg pop(AorB)
int AorB;
{
	/* bound check */
	if (empty(AorB)) {
		printf("Warning: no packet in queue.\n");
		return;
	}
	struct msg message = queue_buffer[AorB][queue_head[AorB]];
	queue_head[AorB] = INC(queue_head[AorB]);
	return message;
}

滑动窗口实现

初始化的时候,把所有的变量初始化为0。

/* the following routine will be called once (only) before any other */
initialize(AorB)
int AorB;
{
	packet_in_buffer[AorB] = 0;
	expect_send[AorB] = 0;
	expect_ack[AorB] = 0;
	expect_recv[AorB] = 0;
}

接受上层调用时,如果发送窗口未满,那么将数据包发送并加入发送窗口,否则加入队列。

/* called from layer 5, passed the data to be sent to other side */
output(AorB, message)
int AorB;
struct msg message;
{
	/* check if msg is in the window */
	if (packet_in_buffer[AorB] < MAX_WINDOW) {
		/* construct a packet */
		struct pkt packet = construct_packet(AorB, message);
		tolayer3(AorB, packet);  
		start_multitimer(AorB, packet.seqnum);
		/* debug output */
		if (DEBUG)
			print_packet(AorB, "Send", packet);
	} else {
		push(AorB, message);
	}
}

接受下层调用时,首先检查数据正确性和seq,如果不符合条件就直接丢弃数据包,否则接收数据包。把数据传到上一层后,根据数据包的acknum释放发送窗口里的数据包,最后检查消息队列,尝试将排队的数据插入到发送窗口中。

/* called from layer 3, when a packet arrives for layer 4 */
input(AorB, packet)
int AorB;
struct pkt packet;
{
	/*	if (DEBUG)
		print_packet("Recieved", packet);*/
	if (compute_check_sum(packet) == 0 && expect_recv[AorB] == packet.seqnum) {
		/* pass data to layer3 */
		struct msg message;
		memcpy(message.data, packet.payload, sizeof(packet.payload));
		tolayer5(AorB, message);
		expect_recv[AorB] = INC(expect_recv[AorB]);
		/* release ACKed packet */
		while (between(expect_ack[AorB], packet.acknum, expect_send[AorB])) {
/*			if (DEBUG)
				print_packet(AorB, "Acknowledged", window_buffer[AorB][expect_ack[AorB]]);*/
			expect_ack[AorB] = INC(expect_ack[AorB]);
			packet_in_buffer[AorB]--;
			stop_multitimer(AorB, expect_ack[AorB]);
		}
		/* add new packet from queue */
		while (packet_in_buffer[AorB] < MAX_WINDOW && !empty(AorB)) {
			struct msg message = pop(AorB);
			struct pkt packet = construct_packet(AorB, message);
			tolayer3(AorB, packet);
			start_multitimer(AorB, packet.seqnum);
			/* debug output */
			if (DEBUG)
				print_packet(AorB, "Send", AorB, packet);
		}
		/* debug output */
		if (DEBUG)
			print_packet(AorB, "Accepted", packet);
	}
}

计时器中断之后,首先通知多重计划器做好重置工作,然后把发送窗口中未ACK的数据包全部重新发送一遍。

/* called when A's timer goes off */
timerinterrupt(AorB)
int AorB;
{
	interrupt_multitimer(AorB);
	int seqnum;
	for (seqnum = expect_ack[AorB]; seqnum != expect_send[AorB]; seqnum = INC(seqnum)) {
		if (seqnum != expect_ack[AorB])
			stop_multitimer(AorB, seqnum);
		tolayer3(AorB, window_buffer[AorB][seqnum]);
		start_multitimer(AorB, seqnum);
/*		if (DEBUG)
			print_packet(AorB, "Timeout retransmit", window_buffer[AorB][seqnum]);*/
	}
}

测试结果如下,成功传输20个数据包。

[1] Send: seq = 0 ack = 7 checksum = 322b aaaaaaaaaaaaaaaaaaaa
[0] Send: seq = 0 ack = 7 checksum = 2821 bbbbbbbbbbbbbbbbbbbb
[1] Send: seq = 1 ack = 7 checksum = 1e16 cccccccccccccccccccc
[0] Accepted: seq = 0 ack = 7 checksum = 322b aaaaaaaaaaaaaaaaaaaa
[0] Accepted: seq = 1 ack = 7 checksum = 1e16 cccccccccccccccccccc
[1] Accepted: seq = 0 ack = 7 checksum = 2821 bbbbbbbbbbbbbbbbbbbb
[1] Send: seq = 2 ack = 0 checksum = 1412 dddddddddddddddddddd
[1] Send: seq = 3 ack = 0 checksum = a07 eeeeeeeeeeeeeeeeeeee
[0] Accepted: seq = 2 ack = 0 checksum = 1412 dddddddddddddddddddd
[1] Send: seq = 4 ack = 0 checksum = fffb ffffffffffffffffffff
[0] Send: seq = 1 ack = 2 checksum = f5f2 gggggggggggggggggggg
[1] Accepted: seq = 1 ack = 2 checksum = f5f2 gggggggggggggggggggg
[0] Send: seq = 2 ack = 2 checksum = ebe7 hhhhhhhhhhhhhhhhhhhh
[0] Accepted: seq = 3 ack = 0 checksum = a07 eeeeeeeeeeeeeeeeeeee
[1] Send: seq = 5 ack = 1 checksum = e1db iiiiiiiiiiiiiiiiiiii
[1] Send: seq = 6 ack = 1 checksum = d7d0 jjjjjjjjjjjjjjjjjjjj
[1] Accepted: seq = 2 ack = 2 checksum = ebe7 hhhhhhhhhhhhhhhhhhhh
[0] Send: seq = 3 ack = 3 checksum = cdc7 kkkkkkkkkkkkkkkkkkkk
[1] Send: seq = 7 ack = 2 checksum = c3ba llllllllllllllllllll
[1] Send: seq = 0 ack = 2 checksum = b9b7 mmmmmmmmmmmmmmmmmmmm
[0] Send: seq = 4 ack = 3 checksum = afa8 nnnnnnnnnnnnnnnnnnnn
[0] Send: seq = 5 ack = 3 checksum = a59d oooooooooooooooooooo
[1] Accepted: seq = 3 ack = 3 checksum = cdc7 kkkkkkkkkkkkkkkkkkkk
[0] Accepted: seq = 4 ack = 0 checksum = fffb ffffffffffffffffffff
[0] Accepted: seq = 5 ack = 1 checksum = e1db iiiiiiiiiiiiiiiiiiii
[0] Send: seq = 6 ack = 5 checksum = 9b90 pppppppppppppppppppp
[1] Accepted: seq = 4 ack = 3 checksum = afa8 nnnnnnnnnnnnnnnnnnnn
[1] Send: seq = 1 ack = 4 checksum = 918c qqqqqqqqqqqqqqqqqqqq
[0] Send: seq = 7 ack = 5 checksum = 877b rrrrrrrrrrrrrrrrrrrr
[1] Send: seq = 2 ack = 4 checksum = 7d77 ssssssssssssssssssss
[0] Send: seq = 0 ack = 5 checksum = 736e tttttttttttttttttttt
[1] Accepted: seq = 5 ack = 3 checksum = a59d oooooooooooooooooooo
[1] Accepted: seq = 6 ack = 5 checksum = 9b90 pppppppppppppppppppp
[0] Send: seq = 1 ack = 5 checksum = 6963 uuuuuuuuuuuuuuuuuuuu
[1] Send: seq = 3 ack = 6 checksum = 554c wwwwwwwwwwwwwwwwwwww
[0] Accepted: seq = 6 ack = 1 checksum = d7d0 jjjjjjjjjjjjjjjjjjjj
[1] Send: seq = 4 ack = 6 checksum = 4137 yyyyyyyyyyyyyyyyyyyy
[1] Accepted: seq = 7 ack = 5 checksum = 877b rrrrrrrrrrrrrrrrrrrr
[1] Accepted: seq = 0 ack = 5 checksum = 736e tttttttttttttttttttt
[0] Accepted: seq = 7 ack = 2 checksum = c3ba llllllllllllllllllll
[0] Accepted: seq = 0 ack = 2 checksum = b9b7 mmmmmmmmmmmmmmmmmmmm
[1] Send: seq = 5 ack = 0 checksum = 1e19 cccccccccccccccccccc
[0] Accepted: seq = 1 ack = 4 checksum = 918c qqqqqqqqqqqqqqqqqqqq
[0] Accepted: seq = 2 ack = 4 checksum = 7d77 ssssssssssssssssssss

完整的代码以及测试用例可见鄙人的GitHub