控制平面作为一种网络范围的逻辑，不仅控制沿着从源主机到目的主机的端到端路径间的路由器如何转发数据报，而且控制网络层组件和服务如何配置和管理

5.1 概述

转发表（在基于目的地转发的场景中）和流表（在通用转发的场景中）是链接网络层的数据平面和控制平面的首要元素。

转发表和流表是如何计算、维护和安装的？

• 每路由器控制：每台路由器有一个路由选择组件，用于与其他路由器中的路由选择组件通信，以计算其转发表的值
• 逻辑集中式控制：逻辑集中式控制器计算并分发转发表以供每台路由器使用

该控制器经一种定义良好的协议与每台路由器中的一个控制代理（CA）进行交互,以配置和管理该路由器的转发表

5.2 路由选择算法

目的：从发送方到接收方的过程中确定一条通过路由器网络的好的路径（等价于路由）。

• 较好路径: 按照某种指标较小的路径
• 指标:站数, 延迟,费用,队列长度等, 或者是一些单纯指标的加权平均

路由选择算法(routing algorithm):网络层软件的一部分,完成路由功能

网络的图抽象

图: G = (N,E)

• N = 路由器集合 = { u, v, w, x, y, z }

• E = 链路集合 ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }

• 边有代价

• c(x,x’) = 链路的代价 (x,x’)

• 如果（x, y）属于E,节点y也被称为节点x的邻居（neighbor）

路由的输入：拓扑、边的代价、源节点

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

图G =（N, E）中的一条路径（path）是一个节点序列（x₁，x₂，… ，x_p），开销为沿着路径所有边的开销的总和，即 c（x₁，x₂）+c（x₂，x₃）+…+c（x_p-1 , x_p），最低开销路径也就是最短路径，即在源和目的地之间的具有最少链路数量的路径。

路由选择算法的原则

• 正确性:算法必须是正确的和完整的
• 简单性:算法在计算机上应简单
• 健壮性:算法应能适应通信量和网络拓扑的变化
• 稳定性：产生的路由不应该摇摆
• 公平性：对每一个站点都公平
• 最优性：某一个指标的最优

路由选择算法的分类

• 集中式路由选择算法：用完整的、全局性的网络知识计算岀从源到目的地之间的最低开销路径。该算法以所有节点之间的连通性及所有链路的开销为输入。具有全局状态信息的算法常被称作链路状态（Link State, LS）算法,因为该算法必须知道网络中每条链路的开销。
• 分散式路由选择算法：路由器以迭代、分布式的方式计算出最低开销路径。每个节点仅有与其直接相连链路的开销知识即可开始工作。距离向量（Distance-Vector, DV）算法的分散式路由选择算法，每个节点维护到网络中所有其他节点的开销（距离）估计的向量。
• 静态路由选择算法：路由随时间的变化非常缓慢，通常是人工进行调整（如人为手工编辑一条链路开销）
• 动态路由选择算法：随着网络流量负载或拓扑发生变化而改变路由选择路径。
• 负载敏感算法：链路开销会动态地变化以反映出底层链路的当前拥塞水平。
• 负载迟钝算法：因为某条链路的开销不明确地反映其当前（或最近）的拥塞水平

5.2.1 链路状态路由选择算法

在链路状态算法中，网络拓扑和所有的链路开销都是已知的。现实中通过让每个节点向网络中所有其他节点广播链路状态分组来完成的，其中每个链路状态分组包含它所连接的链路的标识和开销，常由链路状态广播算法完成，其结果为所有节点都具有该网络的统一、完整的视图。

的链路状态路由选择算法叫作Dijkstra算法，其计算从某节点（源节点，我们称之为u）到网络中所有其他节点的最低开销路径。其通过k次迭代，可知道到k个目的节点的最低开销路径。定义下列记号

• D（v）:到算法的本次迭代，从源节点到目的节点。的最低开销路径的开销
• p（v） 从源到v沿着当前最低开销路径的前一节点
• N’：节点子集；如果从源到。的最低开销路径已确知，n在N’中

当LS算法终止时，对于每个节点，我们都得到从源节点沿着它的最低开销路径的前一节点。对于每个前一节点，我们又有它的前一节点，以此方式我们可以构建从源节点到所有目的节点的完整路径。

该算法的计算复杂性是什么？

在第一次迭代中，我们需要搜索所有的n个节点，在第二次迭代时，我们需要检查n-1个节点，第三次对n-2个节点迭代，所有迭代中需要搜寻的节点总数为n（n + 1）/2，的链路状态算法在最差情况下复杂性为O（n²）

5.2.2 距离向量路由选择算法

距离向量算法是一种迭代的、异步的和分布式的算法，而LS算法是一种使用全局信息的算法。

• 分布式：每个节点都要从一个或多个直接相连邻居接收某些信息，执行计算，然后将其计算结果分发给邻居
• 迭代：此过程一直要持续到邻居之间无更多信息要交换为止
• 异步：不要求所有节点相互之间步伐一致地操作

令d_x(y)是从节点x到节点y的最低开销路径的开销。则该最低开销与著名的Bellman- Ford方程相关，即
dx(y)=minv{c(x,y)+dv(y)}d_x(y)= min_v\lbrace c(x,y)+d_v(y)\rbrace dx​(y)=minv​{c(x,y)+dv​(y)}

例子：

核心思路:

• 每个节点都将自己的距离矢量估计值传送给邻居，定时或者DV有变化时，让对方去算
• 当x从邻居收到DV时，自己运算，更新它自己的距离矢量
• D_x(y)估计值最终收敛于实际的最小代价值d_x(y)

每个节点做的事：

DV的特点

好消息传的快，坏消息传的慢

• 好消息：好消息的传播以每一个交换周期前进一个路由器的速度进行，比如某个路由器接入或有更短的路径

• 坏消息的传播速度非常慢

  比如：

  

解决坏消息传得慢的一种方法：水平分裂(split horizon)算法

但水平分裂算法在某些拓扑形式下会失败（存在环路）

LS 和 DV 算法的比较

• 消息复杂度（DV胜出）
  • LS: 有 n 节点, E 条链路,发送报文O(nE)个，全局传播
  • DV: 只和邻居交换信息，局部传播
• 收敛时间（LS胜出）
  • LS: O(n²) 算法，有可能震荡
  • DV: 收敛较慢，可能存在路由环路
• 健壮性: 路由器故障会发生什么（LS胜出）
  • LS:节点会通告不正确的链路代价。每个节点只计算自己的路由表。错误信息影响较小，局部，路由较健壮。
  • DV: DV 节点可能通告对全网所有节点的不正确路径代价 。每一个节点的路由表可能被其它节点使用

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

自治系统（Autonomous System, AS）

开放最短路优先（OSPF）：

• 使用LS算法
  • LS 分组在网络中（一个AS内部）分发
  • 全局网络拓扑、代价在每一个节点中都保持
  • 路由计算采用Dijkstra算法
• OSPF通告信息中携带：每一个邻居路由器一个表项
• 通告信息会传遍AS全部（通过泛洪）

特性：

• 安全: 所有的OSPF报文都是经过认证的
• 允许有多个代价相同的路径存在
• 对于每一个链路，对于不同的TOS有多重代价矩阵
• 对单播和多播的集成支持
• 在大型网络中支持层次性OSPF

5.4 ISP之间的路由选择：BGP

层次路由：将互联网分成一个个AS(路由器区域)

路由变成了: 2个层次路由

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

层次路由的优点

• 解决了规模问题
• 解决了管理问题

在因特网中，所有的AS运行相同的AS间路由选择协议，称为边界网关协议（Broder Gateway Protocol, BGP），这个协议将因特网中数以千计的ISP黏合起来。BGP是一种分布式和异步的协议

5.4.1 BGP的作用

对于位于相同AS中的目的地而言，在路由器转发表中的表项由AS内部路由选择协议所决定。而对于位于该AS外部的目的地而言情况如何呢？这正是BGP用武之地。

一台路由器的转发表将具有形式为（x，I）的表项，其中x是一个前缀（例如138.16. 68/22），I是该路由器的接口之一的接口号。

• 从邻居AS获得前缀的可达性信息。BGP允许每个子网向因特网的其余部分通告它的存在

• 确定到该前缀的“最好的”路由。为了确定最好的路由，该路由器将本地运行一个BGP路由选择过程

• eBGP: 从相邻的ASes那里获得子网可达信息，跨越两个AS的BGP连接

• iBGP: 将获得的子网可达信息传遍到AS内部的所有路由器，在相同AS中的两台路由器之间的BGP会话

5.4.2 通告BGP路由信息

下面网络有3个自治系统AS1、AS2和AS3

BGP会话：在BGP中，每对路由器通过使用179端口的半永久TCP连接交换路由选择信息。

传播可达性信息，使用了iBGP和eBGP会话

1. 网关路由器3a先向网关路由器2c发送一个eBGP报文“AS3 x”
2. 网关路由器2c然后向AS2中的所有其他路由器(包括网关路由器2a)发送iBGP报文“AS3 x”
3. 网关路由器2a接下来向网关路由器1c发送一个eBGP报文“AS2 AS3 x”
4. 网关路由器1c使用iBGP向AS1中的所有路由器发送报文“AS2 AS3 x"
5. 这个过程完成后，在AS1和AS2中的每个路由器都知道了x的存在并且也都知道了通往x的AS路径

从某个给定的路由器到某个给定的目的地可能有多条不同的路径，每条通过了不同的AS序列。在上图这种情况下，从AS1到x有两条路径：经过路由器1c的路径“AS2 AS3 x” ；以及经过路由器1c的新路径“AS3 x” 。

5.4.3 确定最好的路由

当路由器通过BGP连接通告前缀时，它在前缀中包括一些BGP属性(BGP attribute)

前缀及其属性称为路由。两个较为重要的属性是AS-PATH和NEXT HOP

• AS-PATH属性包含了通告已经通过的AS的列表。BGP路由器还使用AS-PATH属性来检测和防止通告环路。如果一台路由器在路径列表中看到包含了它自己的AS,它将拒绝该通告
• NEXT PATH属性在AS间和AS内部路由选择协议之间提供关键链路。NEXT HOP是AS PATH起始的路由器接口的IP地址

1.热土豆路由选择

热土豆路由选择增加AS向外前缀的步骤。

热土豆路由选择依据的思想是：对于路由器1b,尽可能快地将分组送出其AS（更明确地说，用可能的最低开销），而不担心其AS外部到目的地的余下部分的开销。

2.路由器选择算法

如果到相同的前缀有两条或多条路由，则顺序地调用下列消除规则直到余下一条 路由

1. 路由被指派一个本地偏好值作为其属性之一（除了 AS PATH和 NEXT-HOP以外）
2. 从余下的路由中（所有都具有相同的最高本地偏好值），将选择具有最短AS PATH的路由。
3. 从余下的路由中（所有都具有相同的最高本地偏好值和相同的AS-PATH长度）,使用热土豆路由选择，即选择具有最靠近NEXT-HOP路由器的路由
4. 如果仍留下多条路由，该路由器使用BGP标识符来选择路由

5.4.4 IP 任播

BGP还常被用于实现IP任播（anycast）服务,该服务通常用于DNS中

• CDN公司为它的多台服务器指派相同的IP地址，并且使用标准的BGP从这些服务器的每台来通告该IP地址。当某台BGP路由器收到对于该IP地址的多个路由通告，它将这些通告处理为对相同的物理位置提供不同的路径。

• 当配置其路由选择表时，每台路由器将本地化地使用BGP路由选择算法来挑选到该IP地址的“最好的”（例如，由AS跳计数确定的最近的）路由

• 在这个初始BGP地址通告阶段后，CDN能够进行其分发内容的主要任务。

• 当该客户想向那个IP地址发送一个请求时,因特网路由器则向那个“最近的”服务器转发该请求分组，最近的服务器是由BGP路由选择算法所定义的

实践中CDN通常选择不使用IP任播，IP任播被DNS系统广泛用于将DNS请求指向最近的根DNS服务器

5.4.5 路由选择策略

在路由选择算法中，实际上首先根据本地偏好属性选择路由，本地偏好值由本地AS的策略所确定。

例：

W、X和Y是接入ISP,而A、B和C是主干提供商网络。

假设一个ISP只想 路由流量到/去往它的客户网络 (不想承载其他ISPs之间的流量，即不通告：不是去往我的客户，也不是来自我的客户)

• A向B和C通告路径Aw

• B选择不向C通告BAw：

  • B从CBAw的路由上无法获得收益，因为C,A,w都不是B的客户
  • C从而无法获知 CBAw路径的存在：每个ISP感知到的网络和真实不一致

• C可能会通过 CAw (而不是使用B)最终路由到w

• X 是双重接入的，多宿桩网络，接入了2个网络

• 策略强制让X:X不想路由 从B通过X到C的分组，因而X就不通告给B，它实际上可以路由到C

5.5 SDN控制平面

传统方式：每-路由器(Per-router)控制平面

在每一个路由器中的单独路由器算法元件，在控制平面进行交互

SDN方式：逻辑上集中的控制平面

一个不同的（通常是远程的）控制器与本地控制代理（CAs）交互

SDN体系结构具有4个关键特征

• 基于流的转发。SDN控制的交换机的分组转发工作，能够基于运输层、网络层或链路层首部中任意数量的首部字段值进行
• 数据平面与控制平面分离。数据平面由网络交换机组成，交换机是相对简单（但快速）的设备，该设备在它们的流表中执行“匹配加动作”的规则。控制平面由服务器以及决定和管理交换机流表的软件组成
• 网络控制功能：位于数据平面交换机外部。
• 可编程的网络。通过运行在控制平面中的网络控制应用程序，该网络是可编程的。

5.5.1 SDN控制平面：SDN控制器和SDN网络控制应用程序

SDN控制平面大体划分为两个部分，即SDN控制器和SDN网络控制应用程序。

控制器的功能可大体组织为3个层次

• 通信层：SDN控制器和受控网络设备之间的通信。
• 网络范围状态管理层
• 对于网络控制应用程序层的接口。控制器通过它的“北向”接口与网络控制应用程序交互。

5.5.2 OpenFlow 协议

OpenFlow协议运行在SDN控制器和SDN控制的交换机或其他实现OpenFlow API的设备之间，协议运行在TCP之上，使用6653的默认端口号

从控制器到受控交换机流动的重要报文有下列这些

• 配置：该报文允许控制器查询并设置交换机的配置参数
• 修改状态：该报文由控制器所使用，以增加/删除或修改交换机流表中的表项，并且设置交换机端口特性。
• 读状态：该报文被控制器用于从交换机的流表和端口收集统计数据和计数器值。
• 发送分组：该报文被控制器用于在受控交换机从特定的端口发送出一个特定的报文

受控交换机到控制器流动的重要报文有下列这些：

• 分组进入: 将分组（和它的控制）传给控制器，见来自控制器的packet-out报文
• 流移除: 在交换机上删除流表项
• 端口状态: 通告控制器端口的变化

网络管理员不需要直接通过创建/发送流表来编程交换机，而是采用在控制器上的app自动运算和配置

5.5.3 数据平面和控制平面交互的例子

1. S1, 经历了链路失效，采用OpenFlow报文通告控制器:端口状态报文
2. SDN 控制器接收OpenFlow报文，更新链路状态信息
3. Dijkstra路由算法应用被调用（前面注册过这个状态变化消息）
4. Dijkstra路由算法访问控制器中的网络拓扑信息，链路状态信息计算新路由
5. 链路状态路由app和SDN控制器中流表计算元件交互，计算出新的所需流表
6. 控制器采用OpenFlow在交换机上安装新的需要更新的流表

5.6 ICMP：因特网控制报文协议

因特网控制报文协议（ICMP）,被主机和路由器用来彼此沟通网络层的信息。

ICMP通常被认为是IP的一部分，但从体系结构上讲它位于IP之上，因为ICMP报文是承载在IP分组中的。

ICMP报文是作为IP有效载荷承载的

ICMP报文有一个类型字段和一个编码字段，并且包含引起该ICMP报文首次生成的IP数据报的首部和前8个字节（以便发送方能确定引发该差错的数据报）

Traceroute程序

该程序允许我们跟踪从一台主机到世界上任意一台主机之间的路由。Traceroute是用ICMP报文来实现的

为了判断源和目的地之间所有路由器的名字和地址，源主机中的Traceroute向目的地主机发送一系列普通的IP数据报

这些数据报的每个携带了一个具有不可达UDP端口号的UDP报文段。

• 第一个：TTL =1
• 第二个：TTL=2, etc.
• 该源主机也为每个数据报启动定时器

第n个数据报到达第n台路由器时，第n台路由器观察到这个数据报的TTL正好过期

• 路由器抛弃数据报
• 然后发送一个给源的ICMP报文 (type 11, code 0)
• 报文包括了路由器的名字和IP地址

当ICMP报文到达，源端计算RTT

停止的判据：

• UDP 段最终到达目标主机
• 目标返回给源主机ICMP “端口不可达”报文 (type 3, code 3)
• 当源主机获得这个报文时，停止

5.7 网络管理和SNMP

什么是网络管理？

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

5.7.1 网络管理框架

• 管理服务器是一个应用程序，通常有人的参与，并运行在网络运营中心（NOC）的集中式网络管理工作站上。
• 被管设备是网络装备的一部分（包括它的软件），位于被管理的网络中。在一个被管设备中，有几个所谓被管对象
• 一个被管设备中的每个被管对象的关联信息收集在**管理信息库（MIB）**中，我们将看到这些信息的值可供管理服务器所用
• 在每个被管设备中还驻留有网络管理代理，它是运行在被管设备中的一个进程，该进程与管理服务器通信，在管理服务器的命令和控制下在被管设备中采取本地动作。
• 网络管理框架的最后组件是网络管理协议。该协议运行在管理服务器和被管设备之间，允许管理服务器查询被管设备的状态，并经过其代理间接地在这些设备上采取行动。

5.7.2 简单网络管理协议

简单网络管理协议是一个应用层协议，用于在管理服务器和代表管理服务器执行的代理之间传递网络管理控制和信息报文。

SNMP最常使用的是请求响应模式，其中SNMP管理服务器向SNMP代理发送一个请求，代理接收到该请求后，执行某些动作，然后对该请求发送一个回答。

SNMP第二个常被使用的是代理向管理服务器发送的一种非请求报文，该报文称为陷阱报文（trap message）

SNMPv2定义的7种类型的报文

务器和被管设备之间，允许管理服务器查询被管设备的状态，并经过其代理间接地在这些设备上采取行动。