第5章数据链路层

1、2016第5章 数据链路层首先介绍数据链路层的功能，然后再详细讨论这些功能，接着介绍局域网和广域网数据链路层理论，最后介绍数据链路层常用的设备。两种不同的信道两种不同的信道广播信道点对点信道结点协议栈结点协议栈第第5章章 数据链路层数据链路层数据链路层功能数据链路层功能5.1组帧组帧5.2差错控制差错控制5.3介质访问控制介质访问控制5.45.5网卡、网桥和交换机网卡、网桥和交换机名词：物理链路、数据链路所有的数据链路层的基本功能都是将数所有的数据链路层的基本功能都是将数据帧通过单条链路从一个结点移动到相据帧通过单条链路从一个结点移动到相邻结点，但具体细节依赖于该链路上应邻结点，但具体细节依赖

2、于该链路上应用的具体数据链路层协议。用的具体数据链路层协议。数据链路层可能提供的服务包括：组帧、差错控制、流量控制、可靠传输和介质访问控制。1字节计数法字节计数法2字符填充的首尾定界符法字符填充的首尾定界符法3比特填充的首尾定界符法比特填充的首尾定界符法 4违法编码法违法编码法差错控制方法分两类，一类是自动请求重发（ARQ），另一类是前向纠错（FEC）。假设要发送的信息有n个比特，在偶校验方案中，发送方只需要包含一个附加的比特，选择它的值，使得这n+1个比特（初始的信息加上一个校验位）中1的总数是偶数。对于奇校验方案，校验位值得选择要求有奇数个1。二维奇偶校验：将要发送的信息的n个比特划分成i

3、行j列，对每行每列计算奇偶校验值。结果的i+j+1个奇偶比特构成了差错检测比特。1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 1 0 鬃 发送方和接收方首先要协商一个发送方和接收方首先要协商一个n+1比特比特生成码生成码P， 最高有效位的比特是最高有效位的比特是1发送端的处理发送端的处理选择选择n位的附加比特位的附加比特R（冗余码常称为帧检验（冗余码常称为帧检验序列序列FCS），附加），附加M后面，使得后面，使得k+n比特的比特的数据一起发送到接收端。数据一起发送到接收端。 冗余码

4、冗余码R：用模用模2运算运算【例【例 5-1】 已知：信息码已知：信息码M：110011 信息多项信息多项式：式：M(X)=X5+X4+X+1 生成码生成码P：1101 生成多项式：生成多项式：P(X)=X3+X2+1(n=3)求：冗余码和码字。求：冗余码和码字。解：解： 被除数是信息码被除数是信息码M后添加后添加n=3个个0，即，即110011000。 除数是除数是P即即1101。 用模用模2运算。由计算结果知冗余码是运算。由计算结果知冗余码是1001，码字就是码字就是1100111001。 接收端的处理接收方用P去除接收到的k+n位比特。如果余数为0，则认为正确而被收下得到信息码；如果余数

5、为非0，则接收方认为发生错误，就丢弃该帧。【例 5-2】 已知：接收码字：1100111001 多项式：T(X)=X9+X8+X5+X4+X3+1 生成码P： 11001 生成多项式：P(X)=X4+X3+1(n=4)求：码字的正确性。若正确，则指出冗余码和信息码。解：解： 用字码除以生用字码除以生成码，余数为成码，余数为0，如，如图图5-10所示，所以所示，所以码字正确。码字正确。 因因n=4，所以冗余码，所以冗余码是：是：1001，信息码，信息码是：是：110011 接收端的处理接收端的处理凡是接收方数据链路层接收的帧，我们凡是接收方数据链路层接收的帧，我们都能以非常接近于都能以非常接近于

6、1的概率认为这些的概率认为这些帧在传输过程中没有产生差错。通常帧在传输过程中没有产生差错。通常都这样近似地认为：凡是接收方数据都这样近似地认为：凡是接收方数据链路层接收的帧均无差错。链路层接收的帧均无差错。发送方进行海明码编码 确定最小的校验位数k。 原有信息和k个校验位一起编成长为m+k位的新码字海明码。选择k校验位（0或1）以满足必要的奇偶条件。接收方对收到的码字进行译码 接收端对所接收的信息作所需的k个奇偶检查。 如果所有的奇偶检查结果均为正确的，则认为信息无错误。如果发现有一个或多个错了，则错误的位由这些检查的结果来唯一地确定。考虑长度为考虑长度为m位的信息，若附加了位的信息，若附加了

7、k个个校验位校验位 2k 1m+k（5-1）习惯上校验位被安排在习惯上校验位被安排在1、2、4、8、的位置上的位置上 m=4，k=3时，信息位和校验位的分时，信息位和校验位的分布情况。布情况。k个校验位是通过对个校验位是通过对m+k位复合码字位复合码字进行奇偶校验而确定的进行奇偶校验而确定的对对m=4，k=3，偶校验的例子，只要进，偶校验的例子，只要进行行3次偶性测试。次偶性测试。A=B1 B3 B5 B7=0得得P1=D1 D2 D4（5-2）B=B2 B3 B6 B7=0得得P2=D1 D3 D4（5-3）C=B4 B5 B6 B7=0 P3=D2 D3 D4（5-4）例如，例如，4位信息

8、码为位信息码为1001，利用这，利用这3个公式可求得个公式可求得3个校验位个校验位P1、P2、P3的值和的值和海明码。海明码。P1 P2 1 P3 0 0 13个校验位：个校验位：P1=0；P2=0；P3=1 海明码：海明码：0011001 在接收方，根据这在接收方，根据这3个校验方程对接收到的信息进行同样的奇偶测试：个校验方程对接收到的信息进行同样的奇偶测试：A=B1 B3 B5 B7=0（5-5）B=B2 B3 B6 B7=0（5-6）C=B4 B5 B6 B7=0（5-7） 若若3个校验方程都成立，即方程式右边都等于个校验方程都成立，即方程式右边都等于0，则说明没有错。若，则说明没有错。

9、若不成立即方程式右边不等于不成立即方程式右边不等于0，说明有错。从，说明有错。从3个方程式右边的值，个方程式右边的值，可以判断哪一位出错。可以判断哪一位出错。介质访问控制介质访问控制在下一章要介绍的频分复用（FDM）、时分复用（TDM）、波分复用和码分复用等就是静态划分介质访问控制。载波监听多路访问载波监听多路访问/冲突检测协议（冲突检测协议（Carrier Sense Multiple Access with Collision Detection，CSMA/CD） 当一个结点想要发送数据的时候，它检测网络查看是否有其他结点正当一个结点想要发送数据的时候，它检测网络查看是否有其他结点正在传输

10、，即监听信道是否空闲。在传输，即监听信道是否空闲。 如果信道忙，则等待，直到信道空闲；如果信道闲，结点就传输数据如果信道忙，则等待，直到信道空闲；如果信道闲，结点就传输数据。 在发送数据的同时，结点继续监听网络确信没有其他结点在同时传输在发送数据的同时，结点继续监听网络确信没有其他结点在同时传输数据。数据。 当一个传输结点识别出一个冲突，它就发送一个拥塞信号，这个信号当一个传输结点识别出一个冲突，它就发送一个拥塞信号，这个信号使得冲突的时间足够长，让其他的结点都能发现。使得冲突的时间足够长，让其他的结点都能发现。 其他结点收到拥塞信号后，都停止传输，等待一个随机产生的时间间其他结点收到拥塞信号

11、后，都停止传输，等待一个随机产生的时间间隙（回退时间，隙（回退时间，Backoff Time）后重发。）后重发。争用期争用期数据帧的传输时延至少要两倍于传播时延数据帧的传输时延至少要两倍于传播时延(bit)(m)2(Mbit/s)(m/ s)最短帧长任意两点间最大距离数据传输速率信号传播速度【5-3】考虑一个使用】考虑一个使用CSMA/CD介质访问控制技术的介质访问控制技术的100Mbit/s局局域网，若该网络跨距为域网，若该网络跨距为1km，信号在网络上传播速度为，信号在网络上传播速度为200/ s，则能够使用此协议的最小帧长度为多少？则能够使用此协议的最小帧长度为多少？“截断二进制指数退避

12、截断二进制指数退避”算法算法 确定基本退避时间，它就是争用期确定基本退避时间，它就是争用期2 。以太网把争用期定为。以太网把争用期定为51.2 s。对于对于10Mbit/s以太网，在争用期内可发送以太网，在争用期内可发送512bit，即，即64字节，即最字节，即最小帧长小帧长64字节。字节。1比特时间是发送比特时间是发送1比特所需的时间，也可以说争用比特所需的时间，也可以说争用期是期是512比特时间。比特时间。 设置参数设置参数k=min重传次数，重传次数，10，即重传次数不超过，即重传次数不超过10时，时，k=重传次数；重传次数超过重传次数；重传次数超过10时，时，k=10。从离散的数据集合

13、从离散的数据集合0；1；2；（；（2k 1）中随机地取一个数，）中随机地取一个数，记为记为r。重传应推后的时间就是。重传应推后的时间就是r倍的争用期。倍的争用期。 设置一个最大重传次数设置一个最大重传次数16，超过此值，则丢弃该帧，不再重发，并，超过此值，则丢弃该帧，不再重发，并报告出错。报告出错。令牌环网上的令牌环网上的A站向站向C站发送信息的过程站发送信息的过程（环的比特长度（环的比特长度接口延迟位数）接口延迟位数）/数据传输速率环的介质的长度数据传输速率环的介质的长度/传播时延传播时延即：即：环的比特长度环的比特长度=（环的介质的长度（环的介质的长度/传播时延）传播时延） 数据传输速率数

14、据传输速率+ 接口延迟位数接口延迟位数某令牌环介质长度为某令牌环介质长度为10km，数据传输速率为，数据传输速率为4Mbit/s；环路上共；环路上共有有50个站点，每个站点的接口引入个站点，每个站点的接口引入1位延迟，计算环的比特长度位延迟，计算环的比特长度。网卡、网桥和交换机网卡、网桥和交换机5.5.1 网卡5.5.2 网桥5.5.3 交换机1网卡的功能2查看网卡的MAC地址3修改MAC地址1网桥的工作原理2网桥的类型网桥内部维护一张转发表网桥内部维护一张转发表网桥的功能是：网桥的功能是：自学习自学习形成网桥转发表；形成网桥转发表；过滤帧过滤帧减轻局域网的负荷；减轻局域网的负荷；转发帧转发帧

15、使不同的局域网互连扩大网络的物理范围。使不同的局域网互连扩大网络的物理范围。（1）透明网桥（）透明网桥（Transparent Bridge）（2）源路由网桥（）源路由网桥（Source route Bridge）透明网桥的转发表要记录透明网桥的转发表要记录3项信息：站地址、端口号与时间。项信息：站地址、端口号与时间。逆向自学习方法建立其转发表逆向自学习方法建立其转发表生成树（生成树（spanning tree）算法解决）算法解决回路回路问题问题源路由网桥在每个帧的发送时，把详细的路由信息放在帧的首部中。源路由网桥在每个帧的发送时，把详细的路由信息放在帧的首部中。获取路由算法的基本思想获取路由算法的基本思想 广播风暴广播风暴 增加网络时延增加网络时延 帧丢失帧丢失 在交换式快速以太网中，可以通过交换机为所有结点建立并行的、独立的和专用带宽的连接。工作原理 第三层交换技术就是“第二层交换技术+第三层转发”。解决了局域网中网段划分之后网段中的子网必须依赖路由器进行管理的局面，解决了传统路由器低速、复杂所造成的网络瓶颈问题。实训实训 以太网交换机的以太网交换机的配置配置1