网络层-控制平面

众所周知啊, 数据平面最主要功能是转发, 控制平面的最主要功能就是路由了. 一般有两种方法构建网络控制平面的功能.

比较传统的是由每个路由器自己实现, 通过一些路由协议, 跟其它路由器交换信息, 自己计算出一个转发表.

比较新的是全部交给一个远程控制器来计算, 用远程控制器计算出来的转发表.

路由选择算法

首先来了解一下路由协议吧.

路由

路由协议目标: 从发送方到接收方的过程中确定一条通过路由网络的好的路径(等价于路由). 最好就是成本低, 速度快, 拥堵少.

路由 : 按照某种指标找到一条从源节点到目标节点的较好路径. 这个较好的指标是什么, 取决于网络使用者想要什么.

以网络(子网)为单位进行路由, 路由信息传输, 计算和匹配的代价更低. 但是要求一个网络所有节点地址前缀相同, 并且物理上聚集.

如果希望使用这种路由, 那就要求计算一个网络到另一个网络怎么走了.

网络到网络的路由 = 路由器到路由器之间的路由, 也就是网络对应的路由器到其它网络对应的路由器的路由. 此时路由器以子网到子网的路径为计算目标, 而不是主机到主机; 路由器到路由器之间的最佳路径就是主机之间的最佳路径.

至于一个网络中, 路由器与主机的通信则由链路层解决.

路由选择算法是网络层软件的一部分, 完成路由功能.

网络的图抽象

网络与网络之间可以抽象成一张图, 每一个网络对应的路由器就是一个节点, 之间的路径就是边. 每条边有一个权, 表示直接链路的代价, 记作$C_{A,B}$.

路由的输入: 拓扑, 边的代价, 源节点

路由的输出: 源节点的汇集树

最优化原则

汇集树是此节点到所有其它节点的最优路径形成的树. 路由选择算法就是为所有路由器找到并使用汇集树.

路由选择算法原则

• 正确性

算法必须是正确的和完整的.

完整: 目标所有的站地址, 在路由表中都能找到相应的表项; 没有处理不了的目标站地址.

• 简单性

算法在计算机上应简单: 最优但复杂的算法在时间上的延迟很大, 不实用.

不应该为了获取路由信息增加很多的通信量.

• 健壮性

算法能适应通信量和网络拓扑的变化, 并且很快能适应.

不向很拥挤的链路发数据, 不向断了的链路发送数据.

• 稳定性

产生的路由不应该摇摆

• 公平性

对每一个站点都公平

• 最优性

在某个或者某几个指标上最优.

如果实际上获取的最优的结果代价很大, 可以是次优的.

路由选择算法的分类

大概分成这几类:

全局

这是在所有路由器都拥有完整的拓扑和边代价的信息情况下使用, 有链路状态算法

分布式

通常情况下路由器只知道与它相连的路由器, 和到它那的代价.

迭代地与邻居交换路由信息, 计算出路由信息. 有距离向量算法.

静态

适用于路由随时间变化缓慢的情况.

非自适应算法: 路由表是事先计算好的, 无法适应网络拓扑和通信量的变化.

动态

适用于路由变化很快的情况.

本身可以周期性更新, 根据链路代价的变化而变化.

自适应算法: 能适应网络拓扑和通信量的变化.

链路状态路由选择算法

Link State, 简称 LS.

配置过程

各个路由器通过各种渠道获取整个网络拓扑, 网络中所有链路代价等信息(这一部分与算法无关, 属于协议和实现).

使用 LS 路由算法, 计算本站点到其它站点的最优路径(汇集树), 得到转发表.

按照转发表转发分组

基本工作过程

1. 发现相邻节点, 获取对方的网络地址

2. 测量到相邻节点的代价

3. 组装一个 LS 分组, 描述它到相邻节点的代价情况

4. 将分组通过扩散(泛洪)的方法发到所有其它路由器

这 4 步让每一个路由器都获得拓扑和边代价. 泛洪本身会产生广播风暴问题, 如环路. 因此需要使用 TTL 或者 Seq 版本号. 泛洪需要是可靠的, 一定要收到确认, 否则会一直发.

5. 通过 Dijkstra 算法找到最短路径

OSPF 协议就是一种 LS 协议, 被用在 Internet 上.

Dijkstra 算法

这是一种集中式的算法, 要求网络拓扑和所有链路开销都是已知的. 这个通过链路状态广播来实现.

这个算法可以计算出一个节点的汇集树, 得到这个节点的转发表. 第 k 步时就可以得到从源节点到第 k 个节点的最优路径.

• 初始化

除了源节点, 所有节点都为临时节点. 节点代价除了与源节点相邻的节点, 都为$\mathrm{\infty }$.

• 迭代

从所有临时节点中, 找到一个节点代价最小的临时节点, 将它变为永久节点, 记作 w

对此节点的所有在临时节点集合的邻节点 V 中, 更新它们的节点代价.

如果 D(v) > D(w) + C(w, v), 更新节点代价.

已知迭代, 知道所有节点都有了确定的节点代价.

Dijkstra 算法的讨论

• 算法复杂度

时间复杂度 O($n^2$), 如果有更高效的实现则是 O($n\log n$)

• 消息复杂度

每个路由器都必须 广播 它的链路状态给其它 n 个路由器

每个路由器的消息经过 O(n)条链路, 总体消息复杂度为 O($n^2$)

• 振荡的可能

当链路成本取决于业务量(拥塞程度)时, 路由可能会发生振荡.

如果某处拥塞了, 那么需要重新计算. 但是拥塞可能只是暂时的, 过一会后又需要重新计算.

距离向量路由选择算法

Distance Vector Routing, DV.

这是动态路由算法之一, LS 也是一种动态路由算法.

基本思想是, 每个路由器维护一张路由表, 记录目标, 下一跳和花费. 每个路由器都会跟邻居路由器交换路由表, 根据获得的路由表更新自己的路由表.

相邻节点的代价实际测量就可以得到了.

一个节点测量得出到相邻节点的代价后, 在从相邻节点那里获取路由表, 就可以计算出经过相邻节点, 到别的节点的代价了. 自己只需要找出一个最小的代价, 和相应的下一个节点, 就可以了.

$$D_x(y)=mi{n}_V\{C_{x,y}+D_v(y)\}$$

其中, $D_x(y)$是从 x 到 y 的最小路径代价. V 是 x 的邻居, 里面的式子表示从 V 中找出一个 v, 使得$C_{x,y}+D_v(y)$最小.

核心思路

每个节点都将自己的距离向量估计值传送给邻居, 每隔一段时间或者 DV 有变化时, 让对方去算.

当 x 从邻居收到 DV 时, 自己运算, 更新它自己的距离向量.

最后$D_x(y)$估计值最终收敛于实际的最小代价值.

特性

• 分布式

每个节点不需要完整的网络拓扑或其它信息, 只需要邻居的路由表.

当自己的 DV 变化时, 向邻居通告.

邻居也需要在有必要的时候通告自己的邻居.

• 异步式, 迭代

每次本地迭代都会触发这些事件: 本地链路代价改变, 从邻居来了 DV 的更新消息.

存在的问题

DV 的好消息传得很快, 但是坏消息传的很慢. 好消息是指某链路的代价变小, 坏消息是指某链路的代价变大.

比如说 A-B-C 就这么连着, 每条链路的代价是 1.

在初始状态下, B 认为 A 可达, 代价是 1. 告诉 C 之后, C 认为 A 可达, 代价是 2.

过一段时间, B 发现 A 不可达了, 但是从 C 那里知道 C 可以到达 A, 代价是 2. 于是 B 觉得可以从 C 那里到 A, 自己到 A 的代价是 3.

之后 C 又从 B 那里知道 B 到 A 的代价是 3, 自己是从 B 那里到 A 的, B 到 A 的代价是 3, 那自己到 A 的代价就应该是 4 了. 一直下去, 到 A 的代价会无限大.

解决方案

既然 C 知道到 A 需要经过 B, 那么告诉 B 自己到不了 A 就可以了, 比如到 A 的距离是无穷大. 至于其它节点, 如实相告就行了. 这样 B 就认为 A 不可达了, C 也会知道 A 不可达了. 这种方法叫水平分裂/毒性逆转算法, 对一边说假话, 另一边说真话.

但是这依旧无法完美解决问题. 比如 ABC 成环了, C 跟 D 连着.

哪一天 C 不可达 D 了, 但是 A 和 B 的信息都没有及时更新. A 从 B 那里得知, B 可达 D, 假设代价是 2 的话, 自己算出来就是 3 了. 然后由于 A 觉得自己不是从 C 那里到 D 了, 因此不会告诉 C 假的 D 情况, 而是告诉 C 可达 D. 这样循环下去, 到达 D 的代价也会变成无限大.

LS 与 DV 的比较

• 消息复杂度(DV 更好)

LS 有 N 个节点, E 条链路, 发送报文 O(N*E)个.

局部的路由信息全局传播; 每个路由器只发送自身的链路状态.

DV 只与邻居交换信息, 全局的路由信息局部传播, 每个路由器发送整个路由信息, 但只发给相邻节点.

• 收敛时间(LS 更好)

LS: O($n^2$)算法, 但有可能振荡

DV: 收敛很慢, 可能存在路由环路, count-to-infinity 问题

• 健壮性(LS 更好)

出现路由器故障时:

LS 节点会通告不正确的链路代价, 每个节点只计算自己的路由表/转发表. 错误信息影响较小, 局部

DV 节点可能通告对全网所有节点的不正确的线路代价, 每一个节点的路由表可能被其它节点使用, 错误可以扩散到全网, 更新延迟

因特网中自治系统内部的路由选择

在实际的因特网中节点与节点的关系是非常复杂的, 之前讨论的都是平面路由.

层次路由

平面路由的问题

在一个平面的路由中, 一个网络的所有路由器地位一样, 通过 LS, DV 或者别的路由算法, 所有路由器都会知道其它所有路由器(子网)怎么走.

规模问题: 在规模巨大的网络中, 路由信息会变得很大, 计算代价也很大.

管理问题: 不同的网络所有者希望按照自己的方式管理自己的网络, 也想要对外隐藏自己的网络细节.

层次路由

将互联网分成多个 AS , 自治系统(Autonomous Systems).

一个 ISP 可能包括一个或者多个 AS, 一个 AS 用 AS Number(ASN)唯一标示.

这样之后, 只需要讨论 AS 内部的路由和 AS 之间的路由就可以了.

• AS 内部路由 在同一个 AS 内路由器运行相同的路由协议

  • intra-AS routing protocol 内部网关协议

  • 不同 AS 中的路由器可以运行不同的域内路由协议

  • 网关路由器 AS 边缘路由器, 可以连接到其它 AS

• AS 间运行 AS 间路由协议

  • inter-AS routing protocol 外部网关协议

  • 解决 AS 之间的路由问题, 完成 AS 之间的互联互通

层次路由的优点

解决了规模问题

• AS 内部网关协议

解决了 AS 内部数量有限的路由器相互到达的问题, AS 内部规模可控. 如果 AS 节点还是很多的话, 继续分割就可以了.

• AS 之间的路由协议

AS 之间的规模问题: 增加一个 AS, 只是相当于增加一个节点, 扩展性强. 对于其它 AS, 只是多了一个表项而已.

---

解决了管理问题

各 AS 可以运行自己的内部网关协议, 内部细节可以不对外暴露

---

Intra AS Routing AS 内部路由

RIP

已经不再使用

使用 DV 算法. 每隔 30s 和邻居交换 DV, 通告.

每个通告包括最多 25 个目标子网.

RIP 通告

定期通告, 当改变路由时, 也会进行通告. 如果其它路由器请求也可以发送通告.

每一个通告包括至多 AS 内部的 25 个目标网络, 跳数不超过 16 的 DV(目标网络+跳数+下一跳, 这里链路代价为 1, 跳数就是链路代价)

当 180s 没有收到通告信息, 就认为邻居或者链路失效了.

链路失效和恢复

当路由器发现经过这个邻居的路由已经失效了, 会发送一个新的通告报文给邻居.

邻居因此发送新的通告(如果因为得知某链路失效而导致路由变化的话)

链路失效会快速地在整网中传输.

为了阻止 ping-pong 回路, 使用毒性逆转.

不可达距离: 跳数无限 = 16 跳

RIP 进程处理

RIP 以应用进程的方式实现. 通告报文使用 UDP 报文传送.

OSPF

开放最短路径优先.

使用 LS 算法, LS 分组只在网络中(AS 内部)分发.

OSPF 也会通告, 通告信息中有每一个邻居路由器的一个表项. 通告信息会通过泛洪传遍 AS 全部.

跟 RIP 不同, 通告直接在 IP 数据报上传送而不是使用 UDP/TCP

IS-IS 路由协议几乎和 OSPF 一模一样.

优点

安全: OSPF 报文都是认证过的.

允许 多个代价相同 的路径存在(RIP 只允许一个)

对于每一个链路, 允许有多重代价矩阵

对于尽力而为的服务代价设置比较低, 对于实时服务代价设置比较高

支持单播和多播

在大型网络中支持层次性 OSPF

层次性的 OSPF 路由

OSPF 路由可以有两个层次: 本地, 骨干

• 区域边界路由器

汇总到自己区域内网络的距离, 向其它边界路由器通告

• 边界路由器

连接其它的 AS

• 本地路由器

泛洪只在区域内发生, 路由计算也只计算区域内的. 通过区域边界路由器向外部转发数据包

• 骨干路由器

仅仅在骨干区域才运行 OSPF 路由

AS 之间的路由选择 BGP

BGP, Border Gateway Protocol, 边际网关协议

允许子网向互联网其它网络通告自己的位置

BGP 给每个 AS 提供了这些方法

• eBGP(外部) 从相邻的 Ases 那里获得子网可达信息

• iBGP(内部) 将获得的子网可达信息传遍 AS 内部的所有路由器

• 根据子网可达信息和策略来决定到达子网的"好"路径

BGP 基于距离向量算法, 但不仅仅是距离向量, 还包括到达各个目标网络的详细路径(AS 序号的列表), 避免简单 DV 算法的路由环路问题

网关路由器同时运行 eBGP 和 iBGP

BGP 基础

BGP 会话 两个 BGP 路由器(peers)在一个半永久的 TCP 连接上交换 BGP 报文

通告向不同目标子网前缀的路径, 跟之前的 DV 算法类似

在 BGP 中, 网关路由器知道本 AS 所有子网的信息, 并参与 AS 内路由运算. 网关路由器会告知邻居网关路由器自己的相关路径.

路径的属性

通告一个子网前缀时, 通告里面有 BGP 属性

$$prefix+attributes=route$$

• AS-PATH

前缀的通告所经过的 AS 列表. 这是为了检测环路以及多路径选择. 在向其它 AS 转发时, 需要将自己的 AS 号加上去.

• NEXT-HOP

从当前 AS 跳到下一跳有多个链路时, 需要在这个属性里告知对方通过哪条链路转发

其它属性: 路由偏好指标等

BGP 路由

• 基于策略的路由

网关路由器接收到一个路由通告时, 可以使用 输入策略 来接受和过滤路由.

如果不想经过 AS, 那网关路由器可以过滤某前缀的路由 如果已经有了偏好的路径, 也可以过滤

BGP 路径通告

网关路由器也可能会从多个 eBGP 会话收到有关一个子网 X 的路径, 此时会根据自己的策略来选择路径, 并通过 iBGP 告诉自己所有内部的路由器.

BGP 报文

• OPEN 打开 TCP 连接, 认证发送方

• UPDATE 通告新路径(或者撤销原路径)

• KEEPALIVE 在没有更新的时候保持连接, 也可以用于对 OPEN 请求确认

• NOTIFICATION 报告以前消息的错误, 也用来关闭连接

热土豆路由

热土豆策略: 选择具备最小区域代价的网关作为往 x 的出口

一个 AS 可能有多个网关路由器, 一个节点向外部节点的请求可以从多个路由器发送时, 选择最小区域代价的路由器.

通过路径通告执行策略

当一个 ISP 希望路由流量去往它自己的客户网络, 大概就是 ISP 不想转发别人的请求, 因为没有收益, 就需要这个了.

比如一个 AS 的网关路由器 A 向 B 通告了自己可以到达 X 节点, B 可以选择不通告旁边的节点 C, 因为 A, C, X 都不是自己的客户.

不是去往我的客户, 也不是来自我的客户.

还有一种情况时, 一个桩网络 X 是双重接入的, 多宿桩网络, 接入了两个网络.

X 可能不希望路由从 B 通过自己到达 C, 也会不通告 B, 自己能到 C.

内部网关协议和外部网关协议为什么不同

• 策略

inter-AS 管理员需要控制通信路径, 谁在用它的网络进行数据传输

intra-AS 一个管理员, 所以无需策略. AS 内部的各子网的主机应尽可能利用资源快速路由

• 规模

AS 间路由必须考虑规模问题, 以便支持全网的数据转发

AS 内部路由规模不是一个大问题, 太大了就分开, 或者让 AS 内部也具有层次性.

• 性能

intra-AS 关注性能

inter-AS 策略可能比性能更重要

SDN 控制平面

传统的控制平面是分布式的, 一个路由器基本上有着完整的功能.

SDN 方式实现的是 逻辑上集中 的控制平面,

• 这样使得网络管理更加容易, 避免路由器的错误配置, 对信息流的弹性更好.

• 基于流表的转发, 允许可编程的路由器. SDN 远程控制器集中计算流表然后分发.

• 控制平面的开放实现

流量工程

在传统路由实现中, 流量的控制是非常困难的. 比如 a 到 b 有两条路, 一条路计算出来的链路代价大, 另一条比较小. 路由器会自动地去选择小的. 但是网管可能有特殊需求走大的; 或者希望一起走(负载均衡), 这都是很难控制的, 因为 LS 和 DV 都确定了一条路径.

SDN 特点

• 通用 flow-based 基于流匹配加操作

• 控制平面和数据平面的分离

• 控制平面功能在数据交换设备之外实现

• 可编程控制应用, 在控制器之上以网络应用形式实现各种网络功能

SDN 架构

数据平面交换机

SDN 数据平面交换机, 快速简单商业化交换设备采用, 硬件实现了通用转发功能. 控制器计算和安装流表, 并基于南向 API(如 OpenFlow), SDN 控制器访问基于流的交换机, 定义哪些可以被控制和控制器的协议.

控制应用

SDN 控制器维护网络状态信息, 通过上面的向北 API, 与网络控制应用交互; 通过下面的南向 API, 与网络交换机交互. 逻辑上集中, 但是在实现上采用分布式方法实现.

网络控制应用不是绑定的, 可以被第三方提供. 它是控制的大脑, 采用下层提供的服务, 实现网络功能.

路由器交换机, 接入控制防火墙, 负载均衡等.

SDN 控制器元件

SDN 控制器分为三层:

• 网络控制应用界面层 抽象 API

• 网络范围的状态管理层 网络链路, 交互设备和服务的状态, 相当于一个分布式数据库

• 通信层 SDN 控制器和 SDN 交换机之间进行通信

OpenFlow 协议

这是控制器与 SDN 交换机交互的协议. 采用 TCP 来交换报文(可加密).

OpenFlow 提供了一些 API, 用于指定通用转发动作

OpenFlow 报文类型

• 控制器 -> 交换机

• 异步 (交换机 -> 控制器)

• 对称(misc)

ICMP 因特网控制报文协议

我们在 ping 的时候其实发的就是 ICMP 报文.

ICMP 在网络层上, 基于 IP 协议. 由主机/路由器/网关用于传达网络层控制信息.

ICMP 报文

• 类型

• 编码

• 加上 IP 数据报的头 8 字节, 第一个导致该 ICMP 报文的 IP 数据报

TraceRoute

源主机会发送一系列的 UDP 段给目标主机, TTL 依次从 0 增加, 直到收到一个不可达的端口报错.

当第 n 个数据报到达第 n 个路由器时, 路由器就会抛弃这个数据报, 然后发送一个给源的 ICMP 报文. 这个报文包括了路由器的名字和 IP 地址.

当 ICMP 报文到达目标主机时, 源端计算 RTT.

对一个 nTraceRoute 做 3 次.

判断到达的依据

当 UDP 段最终到达目标主机, 目标返回给源主机 ICMP 端口不可达报文. 当源主机收到这个报文, 停止.

网络管理

网络管理包括了硬件, 软件和人类元素的设置, 综合和协调, 以便监测, 测试, 轮询, 配置, 分析, 评价和控制网络 和网元资源, 用合理的成本满足实时性, 运行能和服务质量的要求.

五大功能

• 性能管理

长期检测设备性能.

性能(利用率, 吞吐量等)量化, 测量, 报告, 分析和控制不同网络部件的性能

设计到的部件有单独部件(网卡, 协议实体)和端到端的链路

• 故障管理

记录, 检测和响应故障. 对于突然发生的强度大的性能降低, 强调对故障的响应.

• 配置管理

跟踪设备的配置, 管理设备配置信息

• 账户管理

定义, 记录和控制用户和设备访问网络资源

限额使用, 给予使用的收费, 以及分配资源访问权限

• 安全管理

定义安全的策略, 控制对网络资源的使用

架构与组件

• Managing Server 管理服务器

是一个应用程序, 通常带有网络循环中的管理者

• Managed device 管理设备

具有可管理的, 可配置的硬件, 软件组件的设备

• Network management protocol 网络管理协议

用于管理服务器查询, 配置, 管理设备;

设备用于通知管理服务器的数据, 事件

• Data 数据

设备状态配置数据, 运行数据, 设备统计数据

管理方法

• CLI 命令行应用

操作问问题直接到单个设备, 使用 ssh 等连接

• SNMP/MIB

操作员通过 SNMP(Simple Network Management Protocol)查询/设置设备数据(MIB)

• NETCONF/YANG

更加抽象的, 全网络, 整体强调多设备配置管理

- YANG 数据建模语言

- NETCONF 远程设备之间与YANG兼容的动作/数据进行通信