CN5.2 传统路由选择算法

Section 5 网络层：控制平面

中科大郑烇、杨坚老师《计算机网络》笔记

5.2 传统路由选择算法

• 路由概念
  • 在一个网络中找一条较好的路径Path
  • 以子网为单位进行扩散，是子网（路由器）到子网（路由器）的路由
    • 第一跳和最后一跳是毫无疑问的
  • 指标：跳数、延迟、费用、队列长度，或一些指标的加权平均
• 路由问题的抽象：图
  • G=(N,E)
  • N：路由器（路由器所在的子网）集合
  • E：点到点的链路
  • 输入：source、dest、weight（跳数、时间、拥塞程度、费用等）
  • 最优化原则：所有路由器找到（路由）并使用（转发）汇集树 sink tree
• 路由的原则：正确、简单、健壮、稳定、公平、次优性
• 路由算法的分类
  • 全局：
    • 所有路由器都拥有完整的拓扑和边的代价信息
    • Link state 算法
  • 局部（分布式）：
    • 路由器只知道邻居路由和到邻居的代价
    • Distance vector算法
  • 静态/动态
    • 动态：周期性更新迭代，反应网络拓扑变化，自适应
• Link State Routing 链路状态算法
  • 获得网络拓扑和链路代价信息
    • 链路状态分组：路由器及其邻居的信息，和该路由器到邻居的代价
    • 泛洪flooding：
      • 减少广播风暴（年龄age字段和版本号）
      • 可靠泛洪，需要路由器确认
  • 使用最短路由算法得到路由表（Dijkstra算法，复杂度N^2，可能存在震荡）
  • 使用其路由表
  • LS应用：OSPF、IS-IS
• Distance Vector Routing 距离矢量算法（Bellman-Fold方程，动态规划）
  • 基本思想
    • 各个路由器维护一张路由表：To | Next | Cost
    • 各个路由器与相邻路由器交换路由表
    • 根据获得的路由信息，更新路由表
  • 定期测量、定期交换、更新路由表
  • 经过若干次的迭代，最终会收敛到最优值
  • 特点：好消息传得快、坏消息传得慢（可能形成环路）
    • 水平分裂（split horizon）：减缓坏消息传得慢的问题（存在环状拓扑的网络不适用）
      • 当B是C到A的下一跳的时候，C传给B的信息是“A不可达”，而传给其他节点的信息是真实信息（C发出的信息水平分裂为了两种情况）
  • 触发：分布式、异步算法
    • 本地链路代价变化了
    • 从邻居节点来了DV更新消息
• LS和DV的比较
  • 消息复杂度（DV胜出）
    • LS：有 n节点, E条链路，报文O(nE)个（局部的路由信息；全局传播）
    • DV:只和邻居交换信息（全局的路由信息，局部传播）
  • 收敛时间（LS胜出）
    • LS：O(n2)算法，有可能震荡
    • DV：收敛较慢，可能存在路由环路
  • 健壮性：某一个路由器故障会发生什么（LS胜出）
    • LS：节点会通告不正确的链路代价，每个节点只计算自己的路由表，错误信息影响较小、局部
    • DV：DV节点可能通告对全网所有节点的不正确路径代价，每一个节点的路由表可能被其它节点使用（错误可以扩散到全网）