https://zhuanlan.zhihu.com/p/97957818
链路状态路由选择协议又称为最短路径优先协议或分布式数据库协议，它基于Edsger Dijkstra的最短路径优先（SPF）算法。 [1] 它比距离矢量路由协议复杂得多，但基本功能和配置却很简单，算法易理解。链路状态协议从网络或者网络的限定区域内的所有其他路由器处收集信息，最终每个链路状态路由器上都有一个相同的有关网络的信息。并且每台路由器都可以独立的计算各自的最优路径。
路由协议
链路状态路由协议是层次式的，网络中的路由器并不向邻居传递“路由项”，而是通告给邻居一些链路状态。与距离矢量路由协议相比，链路状态协议对路由的计算方法有本质的差别。距离矢量协议是平面式的，所有的路由学习完全依靠邻居，交换的是路由项。链路状态协议只是通告给邻居一些链路状态。运行该路由协议的路由器不是简单地从相邻的路由器学习路由，而是把路由器分成区域，收集区域的所有的路由器的链路状态信息，根据状态信息生成网络拓扑结构，每一个路由器再根据拓扑结构计算出路由。 [1]
工作过程
一、了解直连网络
每台路由器了解其自身的链路（即与其直连的网络）。这通过检测哪些接口处于工作状态（包括第3层地址）来完成。
对于链路状态路由协议来说，直连链路就是路由器上的一个接口，与距离矢量协议和静态路由一样，链路状态路由协议也需要下列条件才能了解直连链路：正确配置了接口IP地址和子网掩码并激活接口，并将接口包括在一条network语句中。
二、向邻居发送Hello数据包
每台路由器负责“问候”直连网络中的相邻路由器。与EIGRP路由器相似，链路状态路由器通过直连网络中的其他链路状态路由器互换Hello数据包来达到此目的。
路由器使用Hello协议来发现其链路上的所有邻居，形成一种邻接关系，这里的邻居是指启用了相同的链路状态路由协议的其他任何路由器。这些小型Hello数据包持续在两个邻接的邻居之间互换，以此实现“保持激活”功能来监控邻居的状态。如果路由器不再收到某邻居的Hello数据包，则认为该邻居已无法到达，该邻接关系破裂。
三、建立链路状态数据包
每台路由器创建一个链路状态数据包（LSP），其中包含与该路由器直连的每条链路的状态。这通过记录每个邻居的所有相关信息，包括邻居ID、链路类型和带宽来完成。一旦建立了邻接关系，即可创建LSP，并仅向建立邻接关系的路由器发送LSP。LSP中包含与该链路相关的链路状态信息、序列号、过期信息。
四、将链路状态数据包泛洪给邻居
每台路由器将LSP泛洪到所有邻居，然后邻居将收到的所有LSP存储到数据库中。接着，各个邻居将LSP泛洪给自己的邻居，直到区域中的所有路由器均收到那些LSP为止。每台路由器会在本地数据库中存储邻居发来的LSP的副本。
路由器将其链路状态信息泛洪到路由区域内的其他所有链路状态路由器，它一旦收到来自邻居的LSP，不经过中间计算，立即将这个LSP从除接收该LSP的接口以外的所有接口发出，此过程在整个路由区域内的所有路由器上形成LSP的泛洪效应。距离矢量路由协议则不同，它必须首先运行贝尔曼-福特算法来处理路由更新，然后才将它们发送给其他路由器;而链路状态路由协议则在泛洪完成后再计算SPF算法，因此达到收敛状态的速度比距离矢量路由协议快得多。LSP在路由器初始启动期间、或路由协议过程启动期间、或在每次拓扑发生更改（包括链路接通或断开）时、或是邻接关系建立、破裂时发送，并不需要定期发送。
五、构建链路状态数据库
每台路由器使用数据库构建一个完整的拓扑图并计算通向每个目的网络的最佳路径。就像拥有了地图一样，路由器现在拥有关于拓扑中所有目的地以及通向各个目的地的路由的详图。SPF算法用于构建该拓扑图并确定通向每个网络的最佳路径。所有的路由器将会有共同的拓扑图或拓扑树，但是每一个路由器独立确定到达拓扑内每一个网络的最佳路径。
在使用链路状态泛洪过程将自身的LSP传播出去后，每台路由器都将拥有来自整个路由区域内所有链路状态路由器的LSP，都可以使用SPF算法来构建SPF树。这些LSP存储在链路状态数据库中。有了完整的链路状态数据库，即可使用该数据库和最短路径优先（SPF）算法来计算通向每个网络的首选（即最短）路径。 [2-3]
协议优点
与距离矢量路由协议相比，有如下优点：
创建拓扑图
链路状态路由协议会创建拓扑图，即SPF树，而距离矢量路由协议没有网络的拓扑图，仅有一个网络列表，其中列出了通往各个网络的开销（距离）和下一跳路由器（方向）。因为链路状态路由协议会交换链路状态信息，所以SPF算法可以构建网络的SPF树，有了SPF树，路由器可独立确定通向每个网络的最短路径。
快速收敛
有几个原因使得链路状态路由协议比距离矢量路由协议具有更快的收敛速度。收到一个链路状态数据包（LSP）后链路状态路由协议便立即将该LSP从除接收该LSP的接口以外的所有接口泛洪出去。使用距离矢量路由协议的路由器需要处理每个路由更新，并且在更新完路由表后才能将更新从路由器接口泛洪出去，即使对触发更新也是如此。因此链路状态路由协议可更快达到收敛状态。不过EIGRP是一个明显的例外。
事件驱动更新
在初始LSP泛洪之后，链路状态路由协议仅在拓扑发生改变时才发出LSP。该LSP仅包含受影响链路的信息。与某些距离矢量路由协议不同的是，链路状态路由协议不会定期发送更新。
层次式设计
链路状态路由协议，如OSPF和IS-IS使用了区域的概念。多个区域形成了层次化的网络结构，这有利于路由聚合（汇总），还便于将路由问题隔离在一个区域内。 [2] [4]
协议要求
现代链路状态路由协议设计旨在尽量降低对内存、CPU和带宽的影响。使用并配置多个区域可减小链路状态数据库。划分多个区域还可限制在路由域内泛洪的链路状态信息的数量，并可仅将LSP发送给所需的路由器。 [1]
内存要求
与距离矢量路由协议相比，链路状态路由协议通常需要占用更多的内存、CPU处理时间和带宽。对内存的要求源于链路状态数据库的使用和创建SPF树的需要。
处理器要求
与距离矢量路由协议相比，链路状态路由协议可能还需要占用更多的CPU处理时间。与Bellman-Ford等距离矢量算法相比，SPF算法需要更多的CPU处理时间，因为链路状态路由协议会创建完整的拓扑图。
带宽要求
链路状态数据包泛洪会对网络的可用带宽产生负面影响。这应该只出现在路由器初始启动过程中，但在不稳定的网络中也可能导致问题。
协议比较
如今，用于IP路由的链路状态路由协议有两种。
最短路径优先（OSPF）
OSPF由IETF的OSPF工作组设计，OSPF的开发始于1987年，如今正在使用的有OSPFv2和OSPFv3两个版本。OSPF的大部分工作由John Moy完成。
中间系统到中间系统（IS-IS）
IS-IS由ISO设计的，它的雏形由DEC开发，名为DECnet Phase V，首席设计师是Radia Perlman.
IS-IS最初是为OSI协议簇而非TCP/IP协议簇而设计的，后来，集成化IS-IS，即双IS-IS添加了对IP网络的支持，尽管IS-IS路由协议一直主要供ISP和电信公司使用，但已有越来越多的企业开始使用IS-IS。
两者既有很多共同点，也有很多不同之处。有很多分别拥护OSPF和IS-IS的派别，它们从未停止过对双方优缺点的讨论和争辩。
ospf与is-is的相似之处
无类别；
使用链路状态数据库和Dijkstra算法；
用Hello分组来建立和维护毗邻关系；
用区域来组建层次化拓扑；支持区域间路由汇总；
在多路访问型网络中选举指定路由器；
链路状态的表示方式、时效（aging）和度量值；
更新，判断和洪泛扩散；
收敛能力；
用与isp主干网络；
ospf与is-is的不同之处
is-is不会选举BDR；
当有新的路由器加入时；isis会重新选举；
每当DR发生改变时，就会洪泛一批新的LSA；
isis路由器和全部邻接路由器都建立毗邻关系，而不只和DR建立；
ospf与is-is区域间的其它不同之处
ospf基于一个主干中心，其他区域都链接在主干上（区域边界落在ABR之内，每一条链路只属于一个区域）；
isis中区域边界落在链路上（每一个isis路由器完全属于一个第2层区域）；
ospf单个区域支持50个路由器，isis支持100个；
ospf有更多特性，包括路由标签、完全末梢区域、NSSA、以及虚拟链路。 [1]
对于isis来说，区域边界位于链路上，这样可以显著减少协议数据单元PDU(LSP)的使用，从而使一个区域中有更多的路由器。就cpu的使用效率和路由更新处理来说，isis更有效率，不仅是因为isis的链路状态通告比ospf少，还因为isis添加和删除前缀的操作比较少。isis对区域中的每台路由器只使用一个链路状态分组，其中包括重发布前缀。使用默认定时器，isis比ospf更快的发现路由失效，从而收敛更快。isis中的定时器比ospf的更具可调性，所以能达到更精确的调节粒度。
参考资料
1.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B1%5D_67350Rick Graziani Allan Johnson．思科网络技术学院教程-路由协议和概念．北京：人民邮电出版社，2015.3
2.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B2%5D_67350（美）阿齐兹，（美）马蒂．IP路由协议疑难解析：人民邮电出版社，2013.7
3.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B3%5D_67350尹淑玲．交换与路由技术教程：武汉大学出版社，2012.11
4.https://baike.baidu.com/item/%E9%93%BE%E8%B7%AF%E7%8A%B6%E6%80%81%E8%B7%AF%E7%94%B1%E5%8D%8F%E8%AE%AE/1219386?fr=aladdin#ref_%5B4%5D_67350沈鑫剡．路由和交换技术 ：清华大学出版社，2013.2
如果说距离矢量路由协议提供的是路标，那么链路状态路由协议提供的就是地图。每个链路状态路由器上都有一张完整的网络图。链路状态协议不同于距离矢量协议“依照传闻”进行路由选择的工作方式。每台链路状态路由器从对等路由器那里获取的都是“第一手”的信息。每台路由器都会将一些关于自己，关于本地直连链路以及这些链路的状态和关于所有直连邻居的信息传送给另一台路由器，接受到信息的路由器都会将该类信息做一个拷贝，但绝不修改信息。最终的目的是每台路由器都有一个相同的有关网络的信息。并且每台路由器都可以独立的计算各自的最优路径。
链路状态协议有时也叫最短路径优先协议或叫分布式数据库协议，该类协议是围绕一个著名的算法——E.W.Dijkstra的最短路径算法设计的。
常见的链路状态协议有
OSPF：开放式最短路径优先协议
IS-IS:中间系统到中间系统协议
链路状态协议的工作过程：
第一步：每台路由器都与自己的邻居建立邻接关系。
第二步：每台路由器都向自己的邻居发送链路状态通告（LSA）的数据单元。路由器对自己的每条链路都会生成一条链路状态通告，用于标记该条链路及链路状态，指示路由器接口到链路的代价度量值及链路所连接的所有邻居。每个邻居收到链路状态通告后将向它的邻居洪泛这些通告。
第三步：每台路由器都会将自己收到的LSA拷贝并存入到本地的链路状态数据库（LSDB）中。若每台路由都正常工作，那么所有路由器的链路状态数据库中的网络信息都会是相同的。
第四步：基于本地的链路状态数据库网路信息，使用最短路径优先算法计算出到每台路由器的最短路径。接着链路状态协议会通过查询链路状态数据，找到每台路由器所连接的子网，并把这些信息输入到路由表中。
邻居
邻居发现是建立链路状态环境并运行的第一步。使用Hello协议完成邻居发现。Hello协议定义了一个Hello数据的格式和交换数据包并处理数据包信息的过程。
Hello数据包中至少包含路由ID（router ID）和发送数据包的网络地址。路由器ID是用来将路由在网络中唯一的标识。
当两台路由器之间确认为邻居关系时，它们之间就要进行数据同步即交换和确定数据库信息直到数据库相同为止。为了执行数据库同步，邻居之间必须建立邻接关系。即它们必须就某些参数达成一致。通过Hello数据包建立邻接关系，链路状态就可以在受控的方式下交换信息。与距离矢量协议相比，链路状态协议仅在配置了路由选择协议的接口上广播更新信息。
除了发现邻居建立邻接关系的作用外，Hello数据包还可以作为监视邻接关系的握手信息。如果没有在特定的时间内从邻接路由器接收到Hello数据包，就认为邻居不可达。随即邻接关系解除。
链路状态洪泛扩散
在建立邻接关系后路由器发送LSA。LSA被洪泛给每台路由器，路由器保存收到的LSA，并继续向自己的邻居洪泛（除接收接口外的其他所有配置接口）。这个过程就体现出链路状态协议的优秀之处，因为LSA是立刻被转发的，而在距离矢量协议中所有路由器在接收到更新信息后都必须先将自己路由表更新才会向邻居转发更新信息，触发更新也是如此。因此，当网络拓扑发生变化时，链路状态协议收敛的速度会远远快于距离矢量协议。
