基本概念
- 结点：主机，路由器
- 链路：两个结点之间的物理通道
- 数据链路：两个节点的逻辑通道
- 帧：链路层协议数据单元，包装网络层数据报告
一、 链路层的功能
链路层的主要作用是 加强物理层传输原始比特流，将物理层提供的可能错误的物理连接转化为
功能：
- 1.(将源机中网络层的数据传输到目的机的网络层)
- ：发送数据帧时无需建立链路连接，收到时无需发回确认。丢失的帧不会重新发送，交给上层。用于实时通信/误码率低的通信通道，如
- ：如果源机在规定时间内未收到确认信号，则重新传输丢失的帧，以提高传输的可靠性。适用于无线通信等误码率高的信道。
- ： 建立数据链路 – 传输帧 – 释放数据链路。在发送下一帧之前，目的机器应确认收到的帧。最可靠性
- 2.，即建立、维护和释放连接。用于连接服务
- 3.(封装成帧)
- 4.(限制发送方)
- 5.(帧错/位错)
功能一：封装成帧
将首部和尾部添加到一段数据的前后部分，形成帧。第一个尾部作用:确定帧的界限(帧定界) 
组帧要求：实现数据
： 数据链路层不知道数据内容 数据中出现与控制信息相同时，应采取措施让接收方不会误认，保证透明传输
| 组帧方法 | 介绍 | 特点 |
|---|---|---|
| 1. | 一个错 | |
| 2. | 如果控制信息出现在帧中，则在其前添加转义字符(1Byte） | |
| 3. | 使用01111110为了防止数据中的标志帧开始和结束01111110被误判 |
传输数据中的任何比特组合都不会导致边界判断错误 |
| 4. | 为高-低1，低-高0。“高-高”/"低-低"在数据比特中，电平是非法的 |
常用比特填充和非法编码法
功能二:错误控制(检错/纠错) 编码）
大多数错误是由噪声引起的
| 噪声类型 | 产生原因 | 解决方法 |
|---|---|---|
| 全局性 | 线路本身的电气特性产生（固有的） | 提高减少干扰(从传感器开始) |
| 局部性 | 外部特定的短暂原因(错误的主要原因) | 利用解决 |
“”： 接收端收到发送端发送的东西
有帧错和位错。
| 差错控制 | 解释 |
|---|---|
| 奇偶校验码 | 在信息前添加校验码，使1的数量为奇数/偶数 |
| CRC循环冗余码 | 数据后加0，不同或除以多项式，余数添加到数据后 |
| 海明码(检错&纠错） | 2 r ≥ k r 1 2^r \geq k r 1 2r≥k+r+1在2的幂数位添加校验码，使校验码与其要校验的数据位异或=0，算出校验码纠错：异或后算出1，从高到低排列的数大小即出错的数据位 |
功能三：流量控制
防止较高的发送速度与较低的接受能力不匹配造成传输出错（丢包）
| 数据链路层 | 传输层 |
|---|---|
| 点对点（每两个相邻节点之间） | 端到端（两个主机之间） |
| 接收方收不下就不回复 | 接收端给发送端一个窗口公告 |
| 控制协议 | 解释 | 规定窗口大小 |
|---|---|---|
| 停止等待协议 | 1.每发送一个帧就停止，等对方确认收到后再发下一帧2.超时未收到ACK则重传3.对收到的重复ACK/数据帧，丢弃 | 发送窗口=1,接收窗口=1 |
| 后退N帧协议( | 发送窗口>1,接收窗口=1（发送窗口每收到一个确认前进一格） | |
| 选择重传协议( | 单个确认 | 发送窗口=接收窗口= 2 n − 1 2^{n-1} 2n−1（n为 l o g 2 帧 数 log_2帧数 log2帧数） |
二、链路层的两种信道
传输数据使用的两种链路：
- 点对点链路：两个相邻结点通过一个链路相连。应用：PPP协议、广域网
- 广播式链路：所有主机共享通信介质。应用：局域网
（采取一定的措施，使每个节点与其他节点的信号隔离，不会互相干扰）
- - 信道划分介质访问控制 MAC协议
- 频分多路复用 FDM
- 时分多路复用 TDM - （统计时分复用 STDM）
- 波分多路复用 WDM
- 码分多路复用 CDM
-
- 轮询访问介质控制 令牌传递协议
- 随机访问介质控制
- ALOHA协议
- CSMA协议
2.1 静态划分信道
：将每个设备与该信道上的其他设备的通信隔离开，把时域和频域合理分配给网络上的设备
：把多个信号组合在一条物理信道上传输，使多个设备共享信道资源，提高信道利用率
| 静态划分信道的方法 | 工作 | 特点 |
|---|---|---|
| 频分多路复用 | 所有用户的同一时间占用不同带宽（频率）的资源（”并行“） | 充分利用传输介质的带宽，系统效率高。由于技术成熟，实现较为容易 |
| 时分多路复用 | 每一用户在TDM帧中占用固定序号的时隙，轮流占用信道（”并发“） | 改进的时分复用 - 统计时分复用 STDM：不固定分配时隙，而按需动态分配 |
| 波分多路复用 | 在光纤中传输多种不同波长（频率）的光信号 | 光的频分多路复用 |
| CDMA是码分复用的一种方式 | 1. 每一站点被指定唯一的m位芯片序列（表示1），取反码表示02. 多个站点的芯片序列相互正交（规格化内积=0）3. 合并：各路数据在信道中线性相加4. 分离：合并的数据与源站规格化内积 | 既共享信道的频率又共享时间。频谱利用率高、抗干扰强、保密强。用于无线通信系统，尤其是移动通信系统 |
例1（正交）：A站码片序列
10011110，则B站可选用码片序列为01010111A的序列表示为+1-1-1+1+1+1+1-1，当B为-1+1-1+1-1+1+1+1时，对应位乘积和➗位数 为0，是正交的 例2（分离）：若C收到序列2,0,2,0,0,-2,0,-2,0,2,0,2，而A的码片序列为1,1,1,1，则A发送的数据是101对应位乘积和 ➗ 位数
2.2 动态划分信道
动态媒体介入控制/多点控制：信道并非在用户通信时固定分配
2.2.1 随机访问介质 访问控制
- 1.
纯ALOHA协议：所有用户可随机发送信息，发送时占全部带宽。由于没有冲突监听，若发生冲突，接收方不予确认，发送方。超时重传
时隙ALOHA协议：将时间分成若干相同的时间片，所有用户在时间片开始时才能发送，若
纯ALOHA协议比时隙ALOHA吞吐量更低，效率更低
- 2.：发送帧之前，先监听信道
| CSMA协议 | 信道空闲时 | 信道忙时 | 优点 | 缺点 |
|---|---|---|---|---|
| 1-坚持CSMA | 直接传输 | 一直监听，直到空闲则传输 | 只要空闲就发送，避免了媒体利用率的损失 | 若多个站点要发数据，则冲突不可避免 |
| 非坚持CSMA | 直接传输 | 放弃监听，等一个随机时间后再监听 | 采用随机的重发延迟时间，减少发生冲突的可能性 | 可能存在大家都在延迟等待过程，使媒体处于空闲，使用率低 |
| p-坚持CSMA | 以p概率直接传输，以1-p概率等到下一时间槽再传输 | 放弃监听，等一个随机时间后再进行监听 | 减少冲突，又减少媒体空闲时间 | 发生冲突后依然坚持发送数据帧，造成浪费 |
：发前监听，发送时也监听信道 最多经过 2 τ 2\tau 2τ时间(两倍的总线端到端传播时延) 还没检测到碰撞，就肯定未碰撞 确定重传时机：
2.2.2 轮询访问访问MAC协议
主节点轮流 询问 从属节点是否发送数据。 缺点：产生轮询开销，存在等待延迟，主节点的单点故障
令牌：一个特殊格式的MAC控制帧，控制信道的使用 缺点：产生令牌开销，存在等待延迟 应用于令牌环网（物理星形拓扑、逻辑唤醒拓扑），负载较重，通信量大的网络中。
三、局域网LAN、广域网
在某一区域内由多台计算机联成的计算机组，使用 决定局域网的主要要素：
- 1.网络拓扑结构 星型拓扑、环形拓扑、树形拓扑、总线型拓扑（常用）
- 2.传输介质
- 有线局域网 ： 双绞线、同轴电缆、光纤
- 无线局域网 ： 电磁波
- 3.介质访问控制方法
- CSMA/CD
局域网分类
| 按介质访问方法 | |
|---|---|
| 以太网 | |
| 令牌环网 | / |
| FDDI网 | 光纤 |
| ATM网 | |
| 无线局域网 WLAN | 采用IEEE 802.11标准 |
四、链路层的设备
4.1 物理层扩展以太网 光纤、主干集线器
4.2 链路层扩展以太网
| 根据MAC帧的目的地址进行转发和过滤 | |
|---|---|
|
以太网的站点不知道所发送的帧会经过哪些网桥 |
|
发送帧时将详细的最佳路由信息（路由最少/时间最短）放在帧首部 |
- 多接口网桥
- 直通式交换机：查完地址就立刻转发
- 存储转发式交换机：将帧放入高速缓存，并检查是否正确，正确转发，错误丢弃
：同一时间只有一台设备发送信息的范围 ：若站点发送一个广播信号，所有内接受到信号的设备的范围
补充说明：
- 1. 计算冗余码步骤1.加0 2.模2除法 3.D加余数 FCS的生成及接收端CRC的检验都由硬件实现 （凡是接收端数据链路层接收的帧均无差错） 能实现无比特差错的传输，但并不是可靠传输（发什么就收什么）
发送的数据D为1101011011，采用CRC校验，生成多项式G为10011，则最终发送的数据是？
- 加0：10011表示成多项式为 x 4 + x 1 + x 0 x^4+x^1+x^0 x4+x1+x0，阶r为4。（在发送数据后加四个0）
- 模2除法：加0后的数据除以多项式（），余数为冗余码/FCS/CRC检验码的比特序列
- 最终发送： 源数据D* 2 r 2^r 2r+②中的FCS
- 接收端检错过程：将收到的每一帧除以同样的除数，若余数为0则无差错，否则有错
- 2. 发现双比特错，纠正单比特错
- 第一步：确定校验码位数r 海明不等式 2 r ≥ k + r + 1 2^r \geq k + r+ 1 2r≥k+r+1（k为信息位数）
- 第二步：确定校验码和数据的位置（校验码放在2的几次方的位置）
- 第三步：求出校验码的值（校验位与其要校验的数据位 异或=0）
- 第四步：检错并纠错 令所有要校验的位异或运算，得到的二进制序列就是出错位置
例：D=101101
- 2 r > = 6 + r + 1 2^r>=6+r+1 2r>=6+r+1 可求r为4
- P 1 ( 1 ) , P 2 ( 2 ) , P 3 ( 4 ) , P 4 ( 8 ) P_1(1), P_2(2), P_3(4), P_4(8) P1(1),P2(2),P3(4),P4(8)
- P 1 D 1 D 2 D 4 D 5 = 0 可 得 P 1 = 0 P_1 D_1 D_2 D_4 D_5 = 0可得P_1 = 0 P1D1D2D4D5=0可得P1=0
- 3.
丢包：物理线路故障、设备故障、病毒攻击、路由信息错误等原因导致数据包的丢失
发送窗口大小=接收窗口大小=1
- 1.无差错
- 2.有差错情况
- 1.数据帧丢失或检测到帧出错
- 2.ACK（确认帧）丢失：丢弃重复的1帧，重传确认帧
- 3.ACK迟到：丢弃
信 道 利 用 率 = L / C T 信道利用率=\frac{L/C}{T} 信道利用率=TL/C：发送方在一个发送周期内有效发送数据所占时间占{发送第一帧到收到第一个确认帧的时间}的比率
例：一个信道的数据传输率为4kb/s，单向传播时延为30ms，要使停止-等待协议的信道利用率达到80%，则要求数据帧长度至少为？ L / 4 L / 4 + 2 ∗ 30 = 80 % \frac{L/4}{L/4+2*30} = 80\% L/4+2∗30L/4=80%(忽略 T A T_A TA)
信道吞吐率 = 信道利用率 * 发送速率 改善停等协议：需要增加序号范围，发送方需要缓存多个分组
GBN协议（后退N帧协议）
的长度过大会使接收方无法区分新帧与旧帧 ，应满足 1 ≤ W t ≤ 2 n − 1 1 \leq W_t \leq 2^n -1 1≤Wt≤2n−1 ：收到n号帧的确认，表明接收方已收到n号及之前全部帧 ：出现超时，则重传所有已发送但未确认的帧
SR选择重传协议
GBN中，接收方丢弃一些帧，而导致接收方批量重传这些帧，而SR只重传出错的帧。加大接收窗口，单个确认
最好使 发送窗口=接收窗口（大了会溢出，小了没意义） W T m a x = W R m a x = 2 ( n − 1 ) W_Tmax = W_Rmax=2^{(n-1)} WTmax=WRmax=2(n−1)