[数据结构与算法]路由选择算法

1.路由选择算法

1.1 路由算法

• 之前主要研究了网络层的转发功能，当分组到达一台路由器时，该路由器索引其转发表并决定该分组被指向的链路接口
• 网络层还有至关重要的路由选择功能，不管网络层提供的是数据报服务(此时在给定源和目的地址之间的不同分组可能采用不同的路由) ，还是虚电路服务此时在给定源和目的地址之间的所有分组将采用相同路径) ，网络层都必须为分组选择一条最佳路径。
• 主机通常直接与一台路由器相连接，该路由器即为该主机的默认路由器 (default router)?, 又称为该主机的第一跳路由器 (first- hop router)
• 将源主机的默认路由器称作源路由器( source router)?，把目的主机的默认路由器称作目的路由器 (destination router)
• 可以用图、边、节点（离散数学）来形式化描述路由选择问题。
• 路由算法的分类一
  • 全局式路由选择算法 (global routing algorithm)
    • 所有的路由器掌握完整的网络拓扑和链路费用信息
    • 实践中，具有全局状态信息的算法常被称作链路状态 (Link State , LS) 算法，因为该算法必须知道网络中每条链路的费用
  • 分散式路由选择算法 (decentralized routing algorithm)
    • 路由器只掌握物理相连的邻居及链路费用
    • 以迭代、分布式的方式计算出最低费用路径
    • 例如，距离向量( Distance- Vector, DV) 算法
• 路由算法的分类二
  • 静态路由选择算法 (Static routing algorithm)
    • 人工干预进行调整(如人为手工编辑一台路由器的转发表)
  • 动态路由选择算法 (Dynamic routing algorithm)
    • 能够当网络流量负载或拓扑发生变化时动态改变路由选择路径
• 路由算法的分类三
  • 负载敏感算法 ( load-sensitive algorithm)
    • 链路费用会动态地变化以反映出底层链路的当前拥塞水平
    • 早期的 ARPAnet 路由选择算法就是负载敏感的
  • 当今的因特网路由选择算法都是负载迟钝的 (load-insensitive) ，因为某条链路的费用不明思地反映其当前(或最近)的拥塞水平。

1.2 链路状态路由算法

• 在链路状态算法中，网络拓扑和所有的链路费用都是已知的，也就是说可用作 LS 算法的输入
• 实践中这是通过让每个结点向网络中所有其他结点广播链路状态分组来完成的，其中每个链路状态分组包含它所连接的链路的特征和费用
• 链路状态路由选择算法叫做?Dijkstra 算法（数据结构与算法，具体略）
• 复杂性：n 个节点需要 n(n+1)/2 次比较，O(n^2)
• 存在震荡可能

1.3 距离向量路由算法

• 距离向量算法是一种迭代的、异步的和分布式的算法
  • 分布式：每个结点都要从一个或多个直接相连邻居接收某些信息，执行计算，将其计算结果分发给邻居
  • 迭代：此过程一直要持续到邻居之间无更多信息要交换为止
  • 异步：不要求所有结点相互之间步伐一致地操作。
• 采用Bellman-Ford 算法（算法数据结构与算法，具体略）
• 无穷计数问题：采用毒性逆转技术或定义最大度量

1.4 LS vs DV ？

• 注：N 是结点(路由器)的集合，而 E 是边(链路)的集合
• DV 和 LS 算法采用互补的方法来解决路由选择计算问题
  • 在 DV 算法中
    • 每个结点仅与它的直接相连的邻居交谈
    • 它为其邻居提供了从它自己到网络中(它所知道的)所有其他结点的最低费用估计
  • 在 LS 算法中
    • 每个结点(经广播)与所有其他结点交谈
    • 它仅告诉它们与它直接相连链路的费用
• 报文复杂性
  • DV 算法
    • 要求在每次选代时，在两个直接相连邻 居之间交换报文
    • 当链路费用改变时， DV 算法仅当在新的链路费用导致与该链路相连结点的最低费用路径发生改变时，才传播己改变的链路费用
  • LS 算法
    • 要求每个结点都知道网络中每条链路的费用，这就要求要发送 O(NE）个报文
    • 无论何时一条链路的费用改变时，必须向所有结点发送新的链路费用
• 收敛速度
  • LS 算法的实现是一个要求O（NE) 个报文的 O( N^2 ) 算法。 DV 算法收敛较慢，且在收敛时会遇到路由选择环路，还有无穷计数的问题
• 健壮性： 如果一台路由器发生故障、行为错乱或受到破坏时情况会怎样呢?
  • DV 算法
    • 一个结点可向任意或所有目的结点通告其不正确的最低费用路径
    • 更一般地，每次迭代时，在 DV 算法中一个结点的计算会传递给它的邻居，然后在下次迭代时再间接地传递给邻居的邻居，一个不正确的结点计算值会扩散到整个网络
  • LS 算法
    • 对于 LS 算法，路由器能够向其连接的一条链路广播不正确费用(但是没有其他链路)
    • 一个结点也可损坏或丢弃它收到的任何 LS 广播分组
    • 但是一个 LS结点仅计算自己的转发表，这就意味着在 LS 算法下，路由计算在某种程度上是分离的，提供了一定程度的健壮性
• 总之，两个算法没有一个是明显的赢家，它们的确都在因特网中得到了应用

1.5 层次路由选择

• 将任意规模的网络抽象成图计算路由——过于理想化和简单化，原因如下：
  • 规模。随着路由器数目变大，涉及路由选择信息的计算、存储及通信的开销将高得不可实现。
  • 管理自治。每个网络的管理可能都期望自主控制其内网的路由，还要能将其网络与其他外部网络相连接。
• 这两个问题都可以通过将路由器组织进自治系统 (Autonomous System, AS)?来解决
  • 在相同的 AS 中的路由器都全部运行同样的路由选择算法，且拥有彼此的信息，就像理想化那样。
  • 在一个自治系统内运行的路由选择算法叫做自治系统内部路由选择协议( intra- autonomous system routing protocol)
  • 不同自治系统内的路由器可以运行不同的AS内部路由协议
  • 将 AS 彼此互联是必需的，因此在一个 AS 内的某些路由器还将负责向在本 AS 之外的目的地转发分组，这些路由器位于AS的 “边缘”，被称为网关路由器 (gateway router) 。
• 一个例子

• 

• AS1具有4台路由器，1a、1b、1c 和 1d，这4台路由器的每一台都知道如何沿着优化路径转发到 AS1 内任何目的地的分组地，自治系统 AS2 和 AS3 类似
• 路由器 1b、1c、2a 和 3a 都是网关路由器
• 某些 AS 中的路由器，怎样知道该如何将分组路由选择到位于该 AS 外部的目的地呢？
  • 如果 AS?仅有一个网关路由器连接唯一一个其他 AS?的话，回答这个问题是容易的。因为该 AS 内部的 AS 路由选择协议已经决定了从内部路由器到网关路由器的最低费用路径，网关路由器一旦接收到分组，将分组向通向外部 AS 的一条链路转发。之后由该链路另一端的 AS 负责将该分组向其最终目的地路由选择。
  • 如果源 AS 具有两条或更多条链路(通过一台或更多台网关路由器)通向外部 AS ，如何解决这个问题？
    • 考虑在 AS1 中的一台路由器，它接收了 一个目的地在该 AS 外部的分组。路由器显然应当向它的两个网关路由器之一(1b 或 1c) 转发该分组
    • 为解决选择哪个网关，AS1 需要:①知道经 AS2 和 AS3 分别可达哪些目的地；②向 AS1 中的所有路由器传播这些可达性信息
    • 以上两个任务是由自治系统间路由选择协议( Inter- autonomous system routing protocol)?处理的。事实上，因特网中的所有 AS 都运行相同的 AS 间路由选择协议，该协议称为?BGP4
    • 因此每台路由器能够配置它的转发表以处理外部 AS 目的地
• 假如 AS1 从 AS 间路由选择协议知道了子网 x 是可通过多个网关到达。如何选择？
  • 热土豆路由选择 (hot potato routing)：发送分组的路由器通过 AS 内部路由协议确定自己到达每个网关的最小路径，在这些路径中选择最小的一条，即选择离自己最近的网关发送。