第5章：网络层-控制平面

1.概述

完成转发表和流表的计算、维护和安装有两种可能的方法：

• 每路由器控制：每台路由器有一个路由选择组件，用于与其他路由器中的路由选择组件通信，以计算其转发表的值
• 逻辑集中式控制：每台路由器有一个控制代理（CA），其任务是与控制器通信并且按控制器命令行事

2.路由选择算法

可以用图来形式化描述路由选择问题，图 G = (N, E) 是一个N个节点和E条边的集合

路由选择算法的一种分类方式是根据算法是集中式还是分散式来划分：

• 集中式路由选择算法：用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径，要求算法在真正开始计算之前，要以某种方式获得这些信息，具有全局状态信息的算法常被称作链路状态（Link State, LS）算法，因为该算法必须知道网络中每条链路的开销
• 分散式路由选择算法：每个节点仅有与其直接相连链路的开销知识即可开始工作，然后通过迭代计算过程以及相邻节点的信息交换，一个节点逐渐计算出到达某目的节点或一组目的节点 的最低开销路径。其中一个分散式路由选择算法称为距离向量（Distance-Vector, DV）算法，之所以叫做DV，是因为每个节点维护到网络中所有其他节点的开销（距离）估计的向量

路由选择算法的第二种广义分类方式是根据算法是静态的还是动态的进行分类

• 静态路由选择算法：路由随时间的变化非常缓慢，通常是人工进行调整
• 动态路由选择算法：随着网络流量负载或拓扑发生变化而改变路由选择路径

路由选择算法的第三种分类方式是根据它是负载敏感的还是负载迟钝的进行划分

• 负载敏感算法：链路开销会动态地变化以反映出底层链路的当前拥塞水平
• 负载迟钝算法：某条链路的开销不明确地反映其当前（或最近）的拥塞水平

链路状态路由选择算法

Dijkstra算法：计算从某节点到网络中所有其他节点的最低开销路径

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

Initialization:
N/' = {u}
for all nodes v
	if v is a neighbor of u
		then D(v) = c(u, v)
	else D(v) = ∞
	
Loop
find w not in N/' such that D(w) is a minimum
add w to N/'
update D(v) for each neighbor v of w and not in N/':
	D(v) = min(D(v), D(w) + c(w, v))
	
until N/' = N

距离向量路由选择算法

距离向量（Distance-Vector, DV）算法是一种迭代的、异步的和分布式的算法

Bellman-Ford方程：

$$d_x(y) = min_v \{c (x, v) + d_v(y)\}$$ $d_x(y)$是从节点x到节点y的最低开销路径

每个节点$x$以$D_x(y)$开始，对在$N$中的所有节点$y$，估计从$x$到$y$的最低开销路径的开销。使用DV算法，每个节点$x$维护下列路由选择信息：

• 对于每个邻居$v$，从$x$到直接相连邻居$v$的开销为$c(x,v)$
• 节点$x$的距离向量，即$D_x = [D_x(y): y \in N]$，包含了$x$到$N$中所有目的地$y$的开销估计值
• 它的每个邻居的距离向量，即对$x$的每个邻居$v$，有$D_v = [D_v(y): y \in N]$

每个节点不时的向它的每个邻居发送它的距离向量副本，当节点$x$从它的任何一个邻居$w$接收到一个新距离向量，它保存$w$的距离向量，然后使用Bellman-Ford方程更新自己的距离向量，如果节点$x$的距离向量因这个更新步骤而改变，节点$x$接下来向它的每个邻居发送其更新后的距离向量，继而让所有邻居更新它们自己的距离向量

链路开销改变与链路故障

当出现链路开销增加的情况：

• $t_0$时刻，$y$检测到链路开销变化，$y$计算它到$x$的新的最低开销路径的开销，其值为： $$D_y(x) = min \{c(y,x) + D_x(x), c(y,z) + D_z(x) \} = min \{ 60 + 0, 1+5 \} = 6$$

  从全局看，这个开销是错误的，到了$t_1$时刻，遇到路由选择环路（routing loop），为了到达$x$，$y$通过$z$路由，$z$又通过$y$路由，在这两个节点之间不停的来回反复

• 因为节点$y$已算出到$x$的新的最低开销，它在$t_1$时刻将该新距离向量通知$z$

• 在$t_1$后某个时间，$z$收到$y$的新距离向量，它指示了$y$到$x$的最低开销是6，$z$知道它能以开销1到达$y$，因此算出到$x$的新最低开销是7，于是在$t_2$时刻通知$y$其新开销

• 不断重复

• 循环持续44次迭代，直到$z$算出它经由$y$的路径开销大于50为止

增加毒性逆转

如果$z$通过$y$路由选择到目的地$x$，则$z$将通告$y$，它到$x$的距离是无穷大，这样$y$将永远不会试图经由$z$路由选择到$x$

LS与DV路由选择算法的比较

• 报文复杂性：
  • LS算法要求每个节点都知道网络中每条链路的开销
  • DV算法要求在每次迭代时，在两个直接相连邻居之间交换报文
• 收敛速度：
  • LS算法是$O(NE)$算法
  • DV算法收敛慢
• 健壮性
  • LS算法：路由器能够向其连接的链路广播不正确的开销，一个节点也可损坏或丢弃它收到的任何LS广播分组，一个LS仅计算自己的转发表，路由计算在某种程度上是分离的
  • DV算法：一个节点的计算会传递给它的邻居，然后在下次迭代时再间接地传递给邻居的邻居，一个不正确的节点计算值会扩散到整个网络

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

• 规模：规模增大
• 管理自治：每个ISP都有自己的路由器网络，ISP通常希望按自己的意愿运行路由器，或对外部隐藏其网络的内部组织面貌，理想情况下，一个组织应当能够按照自己的愿望运行和管理器网络，还要能将其网络与其他外部网络连接起来

可以通过将路由器组织进自治系统（Autonomous System, AS）来解决，其中每个AS由一组通常处在相同管理控制下的路由器组成，在相同AS中的路由器都运行相同的路由选择算法并且有彼此的信息，在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议（intra-autonomous system routing protocol）

开放最短路优先（OSPF）

• 使用洪范链路状态信息和Dijkstra最低开销路径算法
• 每台路由器在本地运行Dijkstra的最短路径算法，以确定一个以自身为根节点的所有子网的最短路径树
• 路径开销由管理员配置
  • 可以将所有链路开销设为1，因而实现最少跳数路由选择
  • 也可以将链路权值按与链路容量成反比来设置，从而不鼓励流量使用低宽带链路
• 每当一条链路的状态发生变化时，路由器就会广播链路状态信息，即使链路状态未发生改变，也要周期性地广播链路状态

OSPF的优点有以下几方面：

• 安全
• 多条相同开销的路径
• 对单播与多播路由选择的综合支持
• 支持在单个AS中的层次结构

4.ISP之间的路由选择：BGP

自治系统间路由选择协议（inter-autonomous system routing protocol），在因特网中，所有的AS运行相同的AS间路由选择协议，称为边界网关协议（Broder Gateway Protocol, BGP）

BGP是一种分布式和异步的协议

BGP的作用

在BGP中，分组不是路由到一个特定的目的地址，二十路由到CIDR化的前缀，其中每个前缀表示一个子网或一个子网的集合

BGP为每台路由器提供了一种完成以下任务的手段：

• 从邻居AS获得前缀的可达性信息：BGP允许每个子网向因特网的其余部分通告它的存在
• 确定到该前缀的“最好的”路由：为了确定最好的路由，该路由器将本地运行一个BGP路由选择过程

通告BGP路由信息

对于每个AS，每台服务器可能是：

• 网关路由器（gateway router）：位于AS边缘的路由器，直接连接到在其他AS中的一台或多台路由器
• 内部路由器（internal router）

在BGP中，每对路由器通过使用179端口的半永久TCP连接交换路由选择信息。每条直接连接以及所有通过该连接发送的BGP报文，称为BGP连接，此外，跨越两个AS的BGP连接称为外部BGP（eBGP）连接，而在相同AS中的两台路由器之间的BGP对话称为内部BGP（iBGP）连接

确定最好的路由

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

前缀及其属性称为路由（route），两个较为重要的属性时AS-PATH和NEXT-HOP

• AS-PATH属性包含通告已经通过的AS的列表：

  • 当某一个前缀通过某AS时，该AS将其ASN加入AS-PATH中的现有列表。
  • BGP路由器还使用AS-PATH属性来检测和防止通告环路：如果一台路由器在路径列表中看到了包含自己的AS，将拒绝该通告

• NEXT-HOP是AS-PATH起始的路由器接口的IP地址

  

这里AS1中的每台路由器都知道了到前缀x的两台BGP路由：

• 路由器2a的最左侧接口的IP地址：AS2 AS3；x
• 路由器3d的最左侧接口的IP地址：AS3；x

每条BGP路由包含3个组件NEXT-HOP；ASPATH；目的地前缀

热土都路由选择（hot potato routing）

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

路由器选择算法

对于任何给定的目的地前缀，进入BGP的路由选择算法的输入是到某前缀的所有路由的集合，该前缀是已被路由器学习和接受的。如果只有一条这样的路由，BGP则显然选择该路由。如果到相同的前缀有两条或多条路由，则顺序地调用下列消除规则直到余下一条路由：

1. 路由被指派一个本地偏好（local preference）值作为其属性之一， 本地偏好属性的值是一种策略决定，完全取决于该AS的网络管理员
2. 从余下的路由中（所有都具有相同的最高本地偏好值），将选择具有最短AS-PATH的路由。如果该规则是路由选择的唯一规则，则BGP将使用距离向量算法决定路径，其中距离测度使用AS跳的跳数而不是路由器跳的跳数
3. 从余下的路由中（所有都具有相同的最高本地偏好值和相同的AS-PATH长度），使用热土豆路由选择
4. 如果仍留下多条路由，则选择具有最靠近NEXY-HOP的路由器的路由

5.SDN控制平面

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

• 基于流的转发：传统方法中IP数据报的转发仅依据数据报的目的IP地址进行；SDN控制平面的工作是计算、管理和安装所有网络交换机中的流表项

• 数据平面与控制平面分离：

  • 数据平面由网络交换机组成，交换机是相对简单的设备，该设备在它们的刘表中执行“匹配加操作”的规则
  • 控制平面由服务器及其决定和管理交换机流表的软件组成

• 网络控制功能：位于数据平面交换机外部，SDN控制平面由软件实现，这个软件在服务器上执行，该服务器与网络交换机截然分开且与之远离

  控制平面自身由两个组件组成：一个SDN控制器，以及若干网络控制应用程序

  

• 可编程的网络

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

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

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

• 通信层：SDN控制器和受控网络设备之间的通信。控制器和受控设备之间的通信跨越了一个接口，被称为控制器的“南向”接口，OpenFlow是一种提供这种通信功能的特定协议
• 网络范围状态管理层：由SDN控制平面所做出的最终控制决定
• 对于网络控制应用程序层的接口：控制器通过它的“北向”接口与网络控制应用程序交互

OpenFlow协议

运行在SDN控尸气和SDN控制的交换机或其他实现OpenFlow API的设备之间

从控制器流向受控交换机的重要报文如下：

• 配置
• 修改状态
• 读状态
• 发送分组
• 流删除
• 端口状态
• 分组入

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

假设交换机s1和s2之间的链路断开，并实现了最短路径路由选择，因此，除了s2操作未改变外，s1、s3和s4的入和出流转发规则都受到影响。也假定OpenFlow被用作通信层协议，控制平面只执行链路状态路由选择而不执行其他功能

1. 交换机s1经历与s2的链路故障，使用OpenFlow“端口状态”报文向SDN控制器通报该链路状态的更新
2. SDN控制器接收指示链路状态更新的OpenFlow报文，并且通告链路状态管理器，由管理器更新链路状态库
3. 实现Dijkstra链路状态路由选择的应用程序接受该链路状态更新的通告
4. 计算新的最低开销路径
5. 链路状态路由选择应用与流表管理器交互，流表管理器决定更新的流表
6. 流表管理器使用OpenFlow协议更新位于受影响的交换机s1、s2和s4的流表项

6.ICMP：因特网控制报文协议

ICMP被主机和路由器用来彼此沟通网络层的信息，最典型的用途是差错报告

ICMP报文是作为IP有效载荷承载的，就像TCP和UDP报文段作为IP有效载荷被承载那样

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

7.网络管理、SNMP和NETCONF/YANG

网络管理框架

• 管理服务器
• 被管设备
• 数据
• 网络管理代理
• 网络管理协议
• CLI
• SNMP/MIB：通过简单网络管理协议（Simple Network Management Protocol, SNMP）查询/设置设备的管理信息库（Management Information Base, MIB）
• NETCONF/YANG

简单网络管理协议和管理信息库

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

SNMP最常使用的是请求相应模式，SNMP管理服务器向SNMP代理发送一个请求，代理收到后，执行某些操作，然后发送回答

SNMP第二种常用的功能是代理向管理服务器发送的一种非请求报文，该报文称为陷阱报文（trap message），用于通知管理服务器，一个异常情况已经导致了MIB对象值的改变