1 路由选择算法

  • 路由：按照某种指标(传输延迟,所经过的站点数目等)找到一条从源节点到目标节点的较好路径

  • 以网络为单位进行路由（路由信息通告+路由计算）

    • 一个网络使用的节点地址前缀相同，且物理上聚集
    • 路由：计算一个网络到另一个网络的路径

  • 路由选择算法（routing algorithm）：网络层软件的一部分，完成路由功能

    • 从图中找到一棵

      汇集树（Sink Tree）

      • 此节点到其他节点的最优路径形成的树
      • 路由选择算法就是为所有路由器找到并使用汇集树

  • 配置LS路由选择算法

    • 通过各种渠道获得整个网络的拓扑，整个网络链路代价等信息
    • 使用LS路由算法计算本站点到其他站点的最优路径（汇集树），得到路由表
    • 按照路由表转发分组（datagram方式）

  • LS路由选择算法工作流程

    1. 发现相邻节点，获取对方网络地址

    2. 测量到相邻节点的代价（延迟、开销）

    3. 组装一个LS分组，描述它到相邻节点的代价情况

    4. 将分组通过扩散的方式发送到所有其他路由器

    5. 通过

      Dijkstra算法

      找出最短路径

      • 每个节点独立计算到其他节点的最短路径
      • 迭代算法：第K步知道本届点到K个其他节点的最短路径

  • 符号标记

    • c(i,j)：从节点i到节点j的链路代价（初始状态下非相邻节点之间代价为∞）
    • D(v)：从源节点到目标节点的当前路径代价（节点的代价）
    • P(v)：从源到节点V的路径前序节点（P(P(v))则表示的是前序的前序节点）
    • N’：当前已知最优路径的节点集合（永久节点集合）临时节点：没找到最优路径；永久节点：找到最优路径
  • 目标：找到A到所有节点的最优路径
  • 初始状态：CDEFH与A不相邻，他们代价无限大且前序节点未知（D(v)=∞, P(v)=NULL）；临时节点为B和G
  • 由于B代价最小，所以将B拉入永久节点中。此时永久节点B有两个邻居，临时节点为C和E，因为此时代价都比无穷小，所以对C和E进行重新标记
  • 临时节点当中E的代价最小，所以将E拉入永久节点中。此时临时节点集合为CFG，并重新计算代价。
  • 此时G代价最小，将G拉入永久节点中。此时临时节点集合为CFH，并重新计算代价
  • 此时F代价最小，将F拉入永久节点中。此时临时节点集合CDH。最后进行循环，并根据（D(v), P(v）二元组完成树的绘制
  • Dijkstra算法讨论（n个节点）
    • 每次迭代需要检查所有不在永久集合N中的节点
    • n(n+1)/2 O(n²) 复杂度（有更好的logn的实现）
    • 可能会存在震荡，每次计算出来的不一样，大家都去挤新的路径

1.2 Distance Vector

  • 基本思想
    • 各路由器维护一张路由表（目标, 下一条, 代价）
    • 各路由器与相邻路由器交换路由表（持续）
    • 根据交换的信息，更新路由表

　　XYZ分别记录了自己到B的代价，然后告诉给A；A测量自己到XYZ的代价，最后判断到B应该走哪个节点。每个路由器仅维护了自己的终点和下一跳分别是哪个路由器，这个算法原理很简单

1.3 LS和DV对比

  • 消息复杂度：
    • LS：有n个节点，E条链路，则报文数为 n*E
    • DV：只和邻居交换信息
  • 收敛时间：
    • LS：O(n²)
    • DV：收敛缓慢，可能存在环路问题
  • 健壮性：
    • DV：他可能告诉全网错误信息，自己的代价为0，然后扩散到全网，所有人都把消息转发给他

2 自治系统内部的路由选择

2.1 路由信息协议 RIP

　　路由信息协议（Routing Information Protocol，RIP），该协议是基于距离矢量算法的路由协议。最大支持15跳的长度，DV每隔30秒与相邻路由器交换信息，每个通告最多包括25个目标子网。如果180秒（6个周期）没有收到下一个路由器的路由通告，认为该邻居已失效。

　　RIP通过进程的方式实现，并且使用UDP报文传送数据，网络层的协议实际上使用传输层的服务来实现了网络层。

2.2 开放式最短路径优先 OSPF

　　开放式最短路径优先（Open Shortest Path First，OSPF），该协议是基于链路状态算法的路由协议。OSPF通告信息中携带每个邻居路由器的一个表象，通过泛洪在IP数据报上直接传送OSPF报文（不通过UDP或TCP）。

　　所有OSPF报文都经过认证（安全性高级特性），允许多个代价相同的路径存在，允许多种代价指标来计算路径，并且允许使用层次化的OSPF路由（本地和骨干2个层级，区域边界路由去、骨干路由器、边界路由器）

3 ISP之间的路由选择：BGP

  • 一个平面的路由
  • 一个网络中所有路由器的地位相同
  • 通过LS、DV计算所有路由器（子网）之间路径如何走
  • 所有路由器在同一个平面
  • 平面路由的问题
    • 规模巨大的网络中，路由信息的存储、传输和计算代价巨大
    • 管理问题，不同的网络希望按照自己的方式管理网络，隐藏自己网络的细节，同时与其他网络互联
  • 使用层次路由解决该问题
    • 将互联网分成一个个区域路由器，每个区域内部自治
    • 互联网AS间路由：BGP（Border Gateway Protocol）自治区间路由协议

4 SDN控制平面

　　软件定义网络的方式通过可编程应用在控制器之上以网络应用形式实现各种网络功能，控制平面功能在数据交换设备之外实现

　　控制平面通过南向接口给路由器传输流表，路由器基于流表匹配+动作的方式工作