计算机网络之Ch6链路层和局域网

Posted on

6 链路层和局域网

  • 两种截然不同的链路层信道: 广播信道, 点对点通信链路

6.1 链路层概述

  • 直连网络—链路层—网卡

  • 在通过特定的链路时, 传输节点将数据报封装在链路层帧中, 并将该帧传送到链路中

    (首部 + data(IP包) + 尾部)

6.1.1 链路层提供的服务

  • 成帧: 把数据报封装成帧

  • 链路接入: 媒体访问控制MAC协议规定了帧在链路上传播的规则

  • 可靠交付
  • 差错检测: f(D)=E, 检测码E放在尾部, f(D’) = E’和收到的E对比
  • 流量控制

6.1.2 链路层在何处实现

  • 链路层的主体在网络适配器(也称网络接口卡, 网卡)中实现

6.2 差错检测和纠正技术

  • 使用差错检测和纠正比特EDC来增强数据D

  • f(D) = EDC, 放在数据D尾部一起发送; 接收方收到D’和EDC’, 通过计算f(D’)是否等于EDC’来检错

  • 可能会有未检出比特差错

6.2.1 奇偶校验

  • 主要用于硬件检错, 通信方面一般不用
  • 一维和二维

6.2.2 校验和 Checksum

  • 把数据D分成一个一个16位word, 然后加起来
  • 这里的加法是有进位加法, 且最高位的进位加到最低位上, 直到最高位没有进位
  • 最后全都取反码得到R, 这样就有D & R(数据和校验码)的全部words加起来为0
  • 由软件实现

6.2.3 循环冗余校验CRC

  • 也称多项式编码
  • 发送: D: data bits to be sent (d bits); R: CRC bits(r bits), 即$D \cdot 2^r \oplus R$
  • R的计算:
    • 发送方和接收方需要协定一个$r+1$比特模式, 称为生成多项式G, G最高有效位(最左)是1
    • 选择$r$位附加比特(CRC位, 记为R), 附加在D上, 满足
      • 被G整除, 即$D \cdot 2^r \oplus R=nG$
  • 检错:
    • 接收方用G去除
  • 所有操作都是不进位的模2算术, 加和减都等价于异或
  • 由硬件实现, 计算$R=\text{remainder}\frac{D\cdot 2^r}{G}$, 实现方法为异或电路

补充: 流量控制(书TCP部分3.5.5)

  • 停止等待

    • 源发送一个帧, 接收方收到帧并用ACK回应(表示可以接收下一个帧)

    • 源等待发送下一个帧, 直到收到ACK

    • 序号0或1, RR: receive ready; RNR: receive not ready

    • 发送方 ———- 接收方

      Send 0 —————— >

      ​ < —————— RR1(第0个收到了, 可以接收第一个)

      Send 1 ——————->

      ​ <——————- RR0(正确收到) / RNR1(没收到1, 需要重发) / RR1(收到了1但是不想再收)

  • 滑动窗口

    • 序号0 - 7(3bits帧序号 + 3bits确认号)

    • 只能发0 - 6(7个), 不然RR0有歧义

    • 3个变量维持状态变量:

      发送方:

      • Last ACK: 上一次接收方给出的确认帧序号(准备接收的那个, 也是比已经收到的大1)
      • Last Send: 上一次发送的帧的序号(+ 1)
      • Window Size常量7

      接收方:

      • Last ACK: 上一次接收方给出的确认帧序号
      • Last Receive: 上一次收到的帧的序号(+ 1)
      • Window Size常量7

    • 出错重传:

      • go back n
        • 错了之后的全都重传
      • Selective Reject
        • 只重发错了的
        • 接收方需要有足够大的缓冲
        • 比较复杂, 不在网卡层使用, 在TCP中使用

6.3 多路访问链路和协议(重点)

  • 两种截然不同的链路层信道: 广播信道, 点对点通信链路
  • 点对点链路的协议:
    • HDLC: Bit-Oriented Protocols
    • PPP: Byte-Oriented Protocols
    • SONET(不做要求):
      • 电信的
      • 9行, 对应一个一个话路(时隙)
      • 125$ \mu s$(电话频率)
  • 广播链路
    • 多个节点同时传输帧, 所有节点同时收到多个帧, 则发生碰撞, 也称冲突
    • 多路访问协议
      • 信道划分协议
      • 随机接入协议
      • 轮流协议

6.3.1 信道划分协议

  • 三种: 时分复用,频分复用, 码分复用
  • 时分复用: 将时间划分为时间帧, 每个时间帧划分为N个时隙, 每个时隙分配给N个节点中的一个
  • 频分复用: 在$R$ bps信道中创立$N$个较小的$R/N$ bps信道
  • 码分复用: 对每个节点分配一个码片, 码片是正交的(码片相乘为0)
    • 编码信号 = 原信号$\times$码片序列
    • 解码:编码信号和码片序列的内积
    • 码片频率高, 信号频率低
    • 码片中的0用-1代替, 为1, -1编码

6.3.2 随机接入协议

  • 一个传输节点总是以信道的全部速率进行发送
  • 有碰撞时, 涉及碰撞的每个节点反复重发它的帧知道帧无碰撞地通过为止
  • 重发之前会等待随机一个时延
  • 主要种类: ALOHA和CSMA

ALOHA

  • 无线型, 传输时间远小于传播时间
  • 过程:
    • 节点首次获取某一个数据帧后，立即将该帧完整地传输到信道中。
    • 如果收到ACK则成功，反之则以概率p重传，或1-p等待一个帧时间
    • 等待一个帧时间之后, 再次以概率p重传，或1-p再等待一个帧时间. 以此类推
  • 最大效率为$1/(2e)$, 恰好为时隙ALOHA的一半

时隙ALOHA

  • 假设:
    • 所有帧大小相同为$L$
    • 时间被划分成长度为$L/R$(即传输一帧的时间)的时隙
    • 基站发送脉冲, 主机收到脉冲才能发送帧
    • 如果一个时隙中发生碰撞，则所有节点在该时隙结束前能够检测到该碰撞
  • 过程
    • 节点有新帧需要发送，其需要等到下一个时隙开始时才可以发送。
    • 没有碰撞则传输成功，反之该节点以概率p在后面每个时隙开始重传该帧直到传输成功
  • 帧只会完全冲突或者不冲突, 性能提升明显
  • 有效传输速率$1/e=0.37$

载波侦听多路访问(CSMA)

  • 有线型, 传输时间远大于传播时间, 都是理论协议
  • 规则:
    • 载波侦听：一个节点在传输前先侦听信道，等待知道检测到一段时间信道空闲，然后开始传输
    • 碰撞检测：节点在传输时也一直侦听信道，如果检测到另一个节点也在传输，则马上终止自己的传输，且在进入”侦听-检测”新的循环之前，随机等待一段时间(二进制指数回退)
  • 过程:
    • 发送之前先载波侦听, 如果信道空闲才发送帧
    • 发送后等待ACK, 没等到就重传
  • 帧越长, 传播时间越短, 性能越好
  • 根据信道非空闲时的处理方式分成以下三种
    • 非坚持CSMA
      • 检测到空闲立即传输
      • 信道忙就回去休息(idle), 过一段时间再次检测
      • 休息时间一定是随机的
    • 1坚持CSMA
      • 检测到空闲立即传输
      • 信道忙就一直侦听, 一旦空闲立即发送
      • 如果多个在等, 肯定冲突, 效果不好
    • p坚持CSMA(概率坚持)
      • 空闲时以概率p重传，1-p延后一个时间单位再决定, 忙时一直监听

具有碰撞检测的CSMA: CSMA/CD

  • 以太网的协议, 现在已经无效
  • 碰撞检测: 当一个传输节点在传输时一直侦听此信道, 如果检测到另一个节点正在传输干扰帧, 就停止传输(从而减少了冲突时间)
  • 过程如下
    • 适配器从网络层获得一条数据报, 准备链路层帧, 放入缓存
    • 若侦听到信道空闲: 发送; 若侦听到信道忙, 1坚持, 直到侦听到空闲就发送
    • 发送的同时监听, 如果发现冲突则发送一个高频信号(表示冲突)立即停止; 如果全程无冲突则成功.
    • 侦听到冲突则等待随机时间后回到第二步重试
  • 无ACK(CSMA和ALOHA都有), 但是在CSMA/CD中, 只要全程没冲突即发送成功
  • 最坏要2个传播时间$2\mu$才能检测出来冲突, 因此要发送的最小帧长大于等于$2\mu$ ($\mu$的时间到目的地, 即将到目的第的时候冲突, 冲突再经过$\mu$传到发送方)
  • 重试:
    • 等待时间是$[0, 2^k)$之间的随机整数
    • 前10次重试失败后$k$会加1, 第一次重试$k=1$
    • 第11-16次$k=10$不再增加
    • 16次都不成功则放弃

CSMACD

9.6$\mu s$: 硬件重置: 不管

周期之前会等待512比特时间

jam信号: 4-6字节

6.3.3 轮流协议

  • 轮询协议:

    • 1个主节点, 主节点以循环的方式轮询每个从节点
    • 蓝牙

  • 令牌传递(token-passing)协议

    • 没有主节点, 一种称为令牌的特殊帧在节点之间以特定顺序传递
    • 拿到令牌的节点才能发送帧, 没有帧要发送则马上传递
令牌环token ring
  • 空闲时令牌(短帧)循环
  • 主机等待令牌, 拿到令牌后修改令牌中的一个位, 加上剩下的数据帧
  • 数据帧在环上循环, 再次回到发送方时, 回收并释放令牌
  • 实际上:
    • 传播时延$\mu$<<传输时延$T$, 还没发完就回收了
    • 令牌可以预约, 在令牌上打个标记, 决定优先级
    • 接收方收到数据也会在数据帧尾部打一个标记
FDDI令牌环
  • 100 Mbps令牌环
  • 内外两层环, 断掉一段回路或者坏掉一个主机都没事, 只要将边上的主机的内外环相连
  • $\mu > T$
  • 帧发完以后立即释放令牌(不用回收的时候再释放)
  • 可以不用令牌: 将$\mu$切成多个区域分别发送同步脉冲

6.4 交换局域网

6.4.1 链路层寻址和ARP

MAC地址

  • 并不是主机或者路由器具有链路层地址，而是它们的适配器(网络接口)具有链路层地址。因此具有多个网络接口的主机或者路由器具有多个链路层地址。
  • 因为主机和路由器不必明确地将帧寻址到其间的交换机, 所以链路层交换机无链路层地址
  • 链路层地址称为LAN地址，物理地址或MAC地址。
  • MAC地址长度为6字节，所以共有$2^{48}$个可能的MAC地址(常用16进制表示为XX-XX-XX-XX-XX-XX)
  • 适配器的MAC地址一般是固定的
  • 没有个两块适配器具有相同的地址
  • 适配器的MAC地址具有扁平化结构, 且不论适配器到哪里用都不会变化，带有以太网接口的便携机总是具有同样的MAC地址(IP地址不是这样的)
  • 当适配器要向某些目的适配器发送一个帧时
    • 发送适配器将目的适配器的MAC地址插入到链路层帧中，再发送到局域网上。
    • 接收适配器接收到帧后，检查其中MAC地址是否与自己MAC地址相匹配，如果匹配则取出其中数据，向上层传递，如果不是，则丢弃该帧。
  • 广播：发送适配器需要让局域网上所有适配器都接受并处理某帧，则在该帧的目的地址中插入一个特殊的MAC地址(FF-FF-FF-FF-FF-FF)

地址解析协议 ARP

  • ARP协议: IP地址转换为对应的MAC地址

  • 每台主机或路由器在其内存中有一个ARP表.

ARP过程

  • Sender

    • 查找自己的cache, 如果没有就
    • 构建ARP请求, 插入
    • 用MAC帧广播
    • 缓存目的地的对, 以及时间戳

  • Receiver:

    • 查目的地IP, 如果OK

    • 建立ARP应答, 插入

    • 用MAC帧发送sender MAC

    • 缓存发送方的以及时间戳

6.4.2 以太网

  • 早期的其他局域网技术:
    • ATM(异步传输模式)
    • 令牌环
    • FDDI
  • 以太网几乎占领着现有的有限局域网市场
    • 总线拓扑$\to$星形拓扑
    • 星形拓扑中心: 集线器(hub)$\to$交换机(switch)
以太网帧结构
前同步码 目的地址 源地址 类型 数据 CRC(循环冗余校验码)
8 bytes 6 6 2 46-1500 4
  • 前同步码: 前7字节10101010唤醒接受适配器并同步时钟, 后1字节10101011
  • 类型字段: 复用多种网络协议, 例如可以使用除了IP以外的其他网络层协议
补充: LLC服务(了解概念即可)
  • 以太网是无确认无连接的, 而可以将其改变为LLC, 加上逻辑连接, 流控制和检错
  • 从不在以太网中使用, 但是在WiFi和令牌环中使用
  • 基于HDLC, 主要分为三种
    • 无确认无连接: 什么都不加
    • 有确认无连接: 加ACK和NAK, stop and wait
    • 连接模式(异步平衡模式 异步: 无时钟脉冲 平衡: 无主从模式)
以太网技术
  • 以太网有很多标准, 缩写为10base5, 10base2,10baseT, 10baseFX等.
    • 由IEEE 802.3 CSMA/CD(Ethernet)工作组标准化
    • 其中缩写的第一部分表示该标准的速率:10, 100, 1000, 10G(单位为Mbps)
    • “BASE”指基带以太网, 表示该物理媒体仅承载以太网流量
    • 最后一部分表示物理媒体本身, 以太网是链路层也是物理层的规范. 例如’T’表示双绞铜线.
高速以太网
  • 依然使用MAC协议和帧结构, 星形拓扑
  • 100Mbps高速以太网: 100BASE-TX(2对双绞电缆), 100BASE-FX(2光纤), 100BASE-T4
  • 吉比特以太网
    • Carrier extension: 帧长至少4096bit
    • Frame bursting: 多个小帧合并
    • Full Duplex Operation: 必须用交换集线器
    • 1000Base-SX, 1000BaseLX, 1000Base-CX, 1000Base-T
  • 10Gbps以太网: 略
  • 二层交换机switch: 多端口网桥; 以太网上的router: 三层交换机

6.4.3 网桥/switch/二层交换机(同一个意思)(重要)

  • 主要作用: 互连局域网的网段, 网桥互联的必须是同类型的局域网

  • 不修改帧的内容(路由器会修改)

  • 有交换功能(基于MAC地址, 以主机为单位)(==必考路由器和网桥的区别==)
    • MAC地址看不出网段, 而IP地址看得出
    • 网桥是以主机为单位, 路由是以网段为单位
    • 网桥不涉及封装解封, 路由器涉及
  • 存储转发(store and forward)不涉及协议转换
  • 对于子网中的主机和路由器是透明的(不被知道)

  • 自学习的, 即插即用(plug-and-play)

  • 隧道模式:

    • 完整的帧, 加头和尾传播, 接收去掉头尾, 得到完整的帧

  • 交换:

    • 不选择最短路—支撑树算法(==必考==)

支撑树算法

  • 网桥自动生成交换表, 自动更新
  • 主要分为:
    • 帧转发
    • 地址学习
    • 环路识别
1. 帧转发
  • 交换表结构: <目的MAC地址, 转发端口号, 时间戳>
  • 对于一个到达端口X的帧:
    • 搜索转发表, 看有没有这个MAC地址
      • 如果没找到MAC地址, 在所有端口(除X)都转发
      • 如果有MAC地址, 检查端口号
        • 若端口是X, 直接丢掉
        • 若端口是Y(非X), 如果Y是可以转发状态就转发
          (forwarding状态可收可发, blocking状态只能发)
2. 地址学习

  • 转发表是自学习的

  • 帧X到达端口后:

    • 如果没有这个MAC源地址, 则补上

    • 如果有MAC源地址, 则检查端口号

      • 如果端口是X则更新时间戳
      • 如果端口是Y(非X), 则端口更新为X且更新时间戳

    • 每个表项有计时器, 时间到则删除表项(即一个表项如果一段时间没有对应的帧到来则删除)

3.环路识别
  • 必须要是树结构才能运作
    • 一旦有环路, 会造成一个帧不停转圈和路由震荡
    • 因此需要将某些端口blocking: 不收不发
  • 中心树算法如下:
    • 选择一个根网桥(ID最小)
    • 每个网桥(除了根网桥)选择一个根端口(离根网桥最近)
    • 对每个LAN选择指定网桥
    • 指定端口连接LAN和指定网桥
    • 所有根端口和制定端口为forwarding状态, 其他blocking状态
  • 路径发现
    • 找两个结点间最短路……