第三章数据链路层(2) 3.3数据链路协议 3.4协议描述与验证 3.5链路通信规程举例
第三章 数据链路层 (2) ◼ 3.3 数据链路协议 ◼ 3.4 协议描述与验证 ◼ 3.5 链路通信规程举例
可靠递交 差错帧: ■丢失帧:比如比较长的突发噪声造成帧完全 丢失 ■毁坏帧:帧到达接收者,但是帧的检验和不 对 ARQ: Automatic Repeat request 对收到的帧发送确认 ■如果超时并且没有收到确认,则重传帧
可靠递交 ◼ 差错帧: ◼ 丢失帧:比如比较长的突发噪声造成帧完全 丢失 ◼ 毁坏帧:帧到达接收者,但是帧的检验和不 对 ◼ ARQ:Automatic Repeat Request ◼ 对收到的帧发送确认 ◼ 如果超时并且没有收到确认,则重传帧
停等协议(1) 停等协议( Stop-and-Wait) 发送者在发送一个帧之后停下来,等待对方确认后继续发送 下一帧。如果确认在一段时间后无返回,发送者超时,重传 帧 Sender 简单版本(协议有问题!) while(1)i Receiver transmit(frame 1) receive(frame) transmit(ack) receive(ack) 3 catch(timeout)i continue H++; break
停等协议(1) ◼ 停等协议(Stop-and-Wait) ◼ 发送者在发送一个帧之后停下来,等待对方确认后继续发送 下一帧。如果确认在一段时间后无返回,发送者超时,重传 帧。 Sender ◼ 简单版本(协议有问题!) while (1) { transmit (frame i); try { receive (ack); } catch (timeout) { continue; } i++; break; } Receiver receive (frame); transmit (ack);
发送者 接收者 发送者 接收者 Frame Frame 超 超 时ACK 时 Frame ACK 发送者 接收者 发送者 接收者 Frame F 超 ACK 超 ACK 时 Frame Frame ACK ACK
发送者 超 时 接收者 Frame ACK 发送者 超 时 接收者 Frame ACK Frame ACK 发送者 超 时 接收者 Frame ACK Frame ACK 发送者 超 时 接收者 Frame Frame ACK
停等协议(2) 帧中包含顺序号(1比特)字段,确认也包含顺序号 发送方维护 next frame to send,接收方维护 frame_expected Sender Receiver while(1)i transmit (frame next frame to send frame_expected=0; try i while (1) while (1)i receive(ack n) receive(frame n) if(n=nextframe_to_send continue; ack(frame n) break if(n =frame_expected) i catch(timeout)i continue; continue? break next frame to send++ break: frame_expected +
停等协议(2) ◼ 帧中包含顺序号(1比特)字段,确认也包含顺序号 ◼ 发送方维护next_frame_to_send,接收方维护frame_expected Sender while (1) { transmit (frame next_frame_to_send); try { while (1) { receive (ack n); if (n != next_frame_to_send) continue; break; } } catch (timeout) { continue; } next_frame_to_send ++; break; } Receiver frame_expected = 0; while (1) { receive (frame n); ack (frame n); if (n != frame_expected) continue; break; } frame_expected ++;
停等协议(3) ■考虑停等因素的信道利用率 发送者 接收者 信道容量Bbps 2R 帧长Lbit L/B ACK L/B+2R L+2RB 往返传播延迟2R ■忽略ACK的开销 卫星信道:B=50kbps,2R=0.5sL=1kb U=1000(1000+25000)=1/26 Mbps/Mb/MB/FH Kbps/kb/KB 为了估算方便,而且在不影响结论的情况下,常常采用 Back-of- the- envelope calculation:假设每个字节10个比特,106=220
停等协议(3) ◼ 考虑停等因素的信道利用率: ◼ 信道容量B bps ◼ 帧长L bit ◼ 往返传播延迟2R ◼ 忽略ACK的开销 ◼ 卫星信道:B=50kbps,2R=0.5s, L=1kb U=1000/(1000+25000)=1/26 ◼ Mbps/Mb/MB和Kbps/Kb/KB 为了估算方便,而且在不影响结论的情况下,常常采用Back-ofthe-envelope calculation:假设每个字节10个比特,106=220 发送者 接收者 2R Frame ACK L/B L RB L L B R L B U 2 + 2 = + =
停等协议(4) ■捎带确认:大部分的通信是双向的,ACK帧通 常可由反向发送的数据帧一起捎带回来 ■图3.11给出了捎带确认的例子,B中给出了由 于双方不同步而导致每个数据帧都被重传一次 的情形。也可以采用单独发送ACK而不是捎带 确认的方法
停等协议(4) ◼ 捎带确认:大部分的通信是双向的,ACK帧通 常可由反向发送的数据帧一起捎带回来。 ◼ 图3.11给出了捎带确认的例子,B中给出了由 于双方不同步而导致每个数据帧都被重传一次 的情形。也可以采用单独发送ACK而不是捎带 确认的方法
停等协议(5) 个更加全面的分析:考虑ACK、重传、帧头开销 D为帧中有效数据长度,H为帧头长,L=H+D ACK长度为H 发送者 接收者 T表示等待ACK的超时间隔 Frame P1和P2分别表示数据帧和ACK丢失的概率T 每个数据帧需要进行重传的概率: P=1-(1-P,)(1-P) ■数据帧的平均传输次数为-n= 平均重传次数为 H/B P D P H+D 7)⊥,H+D 1-P B B+2R+
停等协议(5) ◼ 一个更加全面的分析:考虑ACK、重传、帧头开销 ◼ D为帧中有效数据长度,H为帧头长,L=H+D ◼ ACK长度为H ◼ T表示等待ACK的超时间隔 ◼ P1和P2分别表示数据帧和ACK丢失的概率 ◼ 每个数据帧需要进行重传的概率: P = 1–(1–P1)(1–P2) ◼ 数据帧的平均传输次数为 ◼ 平均重传次数为 = − − − = 1 1 1 1 (1 ) k k P kP P P P P − − = − 1 1 1 1 发送者 接收者 2R Frame ACK (L/B 超时 T 重传 H/B ( ) ( 2 ) 1 B H R B H D T B H D P P B D U + + + + + + − =
停等协议(6) 超时间隔T必须取得足够大, 即T≥H/B+2R H+D +1) +2R+-) B H+ D H+D+2RB+B(1-1=P2)°+D 第一个因子表示停等的因素,第二个表示出错重传的 因素,第三个为帧头的开销 假设信道上每比特的误码率为E,且各比特相互独立: 1-P=(1-E)0 P2=(1-E) 这样利用率为: D(1-E 2H+D U (H+D+BT
停等协议(6) ◼ 超时间隔T必须取得足够大, 即T≥H/B +2R ◼ 第一个因子表示停等的因素,第二个表示出错重传的 因素,第三个为帧头的开销 ◼ 假设信道上每比特的误码率为E,且各比特相互独立: ◼ 这样利用率为: H D D P P H D RB H H D B H R B H D P P B D U + • − − • + + + + = + + + + − = (1 )(1 ) 2 1)( 2 ) 1 ( 1 2 H H D P E P E 1 (1 ) 1 (1 ) 2 1 − = − − = − + ( ) (1 ) 2 H D BT D E U H D + + − = +
停等协议(7) 假设H、B、T、E不变,求最佳帧长度Dort 5 H+B(1-(H+BL)(-E)-n) 当E→0时有 √-41(H+B)h(1-E)-1~√4E(H+B) 从而E很小时: H+ BT Dopt E
停等协议(7) ◼ 假设H、B、T、E不变,求最佳帧长度Dopt ◼ 当E→0时有 ◼ 从而E很小时: UD ' = 0 ( 1 4 [( )ln(1 )] 1) 2 Dopt − + − − + = H BT E H BT 1− 4/[(H + BT)ln(1− E)] −1~ 4/[E(H + BT)] E H BT Dopt +