[网络协议]《计算机网络——自顶向下方法》学习笔记——网络层：控制平面

网络层：控制平面

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

OSPF 是一种运行在单一ISP的网络中的路由选择算法。
BGP 是一种在因特网中用于互联网所有网络的路由选择算法，因此常被称为因特网的“黏合剂”.

传统上，控制平面功能与数据平面的转发功能在一起实现，在路由器中作为统一的整体。

概述

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

这些表定义了一台路由器的本地数据平面转发行为。

本章学习这些转发表和流表如何计算、维护和安装的。

完成这些工作有两种可能的方法：

• 每路由器控制
  图5-1显示了在每台路由器中运行一种路由选择算法的情况，每台路由器都包含转发和路由选择功能。
  每台路由器有一个路由选择组件，用于与其他路由器的路由选择组件通信，以计算转发表的值。
  OSPF和BGP协议都基于这种每路由器的方法进行控制的。
• 逻辑集中式控制
  图5-2显示了逻辑集中式控制器计算并分发转发表以供每台路由器使用的情况。
  通用的 “匹配加动作”　抽象允许执行传统的IP转发及其他功能（负载共享、防火墙功能和NAT）的丰富集合。

该控制器经一种定义良好的协议与每台路由器中的一个控制代理（CA）进行交互，以配置和管理该路由器的转发表。
CA 与控制器通信并且按控制器命令行事。
CA 不能直接相互交互也不能主动参与计算转发表。

“逻辑集中式”控制意味着就像路由选择控制服务位于单一集中服务点那样获取它们，即使该服务处于容错和性能扩展性的原因，很可能经由多个服务器实现。

SDN采用了逻辑集中式控制器的概念。

路由选择算法

路由选择算法（routing algorithm），其目的是从发送方到接收方的过程中确定一条通过路由器网络的好的路径（等价于路由）。

通常，一条好路径指具有最低开销的路径。
实践中现实世界还关心诸如策略之类的问题。

必定存在一条定义良好的一连串路由器，使得分组从发送主机到接收主机跨越网络“旅行”。

图（graph）G=(N,E) 是一个N个节点和E条边的集合，其中每条边取自N的一对节点。

如上图所示，一条边还有一个值表示它的开销。

对E中的任一条边(x,y)，我们用c(x,y)表示节点x和y间边的开销。
如果 节点对 (x,y)不属于E，则置$c(x,y)=\infty$。
考虑无向图（即图的边没有方向），因此边（x, y）与边（y, x）是相同的并且 c(x, y) = c(y, x)。
如果(x,y)属于E，节点y也被称为节点x的邻居（neighbor）。

路由选择算法的天然目标是找出源到目的间的最低开销路径。
G=(N,E)中的一条路径是一个节点序列$(x_1,x_2,...,x_p)$
每个对$(x_1,x_2),(x_2,x_3),...,(x_{p?1},x_p)$是E中的边。
路径$(x_1,x_2,...,x_p)$的开销只是沿着路径所有边的开销总和，即$c(x_1,x_2)+c(x_2,x_3)+...+c(x_{p?1},x_p)$。

给定任何两个节点x和y，通常在这两个节点之间有许多条路径，每条路径都有一个开销。
这些路径中的一条或多条是最低开销路径（least-cost path）。

若所有的边具有相同的开销，则最低开销路径也就是最短路径（shortest path），即在源和目的地之间的具有最少链路数量的路径。

路由选择算法在一个位置运行，该位置具有网络的完整信息。

一般而言，路由选择算法的一种分类方式是根据该算法是集中式还是分散式来划分。

• 集中式路由选择算法
  用完整的，全局性的网络知识计算出从源到目的之间的最低开销路径。
  以所有节点的联通性及所有链路的开销为输入。
  计算本身可在某个场点进行，或在每台路由器的路由选择组件中重复进行。
  具有全局状态信息的算法称作链路状态算法

• 分散式路由选择算法
  路由器以迭代，分布式方式计算出最低开销路径。
  没有节点拥有关于网络链路开销的完整信息。
  每个节点仅有与其直接相连链路的开销知识。
  通过迭代计算过程及与相邻节点的信息交换，一个节点逐渐计算出到达某目的节点或一组目的节点的最低开销路径。
  距离向量算法（Distance-Vector, DV），分散式路由选择算法。
  之所以叫作DV算法，是因为每个节点维护网络中所有其他节点的开销（距离）估计的向量。
  通过路由器间交互式报文交换。

路由选择算法第二种广义分类根据算法是静态还是动态进行分类。
静态路由选择算法中，路由随时间变化缓慢，通常是人工进行调整（如人为手工编辑一条链路开销）。
动态路由选择算法，随着网络流量负载或拓扑发生变化而改变路由选择路径。

路由选择算法的第三种分类是根据它是负载敏感还是负载迟钝划分。
负载敏感算法中，链路开销会动态变化以反映底层链路当前拥塞水平。
当今的因特网路由选择算法（如 RIP、OSPF 和 BGP）都是负载迟钝的，因为某条链路开销不明确地反映其当前（或最近）的拥塞水平。

链路状态路由选择算法

在链路状态算法中，网络拓扑和所有链路开销已知，也就是说可用作LS算法的输入。
实践中这是通过让每个节点向网络中所有其他节点广播链路状态分组来完成，其中每个链路状态分组包含它所连接的链路的标识和开销。
在实践中，这经常由链路状态广播算法来完成。

节点广播的结果是所有节点都具有该网络的统一，完整的视图。
于是每个节点都可运行LS算法并计算出相同的最低开销路径集合。

Dijkstra算法计算从某节点（源节点，称为u）到网络中所有其他节点的最低开销路径。
Dijkstra算法是迭代算法，其性质是，经算法的第ｋ次迭代后，可知ｋ个目的节点的最低开销路径，在到所有目的节点的最低开销路径中，这ｋ条路径有ｋ个最低开销。

定义下列记号：

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

下图显示了一个简单的网络拓扑、图中的链路开销等于链路上承载的负载，例如反映要历经的时延。
防止这样的振荡：
一种解决方案可能强制链路开销不依赖于所承载的流量，但那是一种不可接受的解决方案，因为路由选择的目标之一是避开高度拥塞（或高时延）链路。
另一种方案是，保证并非所有路由器都同时运行LS算法。

距离向量路由选择算法

距离向量（Distance-Vector, DV）算法是一种迭代的，异步的，分布式的算法而LS算法是一种使用全局信息的算法。

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

存在于最低开销路径的开销间的一种重要关系。
令$d_x(y)$表示从节点x到节点y的最低开销路径的开销。
则该最低开销与著名的Bellman-Ford方程相关，即：
d x ( y ) = m i n v { c ( x , v ) + d v ( y ) } d_{x}(y)=min_{v}\{c(x,v) + d_{v}(y)\} dx?(y)=minv?{c(x,v)+dv?(y)}

$mi{n}_v$是对于x的所有邻居的。
从x到v遍历后，接下来取v到y的最低开销路径，则该路径开销是$c(x,v)+d_v(y)$。
必须通过遍历某些邻居v开始，从x到y的最低开销是对所有邻居ｖ的$c(x,v)+d_v(y)$的最小值。

基本思想如下：
每个节点x以$D_x(y)$开始，对N中的所有节点y，估计从x到y的最低开销路径的开销。
令$D_x=[D_x(y):y\in N]$是节点x的距离向量，该向量是从x到在N中的所有其他节点y的开销估计向量。

使用DV算法，每个节点x维护下列路由选择信息：

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

在该分布式，异步算法中，每个节点不时地向它的每个邻居发生它的距离向量副本。
当节点ｘ从它的任何一个邻居ｖ接收到一个新距离向量，它保存ｖ的距离向量，然后使用Bellman-Ford方程更新自己的距离向量如下：
D x ( y ) = m i n v { c ( x , v ) + D v ( y ) } D_{x}(y)=min_{v}\{c(x,v) + D_{v}(y)\} Dx?(y)=minv?{c(x,v)+Dv?(y)}

如果节点x的距离向量因更新而改变，节点ｘ接下来向它的每个邻居发送其更新后的距离向量，这继而让所有邻居更新它们自己的距离向量。

只要所有节点继续以异步方式交换它们的距离向量，每个开销估计$D_x(y)$收敛到$d_x(y)$，$d_x(y)$为从节点x到节点y的实际最低开销路径的开销。

LS算法是一种全局算法，在于它要求每个节点在运行Dijkstra算法之前，首先获得该网络的完整信息。

DV算法是分布式的，不使用这样的全局信息。
节点具有的唯一信息是它到直接相连邻居的链路开销和它从这些邻居接收到的消息。

下图说明了DV算法的运行，应用场合是该图顶部有三个节点的简单网络。
算法的运行以同步的方式显示出来，其中所有节点同时从其邻居接收报文，计算其新距离向量，如果距离向量发生了变化则通知其邻居。

从邻居接收更新距离向量、重新计算路由选择表项和通过邻居到目的地的最低开销路径的开销已经变化的过程继续下去，直到无更新报文发送。

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

当一个运行DV算法的节点检测到从它自己到邻居的链路开销变化时，就更新其距离向量，并且如最低开销路径发生了变化，向邻居通知其新的距离向量。

这里只关注ｙ与ｚ到目的地ｘ的距离表中有关表项。
该DV算法导致下列事件序列出现：

• t0时刻，ｙ检测到链路开销变化（开销从4变为1），更新其距离向量，通知其邻居这个变化，因为最低开销路径的开销已改变。
• t1时刻，ｚ收到来自ｙ的更新报文并更新了其距离表。计算出到x的新最低开销（从开销5减为开销2），它向其邻居发送它的新距离向量。
• t2时刻，ｙ收到来自ｚ的更新并更新其距离表。ｙ的最低开销未变，因此ｙ不发送任何报文给ｚ。算法进入静止状态。

现考虑某链路开销增加时发生的情况。
假设ｘ与ｙ间链路开销从４增加到 60,。

• 1） 在链路开销变化前，$D_y(x)=4，D_y(z)=1，D_z(x)=5$。在t0时刻，ｙ检测到链路开销变化（开销从4变为60）。ｙ计算它到ｘ的新的最低开销路径的开销，其值为
  D y ( x ) = m i n { c ( x , y ) + D x ( x ) , c ( y , z ) + D z ( x ) } = m i n { 60 + 0 , 1 + 5 } = 6 D_{y}(x)=min\{c(x,y)+D_x(x), c(y,z)+D_z(x)\}=min\{60+0, 1+5\}=6 Dy?(x)=min{c(x,y)+Dx?(x),c(y,z)+Dz?(x)}=min{60+0,1+5}=6

到了t1时刻，我们遇到路由选择环路，即为到达ｘ，ｙ通过ｚ路由，ｚ又通过ｙ路由。
路由选择环路就像一个黑洞，即目的地为ｘ的分组在t1时刻到达ｙ或ｚ后，将在这两个节点间不停地来回反复。

• 2）因为节点ｙ已算出到ｘ的新的最低开销，它在t1时刻，将该新距离向量通知ｚ。
• 3）在t1后某个时刻，ｚ收到ｙ的新距离向量，它指示了y到x的最低开销是6。
  ｚ计算出到ｘ的最低开销为 $D_z(x)=min50+0,1+6=7$。
  因为ｚ到ｘ的最低开销增加了，于是它在t2时刻通知ｙ其最新开销。
• 4）类似方式，收到ｚ新距离向量后，继续这样过程，并在多次后达到静止。

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

刚才描述的特定循环场景可通过使用称为毒性逆转的技术来避免。
思想为：
如果ｚ通过ｙ路由选择到目的地ｘ，则ｚ将通告ｙ，它（即ｚ）到ｘ的距离是无穷大。
只要ｚ经ｙ路由选择到ｘ，ｚ就持续地向ｙ讲述这个善意的谎言。
因为ｙ相信ｚ没有到ｘ的路径，故只要ｚ继续经ｙ路由到ｘ，ｙ将永远不会试图经过ｚ路由到ｘ。

作为毒性逆转的结果，ｙ的距离表指示了$D_z(x)=\infty$。
当(x,y)链路的开销在t0时刻从４变为60时，ｙ更新其表，虽然开销高达60，仍继续直接路由选择到x，并将到x的新开销通知z，即$D_y(x)=60$。

ｚ在t1时刻收到更新后，便立即将其到ｘ的路由切换到经过开销为50的直接 (z,x) 链路。
这是一条新的到ｘ的最低开销路径，且路径不再经过ｙ，ｚ就在t2时刻通知ｙ现在$D_z(x)=50$。
在收到来自ｚ的更新后，ｙ便用$D_y(x)=51$更新其距离表。
ｚ此时位于ｙ到ｘ的最低开销路径上，所以ｙ在t3时刻通知ｚ其$D_y(x)=\infty$（即使y实际上知道 $D_y(x)=51$）毒化从ｚ到ｘ的逆向路径。

涉及３个或更多节点的环路，无法用毒性逆转检测到。

3. LS与DV路由选择算法比较

在DV算法中，每个节点仅与它的直接相连的邻居交谈，但它为其邻居提供了从它自己到网络中（它所知道的）所有其他节点的最低开销估计。

LS算法需要全局信息。

当在每台路由器中实现时，每个节点（经广播）与所有其他节点通信，但仅告诉它们与它直接相连链路的开销。

Ｎ是节点（路由器）的集合，Ｅ是边（链路）的集合。

• 报文复杂性
  LS算法要求每个节点都知道网络中每条链路的开销。
  这要求发送$O(|N||E|)$个报文.
  无论何时一条链路开销改变时，必须向所有节点发送新的链路开销。
  DV算法要求在每次迭代时，在两个直接相连邻居间交换报文。
  算法收敛所需时间依赖许多因素。
  当链路开销改变时，DV算法仅当新的链路开销导致最低开销路径发生改变时，才传播已改变的链路开销。
• 收敛速度
  LS算法的实现是一个要求$O(|N||E|)$个报文的$O(|N{|}^2)$算法。
  DV算法收敛较慢，且在收敛时会遇到路由选择环路。
  DV算法还会遭遇无穷计数问题。
• 健壮性
  对于LS算法，路由器能向其连接的链路（而不是其他链路）广播不正确开销。
  一个节点可损坏或丢弃它收到的任何LS广播分组。
  一个LS节点仅计算自己的转发表；其他节点自行作类似计算。
  LS下路由计算是分离的，有一定健壮性。
  DV算法下，一个节点可向任意或所有目的节点通告其不正确的最低开销路径。
  每次迭代时，DV算法中一个节点的计算会传递给它的邻居，然后在下次迭代时，在简介传递给邻居的邻居。
  此时，DV下一个不正确的节点计算值会扩散到整个网络。

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

从所有路由器执行相同的路由选择算法以计算穿越整个网络的路由选择路径意义说，一台路由器很难同另一台区别。
在实践中，该模型和这种一组执行同样路由选择算法的同质路由器集合的观点有一点简单化，有以下两个重要原因：

• 规模
  随着路由器数目变得很大，涉及路由选择信息的通信，计算，存储的开销将高的不可实现。
  在大量路由器中迭代的距离向量算法将永远无法收敛，在大量路由器环境下、LS算法要求巨大存储空间和计算时间。
  需采取一些措施，减少像因特网这种大型网络中路由计算的复杂性。
• 管理自治
  因特网是ISP网络，其中每个ISP都有自己的路由器网络。
  ISP常希望按自己的意愿运行路由器（如在自己的网络中运行它所选择的某种路由选择算法），或对外部隐藏其网络的内部组织面貌。
  理想情况下，一个组织应当能够按自己的愿望运行和管理其网络，还要能将其网络与其他外部网络连接起来。

上述两个问题，可通过将路由器组织进自治系统（Autonomous System , AS）来解决，其中每个AS由一组通常处在相同管理控制下的路由器组成。
通常在一个ISP中的路由器及互联它们的链路构成一个AS。
某些ISP将它们的网络划分为多个AS。
特别是，某些一级ISP 在其整个网络中使用一个庞大的AS，而其他ISP则将它们的ISP拆分为数十个互联的AS。
一个自治系统由其全局唯一的AS号（ASN）所标识。
像IP地址那样，AS号由ICANN区域注册机构所分配。

在相同AS中的路由器都运行相同的路由选择算法且有彼此的信息。
在一个自治系统内运行的路由选择算法叫作自治系统内部路由选择协议（intra-autonomous system routing protocol）。

开放最短路优先［OSPF］

OSPF路由选择及其关系密切的协议IS-IS都被广泛用于因特网的AS内部路由选择。
OSPF中的开放一词指路由选择协议规范是公众可用的。
OSPF的最新版本为２，由[RFC 2328]公用文档所定义。

OSPF是一种链路状态协议，它使用洪泛链路状态信息和Dijkstra最低开销路径算法。
使用OSPF，一台路由器构建了一幅关于整个自治系统的完整拓扑图（即一幅图）。
每台路由器在本地运行Dijkstra的最短路径算法，以确定一个以自身为根节点，到所有子网的最短路径树。
各条链路开销是由网络管理员配置的。
管理员也许会选择将所有链路开销设为１，因而实现最少跳数路由选择，或者可能会选择将链路权值按与链路容量成反比来设置，从而不鼓励流量使用低带宽链路。
OSPF不强制使用设置链路权值的策略，而是提供了一种机制（协议），为给定链路权值集合确定最低开销路径的路由选择。

使用OSPF时，路由器向自治系统内所有其他路由器广播路由选择信息，而不仅是向其相邻路由器广播。
每当一条链路的状态发生变化时，（如开销的变化或连接／中断状态的变化），路由器会广播链路状态信息。
即使链路状态还未发生变化，它也要周期性地广播链路状态。
OSPF通告包含在OSPF报文中，该OSPF报文直接由IP承载，对OSPF其上层协议的值为89。
OSPF协议必须自己实现诸如可靠报文传输，链路状态广播等功能。
OSPF协议还要检查链路正在运行（通过向相连的邻居发送HELLO报文），并允许OSPF路由器获得相邻路由器的网络范围链路状态的数据库。

OSPF的优点：

• 安全
  能鉴别OSPF路由器之间的交换（如链路状态更新）。
  使用鉴别，仅有受信任的路由器能参与一个AS内的OSPF协议，因此可防止恶意入侵者，将不正确的信息注入路由器表内。
  在默认状态下，路由器间的OSPF报文是未被鉴别的并能被伪造。
  能够配置两类鉴别，即简单的和MD5的。
  使用简单的鉴别，每台路由器配置相同的口令。
  当一台路由器发送一个OSPF分组，它以明文方式包括了口令。
  简单鉴别并不是非常安全。
  MD5鉴别基于配置在所有路由器上的共享秘密秘钥。
  对发送的每个OSPF分组，路由器对附加了秘密秘钥的OSPF分组内容计算MD5散列值。
  然后，路由器将所得的散列值包括在该OSPF分组中。
  接收路由器使用预配置的秘密秘钥计算出该分组的MD5散列值，并与该分组携带的散列值比较，从而验证分组真实性。
• 多条相同开销的路径
  当到达某目的地的多条路径有相同的开销时，OSPF允许使用多条路径（即，当存在多条相等开销的路径时，无须仅选择单一的路径来承载所有的流量）。
• 对单播与多播路由选择的综合支持
  多播OSPF提供对OSPF的简单扩展，以便提供多播路由选择。
  MOSPF使用现有的OSPF链路数据库，并为现有的OSPF链路广播机制增加了一种新型的链路状态通告。
• 支持在单个AS中的层次结构
  一个OSPF自治系统能层次化地配置多个区域。
  每个区域都运行自己的OSPF链路状态路由选择算法，区域内的每台路由器都向该区域内的所有其他路由器广播其链路状态。
  每个区域内，一台或多台区域边界路由负责为流向该区域外的分组提供路由选择。
  在AS中只有一个OSPF区域配置为主干区域。
  主干区域的主要作用是为该AS中其他区域间的流量提供路由选择。
  主干总是包含本AS中的所有区域边界路由器，且可能还包含了一些非边界路由器。
  在AS中的区域间路由选择要求分组先路由到一个区域边界路由器（区域内路由选择），再通过主干路由到位于目的区域的区域边界路由器，进而再路由到最终目的地。

ISP之间的路由选择：BGP

OSPF是一个AS内部路由选择协议。
在相同AS内的源和目的间进行分组选路时，分组遵循的路径完全由AS内路由选择协议决定。
分组跨越多个AS进行路由时，需要一个自治系统间路由选择协议。
AS通信必须运行相同的AS间路由选择协议。
因特网中，所有AS运行相同的AS间路由选择协议，称为边界网关协议（Broder Gateway Protocol, BGP）。
这个协议将因特网中ISP粘合起来。
BGP是一种分布式和异步的协议。

BGP的作用

考虑一个AS和在AS中的任意一个路由器。
每台路由器有一张转发表，该转发表在将到达分组转发到出路由器链路的过程中起着主要作用。
对于位于相同AS中的目的地而言，在路由器转发表中的表项由AS内部路由选择协议决定。
而对于位于该AS外部的目的地而言，依赖BGP。

在BGP中，分组不是路由到一个特定的目的地址，相反是路由到CIDR化的前缀，其中每个前缀表示一个子网或一个子网的集合。
在BGP的世界中，一个目的地可采用138.16.68/22的形式，对于这个例子包含1024个IP地址。
一台路由器的转发表将具有形式为 (x, I) 的表项，其中ｘ是一个前缀（例如，138.16.68/22），I 是该路由器的接口之一的接口号。

作为一种AS间路由选择协议，BGP为每台路由器提供了一种完成以下任务的手段：

• 从邻居AS获得前缀的可达性信息
  BGP允许每个子网向因特网其余部分通告它的存在。
  BGP确保因特网所有AS知道该子网。
• 确定到该前缀的“最好的”路由
  路由器将本地运行一个BGP路由选择过程。
  该最好的路由将基于策略及可达性信息来确定。

通告BGP路由信息

上图，AS3包括一个具有前缀ｘ的子网。
对于每个AS，每台路由器要么是一台网关路由器，要么是一台内部路由器。
网关路由器是一台位于AS边缘的路由器，它直接连接到在其他AS中的一台或多台路由器。
内部路由器仅连接在它自己AS中的主机和路由器。

考虑向上图中显示的所有路由器通告对于前缀ｘ的可达性信息。

首先，AS3向AS2发送一个BGP报文，告知ｘ存在且位于AS3中
将该报文表示为“AS3 x”。
然后，AS2向AS1发送一个BGP报文，告知ｘ存在且能先通过AS2然后进入AS3，进而到达ｘ；将该报文表示为“AS2 AS3 x”。

以这种方式，每个自治系统不仅知道ｘ的存在，且知道通向ｘ的自治系统的路径。

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

对于直接连接在不同AS中的网关路由器的每条链路而言，通常有一条eBGP连接。

每个AS中的路由器之间有多条iBGP连接。
上图显示了一个AS内部的每对路由器之间的一条BGP连接的通常配置，在每个AS内部产生了网状的TCP连接。
上图中，eBGP会话显示为长虚线，iBGP显示为短虚线。
iBGP连接并不总是与物理链路对应。

为传播可达性信息，使用了iBGP和eBGP会话。
再次考虑向AS1和AS2中的所有路由器通告前缀ｘ的可达性信息
这个过程中，网关路由器3a先向网关路由器2c发送一个eBGP报文AS3 x。
网关路由器去2c然后向AS2中的所有其他路由器（包括网关路由器2a）发送iBGP报文　AS3 x 。
网关路由器2a接下来向网关路由器1c发送一个eBGP报文　AS2 AS3 x 。
在这个过程完成后，在AS1和AS2中的每个路由器都知道了ｘ的存在且知道了通往ｘ的AS路径。

在真实的网络中，从某个给定的路由器到某个给定的目的地可能有多条不同的路径，每条通过了不同的AS序列。

确定最好的路由

因特网中的路由器常常接收到很多不同的可能路径的可达性信息。

一台路由器如何在这些路径间进行选择（且相应地配置它的转发表）呢？

当路由器通过BGP连接通过前缀时，它在前缀中包括一些BGP属性。
前缀及其属性称为路由。
两个较为重要的属性是AS-PATH和NEXT-HOP。
AS-PATH属性包含了通告已经通过的AS的列表。
为生成AS-PATH的值，当一个前缀通过某AS时，该AS将其ASN加入AS-PATH中的现有列表。

5-10中，从AS1到子网ｘ有两条路：
其中一条使用AS-PATH “AS2 AS3”；另一条使用AS-PATH “AS3”。
BGP路由器还使用AS-PATH属性来检测和防止通告环路。
如果一台路由器在路径列表中看到包含自己的AS，它将拒绝该通告。

在AS间和AS内部路由选择协议之间提供关键链路方面，NEXT-PATH属性具有敏感而重要的作用。
NEXT-HOP是AS-PATH起始的路由器接口的IP地址。

为深入理解，再次参考5-10。
对于从AS1通过AS2到ｘ的路由　AS2 AS3 x，其属性NEXT-HOP是路由器2a左边接口的IP地址。
对于从AS1绕过AS2到ｘ的路由AS3 x，其NEXT-HOP是路由器3d最左边接口的IP地址。
总的来说，AS1中的每台路由器都知道了到前缀ｘ的两台BGP路由：

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

每条BGP路由包含３个组件：NEXT-HOP、AS-PATH、目的前缀。

1. 热土豆路由选择

一个简单的BGP下路由选择算法，热土豆路由选择。
考虑5-10路由器1b。
这台路由器将学习到达前缀ｘ的两条BGP路由。
使用热土豆路由选择，（从所有可能的路由中）选择的路由到开始该路由的NEXT-HOP路由器具有最小开销。

在这个例中，路由器1b查阅它的AS内部路由选择信息，以找到通往NEXT-HOP路由器2a的最低开销AS内部路径，及通往NEXT-HOP路由器3d的最低开销AS间路径，进而选择这些最低开销路径中具有最低开销的那条。

当在转发表中增加AS向外前缀时，AS间路由选择协议（BGP）和AS内部路由选择协议（OSPF）都要用到。

2. 路由器选择算法

实践中，BGP使用了比热土豆更复杂但却结合了其特定的算法。

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

• 路由被指派一个本地偏好值作为其属性之一
  一条路由的本地偏好可能由该路由器设置或可能由在相同AS中的另一台路由器学习到。
  本地偏好属性是一种策略决定，完全取决于该AS的网络管理员。
  具有最高本地偏好值的路由将被选择。
• 从余下的路由中（所有都具有相同的最高本地偏好值）
  将选择具有最短AS-PATH的路由。
  如果该规则是路由选择的唯一规则，则BGP将使用距离向量算法决定路径，距离测度使用AS跳的跳数而非路由器跳的跳数。
• 从余下路由中（所有具有相同最高本地偏好值，相同AS-PATH长度），使用热土豆选择，选择最靠近NEXT-HOP路由器的路由。
• 如仍留下多条路由，路由器用BGP标识符选择路由
  BGP是因特网AS间路由选择事实上的标准。

IP任播

BGP还常用于实现任播服务，该服务常用于DNS中。

许多应用中，对下列情况感兴趣：

• 在许多分散的不同地理位置，替换不同服务器上的相同内容。
• 让每个用户从最靠近的服务器访问内容。
  例如，DNS能在遍及全世界的DNS服务器上复制DNS记录。
  当一个用户要访问该复制的内容，可将用户指向具有该复制内容的"最近的"服务器。

描述CDN可能使用IP任播的方式。
在IP任播配置阶段，CDN公司为它的多台服务器指派相同的IP地址，并且使用标准的BGP从这些服务器的每台来通告该IP地址。
某台BGP路由器收到对于该IP地址的多个路由器通告，它将这些通过处理为对相同物理位置提供不同的路径。

当配置其路由选择表时，每台路由器将本地化地使用BGP路由选择算法来挑选到该IP地址的"最好的"路由。
在这个初始BGP地址通告阶段后，CDN能进行其分发内容的主要任务。
当某客户请求视频时，CDN向该客户返回由地理上分散的服务器所使用的共同IP地址，而无论该客户位于何处。
当客户想向那个IP地址发送一个请求时，因特网路由器则向那个"最近的"服务器转发该请求分组，最近的服务器是由BGP路由选择算法所定义的。

实践中，CDN通常选择不使用IP任播，因为BGP路由选择变化能导致相同的TCP连接的不同分组到达Web服务器的不同实例。
但IP任播被DNS系统广泛用于将DNS请求指向最近的根DNS服务器。

路由选择策略

当某路由器选择到目的地的一条路由时，AS路由选择策略能胜过所有其他考虑。
在路由选择算法中，实际上首先根据本地偏好属性选择路由，本地偏好值由本地AS的策略所确定。
例：说明BGP路由选择策略的某些基本概念

假设自治系统W，X，Y是接入ISP，而A, B, C是主干提供商网络。
假设A, B, C直接向彼此发送流量，并向它们的客户网络提供全部的BGP信息。
所有进入一个接入ISP网络的流量必定是以该网络为目的地，所有离开一个接入ISP网络的流量必定源于该网络。
Ｗ，Ｙ是接入ISP。
X是一个多宿接入ISP（经由两个不同提供商连到网络的其余部分）。

Ｘ如何放在转发Ｂ与Ｃ之间的流量呢？
可通过控制ＢＧＰ路由的通告方式容易地实现。
Ｘ如（向其邻居Ｂ和Ｃ）通告它没有通信（除自身外）任何其他目的地路径，那么它将起到一个接入ISP的作用。
也就是说，即使Ｘ知道一条路径如ＸＣＹ到达Ｙ，也不会将其通告Ｂ。
由于Ｂ不知Ｘ有一条路径到Ｙ，Ｂ不会经由Ｘ转发目的为Ｙ的流量。

上述说明了如何使用一条选择的路由通告策略来实现客户／提供商路由选择关系。

下面关注一个提供商网络，比如自治系统B。
假定Ｂ已经从Ａ知道了Ａ有到Ｗ路径AW。
Ｂ能将ＡＷ安装到其路由信息库中。
Ｂ也想向它的客户Ｘ通告路径 BAW。
但，Ｂ应将路径ＢＡＷ通告给Ｃ吗？
如这样作，Ｃ可经由ＢＡＷ将流量引导到Ｗ。
如果Ａ，Ｂ和Ｃ都是主干提供商，而Ｂ也许觉得它不该承担在Ａ与Ｃ间传送流量的负担（和开销）。
Ｂ可能认为，确保Ｃ经过Ａ和Ｃ间的直接连接引导Ａ客户的来去流量是Ａ和Ｃ的工作（和开销）。
目前还没强制主干ISP间如何路由选择的官方标准。

商业运行的 ISP 们都遵从一个经验法则是：
任何穿越某 ISP 主干网的流量必须是其源或目的（或两者）位于该 ISP 的某个客户网络中。
各个对等协议通常是 ISP 双方进行协商，而且对外保密的。

拼装在一起：在因特网中呈现

假设你创建了一个有若干服务器的小型公司网络，包括一条描述公司产生和服务的公共Web服务器，一台从你的雇员获得他们的电子邮件报文的电子邮件服务器和一条DNS服务器。
你希望，全世界可访问你的Web站点。
你乐意你的雇员能向遍及世界的潜在客户发送和接收电子邮件。

首先要获得因特网连接，需与本地 ISP 签订合并并进行连接。
公司将有一台网关路由器，该路由器将与本地 ISP的一台路由器相连。
连接可是一条通过现有电话基础设施的DSL连接，一条到 ISP路由器的租用线，或第一章描述的其他接入解决方案之一。
你的本地 ISP将为你提供一个IP地址范围，如由256个地址组成的一个／24 地址范围。
一旦你有了自己的物理连接和 IP 地址范围，你将在该地址范围内分配 IP 地址：
一个给你的Web服务器，一个给你的电子邮件服务器，一个给你的DNS服务器，一个给你的网关路由器，并将其他 IP 地址分配给公司网络中的其他服务器和联网设备。

除与一个ISP签订合同外，还需与一个因特网注册机构签订合同，以便为你的公司获得一个域名。
你的公司还须呈现在DNS系统中。
外部世界将要联系你的DNS服务器以获得该服务器的IP地址，你还需为注册机构提供你的DNS服务器的IP地址。
注册机构在.com顶级域名服务器中为你的DNS服务器设置一个表项（域名和对应的IP地址）。
此后，任何知道你域名的用户将能经过DNS系统获得你DNS服务器的IP地址。

为使人们能发现你的Web服务器的 IP 地址，你需在你的ＤＮＳ服务器中包括一个将你的Web服务器的主机名映射到它的 IP 地址的表项。
还要为公司中其他公共可用的服务器设置类似的表项。
如此，Ａ要浏览你的Web服务器，DNS系统将联系你的DNS服务器，找到你的Web服务器的 IP 地址，将其给Ａ。
Ａ则能与你的Web服务器创建一个直接的TCP连接。

考虑，Ａ做下列事情发生的状况：
Ａ知道你的Web服务器的 IP 地址，她向该 IP 地址发送一个 IP 数据报。
该数据报将通过因特网进行路由，经历了许多不同的自治系统中的一系列路由器，最终到达你的Web服务器。
当任何一个路由器收到该数据报时，将去它的转发表中寻找一个表项来确定转发该数据报的外出端口。
每台路由器需知道你公司的/24前缀（或某些聚合项）。

一台路由器如何知道你公司的前缀呢？
它从BGP知道了该前缀。
你的公司与本地 ISP 签订合同且获得了分配的前缀（即一个地址范围），你的本地 ISP 将用BGP向与之连接的 ISP 通告你的前缀。
最终，所有因特网路由器得知了你的前缀（包括你的前缀的某个聚合项），因而能将数据报适当地转发到适当的Web和电子邮件服务器。

SDN 控制平面

SDN 控制平面，即控制分组在网络的SDN使能设备中转发的网络范围逻辑，以及这些设备和它们的服务的配置与管理。
将网络的转发设备称为“分组交换机”，因为能够根据网络层源／目的地址，链路层源／目的地址及运输层，网络层，链路层中分组首部字段做出转发决定。

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

• 基于流的转发
  SDN控制的交换机的转发工作，可基于运输层，网络层，或链路层首部中任意数量的首部字段值进行。
  SDN控制平面的工作是计算，管理和安装所有网络交换机中的流表项。
• 数据平面与控制平面分离
  数据平面由网络交换机组成，交换机是相对简单的设备，在其流表中执行＂匹配加动作＂的规则。
  控制平面由服务器及决定和管理交换机流表的软件组成。
• 网络控制功能：位于数据平面交换机外部
  SDN控制平面由软件实现。
  软件在服务器上执行，该服务器与网络交换机截然分开且远离。
  控制平面自身由两个组件组成：一个SDN控制器（或网络操作系统），以及若干网络控制应用程序。
  控制器维护准确的网络状态信息（如远程链路，交换机和主机的状态）；为运行在控制平面中的网络控制应用程序提供这些信息；提供方法，这些应用程序通过这些方法能监视，编程和控制下面的网络设备。
• 可编程的网络
  通过运行在控制平面的网络控制应用程序，网络是可编程的。
  这些应用程序代表了SDN控制平面的"智力"，使用由SDN控制器提供的 API 来定义和控制网络设备中的数据平面。
  例如：
  一个路由选择网络控制应用程序可决定源和目的地间的端到端路径（如使用由SDN控制器维护的节点状态和链路状态信息，执行Dijkstra算法）。
  另一个网络应用程序可执行访问控制，决定交换机阻挡那个分组。
  还有一个应用程序可执行服务器负载均衡的方式转发分组

SDN表示了一种意义重大的网络功能的"分类"，即数据平面交换机，SDN控制器，网络控制应用程序是分离实体，该实体可由不同的厂商和组织机构提供。

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

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

控制器功能可大体组织为３个层次，下图显示了一个通用SDN控制器的视图

• 通信层：SDN控制器和受控网络设备之间的通信
  如果SDN控制器要控制远程SDN使能的交换机，主机或其他设备的运行，需要一个协议来传送控制器与这些设备间的信息。
  设备必须能向控制器传递本地观察到的事件（例：一个报文指示一条附属链路已经激活或停止，一个设备刚加入网络，或一个心跳指示某设备已经启动和运行）。
  这些事件向SDN控制器提供该网络状态的最新视图。
  这个协议构成了控制器体系结构的最底层。
  控制器和受控设备间的通信跨越了一个接口，称为控制器的"南向"接口。
  OpenFlow是一种提供这种通信功能的特定协议。
• 网络范围状态管理层
  SDN控制平面的最终控制决定（配置所有交换机的流表，实现负载均衡，防火墙），将要求控制器具有有关网络的主机，链路，交换机和其他SDN控制设备的最新状态信息。
  交换机的流表含计数器，其值可由网络控制应用很好地使用。
  控制平面的终极目标是决定用于各种受控设备的流表，控制器可维护这些表的拷贝。
  这些信息构成了SDN控制器维护的网络范围"状态"的例子。
• 对网络控制应用程序层的接口
  控制器通过其"北向"接口与网络控制应用程序交互。
  该API允许网络控制应用程序在状态管理层之间读/写网络状态和流表。
  状态改变事件出现时，应用程序可注册进行通告。

SDN控制器被认为是“逻辑上集中” 的，即控制器可被外部视为　单一，整体的服务。
出于故障容忍，高可用性，性能等考虑，实践中，这些服务和用于保持状态信息的数据库一般通过分布式服务器集合实现。
服务器集合实现控制器功能时，必须考虑控制器的内部操作的语义。

如OpenDaylight和ONOS这类现代控制器，已经将注意力放在构建一种逻辑上集中但物理上分布的控制器平台。

OpenFlow协议，位于控制器的通信层。

OpenFlow 协议

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

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

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

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

• 流删除，通知控制器已删除一个流表项。
• 端口状态，向控制器通知端口状态的变化。
• 分组入，一个分组到达交换机端口且不能与任何流表项匹配，
  则这分组将被发送给控制器进行额外处理。
  匹配的分组也发给控制器，作为匹配时采取的一个动作。
  分组入用于将分组发给控制器。

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

SDN控制的交换机和SDN控制器间的交互。

Dijkstra算法实现在每台路由器中并且在所有网络路由器中洪泛链路状态更新：

• Dijkstra算法作为一个单独程序来执行，位于分组交换机外部。
• 分组交换机向SDN控制器发送链路更新，且不互相发送。

假设，交换机s1,s2间的链路断开；s1, s3, s4的入和出流转发规则受到影响。
假定，OpenFlow被用作通信层协议，控制平面只执行链路状态路由选择而不执行其他功能。

• 交换机s1经历了自己与s2间的链路故障，使用OpenFlow “端口状态”　报文向SDN控制器通报该链路状态的更新。
• SDN控制器接收指示链路状态更新的OpenFlow报文，并且通告链路状态管理器，由管理器更新链路状态库。
• 实现Dijkstra链路状态路由选择的网络控制应用程序先前进行了注册，当链路状态更新时，将得到通告。
• 链路状态路由选择应用程序与链路状态管理器相互作用，以得到更新的链路状态；也参考状态管理层中的其他组件，计算新的最低开销路径。
• 链路状态路由选择应用则与流表管理器交互，流表管理器决定更新的流表。
• 流表管理器使用OpenFlow协议更新位于受影响的交换机s1,s2,s4的流表项。

上述图示了，SDN控制平面如何提供服务（网络层路由选择）。
SDN使能的ISP能容易地将最低开销路径的路由选择转变为更加定制的路由选择。
控制器可定制流表，只要改变应用控制软件。．
传统下，必须改变所有路由器中的软件。

SDN 的过去与未来

称之为网络功能虚拟化的通用SDN的目标是用简单的商用服务器，交换机和存储器来颠覆性地替代复杂的中间盒。

ICMP： 因特网控制报文协议

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

在某个位置，IP路由器不能找到一条通往HTTP请求中所指定的主机的路径，该路由器就会向你的主机生成并发出一个ICMP报文以指示该错误。
ICMP常被认为是 IP 一部分，从体系结构讲它位于 IP 之上，因为 ICMP报文承载在 IP 分组中。
也就是说， ICMP报文作为 IP 有效载荷承载的，像TCP与UDP报文段作为 IP 有效载荷被承载那样。

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

ping程序发送一个ICMP类型８编码０的报文到指定主机。
看到回显请求，目的主机发回一个类型０编码０的 ICMP回显应答。
客户程序需能指示操作系统产生一个类型８编码０的ICMP报文。

另一 ICMP报文是源抑制报文。
拥塞的路由器向一台主机发送一个 ICMP源抑制报文，使主机减小其发送速率。
TCP在运输层有自己的拥塞控制机制，不需要网络层反馈信息。

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

数据报的每个携带了一个具有不可达UDP端口号的UDP报文段。
第一个数据报的TTL为１，第二个的TTL为２，第三个的TTL为３，依次类推。
该源主机也为每个数据报启动定时器。
当第ｎ个数据报到达第ｎ台路由器时，第ｎ台路由器观察到这个数据报的TTL正好过期。

根据IP协议规则，
路由器丢弃该数据报并发送一个ICMP告警报文给源主机（类型11编码０）。
该告警报文包含了路由器的名字和它的IP地址。
该 ICMP报文返回源主机时，源主机从定时器得到往返时延，从 ICMP报文中得到第ｎ台路由器的名字与IP地址。

源主机为它发送的每个报文段的TTL字段加１。
这些数据报之一将最终沿着这条路到达目的主机。
因为该数据报包含了一个具有不可达端口号的UDP报文段，该目的主机将向源发送一个端口不可达的 ICMP报文（类型３编码３）。
源主机收到这个特别的 ICMP报文时，直到它不需再发送另外的探测分组。

以这种方式，源主机知道了位于它与目的主机间的路由器数量和标识，及两台主机间的往返时延。
Traceroute客户程序必须能指令操作系统产生具有特定TTL值的UDP数据报，当 ICMP报文到达时，也必须由它的操作系统进行通知。

IPv6 有其对应的 ICMP新版本。

网络管理和 SNMP

网络由许多复杂，交互的硬件和软件部分组成，既包括构成网络的物理部件的链路，交换机，路由器，主机和其他设备，也包括控制和协调这些设备的许多协议。
当一个机构将数以百计或千计的部件拼装在一起形成一个网络时，保持该网络运行良好对网络管理员是一种挑战。

SDN环境中逻辑上集中的控制器能有助于这种过程。
网络管理员使用丰富的网络管理工具和方法来监视，管理和控制该网络。

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

网络管理员在执行其任务中所使用的体系结构，协议和信息库。
其中故障标识，异常检测，满足约定的服务等级约定的网络设计／工程等主题会加以考虑。

网络管理框架

• 管理服务器
  一个应用程序，通常有人的参与，并运行在网络运营中心的集中式网络管理工作站上。
  管理服务器是执行网络管理活动的地方，控制网络管理信息的收集，处理，分析和／或显示。
• 被管设备是网络装备的一部分（包括它的软件），位于被管理的网络中。
  被管设备可是一台主机，路由器，交换机，中间盒，调制解调器，温度计，或其他联网的设备。
  在一个被管设备中，有几个被管对象。
  这些被管对象是被管设备中硬件的实际部分和用于这些硬件及软件组件的配置参数。
• 一个被管设备中的每个被管对象的关联信息收集在管理信息库中，将看到这些信息的值可供管理服务器所用（在许多场合下可被设置）。
  一个MIB对象可以是：一个计数器，例如由IP数据报首部差错而由路由器丢弃的IP数据报的数量，或一台主机接收到的UDP报文段的数量；
  运行在一台DNS服务器上的软件版本的描述性信息；
  一个特定设备功能是否正确的状态信息；
  到一个目的地的路由选择路径的特定协议的信息。
  MIB对象由称为SMI的数据描述语言所定义。
  用形式化语言可确保网络管理数据的语法和语义是定义良好和无二义性的。
• 每个被管设备中还驻留网络管理代理，是运行在被管设备中的一个进程，该进程与管理服务器通信，在管理服务器的命令和控制下在被管设备中采取本地动作。
• 网络管理框架的最后组件是网络管理协议
  该协议运行在管理服务器和被管设备间，允许管理服务器查询被管设备的状态，并经过其代理间接地在这些设备上采取行动。
  代理可用网络管理协议向管理服务器通知异常事件。
  网络管理协议自己不管理网络，而是为网络管理员提供了一种能力，使它们能管理网络。

简单网络管理协议

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

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

请求常用于查询，修改与某被管设备关联的MIB对象值。
SNMP第二个常被使用的是代理向管理服务器发送一种非请求报文，称为陷阱报文。
陷阱报文用于通知管理服务器，一个异常情况已经导致了MIB对象值的改变。

- GetRequest,GetNextRequest,GetBulkRequest都是管理服务器向代理发送的，以请求位于该代理所在的被管设备中的一个或多个MIB对象值。
其值被请求的MIB对象的对象标识符定义在该PDU的变量绑定部分。
GetRequest, GetNextRequest, GetBulkRequest的差异在于它们的数据请求粒度。
GetRequest能请求MIB值的任意集合；
多个GetNextRequest能用于顺序地读取MIB对象的列表或表格；
GetBulkRequest允许读取大块数据，能避免因发送多个GetRequest或GetNextRequest报文可能导致的额外开销。
代理用包括该对象标识符和它们相关值的Response PDU进行响应。

• 管理服务器使用SetRequest PDU来设置位于被管设备中的一个或多个MIB对象的值。
  代理用带有　noError 差错状态的　Response PDU 进行应答，以证实该值的确已被设置。
• 管理服务器使用 InformRequest PDU 来通知另一个MIB信息管理服务器，后者对于接收服务器是远程的。
• Response PDU常从被管设备发送给管理服务器，以响应来自该服务器的请求报文，返回所请求信息。
• SNMPv2 PUD的最后一种类型是陷阱报文。

学习参考资料：

《计算机网络——自顶向下方法》 第7版