王道计算机网络—数据链路层

相关概念

• 节点：主机，路由器
• 链路：节点之间的物理通道，双绞线，光纤，微波；
• 数据链路：节点之间的逻辑通道，数据传输的硬件+软件
• 帧：链路层的数据单元，封装网络层的ip数据报；
• 网络适配器（网卡）：网卡拥有自己的处理器和内存，是一个半自治设备，介于计算机和网线之间，通过操作系统内核的网卡驱动和计算机交互，并且使用自己的处理器和内存接收和发送数据帧，不会占用计算机资源，收到数据会触发中断让CPU去执行网卡驱动;
• mac地址：用于介质访问控制，在网络适配器中固化的地址，ip地址是在计算机中，而mac地址是在网络适配器中

数据链路层功能：

数据链路层负责通过一条链路将数据报帧从一个节点传给与其物理相连的另一个节点，其最基本的服务是将源自网络层的数据可靠的传递给相连链路节点的网络层，加强物理层的传输功能，改进物理层的可能出错的物理连接，使之对网络层表现为一条无差错的链路

分装成帧：

数据链路层以帧为单位传输和处理数据，所以数据链路层必须将网络层传给它的ip数据报封装成帧,封装成帧就是在数据报的头和尾添加帧首部和帧尾部，帧首部和帧尾部的作用是进行帧定界

为了提高传输的效率，帧数据部分的大小应该尽可能大于帧首和帧尾的大小，但是数据链路层对帧数据的大小进行了限制，即：最大传送单元MTU

组帧的方式：

1. 字符计数法：

在帧首部设置一个帧长度字符

问题：如果一个帧出现问题，那么后面的所有帧都会无法确定

2. 字符填充法：

为帧设置一个帧首和帧尾字符，在帧的数据部分如果出现帧首和帧尾字符相同的数据，会影响帧定界的判定,就为它添加一个转义字符，这是实现透明传输的一个操作

3. 零比特填充法：

5110,在数据部分如果遇到五个连续的1，那么就在后面加上一个0，帧的首部和尾部都0111110

4. 违规编码法：

正常的编码方式使用的高低，低高代表1，0，我们可以使用违规编码方式，高高，低低用来给帧进行定界；

差错检测：

差错类型：

• 位错：比特位出错，1变成0，0变成1
• 帧错：帧丢失，帧重复，帧失序

差错控制措施：

1. 检错编码：

• 奇偶校验码

  
  

为数据加上一个校验位，使1的数量是奇数或者偶数，数据接收的时候判断1的个数的奇偶性是否改变；

特点：只能检测出奇数个比特错误，如果两个比特位发生错误，那么1的个数不会改变，错误将无法检测，检错能力为50%；

• 循环冗余码CRC

  
  

需要发送的数据和生成多项式计算，得到冗余码，实际发送的数据是需要发送的数据+冗余码；数据在接收时，将接收的数据和生成多项式相除，如果余数为0，说明没有发生改变

实际传输的数据 = 需要发送的数据 + 帧检验序列FCS(冗余码)

FCS冗余码的计算：

1. 加0：计算多项式的阶;多项式N位，阶为N-1,在数据的后面加上阶个0
2. 模2除法：数据加0后除以多项式，余数为冗余码;

FCS的生成和接收端CRC检测都是由硬件实现的，所以速度很快；CRC循环冗余技术只能做到对帧的无差错接收，错误的帧都会被丢弃；

2. 纠错编码：

• 海明码

海明码工作流程：

1. 确定校验码位数r

   
   

通过海明不等式求出校验码位数

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

校验码只能放在2的几次方的位置，剩下的数据按顺序放好

3. 求出校验码的值

• 首先要找到校验码需要校验的数据，校验码位置的二进制数的1如果数据在这个位置上也是1，那么这个校验码就校验这个数据，举个例子：
• 如果校验码的位置的二进制表示为0001，现在有多个数据，他们的位置表示为0011,0101,1000,1010，在数据中找和校验码相同位置同为1的数据，当前校验码校验的数据为0011,0101，因为他们的最低位同校验码都为1
• 找到校验码需要校验的数据后，在将他们的值（校验码和所有它校验的数据）一起异或等于0，就能通过这个等式得到校验码的值；

4. 检错并纠错

让所有的校验码，和自己校验的数据异或，然后从最后一个校验码开始算，得到的这个二进制数就是出错的那个数据的位置，比如：有四个校验码p1，p2，p3，p4；他们跟自己的数据异或得到1010，那么出错的数据就是0101这个位置，即第五个数据位；

冗余编码：在数据发送前，按照某种关系为数据附加上一定的冗余位，构成一定规则的码字，当数据发生变化时，冗余位也会变化，使码字保持不变，接收的时候会判断码字是否符合原规则，从而判断是否出错；

流量控制

停止 - 等待协议：

发送方在发出了一个分组后，会停下来等待接收方的确认，才会发送下一个分组；
超时重传：如果经过一段时间（一个RTT）还没有收到确认，就重传这个分组；

缺点：信道利用率低

回退N帧协议：GBN Go-back-N

发送窗口：发送方维持着一组连续的允许发送的帧序号；每收到一个确认，就会将滑动窗口前移，

接收窗口：接收方维持着一组允许接收的帧序号；

GBN特点：

• 接收方只按序接收帧，如果帧2丢失，收到了帧3，帧4，那么帧3，帧4会被丢弃；
• 发送方会采用超时重传机制，一旦某个分组出错，就重传后面所有的分组，这也是GBN名字的由来，一旦出错，退回去重传所有已经发送的N个分组；
• 接收方采用累计确认的方式，接收方不一定要对每一个分组进行逐个确认，而是在接收了几个分组后，对最后一个分组进行确认；

缺点：一个分组的丢失会造成大量分组的重传，而这些分组可能是被接收方正常接收的分组，影响传输的效率；

由此看来GBN只是在SW的基础上修改了发送方算法，没有改变接收方算法，接收窗口仍然为1，这样会导致大量分组重传

选择重传协议：SR Selective Repeat

改进了接收窗口的大小，方便接收失序但正确到达的分组，等所缺分组收集全了再交给上层；

传输数据使用的两种链路

1. 点对点链路PPP point-to-point protocol（广域网）
2. 广播式链路(局域网)

PPP协议特点：

1. 简单：使用PPP协议的数据链路层不需要纠错，不需要提供可靠服务，如需可靠传输，则由传输层实现
2. 封装成帧
3. 透明传输
4. 支持多种网络层协议：网络层传来的ip数据报可以采用多种协议
5. 支持多种类型链路：串行/并行，同步/异步，电/光
6. 差错检测
7. 检测链接状态
8. 最大传输单元：MTU
9. 网络层地址协商：PPP提供了一种机制使通信双方能知道彼此的网络层ip地址；

PPP协议的三个组成：

1. 一个将IP数据报封装到串行链路的方法

PPP既支持面向字符的异步链路，又支持面向比特的同步链路；

2. 链路控制协议 LCP协议 link-control-protocol

用来建立，配置和测试数据链路链接，身份验证

3. 网络控制协议 NCP协议 network-control-protocol

用来支持不同的网络层协议，每一个网络层协议都需要一个对应的NCP协议来配置，为网络层协议建立和配置逻辑链接

PPP协议的帧格式：

• F：帧首和帧尾
• A，C：预留字段，最初考虑留这两个字段进行其他定义，但是至今都没有给出
• 协议：标识信息部分的内容，IP数据报，LCP数据，网络层控制数据
• FCS：CRC循环冗余码的帧检验序列

PPP协议的工作流程：

这里以拨号接入为例：

1. 当用户拨号接通ISP拨号服务器后，就建立了一条从用户PC到ISP的物理连接,
2. 此时PC向ISP发送多个LCP分组（多个PPP帧形式）建立LCP连接；
3. 网络层配置
4. NCP为PC分配一个临时的IP地址

广播式链路（局域网）：

所有主机共享通信介质，当一个站点发送数据时，总线上的所有站点都能检测和接受这个数据，应用于早期的以太网，无线局域网，常用于局域网

介质访问控制技术：

介质访问的目的是采取一定措施，使两节点之间的通信不会发生干扰，介质访问控制主要有两种实现方式：

1. 静态划分信道

• 频分多路复用FDM：
  给用户分配不同频率的频带，在通信过程中，用户始终都占用这个频带，在各自的频带通信

  
  

• 时分多路复用TDM：
  将介质的使用分成多个时间片，用户轮流占用信道，类似进程并发占用CPU的时间片TDM帧标志着一个周期
  

  

• 码分多路复用CDM：
  先了解一下CDM中的新概念
  1. 芯片/码片：1个比特被分为m个更小的时间槽，称为码片，通常1比特被分成64或128个码片
  2. 芯片序列：每一个站点被指定一个唯一的m位的码片

CDM规定发送1比特就发送芯片序列，发送0比特就发送芯片序列的反码，为了站点发送的数据可以共享信道，CDM还规定了站点的芯片序列必须相互正交，相互正交就是规格内积化为0；规格化内积就是对应数据相乘再相加再除以数据的个数；

数据的合并：

各数据在信道中线性相加

数据的分离：

合并的数据和接受端的芯片序列规格化内积，规格化内积就是对应数据相乘再相加再除以数据的个数；

(101011)和（110011）规格内积化：（11+01+10+00+11+11）/ 6 = 0.5 , 这里的规格内积化不为0，所以不满足芯片序列的要求，这里是举例，正常的芯片序列为64或128位；

2. 动态划分信道

CSMA/CD协议：载波监听多点接入碰撞检测（carrier Sense multiple access with Collision detection）！考研重点！

• CS：Carrier Sense，载波监听，每个站在发送数据前以及发送数据时都要检测当前总线是否有其他计算机在发送数据
• MA：multiple access,多点接入，许多计算机（站点）以多点接入的方式连接在一根总线上，总线型网络
• CD：collision detection，碰撞检测，边发送边检测 网络适配器一边发送数据同时一边检测信道上电压的变化，以便判断自己在发送数据时其他站是否也在发送数据。

传播延时对载波监听的影响
重传机制
（十二点了，明天早上还要起来看操作系统，记一下，以后有时间再盘吧）
// 2020. 7.23 

局域网：

在某一区域内由多态计算机使用广播信道互联成的计算机组；

局域网的网络拓扑结构：

1. 星型拓扑

   
   

• 传输速度快，网络构建简单，便于控制和管理
• 网络可靠性低，如果集线器出现问题，所有站点都无法通信

2. 总线型拓扑

   
   

• 可靠性高，一个站点出现问题不会影响其他站点
• 设备成本低，使用方便

3. 环形拓扑

   
   

• 最蠢的拓扑方式，不说了

局域网传输介质：

• 有线：双绞线，光纤
• 无线：电磁波

数据链路层的组成：

• 逻辑链路控制子层LLC子层：
  LLC负责和网络层交互，为网络层提供服务：无确认无连接，确认无连接，确认连接
• 介质访问控制子层MAC子层：
  MAC负责和物理层交互：数据帧的封装和拆分，帧的寻址和识别，差错控制

以太网：

以太网是局域网的一种，采用CSMA/CD介质访问控制技术，是当今局域网最广泛的应用

特点：

1. 成本低
2. 是应用最广泛的局域网技术
3. 满足网络速率的需求，10m/s~10Gb/s
4. 无差错接收，不实现可靠传输

10BASE-T以太网

• 物理上采用星型拓扑结构，逻辑上采用总线型拓扑
• 采用曼切斯特编码
• 采用CSMA/CD介质访问控制协议

以太网的MAC帧：

• 类型：用于描述上层的协议
• 46-1500：46保证了以太网最小帧不能小于64b，因为CMSA/CD协议规定最远两端数据往返是征用期，为了在征用期内能检测到碰撞，规定最小不能小于64b；1500是MTU
• 数据帧尾是通过曼切斯特编码的电信号是否变化来判断的，帧和帧之间会有时间间隔

网桥和交换机

网桥：

网桥是数据链路层的设备，采用存储转发方式，根据MAC帧的目的地址对接收到的帧进行转发和过滤

两个以太网通过网桥连接起来后，成为一个覆盖范围更大的以太网，原来的以太网称为网段

网桥的优点：

1. 过滤数据，选择转发，提高吞吐量
2. 扩大通信范围
3. 提高可靠性：网桥不会转发错误的帧，网络出现故障只会影响个别网段
4. 可以连接不同物理层，不同mac层，不同速率的以太网

透明网桥：

局域网上的站点不知道所发送的帧将经过哪几个网桥，透明网桥即插即用，通过自学习算法逐步建立自己的转发表

源路由网桥：

在发送帧时，会将最佳路由信息放在帧首部，源站通过广播的方式向目的站发送一个发现帧

实践证明，即插即用的透明网桥最终取得了市场竞争的胜利，源路由网桥现在已经很少使用

交换机（多接口网桥）：

• 直通式交换机：接收到帧的时候立刻根据帧的MAC地址决定该帧的转发接口，转发延迟小，可靠性低，无法支持不同速率端口的交换

• 存储转发式交换机：将帧放入高速缓存，检查是否正确，错误则丢弃，延迟大，可靠性高，支持不同速率的端口交换