计网第六章--数据链路层

链路层概述
- 链路层的术语
  - 节点：主机和路由器
  - 链路：沿着通信路径连接相邻节点的通信信道
  - 数据帧frame：第二层的分组，封装了的数据报
  - 数据链路层的职责：将数据报从一个节点传送到与该节点直接有物理链路相连的另一个节点
- 链路层提供的服务
  - 封装数据报为数据帧，增加头部、尾部信息，接入链路
  - 在相邻节点之间可靠传输数据帧
  - 流量控制：控制发送节点向接收节点发送数据帧的频率
  - 差错检查：接收方需要检测收到的数据帧是否发生比特错误
  - 错误纠正：接收方可以对比特错误进行标识和纠正
  - 半双工和全双工，半双工两个节点都可以发送数据，但不能同时发送
- 链路层实现的位置
  - 在主机和网络设备（路由器）上实现
  - 在主机上，链路层的主体部分是在网络适配器上实现的
  - 网络适配器
    - 发送方
      - 封装数据报为数据帧
      - 增加差错检测比特，可靠数据传输，流量控制
    - 接收方
      - 执行检查错误、可靠数据传输、流量控制
      - 抽取数据报、将其递交给上层
差错检测和纠错（重点）
- 差错检测和纠错技术
  - 比特级差错检测和纠错：对一个节点发送到一个相邻节点的帧，检测是否出现比特差错，并纠正
  - 差错检测和纠正技术不能保证接收方检测到所有的比特差错，即可能出现未检测到的比特差错，而接收方并未发现。
- 差错检测技术
  - 奇偶校验：最基本的方法
  - Internet校验和：常用于运输层
  - 循环冗余检测：常用于链路层
- 比特奇偶校验
  - 发送方
    - 在要发送的信息D（d位）后面附加一个奇偶校验位
    - 使“1”的个数是奇数（奇校验）或偶数（偶校验）
    - 一起传输发送（d+1位）。
  - 接收方
    - 检测收到的信息（d+1位）中“1”的个数。
    - 偶校验：发现奇数个“1”，至少有一个比特发生差错（奇数个比特差错）。
    - 奇校验：发现偶数个“1”，至少有一个比特发生差错。
- 二维奇偶校验
  - 将要传信息D（d比特）划分为i行j 列（i 个组，每组j位）；
  - 对每行和每列分别计算奇偶值；
  - 结果的i+j+1个奇偶比特构成了帧的差错检测比特。
  - 可以检测并纠正单个比特差错（数据或校验位中）。
  - 能够检测(但不能纠正)分组中任意两个比特的差错。
- Internet校验和方法
  - 发送方
    - 将数据的每两个字节当作一个16位的整数，可分成若干整数；
    - 将所有16 位的整数求和；
    - 对得到的和逐位取反，作为检查和，放在报文段首部，一起发送。
  - 接收方
    - 对接收到的信息(包括检查和项)按与发送方相同的方法求和。
    - 如果结果为全“1”：则收到的数据无差错；
    - 如果结果中有“0”：则收到的数据出现差错。
- 循环冗余检测CRC（重点计算）
  - 多项式编码：把要发送的比特串看作为系数是0或1的一个多项式，对比特串的操作看作为多项式运算。
  - 基本思想
    - 设发送节点要把数据D（d比特）发送给接收节点。
    - 发送方和接收方先共同选定一个生成多项式G（r+1比特），最高有效位 (最左边)是1。
  - 发送方：
    - 计算出一个r位附加比特R，添加到D的后面产生DR（d+r 比特）
    - DR能被生成多项式G模2运算整除，一起发送。
  - 接收方：
    - 用生成多项式G去除接收到的DR（d+r比特）
    - 余数非0：传输发生差错；
    - 余数为0：传输正确，去掉尾部r位，得所需数据D。
多路访问链路和协议
- 网络链路
  - 点对点链路：链路两端各一个节点。一个发送和一个接收。如点对点协议PPP
  - 广播链路：多个节点连接到一个共享的广播信道
- 多路访问协议
  - 目的：协调多个节点在共享广播信道上的传播
  - 冲突：两个以上的节点同时传输帧，使接收方收不到正确的帧
- 多路访问协议类型
  - 信道划分协议
    - 把信道划分为小“片” (时隙)
    - 给节点分配专用的小“片”
  - 随机访问协议
    - 不划分信道，允许冲突
    - 能从冲突中“恢复”
  - 轮流协议
    - 通过轮流访问信道避免冲突，要发送的节点越多轮流时间越长
- 信道划分协议
  - 时分多路访问TDMA：将时间划分为时间帧，每个时间帧再划分为N个时隙（长度保证发送一个分组），分别分配给N个节点。每个节点只在固定分配的时隙中传输。
  - 频分多路访问FDMA：将总信道带宽 R b/s划分为 N 个较小信道（频段，带宽为R/N），分别分配给 N 个节点。
  - 码分多路访问CDMA：每个节点分配一个唯一的编码，每个节点用它唯一的编码来对它发送的数据进行编码
- 随机访问协议
  - ALOHA协议
    - 纯ALOHA
      - 非时隙Aloha: 简单，不需同步
      - 帧一到达，立即传输
      - 如果与其他帧产生冲突，在该冲突帧传完之后：
        以概率p立即重传该帧；
        或等待一个帧的传输时间，再以概率p传输该帧，或者以概率1-p等待另一个帧的时间。
      - 冲突概率:
        在t0发送的帧，和在 [t0-1,t0+1]的发送的其它帧冲突
    - 时隙ALOHA
      - 时间被划分为相同大小的时隙，一个时隙等于传送一帧的时间
      - 当节点要发送新帧，它等到下一时隙开始时传送
      - 没有冲突，节点可以在下一时隙发送新帧
      - 如果有冲突，节点在随后的时隙以概率p重传该帧，直到成功为止。
  - CSMA（载波侦听多路访问）
    - 载波侦听：某个节点在发送之前，先监听信道。
      - 信道忙：有其他节点正往信道发送帧，该节点随机等待（回退）一段时间，然后再侦听信道。
      - 信道空：该节点开始传输整个数据帧。
  - 带冲突检测的CSMA（CSMA/CD）
    - 基本原理：传送前侦听
      - 信道忙：延迟传送
      - 信道闲：传送整个帧
    - 发送同时进行冲突检测：一旦检测到冲突就立即停止传输，尽快重发。
    - 目的：缩短无效传送时间，提高信道的利用率。
  - 以太网CSMA／CD的运行机制
    - 1. 适配器从网络层得到分组,创建帧
    - 2. 如果适配器侦听到信道空闲,开始传送帧。如果信道忙,它会等到信道空闲才传送帧
    - 3. 如果适配器传送整个帧时，都没有检测到其它传输, 则完成该帧的传送
    - 4.如果适配器在发送中检测到其它传送,就放弃传送，并发送一个拥塞信号
    - 5. 放弃传送后，适配器进入指数回退阶段，即该帧经过n次冲突后，适配器在{0,1,2,…,2＾m-1}中随机选取一个K值，其中m=min(n,10),然后等待K*512比特时间后,回到第2步
  - 以太网CSMA/CD的运行机制讨论
    - 拥塞信号：48比特，确保所有传送者知道冲突发生
    - 比特时间：对于10 Mbps Ethernet 为0.1微秒，当K=1023，等待时间大约50毫秒
    - 二进制指数回退算法（超级重点）
      - 目标：适配器依据当前负载情况重传，重负载时等待时间变长
      - 第一次冲突：在{0,1}中选k值；延迟Kx512比特时间传送
      - 第二次冲突：在{0,1,2,3}中选k值…
      - 10次以后，在 {0,1,2,3,4,…,1023}中选k值。
      - K是等概率选择
- 轮流协议
  - 轮询协议：主节点“邀请”从节点依次传送
    - 轮询协议要求首先从连入共享信道的节点中选择一个作为主节点，其余节点为从节点。
    - 主节点以循环的方式轮询每个节点。例如主节点首先向节点1发送一个报文，告诉它（节点1）能够传输的帧的最多数量。如果节点1有数据要发送，则最多可发送允许的最多数据的数据；
    - 然后主节点会继续询问节点2，节点3。
  - 令牌传递：控制令牌顺序从一个节点传递到下一个节点。
    - 在这种协议中没有主节点，一个称为令牌的小的特殊帧在节点之间以某种固定的次序进行交换。
    - 例如节点1可能总是把令牌发送给节点2，节点2可能总是把令牌发送给节点3，而节点4总是把令牌发送给节点1.
    - 当一个节点收到令牌时，仅当它有一些数据帧要发送时，它才持有这个令牌，否则，它立即向下一个节点转发该令牌。
    - 当一个节点收到令牌时，如果它确实有数据帧要传输，它发送最大数目的帧数，然后把令牌转发给下一个节点。
交换局域网
- 局域网概述
  - 局域网：Local Area Network ( LAN )
  - 多址访问协议广泛应用于局域网
  - 基于随机访问的CSMA/CD广泛应用于局域网
- 常见的网络拓扑结构
  - 星形结构：中央结点集中式通信控制
  - 总线结构：所有的站点都连接在同一个传输线总线上
  - 环型结构：站与站点之间首尾相接，形成一个环，数据只能沿单方向传输
  - 树形结构：它是从星型拓扑演变而来的，形状像一棵倒挂的树
  - 网状结构：网状网络的每一个站点都与其它站点一一直接互连
- 链路层寻址和ARP
  - 网络层地址：节点在网络中分配的一个唯一地址（IP地址）。用于把分组送到目的IP网络。长度为32比特（IPv4）。
  - 链路层地址MAC：用于把数据帧从一个节点传送到另一个节点(同一网络中)。1A-2F-BB-76-09-AD
  - DNS域名系统：将主机名解析到IP地址。
  - ARP地址解析协议：将IP地址解析到MAC地址。
    - 两个主机位于同一个局域网
      - 主机A希望发送数据报给主机B
        B的MAC地址不在A的ARP映射表中
      - 主机A 广播 ARP查询分组, 其中包含B的IP地址
        目的MAC地址=FF-FF-FF-FF-FF-FF
        局域网中所有节点收到ARP查询分组
      - 主机B收到ARP查询分组，返回B的MAC地址给主机A
        包含有B的MAC地址的帧发送给主机A(单播)
      - 主机A在它的ARP表中缓存 IP-to-MAC 地址对
    - 发送数据报到子网之外
      - 主机A构建IP数据报，源地址是A的IP地址，目的地址是B的IP地址
      - 主机A构建链路层数据帧，目的MAC地址是路由器左边端口的MAC地址
      - 数据帧从主机A发送到路由器R
      - 路由器R收到数据帧，抽取出数据报递交到IP层
      - 路由器R转发数据报，源地址为A的IP地址，目的地址为B的IP地址
      - 路由器R将该数据报封装成链路层帧，目的MAC地址为主机B的MAC地址