路由算法与路由协议
选择转发IP分组的过程叫做：路由选择
路由选择的核心：路由选择算法
带权无向图
将网络抽象为一个带权无向图G=(N, E)，N代表结点集合，E是边的集合
网络中的路由器抽象为G的结点，连接两个路由器的网络链路抽象为G的边
网络链接的费用（比如时延）抽象为G的权值
存在结点X、结点Y：
如果两个结点间有边，则费用为：X到Y的权值
如果两个结点间没有边，费用为：无限
路由选择算法的分类
分类标准
- 是否需要全局信息
- 静态动态
- 是否敏感
依据 是否需要全局信息 进行的划分
- 全局式 路由选择算法，典型：链路状态 路由选择算法（LS算法）
- 分布式 路由选择算法，典型：距离向量 路由选择算法（DV算法）
依据 静态动态 进行的划分
- 静态：人工干预
- 动态：LS算法、DV算法
链路状态路由选择算法（LS算法）
是一种全局式路由选择算法，每个路由器在计算路由时，需要构建整个网络的拓扑图
利用 Dijkstra算法 求最短路径
| 标识 | 含义 |
|---|---|
| D(v) | 到本次迭代为止，源结点到目的结点v的当前路径距离 |
| P(v) | 到本次迭代为止，在源结点到目的结点v的当前路径上，结点v的前序结点 |
| c(x,y) | 结点x到结点y之间直接链路的费用 |
| S | 结点的集合，用于存储源结点到该结点的最短路径已求出的终点集合 |
P(v)：如果路径上只有两个结点，则该值就是最后一个结点
例如：x->y P(y)=y
c(x,y)：如果x和y之间没有链路相连，则c(x,y)=
距离向量路由选择算法（DV算法）
基础是 Bellman-Ford 方程（简称 B-F方程）
令 dx(y) 表示结点x到结点y的路径的最低费用，根据 B-F 方程，有以下的公式：
dx(y) = min { c(x,v) + dv(y) }
例子：
x -- 2 -- y、y -- 3 -- z、x -- 7 -- z
计算结果：
dx(z) = min { c(x,z)+dz(z), c(x,y)+dy(z) } = min { 7+0, 2+3 } = 5
特点
- 路由器分别维护自己的转发表（DV），并且接收邻居（与本路由器直接相连）的通知
- 收到通知进行对比更新
层次化路由选择
大规模网络路由选择 最有效可行的解决方案
层次化路由选择原理
大规模互联网的路由划分为两层：
- 自治系统 内 路由选择：计算到达自治系统内目的网络的路由
- 自治系统 间 路由选择：负责其他自治系统网络的可达性消息
自治系统：
autonomous system, AS，互联网按组织边界划分为多个自治系统。每个自治系统由运行 相同 路由协议和路由选择算法的路由器组成
网关路由器：
每个自治系统存在至少一个与其他自治系统互连的路由器
Internt路由选择协议
根据层次化路由选择划分为：
- 内部网关协议（Interior Gateway Protocol, IGP），Internet自治系统 内 路由选择协议
- 外部网关协议（Exterior Gateway Protocol, EGP），Internet自治系统 间 路由选择协议
IGP的典型协议：
- 路由信息协议（Routing Information Protocol, RIP）
- 开放最短路径优先协议（Open Shortest Path First, OSPF）
EGP的典型协议：
- 边界网关协议（Border Gateway Protocol, BGP）
RIP
适用于 较小 的自治系统（AS），基于 距离向量路由选择算法 的IGP协议
RIP报文，封装进 UDP 数据报
RIP特性：
- RIP在度量路径时采用 跳数
- RIP的费用定义在源路由器和目的子网之间
- RIP被限制在网络直径不超过 15跳 的自治系统内部使用
OSPF
适用于 规模较大 的自治系统（AS），基于 链路状态路由选择算法 的IGP协议
直接封装于 IP 数据报
OSPF的优点：
- 安全
- 支持多条相同费用路径
- 支持区别化费用度量
- 支持单播路由与多播路由
- 分层路由
BGP
实现跨自治系统的路由信息转换。典型版本是BGP4
直接封装于 TCP 报文段
BGP的4种报文：
- OPEN（打开）报文
- UPDATE（更新）报文
- KEEPALINE（保活）报文
- NOTIFICATION（通知）报文
