Chapter 3. 数据链路层
公式与性质
-
数据链路层的基本功能：封装成帧、透明传输、差错检测。
-
组帧
- 字符计数法：在帧首部使用一个计数字段来记录该帧所含的字节数（包含自身占用的 1 个字节）。
- 字节填充法：
Start of Header, SOH放在帧的最前面，End of Transmission, EOF放在帧的最后面，对源数据使用Escape Character, ESC转义源数据中与定界符相同的字段。 - 零比特填充法：使用
0111 1110标志一个帧的开始和结束。对源数据每遇到 5 个连续的1，就自动在其后插入一个0。 - 违规编码法：物理层。如曼彻斯特将 1 编码成"高-低"电平对，将 0 编码成"低-高"电平对，则"高-高"和"低-低"为违规编码，作为帧定界标志。
-
检错编码
- 奇偶校验码
- 奇校验码：附加一个校验位后，1 的个数为奇数。
- 偶校验码：附加一个校验位后，1 的个数为偶数。
- 循环冗余
Cyclic Redundancy Code, CRC码（单bit检错，可纠错但未使用）：k 阶生成多项式生成 r=k+1 位冗余码，附加在数据后。- 计算：附加 k 个
0在数据后，将数据与生成多项式的系数序列进行模二除法（相减即异或）所得余数即为CRC码。 - 若传输无差错，则余数为 0 。
- 传输出现差错时余数仍为 0 的概率极低，故可认为凡是数据链路层接收的帧均无差错。
- 计算：附加 k 个
- 海明码（单
bit纠错， 双bit检错）：- 海明码的信息位数 n 和检验位数 k 满足 n+k \le 2^k -1 。
-
H_7 H_6 H_5 H_4 H_3 H_2 H_1 D_4 D_3 D_2 D_1 P_4 P_2 P_1 - 检验位 P_i \ (i \ge 1) 在海明位号 H_i \ (i \ge 1) 为 2^{i-1} 的位置上。
- 被检验数据位的海明位号 D_i \ (i \ge 1) 等于检验该数据位的各检验位海明位号之和。
- 检验位的值为由该检验位检验的所有数据位求异或。
- 检验时由检验位和所有参与构成该检验位的数据位求异或。
S_1 = P_1 \oplus D_1 \oplus D_2 \oplus D_4 \\ S_2 = P_2 \oplus D_1 \oplus D_3 \oplus D_4 \\ S_3 = P_3 \oplus D_2 \oplus D_3 \oplus D_4- 若 S_1S_2S_3 的值为
000则无错，否则是出错的位号。
- 奇偶校验码
-
自动重传请求 ARQ协议发送窗口 W_T 接收窗口 W_R 停止等待协议 Stop-Wait, S-W=1 =1 后退 N 帧协议 Go-Back-N, GBN\gt 1 =1 选择重传协议 Selective Repeat, SR\gt 1 \gt 1 -
GBN协议对某个数据帧的确认帧Acknowledge, ACK就代表该数据帧和之前所有的帧都已正确无误地收到。若采用 n 比特对帧编号，则 1 \lt W_T \le 2^n -1 。当信道误码率较大时，不一定优于S-W。 -
SR协议一旦检测到某个数据帧出错，就立刻返回否定帧NAK要求重传。W_R + W_T \le 2^n, \ W_R \le W_T 。 -
发送方发送分组的发送时延 T_D ，往返时延 RTT ，接收方确认分组的发送实验 T_A ，则
S-W信道利用率 U=\frac {T_D}{T_D + RTT + T_A} ，发送窗口为 n 的连续ARQ（GBN，SR）信道利用率 U=\frac {nT_D}{T_D + RTT + T_A} -
信道划分介质访问控制
- 频分复用
Frequency Division Multiplexing, FDM - 时分复用
Time Division Multiplexing, TDM- 统计时分复用
Stastic TDM, STDM
- 统计时分复用
- 波分复用
Wavelength Division Multiplexing, WDM - 码分复用
Code Division Multiplexing, CDM- 不同站的码片序列相互正交，规格化内积为 0 。
- 收到的信息与码片序列的规格化内积为 1 则为
1，为 -1 则为0。
- 频分复用
-
随机访问介质访问控制
Additive Links Online Hawaii Area, ALOHA协议- 纯
ALOHA协议：随时发送，未收到确认即认为发生冲突，等待一段时间再发送。 - 时隙
ALOHA协议：同步各站点的时间，将时间划分成一段段等长的时隙slot，只有在每个时隙开始时才能发送帧，发送一帧的时间必须小于或等于时隙的长度。
- 纯
- 载波监听多路访问
Carrier Sense Multiple Access, CSMA协议1-坚持 CSMA：要发送数据时，首先监听信道；若信道空闲，则立即发送；否则继续监听直到信道空闲后立即发送。非坚持 CSMA：要发送数据时，首先监听信道；若信道空闲，则立即发送；否则放弃监听，等待一个随机的时间后再重新监听。p-坚持 CSMA：要发送数据时，首先监听信道；若信道忙，则继续监听（等到下一个时隙再监听）；若信道空闲，则以概率 p 发送数据，以概率 1-p 推迟到下一个时隙继续监听。
- 载波监听多路访问/冲突检测
CSMA/Collision Detection, CSMA/CD协议：- 先听后发，边听边发，冲突停发，随机重发。
- 只适用于半双工通信。
- 争用期（冲突窗口）：以太网的端到端往返时间 2\tau 。
- 最短帧长 = 总线传播时延 \times 数据传播速率 \times 2 = 争用期 \times 信道带宽，小于该长度的帧都是因冲突而异常中止的无效帧。
- 对于 10Mbps 和 100Mbps 以太网，争用期的长度都为 51.2 \mu s （100Mbps 以太网的最大长度缩减为 100m），在争用期内可发送 512bit ，即 64B 。
MAC帧的长度不小于 64B ，不大于 1518B 。- 不需要
ACK帧，争用期内未检测到冲突即视为发送成功。
- 二进制指数退避
- 基本退避时间：争用期 2\tau 。
- 从离散的整数集合 [0,1,\cdots ,(2^k-1)], k = min[重传次数, 10] 中随机取出一个数，记为 r ，重传所需推迟的时间即为 2r\tau 。
- 重传 16 次仍不成功时，开摆，向高层报告出错。
- 载波监听多路访问/冲突避免
CSMA/Collision Avoidance, CSMA/CD协议：- 避免：尽量降低冲突发生的概率。
- 所有站完成发送后，必须等待一段很短的时间（继续监听）才能发送下一帧，这段时间称为帧间间隔
InterFrame Space, IFS。SIFS（短IFS）：最短的IFS，用来分隔属于一次对话的各帧。
PIFS（点协调IFS）：中等长度IFS。
DIFS（分布式协调IFS）：最长的IFS，用于异步帧竞争访问的时延。
EIFS：前一帧出错的情况下，重传的时延。
- 若站点最初有数据要发送（非重传），且检测到信道空闲时，在等待
DIFS后，就发送整个数据帧，否则执行CSMA/CA退避算法，选取一个随机退避值；一旦检测到信道忙，则退避计时器就保持不变，只要信道空闲，退避计时器就进行倒计时；当退避计时器减至 0 时，站点就发送整个帧并等待确认；若收到ACK帧，则发送下一帧（从执行CSMA/CA退避算法开始）；若超时，则重新使用CSMA/CA协议争用该信道，直到开摆。 - 信道预约：处理隐蔽站问题。
- 等待
DIFS后，广播一个请求发送控制帧Request to Send, RTS，包括源地址、目的地址和这次通信所需的持续时间。若AP空闲，则等待SIFS时间后返回允许发送控制帧Clear to Send, CTS，也包括这次通信所需的持续时间。 RTS中所需占用信道的持续时间是指从RTS帧发送完毕后到目的站最后发完ACK帧为止的时间。- 只有当数据帧长超过某个数值时，使用
RTS帧和CTS帧才比较划算。 -
- 等待
- 轮询访问：令牌传递协议
- 当网络空闲时，环路中只有令牌帧在循环传递。
- 当令牌传递到有数据要发送的站点时，该站点就修改令牌中的一个标志位，并在令牌中附加自己需要传输的数据，将令牌变成一个数据帧，然后将这个数据帧发送出去。
- 数据帧沿着环路传输，接收到的站点一边转发数据，一边查看帧的目的地址。若目的地址和自己的地址相同，则接收站就复制该数据帧，以便进一步处理。
- 数据帧沿着环路传输，直到到达该帧的源站点，源站点收到自己发出去的帧后便不再转发。同时，通过检验返回的帧来查看数据传输过程中是否出错，若出错则重传。
- 源站点传送完数据后，重新产生一个令牌，并传递给下一站点，交出信道控制权。
- 适合负载很高（多个结点在同一时刻发送数据概率很大）的广播信道。
- 既不共享时间，又不共享空间；实际在随机访问介质访问控制的基础上限定了有权发送数据的站点只能有一个。
-
DIX Ethernet V2的MAC帧格式：6 \ 6 \ 2 \ N \ 4，收发协数验，N\in[46,1500] 。 -
IEEE 802.3的MAC帧格式：6 \ 6 \ 2 \ N \ 4，收发长数验，N\in[46, 1500] 。 -
光纤和 \ge 2.5Gbps以太网 必然是全双工通信。\lt 2.5Gbps以太网 使用半双工通信方式时使用
CSMA/CD协议。 -
IEEE 802.11的MAC帧格式：30 \ N \ 4，首数验， N\in[0,2312] ，首部 3+1 地址；去往AP中起止，来自AP止中起；九十比特表去来。 -
IEEE 802.1Q的MAC帧格式：6 \ 6 \ 4 \ \ 2 \ N \ 4，收发V协数验，N\in[46,1500] 。V：
VLAN标识符VID。
插入VLAN标签后，需要重新计算FCS。 -
Point-to-Point Protocol, PPP协议- 链路控制协议
Link Control Protocol, LCP：建立、配置、测试数据链接，身份验证。 - 网络控制协议
Network Control Protocol, NCP：每个不同的网络层协议都要用一个相应的NCP控制。 - 将
IP数据报封装到串行链路的方法。
- 使用异步传输时，采用字节填充法，转义字符
0x7D。使用同步传输时，采用零比特填充法。 PPP是点对点的，无需使用CSMA/CD协议，故数据段长度为 0 \sim 1500 字节，而不是 46 \sim 1500 字节。PPP不使用序号和确认机制，只保证无差错接收（CRC），因此是不可靠服务。PPP只支持全双工的点对点链路，不支持多点线路。PPP的两端可以运行不同的网络层协议，但仍可使用同一个PPP进行通信。PPP是面向字节的，所有PPP帧的长度都是整数个字节。
- 链路控制协议
-
以太网交换机的交换模式：
- 直通交换方式：只检查帧的目的
MAC地址，以决定该帧的转发接口。时延小，适用于不需要速率匹配、协议转换（如MAC\rightarrow802.1Q）或差错检测的线路。 - 存储转发交换方式：可靠性高，支持差错检测、速率转换，时延较大。
- 直通交换方式：只检查帧的目的
考点
-
以太网接收方不需要向发送方返回
CRC校验是否正确的信息。 -
待传输的消息为
1100 1001，CRC生成多项式为 x^3+1 ， 则加上校验码后的消息为1100 1001 011。x^3+1 的
G=1001。_____________ 1001 / 11001001000 1001 · · 1010 · · 1001 · · 0110· · 0000· · 1100 · 1001 · 1010 · 1001 · 0110· 0000· 1100 1001 1010 1001 ------------- 011 -
海明码纠错 d 为需要码距 2d+1 ，检错 d 位需要码距 d+1 。
-
T1线路采用的是时分复用。 -
在
CSMA/CD协议中，若传输速率提高，则冲突域最大距离应缩小。传输速率提高意味着发送时间变短，即用于冲突检测的时间变短。
-
令牌环网络中，没有数据要发送的结点应当立即传递令牌帧。
-
局域网工作在
OSI模型的物理层和数据链路层。 -
不同的
VLAN可以通过路由器进行转发。 -
如果期望将同属于一个广播域的两个网络分割为两个独立的较小广播域网络，可以选择的方案是利用路由器互联两个网络或 将网络划分为两个
VLAN。 -
从互联网角度看，广域网和局域网是平等关系。
-
不具备流量控制功能的协议之一是
PPP协议。 -
全双工 n 口交换机的总带宽为 n*2*单个端口的带宽 。