第5讲数据链路层ppt课件

1、河海大学电子信息工程系专业课程河海大学电子信息工程系专业课程结点结点帧帧q早期的数据通讯协议曾叫作通讯规程(procedure)。因此在数据链路层，规程和协议是同义语。局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3网局域网主机 H1 向 H2 发送数据链路层运用层运输层网络层物理层链路层运用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动局域网广域网主机 H1主机 H2路由器 R1路由器 R2路由器 R3网局域网主机 H1 向 H2 发送数据链路层运用层运输层网络层物理层链路层运用层运输层网络层物理层链路

2、层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层察看帧的流动物理层物理层数据链路层数据链路层网络层网络层传输层传输层运用层运用层比特流比特流物理层物理层数据链路层数据链路层网络层网络层保证数据流的顺序保证数据流的顺序传输层传输层运用层运用层源源宿宿控制字符传输错误控制字符传输错误5 1 2 3 4 5 0 1 2 3 8 0 1 2 3 4 5 6 5 0 1 2 3 5 1 2 3 4 7 0 1 2 3 8 0 1 2 3 4 5 6 5 0 1 2 3 帧头：阐明帧的字符数帧头：阐明帧的字符数出现过失带来的问题出现过失带来的问题 无法确定下一帧的帧头位

3、置无法确定下一帧的帧头位置 无法确定重传帧的帧头位置无法确定重传帧的帧头位置待发送数据待发送数据接纳到有接纳到有过失数据过失数据 n待发送数据待发送数据帧头帧头帧尾帧尾内容与帧标识符一样内容与帧标识符一样DLESTXADLEBDLEETXASCII字符字符内容为内容为“DLE填充填充“DLEDLESTXADLEBDLEETXDLESTXADLEDLEBDLEETXDLE321ASCII字符字符保管内容保管内容“DLE丢掉被填充的丢掉被填充的“DLEDLESTXADLEBDLEETXDLESTXADLEDLEBDLEETXDLE321帧头帧头帧尾帧尾在在L2插入插入/去除填充位去除填充位“00

4、1 1 1 1 1 1 0 0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 0m位位r位位n位码字位码字 n = m + r 数据位数据位冗余校验位冗余校验位码位一样码位一样码位不同码位不同码距码距 3数据位数据位数据位数据位检验位检验位检验位检验位传输过失传输过失传输过失传输过失传输过失传输过失纠错码的才干1纠错码的才干纠错码的才干Hamming间隔为间隔为2d+1的纠错编码，只能纠正的纠错编码，只能纠正d位数据错误。位数据错误。判别：出现判别：出现d位错误的概率大于位错误的概率大于d+1位错误。位错误。纠错码的功能纠错码的功能在接纳方发现并纠正过失数

5、据帧。在接纳方发现并纠正过失数据帧。3位传输过失位传输过失2位传输过失位传输过失 1101010110 Q 商商 除数除数 P 110101 101000110100000 2nM 被除数被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数余数发送数据：发送数据： 1010001101 01110 11010 10110 除数除数 P 110101 1010001101 01110 接纳接纳 110101 111011 110101 111010 110101 11

6、111 0 11010 1 101 111 110 101 11 0101 11 0101 0 00000 0 00000 0 余数余数结论：传输无过失结论：传输无过失 11010 10110 除数除数 P 110101 1010001101 11101 接纳接纳 110101 111011 110101 111010 110101 11111 1 11010 1 101 011 110 101 11 1100 11 0101 10011 余数余数结论：传输有过失结论：传输有过失ABDATADATADATADATA送主机 B送主机 B送主机 B送主机 B时间不需求流量控制ABDATA送主机 B

7、DATA送主机 B需求流量控制物理层物理层数据链路层数据链路层网络层网络层比特流比特流物理层物理层数据链路层数据链路层网络层网络层发送方发送方A接纳方接纳方Bfrom_network_layerfrom_physical_layerto_network_layerto_physical_layerframe物理传输通道物理传输通道packet arrivalframe arrival类类型型kind序序号号seq确确认认ack数数据据info帧头帧头来自发送方网络层来自发送方网络层from_network_layer帧帧frame: s区分数据帧区分数据帧/控制帧控制帧分组分组packetpa

8、cket_arrivalfrom_network-layer(&buffer)to_physical-layer(&s)s = bufferpacketpacketpacketheadbuffer&s来自网络层来自网络层送往物理层送往物理层yesframe_arrivalto_network-layer(&r)from_physical-layer(&r)packetpackethead&r送往网络层送往网络层来自物理层来自物理层yeswait_for_event(&event)循环等待循环等待no&r物理层物理层数据链路层数据链

9、路层网络层网络层比特流比特流物理层物理层数据链路层数据链路层网络层网络层发送方发送方A接纳方接纳方Bframe单工物理信道单工物理信道packet_ arrivalframe_arrival假设假设B的接纳才干小于的接纳才干小于A的发送才干怎样办？的发送才干怎样办？packet_arrivalfrom_network-layer(&buffer)to_physical-layer(&s)s = bufferpacketpacketpacketheadbuffer&s来自网络层来自网络层送往物理层送往物理层yeswait_for_event(&event)fram

10、e_arrival来自物理层来自物理层yes接纳方确实认帧到达接纳方确实认帧到达headframe_arrivalto_network-layer(&r)from_physical-layer(&r)packetpackethead&r送往网络层送往网络层来自物理层来自物理层yeswait_for_event(&event)循环等待循环等待no&rto_physical-layer(&s)head&s确认帧确认帧送往物理层送往物理层物理层物理层数据链路层数据链路层网络层网络层比特流比特流物理层物理层数据链路层数据链路层网络层网络层发送方发

11、送方A接纳方接纳方Bframe半双工物理信道半双工物理信道packet_ arrivalframe_arrival假设帧在传输中被损坏假设帧在传输中被损坏或丧失怎样办？或丧失怎样办？head收到确认方可发送下一帧收到确认方可发送下一帧时间ABDATA0送主机ACKDATA1送主机ACK(a) 正常情况ABDATA0DATA0送主机ACK(c) 数据帧丧失重传tout丢失 ！ABDATA0送主机ACKDATA0丢弃ACK(d) 确认帧丧失重传tout 丢失 ！ABDATA0NAKDATA0送主机ACK(b) 数据帧出错重传出错四种情况四种情况发送帧发送帧m 丧失丧失超时重传超时重传超时重传超时重

12、传期望接纳期望接纳seq=0期望接纳期望接纳seq=0接纳帧接纳帧m，回送确认，回送确认期望接纳期望接纳seq=1确认帧确认帧m收到收到帧帧m, seq=0帧帧m, seq=0帧帧m, seq=0期望接纳期望接纳seq=1接纳帧接纳帧m的的seq=0，丢弃，丢弃收到确认收到确认发送帧发送帧 m+1期望接纳期望接纳seq=1接纳帧接纳帧m+1，回送确认，回送确认期望接纳期望接纳seq=0确认帧确认帧m+1收到收到收到确认收到确认发送帧发送帧 m+2确认帧确认帧m收到收到帧帧m+1, seq=1ABDATADATAACK传播时延 tp处置时间 tpr确认帧发送时间 ta传播时延 tp处置时间 tp

13、rtT时间两个胜利发送的数据帧之间的最小时间间隔数据帧的发送时间tf设置的重传时间toutDATA0DATA1DATA2DATA3DATA4DATA5重传 DATA2重传 DATA3ACK1ACK2ACK1 确认 DATA0ACK2 确认 DATA1DATA2 出错，丢弃DATA3 不按序，丢弃，重传 ACK2DATA4 不按序，丢弃，重传 ACK2DATA5 不按序，丢弃，重传 ACK2ACK3ACK3 确认 DATA2ACK4 确认 DATA3ACK4重传 DATA5重传 DATA4超时重传时间ABtout送交主机送交主机?ACK2ACK2ACK2packet_arrivalfrom_ne

14、twork-layer(&buffer)to_physical-layer(&s)s = buffer来自网络层来自网络层送往物理层送往物理层yesframe_arrivalto_network-layer(&r)from_physical-layer(&r)送往网络层送往网络层来自物理层来自物理层yeswait_for_event(&event)循环等待循环等待no发送帧发送帧接纳帧接纳帧packet_arrivalfrom_network-layer(&buffer)to_physical-layer(&s)s = buffer来自网

15、络层来自网络层送往物理层送往物理层yesframe_arrivalto_network-layer(&r)from_physical-layer(&r)送往网络层送往网络层来自物理层来自物理层yeswait_for_event(&event)循环等待循环等待no发送帧发送帧接纳帧接纳帧A sends toBA gets from B类型类型序列号序列号确认号确认号数据数据dataseq fromAack toBpacket from A L3收到确认帧后向后收到确认帧后向后滑动，至窗口满。滑动，至窗口满。顺序接纳来自网络顺序接纳来自网络层的分组，成帧层的分组，成帧赋予序

16、列赋予序列号，发送号，发送并保管最并保管最多多W个待个待确认帧。确认帧。接纳窗口满，落在窗接纳窗口满，落在窗口外的帧被丢弃。口外的帧被丢弃。接纳来自物理层的帧接纳来自物理层的帧对进入窗口的帧对进入窗口的帧顺序提交网络层顺序提交网络层，产生确认。，产生确认。接纳窗口向后滑动，最接纳窗口向后滑动，最多保管待上交帧多保管待上交帧W个。个。W接接收收缓缓冲冲区区seq发发送送缓缓冲冲区区seqseq，ack，data A B(0, 1, A0)(0, 1, A0)(0, 0, B0)(0, 0, B0)(1, 0, A1)(1, 0, A1)(1, 1, B1)(1, 1, B1)(0, 1, A2)

17、(0, 1, A2)(0, 0, B2)(0, 0, B2)(1, 0, A3)(1, 0, A3)(1, 1, B3) A B 期望期望 seqB=0 (0, 1, A0) 期望期望 seqA=0 (0, 1, A0) * 交网络层交网络层 (0, 0, B0) 期望期望 seqA=1 期望期望 acqA=0 seqO OacqO O (0, 0, B0) 期望期望 seqA=1 seqP PacqP P (0, 0, B0)* 期望期望 seqB=1 (1, 0, A1) (0, 1, A0) seqO OacqO O (0, 0, B0) 期望期望 seqA=1 seqO OacqO O

18、 (0, 0,B0) 期望期望 seqB=1 (1, 0, A1) (1, 0, A1)* seqP PacqP P (1, 1, B 1) 期望期望 seqA=0 超时重传超时重传 (0, 1, A0) 超时重传超时重传 (0, 1, A0) (0, 1, A0) A B 期望期望(0,0) (0, 1, A0) (0, 1, B0) 期望期望(0,0) (0, 1, A0)* seqP PackO O (0, 0, B0) 期望期望(1,0) seqP PackO O (0, 1, B0)*期望期望(1,0) (0, 0, A0) 丢弃丢弃 (0, 0, B0) 期望期望(1,1) (1,

19、 0, A1) (0, 0, A0) 丢弃丢弃 (1, 0, B1) 期望期望(1,1) (1, 0, A1)* seqP PackO O (1, 1, B1) 期望期望(0,1) seqP PackO O (1, 0, B1)* 期望期望(0,1) (1, 1, A1) 丢弃丢弃 (1, 1, B1) 期望期望(0,0) (0, 1, A2) (1, 1, A1) 丢弃丢弃 (0, 1, B2) 期望期望(0,0) (0, 1, A2) seqP PackO O (0, 0, B2) 期望期望(1,0) 发送方发送方接纳方接纳方TfRTf + R Tf + RTf发送方发送方接纳方接纳方21

20、n0 1 E D D D D D D 2 3 4 5 6 7 8 出错出错丢弃丢弃超时间隔超时间隔确认确认发送发送接纳重传接纳重传重传重传0 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 90123456确认确认发送发送重发重发发送方缓冲区存放有序列编号、曾经发送方缓冲区存放有序列编号、曾经发送、等待确认的帧。发送、等待确认的帧。Seq = 0 Seq = 1 012345678234567891011019确认确认发送发送重发重发Ack = 7 Ack = 0 Ack = 1 正确接纳的帧顺序交网络层，发送确认：正确接纳的帧顺序交网络层，发送确认：初始初始ack=1，期望接纳，

21、期望接纳seq0；收到收到seq0和和seq1，发送，发送ack0和和ack1，等待接纳，等待接纳seq2。01234567823456789101101确认确认发送发送重发重发收到确认帧后滑动发送窗口：收到确认帧后滑动发送窗口：收到收到ack0和和ack1，待确认帧，待确认帧seq0和和seq1移出。移出。Seq = 0 Seq = 1 Seq = 2 Seq = 3 Seq = 4 Ack =7 Ack = 0 Ack = 1 01234567823456789101101ED9确认确认发送发送重发重发帧帧seq2丧失，收到帧丧失，收到帧seq3：期望期望seq2，收到，收到seq3，丢弃

22、；，丢弃；发送发送ack1，继续期望，继续期望seq2。Ack = 7 Ack = 0 Ack = 1 Ack = 1 01234567823456789101101EDDDDD确认确认发送发送重发重发Ack = 7 Ack = 0 Ack = 1 Ack = 1 Ack = 1 Ack = 1 Ack = 1 Ack = 1 帧帧seq2超时时间到，根据确认值为超时时间到，根据确认值为ack=1，延续重传从帧，延续重传从帧seq2开场的开场的缓冲区中的待确认帧。缓冲区中的待确认帧。Seq = 0 Seq = 1 Seq = 2 Seq = 3 Seq = 4 Seq = 5 Seq = 6

23、Seq = 7 Seq = 0 01234567823456789101101EDDDDDD2确认确认发送发送Ack = 7 Ack = 0 Ack = 1 Ack = 1 Ack = 1 Ack = 1 Ack = 1 Ack = 1 Ack = 1 Ack = 2 重发重发正确接纳期望帧正确接纳期望帧seq = 2，上交网络，上交网络层，回送确认层，回送确认ack2，期望帧，期望帧seq3。Seq = 0 0 Seq = 1 1 Seq = 2 2 Seq = 3 3 Ack = 7 Seq = 4 4 0 Ack = 0 Seq = 5 5 1 Ack = 1 Seq = 6 6 2 A

24、ck = 2 Seq = 7 7 3 Ack = 3 Seq = 0 8 4 Ack = 4 Seq = 1 9 5 Ack = 5 Seq = 2 10 6 Ack = 6 Seq = 3 11 7 Ack = 7 Seq = 4 12 8 Ack = 0 Seq = 5 13 9 Ack = 1 Seq = 6 14 10 Ack = 2 Seq = 7 15 11 Ack = 3 16 12 Ack = 4 17 13 Ack = 5 18 14 Ack = 6 19 15 Ack = 7 延续发送帧延续发送帧815延续发送帧延续发送帧07Seq = 00Seq = 11Seq = 22

25、Seq = 33Ack = 7Seq = 440Ack = 0Seq = 551Ack = 1Seq = 662Ack = 2Seq = 773Ack = 3Seq = 084Ack = 4Seq = 195Ack = 5Seq = 2106Ack = 6Seq = 3117Ack = 7Seq = 412Seq = 513Seq = 614Seq = 715发送方有能够不立刻确认接纳帧，夹带确发送方有能够不立刻确认接纳帧，夹带确认认ack=n，意味着，意味着n-1, n-2也被确认。也被确认。收到收到ack=7，本是帧，本是帧7确实认，被断定确实认，被断定为帧为帧15确实认，误以为第二窗口发

26、送确实认，误以为第二窗口发送胜利，开场发送后续帧。胜利，开场发送后续帧。延续发送帧延续发送帧06延续发送帧延续发送帧713Seq = 00Seq = 11Seq = 22Seq = 33Ack = 7Seq = 440Ack = 0Seq = 551Ack = 1Seq = 662Ack = 2Seq = 773Ack = 3Seq = 084Ack = 4Seq = 195Ack = 5Seq = 2106Ack = 6Seq = 311Seq = 412Seq = 51314收到收到ack=6，从，从seq=7开场重传开场重传第二窗口的数据帧，不会误以第二窗口的数据帧，不会误以为第二窗口发

27、送胜利。为第二窗口发送胜利。12n0 1 2 3 4 5 6 7 8 2 0 1 E 3 4 5 6 7 8 2 出错出错接纳缓存接纳缓存超时间隔超时间隔确认确认发送发送接纳重传接纳重传排序上交排序上交重传重传重传重传012345678291011121314151617确认确认发送发送接接 收收 方方 缓缓 冲冲 区区23D 34D 45D 56D 67D 789接纳方期望接纳接纳方期望接纳seq2，缓存其后的正确帧。缓存其后的正确帧。发发 送送 方方 缓缓 冲冲 区区Seq = 2, D 2Seq = 3, D 3Seq = 4, D 4Seq = 5, D 5Seq = 6, D 6Se

28、q = 7, D 7Seq = 8, D 801234567829101112131415161701E34567829101112131415确认确认发送发送发发 送送 方方 缓缓 冲冲 区区Seq = 2, D 2Seq = 3, D 3Seq = 4, D 4Seq = 5, D 5Seq = 6, D 6Seq = 7, D 7Seq = 8, D 8接接 收收 方方 缓缓 冲冲 区区23D 34D 45D 56D 67D 78D 890 1 2 3 4 5 6 7 8 2 01E34567829101112131415确认确认发送发送将帧将帧seq2和接纳方缓冲区中的帧正确和接纳方缓

29、冲区中的帧正确排序，提交网络层，回送排序，提交网络层，回送ack=8，滑，滑动接纳窗口。动接纳窗口。接接 收收 方方 缓缓 冲冲 区区9101112131501接接收收方方01234567891011121314发发送送方方012345678910111213141516171819发送方缓冲区发送方缓冲区01234567891011121314接接收收方方缓缓冲冲区区01234567891011121314Ack=01234567891011121314接接收收方方01234567891011121314发发送送方方01234567891011121314Seq=01234567891011

30、121314发送方缓冲区发送方缓冲区0D01D12D23D34D45D56D67D78D89D910D1011D1112D1213D1314D14接接收收方方缓缓冲冲区区15012345678910111213发送帧发送帧014等待确认。等待确认。帧帧014上交网络层，回送上交网络层，回送确认，接纳窗口滑动。确认，接纳窗口滑动。帧帧014确实认丧失！确实认丧失！帧帧0超时，被重传。超时，被重传。重传帧重传帧0正确到达，正确到达，seq=0在可接纳范围，在可接纳范围，被接纳在缓冲区内，回送被接纳在缓冲区内，回送ack=14。发送方缓冲区发送方缓冲区0D01D12D23D34D45D56D67D78D89D910D1011D1112D1213D1314D14接接收收方方缓缓冲冲区区150D012345678910111213Ack=15接接收收方方15发发送送方方151617181920212223242526272829Seq=1501234567891011