计算机网络(数据链路层)

1第3章数据链路层张瑞[e-mail]23.1数据链路层的基本概念3.2组帧3.3差错控制3.4点对点协议PPP3.5使用广播信道的数据链路层3.6以太网的MAC层3.7扩展的以太网3.8虚拟局域网第3章数据链路层3链路(link)一条无源的点到点的物理线路段，中间没有任何其他的交换结点数据链路(datalink)除了物理线路外，还必须有通信协议来控制这些数据的传输。若把实现这些协议的硬件和软件加到链路上，就构成了数据链路3.1数据链路层的基本概念4局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2从层次上来看数据的流动数据链路层的简化模型5局域网广域网主机H1主机H2路由器R1路由器R2路由器R3电话网局域网主机H1向H2发送数据链路层应用层运输层网络层物理层链路层应用层运输层网络层物理层链路层网络层物理层链路层网络层物理层链路层网络层物理层R1R2R3H1H2仅从数据链路层观察帧的流动数据链路层的简化模型（续）6两个主机通信时，应用进程将数据从应用层往下传，经过物理层到达传输线路，到达接收端后，通信线路将数据传到物理层，最后由应用层交给应用进程。为了分析链路层协议，采用简化的链路层模型数据链路层以上的各层用一个主机代替；物理层和通信线路等效成一条简单数据链路；数据链路层的简化模型7数据链路层主机A缓存主机B数据链路AP2AP1缓存发送方接收方帧高层帧数据链路层的简化模型89讨论链路层时，常常在两个对等的数据链路层之间画出一个数字管道，而在这条数字管道上传输的数据单位是帧。物理层间传输的是比特流，物理媒体上传送的是电或光信号，而在链路层上传输的数据帧。结点结点帧帧数据链路层像个数字管道10基本功能向网络层提供可靠的、透明的数据传输服务，将源节点的网络层数据可靠地传送到相邻节点的网络层主要功能描述链路管理封装成帧流量控制差错控制将数据和控制信息区分开透明传输寻址数据链路的建立、维持和释放两结点通信前要交换一些信息，称为建立数据连接，然后传输数据数据链路层，数据的传送以帧为单位帧定界(帧同步)是指接收方能从收到的比特流中区分一个帧的开始和结束的地方发送方发送数据的速率必须使接收方能来得及接收纠错：通过编码技术，接收方自动将差错改正过来检错：检测出帧有错误，要么忽略或重传数据和控制信息在同一个帧中，收方将其区分开不管所传数据的比特组合，都能在链路上传送；若所传的数据的比特片段与某一个控制信息相同，要有可靠机制，保证收方能正确识别每一帧都能送到正确的目的地；收方也能知道发送方的地址数据链路层的主要功能113.1数据链路层的基本概念3.2组帧3.3差错控制3.4点对点协议PPP3.5使用广播信道的数据链路层3.6以太网的MAC层3.7扩展的以太网3.8虚拟局域网第3章数据链路层12组帧(framing)就是在一段数据的前后分别添加首部和尾部，这样就构成了一个帧。目的：使接收方能准确识别帧的边界首部和尾部的一个重要作用就是进行帧定界≤MTU数据链路层的帧长3.2组帧13帧定界（帧同步）的方法1、字节计数法2、使用字符填充的首尾定界法3、使用比特填充的首尾定界法*4、违法编码法14思想在帧头设置一个长度域，放置该帧的字节数，当收方收到帧后，通过帧的长度，确定帧的开始。问题当帧的长度域出错，帧同步完全丢失；该方法很少单独使用。1、字节计数法15字节计数法举例16思想使用特殊的ASCII字符（不可打印的控制字符）作为帧的起始和终止定界符。例如：使用SOH作为开始符，EOT作为结束符。问题：数据传输不透明当数据中出现定界符(SOH或EOT)时，如何加以区分是数据还是定界符？解决：字符填充发送端的数据链路层在数据中出现控制字符“SOH”或“EOT”的前面插入一个转义字符“ESC”(其十六进制编码是1B)。接收端的数据链路层在将数据送往网络层之前删除插入的转义字符。2、字符填充法17缺点：使用字符来控制帧的传输，数据传输的单位是字符(8bit的ASCII)，帧的长度是8的倍数；传输任意长度的二进制比特带来不便。字符填充法举例SOHSOHEOTSOHESCESCEOTESCSOHESCESCESCSOH原始数据EOTEOT经过字节填充后发送的数据字节填充字节填充字节填充字节填充发送在前帧开始符帧结束符SOH如果转义字符也出现数据当中，那么应在转义字符前面插入一个转义字符。当接收端收到连续的两个转义字符时，就删除其中前面的一个。18思想使用一个特殊的比特模式01111110作为帧的起始和结束标志。发送方边发送边检查数据，每连续发送5个“1”后在后面自动插入一个“0”。这样数据中只会连续出现5个“1”，而不会出现定界符。接收方在收到5个连续的“1”后将后面的“0”删掉而恢复出原始数据。好处数据传输的基本单位是比特而不是字符，可用来传输任意长度的二进制比特串，通用性强。3、比特填充法19零比特的填充与删除01001111110001010数据中某一段比特组合恰好出现和定界符一样的情况会被误认为是定界符发送端在5个连1之后填入0比特再发送出去填入0比特010011111010001010在接收端将5个连1之后的0比特删除，恢复原样在此位置删除填入的0比特01001111101000101020比特填充法举例21前提物理介质上使用的信号编码有冗余码字时，使用这些冗余的码字来作为帧的定界。举例如曼彻斯特编码或差分曼彻斯特编码中，有效电平是“低－高”或“高－低”，而“低－低”和“高－高”电平没有定义，这种违法编码可以作为帧的边界。4、违法编码法223.1数据链路层的基本概念3.2组帧3.3差错控制3.4点对点协议PPP3.5使用广播信道的数据链路层3.6以太网的MAC层3.7扩展的以太网3.8虚拟局域网第3章数据链路层23差错控制技术：发现差错如何处理？前向纠错自动重发请求如果发送的数据丢失，那么接收端是不可能进行确认的，怎么办呢？差错编码技术：如何发现差错？检错码（奇偶校验码、CRC）纠错码（海明码）由接收方来检查并纠正错误不能纠正，接收方反馈。若有错误则重发，否则给肯定应答在发送端引入计时器，进行超时重发为了避免相同的帧收到多次，需要对帧进行编号3.3差错控制24前向纠错（FEC，ForwardErrorCorrect）即发送方发送能使接收方检错并纠错的冗余位，纠错任务由接收方完成；常采用海明码。主要应用于没有反向信道或反向传输时间很长的场合缺点：为纠错附加的冗余码较多，传输效率低优点：实时性好。3.3.1差错控制技术25自动重发请求（ARQ–AutomaticRepeatreQuest）即发送方发送能使接收方检错的冗余位，若无差错，则接收方回送一个肯定应答(ACK)；若有差错，则接收方回送一个否定应答(NAK)，要求发送方重发。缺点：信息传递连贯性差优点：接收端设备简单，只要请求重发，无需纠正错误。差错控制技术（2）26差错编码差错编码：数据块中插入冗余信息的过程。思想：判断一个数据块中是否存在传输错误，发送端必须在数据块中插入一些冗余信息，使得数据块中的各个比特建立某种形式的关联，接收端通过验证这种关联关系来判断是否有传输错误。差错编码策略检错码：能检测出错误，但不能纠正错误，如CRC纠错码：能知道错误，且知道错误的位置，如海明码3.3.2差错编码技术27检错码的构造检错码(码字、传输帧)＝信息位＋冗余校验位码字长n=K(信息位位数)＋r(校验位位数)编码效率R＝有效数据位K／码字长n信息字段和校验字段之间的对应关系校验字段越长，编码的检错能力越强，编码/解码越复杂；附加的冗余信息在整个编码中所占的比例越大，传输的有效成分越低，传输的效率下降。检错码一旦形成，整个检错码将作为一个整体被发往线路，通常的发送顺序是信息字段在前，校验字段在后。3.3.2.1检错码28奇校验：使码字中“1”的总个数为奇数。偶校验：使码字中“1”的总个数为偶数。奇/偶校验码：最常用的一种检错码，包括：水平奇/偶校验码垂直奇/偶校验码水平垂直奇/偶校验码奇偶校验码包括信息位和校验位需要对信息按行、列分组然后对列进行奇/偶校验方阵校验（在水平校验的基础上，增加垂直校验）29其信息字段以字符为单位，校验字段仅含一个比特称为校验比特或校验位。例如：使用七单位的ASCII码来构造成八单位的检错码时若采用奇/偶校验，校验位的取值应使整个码字包括校验位，1的比特个数为奇数或偶数。水平奇/偶校验30例：信息字段奇校验码偶校验码01100010110001001100011编码效率：Q/(Q+1)(信息字段占Q个比特)应用：通常在异步传输方式中采用偶校验，同步传输方式中采取奇校验。水平奇/偶校验31垂直奇/偶校验做法：被传输的信息进行分组，并排列为若干行和若干列。组中每行的相同列进行奇/偶校验，最终产生由校验位形成的校验字符（校验行），并附加在信息分组之后传输。举例：4个字符（4行）组成一信息组，求垂直奇/偶校验码32例：4个字符（4行）组成一信息组，其垂直奇/偶校验码为：发往线路顺序（垂直奇校验）0111001|0010101|0101011|1010101|0101101编码效率：PQ/P(Q+1)（假设信息分组占Q行P列）垂直奇/偶校验33水平垂直奇/偶校验水平垂直奇/偶校验码(方阵校验)在水平校验的基础上实施垂直校验。例：4行7列信息组的水平垂直偶校验码为：34水平垂直奇/偶校验发往线路顺序(偶校验字符)：01110010|00101011|01010110|10101010|10100101第1字符|第2字符|第3字符|第4字符|垂直偶校验字符编码效率：PQ/(P+1)(Q+1)（假设被传信息分组占Q行P列）水平偶校验位353.3.2.2循环冗余码循环冗余码（CyclicRedundancyCheck，CRC）计算机和数据通信中使用最广泛的检错码，漏检率低，可用简单的电路实现。CRC编码的一般操作给定一个k比特的帧或报文，发送方生成n比特的序列（也称为帧检验序列FCS，FrameCheckSequence），形成（k+n）的码字，该码字能被某个事先确定的数整除。接收方用相同的数去除收到的帧，如果无余数，则认为数据帧无差错36CRC也称多项式编码任意一个由二进制位串组成的代码都可以和一个系数仅为‘0’和‘1’取值的多项式一一对应。多项式表示：即将k比特的数据用k项多项式表示，它的各项为Xk-1…X0，它的系数为数据中对应位的0或1。例如：代码1010111对应的多项式为x6+x4+x2+x+1多项式为x5+x3+x2+x+1对应的代码10111137冗余码的计算假设待传送的数据M=1010001101（共kbit）。我们在M的后面再添加供差错检测用的nbit冗余码一起发送。计算方法用二进制的模2运算进行2n乘M的运算，这相当于在M后面添加n个0。得到的(k+n)bit的数除以事先选定好的长度为(n+1)bit的数P，得出商是Q而余数是R，余数R比除数P少1个比特。核心问题：P如何选定？P若选定，则n就确定了。生成多项式38二进制模2运算模2运算用模2运算进行加法时不进位。减法和加法一样，按加法规则进行运算。举例1111＋1010＝？答案为010139冗余码计算举例设M=1010001101，P=110101，n=5，模2运算的结果2nM除以P得出：商Q=1101010110余数R=01110将余数R作为冗余码添加在数据M的后面发送出去，即发送的数据是10100011010111