《高级计算机网络》由会员分享，可在线阅读，更多相关《高级计算机网络（97页珍藏版）》请在金锄头文库上搜索。
1、The Data Link LayerChapter 33.1 Data Link Layer Design IssuesServices Provided to the Network LayerFramingError ControlFlow ControlFunctions of the Data Link LayerProvide service interface to the network layerDealing with transmission errorsRegulating data flowSlow receivers not swamped by fast send
2、ersFunctions of the Data Link Layer (2)Relationship between packets and frames.Services Provided to Network Layer(a) Virtual communication. (b) Actual communication.Services Provided to Network LayerUnacknowledged connectionless serviceno logical connectionreal-time communications Acknowledged conne
3、ctionless serviceno logical connection, acknowledged each framewireless channelsServices Provided to Network LayerAcknowledged connection-oriented servicethe connection is establishedframes are transmittedthe connection is releasedServices Provided to Network Layer (2)Placement of the data link prot
4、ocol.FramingCharacter countFlag bytes with byte stuffingStarting and ending flags,with bit stuffingPhysical layer coding violationsFramingA character stream. (a) Without errors. (b) With one error.Framing (2)(a) A frame delimited by flag bytes. (b) Four examples of byte sequences before and after st
5、uffing.Framing (3)Bit stuffing (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in receivers memory after destuffing.Framing (4)局域网中采用曼彻斯特编码进行传输（IEEE 802.5令 牌环协议）。帧的起始定界符：J K 0 J K 0 0 0（二进制序列）帧的结束定界符：J K 1 J K 1 X XJ K 0 J K 0 0 0 J K 1 J K 1 3.2 Error
6、 Detection and CorrectionError-Correcting CodesError-Detecting CodesError-Correcting CodesA frame: m data bits + r check bits ,total length be n=m+r bitsCodeword: n bitsa Hamming code to correct burst errorsHamming distance:C1=10001001, C2=10110001, d(C1,C2)=3Hamming distance of the complete code: m
7、inimumError-Correcting Codes一种编码的检错和纠错能力取决于它的Hamming距离：(1) 能够检测出d位差错的编码，其编码的Hamming距离至少为d+1;(2) 能够纠正d位差错的编码，其编码的Hamming距离至少为2d+1;Error-Correcting Codes(3) 有m个信息位和r个检测位的编码，它能纠正所有单错，则(m + r +1)2r例：m = 4, r = 3 m = 7, r =4 m =8, r =4Error-Correcting CodesHamming码的纠错过程：1 k n 检测位在2i位上(i=0,1)k = 11 = 1 +
8、2 + 8“H”: 1001000 0 0 1 1 0 0 1 0 0 0 0 （奇校验）接收 0 0 1 1 0 0 1 0 0 0 1检测位 1: （奇数位）0 + 1 + 0 + 1 + 0 + 1 = 12：(2,3,6,7,10,11) 0 + 1 + 0 + 1 + 0 + 1 = 14: (4,5,6,7) 1 + 0 + 0 + 1 = 08: (8,9,10,11) 0 + 0 + 0 + 1 = 1出错位 k=1011Error-Correcting CodesUse of a Hamming code to correct burst errors.Error-Detec
9、ting Codes一种多项式编码：循环冗余码（CRC，Cyclic Redundancy Check）m位数据：am-1, am-2, . . . , a1, a0 (ai = 1/0)对应的多项式，称为信息多项式M(x):M(x)= am-1xm-1+ am-2xm-2+ . . . + a1 x+ a0产生CRC，找到一个生成多项式G(x)，阶数为rG(x)=xr+ . . . +1代码 c= am-1, am-2, . . . , a1, a0,br-1, br-2, . . . ,b0 (bi=1/0)对应的代码多项式C(x):C(x)= am-1xm+r-1+ am-2xm+r-2
10、+. . . + a1xr+1+ a0xr+ br-1xr-1+ br-2xr-2+ . . .+ b0Error-Detecting Codes如何找出C(x)：C(x) = xrM(x) + R(x), R(x)的阶 = r-1, 为xrM(x)/ G(x)的余数多项式。设接收多项式T(x):若T(x)/ G(x)的余数多项式为零，则T(x)是码多项式，视为无差错。Error-Detecting CodesCRC的一些性质：(1)G(x)=x16+x12+x5+1,则生成的CRC码可以检测出所有的单位错和双位错，所有奇数错。突发差错：一个长度为k的突发差错，其差错多项式E(x)为E(x)
11、= xi( xk-1+ . . . +1 )(2)若G(x)的阶为r，则生成的CRC码可以检测出所有长度等于或小于r位的突发差错。Error-Detecting Codes(3) 若G(x)的阶为r，则生成的CRC码不能检测出所有长度等于r+1位的突发差错的概率（2r-1）-1。（E(x)= G(x) 中间有r-1项，只有一个是G(x) ）(4) 若G(x)的阶为r，则生成的CRC码不能检测出所有长度大于r+1位的突发差错的概率（2r）-1。Error-Detecting CodesCalculation of the polynomial code checksum.3.3 Elementa
12、ry Data Link ProtocolsAn Unrestricted Simplex ProtocolA Simplex Stop-and-Wait ProtocolA Simplex Protocol for a Noisy ChannelElementary Data Link Protocols通信模型的约定： 物理层、数据链路层和网络层是各自独立的进程 主机A用可靠的、面向连接的服务向主机B发送长的数据流（待发的数据无限） 程序中有两个进程 to_physical_layer: 发送一帧 from_physical_layer:接收一帧 校验和的计算与填入由硬件实现 Elemen
13、tary Data Link Protocols 过程wait_for_event(&event), 接收一帧后：event=cksun_err , frame_arrival , timeout, network_layer_ready 定义了五种数据结构（用C语句描述）boolean, seq_nr, packet, frame_kind, frameseq_nr 取值0MaxSeq（常量由各协议定义）packet 长度固定为MAX_PKT字节frame 包含四个字段：kind, seq, ack, infoElementary Data Link Protocols其中kind：控制 ，
14、数据seq：序号 ack：确认 info：分组（数据帧）过程 to_network_layer, from_network_layer 超时控制：过程 start_timer, stop_timer 确认控制：过程 start_ack_timer, stop_ack_timer 宏inc将序号循环加1Protocol DefinitionsContinued Some definitions needed in the protocols to follow. These are located in the file protocol.h.Protocol Definitions (ctd.
15、)Some definitions needed in the protocols to follow. These are located in the file protocol.h.3.3.1 Unrestricted Simplex Protocol假设：信道无差错，单向传输，报文处理时间忽略不计，缓冲器空间无限大。协议1（乌托邦）两个过程：发送 接收 （无序号，无确认，只有info）详教材205页Unrestricted Simplex Protocol3.3.2 Simplex Stop-and-Wait Protocol去掉协议1的条件：收方能以无限快的速率处理外来数据主要问题：防止发方发送数据过快，使收方来不及处理收方：花费t执行from_physical_layer和 to_network_layer发方：平均速率小于每t秒一帧。（前一帧取出后，才可发下一帧）。 收方将收到的分组交给网络层后，回送给发方一个短帧（确认帧）协议2（停等协议）详教材207页与协议1的区别是在接收和发送过程中增加了一个等待过程 Simplex Stop-and- Wait Protocol3.3.3 A Simplex Protocol for a Noisy Channel帧可能出错或丢失，防止帧的重复接收问题： 主机
