《ch03-datalink》由会员分享，可在线阅读，更多相关《ch03-datalink（47页珍藏版）》请在金锄头文库上搜索。
1、3 The Data Link Layer,Highlights,Data Link Layer Design Issues FramingError Control & Flow ControlError Detection and Correction Error Correcting CodeError Detecting CodeSliding Window Protocols One-Bit Sliding Window ProtocolProtocol Using Go Back NUsing Selective RepeatExamples of Data Link Protoc
2、ols SLIPPPP,Data Link Layer Design Issues,Data Link Layer Design Issues,目标研究在直接的邻居(adjacent machines)之间的可靠和高效的通信算法Adjacent:通过通信信道连接的两台计算机，就好像是通过电线（Like a wire)连接一样,接收者会与发送者发送顺序完全相同的顺序接收比特流，不会出现乱序问题Data Link Layer Design Issues向网络层提供什么样的服务？成帧差错控制流量控制,成 帧,Character Count,A character stream. (a) Withou
3、t errors. (b) With one error.,字符记数法 Uses a field in the header to specify the number of characters in the frame (DEC:DDCMP),Byte Stuffing,(a) A frame delimited by flag bytes.(b) Four examples of byte sequences before and after stuffing.,字符添充法:Having each frame start and end with special bytes (IBM:B
4、ISYNC，PPP),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.,比特添充法: Starting and ending flags, with bit stuffing (Example: HDLC)帧边界字节 01111110 发送者检查发送的数据比特流，一旦遇到5个连续的1，就在后面插入一个0,Example with Possible Error
5、s (Bit Stuffing),Bit StuffingExample with possible errors,Physical Layer Coding Violations,Physical layer coding violations:物理层编码违例法 (IEEE:802.3),Manchester,差分Manchester,Error Control & Flow Control,差错控制,保证网络层的数据按照正确的顺序无差错的交付到接收方使用反馈机制硬件问题或线路问题导致帧完全丢失，接收一方不可能会有任何动作帧丢失和ACK丢失两种情况:发送方使用超时定时器管理定时器和帧编号，保
6、证数据以正确的顺序并且“完全一次”交给目的地的网络层,流量控制,发送者快，接收者处理慢的情况(比线路速度慢)常用的两种方法 Feedback-based flow control,接收方发送反馈信息给发送方（如：窗口方案，XON/XOFF方案)Rate-based flow control,限制发送者的发送速率（使得发送方不致于竭尽他所用传输线路的带宽),Error Detection and Correction,Error Correcting Code,汉明距离,汉明距离：对应比特位上相异的比特数目(10001001 and 10110001, Hamming distance = 3)
7、检出d比特错误： need a distance d+1 code 纠正d比特错误： need a distance 2d+1 code,Example of an Error-Correcting Code,Consider a code with only four valid codewords: 0000000000, 0000011111 1111100000, 1111111111This code has a distance 5, which means that it can correct 2 errors.If the codeword 0000000111 arrive
8、s, the receiver knows that the original must have been 0000011111If a triple error changes 0000000000 into 0000000111, the error will not be corrected properly,汉明编码,为修正单比特错误所需要的冗余位：m+r+1 2r m: 消息比特数, r :冗余位m个消息比特r个冗余位, 2m种有效消息， 2n种编码 n = m + r每个有效消息，有n个无效消息专属于该消息，汉明距离为1，才能纠正单比特错误 2m (1 + n) 2n (m +
9、r + 1) 2r. Example: m=7,r4,码字的比特位编号为1，2，3，其中位编号恰好等于2的幂的比特位(1, 2, 4, 8, etc.) 用作校验, 其余位(3, 5, 6, 7, 9, 10，etc.) 用作m位数据的编码 例如：m=7,r=4，编码数据 10010003=1+2， 5=1+4， 6=2+4， 7=1+2+4 , 9=1+8, 10=2+8, 11=1+2+8 1=35 79 112=3 67 10114= 5678= 91011,Bit number 1 2 3 4 5 6 7 8 9 10 11Data bit 0 0 1 1 0 0 1 0 0 0 0,
10、汉明编码,Hamming code,Use of a Hamming code to correct burst errors.,Error Detecting Code,Polynomial Code,Also known as CRC (Cyclic Redundancy Check)Treating bit strings as representations of polynomials with coefficients of 0 and 1A k-bit frame is regarded as the coefficient list for a polynomial with
11、k terms, ranging from xk-1 to x0: 110001= x5 + x4 + x0Polynomial arithmetic is done modulo 2, addition and subtraction are identical to XOR The algorithm for computing the checksum:Append r zero bits to the low-order end of the frameDivide the bit string corresponding to G(x), using modulo 2 divisio
12、nSubtract the remainder from the bit string using modulo 2 subtraction,Calculation of the CRC,Calculation of the polynomial code checksum.,Generator Polynomial,Certain polynomials have become international standards CRC-16 x16+x15+x2+1CRC-CCITT (HDLC)x16+x12+x5+1CRC-32 (IEEE802)x32+x26+x23+x22+x16+x
13、12+x11+x10+x8+x7+x5+x4+x2+x1+1,The Calculation of CRC,HardwareA simple shift register circuit can be constructed to compute and verify the checksumsSoftware,static u16 fcstab256 = 0x0000, 0x1189, 0x2312, 0x329b, 0x4624, 0x57ad, 0x6536, 0x74bf, 0x8c48, 0x9dc1, 0xaf5a, 0xbed3, 0xca6c, 0xdbe5, 0xd49d,
14、0xc514, 0xb1ab, 0xa022, 0x92b9, 0x8330, 0x7bc7, 0x6a4e, 0x58d5, 0x495c, 0x3de3, 0x2c6a, 0x1ef1, 0x0f78;u16 fcs16(u16 fcs, unsigned char *cp, int len) while (len-) fcs = (fcs 8) fcstab(fcs *cp+) ,Sliding Window Protocols,滑动窗口技术的主要目的,在有误码线路上进行无差错传输提高线路的利用率,搭载,Piggybacking数据帧到达后，接收方不立刻回送单独的控制帧，而是等待一段时间
15、在反向数据中搭载控制信息ACK is attached to the outgoing data frame (using the ack field in the frame header).,发送窗口&接收窗口,发送窗口Sender maintains a set of sequence numbers corresponding to frames it is permitted to send. These frames are said to fall within the sending window窗口左：已发送窗口中：正在发送（未收到对方确认）窗口右：未发送接收窗口 接收端允许收到的数据帧编号集合（接收窗口)窗口左：已收到的，收到后丢弃数据但回ACK窗口中：准备接收的，收到后保留有效数据并回ACK窗口右：拒收（收到后抛弃，也不回ACK),
