computer-network-note-3

数据链路层

数据链路层设计要点

数据链路层概述

• 物理层实现了比特流的传输，数据链路层在其基础上实现帧(frame)的传输
  • 数据链路层传输的协议数据单元(PDU)是帧
• 数据链路层使用的信道类型
  • 点对点信道
    • 使用一对一的点对点通信方式。
  • 广播信道
    • 使用一对多的广播通信方式
    • 广播信道上连接多个主机，必须采用专门的共享信道协议来协调数据发送
• 数据链路层涉及的问题
  • 成帧(framing)：怎样组成帧、怎样使接收方识别帧
  • 差错控制：帧在传输过程中出错的检测
  • 流量控制及可靠传输：仅是数据链路层的选项
  • 广播信道中的介质访问控制

成帧方法

• 成帧要考虑的问题：接收方如何识别帧的边界？
• 常用的成帧方法
  • 字符计数法:在帧头部字段中指明本帧的字节数，接收方通过该字段得知该接收多少 字节
  • 字符填充的首尾定界法:定义专门的字符作为帧的起始/结束标志，并使用字符填充方式将标志字符与数据区分开来
  • 比特填充的首尾定界法:定义专门的比特序列作为帧的起始/结束标志，并使用比特填充方式将标志序列与数据区分开来
  • 物理编码违例法:使用无效的物理编码作为帧的开始/结束标志，供接收方识别

错误检测和纠正

检错编码(Error detecting code)

• 任何通信链路在传输数据时都可能出错

• 一般用误码率BER(Bit Error Rate)表示链路可靠性

  • 误码率=出错的比特数/传送的总比特数

• 处理方法

  • 使用可检测并纠正错误的编码：纠错码
  • 使用可检测错误的编码 + 重传：检错码

• 常用检错编码方法

  • 奇偶校验
  • 简单累加和(校验和)
  • 循环冗余校验CRC(Cyclic Redundancy Check)

• 循环冗余校验CRC原理

  • 发送方把数据划分为组，设每组 k 个比特，在其后添加供差错检测用的n 位冗余码，(k+n)比特一起发送

  • 对数据M计算n位冗余码的过程：

    • 用二进制的模 2 运算进行 2 n 乘 M 的运算，这相当于在 M 后面添加n 个 0
    • 得到的 (k + n) 位的数除以事先选定好的长度为 (n + 1) 位的除数 P，得出商是 Q 而余数是 R，余数 R 比除数 P 少1 位，即 R 是 n 位
    • R作为冗余码，添加在数据M后面，最终发送数据：2 nM+R

    注：除数P为双方事先商定

  • 接收方对收到的(k+n)比特计算冗余码，结果为0表示传输正确，否则表示传输错误

  • 在网络中具体实现时，通常采用硬件电路生成CRC校验和(checksum)

纠错编码(Error correcting code)

• 检错码只能发现数据出现了错误，无法得知哪个比特出错
• 纠错编码通过增加冗余信息使得能够检测错误发生所在，以便于纠正，又称为前向纠错(forward error correcting)– 海明编码
• 关于数据链路层检错/纠错的讨论
  • 通过检错码/纠错码可以做到帧的无差错接收，或者说“无比特差错”
  • 并不意味着可靠传输，其他的错误包括：
    • 帧丢失、帧重复、帧失序

基本数据链路协议

无限制的单工协议

• 假设前提
  • 单项传输
  • 理想信道
  • 发送方总有数据发送
  • 接收方总能及时处理收到的数据

单工停- 等(stop-and-wait)协议

• 按照“无限制的单工协议”，如果接收方处理帧的速度不及发送方，则帧可能丢失
• 解决方法：增加流量控制(flow control)机制，得到单工停等协议
  • 接收方每收到一帧，都向发送方返回一个应答帧
  • 发送方每发送一帧，都等待来自接收方的应答帧，之后才发送下一帧

有噪声信道的单工协议

• 在有噪声信道中，帧在传输过程中可能出错
• 解决方法 (ARQ(Automatic Repeat reQuest)协议)
  • 校验和：使接收方能够检测帧是否出错
  • 确认帧：使发送方知道帧已被正确接收
  • 超时重发：发送方在规定时间内未收到确认帧，则重发帧
  • 帧序号：保证接收方不会重复接收帧
• 协议设计要考虑的三种情形
  • 数据帧被正确接收:接收方返回确认帧，发送方收到后继续发送下一帧
  • 数据帧出错或丢失:接收方未收到帧或校验出错丢弃该帧，发送方等待确认帧超时后，重发数据帧
  • 确认帧出错或丢失:发送方未收到有效的确认帧，重发数据帧，接收方收到后，检查帧序号重复，不上交该帧，只返回确认帧

滑动窗口协议

简介

• 传输链路存在时延，而ARQ协议在同一时刻仅有一个 帧在链路上传输(数据帧或确认帧)，其对信道的利用率 较低
• ARQ协议的信道利用率过低(尤其当传输时延较长时)

滑动窗口协议原理(sliding window protocol)

• 滑动窗口协议的基本思想
  • 允许发送方连续发送多个帧
  • 通过滑动窗口实现流量控制
    • 每个待发送的帧都有一个序列号
    • 发送方维护一个发送窗口，它包含一组序列号，对应允许它发送的帧
    • 接收方维护一个接收窗口，对应允许它接收的帧
• 发送方
  • 发送窗口内的序列号代表允许它发送的帧
    • 窗口内最大的序列号称为窗口上边界，或窗口上沿、前沿
    • 窗口内最小的序列号称为窗口下边界，或窗口下沿、后沿
  • 每当从网络层得到一个数据包，将其组成帧发出后，发送窗口的上边界+1
  • 发送窗口下边界的帧被接收方确认后，下边界+1
• 接收方
  • 接收窗口内的序列号代表它可以接收的帧
  • 收到的帧序列号等于窗口下边界时，将该帧上交网络层，并返回确认帧，同时整个窗口向前移动1个位置
  • 如果收到帧序列号落在接收窗口之外，则将其丢弃
  • 注意：接收窗口总是保持固定大小

后退N帧的滑动窗口协议(Go back N)

• 当某帧出错时，该帧之后的帧全被丢弃，从出错帧开始重新发送
• 实际上此时接收窗口宽度为1

选择性重传的滑动窗口协议(selective repeat)

• 当某帧出错时，只选择性地重发该帧，该帧之后发送的帧由接收方数据链路层缓冲，收到重发的出错帧后上交给网络层
• 当接收方检测到出错帧时，发送一个否定的确认(NAK, Negative Acknowledgement)
  • 带来的好处：发送方可以尽快重发出错帧，而不必等到超时
• 该协议要求接收方能够临时性缓冲接收窗口内的帧
• ACKn表示n 及 n以前的帧均已被正确接收

点对点协议 PPP

• 早期的数据链路层协议：HDLC(High-level Data Link Control)

ppp协议的特点

• PPP (Point-to-Point Protocol)：一种数据链路层协议，广泛应用于点到点链路的数据传输
  • 拨号上网、光纤传输、…
• 1992 年制订，1993和 1994 年修订，成为Internet标准RFC 1661
• PPP 协议有三个组成部分
  • 将 IP 数据报封装到串行链路的方法
  • 链路控制协议 LCP (Link Control Protocol)
  • 网络控制协议 NCP (Network Control Protocol)

PPP的帧格式

• PPP 是面向字节的，所有的 PPP 帧的长度都是整数字节
• 标志字段F：=0x7E (二进制：01111110)
• 地址字段A：置为 0xFF，实际上不起作用
• 控制字段C：通常置为 0x03
• 协议字段：2字节，用于识别信息字段(又称为载荷,payload)的类型
  • 0x0021：PPP 帧的信息字段是IP 数据报
  • 0xC021：信息字段是 PPP 链路控制数据(LCP)
  • 0x8021：信息字段是网络控制数据(NCP)
• 校验字段FCS：2字节的CRC校验

• PPP的透明传输问题(帧边界识别)

  • 同步传输( 如SONET/SDH)：零比特填充
  • 异步传输：字符填充

• 字符填充

  • 信息字段(载荷)中的每一个0x7E -> 0x7D, 0x5E
  • 信息字段中的每一个0x7D -> 0x7D, 0x5D
  • 信息字段中的每一个ASCII 码控制字符(小于 0x20 的字符)前面加入 0x7D，且编码改变

• 零比特填充

  • 发送端：只要发现有 5 个连续 1，则立即填入一个 0
  • 接收端：对帧中的比特流进行扫描，每当发现 5 个连续1时，就把这 5 个连续 1 后的一个 0 删除

PPP 协议的工作状态

介质访问控制

局域网的数据链路层

• 局域网的主要特点:网络为一个单位所拥有，且地理范围和站点数目均有限
• 局域网要解决的重要问题：介质访问控制技术
  • 静态划分信道
    • 频分复用
    • 时分复用
    • 波分复用
    • 码分复用
  • 动态介质访问控制(多点访问)
  • 随机访问：用户可随机发送信息，可能产生碰撞(冲突)
    • 典型协议：ALOHA、CSMA、CSMA/CD、CSMA/CA等
  • 受控访问：如多点线路探询(polling)，或轮询 -> 局域网中使用较少

CSMA/CD协议

• Carrier Sense Multiple Access with Collision Detection载波监听多点访问/碰撞检测

  • 注意：collision又被译为“冲突”
  • 是一种随机访问协议

• CSMA/CD的几个核心概念

  • 载波监听(carrier sense)
    • 结点在发送数据之前先检测一下总线上是否有其他结点正在发送数据，如有则暂时不要发送数据，以免发生碰撞  “发送前先听”
  • 碰撞检测(collision detection)
    • 结点边发送数据边检测信道上是否发生了碰撞(监听总线上传输的信号)  “边发送边听”
    • 由于线路的传播时延，单纯靠载波监听并不能完全避免碰撞  碰撞仍有可能发生
    • 在发生碰撞时，两个或更多的信号在总线上相互叠加，导致无法识别
  • 碰撞强化
    • 发送方检测到碰撞后，立即停止发送，并发送32或48bit的人为干扰信号(jamming signal)，以便让所有用户都知道已经发生了碰撞
  • 碰撞退避
    • 碰撞后，结点等待一段时间，重新开始载波检测和发送操作
    • 为避免退避后再次碰撞，冲突各方的等待时间应各不相同
    • 以太网采用截断二进制指数退避算法(truncated binary exponential backoff)
      • 退避时间：T = 2τ×倍数
      • 倍数：在0, 1, …, 2k-1中取随机数，k = min(重传次数, 10)
      • 重传次数超过16后，丢弃该帧，并向上层报告

• 争用期

  • 一个站点开始发送数据后，最多经过时间 2τ(两倍的端-端时延 )就可知道是否发生了碰撞
  • 以太网的端到端往返时延 2τ称为争用期，或碰撞窗口
  • 如果经过争用期还没有检测到碰撞，就可以肯定这次发送不会发生碰撞

• 以太网的争用期

  • 以太网的争用期长度：51.2 us
  • 对于 10 Mb/s 以太网，在争用期内可发送512 bit，即 64 字节
  • 在发送数据时，若前 64 字节未发生碰撞，就不会发生碰撞
  • 据此规定以太网帧长≥ 64 字节，长度小于 64 字节的帧为无效帧

• CSMA/CD协议的优缺点讨论

  • 网络负载较轻时效率高
  • 硬软件实现简单、灵活
  • 网络负载较重时，碰撞发生概率增大，网络效率较低
  • 由于存在多次冲突的可能，数据从发送方到达接收方的时间没有保证 -> 实时性较差

局域网技术标准

• IEEE802标准将局域网的数据链路层分为两个子层
  • LLC(Logic Link Control)逻辑链路控制子层
  • MAC(Media Access Control)介质访问控制子层

以太网

以太网(Ethernet)简介

• Ether：以太
• 1975年，Xerox公司Palo Alto研究中心(PARC)研制
• 1980年，DEC、Intel和Xerox公司联合推出以太网标准DIX v1
• 1982年，DIX v2
• 1983年，IEEE802.3标准

以太网物理层

• 最初的以太网为总线结构，采用50Ω同轴电缆，传输速率10Mbps

  • 缺点：总线上单点故障会导致全网瘫痪，网络中结点数较多时可靠性较差且维护困难；同轴电缆成本较高

• 后发展为采用更便宜和灵活的非屏蔽双绞线，使用集线器(HUB)连接各个结点，物理上呈星形结构

  • 此种技术称为10Base-T(10：10Mbps，Base：基带传输，T：双绞线(Twisted pair))
  • 使用集线器的以太网在逻辑上仍是一个总线网
  • 集线器很像一个多接口的转发器，工作在物理层

• 采用曼彻斯特(Manchester)编码

  • 用电平的跳变表示0 或 1，即每个码元都有电平跳变

以太网的MAC层

• 以太网采用CSMA/CD介质访问控制协议

• MAC地址

  • 结点发送数据时，以太网总线结构，总线上的所有结点都能收到帧
  • 按照IEEE802.3标准，给每个结点分配唯一的MAC地址
  • MAC地址为48 bit，高24bit为厂商标识符，低24位由厂商自行分配，须保证每个网络接口具有全球唯一的MAC地址

• 适配器每收到一个帧就检查帧中的目的MAC地址，如果是发往本站的帧则进行处理，否则丢弃

  • “发往本站的帧”包括以下三种帧：
    • 单播(unicast)帧 (一对一)
    • 广播(broadcast)帧 (一对全体)，MAC地址为全1表示广播
    • 组播/多播(multicast)帧 (一对多)

• 以太网的帧格式(5个字段)

  • 目的地址、源地址：各6字节的MAC地址
  • 类型：2字节，标明上层协议类型，例：0x0800表示IP包
  • 数据：网络层数据报，长度46 ~ 1500字节
  • FCS：4字节，帧校验序列，采用CRC校验

高速以太网

• 快速以太网(Fast Ethernet)

  • IEEE802.3u标准
  • 传输速率100Mb/s
  • 仍使用 IEEE 802.3 CSMA/CD 协议(全双工模式时不用)
  • MAC 帧格式仍然是 802.3 标准规定的
  • 最短帧长不变，但将一个网段的最大电缆长度减小到100m
  • 线缆标准
    • 100BASE-TX：使用2 对UTP 5 类线或屏蔽双绞线 STP
    • 100BASE-FX：使用1对光纤
    • 100BASE-T4：使用4 对 UTP3类线或5类线

• 千兆以太网(Gigabit Ethernet)

  • IEEE802.3z标准
  • 传输速率1Gb/s
  • 仍使用 IEEE 802.3 CSMA/CD 协议(全双工模式时不用)
  • 线缆标准
    • 1000BASE-X：基于光纤
      • 1000BASE-SX SX表示短波长
      • 1000BASE-LX LX表示长波长
      • 1000BASE-CX CX表示铜线
    • 1000BASE-T：使用 4 对 5类双绞线UTP

• 万兆以太网(10Gbps以太网)

  • IEEE802.3ae标准
  • 传输速率10Gb/s
  • 帧格式不变
  • 传输介质：光纤、双绞线(10GBase-T)
  • 只工作在全双工模式，不存在争用，因此不用CSMA/CD

• 更高速的以太网

  • IEEE802.3ba: 40GE，传输速率40Gb/s
  • IEEE802.3bm: 100GE，传输速率100Gb/s

局域网互连

在物理层扩展局域网

• 使用中继器(repeater)或集线器(HUB)可实现局域网在物理层的互连
  • 优点：可以方便地实现网络的扩展，且成本较低
  • 缺点：碰撞域增大，碰撞发生概率增大，可能影响网络性能

在数据链路层扩展局域网

• 使用网桥(bridge)可实现局域网在数据链路层的互连

• 网桥的基本工作原理

  • 根据 MAC 帧的目的地址对收到的帧进行转发
  • 具有过滤帧的功能：当收到一个帧时，检查该帧的目的 MAC 地址，确定将该帧转发到哪一个接口(并不向所有的接口转发帧)

• 用网桥实现局域网互连的优点

  • 过滤通信量、增大吞吐量
    • 各网段是独立的碰撞域
  • 扩大了物理范围
  • 提高了可靠性
  • 可互连不同物理层、不同 MAC 子层和不同速率的局域网

• 用网桥实现局域网互连的局限性

  • 存储转发增加了时延
  • 在MAC 子层并没有流量控制功能
  • 网桥只适合于用户数不太多(不超过几百个)和通信量不太大的局域网

• 多接口网桥—交换机

  • 交换机(switch)早期称为交换式集线器(switching HUB)
  • 通常有十几到几十个网络接口，每个接口可连接主机或其他交换机
  • 其内部工作原理为网桥，每一个网络接口被视为一个网段，因此交换机是一种多接口网桥
  • 与集线器相比
    • 交换机工作在数据链路层，每个接口为一个网段(碰撞域)，可以大幅提高网络性能
    • 集线器由所有接口共享传输介质的带宽，而交换机为每个接口独享带宽
  • 交换机按照自学习算法(self-learning)建立转发表

• 透明网桥还使用生成树算法(spanning tree)

  • 用途：当多个局域网互连形成环路时，避免帧无休止转发
  • 方法：建立生成树
    • 互连在一起的网桥彼此通信后，能找出网络拓扑的一个子集。在该子集中，整个连通的网络中不存在回路，即在任何两个站之间只有一条路径
    • 考虑到网络拓扑动态变化，生成树需定期更新

• 虚拟局域网(VLAN)

  • VLAN(Virtual LAN)，在现有局域网基础上，通过将网络站点分组，构成若干逻辑上独立的虚拟局域网
  • VLAN的用途：便于管理、控制广播风暴、安全性、…(帧不会在两个VLAN之间自动转发，包括广播帧)
  • IEEE 802.1Q在以太网帧中扩展VLAN标记(tag)，供交换机识别和转发