概述

数据链路层经一条链路,将数据从一个节点传输到相邻节点

节点:主机和路由器

链路:连接通信路径中相邻节点的路径

链路层服务

  • 将数据报封装进帧

  • 帧首部的MAC地址标识源、目的地

  • 相邻节点的可靠交付

  • 流量控制

  • 差错检测

  • 纠错

差错检测和纠错

基本原理

  • 发送方:信息数据+冗余数据

  • 接收方:检查信息数据和冗余数据的关系,发现差错

奇偶校验

设置奇偶校验位

  • 1的数量为奇数,奇偶校验位设为1

  • 1的数量为偶数,奇偶校验位设为0

检查和

  • 发送方计算检查和:求和、回卷、求反(运输层UDP部分)

  • 接收方重新计算检查和,与字段值进行对比

循环冗余码校验 CRC

基本思想

信息位 K位 校验位 R位

数据发送、接受方约定一个除数

K个信息位和R个校验位作为被除数,添加校验位后需保证除法的余数为0

收到数据后,进行除法检查余数是否为0

若余数非0说明出错,进行重传或纠错

本部分中的二进制除法

举例:

生成多项式为$ G(x) = x^3 + x^2 + 1 $,即除数为1101。信息码为101001,求CRC码。

如图。

CRC码计算方法.png

  1. 首先确定余数位数:余数位数 = 除数位数-1 = 校验码位数 = 3

由于对校验码的要求是:(信息码+校验码)为除数的整数倍

故在计算时应在信息码后补[余数位数]个0,即3个0

  1. 二进制除法,以1、0作为商的每一位

  2. 对被除数和除数每一位做异或运算(相同为0,不同为1)

  3. 直至补完3个0,得到校验位

将信息码与校验码拼接得到CRC码

构造方法

CRC生成(批注).png

  1. 确定信息码长度K、生成多项式的最高次幂R,CRC位数为N=K+R=9

    仍以上文举的例子为例,信息码=101001,位数为6;生成多项式=x^3^+x^2^+1,最高次幂为3,CRC位数为6+3=9

  2. 移位。信息码左移R位,低位补0(或者理解为,在信息码后补R个0)

  3. 相除。用2中补完0的数作为被除数,除生成多项式,取余数,生成CRC码。

检错和纠错

上文生成的CRC为101001001,与1101进行除法,若余数为000,代表没有出错;若余数为010,十进制值为2,代表第2位或第9位出错

CRC检错.png

对于3位余数,可以表示2^3^-1=7位错位(000表示没有出错)

如果出错的位数没有超过余数所能表示的范围,则出错位之间就算一一对应的关系,CRC码可能纠错。

多路访问协议

碰撞:单一广播信道,节点的两个或更多并行传输,产生干扰,如果节点同时接收两个或更多信号,则称发生了碰撞

决定节点怎样共享信道的分布式算法

必须使用信道本身,不用外信道来协调

理想的多路访问协议

  1. 当一个节点要传输,它能够以速率R发送

  2. 当M个节点要传输,每个能以平均速率 $\frac{R}{M}$ 发送

  3. 全分散

    • 无特殊节点来协调传输

    • 无同步时钟、时隙

  4. 简单

MAC协议分类

三大类:

  • 信道划分

    • 将信道划分为较小的”段“(时隙,频率,编码)

    • 为节点分配一部分专用

  • 随机访问

    • 不划分信道,允许碰撞

    • 从”碰撞“恢复

  • 轮流协议

    • 节点轮流,有更多信息要发送的能够轮流较长的时间

信道划分协议

时分多路复用:TDMA

  • 循环访问信道

  • 每个站点在每个循环中获得固定长度时隙(长度=分组传输时间)

  • 不使用的时隙空闲

举例:

1 3 4 1 3 4

如图,6个站点的的LAN,划分出6段时隙;时隙1、3、4有分组,而2、5、6空闲

频分多路复用:FDMA

  • 信道频谱划分为频带

  • 每个站点分配固定的频带

  • 频带中未使用的传输空间空闲

举例:

FDMA.png

6个站点的LAN,划分出6道频带;频带1、3、4有分组使用,2、5、6空闲

随机访问协议

  • 当站点有分组要发送

    • 以信道全部速率R传输

    • 节点间无优先权协调

  • 两个或更多传输节点——碰撞

  • 随机访问MAC协议定义了

    • 如何检测碰撞

    • 如何从碰撞中恢复

时隙ALOHA

  1. 假定

    • 所有帧有相同长度

    • 时间划分为等长时隙,每个时隙能够传输1个帧

    • 节点仅在时隙开始时开始传输帧

    • 节点是同步的

  2. 操作

    • 当节点获得新帧,将在下一个时隙中传输

    • 无碰撞,节点能够在下一个时隙中发送新帧

    • 如果碰撞,节点在每个后续时隙中以概率p重传帧

    时隙ALOHA.png

    如上图所示,c表示碰撞,S表示成功发送帧,E表示空闲时隙

    在第一个C时隙,节点1、2、3同时传输帧,发生碰撞

    在第二个C时隙,节点1、2同时传输帧,发生碰撞

    紧接着下一个时隙,节点2成功发送帧

    以此类推,不再重复描述

  3. 优点

    • 单个活跃节点能够连续地以信道的全速传输

    • 高速分散:仅节点中的时隙需要同步

    • 简单

  4. 缺点

    • 碰撞浪费时隙

    • 有空闲时隙

    • 节点可能能够以小于传输分组的时间检测到碰撞

    • 时钟同步

  5. 效率

    • 定义:节点发送成功的时隙与总时隙的长度比值

    • 假定N个节点,每个时隙以概率p发送。对于节点一,在某一个时隙中发送成功的概率为 $p(1-p)^{N-1}$

    • 任何节点发送成功的概率为 $Np(1-p)^{N-1}$

    • 对N节点为使效率最大化,求p,使 $Np(1-p)^{N-1}$ 最大化

      当N趋近无穷大,取 $Np(1-p)^{N-1}$ 极限,得到 $\frac{1}{e}=0.37$

    信道用于有用传输的时间是 37%

非时隙ALOHA

  • 无同步要求

  • 当帧到达立即传输

  • 碰撞概率增加:在t0发送与在[t0-1, t0+1]的其他帧碰撞

ALOHA.png

纯ALOHA的效率仅为时隙ALOHA效率的一半

CSMA(载波侦听多路访问)

  • CSMA:在传输前侦听

    • 如果侦听到信道空闲,传输整个帧

    • 如果侦听到信道忙,推迟传输

    不要打断他人说话

  • CSMA碰撞

    • 碰撞依然会出现:传播时延导致两个节点也许不能听到其他节点传输

    • 整个分组传输时间被浪费

    • 举例与传播试验

CSMA/CD

  1. 载波侦听:如同在CSMA

    • 发生碰撞后,在短时间内检测到碰撞

    • 终止碰撞的传输,减少信道浪费

  2. 碰撞检测

    • 在有线的LAN中容易:测量信号强度,比较传输的和接收的信号

    • 在无线LAN中困难:无线节点为了节省能源,Frame发送完毕后就会关闭而没有载波

礼貌的交谈着

”轮流“MAC协议

信道划分MAC协议:

  • 在高负载时高效、公平地共享信道

  • 低负载时低有效:信道访问中延时,有空闲时隙

随机访问MAC协议:

  • 低负载时有效:单个节点能够全面利用信道

  • 高负载:碰撞开销

”轮流“协议:

  • 兼有各方优点

轮询协议

  • 主节点”邀请“从节点依次传输

  • 关注问题:

    • 轮询开销

    • 轮询延迟

    • 单点故障(主节点)

令牌协议

  • 控制令牌从一个节点顺序地传递到下一个

  • 令牌报文

  • 关注问题:

    • 令牌开销

    • 时延

    • 单点故障(令牌)

链路层编址

  • IP地址:

    • 网络层地址

    • 用于使数据包到达目的IP子网

  • MAC(或LAN或物理或以太网)地址

    • 用于使数据包从一个接口到达另一个物理连接的接口(同一个网络内)

    • 48 bit MAC地址(对多数LAN)烧在了适配器ROM中

ARP:地址解析协议

问题:已知B的IP地址,怎样决定B的MAC地址?

  • LAN上的每个IP节点(主机、路由器)都有ARP表

  • ARP表:对某些LAN节点的IP/MAC地址映射

    <IP地址; MAC地址; TTL>

    • TTL(寿命):地址映射将被忘记的时间长度(通常为20分钟)

ARP协议:相同的LAN(网络)

  • A要向B发送数据报,并且B的MAC地址不再A的ARP表中

  • A广播ARP请求分组,包含B的IP地址:

    • 目的地MAC地址=FF-FF-FF-FF-FF-FF

    • 在LAN上的所有机器接收ARP请求

  • B接收ARP分组,用它的MAC地址回答A:帧发送到A的MAC地址(单播)

  • A在它的ARP表中缓存IP到MAC的地址对,直到信息超时。

    • 软状态:信息超时除非被更新

ARP即插即用:节点创建它们的ARP表无需网络管理员干预

选路到另一个ARP

目的:从A到B经R发送数据报。

A直到B的IP地址

选路到另一个LAN.png

在路由器R中有两个ARP表,每张表对应一个IP网络(LAN)

  1. A生成具有 源A&目的地B 的数据报

  2. A使用ARP从111.111.111.110(R的IP地址)获取R的MAC地址

  3. A生成以R的MAC地址作为目的地的链路层帧,帧包含 A-to-B 数据报

  4. A的适配器发送帧

  5. R的适配器接收帧

  6. R从以太网帧取出IP数据报,看到它的目的地是B

  7. R使用ARP取得B的MAC地址

  8. R生成包含 A-to-B 数据报的帧向B发送

以太网

  • 共享式以太网

    • 网络中所有主机的收发都依赖于同一套物理介质,即共享介质

    • 同一时刻只能有一台主机在发送,各主机通过遵守CSMA/CD规则来保证网络的正常通讯

  • 交换式以太网

    • 扩展了网络带宽

    • 分割了网络冲突域,使得网络冲突被限制在最小的范围内

    • 交换机更智能,提供更多功能

以太网帧结构

发送适配器在以太网帧(或其他网络层协议分组)中封装IP数据报

以太网帧结构.gif

  1. 前导码:格式为10101010……,共7字节

  2. 帧开始定界符:10101011,1字节

    • 用于同步发送方、接收方时钟速率
  3. 目的地址、源地址:分别为6字节。当网卡接收到一个数据帧,会检查该帧的目的地址是否与自己匹配,若不匹配,丢弃。

  4. 类型:指示较高层次协议,2字节。大部分为IP协议。

  5. CRC:帧检测字段,4字节。见本文”差错检测“小节

以太网使用CSMA/CD协议

  • 载波侦听:先听再说

    • 适配器在发送前监听总线是否空闲,若空闲则发送数据
  • 冲突检测:边说边听

    • 数据在发送的同时保持对总线的监听,发现冲突则停止发送
  • 随机延迟后重发

    • 冲突发生后拟采用指数回退方法等待一段随机事件后,再进行监听和发送

指数回退方法

  • 目标:估计当前负载,适应重传尝试

    • 负载较重:随机等待将更长
  • 首次碰撞:从{0,1}中选择K;时延是 $ K • (512bit传输时间) $

  • 第二次碰撞后:从{0,1,2,3}中选择K

  • N次碰撞后,从{0,1,…2^N-1}中选择K

曼彻斯特编码(以太网编码技术之一)

  • 用于10 Base T

  • 每个比特具有一个跃迁

  • 允许发送和接收节点中的时钟互相同步

    • 节点之间的集中式、全局时钟没有必要
  • 位于物理层

交换机

为数据帧从一个端口到另一个任意端口的转发提供了低时延、低开销的通路

工作在链路层

例子

graph BT

1(集线器)
2(集线器)

A --- 1
B --- 1
C --- 1

D --- 2
E --- 2
F --- 2

1 --- 交换机
2 --- 交换机

交换表:

地址 接口
A 1
B 1
E 2

假定C向D发送帧:

  1. 交换机从C接收帧

    • 注意到C位于接口1,将C添加入交换表中:

      地址 接口
      A 1
      B 1
      E 2
      C 1
    • D不在表中,交换机将向接口2和3转发帧

  2. D接收帧

假定D回答C的帧

  1. 交换机从D接收帧

    • 注意到D位于接口2,加入交换表中

      地址 接口
      A 1
      B 1
      E 2
      C 1
      D 2
    • 因为C在表中,所以直接向接口1转发帧

  2. C接收帧

流量隔离

交换机安装将子网分割成LAN段

graph BT

subgraph 碰撞域1
    1(集线器)
    A --- 1
    B --- 1
    C --- 1
end

subgraph 碰撞域2
    2(集线器)
    D --- 2
    E --- 2
    F --- 2
end

1 --- 交换机
2 --- 交换机

交换机过滤分组:

  • 相同LAN段的帧通常不再其他LAN段上转发

  • 段成为分离的碰撞域

交换机vs路由器

  • 路由器位于网络层,检查网络层首部;交换机位于链路层

  • 路由器维护选路表,实现选路算法

  • 交换机维护交换机表,实现过滤、学习算法

PPP

点对点链路层控制

一个发送方、一个接收方、一段链路

比广播链路容易处理

无媒体访问控制;不需要明确的MAC编址

概述

PPP协议是在点对点链路上运行的数据链路层协议

支持用户认证,是广域网接入使用最广泛的协议

组成

PPP协议.png

  1. 标志字段:0x7E(01111110),1字节。位于开始和结尾,标志PPP数据帧的开始和结束

  2. 地址字段:FF(11111111),1字节。用于指定对方的数据链路层地址,但由于PPP是点对点协议,故此字节无意义,填充为0xFF

  3. 控制字段:固定值0x03,1字节

  4. 协议字段:指定上层协议(IP等),2字节

  5. 数据字段:最长不超过1500字节

  6. FSC:校验字段,2字节

字节填充

PPP帧的标志字段为<01111110>,若在数据字段出现该字节会出错。解决方法为字节填充

当数据字段出现<01111110>字节时:

  • 发送方:重复填充该字节,即将其变为两连续字节:<01111110><01111110>

  • 接受方:

    • 重复<01111110><01111110>:丢弃第一个字节,继续数据接收

    • 单个<01111110>:标志字节