---

前言

本文主要介绍路由选择算法，写作框架依照PPT而非课本（因为PPT上的内容更全一点）

路由选择算法

The Optimality Principle最优化原则

Shortest Path Routing

A Link-State Routing Algorithm 链路状态路由选择算法

首先，很重要的问题！
链路状态路由选择算法≠迪杰斯特拉算法
迪杰斯特拉算法实际上只是链路状态路由选择算法的一个步骤。
考试的时候老师会出题，让你用链路状态路由选择算法生成路由表，很多同学直接用迪杰斯特拉算法解决，这是不对的（直接用眼睛看出结果更不对）。这是考试要注意的一个点。

图中曲线表示不是直接相连。

注意看右边的转发表（Forwarding Table）
路由表是Routing Table
左侧是目的地，实际当中应该是目的IP和子网掩码与出来的结果。
右侧是出口。
比如我要从u去y，这个转发表就告诉我“你应该从w出去！”

路由器的结构结构可划分为两大部分：路由选择部分和分组转发部分
路由选择部分也叫做控制部分，其核心构件是路由选择处理机。路由选择处理机的任务是根据所选定的路由协议构造出路由表，同时经常或定期地和相邻的路由器交换路由信息而不断地更新和维护路由表。
分组转发部分由三部分组成：交换结构、输入端口和输出端口。
交换结构的作用就是根据转发表(forwarding table)对分组进行处理，将某个输入端口进入的分组从一个合适的输出端口转发出去。
请注意“转发”和“路由选择”是有区别的。
“转发”即使路由器根据转发表把收到的IP数据报从路由器合适的端口转发出去。“转发”仅仅涉及到一个路由器。
“路由选择”涉及到很多路由器，路由表是许多路由器协同工作的结果。这些路由器按照复杂的路由算法，得出整个网络的拓扑变化情况，因而能够动态改变所选择的路由，并由此构造出整个的路由表。
路由表一般仅包含从目的网络到下一跳的映射
转发表是从路由表得出的。转发表必须包含完成转发功能所必需的信息。也就是说，在转发表的每一行必须包含从要到达的目的网络到输出端口和某些MAC地址信息（如下一跳的以太网地址）的映射。
将转发表和路由表用不同的数据结构实现会实现会带来一些好处，这是因为在转发分组时，转发表的结构应当是查找过程最优化，但路由表则需要对网络拓扑变化的计算最优化。
摘自https://www.cnblogs.com/qinyongzhu/p/4929833.html

我们用Dijkstra算法算出来的是从出发点u到每一个点的最短路径。但是通过观察转发表我们发现，这个转发表里根本没用到这么详细的信息。
转发表主要就是告诉我们分组要从哪一个输出端口转发出去。这个转发表也是一样，如果我是一个分组，我要去Z，他只告诉我：从这边出去到W那边去吧！他并没有告诉我我到了W之后要怎么做（实际上我到了W之后，W会告诉我接下来怎么走）