链路层

网络层解决了从一个网络到另一个网络的路由问题, 链路层解决的是一个节点到相邻节点的问题. 点对点 传输层功能.

概述

在第二层中, 数据会封装成协议数据单元帧 frame , 将数据从一个节点通过链路发送到相邻的物理节点.

分组在不同的链路上以不同的链路协议传送

• 在第一跳链路使用以太网;

• 在中间链路使用帧中继链路

• 在最后一跳使用 802.11 无线网络

不同的链路协议也提供不同的服务, 在链路层上也可能提供可靠数据传送服务

链路层服务

• 发送

数据成帧, 链路接入.

将数据报封装在帧里, 加上帧头, 帧尾部. 如果使用的是共享性介质, 信道接入获得信道访问权.

在帧头部使用 MAC 物理地址来标示源和目的

在高差错链路的相邻节点间(一个网络中)进行可靠的转发, 如无线链路

低差错链路很少使用, 协议太复杂了. 要求发送方对每一帧都进行差错控制编码, 根据接收方反馈做出相应动作; 要求接收方进行差错控制解码, 发送 ACK/NAK

• 流量控制 flow control

使得相邻的发送和接收方节点速度匹配

• 错误检测 error detection

差错由信号衰减和噪声引起, 接收方应该可以检测出错误

• 差错纠正

接收端检查和纠正 bit 错误, 不通过重传来纠错

• 半双工和全双工

是半双工的, 链路可以双向传输, 但一次只有一个方向

在哪实现?

链路层在每一个主机, 路由器, 交换机端口上实现.

链路层功能在适配器上实现, 实现链路层和相应的物理层功能.

差错检测和纠正技术

一份数据由数据 D 跟差错检测和纠正比特 EDC(Error Detection and Correction)组成

数据 D 由差错检测保护, 通常也包含链路层头部字段.

错误检测不是 100%正确, 但是大部分时候都会正确. EDC 越长, 检测和纠正效果越好

差错检测

奇偶校验

• 单比特奇偶校验

只能检测一个 bit 错误. 分为奇校验方案和偶校验方案, 不过都一样.

偶校验方案: 设置奇偶校验位, 使 1 的数量为偶数

• 二维奇偶校验

检测和纠正一个 bit 错误

Internet 校验和

目标: 检测在传输报文段时的错误(仅用在传输层)

方法: CRC(循环冗余校验)

UDP 使用的是 16 位校验和而不是 CRC

• 发送方

将 UDP 报文段的内容(包括 UDP 报头字段和 IP 地址)每两个字节作为一个整数, 然后加起来. 如果产生了进位, 把进位加进来. 最后对这个结果按位取反, 就得到校验和了.

• 接收方

计算校验和, 然后比对. 如果不一样那肯定出错了; 如果一样可能出错了也可能没出错.

多点访问协议

多路访问链路和协议

有两种类型(一个子网内部链路连接形式)

• 点对点 point-to-point

以太网交换机和主机之间的点对点链路, 如拨号访问的 PPP

• 广播 broadcast(共享线路或媒体)

传统以太网是这样的.

HFC 上行链路

802.11 无线局域网, 4G/5G, 卫星

---

对于一个单个共享的广播型链路, 如果有两个或者更多站点同时传送就会发生冲突(collision)

多个节点在同一时刻发送, 就会收到 2 个或多个信号叠加.

因此需要 多路访问协议(介质访问控制协议 MAC) . 这是一种分布式算法, 决定节点什么时候可以发送.

关于共享控制的通信必须借助信道本身传输. 没有带外的信息, 各节点使用其协调信道使用; 用于传输控制信息.

理想的多路访问协议

给定一个 R bps 的广播信道,

• 当一个节点要发送时, 可以以 R 速率发送.

• 当 M 个节点要发送时, 每个节点可以以 R/M 的平均速率发送.

• 完全分布式的, 没有特殊节点来协调发送, 也没有时钟和时隙的同步.

• 简单.

MAC(媒体访问控制)协议

分类

三大类

• 信道划分

把信道划分成小片(以时间, 频率, 编码划分)

分配片给每个节点专用

• 随机访问

信道不划分, 允许冲突.

冲突后恢复

• 依次轮流

节点依次轮流, 但是有很多数据传输的节点可以获得较长的信道使用权

信道划分 MAC 协议

时分复用 TDMA

TDMA, time division multiple access 时分复用

约定轮流使用信道, 信道的时间分为周期, 每个站点使用每周期中固定的时隙(长度=帧传输时间)传输帧

• 如果站点无帧传输, 时隙(slot)空闲->浪费

如果站点没有要传输的帧, 这个时间片已经交给它, 其它的不能发送.

频分复用 FDMA

FDMA, frequency division multiple access 频分复用

信道的有效频率范围被分成一个个小的频段, 每个站点被分配一个固定的频段

• 分配给站点的频段如果没被使用, 空闲

跟时分复用一样, 空闲别人也不准用

码分多路访问 CDMA

CDMA, code division multiple access, 码分多路访问.

所有站点在整个频段上同时进行传输, 采用编码原理加以区分.

• 完全无冲突

• 前提是信号同步很好, 线性迭代

TDMA 是不同的人在不同的时候说话, FDMA 是不同的组在不同的房间里说话, CDMA 是不同的人用不同的语言说话

随机存取协议

• 当节点有帧要发送时,

以信道宽带的全部 R bps 发送, 并且没有节点间的预先协调

• 两个或更多节点同时传输则产生冲突.

随机存取协议需要解决如何检测冲突和如何从冲突中恢复.

随机 MAC 协议: 时隙 ALOHA, ALOHA, CSMA, CSMA/CD, CSMA/CA

时隙 ALOHA

假设:

• 所有的帧是等长的

• 时间被划分成相等的时隙(slot)

• 每个时隙可以发送一帧

• 节点只在时隙开始的时候发送帧

• 节点在时钟上是同步的

• 如果两个或者多个节点在一个时隙中传输, 所有的站点都能检测到冲突.

运行:

• 当节点准备好新的帧时, 在下一个时隙传输

• 没有检测到冲突, 成功传输

节点能够在下一时限发送新帧

• 检测时如果检测到冲突, 失败

节点在每一个随后的时隙以概率 p 重传帧, 直到成功.

两个节点信号叠加, 能量不一样, 就检测到冲突了.

优点:

• 节点能够以信道带宽全速连续传输

• 高度分布, 仅需要节点之间进行时隙上的同步

• 简单

缺点

• 存在冲突, 浪费时隙

• 即使有帧要发送, 仍然有可能存在空闲的时隙

• 节点检测冲突时间需要小于帧传输时间

• 需要时钟上同步

---

假设有很多节点, 每个节点有很多帧要发送, 成功传输帧的时隙为 X%, 这个 X%就是信道利用率.

对于时隙 ALOHA, 假设 N 个节点有很多帧要发送, 每个节点在时隙传输的概率为 p.

那么一个节点成功的概率是$p\cdot (1-N{)}^{N-1}$

N 个节点成功的概率是$N\cdot p\cdot (1-N{)}^{N-1}$

最理想的情况当然是一个 p 使得上面这个式子最大了.

假定 N 无穷多, 这个极限会趋近于 1/e, 也就是 0.37

因此, 时隙 ALOHA 的最佳情况下, 信道利用率为 37%.

纯 ALOHA(非时隙)

无时隙的 ALOHA 比较简单, 无须节点间在时间上同步. 当节点有帧需要传输时, 马上传输.

但是这样冲突的概率增加了, 帧在$t_0$发送的话, 会与在$[t_0-1,t_0+1]$区间的帧冲突, 原本只会在$[t_0,t_0+1]$区间冲突的. 增大了一倍.

纯 ALOHA 的效率是 17.5%

CSMA(载波侦听多路访问)

CSMA 在传输前先侦听信道:

• 如果信道空闲, 传送整个帧

• 如果信道忙, 推迟传送

冲突仍然可能发生, 这是由传播延迟造成的. 两个节点可能侦听不到正在进行的传输. 如果发生了冲突, 整个冲突帧的传输时间都被浪费了, 是无效的传输.

传播延迟(距离)决定了冲突的概率. 节点需要根据本地的信道使用情况来判断全部信道的使用情况.

CSMA/CD(冲突检测)

CSMA/CD, CSMA with collision detection

CSMA 部分跟之前一样, 先侦听再发送.

没有传完一个帧就可以在短时间内检测到冲突, 冲突发生就传输终止, 减少对信道的浪费.

冲突检测 CD 技术在有线局域网中容易实现,

• 检测信号强度, 比较传输与接收到的信号是否相同

• 通过周期的过零点检测

---

• 以太网 CSMA/CD 算法

1. 适配器获取数据帧, 创建帧

2. 发送前, 侦听信道 CS, 闲就开始传送帧, 忙就一直等到闲再发送.

3. 发送过程中, 冲突检测 CD. 没有冲突就成功了, 有冲突就放弃, 之后尝试重发.

4. 发送方适配器检测到冲突, 除了放弃, 还会发送一个阻塞信号, 所有听到冲突的适配器也会这么做. 这样子可以强化冲突, 让所有站点都知道.

5. 如果放弃了, 适配器等待一段时间后回到 2(如进入指数退避状态).

• 指数退避

这是一种二进制指数退避算法, 用于电缆网络多路访问协议

目标: 适配器试图适应当前负载, 在一个变化的碰撞窗口中随机选择时间点尝试重发. 如果高负载, 重传窗口时间大, 减少冲突, 但是等待时间长; 如果低负载, 使得各站点等待时间少, 但是冲突概率大.

在第 m 次失败后, 适配器随机选择从 0 到$2^m-1$中选一个数 k, 等待 k*512 比特时间, 然后转到步骤 2.

首次碰撞在 0 到 1 选择 k, 第二次碰撞在 0 到 3 选择 k, 依次类推.

---

设$t_{prop}$是 LAN 上两个节点的最大传播延迟, $t_{trans}$是传输最大帧的时间, 则

$$efficiency=1/(1+5(\cdot t_{prop}/\cdot t_{trans}))$$

当$t_{prop}$趋于 0, 或者$t_{trans}$趋于 1, 效率都趋于 1.

这比 ALOHA 性能更好, 简单廉价, 而且分布式

轮流 MAC 协议

信道划分 MAC 协议在高负载时是有效且公平的. 但是在低负载时效率低下.

随机访问 MAC 协议在低负载时高效, 但是高负载时冲突概率大, 冲突开销很大.

轮流协议集成两者优点.

轮询协议

主节点邀请从节点依次传送

缺点

• 轮询开销 轮询本身就需要消耗带宽

• 等待时间 每个节点需要等到主节点轮询后才开始传输, 即使只有一个节点要发送数据, 也得等到轮询一周后才能够发送.

• 单点故障 主节点失效时整个系统无法工作

令牌传递协议

控制令牌(token)循环从一个节点到下一个节点传递

令牌报文是一个特殊的帧

缺点:

• 令牌开销 本身消耗带宽

• 延迟 只有等到抓住令牌, 才可传输

• 单点故障(token) 令牌丢失会产生系统级故障, 整个系统无法传输. 生成令牌机制复杂

交换局域网 LANs

链路层寻址和 ARP

MAC

在网络层中需要使用 32bit 的 IP 地址(IPv4), 前 n-1 跳用于使数据报到达目的 IP 子网, 最后一跳到达子网的目标节点.

在链路层中需要一个 LAN(MAC/物理/以太网)地址, 用于使帧从一个网卡传递到与其物理连接的另一个网卡(在同一个物理网络中)

MAC 地址有 48bit, 固化在适配器的 ROM 中, 有时也可以通过软件设定. 理论上没有重复的 MAC 地址.

通常用 16 进制表示.

这样的话, LAN(局域网)中的每一个接口, 都有一个唯一的 48 位 MAC 地址, 和一个本地唯一的 32 位 IP 地址.

IP 地址和 MAC 地址的作用是不同的.

• IP 地址是分层的

一个子网的所有站点前缀一致, 路由聚合, 减少路由表

希望网络层地址可配置, IP 地址完成网络到网络的交付

• MAC 地址是平面的

网卡在生产的时候不知道要去哪里, 因此给网卡一个唯一标识, 用于区分一个网络内部不同的网卡即可.

可以完成一个物理网络内部的节点到节点的数据交付

MAC 可以移动, IP 是不能移动的.

ARP

在最开始, 大家都不知道彼此的 MAC 和 IP, 但是依旧有通信需求. 但是想通信就得要 MAC 和 IP, 这时候就需要 ARP 了.

在 LAN 上每个节点都有一个 ARP 表, 里面有一些 LAN 节点的 IP/MAC 地址映射. <IP, MAC, TTL>. TTL 是指地址映射失效时间, 典型是 20min.

• 在同一个 LAN

假设现在 A 想要向同个 LAN 的 B 发送数据报, 并且已经知道 B 的 IP 了, 如果 B 的 MAC 在 A 的 ARP 表里那就直接发送了, 如果不在就需要通过 ARP 请求来获取.

A 会发送一个广播, 目的 MAC 地址设置为 FF:FF:FF:FF:FF:FF, IP 设置为 B 的 IP.

这样所有节点都会收到这个请求, 但是只有 B 会响应.

B 的响应是单播而不是广播了, 毕竟双方的 MAC 和 IP 都知道.

A 收到 B 的响应后, 在自己的 ARP 表里建立映射.

ARP 表是即插即用的, 不需要网络管理员的干预.

• 不在同一个 LAN

不在同一个 LAN 时, 就需要通过路由器转发了.

路由器会维护很多个 ARP 表, 取决于它有多少个局域网.

A 发现 B 不在 LAN 中, 会查询路由表看自己应该往哪里发, 最后会找到下一跳的 IP, 然后再从 ARP 表里找下一跳 IP 对应的 MAC, 然后发过去. 但是这个帧的 IP 字段设置的是 B 的 IP 而不是下一跳的 IP.

一般情况下这个下一跳就是路由器. 路由器收到之后会解包, 发现这个 IP 不是自己, 就会准备转发了. 路由器会将目的 MAC 改成下一跳的 MAC, 封装好后转发出去. 之后的路由器也会这么做, 直到到达目的主机.

以太网

Ethernet 以太网, 是目前最主流的 LAN 技术, 也是最早广泛应用的 LAN 技术.

物理拓扑

• 总线

上世纪 90 年代中期很流行.

所有节点都在一个碰撞域中, 一次只允许一个节点发送.

可靠性差, 如果介质破损, 截面形成信号的反射, 发送节点会误以为是冲突.

• 星型

目前最主流的.

连接选择集线器(hub, 被淘汰了)或者交换机(switch, 玩不了)

现在一般是交换机在中心. 每个节点以及相连的交换机端口使用(独立的)以太网协议, 不会和其它节点发送产生碰撞.

以太网帧结构

发送方适配器在以太网帧里面封装 IP 数据报或者其它网络层协议数据单元.

• 前导码/前同步码 preamble

7B 10101010 + 1B 10101011

用来同步接收方和发送方的时钟速率, 使得接收方将自己时钟跳到发送方的时钟, 从而可以按照发送方的时钟来接收所发送的帧

• 地址

6 字节源 MAC 地址和 6 字节目标 MAC 地址

节点收到一个包, 如果帧目标地址==本站 MAC 地址/广播地址, 则接收; 否则适配器会忽略这个帧.

• 类型

指出高层协议, 大部分时候是 IP

• CRC 在接收方校验. 没有通过校验就丢弃帧

以太网的服务

以太网提供的是无连接, 不可靠的服务.

• 无连接

帧传输前, 发送方和接收方没有握手

• 不可靠

没有 ACK/NAK, 递交给网络层的数据可能有 gap, 除非使用 TCP 协议之类的可靠传输协议, 否则应用层会看到 gap.

以太网的 MAC 协议采用的是二进制退避的 CSMA/CD 介质访问控制形式

链路层交换机

Switch 交换机

功能

是链路层设备, 扮演主动角色(端口执行以太网协议).

• 对帧进行存储和转发

• 对到来的帧, 检查帧头, 根据目标 MAC 地址进行 选择性 转发

• 当帧需要向某个/些网段进行转发, 需使用 CSMA/CD 进行接入控制

• 通常一个交换机端口一个独立网段

它是透明的, 主机对交换机的存在可以不关心. 通过交换机相连的各节点跟直接相连一样, 交换机有 MAC 地址, 但是没有 IP 地址(可以配置)

即插即用, 自学习

多路同时传输

主机有一个专用和直接到交换机的链接, 交换机会缓存到来的帧, 对每个帧进入的链路使用以太网协议, 没有碰撞. 是全双工的.

每条链路都是一个独立的碰撞域, MAC 协议在其中的作用弱化了.

对于 A 到 B 和 C 到 D 是可以同时传输的, 没有碰撞; 但是 A 到 B 和 C 到 B 是不能同时传输的.

转发表

交换机自己会维护一个转发表, 里面的表项有主机的 MAC 地址, 到达该 MAC 经过的接口; 时戳. 每个表项通过类似路由协议的东西创建和维护.

自学习

交换机可以通过学习来得到主机的 MAC 地址而不需要预先配置.

当遇到未知的 MAC 地址时, 会发送一个广播, 来找到目的地.

过滤和转发

交换机收到一个帧时,

1. 记录进入链路和发送主机的 MAC 地址

2. 使用目标 MAC 地址对交换表进行索引

3. 如果找到了, 并且目的地正确, 那么发过去, 如果目的地不正确, 那就过滤了. 如果没有找到, 那么泛洪来获取目标地址, 然后记录下来.

交换机本身是可以级联的.

交换机与路由器

• 都是存储转发设备, 但层次不同

交换机是链路层设备, 检查的是链路层头部

路由器是网络层设备, 检查网络层头部

• 都有转发表

交换机维护交换表, 按照 MAC 地址转发. 它有自学习和生成树算法(避免成环), 可以限制广播帧的转发. 表项随着站点增多而增多. 可以自动配置. 二层设备, 速率高.

路由器维护路由表, 执行路由算法. 路由算法可以避免成环, 无需执行生成树算法. 它对广播分组进行限制, 需要人工配置. 三层设备, 速率低.

虚拟局域网 VLAN

当一个局域网规模越来越大时, 就会产生一些问题. 一次广播就需要所有用户都接收到, 即使只需要一个用户响应. 同时也会有安全性/私密性的问题.

这时候可以考虑增加交换机了, 但是如果规模没那么大, 交换机又有点浪费了. 如果一个交换机可以当多个交换机用就好了. 虚拟局域网就是解决这样的问题.

基于端口的 VLANS

带有 VLAN 功能的交换机可以被配置, 某些端口对应一个虚拟的 LAN, 也就是 VLAN. 这样的话, 一个交换机就相当于多个交换机了.

也可以基于 MAC 隔离, 在交换表或者再弄一个表, 某些 MAC 地址对应一个虚拟局域网.

• 流量隔离

比如 16 个端口被分成 1 到 8 虚拟局域网 A 和 9 到 16 虚拟局域网 B, 之后 A 里面的广播只会在 A 里面广播, 不会跟 B 有关, 就实现了流量隔离.

• 动态成员

成员可以在 VLANs 中动态分配, 今天我可以是 A 的成员, 明天我可以是 B 的成员.

• 在 VLANs 中转发

这个就比较麻烦了, 需要通过路由器来进行转发. 不过现在的话, 家用路由器都是交换机+路由器了, 损耗也不会很大.

VLANs 互联多个交换机

如果有一天不得不买一个新交换机, 这个交换机大概率需要跟之前的 VLAN 做一下适配了. 这时候就需要让它们互联.

• 方法 1

各交换机每个 VLAN 一个端口和另外交换机相应的 VLAN 端口相连, 但是这样有扩展性问题.

• 方法 2

干线端口 trunk port 多个交换机共享定义的 VLAN, 在它们之间传输帧

帧在不同交换机上的一个 VLAN 上转发, 此时不能再使用 vanilla 802.1 帧了, 必须携带一个 VLAN ID.

802.1 q 协议增加/删除附加的头部字段, 用于在 trunk 端口上进行帧的转发.

链路虚拟化 MPLS

MPLS

MPLS, Multiprotocol label switching, 多协议标签交换. 目的是改善 IP 路由器的转发速度.

在支持 MPLS 的路由器网络之间, 基于固定长度的标签而不是目的地 IP 地址转发数据报.

• 固定长度标识符更快查找

• 借鉴了虚拟电路 VC 方法的思想

• 但是 IP 数据报仍然保留 IP 地址

具有 MPLS 能力的路由器

这种路由器叫 label-switched router, 标签交换路由器. 它基于标签的值进行分组转发. MPLS 转发表和 IP 转发表相互独立.

它具有弹性(Flexibility), MPLS 转发策略可以和 IP 的不同.

• 采用源地址和目标地址来路由到达同一个目标的流, 不同路径(支持流量工程)

• 如果链路失效了, 能够快速重新路由: 预先计算好的备份链路(对于 VoIP 有效)

对于这样的一个路由器R0, 假设它下一跳就能到达主机A了, 那么它的表项应该是这样的:

一个目的地A和出接口, 还有有一个入标签, 路由器会把标签为入标签的分组转发到相应的端口. 这个就没有出标签了, 因为路由器在转发这个分组的时候不会改变标签, 而是移除标签.

假设它的下一跳是另一个路由器R1, 并且R1可以到达主机B, 同时R1的表项是这样的:

目的地B和出接口, 入标签3.

那么R0想要到达主机B的话, 就需要发送一个分组标签为3的分组, 也就是出标签为3. 它对B的表项应该是这样的:

入标签自己设定, 不过这个是需要通知其它路由器的. 出标签是3, 目的地是B, 出接口.

MPLS 与 IP

IP routing 到达目标的路径仅仅取决于目标地址

MPLS routing 到达目标的路由, 可以基于源和目标地址

MPLS 的转发表表项里有 in label, out label, dest, out interface

数据中心网络

数据中心有非常多的设备, 需要实现负载均衡等功能.

网元 network element

• Border routers 边界路由器

数据中心外的连接

• Tier-1 switches 一级交换机

连接~16 T-2s 以下

• Tier-2 switches 二级交换机

连接到 ~16 TORs 下面

• Top of Rack (TOR) 顶部交换机

每架一个, 超高速

• Server racks 服务器机架

应用层路由

数据中心网络有一个负载均衡器, 在应用层.

• 接受外部客户端请求

• 将请求导入到数据中心内部

• 返回结果到外部客户端(对于外部客户端来说, 这是透明的)

多路径

在交换机之间, 机器阵列之间有丰富的互连措施. 这有助于增加吞吐量, 通过冗余量增加可靠性.