网络层：控制平面

5.1概述

之前说过转发表和流表的计算、维护和安装有2种方法，每路由器控制和逻辑集中式控制。

每路由器控制中每台路由器运行一种路由选择算法，每台路由器都有转发和路由选择的功能。每台路由器都有一个路由选择组件，用于与其他路由器中的路由选择组件通信，以计算转发表。

逻辑集中式控制一般由一个协议与每台路由器中的控制代理（CA）进行交互，以配置和管理路由器的转发表。CA一般具有最少的功能，主要任务是与控制器通信并且按控制器命令行事。这些CA不能相互交互，也不能主动参与计算转发表。

5.2路由选择算法

路由选择算法的目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径。通常一条好的路径指具有最低开销的路径。实际生活中可能还会关心不同组织的策略等。

可以使用图的方式来描述路由选择问题，图G=（N，E）是一个N个节点和E条的集合其中每条边都连接两个节点。在网络层路由选择环境中，图中的节点标识路由器，这是做出分组转发决定的点；连接这些节点的边就是路由器之间的物理链路。如果是在BGP域间路由协议下，这些节点可能代表网络，边代表两个网络之间的对等连接。

如下图，每条边还有一个值来代表其对应的开销。通常一条边的开销可能反映出对应链路的物理长度，或金钱开销。对于任意一条边，我们用c（x，y）表示节点xy之间的开销。如果不存在这个路径，那么开销为无穷大，此外这里只考虑无向图（路径没有方向）如果（x，y）属于E，就说y是x的邻居。

路由选择算法的目标就是找出从源到目的主机的最低开销路径。在G=（N，E）中路径是一个节点序列（x1,x2,x3...）没对节点（x1,x2）(x2,x3)...都是一个边，这条路径的开销就是所有边的开销的总和。两个节点中有多条路径，每条路径都有一个开销，其中会有最低开销的路径，如果所有边具有相同的开销，那么最低开销路径就是最短路径。

路由选择算法可以分为集中式和分散式两种：

集中式路由选择算法用完整的、全局性的网络知识计算出从源到目的地直接的最低开销路径。这要求该算法在开始计算之前就需要了解到这个网络的所有节点的连通性和每条链路的开销。计算可以在特定的地点进行，也可以在每个路由器的路由选择组件中进行。这种具有全局状态信息的算法叫做链路状态（LS）算法

分散式路由选择算法中，路由器以迭代、分布式的方法计算出最低开销路径。每个节点仅有与其相连的链路的开销知识，通过迭代计算以及与相邻节点的信息交换，一个节点计算出到达目标节点或一组目的节点的最低开销路径。这种分散式算法更适合路由器直接交互的控制平面。

路由选择算法的第二类分类方式是按照其算法是静态还是动态来分类。在静态路由选择算法中，路由随时间变化很慢，通常是人工进行调整；动态路由选择算法中，随着网络流量负载或网络拓扑发生变化而改变路由选择路径，可周期性的运行或直接响应拓扑和链路开销的变化而运行。但也容易受路由选择循环、路由震荡之类影响。

第三类分类方式是根据其是负载敏感还是负载迟钝。负载敏感算法中，链路开销会动态的反应出底层链路的拥塞水平。而当今的路由选择算法大多是负载迟钝的，因为链路的开销不明确地反应底层链路的颜色水平。

5.2.1链路状态路由选择算法

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

下面的链路状态算法叫做dijkstra算法，它计算从某节点到网络中其他节点的最低开销路径，其算法的本质是经历k次迭代后，可以获得k个最低开销路径，D(v)记作到本次迭代源到目的节点v的最低开销路径，p(v)是从源到v沿着最低开销路径的v的邻居。N`是节点子集，也就是已经确定最低开销路径要经过的节点集合。

在算法终止时，会获得沿着最低开销路径到所有节点的前一个节点以及最低开销，而对于前一个节点，我们也有其的前一个节点，以此类推即可构建完整路径。并形成一个转发表

但是在网络拓扑中，相同链路不同方向的开销是不同的，也就是链路开销是非对称的。下图中，x、z分别向w发送一个单元的流量y发送数量为e的流量。

如上图，初始时，z，x，y的路由选择如图a；图b时因为（w，x）的流量较大，开销增多，导致所有流量方向呈顺时针，因此图c又会呈现逆时针，以此类推呈现出网络振荡的状态。显然会影响LS算法对路由路径的计算。一种解决方法是强制所有链路开销不依赖流量（显然不可行）第二种是确保并非所有的路由器都同时运行LS算法（类似一个“阻尼”的作用，减小网络振荡的幅度）我们希望即使所有路由器都以相同周期运行LS算法，但在每个节点的算法的执行时机不相同。值得一提的是，因特网上的路由器能实现自同步，即使在每个节点的算法的执行时刻不相同，算法的执行时机也会在路由器上变为相同并保持，解决方法就是让每台路由器发布链路通告的时间随机化。

5.2.2距离向量路由选择算法

距离算法（DV）算法是一种迭代的、异步的、分布式的、自我终止的算法。令dx(y)是从节点x到y的最低开销，那么dx(y)=minv{c(x,y)+dv(y)}(Bellman-Ford方程)

此方程的解不仅为转发表提供了表项，而且它提出了将在DV算法中发生的邻居到邻居通信的形式。

每个节点以Dx(y)开始，对N中的所有节点y，估计从x到y的最低开销路径的开销。令Dx=[Dx(y):y∈N]是节点x的距离向量，是从x到N中的其他节点y的开销估计向量。使用DV算法，每个节点维护一下信息：

对于邻居v，从x到直接相连邻居v的开销为c(x,v);

节点x的距离向量，即D=[Dx(y):y∈N],包含了x到N中所有目的地y的开销估计值；

它的每个邻居的距离向量，即对x的每个邻居v都有Dv=[Dv(y):y∈N]

在该算法中，每个节点不时的向每个邻居发送它的距离向量副本，当该节点x从它的任何一个邻居w接收到一个新的距离向量，它保存w的距离向量然后使用Bellman-Ford公式更新自己的距离向量。如果节点x的距离向量因此发生改变，x接下来就会向它的每个邻居发生其更新后的距离向量，继而让所有邻居继续更新他们的距离向量，每个开销估计都会收敛到实际的最低开销路径的开销。

在DV算法中，x想要知道到目的节点y的最短路径开销，真正需要知道的是沿着最低开销路径的下一跳的节点。LS是一个全局性的算法，是因为它需要获取整个网络的全局信息，而DV算法是分布式的，节点所需要的唯一信息是从邻居节点获取到的信息和到邻居节点的链路开销。

下图是一个DV算法的运行示例，

从邻居接收更新距离向量、重新计算路由选择表项和通知邻居到目的地最低开销路径的开销已经变化的过程继续下去，直到无更新报文发送，就不会再进行路由选择表的计算，算法就会进入静止状态，直到某条链路开销发生改变。

1.距离向量算法：链路开销改变和链路故障

当DV算法检测到从它到邻居节点的链路开销发生变化时，它就会更新距离向量，如果最低开销路径发生变化，其就会向邻居通知更新向量。

如图a，如果y->x的开销由4减小到1，y此时会更新路由选择表并由路径y->z告知z更新距离向量，z再向y发送更新报文，y的开销不变，不再发送更新报文。只需两次迭代即可达到静止状态。

如图b，在链路开销变化前，Dy(x)=4,Dy(z)=1,Dz(x)=c(z,y)+c(y,x)=5.如果y->x的开销增大到60，

此时y计算出的新的Dy(x)=min{c(y,x),D(y,z)+D(z,x)}=min{60,1+5}=6,此时y会向z发送更新报文，z之后又会向y发送更新报文，此时就会发送路由选择环路，双方会反复的发送更新报文直到计算出准确的最低开销（会经过44次迭代）如果c(y,z)变为∞呢，此时会迭代无穷多次。

2.距离向量算法：增加毒性逆转

刚刚描述的问题可以使用毒性逆转的技术解决。如果z通过y路由到x，z将告诉y，它到x的距离是无穷大，也就是z将向y通告Dz(x)=∞（即使z认为Dz(x)=5）y相信z没有到x的路径，y就不会试图从z路由到x。

此时面对刚刚的问题，y的距离表中Dz(x)=∞，所以Dx(y)=60,然后y向z发送更新报文，z会更新Dz(x)为50，然后再更新y的距离变量。毒性逆转虽然可以解决这个路由选择环路问题，但是如果是涉及到3个或3个以上节点的环路，毒性逆转无法检测到这个环路。

3.LS和DV算法的比较

DV和LS算法采用互补的方式解决路由选择计算问题，在DV算法中，每个节点与邻居节点交谈并交换自己所知的所有最低开销估计；而LS算法需要全局信息，每个节点在计算前需要向所有节点进行广播并发送自己相邻节点的链路开销。

报文复杂性：LS需要每个节点都知道网络中所有链路的开销，其需要发送O(|N|·|E|)个报文，而且只要有一个链路开销变化，就需要向所有节点发送新的链路开销。DV算法只需在迭代时向邻居发送报文，但在DV算法中有多种影响因素，当链路开销改变时，DV算法仅在新的链路开销导致与该链路最低开销发生变化时才会更新向量。

收敛速度：LS的收敛速度为O(|N|·|E|)，而DV算法的收敛速度难以估量，如果遇到环路，可能还会转变为无穷级数。

健壮性：如果一台路由器发生故障或行为错乱时，对于LS算法，该路由器可能会向其他路由器广播错误的开销或者损害和丢弃其接收到的LS分组，但LS算法的计算可以是分布式的，提供了一定的健壮性。对于DV算法，一个节点可以向邻居节点通告错误的最低开销路径，而且DV算法中每个节点的运算还会传递给它的邻居，此时这个错误的计算值可能会扩散到整个网络。

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

网络的路由器的规模较大且大多数网络会由ISP或组织管理自治，所有会使用自治系统（AS）来解决。一个AS通常由一组处在相同管理控制下的路由器组成，通常是一个ISP的路由器和互联他们的链路组成。某些ISP也会将他们的网络分为多个互联的AS。每个AS由全局唯一的一个AS号（ASN）标识。在相同AS中的路由器都运行相同的路由选择算法且有彼此的信息。在一个AS中运行的路由选择算法叫做自治系统内部路由选择协议.

开放最短路优先（OSPF）

OSPF是一种链路状态协议，使用洪泛链路状态信息和Dijkstra最低开销路径算法，每个路由器都有一个完整的网络拓扑图，路由器在本地运行Dijkstra算法。每条链路开销都是网络管理员手动配置的。

使用OSPF时，路由器向AS中的所有的其他路由器广播路由选择信息，当有链路状态发生变化时就会进行广播，即使没有发生变化，每30min也会进行一次广播。OSPF通告包含在OSPF报文中，该报文由IP承载，协议需要自己实现可靠报文传输，链路状态广播等功能。OSPF还需要检测链路正在运行（通过向邻居发送HELLO报文）并允许OSPF路由器获取邻居的网络范围链路状态的数据库。

OSPF的优点有安全、允许使用多条相同开销的路径（当开销相同时可以同时使用多条链路）、对单播和多播的支持、支持在AS中的层次结构。

5.4ISP之间的路由选择：BGP

OSPF是AS内部的路由选择协议，还需要AS间的路由选择协议即自治系统间路由选择协议。在因特网中，不同AS之间必须运行相同的AS间路由选择协议，叫做边界网关协议（BGP）

5.4.1BGP的作用

BGP的主要作用是使得AS内部的路由器可以访问到AS外的路由器。在BGP中，一个分组往往路由到一个CIDR化的前缀，如（138.16.68/22）路由器的转发表将具有(x,I)的表项，x是一个前缀，I是路由器一个接口的接口号。

作为AS间的路由选择协议，BGP使得路由器可以从邻居AS处获取前缀的可达性信息，也就是说每个子网都可以被所有AS所知道。而且BGP还可以确定到达该前缀的最好的路由。

5.4.2通告BGP路由信息

图中网络具有三个AS，AS3具有一个前缀为x的子网，AS中的路由器可以分为内部路由器和网关路由器。网关路由器是一台位于AS边缘的路由器，直接连接到其他AS中的一台或多台网关路由器。

如果AS3需要通告子网x的存在，在高层次上可能只需AS3向AS2发送一个报文，AS2再向AS1传送报文告知前缀x在AS3中即可，但实际上报文是由路由器发送的，也就是说这并不准确。在BGP中每对路由器通过179端口建立TCP连接交换路由选择信息，每条直接连接以及通过该连接发送的所有BGP报文叫做BGP连接。跨越了两个AS的BGP连接叫做外部BGP（eBGP）连接在AS内部的叫做内部BGP（iBGP）连接。如下图，

此时在AS3通告子网x时，首先网关路由器3a会向2c发送一个eBGP报文“AS3 x”2c接着向AS2中的其他路由器发送iBGP报文“AS3 x”然后2a会向AS1发送eBGP报文“AS2 AS3 x”，AS1中再通告iBGP报文“AS2 AS3 x”（当然，多个AS时同一个AS中的路由器可能会有多条路径到达x）

5.4.3确定最好的路由

当路由器通过BGP连接通告前缀时，会在前缀中包括一些BGP属性，在BGP中前缀及其属性被称为路由。比较重要的属性有AS-PATH(表示该通告已经经过的AS)和NEXT-HOP(AS-PATH路径中，通往下一跳的网关路由器的对应接口的IP)BGP路由器可以使用AS-PATH检测和避免通告环路，如果一个路由器在路径中看到了自己，它将拒绝该通告。

1.热土豆路由选择

热土豆路由选择的最大特定是尽快转发，会将分组尽快的进行转发而不是在本地大量的计算整个最低开销路径。它会根据已知的所有路径，例如有两个路径“AS2 AS3 x”“AS3 x”其中的NEXT-HOP字段分别对应网关路由器2a和3d，AS1中路由器会分别计算到这两个网关路由器的最低开销并选择开销最低的进行转发，而不是计算到x的最低开销。（与之对应的计算到x的最低开销的叫做冷土豆协议）

2.路由器选择算法

在实践中，如果到达目标后缀只有一条路由，会直接进行转发，如果有多条路由会调用以下规则：

首先路由器会被指派一个本地偏好（由管理员设置）一条路由的本地偏好可能由该路由器设置或由相同AS中的另一个路由器学习到。具有最高偏好的路由将被选择；如果具有相同的偏好，将选择具有最短AS-PATH的路由（以跳数测量）；如果前两者相同，会使用热土豆路由选择；如果仍剩下多条路由，会使用BGP标识符来选择路由。

5.4.4任播

BGP还成被用于实现任播服务，通常位于DNS服务中。比如想要改变不同服务器上的相同内容或者让离用户最近的服务器响应用户需求。

在任播的配置阶段，CDN(内容分发网络)会为多台服务器指派相同的IP，使用标准的BGP从这些服务器的每台来通告该IP地址，当某台BGP路由器收到对于该IP地址的多个路由器通告时他会为这些通告提供不同的路径(因为具有多台服务器共享一个IP，此时物理路径是绝对不同的)当配置路由选择表时，每台路由器会本地使用BGP路由选择协议选择一台“更好的”路由。无论客户在哪里发送请求，都会向“最近的”服务器发送请求。

5.4.5路由选择策略

图中显示了6个AS，假设WXY是接入ISP，ABC是主干提供商网络，ABC直接向彼此直接发送流量，并向客户提供全部的BGP信息。所有进入一个接入ISP的流量的目的地一定是该网络，所有离开接入ISP的流量一定源于该网络。WY是接入ISP，X是一个多宿接入ISP（经不同的提供商连接到网络的其余部分）通过控制BGP路由通告方式，可以避免BC之间的流量通过X来传输。如果X没有向B和C通告它没有通往别的（除自身外）目的地的路径那么它就是一个接入ISP的作用，即使此时X知道有一个通往Y的路径，他也不会告知BC。

5.5SDN控制平面

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

基于流的转发。SDN控制的交换机的分组转发规则能基于运输层、网络层或链路层首部中任意数量的首部字段进行。分组转发的规则被定义在流表中，而SDN控制平面负责计算、管理和安装所有网络交换机中的流表项。

数据平面和控制平面分离。数据平面由网络交换机组成，控制平面由服务器以及决定和管理交换机流表的软件组成。

网络控制功能：位于数据平面交换机外部。网络控制功能从数据平面的网络设备中被提取出来，并集中在一个或多个服务器上实现，使得网络逻辑集中化。这种集中式的控制允许管理员以全局视角配置、监控和优化整个网络的行为。同时，通过开放的接口（如OpenFlow），SDN控制器能够动态地对交换机流表进行编程，实现灵活的流量管理和策略实施。

可编程的网络。运行在控制平面中的网络控制程序是可编程的，可以使用SDN控制器提供的API定义和控制网络设备中的数据平面。

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

SDN控制平面主要分为SDN控制器和SDN网络控制应用程序。控制器的功能主要分为3层。

通信层（控制器与受控设备跨越“南向”接口进行通信）、网络范围状态管理层（维护网络状态）、对于网络控制应用程序层的接口（与网络控制应用程序交互的“北向”接口）。

SDN控制器被认为是逻辑上集中的，在外部可以被视为整体，但是实际上可能会采取分布式的服务器集合实现。

5.5.2OpenFlow协议

此协议运行在SDN控制器和SDN控制的交换机或其他实现OpenFlowAPI的设备之间。运行于TCP，默认为6653端口。从控制器流向受控交换机的重要报文包括：配置（查询和设置交换机配置参数）、修改状态（修改交换机流表表项并设置交换机端口特性）、发送分组（用于在交换机从特定端口发送一个特定报文）

从受控交换机流向控制器的重要报文主要有：流删除（通知已删除一个流表项）、端口状态（通知端口状态变化）、分组入（没有匹配到的分组会交给控制器处理，匹配的分组也可能会交给交换机）

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

因特网控制报文协议（ICMP）被主机和路由器用来彼此沟通网络层的信息。最典型的用途就是差错报告。通常认为ICMP是IP的一部分，但是它在结构上位于IP之上，被作为IP的有效载荷承载。ICMP报文中有一个类型字段和一个编码字段，并且包含引起该ICMP报文首次生成的IP数据报的首部和前8字节（以便发送方确认引发差错的数据报）下图是ICMP报文类型

5.7网络管理、SNMP和NETCONF/YANG

5.7.1网络管理框架

管理服务器。管理服务器是一个应用程序，运行在网络运营中心（NOC）的集中式网络管理工作站上。管理服务器是执行网络管理活动的地方，控制网络管理信息和命令的收集、处理、分析和显示。在这里可以配置、监视和控制网络的被管设备。一个网络往往有多个管理服务器。

被管设备。可以是主机、路由器、交换机、中间盒等联网设备。

数据。每个被管设备都有与之相关联的数据，也叫状态。配置数据是有网络管理员显式配置的设备信息。运行数据是设备在运行过程中获取的信息。设备统计是设备操作员更新的状态指示器和计数。网络管理员可以远程查询设备数据，在一些情况下可以通过写入设备数据值来远程控制设备。

网络管理代理。网络管理代理是被运行在被管设备上的一个软件进程，与管理服务器通信，在管理服务器命令和控制下在被管设备上执行本地操作。

网络管理协议。该协议运行在管理服务器和被管设备之间，允许管理服务器查询被管服务器的状态，并经过其代理间接地在这些设备上执行操作。代理可以通过协议向管理服务器通知异常事件，但是网络管理协议不能自己管理网络。

在实践中，往往采用三种方式来管理网络，涉及组件包括：

CLI。运营商可以直接向设备发出命令行接口（CLI）命令，可以直接在被管设备的控制台上输入，或者远程输入。但是CLI命令比较困难且容易出错而且往往只针对单个设备

SNMP/MIB。运营商可以通过简单网络管理协议（SNMP）查询/设置管理信息库（MIB）对象中包含的数据。

NETCONF/YANG。NETCONF/YANG方法对网络管理采取了更抽象、全网络和整体的观点，更强调配置管理。YANG是一种用于对配置和操作数据进行建模的数据建模语言。NETCONF协议是用于对远端设备、从远端设备或在远端设备之间传递YANG兼容的操作和数据。

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

SNMP是一个应用层协议，用于管理服务器和管理服务器代理之间传递网络管理控制和信息报文。通常使用请求响应模式，常用于查询或修改与某被管设备有关的MIB对象值。

第二种常用的功能是发送陷阱报文（非请求报文）用于通知管理服务器一个异常情况导致MIB对象值的改变。

下表是SNMP版本3定义的7种报文，这些保额被称作协议数据单元（PDU）

5.7.3METCONF和YANG

NETCONF在管理服务器和被管理网络设备之间运行，提供报文用于：在被管设备上检索、设置和修改配置数据；查询被管设备的运行数据和统计；订阅由被管设备产生的通知。

NETCONF会话示例如下：

YANG是一种数据建模语言，用于定义NETCONF使用的网络管理数据的结构、语法和语义。