1.数据链路层

1.1 概述

一些术语：
- 将运行链路层协议协议的任何设备均称为结点( node) ，包括主机、路由器、交换机和 WiFi 接人点等等
- 沿着通信路径连接相邻结点的通信信道称为链路( link)
- 在通过特定的链路时，传输结点将网络层数据报封装在链路层帧(frame） 中，并将该帧传送到链路中
一个交通运输的类比例子说明网络层与链路层：
- 游客想从 A 到 B 去游玩，旅行社选择出最佳路线：从 A 坐大巴到 C，从 C 坐飞机到 D，从 D 坐火车到目的地 B。
- 一个游客好比一个数据报，每个运输区段好比一条链路，每种运输方式好比一种链路层协议，而该旅行社好比一个路由选择协议

1.2 链路层服务

链路层协议能够提供的可能服务包括:
- 成帧( framing) ：
  - 将数据报组装成数据帧，加首部和尾部
- 链路接入（link access）：
  - 媒体访问控制 (Medium Access Control , MAC) 协议规定了帧在链路上传输的规则
  - 帧首部的 MAC 地址，用于标识帧的源和目的，不同于 IP 地址！
- 相邻节点的可靠交付
  - 在低误码率的有线链路上，链路层可靠交付可能会被认为是一种不必要的开销，因而很少采用
  - 误码率高的链路如无线链路，需要可靠交付。其目的是本地(也就是在差错发生的链路上)纠正一个差错，而不是通过运输层或应用层协议迫使进行端到端的数据重传
- 差错检测和纠正
  - 因特网的运输层和网络层也提供了有限形式的差错检测，即因特网检验和。
  - 链路层的差错检测通常更复杂，并且用硬件实现
  - 差错纠正类似于差错检测，区别在于接收方不仅能检测帧中出现的比特差错，而且能够准确地确定帧中的差错出现的位置(并因此纠正这些差错)

1.3 链路层具体实现

链路层是实现在路由器的线路卡中的。主机的链路层呢？
一个典型的主机体系结构：
- 链路层的主体部分是在网络适配器 (network adapter) 中实现的，网络适配器有时也称为网络接口卡 (Network Interface Card , NIC)
- 位于网络适配器核心的是链路层控制器，通常是一个实现了许多链路层服务的专用芯片，因此，链路层控制器的许多功能是用硬件实现。
- 越来越多的网络适配器被综合进主机的主板，即所谓的局域网在主板配置
链路层是硬件和软件的结合体，即此处是协议栈中软件与硬件交接的地方

2.差错检测和纠正

略

3.多路访问协议

3.1概述

有两种类型的网络链路：点对点链路和广播链路
- 点对点链路( point-to-point link) 由链路一端的单个发送方和链路另一端的单个接收方组成。
- 许多链路层协议都是为点对点链路设计的，如点对点协议( point- to-point protocol , PPP) 和高级数据链路控制 (high-Ievel data link control，HDLC)
- 广播链路 (broadcast link) ，它能够让多个发送和接收结点都连接到相同的、单一的、共享的广播信道上。
- 以太网和无线局域网是广播链路层技术的例子
先暂缓讨论特定的链路层协议，而研究一个对链路层很重要的问题：如何协调多个发送和接收结点对一个共享广播信道的访问，这就是多路访问问题( multiple access problem)
为解决此类问题 —— 多路访问协议( multiple access protocol) ，即结点通过这些协议来规范它们在共享的广播信道上的传输行为
因为所有的结点都能够传输帧，所以多个结点可能会同时传输帧，结果所有结点同时接到多个帧，传输的帧在所有的接收方处碰撞( collide) 了，此时没有一个接收结点能够有效地获得任何传输的帧
- 显然，如果许多结点要频繁地传输帧，许多传输将导致碰撞，广播信道的大量带宽将被浪费掉
- 当多个结点处于活跃状态时，为了确保广播信道执行有用的工作，以某种方式协调活跃结点的传输是必要的。这种协调工作由多路访问协议负责
多路访问协议划分为 3 种类型
- 信道划分协议 (channel partitioning protocol)
- 随机接入协议 (random access protocol)
- 轮流协议( taking-turns protocol)
理想的多路访问协议：
- 给定：速率为 R bps 的广播信道
- 期望：
  - 当仅有一个结点有数据发送时，该结点具有 R bps 的吞吐量;
  - 当有 M 个结点要发送数据时，每个结点吞吐量为 R/M bps
  - 协议是分散的：这就是说不会因某主结点故障而使整个系统崩溃
  - 协议是简单的，使实现不昂贵

3.2信道划分协议

之前讲过，时分多路复用 (TDM) 和频分多路复用 (FDM) 是两种能够用于在所有共享信道结点之间划分广播信道带宽的技术
TDMA（time division multiple access）：
- 周期性接入信道
- 每个站点在每个周期，占用固定长度的时隙
- 未用时空闲时隙、
- 消除了碰撞而且非常公平，每个结点在每个帧时间内得到了专用的传输速率
- 然鹅，结点被限制于 R/Nbps 的平均速率，即使当它是唯一有分组要发送的结点；结点必须总是等待它在传输序列中的轮次，即使当它是唯一有分组要发送的结点
FDMA（frequency division multiple access）
- 信道频谱划分为多个频带
- 每个站点分配一个固定的频带
- 无传输频带空闲
- 避免了碰撞，在 N 个结点之间公平地划分了带宽
- 然鹅，限制了一个结点只能使用 R/N 的带宽，即使当它是唯一一个有分组要发送的结点时

3.3 随机接入协议

在随机接入协议中，一个传输结点总是以信道的全部速率(即 R bps) 进行发送
没有事先的节点间协调，当有碰撞时，涉及碰撞的每个结点反复地重发（不必立即重发）它的帧 (也就是分组) ，到该帧无碰撞地通过为止
在重发该帧之前等待一个随机时延。涉及碰撞的每个结点独立地选择随机时延
典型的数据接入协议：
- ALOHA 协议
- CSMA 协议、CSMA/CD、CSMA/CA

3.3.1 时隙 ALOHA

最简单的随机接人协议之一 —— 时隙 ALOHA 协议
假设：
- 所有帧大小相同
- 时间被划分等长的时隙(一个时隙等于传输一帧的时间)
- 结点只在时隙起点开始传输帧
- 结点是同步的，每个结点都知道时隙何时开始
- 如果在一个时隙中有两个或者更多个帧碰撞，则所有结点在该时隙结束之前检测到该碰撞事件
在每个结点中，时隙 ALOHA 的操作是：
- 每个结点在每个时隙以概率 p 发送数据
- 当结点有一个新帧要发送时，等到下一个时隙开始并在该时隙传输整个帧
- 如果没有碰撞，该结点成功地传输它的帧
- 如果有碰撞，该结点检测到这次碰撞，以概率 p 在后续的每个时隙中重传它的帧，直到成功
优点：
- 单个节点活动时，可以连续以信道全部速率传输数据
- 高度分散化，只需时钟同步
- 简单
缺点：
- 冲突，浪费时隙
- 空闲时隙
- 结点也许能以远小于分组传输时间检测到冲突
效率：
- 定义：长期运行中成功时隙的比例（很多结点、很多帧待发送）
- 因为有 N 个结点，任意一个结点成功传送的概率是 Np(l-p)^N-1
- 当 N 无穷大时，可得最大效率 = 1/e = 0.37
- 相似的分析还表明 37% 的时隙是空闲的， 26% 的时隙有碰撞

3.3.2 ALOHA 协议

第一个 ALOHA 协议实际上是一个非时隙、完全分散的协议。更加简单，无需同步
当有新的帧需要发送时，立即发送
冲突性增大，若在t₀ 时刻发送，会与在[t₀ - 1 , t₀ + 1] 期间发送的帧冲突
任意一个结点成功传送的概率是 p(1 - p)^2(N-1)
当 N 无穷大时，可得最大效率 = 1/2e = 0.18，刚好是时隙 ALOHA 的一半。这就是完全分散的 ALOHA 协议所要付出的代价

3.4 载波侦听多路访问 (CSMA)

载波侦听( carrier sensing) ，即一个结点在传输前先侦听信道
- 若信道空闲，则发送完整帧
- 若信道上有帧正在发送，则推迟发送
  - 1 - 坚持 CSMA
  - 非坚持 CSMA
  - p - 坚持 CSMA
碰撞检测( collision detection) ，即当一个传输结点在传输时一直在侦听此信道
- 如果它检测到另一个结点正在传输干扰帧，它就停止传输，在重复"侦听-当空闲时传输"循环之前等待一段随机时间
以上两个规则包含在载波侦听多路访问( Carrier Sense Multiple Access , CSMA) 和具有碰撞检测的 CSMA(CSMA with Collision Detection, CSMA/CD)
对于 CSMA，如果所有的结点都进行载波侦听了，为什么当初会发生碰撞？—— 以时空图解释：
- 在时刻 t0，结点 B 侦听到信道是空闲的，因此结点 B 开始传输，沿着广播媒体在两个方向上传播它的比特
- 在时刻 t1(两时刻相差极短)，结点 D 有一个帧要发送。尽管结点 B 在该时刻正在传输，但 B 传输的比特还没有到达 D ，因此 D 此时侦听到信道空闲，从而 D 开始传输它的帧
- 一个短暂的时间之后， B 的传输开始在 D 干扰 D 的传输
- 显然广播信道的端到端信道传播时延 (channel propagation delay) (信号从一个结点传播到另一个结点所花费的时间) 在决定其性能方面起着关键的作用
- 继续发生冲突帧，导致浪费资源
对于 CSMA / CD：
- 短时间内可以检测到冲突，冲突后终止传输，减少信道浪费
- 当某结点执行碰撞检测时，一旦它检测到碰撞将立即停止传输
- 在多路访问协议中加入碰撞检测，通过不传输一个无用的、(由来自另一个结点的帧干扰)损坏的帧，将有助于改善协议的性能
- 在结点中与广播信道相连的适配器负责链路层帧的传输
  - 信道空闲则开始传输，信道忙则等待，直到侦听到没有信号能量时才开始传输
  - 在传输过程中，适配器监视来自其他使用该广播信道的适配器的信号能量的存在
  - 如果在传输时检测到来自其他适配器的信号能量，它中止传输。适配器等待一个随机时间量后，再次返回第一步
- 随机时间长短如何选择？
  - 当碰撞结点数量较少时，时间间隔较短；当碰撞结点数量较大时，时间间隔较长
  - 采用二进制指数后退（binary exponential backoff）算法
  - 当传输一个给定帧时，在该帧经历了一连串的几次碰撞后，结点随机地从 [ 0,1, 2, … , 2^n-1] 中选择一个 K 值。对于以太网，一个结点等待的实际时间量是 K*512 比特时间
  - 因此从中选择 K 的集合长度随着碰撞次数呈指数增长；正是由于这个原因，该算法被称为二进制指数后退
- CSMA / CD 效率问题
  - 当只有一个结点有一个帧发送时，该结点能够以信道全速率进行传输。然而，如果很多结点都有帧要发送，信道的有效传输速率可能会小得多。
  - CSMA / CD 效率的推导超出了本书的范围
  - 当结点间的传播时延约为 0 时，或最大帧的传输时间很大时，CSMA / CD 的效率很高

3.5 轮转访问协议

主要讨论们两种比较重要的轮流协议：
- 轮询协议 ( polling protocol)
- 令牌传递协议 ( token-passing protocol)
轮询协议 ( polling protocol)
- 要求这些结点之一要被指定为主结点，主结点以循环的方式轮询 ( poll) 每个结点（轮流“邀请”每个从属结点发送数据）
- 问题：
  - 轮询开销
  - 等待延迟
  - 单点故障
令牌传递协议 ( token-passing protocol)
- 控制令牌依次以某种固定的次序从一个结点传递到下一个结点，持有令牌的结点发送数据
- 令牌：很小的特殊帧
- 问题：
  - 令牌开销
  - 等待延迟
  - 单点故障

原文链接：https://blog.csdn.net/weixin_45763536/article/details/106756988