数据链路层

第三章 数据链路层

1. 功能

• 数据链路层在物理层提供服务的基础上向网络层提供服务，其最基本的服务是将源自网络层来的数据可靠地传输到相邻节点的目标机网络层。其主要作用是加强物理层传输原始比特流的功能，将物理层提供的可能出错的物理连接改造成为逻辑上无差错的数据链路，使之对网络层表现为一条无差错的链路。

功能一：为网络层提供服务。无确认无连接服务，有确认无连接服务，有确认面向连接服务。 有连接一定有确认！

功能二：链路管理，即连接的建立、维持、释放（用于面向连接的服务）。

功能三：组帧。 功能四：流量控制。 功能五：差错控制（帧错/位错）。

2. 组帧

• 封装成帧：在一段数据的前后部分添加首部和尾部，这样就构成了一个帧。
• 帧同步：接收方应当能从接收到的二进制比特流中区分出帧的起始和终止。
• 透明传输：不管所传数据是什么样的比特组合，都应当能够在链路上传送。

2.1 组帧的四种方法

1. 字符计数法
2. 字符（节）填充法
3. 零比特填充法
4. 违规编码法

2.1.1 字符计数法

• 帧首部使用一个计数字段（第一个字节，八位）来标明帧内字符数。
• 缺点：一旦一个帧出现了缺失字符等情况，会影响到后面的帧

2.1.2 字符（节）填充法

• 使用ASCII码，比如键盘上面的字符时，可以直接实现透明传输，但是使用非ASCII码，如二进制数字时，需要采用字符填充方法实现透明传输
• 如下图所示：SOH是开始，EOT是结束，ESC是转义

2.1.3 零比特填充法

1. 在发送端，扫描整个信息字段，只要连续5个1，就立即填入1个0。
2. 在接收端收到一个帧时，先找到标志字段确定边界，再用硬件对比特流进行扫描。发现连续5个1时，就把后面的0删除。
3. 保证了透明传输：在传送的比特流中可以传送任意比特组合，而不会引起对帧边界的判断错误。

2.1.4 违规编码法

• 如下所示，比如使用曼彻斯特编码时，可以使用与曼彻斯特编码不同的编码方式定义首尾

3. 差错控制

3.1 检错编码

3.1.1 奇偶校验码

• n-1位信息元，1 位校验元
• 奇偶校验码特点：只能检测奇数位的出错情况，但并不知道哪些位出错了，也不能发现偶数位的出错情况，检错能力为50%
• 若采用奇校验，那么传输的数据中1的个数若是偶数个则可检测出错误，若1的个数是奇数个，则检测不出错误

3.1.2 CRC (循环冗余码)

• 生成多项式是题目会直接给出的
• r + 1 位是生成多项式的二进制位数，如果给出的是代数形式的多项式，需要会转换成二进制
• r 为最高项数
• 除法为模二除
• FCS的生成以及接收端CRC检验都是由硬件实现，处理很迅速， 因此不会延误数据的传输。

3.2 纠错编码

3.2.1 海明码

• 两个码字的对应比特取值不同的比特数称为这两个码字的海明距离(码距)，在一个有效编码集中，任意两个码字的海明距离的最小值称为该编码集的海明距离(码距)
• 海明码纠错d位，需要码距为2d+1的编码方案；检错d为，则只需码距为d+1

1. 确定校验码位数 r

2. 确定校验码和数据的位置

• 放在2的n次方位置上，比如放在2、4、8、16 ……

3. 求出校验码的值

• 把序号化为二进制数，和序号中与 1 位置相同的（包括其本身）分为一组
• 对不同组的数进行二进制排列，进行偶校验的方式得出 0或1的结果，并填入所负责的校验码的位置中

4. 检错并纠错

4. 流量控制和可靠传输机制

• 停止等待协议：发送窗口大小 =1，接收窗口大小 =1
• 后退N帧协议（GBR）：发送窗口大小 >1，接收窗口大小 =1
• 选择重传协议（SR）：发送窗口大小 >1，接收窗口大小 > 1

4.1 停止等待协议

• 目的：实现流量控制
• 缺点：除了比特出差错，底层信道还会出现丢包问题，信道利用率低
• 实现前提：半双工（我们研究的）和全双工
• 可能出现的情况：无差错情况&有差错情况

信道利用率

4.2 滑动窗口协议

4.2.1 后退N帧协议(GBN)

1.发送方

2.接收方

3.滑动窗口长度

4.性能分析

• 因连续发送数据帧而提高了信道利用率
• 在重传时必须把原来已经正确传送的数据帧重传，传送效率降低。

4.2.2 选择重传协议(SR)

1.发送方

2.接收方

3. 滑动窗口长度

5 介质访问控制

*动态划分信道

5.1 ALOHA协议（随

• 纯ALOHA协议
• 时隙ALOHA协议

5.1.1 纯ALOHA协议

• 纯ALOHA协议思想：不监听信道，不按时间槽发送，随机重发。想发就发
• 若发生冲突：接收端不予确认，发送端收不到确认就重发
• 解决冲突：超时后随机一段时间后重传

5.1.2 时隙ALOHA协议

• 时隙ALOHA协议的思想：把时间分成若干个相同的时间片，所有用户在时间片开始时刻同步接入网络信道， 若发生冲突，则必须等到下一个时间片开始时刻再发送。控制想发就发的随意性

5.1.3 两者比较

1. 纯ALOHA比时隙ALOHA吞吐量更低，效率更低。
2. 纯ALOHA想发就发，时隙ALOHA只有在时间片段开始时才能发。

5.2 CSMA协议

• CS：载波侦听/监听，每一个站在发送数据之前要检测一下总线上是否有其他计算机在发送数据。
• MA：多点接入，表示许多计算机以多点接入的方式连接在一根总线上。
• 协议思想：发送帧之前，监听信道。

	优点	缺点
1-坚持CSMA	只要媒体空闲，站点就马上发送，避免了媒体利用率的损失	假如有两个或两个以上的站点有数据要发送，冲突就不可避免
非坚持CSMA	采用随机的重发延迟时间可以减少冲突发生的可能性。	可能存在大家都在延迟等待过程中，使得媒体仍可能处于空闲状态，媒体使用率降低
p-坚持CSMA	既能像非坚持算法那样减少冲突，又能像1-坚持算法那样减少媒体空闲时间	发生冲突后还是要坚持把数据帧发送完，造成了浪费

5.3 CSMA/CD协议

• CD：碰撞检测（冲突检测），“边发送边监听”，适配器边发送数据边检测信道上信号电压的变化情况，以便判断自己在发送数据时其他站是否也在发送数据。
• 先听后发发生冲突的原因：电磁波在总线上总是以有限的速率传播的
• 避免冲突的方法：让传输时延是传播时延的两倍
• 最小帧长=总线传播时延 x 数据传输速率 x 2 = RTT * 数据传输速率

5.3.1 确定碰撞后的重传时机

5.4 CSMA/CA协议

5.4.1 工作原理

1. 发送数据前，先检测信道是否空闲。 空闲则发出RTS；信道忙则等待。
2. 接收端收到RTS后，将响应CTS。 发送端收到CTS后，开始发送数据帧（同时预约信道：发送方告知其他站点自己要传多久数据）。
3. 接收端收到数据帧后，将用CRC来检验数据是否正确，正确则响应ACK帧。
4. 发送方收到ACK就可以进行下一个数据帧的发送，若没有则一直重传至规定重发次数为止（采用二进制指数 退避算法来确定随机的推迟时间）。
5. 隐蔽站和暴露站

5.4.2 CSMA/CD与CSMA/CA

• 相同点：两个在接入信道之前都须要 进行监听。当发现信道空闲后，才能进行接入。
• 不同点：

1. 传输介质不同：CSMA/CD 用于总线式以太网【有线】，而CSMA/CA用于无线局域网【无线】。
2. 载波检测方式不同：因传输介质不同，CSMA/CD通过电缆中电压的变化来检测；而CSMA/CA采用能量检测（ED）、 载波检测（CS）和能量载波混合检测三种检测信道空闲的方式。
3. CSMA/CD检测冲突，CSMA/CA避免冲突，二者出现冲突后都会进行有上限的重传。

5.5 令牌传输协议（轮询访问协议）

• 令牌：一个特殊格式的MAC控制帧，不含任何信息。 控制信道的使用，确保同一时刻只有一个结点独占信道。
• 问题： 1.令牌开销 2.等待延迟 3.单点故障
• 应用于：令牌环网（物理星型拓扑，逻辑环形拓扑）。 采用令牌传送方式的网络常用于负载较重、通信量较大的网络中

5.6 静态划分信道

• 三种信道化协议：FDMA（频分多路访问）、 TDMA（时分多路访问）和CDMA（码分多路访问）
• FDMA与FDM的区别：FDMA是数据链路层的，FDM是物理层的

6. 局域网

6.1 概述

• 局域网：简称LAN，使用广播信道。

• 决定局域网的主要要素为：网络拓扑，传输介质与介质访问控制方法。

• 标准：

IEEE 802.3 ：以太网介质访问控制协议 （CSMA/CD）及物理层技术规范

IEEE 802.5 ：令牌环网（Token-Ring)的介质访问控制协议及物理层技术规范

IEEE 802.8 ：光纤技术咨询组，提供有关光纤联网的技术咨询

IEEE 802.11：无线局域网（WLAN）的介质访问控制协议及物理层技术规范

• 局域网的拓扑结构

1. 星型
2. 总线型
3. 环型
4. 树型

• 局域网介质访问控制方法

1. CSMA/CD ，常用于总线型局域网
2. 令牌总线 ，常用于总线型局域网
3. 令牌环， 用于环形局域网，如令牌环网

• 局域网的分类

1. 以太网
2. 令牌环网
3. FDDI网（光纤）
4. ATM网
5. 无线局域网

6.2 MAC子层和LLC子层

6.3 以太网

• 以太网是当今现有局域网采用的最通用的通信协议标准。以太网络使用CSMA/CD技术。
• 访问方法：标准以太网使用1-持续的CSMA/CD方法（结合二进制指 数退避策略）
• 时隙：在以太网络中，一个帧从最大长度网络的一端到另一端之间往 返所需的时间
• 以太网提供无连接、不可靠的服务
• 以太网拓扑：逻辑上总线型，物理上星型。

6.3.1 各种传输介质的适用情况

6.3.2 以太网MAC帧

• 最常用的MAC帧是以太网V2的格式。

6.3.3 高速以太网

• 速率≥100Mb/s的以太网称为高速以太网

1. 100BASE-T以太网

• 在双绞线上传送100Mb/s基带信号的星型拓扑以太网，仍使用IEEE802.3的CSMA/CD协议。 支持全双工和半双工，可在全双工方式下工作而无冲突。

2. 吉比特以太网

• 在光纤或双绞线上传送1Gb/s信号，支持全双工和半双工，可在全双工方式下工作而无冲突。

3. 10吉比特

• 10吉比特以太网在光纤上传送10Gb/s信号，只支持全双工，无争用问题。

6.4 无线局域网

• IEEE 802.11是无线局域网通用的标准

6.4.1 802.11的MAC帧头格式

• 地址1：下一跳地址 。地址2：源地址 。地址3：目的地址

• RA是Receiver Address的缩写，BSSID是Basic Service Set IDentifier 的缩写，SA 是Source Address 的缩写，DA是Destination Address的缩写

• IEEE 802.11定义了三种类型的帧：管理帧、控制帧和数据帧（注意和HDLC区分）

• 无限局域网的分类

1. 有固定基础设施无线局域网
2. 无固定基础设施无线局域网的自组织网络

7. 广域网

• 广域网简称 WAN，主要使用分组交换技术。如因特网 （Internet）是世界范围内最大的广域网。

7.1 PPP协议

• 点对点协议PPP 是目前使用最广泛的数据链路层协议，用户使用拨号电话接入因特网时一般都使用 PPP协议。只支持全双工链路，面向字节

1. PPP协议应该满足的要求

2. PPP协议无需满足的要求

3. PPP协议的三个组成部分

1. 一个将IP数据报封装到串行链路（同步串行/异步串行）的方法。
2. 链路控制协议LCP：建立并维护数据链路连接。 身份验证
3. 网络控制协议NCP：PPP可支持多种网络层协议，每个不同的网络层协议都要一个相应的NCP来配 置，为网络层协议建立和配置逻辑连接。

4. PPP协议帧格式

7.2 HDLC协议

• 高级数据链路控制（HDLC），是面向比特的数据链路层协议，数据报文可透明传输，用于实现透明传输的“0比特插入法”易于硬件实现，采用全双工通信 ，所有帧采用CRC检验，对信息帧进行顺序编号，可防止漏收或重份，传输可靠性高。

1. HDLC的站

1. 主站的主要功能是发送帧、接收响应帧，并负责对整个链路的控制系统的初启、 流程的控制、差错检测或恢复等。
2. 从站的主要功能是接收由主站发来的命令帧，向主站发送响应帧，并且配合主站参与差错恢复等链路控制。
3. 复合站的主要功能是既能发送，又能接收命令帧和响应帧，并且负责整个链路的控制。

2. HDLC的帧格式

3. HDLC两种通用的传输方式

• 正常响应方式(NRM)：主站能发送指令，而从站只能响应
• 异步平衡方式(ABM)：每个站点既有主站的功能又有从站的功能，这是现在普遍应用的方式

7.3 PPP协议＆HDLC协议

8. 数据链路层设备

8.1 网桥

• 网桥根据MAC帧的目的地址对帧进行转发和过滤。当网桥收到一个帧时，并不向所有接口转发此帧，而先检查此帧的目的MAC地址，然后再确定将该帧转发到哪一个接口，或者是把它丢弃（即过滤）。
• 网桥的优点：

1. 过滤通信量，增大吞吐量。
2. 扩大了物理范围。
3. 提高了可靠性。
4. 可互连不同物理层、不同MAC子层和不同速率的以太网。

• 网段：一般指一个计算机网络中使用同一物理层设备（传输介质，中继器，集线器等）能够直接通讯的那一 部分

1. 透明网桥

• “透明”指以太网上的站点并不知道所发送的帧将经过哪几个网桥，是一种即插即用设备—自学习

2. 源路由网桥

• 在发送帧时，把详细的最佳路由信息（路由最少/时间最短）放在帧的首部中
• 方法：源站以广播方式向欲通信的目的站发送一个发现帧。

8.3 交换机

• 多接口网桥——以太网交换机

1. 直通式交换机

• 查完目的地址（6B）就立刻转发。 延迟小，可靠性低，无法支持具有不同速率的端口的交换

2. 存储转发式交换机

• 将帧放入高速缓存，并检查否正确，正确则转发，错误则丢弃。

• 延迟大，可靠性高，可以支持具有不同速率的端口的交换。

8.3 广播域和冲突域

• 广播域：网络中能接收 任一设备发出的广播帧 的所有设备的集合。简 单的说如果站点发出一 个广播信号，所有能接 收收到这个信号的设备 范围称为一个广播域。

• 冲突域：在同一个冲突域中的每一个节点都能收到所有被发送的帧。 简单的说就是同一时间内只能有一台设备发送信息的范围。

  

考点加强记忆

1. 为了避免传输过程中帧的丢失，数据链路层采用的方法是计时器超时重传
2. 对于信道比较可靠且实时性要求比较高的网络，数据链路层采用无确认的无连接服务比较合适
3. 在不可靠的信道上无确认的服务效率比较低。为提高有效性，应该引入有确认的服务
4. 数据链路层不用考虑物理层的传输细节
5. 数据链路层会为网络层提供三种可能的服务：无确认的无连接服务、有确认的无连接服务、有确认的面向连接服务
6. 海明码纠错d位，需要码距为2d+1的编码方案；检错d为，则只需码距为d+1
7. 在使用多项式编码时，发送端和接收端必须预先商定一个生成多项式
8. 选择重传协议SR收下发送序号不连续但仍处在接收窗口中的那些帧数据
9. 信道利用率是对发送方而言的，是指发送方在一个周期的时间内，有效的发送数据所需要的时间占整个发送周期的比率
10. 注意发送帧和接受帧的时间可能不一致
11. 在连续的ARQ算法中，发送窗口的大小≤窗口总数-1
12. 在选择重传协议中，需要满足：发送窗口大小+接受窗口大小≤2的n次方，接收窗口大小不应该超过发送窗口大小
13. 采用CSMA/CD协议的以太网只能进行半双工通信
14. 把以太网端到端往返时间2τ称为争用期（又称冲突窗口和碰撞窗口）
15. 使用二进制回退算法的理由是这种算法考虑了网络负载对冲突的影响，其中k值越大，帧重传时再次发生冲突的概率就越小
16. 信道划分协议是静态划分信道的方法，肯定不会发生冲突IEEE 802.3 标准描述的是物理层和数据链路层的MAC子层的实现方法
17. 网卡实现的主要功能在物理层和数据链路层
18. 在使用静态地址的系统中，如果有重复的硬件地址，那么两个设备都不能正常通信
19. 以太网广播中，连接在总线上的所有结点（包括发送结点）都能“收听”到发送结点发送的数据信号
20. 吉比特以太网的物理层有两个标准：IEEE802.3z和IEEE802.3ab，前者采用光线通道，后者才用4对UTP5类线
21. 链路聚合是解决交换机之间带宽瓶颈问题的技术
22. PPP只支持全双工链路
23. HDCL常用的操作方式中，传输过程只能由主站启动的是：正常响应模式
24. HDCL不属于TCP/IP协议族
25. PPP两端的网络层可以运行不同的网络层协议，但仍然能使用同一个PPP进行通信
26. VLAN不仅可以隔离冲突域，而且可以隔离广播域
27. 以太网交换机进行转发决策时使用的PDU地址是目的物理地址
28. 交换技能隔离冲突与，工作在全双工状态，是网络中多结点同时通信，提高了网络的利用率，这是交换机的优点
29. 固定长度成帧：不需要定义帧的边界，长度本身可以F用作分隔符，例如ATM信元
30. 差错类型：

• 单比特差错：比特流只出现一位的差错
• 突发性差错：比特流出现超过一位的差错

32. 检错和纠错的核心概念是冗余，纠错比检错更难

[[计网-第四章(网络层)]]