基础链路层协议(六):双向通信初步--使用Go-Back-N的滑动窗口协议

January 25, 2015 at 12:03 am

直到现在为止的讨论中,我们都忽略了一个帧到达接收端的时间以及一个应答帧返回发送端的时间。现实情况中,这些时间往往是不能忽视的。我们通过一个简单的例子说明这一点。考虑一个50kbps的卫星信道,它带有250ms的传播延迟(propagation delay)。为了方便讨论,这里先介绍一下传输延迟的具体定义。传输延迟指的是(光或其它波)信号从发送端到达接收端所需的时间,它的计算公式为d/s,其中d是发送端到接收端的距离,s是信号在介质中的传播速度。正如打电话有时会发生的延迟一样,不论数据量多少,延迟的量都是固定的,和数据量本身无关。假设我们再这样一个信道上发送一个1000比特的帧,那么受到信道带宽的限制,这个帧完全发送出去(而不是到达)需要1000 / 25000 = 20ms,这个延迟称为传输延迟(transmission),类比于打电话的例子,这相当于人讲话时的速度。说完一句话本身需要20ms,而这整句话到达对方那里还要延迟250ms,所以对方听到整句话需要270ms(当然这句话的第一个字在第250ms时就开始听到了)。于是第270ms时整个帧才到达接收端,那么极限情况下,发送端则要在270ms+250ms=520ms时收到应答信号(也就是直到这个时候才听到对方回的话)。那么,即使在最好的情况下,实际上发送者在520ms中仅发挥了20ms的作用,20ms/520ms = 96%,或者说只有4%的带宽得到了利用。 审视一下就会发现,出现上述结果的一个主要原因是我们规定在接收到应答帧后再发送第二个帧。如果我们不这样规定,而是允许发送w个帧之后再等待应答帧,就可以解决这个问题(对应打电话的例子,就是我们先说好几句话,而不是先等对方答前一句话,当然这在打电话中有些奇怪)。只要w足够大,滑动窗口就不会满,数据就能持续地被发送。 我们通过bandwith-delay product来计算w,指的是带宽和传播延迟的乘积。我们把bandwith-delay product除以每一帧的比特数记为BD,那么我们取w=2BD+1。这么取的原因是,我们希望当我们的w个帧完全发送出去时,正好赶上对方对第一个帧的应答,这样我们就可以继续发新的帧了(对应打电话的例子,我们希望我们说完所有n句话的时候,正好听到对方对于第一句话的应答)。我们以刚才的数据具体为例:容易计算得到w=26.那么当我们发送出所有的帧后,正好是520ms,对方在第250ms时开始接收到第一个帧,在第270ms时接收完成,在第520ms时应答帧到达发送端,于是可以发送新的帧了。此后,每20ms就会有一个应答帧到来,正值把前一个帧发送出去,于是又可以发送新帧。所以我们一共需要大小为26的窗口就够了。如果窗口的大小不够大,就容易发生窗口满了然后堵塞的现象,我们有以下公式来衡量: 这是上界,我们甚至没有考虑处理帧所要花的时间以及应答帧的长度,当然这些时间是比较短的。上面的公式告诉我们,如果传播延迟很大,我们所需要的窗口就要很大。如果我们采用以前的策略,也就是说w=1,那么即使延迟只是一个帧大小的量,效率也会远小于50%。这种让很多帧发送出去但还没处于应答的策略称为流水线(pipelining)。 当然之前的讨论是非常理想的。第一个明显的问题是,这么多的帧同时发送,如果中途某几个帧丢失了怎么办呢,在接收方发现出错之前,后续的帧慢慢地来到了。对于接收到错误帧的接收方,如何处理后续到来的正确帧呢?注意无论如何,接收方发送给网络层的帧必须是按顺序的。在流水线策略中,有两种基础的方法来解决这种错误问题。今天要介绍的这种,称为回退N(go-back-n),它的实现较为简单,策略就是舍弃接下来的所有帧,不对那些帧发送应答。这种策略实际上就对应了接收窗口的大小是1,换句话说,如果来的帧不是接收窗口所需要的下一个帧,就统统舍弃。如果在超时之前发送者的发送窗口被填满了,流水线上就慢慢没有作业了,最终发送者会因为超时而重发之前的帧。当然,这个策略在错误率较高的情况下会浪费大量带宽。   基于上述讨论,我们可以设计一个go_back_n的协议了,需要改动的地方较多,先放出代码,再一一分析。 static bool between(seq_nr a, seq_nr […]

C/C++ enum使用小tip

January 17, 2015 at 11:36 pm

最近打算把这些小tip也放到这里来,也算是填充一下什么都没有的blog。 对于不显式赋值的enum成员,可以在结尾加上一个MAXIMUM_BLABLA,这样以后如果有某种建立关于每一个enum成员的数组时,就可以使用MAXIMUM_BLABLA作为enum成员的成员数来使用,一旦需要改动enum的成员,只要使用这个值,其它地方的代码就都不需要改了。 希望以后有用到这个tip的时候。 enum WEEK{ MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY, MAXIMUM_DAYS }; TASK daily_task[MAXIMUM_DAYS];