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节点可能通告对全网所有节点的不正确路径代价，每一个节点的路由表可能被其它节点使用（错误可以扩散到全网）