计算机网络和协议分析课件

Slide Title,Body Text,Second Level,Third Level,Fourth Level,Fifth Level,Sep10 CN,Weihong,Chen,Hunan City University,Advanced Computer Networks,计算机网络,Advanced Computer Networks计算机网,Review,Data link layer design issues,Service Provided to the network layer,Framing,Error-Correcting Codes,Error-Detecting Codes,2,ReviewData link layer design i,The Data Link Layer,Chapter 3,3,The Data Link LayerChapter 3,Topics,Error detection and correction,Hamming code,CRC(Cyclic Redundancy Check),4,TopicsError detection and corr,2.1 Error-Correcting Codes,2.Error Detection and Correction,101011,010101,111000,010010,101011,0,010101,1,111000,1,010010,0,010100,Even,check,?,A single,parity bit,appended to the data,the parity bit is chosen so that the number of 1 bits in the codeword is even(or odd),E.g.,1011010 1011010,0,2D parity check,code:Form the data to be transmitted into a matrix.Add a parity bit to each row and each column of the matrix.,5,2.1 Error-Correcting Codes2.E,Hamming distance,Rule:,To determine how many bits differ,just,exclusive OR,the two codewords and count the number of 1 bits in the result,for example:,Definition:,The number of bit positions in which two codewords differ is called,the Hamming distance,.,Significance:,if two codewords are a Hamming distance d apart,it will require d single-bit errors to convert one into the other.,6,Hamming distance Rule:To de,The bits that are powers of 2(1,2,4,8,16,etc.)are check bits.The,rest(3,5,6,7,9,etc.)are filled up with the m data bits.Each check bit forces the parity of some collection of bits,including itself,to be even(or odd).,Hamming code,Correct single errors!,7,The bits that are powers,Exercise,1.An 8-bit byte with binary value 10101111 is to be encoded using an even-parity Hamming code.What is the binary value after encoding?,2.A 12-bit Hamming code whose hexadecimal value is 0 xE4F arrives at a receiver.What was the original value in hexadecimal?Assume that not more than 1 bit is in error.,101001001111,The original 8-bit data value was 0 xAF.,8,Exercise1.An 8-bit byte with,Goal:,detect“errors”(e.g.,flipped bits)in transmitted frame(note:used at transport layer,only,),Sender,Receive,2.2 Error-Detecting Codes,9,Goal:detect“errors”(e.g.,f,Modulo 2 arithmetic,No carries for addition or borrows for subtraction,Both addition and subtraction are identical to exclusive OR,Long division is carried out the same way as it is in binary except that the subtraction is done modulo 2,as above.,10,Modulo 2 arithmeticNo carries,Generator Polynomial-G(x),The sender and receiver must agree upon a generator polynomial in advance,Both the high-and low-order bits of G(x)must be 1,To compute the,checksum,for some frame with,m,bits,corresponding to the polynomial M(x),the frame must be longer than G(x),11,Generator Polynomial-G(x)T,The idea of CRC,The idea is to,append a checksum to the end of the frame,in such a way that the polynomial represented by the checksummed frame is divisible by G(x).When the receiver gets the checksummed frame,it tries dividing it by G(x).If there is a remainder,there has been a transmission error.,12,The idea of CRC The id,view data bits,D,as a binary number,choose r+1 bit pattern(generator),G,goal:choose r CRC bits,R,such that,exactly divisible by G(modulo 2),receiver knows G,divides by G.If non-zero remainder:error detected!,can detect all burst errors less than r+1 bits,widely used in practice(ATM,HDLC),Cyclic Redundancy Check,13,view data bits,D,as a binary,R=,remainder ,D,.,2,r,G,Example1,Data Frame:101110000,Generator G(x)=x,3,+1,The transmitted Frame:101110000,011,14,R=remainder D.2r,Fig.2 Calculation of the polynomial code checksum,Fig.2 illustrates the calculation for a frame 1101011011 using the generator G(x)=x,4,+x+1.,Example2,The transmitted Frame:,15,Fig.2 Calculation of the polyn,Transmitting T(x),receiving T(x),Receiver computes E(x)=T(x)/G(x),Those errors that happen to correspond to polynomials containing G(x)as a factor will slip by;all other error will be caught.,16,Transmitting T(x),receiving T,What is the remainder obtained by dividing x,7,+x,5,+1 by the generator polynomial x,3,+x+1?,在数据传输过程中，若接收方收到发送方送来的信息为,10110011,，生成多项式为,G(x)=x,3,+x,2,+1,，接收方收到的数据是否正确？若想发送的一段信息为,10110011,，则在线路上传输的码字是怎样的？,Exercise,010,不正确,10110011,100,17,What is the remainder obtained,The popular G(x),CRC-4 X,4,+X+1,CRC-8 X,8,+X,5,+X,4,+1,CRC-12 X,12,+X,11,+X,3,+X+1,CRC-16 X,16,+X,15,+X,2,+1,CRC-16-CCITT X,16,+X,12,+X,5,+1,CRC32 X,32,+X,26,+X,23,+X,22,+X,16,+X,12,+X,11,+X,10,+X,8,+X,7,+X,5,+X,4,+X,2,+X+1,18,The popular G(x)CRC-4 X4+X+,冗余码的计算举例,现在,k,=6,M,=101001,。,设,n,=3,除数,P,=1101,，,被除数是,2,n,M,=101001000,。,模,2,运算的结果是：,商,Q,=110101,，,余数,R,=001,。,把余数,R,作为,冗余码,添加在数据,M,的后面发送出去。发送的数据是：,2,n,M,+,R,即：,101001001,，共,(,k,+,n,),位。,19,冗余码的计算举例 现在 k=6,M=101001。,接收端对收到的每一帧进行,CRC,检验,(1),若得出的余数,R,=0,，则判定这个帧没有差错，就,接受,(accept),。,(2),若余数,R,0,，则判定这个帧有差错，就,丢弃,。,但这种检测方法并不能确定究竟是哪一个或哪几个比特出现了差错。,只要经过严格的挑选，并使用位数足够多的除数,P,，那么出现检测不到的差错的概率就很小很小。,20,接收端对收到的每一帧进行 CRC 检验(1)若得出的余数,Summarize,Design issues,Service Provided to the network layer,Framing,Error-Correcting Codes,Error-Detecting Codes,21,SummarizeDesign issues21,Homework,Page243,2,3,5,14,15,22,Homework Page24322,Preparation,Elementary data link protocols,23,Preparation Elementary data li,差错的检测与控制,（,1,）差错检测,衡量通信线路传输质量的技术指标是,误码率,。,Pe=,错误接收的码元数,/,接收的总码元数,（,2,）几种冗余校验方法,垂直冗余校验,水平冗余校验,水平垂直冗余校验,循环冗余校验,24,差错的检测与控制（1）差错检测24,垂直奇偶校验,垂直奇偶校验又称纵向奇偶校验，它能检测出每列中所有奇数个错，但检测不出偶数个的错，如下图所示，因而对差错的漏检率接近,1/2,。,位,数字,0 1 2 3 4 5 6 7 8 9,C1,0 1 0 1 0 1 0 1 0 1,C2,0 0 1 1 0 0 1 1 0 0,C3,0 0 0 0 1 1 1 1 0 0,C4,0 0 0 0 0 0 0 0 1 1,C5,1 1 1 1 1 1 1 1 1 1,C6,1 1 1 1 1 1 1 1 1 1,C7,0 0 0 0 0 0 0 0 0 0,偶,C0,0 1 1 0 1 0 0 1 1 0,奇,1 0 0 1 0 1 1 0 0 1,垂直奇偶校验方式,25,垂直奇偶校验 垂直奇偶校验又称纵向奇偶校验，它能检,水平奇偶校验,水平奇偶校验又称横向奇偶校验，它不但能检测出各段同一位上的奇数个错，而且还能检测出突发长度,=p,的所有突发错误。其漏检率要比垂直奇偶校验方法低，但实现水平奇偶校验时，一定要使用数据缓冲器。,位,数字,0 1 2 3 4 5 6 7 8 9,偶校验,C1,0 1 0 1 0 1 0 1 0 1,1,C2,0 0 1 1 0 0 1 1 0 0,0,C3,0 0 0 0 1 1 1 1 0 0,0,C4,0 0 0 0 0 0 0 0 1 1,0,C5,1 1 1 1 1 1 1 1 1 1,1,C6,1 1 1 1 1 1 1 1 1 1,1,C7,0 0 0 0 0 0 0 0 0 0,0,水平奇偶校验方式,26,水平奇偶校验 水平奇偶校验又称横向奇偶校验，它不但,水平垂直校验,水平垂直校验,(LRC),又叫报文校验、方块校验。,将若干水平奇偶校验码排成若干行，然后对每列进行奇偶校验，放在最后一行，该检验字符的编码方法是使每一位纵向代码中,1,的个数成为奇数,(,或偶数,),。传输时按照列顺序进行传输，在一批字符传送之后，另外增加一个检验字符，在接收端又按照行的顺序检验是否存在差错。,图,2-25,水平垂直奇偶校验方式,Back,27,水平垂直校验 水平垂直校验(LRC)又叫报文校验、,28,28,29,29,30,30,31,31,Back,32,Back32,Thanks!,33,Thanks!33,