[计算机网络(第八版)]第三章 数据链路层（学习笔记）

• 物理层解决了相邻节点透明传输比特的问题

3.1 数据链路层的几个共同问题

3.1.1 数据链路和帧

• 链路：
  • 从一个节点到相邻节点的一段物理线路，中间没有任何其他的交换节点
• 数据链路：
  • 节点间的逻辑通道
  • 是把实现控制数据传输的协议的硬件和软件加到链路上，即数据链路是链路加协议
• 数据链路层：
  • 负责通过一条链路从一个节点向物理链路直接相连的相邻节点传送帧
  • 数据链路层的协议数据单元：
    • 帧
  • 数据链路层把网络层交下来的数据构成帧发送到链路上，以及把接收到的帧中的数据取出并上交给网络层。
  • 网络层协议数据单元就是IP数据报（或简称为数据报、分组或包)。
  • 
  • 数据链路层向上，向网络层提供明确的服务接口；向下，利用物理层提供的服务
  • 点对点信道的数据链路层通信时的主要步骤如下:
    1. 节点A的数据链路层把网络层交下来的IP数据报添加首部和尾部封装成帧。
    2. 节点A把封装好的帧发送给节点B的数据链路层。
    3. 若节点B的数据链路层收到的帧无差错，则从收到的帧中提取出IP数据报交给上面的网络层;否则丢弃这个帧。

3.1.2 三个基本问题

• 数据链路层的信道类型：
  • 点对点信道
    • 一对一的通信方式，用于主干网
  • 广播信道
    • 一对多的通信方式
  • 链路中通信双方的信道使用不同的类型，会有不同的控制协议
• 数据链路层协议的三个基本问题：
  • 封装成帧
  • 透明传输
  • 差错检测

1. 封装成帧

• 封装成帧
  • 就是在一段数据的前后分别添加首部和尾部。
  • 首部和尾部的一个重要作用就是进行帧定界（即确定帧的界限)。
• 将比特流划分成帧的主要目的是为了检测和纠正物理层在比特传输中可能出现的错误
• 每一种链路层协议都规定了所能传送的帧的数据部分长度上限——最大传送单元 MTU (Maximum Transfer Unit)。
  • 即一个帧中所能封装的IP数据报的长度
• 
• 定界符
  • 使用控制字符作为帧定界符
  • 控制字符SOH作为帧首部，控制字符EOT作为帧尾部
  • 
• 成帧的方法
  • 字节计数法
  • 带字节填充的定界符法
  • 带比特填充的定界符法
  • 物理层编码违例

2. 透明传输

• 透明
  • 表示某一个实际存在的事物看起来却好像不存在一样
• 透明传输
  • 在数据链路层透明传送数据表示无论什么样的比特组合的数据，都能够按照原样没有差错地通过这个数据链路层。
  • 即一个帧发送的时候什么样，接收的时候就是什么样
• 带字节填充的定界符法实现透明传输
  • 字节填充或字符填充
    • 发送端的数据链路层在数据中出现控制字符“SOH"或“EOT”的前面插入一个转义字符“ESC"，在接收端的数据链路层在把数据送往网络层之前删除这个插入的转义字符。
    • 
• 带比特填充的定界符法
  • 使用特殊比特序列作为帧的开始，遇到数据部分与比特填充定界符相同时，采用比特填充法实现透明传输。
  • 以01111110为帧的开始，当数据部分出现5个1时就插入一个0，保证不会出现6个1的情况
• 物理层编码违例
  • 使用特殊的定界符，保证在正常的编码中不太容易产生或不会产生相应的信号，例如以太网中的帧前导码、差分曼彻其特编码的不正常跳变信号等。
  • 如以10101010等有规律的信号定界，数据部分的信号一般不会有规律

3. 差错检测

• 比特差错
  • 由于噪声的影响，比特在传输过程中可能会产生差错，1可能会变成0，而0也可能变成1。
• 称为误码率BER
  • 在一段时间内，传输错误的比特占所传输比特总数的比率(Bit Error Rate)。
  • 误码率与信噪比有很大的关系。提高信噪比，就可以使误码率减小。
• 差错检测
  • 为了保证数据传输的可靠性，帧不出错
  • 目前在数据链路层广泛使用循环冗余检验CRC的检错技术。
  • 检错码：
    • 主要用在高可靠、误码率低的信道
    • 有错误就丢弃，重新发送
  • 纠错码：
    • 主要用于错误发生频繁的信道
    • 错误率高的信道重发还是错误
• 循环冗余检验CRC
  • CRC就是在数据M的后面添加供差错检测用的n位冗余码，然后构成一个帧发送出去，一共发送(k + n)位。
  • n位冗余码可用二进制的模2运算（不进位、不退位、不借位）得到
    1. 在M后面添加n个0，得到(k + n)位的数
    2. 得到的(k + n)位的数除以收发双方事先商定的长度为(n + 1)位的除数P
    3. 得出商是Q而余数是R (n位，比P少一位)。
    4. 这个余数R就作为冗余码拼接在数据M的后面发送出去。
    • 
    • (0-1)可以当成(2-1)结果为1，或者看成异或运算
    • 如果第一位大于等于除数，就商1，否则商0
    5. 接收方检验是否出错，就用添加冗余码后的数再除一次除数看是否可以除尽，可以无出错，否则出错
  • 这种为了进行检错而添加的冗余码常称为帧检验序列FCS
  • 循环冗余检验CRC和帧检验序列FCS并不是同一个概念。
    • CRC是一种检错方法
    • FCS是添加在数据后面的冗余码，在检错方法上可以选用CRC，但也可不选用CRC。
• 数据链路层实现的只是接收的每个帧是无差错的，并不能保证可靠传输
• 可靠传输
  • 不出现帧丢失
  • 不出现帧重复
  • 不出现帧失序

3.2 点对点协议PPP

• PPP是目前使用得最广泛得数据链路层协议

3.2.1 PPP协议的特点

1. PPP协议应满足得要求

1. 简单
2. 封装成帧
3. 透明性
4. 多种网络层协议，PPP协议必须能够再同一条物理链路上同时支持多种网络层协议，能将网络层得数据报封装成帧传输
5. 多种类型链路，PPP必须能够再多种类型得链路上运行
6. 差错检测
7. 检测连接状态
8. 最大传送单元，MTU是数据链路层得帧可以载荷得数据部分得最大长度，不是帧得总长度
9. 网络层地址协商，PPP必须提供一种机制使两个网络层得实体能够通过协商知道或能够配置彼此得网络层地址
10. 数据压缩协商，PPP必须提供一中方法来协商使用数据压缩算法

2. PPP协议的组成

• PPP协议的三个组成部分
  1. 一个将IP数据报封装到串行链路的方法。PPP 既支持异步链路(无奇偶检验的8比特数据)，也支持面向比特的同步链路。
  2. 一个用来建立、配置和测试数据链路连接的链路控制协议LCP
  3. 一套网络控制协议NCP， 其中的每一个协议支持不同的网络层协议

3.2.2 PPP协议的帧格式

1. 各字段的意义

• PPP帧的首部和尾部分别为四个字段和两个字段。
• 首部的第一个字段和尾部的第二个字段都是标志字段F (Flag)，规定为0x7E
  • 标志字段表示一个帧的开始或结束。
  • 标志字段就是PPP帧的定界符。
• 首部中的地址字段A规定为0xFF (即111111)
• 控制字段C规定为0x03 (即0000011)。
• 字段A与字段C的定义至今也没有给出。
  • 这两个字段实际上并没有携带PPP帧的信息。
• PPP首部的第四个字段是2字节的协议字段。
  • 表示上层IP数据报部分的类型
  • 当协议字段为0x0021时，PPP帧的信息字段就是IP数据报。
  • 若为0xC021， 则信息字段是PPP链路控制协议LCP的数据，
  • 0x8021表示这是网络层的控制数据。
• 信息字段的长度是可变的，不超过1500字节。
• 尾部中的第一个字段(2字节)是使用CRC的帧检验序列FCS。

透明传输问题

• 当PPP用在异步传输时，使用字节填充法。
• 当PPP用在同步传输链路时，采用零比特填充法。
• 同步传输(SONET/SDH链路)
  • 面向比特的传输，同步传输的单位是帧
  • 同步传输收发双方时钟统一、字符间传输同步无间隔。即发一个比特收一个比特
• 异步传输
  • 面向字节的传输，异步传输的单位是字符;
  • 异步传输效率低，高速链路开销大。
  • 收到的比特数达到一个字节再进行接收
  • 异步，发送的比特没有马上被接收

2. 字节填充

• 当PPP使用异步传输时，把转义符定义为0x7D (即1111101)， 并使用字节填充
  1. 把信息字段中出现的每一个0x7E字节转变成为2字节序列(0x7D, 0x5E)。
  2. 若信息字段中出现一个0x7D的字节(即出现了和转义字符一样的比特组合)，则把0x7D转变成为2字节序列(0x7D, 0x5D)。
  3. 若信息字段中出现ASCII码的控制字符(即数值小于0x20的字符)，则在该字符前面要加入一个0x7D字节，同时将该字符的编码加以改变。
• 

3. 零比特填充

• 在发送端，先扫描整个信息字段，只要发现有5个连续1，则立即填入一个0。
• 接收端在收到一个帧时，先找到标志字段F以确定一个帧的边界，接着再用硬件对其中的比特流进行扫描。每当发现5个连续1时，就把这5个连续1后的一个0删除，以还原成原来的信息比特流
  • 这样就保证了透明传输，不会引起对帧边界的错误判断。
• 

3.2.3 PPP协议的工作状态

3.3 使用广播信道的数据链路层

3.3.1 局域网的数据链路层

• 局域网最主要的特点是
  • 网络为一个单位所拥有，且地理范围和站点数目均有限。
• 局域网的优点
  1. 具有广播功能，从一个站点可很方便地访问全网。
  2. 便于系统的扩展和逐渐地演变，各设备的位置可灵活调整和改变。
  3. 提高了系统的可靠性(reliability)、可用性(availability)和生存性(survivability)。
• 局域网可按网络拓扑进行分类
  • 
  • 都共享一个信道
• 广播信道的问题
  • 可能2个或多个站点同时请求占用信道
• 解决方法
  • 静态划分信道
    • 方式
      • 频分复用
      • 时分复用
      • 波分复用
      • 码分复用
    • 适用于通信量大且流量稳定、用户少且用户数目固定的情况
    • 代价高，不适合突发性业务，不适合局域网
  • 动态媒体接入控制
    • 又称多点接入
    • 信道不是在用户通信时固定分配给用户的
    • 方式
      • 随机接入
        • 所有的用户可以随机的发生信息
        • 如以太网
      • 受控接入
        • 用户不能随机的发送信息，必须服从一定的控制
        • 如轮询

1. 以太网的两个主要标准

• IEEE 802 委员会就把局域网的数据链路层拆成两个子层
  • 逻辑链路控制LLC (Logical Link Control)子层
  • 媒体接入控制MAC (Medium Access Control)子层
• 与接入到传输媒体有关的内容都放在MAC子层，而LLC子层则与传输媒体无关，不管采用何种传输媒体和MAC子层的局域网对LLC子层来说都是透明的
  • 
• 目前逻辑链路控制子层LLC的作用已经消失，适配器上基本只装有MAC协议没有LLC协议

2. 适配器的作用

• 适配器(adapter)
  • 计算机与外界局域网的连接是通过适配器(adapter)。
  • 适配器本来是在主机箱内插入的一块网络接口板(或者是在笔记本电脑中插入一块PCMCIA卡——个人计算机存储器卡接口适配器)。
  • 这种接口板又称为网络接口卡NIC或简称为“网卡”。
• 适配器的一个重要功能就是要进行数据串行传输和并行传输的转换。
• 由于网络上的数据率和计算机总线的数据率并不相同，因此在适配器中必须装有对数据进行缓存的存储芯片。
• 在主板上插入适配器时，还必须把管理该适配器的设备驱动程序安装在计算机的操作系统中。
  • 驱动程序会告诉适配器，应当从存储器的什么位置上把多长的数据块发送到局域网，或者应当在存储器的什么位置上把局域网传送过来的数据块存储下来。
• 适配器还要能够实现以太网协议
• 适配器使用数据链路层中规定的MAC地址进行局域网通信
• 

3.3.2 CSMA/CD协议

• 总线型以太网
  • 最早的以太网是将许多计算机连接到一根总线上
• 总线的特点是
  • 易于实现广播、简单、可靠
  • 当一台计算机发送数据时，总线上的所有计算机都能检测到这个数据。
    • 这种就是广播通信方式。
• 为了在总线上实现一对一的通信，可以使每一台计算机的适配器都拥有一个与其他适配器都不同的地址。在发送数据帧时，在帧的首部写明接收站的地址。仅当数据帧中的目的地址与适配器ROM中存放的硬件地址一致时，该适配器才能接收这个数据帧。适配器对不是发送给自己的数据帧就丢弃。
• 把局域网上的计算机称为“主机”“工作站”“站点”或“站”。
• 以太网采取的两种重要措施
  • 采用无连接的工作方式
  • 发送的数据使用曼切斯特编码，便于同步
• 总线型以太网多个站点同时发送信息
  • 会产生发送碰撞或冲突，导致发送失败
    • 碰撞后信号叠加，虽然还能继续传输，但是无法辨别出发送的信息
  • 
• CSMA/CD
  • 载波监听多点接入/碰撞检测
• CSMA/CD协议的要点
  • “多点接入”就是说明这是总线型网络，许多计算机以多点接入的方式连接在一根总线上。
  • 协议的实质是“载波监听”和“碰撞检测”。
  • “载波监听”也就是“边发送边监听”。
    • 载波监听就是不管在想要发送数据之前，还是在发送数据之中，每个站都必须不停地检测信道。
  • 碰撞检测
    • 在发送前检测信道，是为了避免冲突。如果检测出已经有其他站在发送，则本站就暂时不要发送数据。
    • 在发送中检测信道，是为了及时发现如果有其他站也在发送，就立即中断本站的发送。
    • “碰撞检测”是适配器边发送数据边检测信道上的信号电压的变化情况。
    • 当适配器检测到的信号电压变化幅度超过一定的门]限值时，就认为总线上至少有两个站同时在发送数据，表明产生了碰撞。
    • 所谓“碰撞”就是发生了冲突。因此“碰撞检测”也称为“冲突检测”。
    • 一旦发现总线上出现了碰撞，其适配器就要立即停止发送，然后等待一段随机时间后再次发送。
• 既然每一个站在发送数据之前已经监听到信道为“空闲”，那么为什么还会出现数据在总线上的碰撞呢?
  • 因为不会查看整个信道，而只是检测自己到总线出去一部分的区域
• 为什么进行碰撞检测
  • 信号传播有时延，监听信道空闲，但信道可能并非真正空闲
  • 每个站点在自己发送数据到达终点之前都存在碰撞的可能性

• 总线上的单程端到端传播时延记为$\tau$
• 至少在$2\tau$时刻收到回来的信号才是没有发送碰撞(B马上回送信号)
• A只有在发送之后收到信号才知道是否发生了冲突
• 在使用CSMA/CD协议时，一个站不能同时发送和接收，但是必须边发送边监听信道（半双工通信）
• 每一个站在自己发送数据之后的一小段时间内，存在着遭遇碰撞的可能性。以太网不能保证在检测到信道空闲后的某一时间内，一定能够把自己的数据帧成功地发送出去。以太网的这一特点称为发送的不确定性。
• 在发送数据帧后至多经过时间$2\tau$就可知道所发送的数据帧是否遭受了碰撞。因此以太网的端到端往返时间$2\tau$称为争用期(contention period)
  • 争用期又称为碰撞窗口(collisionwindow)。
  • 经过争用期这段时间还没有检测到碰撞，才能肯定这次发送不会发生碰撞。
  • 基本退避时间为争用期$2\tau$，具体的争用期时间是51.2 us。
    • 对于10 Mbit/s 以太网在争用期内可发送512比特，即64字节。
    • 也可以说争用期是512比特时间。
      • 1比特时间就是发送1比特所需的时间。
      • 可以直接使用比特作为争用期的单位。
    • 争用期是512比特，即争用期是发送512比特所需的时间。
    • 发送的数据量小于512比特，说明一定发送碰撞（未过争用期）
      • 因为有站点在$\tau$时间内就发送了信息
  • 以太网在发送数据时，若前64字节没有发生冲突，则后续的数据就不会发生冲突。所有以太网规定了最短有效帧长为64字节。凡长度小于64字节的帧都是由于冲突而异常中止的无效帧，应当立即将其丢弃。
  • 理论上，以太网的最大端到端长度约为5 km(电磁波信号1km大勺需要5us，一半争用期 t =25.6 us) 。
    • 如果长度大于5km，收到回来的信号刚好在发送完信息之后，则会认为没有发送碰撞
• 碰撞后什么时候重传
  • 采用截断二进制指数退避确定。
  • 发生碰撞的站停止发送数据后，要退避一个随机时间后再发送数据。
    • 基本退避时间$2\tau$
    • 从整数集合[0,1,…,(2^k-1)]中随机取出一个数，记为r，重传所需的时延为T = r X 基本退避时间
    • 参数k = Min[重传次数,10]
    • 当重传达16次仍不能成功时即丢弃该帧，并向高层报告。
• 强化碰撞
  • 当发送数据的站一旦发现发生了碰撞时，除立即停止发送数据外，还要再继续发送32比特或48比特的人为干扰信号，以便让所有用户都知道现在已经发生了碰撞，阻止其他用户发送信号。
    • 对于10 Mbit/s以太网，发送32 (或48）比特只需要3.2(或4.8) us。
    • 帧间最小间隔为9.6us，发送一个帧等9.6us看是否发生了碰撞（48比特的数据发送到达对方最晚自己收到会送的信号知道碰撞需要9.6us）
  • 
• CSMA/CD重要特性
  • 使用CSMA/CD协议的以太网不能进行全双工通信而只能进行双向交替通信半双工通信)
    • 进行全双工通信，一个信道双方同时发送信息一定碰撞
  • 每个站在发送数据之后的一小段时间内，存在着遭遇碰撞的可能性
  • 这种发送的不确定性使整个以太网的平均通信量远小于以太网的最高数据率。
    • 先听后发、边听边发、冲突停止、延迟重发

3.3.3 使用集线器的星形拓扑

• 传统以太网传输媒体的变化过程
  • 粗同轴电缆 => 细同轴电缆 => 双绞线
• 使用双绞线作为传输媒体的以太网采用星形拓扑结构
  • 在星形的中心则增加了一种可靠性非常高的设备，叫作集线器(hub)
  • 
• 10BASE-T以太网
  • “10”代表10 Mbit/s的数据率
  • BASE表示连接线上的信号是基带信号
  • T代表双绞线
  • 每个站到集线器的距离不超过100 m（一般默认双绞线的最远传输距离为100m）
• 集线器的特点
  1. 由于集线器使用电子器件来模拟实际电缆线的工作，所以使用集线器的以太网在逻辑上仍是一个总线网，仍让是总线型共享信道的方式
     • 各站共享逻辑上的总线
     • 使用的还是CSMA/CD协议（各站中的适配器执行CSMA/CD 协议)。
     • 网络中的各站必须竞争对传输媒体的控制，并且在同一时刻至多只允许一个站发送数据。
  2. 一个集线器有许多端口，用两对双绞线与一台计算机上的适配器相连，即发送和接收各使用一对双绞线
  3. 集线器工作在物理层，它的每个端口仅仅简单地转发比特——收到1就转发1，收到0就转发0，不进行碰撞检测。
     • 若两个端口同时有信号输入（即发生碰撞)，那么所有的端口都将收不到正确的帧。
  4. 集线器采用了专门的芯片，进行自适应串音回波抵消，可使端口转发出去的较强信号不致对该端口接收到的较弱信号产生干扰(这种干扰即近端串音)。
  • 

3.3.4 以太网的信道利用率

• $T_0$为发送帧所需的时间
• $2\tau$为争用期
• 成功发送一个帧需要占用信道的时间为$T_0+\tau$
  • 如果在本站点发送信息的过程中，如果有别的站点发送了信息，到达本站点所需的时间至多为$\tau$，所以只要$T_0+\tau$没有收到碰撞信号就是发送成功
• 在以太网中定义了参数a
  • 参数a是以太网单程端到端时延$\tau$与帧的发送时间$T_0$之比
  • $a=\frac{\tau }{T_0}$
  • 当a→0时，表示只要一发生碰撞，就立即可以检测出来，并立即停止发送，因而信道资源被浪费的时间非常非常少。
  • 反之，参数a越大，表明争用期所占的比例越大，这就使得每发生一次碰撞就浪费了不少的信道资源，使得信道利用率明显降低。
  • 以太网的参数的值应当尽可能小些。
• 当数据率一定时，以太网的连线的长度受到限制(否则$\tau$的数值会太大)，同时以太网的帧长不能太短(否则$T_0$的值会太小，使a值太大)。
• 极限信道利用率$S_{max}$
  • 假定以太网上的各站发送数据都不会产生碰撞，并且总线一旦空闲就有某一个站立即发送数据。
  • 发送一帧占用线路的时间是$T_0+\tau$，帧本身的发送时间是$T_0$
  • $S_{max}=\frac{T_0}{T_0+\tau }=\frac{1}{1+a}$
  • 只有当参数a远小于1才能得到尽可能高的极限信道利用率

3.3.5 以太网的MAC层

1. MAC层的硬件地址

• 硬件地址又称为物理地址或MAC地址
  • 该地址使用在MAC帧中
• 每个适配器都有一个MAC地址，相当于该适配器的标识符，与其所处的位置无关
  • MAC地址固化在适配器的ROM中
  • 一个网卡提供一个接口，一个网卡有一个对应的MAC地址，所以每个接口都有一个与之对应得MAC地址

• IEEE 802 标准规定MAC地址字段采用6字节(48位)