2022 Spring,cy 老师的计网原。算是当期末的背诵提纲使用吧。希望不会咕咕咕。

“补完计划”是指半期开始才开始做这个东西。

介质访问子层基础

本节目标

  1. 了解 MAC 子层的位置和功能

  2. 掌握两种 ALOHA 协议的原理和性能

  3. 掌握 CSMA 的工作原理及性能区别

  4. 掌握经典以太网的拓扑和帧结构

  5. 掌握以太网 CSMA/CD 中最小帧长与相关参数的关系

  • 多路访问协议

image-20220331103939307image-20220331115410069

Mac 子层

image-20220331103335999

数据链路层分为两个子层:用于介质访问控制的 Mac 子层(Medium Access Control)和逻辑链路控制 LLC 子层。

随机访问

ALOHA 协议

纯 ALOHA 协议

纯 ALOHA 协议的工作原理是想发就发,而两个或以上的帧随时可能会冲突。发生冲突的帧被完全破坏,破坏了的帧要进行重传。

为了便于分析我们定义以下概念并做出相应假设:

  • 帧时:发送一个标准长的帧所需的时间
  • 网络负载:某段时间内所有通信站点总共发送的平均帧数,即平均负载 $G$
  • 某个帧时内,到达帧数为 $k$ 的概率为 $P[k] = \dfrac{G^k}{k!}\times e^{-k}$.
    • $k=0$ 时表示该帧时内没有帧到达的概率为 $P[0] = e^{-G}$.

image-20220331110240317

纯 ALOHA 协议的冲突危险期是 $2D$,其中 $D$ 是帧时长度。这是因为针对一个数据帧来说,另一个数据帧只有其发送时间在这个数据帧的发送时间的 $\pm D$ 之外,才可能与其不冲突。

于是,想要成功传输一个帧,这 $2D$ 的时间内应该均没有其他帧到达。于是该帧被成功传输的概率为 $P[0]^2=e^{-2G}$.

在一个帧时内,纯 ALOHA 协议平均成功传输的帧数为:$S=G\times e^{-2G}$,当 $G=0.5$ 时,$S_{max} \approx 0.184$.

分隙 ALOHA 协议

分隙 ALOHA(Slotted ALOHA)将连续的时间离散化成时隙,每一个 Time Slot 的长度就是 $D$。其规定每一帧的发送只能在时隙的起点。也就是说,既然冲突就彻底冲突,要不然就不可能冲突:

image-20220331110624254

这样做将冲突危险期降为了 $D$,一个帧时内平均成功传输的帧数 $S=G\times e^{-G}$,当 $G=1$ 时 $S_{max}=\frac 1 e \approx 0.368$.

CSMA 协议

CSMA 协议是载波侦听多路访问协议(Carrier Sense Multiple Access)的缩写。载波监听是说站点在为发送帧而访问传输信道之前,首先会监听信号是否已有载波。若已有载波,即有其他用户在使用信道,则不发送帧以避免冲突。

CSMA 协议的特点:“先听后发”。

持续式 CSMA

特点:

  • 经侦听,若介质空闲则发送
  • 若发送时出现冲突则等待随机时间再重复侦听步骤
  • 如介质忙则持续侦听,一旦空闲立即发送

优点:

  • 持续侦听的等待延迟较小

主要问题:

  • 如果两个以上的站等待发送,一旦介质空闲就一定会发生冲突
非持续式 CSMA

改进:

  • 如介质忙,则等待随机时间,然后再次侦听

优点:

  • 等待一个随机时间可以减少再次碰撞冲突的可能性

主要问题:

  • 信道利用率下降,传输时延增加:等待时间内介质上如果没有数据传送,则浪费了时间
p-持续式 CSMA

改进:

  • 经侦听,如介质空闲,那么以 $p$ 的概率发送,以 $1–p$ 的概率延迟一个时间单元发送
  • 如介质忙,持续侦听,一旦空闲重复上述步骤
  • 如果发送已推迟一个时间单元,再重复上述步骤

这就类似于 Russian Roulette…

持续式 CSMA 事实上是 1-持续式 CSMA.

image-20220331111701225

如 0.01-persistent CSMA,高吞吐量可能意味着高时延…

受控访问

位图协议

每个周期划分成两个时段:

  • 竞争期:在自己的时槽内发送竞争 Bit,举手示意预留资源(Contention Slot)
  • 传输期:按序发送,明确使用权,避免冲突

image-20220331112032634

假设有 $N$ 个用户,需 $N$ 个时隙,每帧 $d$ bit。则信道利用率:

  • 当在低负载时:$\omega = \dfrac d {d+N}$
  • 当在高负载时:$\omega = \dfrac d {d+1}$

    位图协议的缺点:位图协议时延较大,没有考虑优先级。

二进制倒计数协议

将所有站点编二进制序号。若站点要占用信道则广播该信号,不同站发的地址按位或。一旦某站了解到比本站地址高位更高的位置被置为“1”,便放弃发送请求。

N个站的二进制编码所需位数是 $\log_2N$ 位,每帧 $d$ 比特,信道的利用率为:$\omega = \dfrac d {d+\log_2 N}$。

如何实现 100% 的利用率?如果规定每个帧的帧头为发送地址,竞争时也在发源地址,则效率为 100%。

特点分析:高序号站点优先。

IEEE 802.5 令牌环

令牌(Token)便是使用信道发送信息的权限。令牌环是说令牌在站点环中不断传递,发送站点抓取环中传输的令牌,获得发送权,从而向环中发送数据帧。为了防止无限循环,环上的帧需要由目的站或发送站将其从环上去除,重新生成令牌,并转入监听模式。

  • 环的维护:环上存在一个监控站,负责环的维护,通过站的竞争产生令牌
  • 监控站的职责:保证令牌不丢失;处理环断开情况;清除坏帧,检查无主帧;
  • 优点:重负载下,效率接近 100%;除了环,令牌也可以运行在其它拓扑上,如令牌总线;
  • 缺点:令牌具有其维护代价。

有限竞争

自适应树搜索协议

image-20220331114703935

将所有站点组织成一颗二叉树结构。初始时所有站可以竞争信道,如果只有一个站要使用信道则直接发送。

不然,在第 1 槽内半数站(2 以下站)参与竞争,如其中之一获得信道,本帧后的时槽留给 3 以下的站。

重负载时,从根结点开始竞争,发生冲突的概率非常大。为提高效率,可以从中间结点开始竞争。

Mac 子层进阶

经典以太网:Mac 子层

image-20220407102316451

CSMA 协议确实是在侦听到介质上没有数据发送时才发送,而发送后在实际应用中却仍然可能发生冲突。这包括两种可能的情况:

  • 同时传送
  • 传播延迟时间

而面对潜在的冲突,我们可以使用 CSMA/CD(CSMA with Collision Detection,载波监听冲突检测)模式,即先听后发,边发边听。

image-20220331120232405

Collision Detection 的 Motivation:两个帧发生冲突之后,继续传输损坏帧毫无意义,浪费信道。如果站点边发送便监听,如果监听到冲突则停止发送,则可以提高信道的利用率。

CSMA/CD 的工作过程:

  • 经侦听,若介质空闲则发送
  • 若介质忙则持续侦听,一旦空闲立刻发送
  • 如果发生冲突,立即停止并发送 Jam(强化)信号,等待一个随机分布的时间再重复步骤

Jam 信号是向连接中的所有站点汇报“有冲突发生”,停止传输。

image-20220331120619288

定义冲突窗口为发送站发送帧后能检测到冲突的最长时间,如上述的 $t_4-t_0$。冲突窗口最大为 $2D=RTT$,其中 $D$ 为单边延迟。

这对发送方提出了需求:在发送一帧的同时,完成该帧的冲突检测。如有冲突,则要求在一帧发送完成前检测到冲突。

因此要求发送方①帧与帧之间的发送间隔至少为一个冲突窗口的时间,即 $2D$. 除此之外,我们还需规定②最短帧长

二进制指数后退的 CSMA/CD

  • 确定基本退避时间槽,其长度为以太介质上往返传播时间($2𝜏$),以太网中设为 512 Bit 时间
  • 定义重传次数 $k$ 满足 $k = \min {\{\text{cnt}, 10\}}$.
  • 从整数集合 $[0,1,\cdots, 2k −1]$ 中随机地取出一个数,记为 $r$
  • 重传所需的时延就是 $r$ 倍的时间槽 $2𝜏$
  • 当重传达 16 次仍不能成功时即丢弃该帧,并向高层报告

接下来进行效率分析。假设 $F$ 为 frame length,$B$ 为 bandwidth,$L$ 为电缆长度,$c$ 为信号传输速度,每帧有 $e$ 个竞争时间槽。记 $P := F / B$.

信道效率 $\omega = \dfrac P {P + 2𝜏 /A}= \dfrac 1 {1 + 2BLe/cF}$,其中 $A$ 是某个站获得信号的概率。

帧结构

image-20220407102404300

  • 硬件地址又称为物理地址,或 MAC 地址
  • MAC帧中的源地址和目的地址长度均为6字节

单播、广播、组播与 Mac 地址

image-20220407101113601

  • 单播:发送者发送四份相同的数据
  • 组播:发送者发送一份数据,由路由器进行复制。若上路接收端撤走则上路不再发送。
  • 广播:发送者发送一份数据,由路由器进行复制。类似于全域搜索。

这体现在 Mac 地址的编号中:

image-20220407101459041

  • 前 3 个字节为生产厂商特有,后 3 个字节为生产厂商进行指定。
  • 原地址的 $b_1$ 位只可能是 $0$。
  • 接收端除了精准匹配目的地址与自己的 Mac 地址相同(单播)之外,还应该注意广播与组播的情况,比如 $\text{FF-FF-FF-FF-FF-FF}$.

数据包类型

  • IPv4: 0x0800
  • ARP: 0x0806
  • IPv6: 0x86DD
  • PPP: 0x880B
  • PPPoE: 0x8864

数据字段

image-20220407102459233

  • 允许的数据字段为 $46$ ~ $1500$ 字节。
  • 最小帧长 $46+18=64$ Byte.
  • 最大帧长 $1500+18=1518$ Byte.
  • 也就是说,给予上层的最大传输单元 MTU:1500 Byte.
  • 数据字段不足 46 字节,需要填充整数字节(Padding)至 46 字节,以保证以太网 Mac 帧不小于 64 字节。

校验和

  • FCS, Frame Check Sequence

  • 使用 CRC32 计算除了校验和以外的其他字段

  • 对于检查出的无效 MAC 帧就简单地丢弃,以太网不负责重传丢弃的帧

链路层交换原理

先考虑使用集线器来进行以太网的组建。集线器是物理层的设备,所有端口内部都是连通的,使用同一根总线。使用 Hub 来扩展以太网,不仅不会增加集线器的容量,还限制了网络的可扩展性。

我们或许可以通过“分域”的方式来解决这个问题,而这里便用交换机来替代集线器。

image-20220407105130838

我们的目标是在交换机中建立“转发表”,关联站地址与接口。

image-20220407110555004

如何避免手工配置呢?可以采用“逆向学习源地址”的方式,根据接收到的帧完善 Mac 地址表。

Mac 地址表的工作方式

image-20220407110739162

image-20220407110743359

image-20220407110748765

安全隐患的防范:防止 Mac 地址表溢出?

  • 设定老化时间(默认 300 s)
  • 当老化时间到期时,该表项会被清除
  • 在“逆向学习”更新表项时,同时更新其老化时间

生成树协议

树形的拓扑结构使得任何一条“割边”被去掉之后,网络就变成了两个连通支。可靠的网络需要冗余的拓扑结构,但是可能会导致物理环路的产生。

物理环路的产生具有下列问题:

Mac 地址表不稳定 当一个帧的多个副本到达不同端口时,交换机会不断修改同一 Mac 地址对应的端口。

image-20220407112309625

重复帧 X 发送到环路的单播帧,造成目的设备 Y 收到重复的帧。

广播风暴 交换机(网桥)在物理环路上无休止地泛洪广播流量,无限循环,迅速消耗网络资源。

image-20220407112436267

物理环路的解决思路?建网的时候建成复杂的图拓扑结构,而使用的时候构造最小生成树!

而实际运用时,我们对于这张“图”的拓扑结构并不知情,图中的每个结点都是一个单独的交换机,和其他的交换机连接与否均存在可能。

BPDU 与生成树的选举

接下来介绍如何得到一颗无环的生成树。参与组网的交换机需要收发 BPDU(桥协议数据单元)选举产生根桥、根端口、指定端口,形成生成树。

image-20220407114215580

生成树的三个选举过程:

  • 选举根桥作为整个局域网的根(树根)
    • 首先比较优先级,优先级数值最小的交换机胜出成为根桥
    • 如果优先级数值相等,MAC 地址最小的交换机成为根桥
    • 根桥的所有端口都处在转发状态
  • 为每个非根桥选出一个根端口
    • 每个非根桥,通过比较其每个端口到根桥的根路径开销,选出根端口
    • 具有最小根路径开销的端口被选作根端口
    • 如果多个端口的根路径开销相同,则端口ID最小的端口被选作根端口
    • 非根桥只能有一个根端口,根端口处于转发状态
    • 定义“路径开销”为路径的 Capacity

image-20220407114605184

  • 为每个网段确定一个指定端口

    • 即代表端口,代表这个网段向其他网段转发数据
    • 对于每一个网段,在所有连接到它的交换机(网桥)端口中进行选择
    • 一个具有最小根路径开销的端口,作为该网段的指定端口
    • 指定端口处于转发状态,负责该网段的数据转发
    • 连接该网段的其他端口,若既不是指定端口,也不是根端口,则阻塞
  • 端口角色与端口状态

image-20220407115511884

为了适应网络的动态变化:

image-20220407115825127

源路由网桥

源路由(Source Routing)网桥的需求分析

  • 目的地定位:发送者需要知道目的主机在哪里

    • 如果不在自己的 LAN 里,在发出的帧头内构造一个准确的路由序列,包含要经过的网桥、LAN的编号
    • 网桥对接收到的帧,决定是否采用源路由
  • 通过广播“发现帧”(Discovery Frame)获得最佳路由(在搜索时记录中间路径)

    • 源站若需要定位目的地,则发送“发现帧”,每个网桥收到后广播
    • 该帧经过网桥时被加上桥标识(接口标识),目的站收到后发应答帧
    • 源站收到后就知道了到目的站的最佳路由
  • 优点:对拓扑和带宽进行最优使用
  • 缺点:网桥的插入对于网络是不透明的(要进行端-网协同)

image-20220407120832227

链路层交换机

交换机是一种即插即用网络设备,执行数据链路层交换算法。其交换方式从带宽的角度可以分为对称交换与非对称交换两种,这取决于出和入的带宽是否相同。

image-20220407121138075

链路层交换机的三种交换模式:

存储转发 转发前必须接收整个帧、执行 CRC 校验。这样可以不转发出错帧、支持非对称交换,而转发延迟较大。

直通交换 一旦接收到帧的目的地址,就开始转发。这样延迟非常小,可以边入边出,但可能转发错误帧,不支持非对称交换。

image-20220407121317152

无碎片交换 接收到帧的前 64 字节,即开始转发。这样过滤了冲突碎片,延迟和转发错帧介于存储转发和直通交换之间,但仍可能转发错误帧,不支持非对称交换。

image-20220407121350899

VLAN

广播域 广播域是一个广播帧能够到达的范围。在缺省情况下,交换机所有端口同属于一个广播域,无法隔离广播域。广播帧在广播域中传播,占用资源,降低性能,且具有安全隐患。

image-20220414103157970

虚拟局域网 需要在物理网络上根据用途、工作组、应用等来进行逻辑划分的局域网络,与用户的物理位置没有关系。

每一个 VLAN 是一个独立的广播域,交换机通过划分 VLAN 来分隔广播域。不同 VLAN 的成员之间不能直接进行二层通信。

image-20220414103237277

VLAN 类型

VLAN 有四种类型,包括基于端口的、基于 MAC 地址的、基于协议的和基于子网的。

基于端口的 VLAN 增加 VLAN Table,存储 VLAN ID 与 端口 的关系。

image-20220414103455111

基于 MAC 地址的 VLAN 增加 VLAN Table,存储 VLAN ID 与 MAC 地址 的关系。

image-20220414103541618

基于协议的 VLAN 增加 VLAN Table,存储 VLAN ID 与 协议 的关系。

image-20220414103608166

基于子网的 VLAN 增加 VLAN Table,存储 VLAN ID 与 子网 的关系。

image-20220414103814578

问题 如何让交换机区分不同 VLAN 的数据帧?

在数据帧中需要携带 VLAN 标记…VLAN 标记由交换机添加/剥除,对终端站点透明。

image-20220414104950548

帧标记标准 IEEE 802.1Q

image-20220414105155439

Access 端口与 Trunk 端口

接入链路类型端口可以通过指定 VLAN 的流量,干道链路允许多个 VLAN 的流量通过。

image-20220414105507630

WLAN

无线局域网 指以无线信道作为传输介质的计算机局域网。

无线局域网的组网模式

image-20220414110721285