# 路由选择算法
# 路由概念
- 路由：按照某种指标找到一条从源节点到目标节点的较好路径
- 较好路径：按照某种指标较小的路径
- 指标：站数，延迟，费用，队列长度等
- 以网络为单位进行路由
- 网络为单位进行路由，路由信息传输，计算和匹配的代价低
- 前提条件：一个网络的所有节点地址前缀相同，且物理上聚集
- 路由就是：计算机网络到其他网络如何走的问题
- 网络到网络的路由 = 路由器 - 路由器之间的路由
- 网络对应的路由器到其他网络对应的路由器的路由
- 在一个网络中，路由器 - 主机之间的通信，链路层解决
- 到了这个路由器就是到了这个网络
- 路由选择算法：网络层软件的一部分，完成路由功能
# 路由的原则
- 正确性（correctness）：算法必须式正确和完整的，使分组一站一站的接力，正确发向目标站；完整：目标所有的站地址，在路由表中都能找到相应的表项，没有处理不了的目标站地址
- 简单性（simplicity）：算法在计算机上应简单，最优但是复杂的算法，时间上延迟很大，不实用，不应为了获取路由信息增加很多通信量
- 健壮性（robustness）：算法应该能适应通信量和网络拓扑的变化：通信量变化，网络拓扑的变化算法很快就能适应，不向很拥挤的链路发送数据，不向断了的链路发送数据
- 稳定性（stability）：产生路由不应该摇摆
- 公平性（fairness）：对每一个站点都公平
- 最优性（optimality）：对某个一个指标最优
# 路由算法分类
# 全局
- 所有的路由器拥有完整的拓扑和边的代价的信息
- link state 算法
# 分布式
- 路由器只知道它有物理连接关系的邻居路由器，和到相应邻居的路由器的代价值
- 迭代的与邻居交换路由信息，计算路由信息
- distance vector 蒜贩
# 静态
- 路由随时间变化缓慢
# 动态
- 路由变化快
- 周期性更新
- 根据链路的代价的变化而变化
# 因特网中自治系统内部的路由选择
# RIP
# 概述
- 在 1982 年发布的 B5D-UNIX 中实现
- 在 Distance vector 算法
- 距离矢量：每条链路 cost=1，max hops = 15 hops（最大跳数）
- DV 每隔 30 秒和邻居交换 DV，通告
- 每个通告包括：最多 25 个子网
# RIP 通告（advertisements）
- DV：在邻居之间每 30 秒交换通告报文
- 定期：而且在改变路由的时候发送通告报文
- 在对方的请求下可以发送通告报文
- 每一个通告：至多 AS 内部的 25 个目标网络 DV
- 目标网络 + 跳数
# RIP 链路失效和恢复
- 如果 180 秒没有收到通告消息 --> 邻居或者链路失效
- 发现经过这个邻居的路由已失效
- 新的通告报文会传送给邻居
- 邻居因此发出新的通告
- 链路失效快速的在整网中传输
- 使用毒性逆转组织 ping-pong 回路（不可达的距离，跳数无限 = 16 段）
# RIP 进程处理
- RIP 以应用进程的方式实现：route-d（daemon）
- 通告报文通过 UDP 报文传送，周期性重复
- 网络层的协议使用传输层的服务，以应用层实体的方式实现
# OSPF
# OSPF（Open Shortest Path First）概述
- open：标准公开
- 使用 LS 算法
- LS 分组在网络中（一个 AS 内部）分发
- 全局网络拓扑，代价在每一个节点中都保持
- 路由计算采用 Dijkstra 算法
- OSPF 通告信息中携带，每一个邻居路由器一个表项
- 通告信息会传遍 AS 全部（通过泛洪）
- 在 IP 数据报上直接传送 OSPF 报文（而不是 UDP 和 TCP）
- IS-IS 路由协议：几乎和 OSPF 一样
# OSPF 高级特性（RIP 没有的）
- 安全：所有的 OSPF 报文都是经过认证的
- 允许有多个代价相同的路径存在（RIP 中只有一个）
- 对于每一个链路，对于不同的 TOS 有多重代价矩阵
- 对单播和多播的集成支持
- 在大型网络中支持层次性的 OSPF
# 层次化的 OSPF 路由
- 两个级别的层次性：本地，骨干
- 链路状态通告仅仅在本地区域 Area 范围内进行
- 每一个节点都拥有本地区域的拓扑信息
- 区域边界路由器：汇总（聚集）到自己的区域内的网络的距离，向其他区域边界路由器通告
- 骨干路由器：仅仅在骨干区域内，进行 OSPF 路由
- 边界路由器：连接其他的 AS
# ISP 之间的路由选择 BGP
# 层次路由
# 概述
- 一个平面的路由
- 一个网络中的所有路由器地位一样
- 通过 LS，DV 或者其他路由算法，所有路由器都要直到其他所有路由器如何走
- 所有路由器在一个平面
- 平面路由问题
- 规模巨大的网络中，路由信息的存储，传输和计算代价巨大
- DV：距离矢量很大，且不能收敛
- LS：几百万个节点的 LS 分组的泛红传输，存储以及最短路径算法的计算
- 管理问题
- 不同的网络所有者希望按照自己的方式管理网络
- 希望对外隐藏自己网络的细节
- 当然，还希望和其他网络互连
- 规模巨大的网络中，路由信息的存储，传输和计算代价巨大
- 将互联网分成一个个 AS
- 某个区域内的路由器集合，自治系统
- 一个 AS 用 AS Number 唯一表示
- 一个 ISP 可能包括一个或者多个 AS
- 路由器变成了 2 个层次路由
- AS 内部路由：在一个 AS 内路由器运行相同的路由协议
- AS 间运行 AS 间的路由协议
# 优点
- 解决了规模问题
- 内部网关协议解决：AS 内部数量有限的路由器相互到达问题，AS 内部规模可控
- AS 之间的路由的规模问题
- 添加一个 AS，对于整体来说只是添加了一个节点 = 子网
- 对于其他 AS 来说只是增加了一个表项，就是这个新增的 AS 如何走的问题
- 扩展性强：规模增大，性能不会减得太多
- 解决了管理问题
- 各个 AS 可以运行不同的内部网关协议
- 可以使自己的网络细节不向外透露
# 互联网间的路由 BGP
# 概述
- BGP：自治系统区域间路由协议
- 连接互联网中的各个 AS
- BGP 提供给每个 AS 的方法
- eBGP：从相邻的 AS 哪里获得子网可达信息
- iBGP：将获得的子网可达信息传遍 AS 内部的所有路由器
- 根据子网可达信息和策略来决定到达子网的好路径
- 允许子网向互联网其他网络通告我的位置
- 基于距离矢量算法
# BGP 基础
- BGP 会话：两个 BGP 路由器在一个半永久的 TCP 连接上交换 BGP 报文
# 路径的属性 BGP 路由
- 当通告一个子网前缀时，通告包括 BGP 属性
- 两个重要属性
- AS-PATH：前缀的通告所经过的 AS 列表
- 检测环路
- 在向其他 AS 转发时，需要将自己的 AS 号加上
- NEXT-PATH：从当前 AS 到下一个 AS 有多个链路，NEXT-HOP 属性中，告诉对方通过哪个 I 转发
- 其他属性：路由偏好指标，如何被插入的属性
- AS-PATH：前缀的通告所经过的 AS 列表
- 基于策略的路由
- 当一个网关路由接收到一个路由通告，使用输入策略来接受或过滤
- 策略也决定了是否向它别的邻居通告收到这个路由信息
# BGP 报文
- 使用 TCP 协议交换报文
- BGP 报文
- OPEN：打开 TCP 连接，认证发送方
- UPDATE：通过更新路径
- KEEPALIVE：在没有更新时保持连接，也用于对 OPEN 的请求确认
- NOTIFICATION：报文以前消息的错误，也用来关闭连接
# SDN 控制平面
# 概述
- SDN 方式：逻辑上集中的控制平面
- 一个不同的控制器与本地控制代理交互
# 为什么需要在逻辑上集中的控制平面
- 网络管理更加容易：避免路由器的错误配置，对于通信流的弹性更好
- 基于流表的转发，允许可编程的路由器
- 控制平面的开放实现
# OpenFlow 协议
- 控制器和 SDN 交换机交换的协议
- 采用 TCP 来交换报文
- 三种 OpenFlow 报文类型
# OpenFlow 控制器交换机报文
- 特性：控制器查询交换机特性，交换机应答
- 配置：交换机查询 / 设置交换机的配置参数
- 修改状态：增加删除修改 OpenFlow 表中的流表
- packet-out：控制器可以将分组通过特定的端口发出
# OpenFlow 交换机到控制器的报文
- 分组进入：将分组（和它的控制）传给控制器，见来自控制器的 pcaket-out 报文
- 流移除：在交换机上删除流表项
- 端口状态：通告控制器端口的变化
