基础链路层协议(五):双向通信初步--单比特滑动窗口协议

December 8, 2014 at 1:47 am

接下来我们正式讨论双向通信。接下来的几节中,我们将从最简单的单比特滑动窗口协议开始,慢慢扩充、完善滑动窗口协议。 首先介绍一下滑动窗口协议中的一些基本概念。 在滑动窗口协议中,每一个发出去的帧都带有一个sequence number,事实上我们再协议3中已经使用了这个概念来记录编号。在滑动窗口协议中,通常sequence number是一个0到某个特定最值之间的一个数字,最值一般是,以方便sequence number正好存在n-bit中。滑动窗口协议最核心的地方在于任何时刻,发送端总是维护了它可以发送的帧的sequence number的集合,我们称这些帧落在sending window[发送窗口]中。与之对应地,接收端维护了它能接收的帧的集合,称为receiving window[接收窗口]。发送窗口和接收窗口的上界和下界不一定相同,甚至它们的大小也不一定相同。在一些协议中它们的大小是固定的,而在另一些中甚至随着帧的接收、发送窗口的大小也发生变化。 发送窗口中维护了那些未收到应答的帧的序号,这些帧可能已经发送,或者将要被发送,总之还没收到应答。当一个包从网络层过来时,它被赋予最小的可用的sequence number,由此将窗口的upper edge[上界]增加1;类似地,当一个应答过来时,窗口的lower edge[下界]增加1。通过这种方式,窗口总是维护着一个未应答帧的(序号的)列表。 上图给出了一个单窗口的3-bit sequence number的窗口运作示意图。 (a)状态是初态,此时发送端的上界和下界都指向区域0的左边,表示没有数据,下一个可用序号是0,我们记一个区域的左边界的编号为区域编号,所以此时下界和上界均为0;接收端的下界为0,上界为1,如灰色部分所示,接收方期待序号为0的数据。 (b)状态中,发送方从网络层得到了一个帧,于是标记为序号0,上界加1,变为1,指向区域1的左端。 (c)状态中,接收方成功接收到0号帧,于是上界和下界都增加1,期待序号为1的数据。此时发送方没有收到应答帧,所以状态不变。 (d)状态中,发送方成功收到了应答帧,于是下界加1,下一个可用序号为1。 […]

基础链路层协议(四):双向通信初步--piggybacking

December 3, 2014 at 1:05 pm

这一节开始我们讨论双向的通信机制。在具体讲协议之前,这一节讲一点轻松的东西,piggybacking机制。piggyback原意是背负式运输、负载运动,在链路层中,指的是应答帧随着数据帧一起发送的机制,这一节我们着重讨论这个机制的优缺点。 在实际的通信机制中,绝大部分通信都是双向的。回顾上一节中设计的协议三,它支持单向的有噪音通信,所以如果我们在两个通信端各运行一个协议三,实际上就实现了一个双向通信机制。相当于两台机器之间维护了两个连接,每个连接由向前的一个数据频道和一个向后的应答频道构成。显然这种设计使得应答频道的带宽几乎全部浪费。 一个更好的方式自然是使用一个协议、一个连接来实现双向通信,毕竟我们的协议二、三实际上已经存在双向通信,通常而言应答频道和数据频道在物理上带宽是一致的,所以要解决双向通信实际上只是协议设计的问题。最直接的方式就是混杂地传递信息,一个帧可能是一个数据帧,也可能是一个应答帧,我们通过给帧的head部分增设一个kind域来标明帧的性质即可。 在此基础上,为了更好地提高性能,当B收到A的一个数据帧时,并不急于发送应答帧,而是等到A有来自于网络层的要发给B的数据帧时,把应答信息捆绑在数据帧上传输给B,这种延迟发送应答帧而使得应答和数据得以捆绑在下一个帧中一起发送的机制就称为piggybacking。 这样做有显而易见的好处。一个应答信号实际上占用不了多少字节,但是一个完整的帧则必须包含头部、数据、校验和等,这是很大一部分开销。另一方面,piggybacking从总量上减少了帧的发送数量,这也减轻了接收者对帧的处理负担(在下一节介绍具体协议的时候我们可以看到,有些协议只需一个额外的比特位就可以piggyback一个应答信号)。 然而,piggybacking也为我们引入了新的问题。 接收方A的链路层需要等待自己的网络层多久呢?如果等得太久,在协议三中,就会导致发送方B重发数据帧,使得应答失去意义。如果接收方A可以预知它的网络层何时发送数据,那么它就可以决定是发送一个单一的应答帧还是等待数据来了piggyback过去。但是显然接收方A没有预知能力,所以我们不得不采取一些比较笨的方法,比如设定一个固定的等待时间,如果新的网络层的包很快地来了,我们就进行piggybacking,否则就发送单一的应答帧。 好了,这一节就简单的介绍一下piggybacking机制,下一节开始学习真正的双向通信协议,滑动窗口协议。