路由选择

路由选择算法

路由选择算法(routing algorithm)：网络层软件的一部分，完成路由功能，为转发提供路线。

路由的原则：

  • 正确性(correctness)：算法必须是正确的和完整的。
  • 简单性(simplicity)：算法在计算机上应简单。
  • 健壮性(robustness)：算法应能适应通信量和网络拓扑的变化。
  • 稳定性(stability)：产生的路由不应该摇摆。
  • 公平性(fairness)：对每一个站点都公平。
  • 最优性(optimality)：某一个指标的最优，时间上，费用上，等指标，或综合指标。

LS路由的基本工作过程：

  1. 发现相邻节点,获知对方网络地址
  2. 测量到相邻节点的代价(延迟,开销)
  3. 组装一个LS分组，描述它到相邻节点的代价情况
  4. 将分组通过扩散的方法发到所有其它路由器
  5. 通过Dijkstra算法找出最短路径（这才是路由算法）

距离矢量路由选择(distance vector routing)

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

  • 各路由器维护一张路由表

    image-20230427100345726

  • 各路由器与相邻路由器交换路由表

  • 根据获得的路由信息,更新路由表

算法对比

  • 消息复杂度：DV更好
    • LS：局部的路由信息；全局传播。
    • DV：只和邻居交换信息，全局的路由信息，局部传播。
  • 收敛时间：LS更好
    • LS：O(n2) 算法。
    • DV：收敛较慢，可能存在路由环路。
  • 健壮性：LS更好
    • LS：错误信息影响较小，局部，路由较健壮
    • DV：DV 节点可能通告对全网所有节点的不正确路径代价。

子网自治系统内部的路由选择

RIP：

基于距离矢量算法的一种路由实现

步骤：

  • 每条链路cost=1，计算出邻居的跳数
  • DV每隔30秒和邻居交换DV，通告（每个通告包括：最多25个目标子网）
  • 最后计算出路由

OSPF：

基于链路状态算法的一种路由实现

步骤：

  • LS 分组在网络中（一个AS内部）分发
  • 全局网络拓扑、代价在每一个节点中都保持
  • 路由计算采用Dijkstra算法

ISP之间的路由选择

BGP：

自治区域间路由协议“事实上的”标准

平面路由的问题：

  • 规模巨大的网络中，路由信息的存储、传输和计算代价巨大
  • 管理问题：
    • 不同的网络所有者希望按照自己的方式管理网络
    • 希望对外隐藏自己网络的细节

BGP将互联网分成一个个AS(路由器区域)，解决了平面路由的问题。

BGP 提供给每个AS以以下方法：

  • eBGP: 从相邻的ASes那里获得子网可达信息
  • iBGP: 将获得的子网可达信息传遍到AS内部的所有路由器
  • 根据子网可达信息和策略来决定到达子网的“好”路径