本章目标：理解网络层控制平面的工作原理
传统路由选择算法
SDN控制器
ICMP: Internet Control Message Protocol
网络管理(略)
以及它们在互联网上的实例和实现OSPF, BGP, Openflow, 0DL和ONOS控制器, ICMP, SNMP

5.1 导论

回顾：
2个网络层的功能：
转发：将分组从路由器的一个输入端口移到合适的输出端口———数据平面
路由：确定分组从源到目标的路径———控制平面

2中构建网络控制平面的方法：
每个路由器控制功能实现（传统）
逻辑上集中的控制功能实现（software defined networking）

5.2 路由选择算法

网络层的路由可以看作是子网到子网的路由，主机到主机的路由工作量太大了。

路由协议
路由协议的目标:确定从发送主机到接收主机之间,通过路由器的网络“较好”的路径(等价于路由器的序列)

• 路径：路由器的序列，分组将会沿着该序列从源主机到达最后的目标主机
• “较好”：最小“代价”,“最快的”,“最不拥塞”
• 路由：一个“top-10”网络挑战!

路由（route）的概念

• 路由:按照某种指标(传输延迟，所经过的站点数目等)找到一条从源节点到目标节点的较好路径
  • 较好路径:按照某种指标较小的路径
  • 指标:站数,延迟,费用,队列长度等,或者是一些单纯指标的加权平均
  • 采用什么样的指标,表示网络使用者希望网络在什么方面表现突出,什么指标网络使用者比较重视口
• 路由器-路由器之间的最优路径=主机对之间的最优路径
  • 路由器连接子网,子网到路由器之间的跳数就一跳,必须要走
  • 路由器到下一跳路由器(节点到节点)之间的最优路径找到了，也就找到了从源子网向目标子网所有主机对之间的最优路，大大降低了路由计算的规模
  • 在路由计算中按照子网到子网的路径计算为目标,而不是主机到主机
• 路由选择算法(routing algorithm)：网络层软件的一部分,完成路由功能

路由选择算法的原则

• 正确性(correctness)：算法必须是正确的和完整的，使分组一站一站接力，正确发向目标站；完整:目标所有的站地址，在路由表中都能找到相应的表项，没有处理不了的目标站地址。
• 简单性(simplicity)：算法在计算机上应简单，最优但复杂的算法时间上延迟很大，不实用，不应为了获取路由信息增加很多的通信量。
• 健壮性(robustness)：算法应能适应通信量和网络拓扑的变化；通信量变化，网络拓扑的变化算法能很快适应；不向很拥挤的链路发数据，不向断了的链路发送数据。
• 稳定性(stability)：产生的路由不应该摇摆
• 公平性(fairness)：对每一个站点都公平
• 最优性(optimality)：某一个指标的最优，时间上，费用上，等指标，或综合指标：实际上获取最优的结果代价较高，可以是次优的

路由算法分类

全局或者局部路由信息?
全局：

• 所有的路由器拥有完整的拓扑和边的代价的信息
• “ link state”算法

分布式：

• 路由器只知道与它有物理连接关系的邻居路由器,和到相应邻居路由器的代价值
• 叠代地与邻居交换路由信息计算路由信息
• “ distance vector”算法

静态或者动态的?
静态：

• 路由随时间变化缓慢

动态

• 路由变化很快
• 周期性更新
• 根据链路代价的变化而变化

静态：非自适应算法( non-adaptive algorithm)，不能适应网络拓扑和通信量的变化，路由表是事先计算好的。
动态：自适应路由选择( adaptive algorithm)，能适应网络拓扑和通信量的变化。

链路状态路由选择 link state routing

LS路由的基本工作过程：

1. 发现相邻节点,获知对方网络地址
2. 测量到相邻节点的代价(延迟,开销)
3. 组装一个LS分组,描述它到相邻节点的代价情况
4. 将分组通过扩散的方法发到所有其它路由器
   • 以上4步让每个路由器获得拓扑和边代价
5. 通过 Dijkstra算法找出最短路径(这才是路由算法)
   • 每个节点独立算出来到其他节点(路由器=网络)的短路径
   • 选代算法:第k步能够知道本节点到k个其他节点的最短路径

链路状态分组通过泛洪散播路由信息

LS路由选择算法的工作原理
节点标记：每一个节点使用(D(v),p(v))，如：(3,B)来标记

• D(v)从源节点由已知最优路径到达本节点的距离
• P(v)前序节点来标注

2类节点
临时节点(tentative node)：还没有找到从源节点到此节点的最优路径的节点
永久节点(permanent node)N’：已经找到了从源节点到此节点的最优路径的节点

Dijkstra算法

1. 初始化
   • 除了源节点外,所有节点都为临时节点
   • 节点代价除了与源节点代价相邻的节点外,都为∞
2. 从所有临时节点中找到一个节点代价最小的临时节点，将之变成永久节点(当前节点)W
3. 对此节点的所有在临时节点集合中的邻节点(V)
   • 如D(v)>D(w)+c(w,v),则重新标注此点,(D(W)+C(W,V),W)
   • 否则,不重新标注
4. 开始一个新的循环2-3

取永久节点的邻居，来不断更新临时节点的标记，直到遍历完获取代价最小的+前序，放到永久节点集和中。
要点：从所有临时节点中找到一个节点代价最小的临时节点，将之变成永久节点。
O(n^2)

可能的震荡：链路代价=链路承载的流量

距离矢量路由选择 distance vector routing

距离矢量路由选择的基本思想

• 各路由器维护一张路由表，结构如图（其他代价）
• 各路由器与相邻路由器交换路由表
• 根据获得的路由信息，更新路由表

代价及相邻节点间代价的获得

• 跳数(hops)、延迟(delay)，队列长度
• 相邻节点间代价的获得：通过实例

路由信息的更新：

• 根据实测，得到本节点A到相邻节点的代价（如：延迟）
• 根据各相邻节点声称它们到目标站点B的代价
• 计算出本站点A经过各相邻站点到目标站点B的代价
• 找到一个最小的代价，和相应的下一个节点Z，到达节点B经过此节点Z，并且代价为A-Z-B的代价

通过①定期测量它到相邻节点的代价②定期与相邻节点交换路由表(DV)来更新路由表

DV的无穷计算问题
DV的特点：好消息传得快，坏消息传得慢
好消息（比如：某个路由器接入或有更短的路径）的传播以每一个交换周期前进一个路由器的速度进行。

距离矢量算法
Bellman-Ford方程（动态规划）

核心思路：

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

每个节点不时地向它的每个邻居发送它的距离向量副本。当节点x从它的任何一个邻居v接收到一个新距离向量， 它保存v的距离向量， 然后使用Bellman-Ford方程更新它自己的距离向量。

LS算法是一种全局算法， 在于它要求每个节点在运行Dijkstra算法之前， 首先获得该网络的完整信息。 DV算法是分布式的（异步的）， 它不使用这样的全局信息。节点具有的唯一信息是它到直接相连邻居的链路开销和它从这些邻居接收到的信息。

关于坏消息传的很慢
原本 a-(1)-b-(1)-c-(1)-d-(1)-e
现在 a b-(1)-c-(1)-d-(1)-e 即a和b之间无法通信了，a可能坏掉了
原本c路由表中的信息：dest=a,next=b,cost=2
b现在更新自己的路由表，它从邻节点获取到c到a代价为2，那么b更新自己的路由表dest=a,next=c,cost=3，然后c又更新自己的路由表。反复无限次后，到a的距离变成INF，不可达。

要解决这个问题，采用水平分裂（split horizon）算法，书里面叫毒性逆转（p.253）
c知道要经过b才能到达a，所以c向b报告它到a的距离为INF，而c告诉d它到达a的真实代价。
这样坏消息以一次交换一个节点的速度传播

水平分裂在有环路的情况下不能杜绝“坏消息”传得慢的情况。
如下图，假设D之后坏掉了

原本路由表A中有dest=d,next=c,cost=2
原本路由表B中有dest=d,next=c,cost=2
现在c到d不可达，但是A、B表更新的时候可能会反复多次，才设置D为不可达

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

消息复杂度（DV胜出）
LS：有n节点，E条链路，发送报文O(nE)个；局部的路由信息，全局传播
DV：只和邻居交换信息；全局的路由信息，局部传播

收敛时间（LS胜出）
LS:O(n2)，有可能震荡
DV：收敛较慢，可能存在环路问题，count-to-infinity问题

健壮性：路由器故障会发生什么（LS胜出）
LS：节点会通告不正确的链路代价；每个节点只计算自己的路由表；错误信息影响较小，局部，路由较健壮
DV：DV节点可能通告对全网所有节点的不正确路径代价；由于一个节点的路由表可能被其他节点使用，错误可以扩散到全网。

5.3 自制系统内部的路由选择

两种常见的内部网关协议：RIP、OSPF

RIP Routing Information Protocol

采用距离矢量算法：

• 距离矢量：每条链路cost=1hop 1跳（max=15hops）大于15则不可达
• DV每隔30秒和邻居交换DV，通告；定期，而且在改变路由的时候发送通告报文；在对方的请求下可以发送通告报文。
• 每个通告包括：最多25个目标子网

RIP：链路失效和修复
如果180秒没有收到通告信息—>邻居或者链路失效

OSPF Open Shortest Path First

使用链路状态路由选择算法
IS-IS路由协议：几乎和OSPF一样

OSPF相比于RIP的优势：

• 安全:所有的OSPF报文都是经过认证的(防止恶意的攻击)
• 允许有多个代价相同的路径存在(在RIP协议中只有一个)
• 对于每一个链路,对于不同的TOS有多重代价矩阵
  • 例如:卫星链路代价对于尽力向为的服务代价设置比较低,对实时服务代价设置的比较高
  • 支持按照不同的代价计算最优路径,如:按照时间和延迟分别计算最优路径
• 对单播和多播的集成支持:
  • Multicast OSPF(MOSPF)使用相同的拓扑数据库就像在OSPF中一样
• 在大型网络中支持层次性O5PF

**TOS Type of Service 服务类型

层次化的OSPF路由

通过把一个自治区划分为若干个区域，就能够限制链路状态分组泛洪的状态和数量；如果是其他区域的机器，那么先路由到backbone，backbone路由到对应区域；如果是其他的自治区，那么先路由到boundary路由器，再路由到对应自治区区域。

5.4 ISP之间的路由选择：BGP

一个平面的路由

• 一个网络中所有的路由器的地位一样
• 通过LS，DV，或者其他路由算法，所有的路由器都要知道其他所有路由器（子网）如何走
• 所有路由器在一个平面

平面路由的问题

• 规模巨大的网络中，路由信息的存储、传输和计算代价巨大
  • DV：距离矢量很大，且不能够收敛
  • LS：几百万个节点的LS分组的泛洪传输，存储以及最短路径算法的计算
• 管理问题：
  • 不同的网络所有者希望按照自己的方式管理网络
  • 希望对外隐藏自己网络的细节的同时还能够和其他网络互联

层次路由

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

• 某个区域内的路由器集合,自治系统”autonomous systems”(AS)
• 一个AS用 AS Number(ASN)唯一标示
• 一个ISP可能包括1个或者多个AS

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

• AS内部路由:在同一个AS内,路由器运行相同的路由协议
  • “intra-AS” routing protocol 内部网关协议
  • 不同的AS可能运行着不同的内部关协议
  • 能够解决规模和管理问题如: RIP OSPF IGRP
  • 网关路由器:AS边缘路由器，可以连接到其他AS
• AS间运行AS间路由协议
  • “inter-AS” routing protocol外部网关协议
  • 解决AS之间的路由问题，完成AS之间的互联互通

按照物理区域分区，每个自治区内可以选择自己的路由选择协议，因为路由器和子网的数量都有限，哪种路由选择算法都能满足需求。
外部网关协议解决的自治区之间的可达性。
既满足了管理上的诉求，也满足了安全方面的诉求，还能解决规模上的问题（一个自治区内的若干子网、路由器都被看作了一个点）。

互联网AS间路由：BGP

Border Gateway Protocol自治区域间路由协议”事实上的”标准，将互联网各个AS粘在一起的胶水。

• eBGP：从相邻的AS那里获取子网可达信息
• iBGP：将获得的子网可达信息传遍到AS内部的所有路由器

根据子网可达信息和策略来决定到达子网的最优路径。
使用优化的距离矢量算法，不仅仅提供到达某一子网的代价，还提供详细路径。

iBGP之间可以没有直接连接的物理链路，只有TCP连接，是逻辑上的邻居，通过内部网关协议来进行路由。交流内部子网可达信息。
IGP（内部网关协议）是在一个自治网络内网关（主机和路由器）间交换路由信息的协议。

热土豆路由

2d通过iBGP获知，它可以通过2a或者2c到达3c
热土豆策略：选择具备最小内部区域代价的网关作为往dest的出口（如：2d选择2a），不关心域间的代价。

BGP：通过路径通告执行策略

假设一个ISP只想路由流量到/去往它的客户(不想承载其他ISPs之的流量,即不通告,不是去往我的客戶,也不来自我的客戶)
A向B和C通告路径Aw
B选择不向C通告BAw：
B从CBAw的路由上无法获得收益,因为CAw都不是B的客戶
C从而无法获知CBAw路径的存在:每个ISP感知到的网络和真实不一致
C可能会通过CAw(而不是使用B)最终路由到w

为什么内部网关协议和外部网关协议策略不同？
内部网关协议在一个自治区内部使用的，网络的所有资源（包括链路、主机计算资源）要为内部用户提供服务。所以关注性能。
外部网关是自治区之间的路由。例如，不一定会选择性能最好的路径，需要控制谁要经过我的流量、我的区域来通信，关注政治策略、经济策略。

5.5 SDN控制平面

传统方式：per-router控制平面
在每一个路由器中的单独路由器算法元件，在控制平面进行交互
SDN方式：逻辑上集中的控制平面
一个不同的（通常是远程的）控制器与本地控制器代理（CAs）交互

4个关键特征

1. 基于流的转发
2. 数据平面与控制平面分离
3. 网络控制功能
4. 可编程的网络

5.6 ICMP 因特网控制报文协议

telnet
traceroute

第5章总结

• 网络层控制平面的方法：
  • 每个路由器控制（传统方法）
  • 逻辑上集中的控制（software defined networking）
• 传统路由算法：
  • 在互联网上实现：RIP，OSPF, BGP
• SDN控制器
  • 实际中的实现：ODL，ONOS
• Internet Control Message Protocol
• 网络管理和SNMP协议