数据链路层的功能
数据链路层的地位
数据链路层使用物理层提供的“比特传输”服务
数据链路层为网络层提供服务，将网络层的IP数据报（分组）封装成帧，传输给下一个相邻结点
物理链路：传输介质（第0层）+ 物理层（第1层）实现了相邻结点之间的“物理链路”
逻辑链路：数据链路成需要基于“物理链路”，实现相邻结点之间逻辑上无差错的“数据链路（逻辑链路）”
功能介绍
组帧（封装成帧）
帧定界：如何让接收方能够确定帧的界限
透明传输：接收方链路层可以从收到的帧内恢复原始SDU，让网络层感受不到将分组封装成帧的过程
差错控制
发现并解决一个帧内部的“位错”
可靠传输
发现并解决“帧错”，包括：帧丢失、帧重复、帧失序
流量控制
控制发送方发送的速率不要太快，能够让接收方来得及接受发过来的所有帧
介质访问控制
“广播信道”需要实现此功能，广播信道在逻辑上是总线型拓扑，多个结点需争抢传输介质的使用权
“点对点信道”通常不需要实现此功能。点对点信道通常意味着两个结点之间有专属的传输介质，不用抢
组帧
字符计数法
帧长 = 计数字段长度 + 帧的数据部分长度
原理：在每个帧开头，用一个定长计数字段表示帧长
缺点：任何一个计数字段出错，都会导致后续所有帧无法定界
字节填充法
特殊字符：标记帧开头的字符SOH；标记帧结尾的字符EOT；转义字符ESC
如个帧的数据部分包含特殊字符，发送方需要在这些特殊字符之前填充转义字符，接收方需要做逆处理
零比特填充法
用特殊的比特串01111110标记帧开头、帧结尾；发送方需要对帧的数据部分进行处理，每遇到连续的5个1，就填充1个0；接收方需要对帧的数据部分进行逆处理，每遇到连续的5个1，就删除后面的1个0
违规编码法
使用“违规信号”表示帧开头、帧结尾（需要物理层的配合）
如：采用曼彻斯特编码时，使用“中间不跳变”作为“违规信号”，标记帧的开头和结尾
差错控制
差错控制：主要解决一个帧内部的“位错”
检错编码
帮助接受方发现比特错误，丢弃帧，并通知发送方重传帧
奇偶校验码
奇校验码：整个校验码（有效信息位和校验位）中“1”的个数为奇数
偶校验码：整个校验码（有效信息位和校验位）中“1”的个数为偶数
一般采用偶校验码，因为偶校验易于硬件实现：只需将各信息位进行异或，得到的结果即为偶校验位；对受到的数据进行偶校验，只需对所有位进行异或，若结果为1说明出错
CRC校验码
循环冗余校验码的基本思想：数据的发送方和接收方约定一个“除数”，将K个信息位+R个校验位作为“被除数”，添加校验位后需要保证除法（模2除）的余数为0，收到数据后，进行除法检查余数是否为0，若不为0，则证明出错
纠错编码
帮助接收方发现并纠正比特错误
海明校验码
基本思想：分组偶校验，多个校验位可以反映出出错位置
步骤
确定校验位个数：2k >= n + k +1
确定校验位分布：P1、P2、P3...分别在1,2,4,8,16...;空出来的位置依次填入信息位
将信息位的位置序号用k位二进制数表示出来；校验位Pi与位置序号为第i位为1的信息位归为同一组，进行偶校验
对P1、P2、P3...所属各分组进行异或（相当于分组偶校验），求得S1、S2、S3...；S1 S2 S3 = 000说明无错误；S1 S2 S3 != 000说明有错误
海明码有1位纠错，2位检错能力；为了区分1位错和2位错，还需添加“全校验位”对整体进行ou偶校验
可靠传输与流量控制
可靠传输：发现并解决“帧错”
流量控制：控制发送方发送帧的速率别太快
滑动窗口机制
发送窗口（Wt）：发送方只能发送窗口内的帧
接收窗口（Wr）：接收方只能接收窗口内的帧
发送窗口之外的帧，暂不允许发送；接收方若收到接收窗口之外的帧，直接丢弃；接收方通过“确认机制”控制发送方的窗口向前滑动，从而实现流量控制
确认机制
确认帧（ACK_i）：若接收方收到i号帧，且没有检测出“差错”，需要给发送方返回确认帧ACK_i
否认帧（NAK_i）：若接收方收到i号帧，但检测出i号帧有“差错”，则需要丢弃该帧，并给发送方返回否认帧NAK_i
重传机制
超时重传：若发送方超时未受到ACK_i，则重传i号帧
请求重传：若发送方收到接收方返回的NAK_i，则重传i号帧
帧编号
Wt + Wr <= 2n
停止-等待协议（S-W）
滑动窗口机制：Wt = 1；Wr = 1
确认机制：引入确认帧
重传机制：引入超时重传
帧编号：仅需1比特
若接收方收到重复帧（例如接收方发送的ACK丢失，发送方超时重传），此时帧序号落在接收窗口之外，接收方会先丢弃重复帧，再返回重复帧的ACK
若接收方检测出接收到的帧出现差错，此时接收方会直接把这个帧丢弃，且不返回ACK，发送方就会因为超时重传，重新发送这个帧
后退N帧协议（GBN）
滑动窗口机制：Wt > 1；Wr = 1
确认机制：引入确认帧
重传机制：引入超时重传
帧编号：Wt + Wr <= 2n
关于确认帧：接收方可以“累计确认”，即连续接收到多个数据帧时，可以仅返回最后一个帧的ACK，代表已经接收到该帧以及该帧之前的所有帧
关于超时重传：如发送方超时未受到ACK_i，则重传i号帧以及之后的所有帧
当接收方收到落在接收窗口之外的帧或检测出差错的帧时，接收方会丢弃此帧，并返回目前已经接收到的最后一个正确帧的ACK，以提醒发送方后退回i + 1号帧重传
选择重传协议（SR）
滑动窗口机制：Wt > 1；Wr > 1；Wr <= Wt
确认机制：引入确认帧、否认帧
重传机制：引入超时重传、请求重传
帧编号：Wt + Wr <= 2n
SR协议不支持“累计确认”，必须一帧一确认
三种协议的信道利用率分析
介质访问控制
介质访问控制
多个节点共享同一个“总线型”广播信道时，可能发生“信号冲突”，此时就需要介质访问控制
信道划分
时分复用（TDM）
原理：将时间分为等长的“TDM”帧，每个“TDM”帧又分为等长的m个“时隙”，将m个时隙分配给m对用户（节点）使用
缺点：
每个节点最多只能分配到信道总带宽的1/m
如果某节点暂不发送数据，会导致被分配的“时隙”闲置，信道利用率低
统计时分复用（STDM）
又称异步时分复用，即在TDM的基础上，动态按序分配时隙（通过统计每个节点对信道的使用需求，动态按需分配时隙）
优点：
如果需要时，一个节点可以在一段时间内获得所有的信道带宽资源
如果某节点暂不发送数据，可以不分配“时隙”，信道利用率更高
频分复用（FDM）
原理：将信道的总频带划分为多个子频带，每个子频带作为一个子信道，每对用户使用一个子信道进行通信
优点：各节点可以同时发送信号，充分利用了信道带宽
缺点：FDM只能用于模拟信号的传输
波分复用（WDM）
即光的频分复用
码分复用（CDM）
给各节点分配专属“码片序列”，“码片序列”包含m个码片（信号值），可看作“m维向量”；为了便于从叠加信号中分离出各个节点的信号，各节点的“m维向量”必须相互正交
节点发出m个信号值，与“码片序列”相同，表示比特1,相反表示信号0
当多个发送方同时发送数据时，信号值会叠加
接收方收到的是叠加的信号，需要从中分离出各发送方的数据（通过叠加信号与发送方码片序列作“规格化内积”，结果为1表示比特1,结果为-1表示比特0）
随机访问
纯ALOHA
时隙ALOHA
CSMA协议
CSMA协议，即载波监听多路访问协议，CSMA协议在ALOHA协议的基础上提出改进，在发送数据之前，先监听信道是否空闲，只有信道空闲时，才会尝试发送数据
1-坚持CSMA协议
非坚持CSMA协议
p-坚持CSMA协议
CSMA/CD协议
一般用于有线网络
特点：先听后发，边听边发，冲突停发，随机重发
争用期：一个节点最多需要花多久可以确定自己已经占用了整个信道
争用期 = 2 x 最大单向传播时延（最大RTT）
最短帧长 = 2 x 最大单向传播时延 x 信道带宽
若收到的帧小于最短帧长，视为无效帧；如果A节点发送的数据帧长度小于最短帧长，可能会导致A节点误认为发送过程中没有发生冲突
最长帧长：规定最长帧长可防止某些节点一直占用信道
以太网规定：最短帧长 = 64B，最长帧长 = 1518B
如何随机重发：随机等待时长 = r倍争用期（争用期是一段固定大小的时间），其中r是随机数
如果k <= 10，在[0，（2k - 1）]区间随机取一个整数r
如果k > 10，在[0，（210 - 1）]区间随机取一个整数r
特别注意
第10次冲突，是“随机重发”的分水岭，大于10次随机数r的取值区间就不会再发生变化
第16次冲突，直接躺平，放弃传帧，报告网络层
CSMA/CD协议中没有ACK机制，若发送过程中未检测到冲突，就认为帧发送成功
CSMA/CA协议
一般用于无线网络
特点：先听后发，忙则退避
DIFS：最长的帧间间隔；DIFS > 传播时延 + SIFS（这样可以保证信道是空闲的）
SIFS：最短的帧间间隔；预留SIFS用于处理受到的帧（差错控制等）
过程：若亲到空闲，间隔DIFS后，再发送帧（一口气发完，发送过程中不用检测冲突）；若信道不空闲，则进行“随机退避”
随机退避原理：用二进制指数退避算法确定一段随机退避时间（倒计时）；发送方会保持监听信道，只有信道空闲时才“扣除倒计时”，倒计时结束后立即发送帧
接收方：每收到一个正确数据帧都返回ACK，若发送方超时未受到ACK，则进行“随机退避”
通过信道预约机制可以解决“隐蔽站”问题
发送方广播RTS控制帧（先听后发，忙则退避）
AP广播CTS控制帧
其他无关节点收到CTS后自觉“禁言”一段时间（虚拟载波监听机制），发送方受到CTS后，就可以发送数据帧
AP收到数据帧后，进行CRC校验，若无差错就返回ACK帧
注：若超时未收到CTS，说明预约失败，则“随机退避”后再次RTS预约；“先预约，再发送”这种模式可以启用，也可以不启用（数据帧较短没有必要启用）
轮询访问
令牌环网技术：由IBM公司开发的一种局域网技术
核心特点：环形拓扑结构，各节点“轮询访问”信道，不会发生信道冲突
令牌传递协议
令牌帧
需要指明当前获得令牌的节点编号；
只有获得令牌的节点才能往信道上发送数据；
如果获得令牌的节点没有数据要发送，就将令牌传递给下一个节点
数据帧
需指明数据帧的源地址/目的地址、是否已被接受、获得令牌的节点编号；
数据帧从源结点发出，传递一圈后回到源结点；
数据帧传递一圈过程中，会被目的节点复制一份数据，并将数据帧标记为“已接受”；
数据帧回到源结点后，如果发现异常状况，就会尝试重发，若无异常，就将令牌传递给下一个节点
其他
无论是令牌帧还是数据帧，都只能沿单向传递
获得令牌的节点，每次只能发一帧，发完就释放令牌
需要用专门的网络设备（MAU）实现集中控制
令牌传递协议很适用于负载高的网络（不会发生冲突、效率高）
局域网
以太网 ---> IEEE 802.3
无线局域网 ---> IEEE 802.11
VLAN ---> IEEE 802.1Q
局域网的特点
覆盖较小的地理范围
较低的时延和误码率
局域网内的各节点之间以“帧”为单位进行传输
支持单播、广播、多播
局域网的分类（重点关注：拓扑结构、传输介质、介质访问控制方式）
有线局域网
令牌环网
环形拓扑
同轴电缆或双绞线
令牌传递协议
以太网
同轴电缆以太网
总线形拓扑
同轴电缆
CSMA/CD
光纤以太网
点对点拓扑（用于中继器/集线器/交换机之间的传输，通常不会直接连接终端节点）
光纤
NULL（用两条光纤实现全双工通信）
双绞线以太网
用集线器连接
物理上和逻辑上都是总线形拓扑
双绞线
CSMA/CD
用交换机连接
物理上和逻辑上都是星形拓扑
双绞线
CSMA/CD（半双工）、NULL（全双工）
无线局域网
WiFi/802.11
IEEE 802.11定义为星形（1个AP + N台移动设备）
无线（Wireless）
CSMA/CA
局域网的硬件架构
ROM中保存有全球唯一的MAC地址（物理地址，48bit）
RAM用于帧缓冲
网络适配器要点
负责把帧发送的局域网
负责从局域网接受帧
需要根据接入的局域网类型，按照标准实现数据链路层 + 物理层功能
需要完成数据的串/并行转换
需要支持帧缓冲
以太网与IEEE802.3
冲突域：如果两个节点同时发送数据，会导致冲突，则二者处于同一个“冲突域”
广播域：如果一个节点发送广播帧，可以被另一个节点接受，则二者处于同一个“广播域”
集线器既不隔离冲突域，也不隔离广播域
交换机隔离冲突域，不隔离广播域
路由器既隔离冲突域，也隔离广播域
物理层标准
MAC层标准
VLAN与IEEE 802.1Q
在大型的局域网中，整个局域网是一个很大的广播域，容易出现广播风暴，不利于信息安全，因此提出了VLAN
VLAN的特点
可以将一个大型的局域网分割成若干较小的VLAN，每个VLAN是一个广播域
需要使用支持VLAN功能的以太网交换机来实现
每个VLAN对应一个VID
VLAN划分方式
基于接口：VID <---> 接口号
基于MAC地址：VID <---> MAC地址
基于IP地址：VID <---> IP地址
802.1帧
在标准以太网帧的基础上增加了4个字节的VLAN标签
6 6 4 2 N 4，收发V协数验
无线局域网与IEEE 802.11
基本概念
802.11无线局域网是星形拓扑，中心成为接入点（AP），也可成为无线接入点（WAP）
服务集标识符（SSID）：服务集名称
基本服务区（BSA）：服务集范围
基本服务集（BSS）：1个基站 + N个移动站
拓展服务集（ESS）：将多个AP连接到同一个分配系统，组成一个更大的服务集
漫游：从一个AP切换到另一个AP，且通信继续保持，不中断
门户（POrtal）：可将802.11无线局域网接入802.3有线以太网
802.11帧的分类
数据帧
控制帧
如ACK、RTS、CTS帧
管理帧
如探测请求/探测响应帧
广域网（WAN）
特点：覆盖范围广，几十公里到几千公里
主要任务：长距离运送主机所发送的数据；将分布在各地方的局域网互联起来
WAN各节点之间通常是点对点高速链路
PPP协议（点对点协议）
点对点协议是目前最流行的点对点链路控制协议。主要有两种应用场景：用户接入互联网时与ISP之间的通信；两台网络设备之间通过直连专线通信
PPP协议的组成
链路控制协议（LCP）：负责数据链路本身的建立、配置、测试、维护和终止
网络控制协议（NCP）：在LCP成功建立并（可选）完成认证的数据链路上，负责特定网络层协议的配置和管理。
定义PPP帧格式
以太网交换机的工作原理
特点
交换机 = 多端口网桥
交换机工作在数据链路层，可以根据目的MAC地址转发帧
自学习功能（支持即插即用）
交换表：初始为空，记录[MAC地址，端口号]的对应关系
交换机每收到一个帧，就将“发送方”的[MAC地址，端口号]更新到交换表
若不知道“接收方”在哪里，就把帧广播到除入口外的其他端口
若知道“接收方”在哪里，就把帧精准转发至某个端口
交换表中每个表项都有”有效时间“，过期表项自动作废
两种交换方式
直通交换
只检查帧开头的目的MAC地址，以决定帧的转发端口
优点：转发时延低
缺点：不适用于需要速率匹配、协议转换或差错检测的线路
存储转发交换
先把帧完整接收到交换机内部的高速缓存中，进行差错检测等必要处理，在根据交换表决定从那个端口转发出去
优点：适用于需要速率匹配、协议转换或差错检测的线路
缺点：转发时延高