Link-State Routing Protocols

链路状态路由协议(link-state routing protocol)的一些特征:

1.对网络发生的变化能够快速响应

2.当网络发生变化的时候发送触发式更新(triggered update)

3.发送周期性更新(链路状态刷新),间隔时间为30 分钟

链路状态路由协议只在网络拓扑发生变化以后产生路由更新.当链路状态发生变化以后,检测

到变化的设备创建LSA(link state advertisement),通过使用组播地址传送给所有的邻居设备,

然后每个设备拷贝一份LSA,更新它自己的链路状态数据库(link state database,LSDB),接着再

转发LSA 给其他的邻居设备.这种LSA 的洪泛(flooding)保证了所有的路由设备在更新自己

的路由表之前更新它自己的LSDB

LSDB 通过使用Dijkstra 算法(shortest path first,SPF)来计算到达目标网络的最佳路径,建立一

条SPF 树(tree),然后最佳路径从SPF 树里选出来,被放进路由表里

OSPF 和IS-IS 协议被归类到链路状态路由协议中.链路状态路由协议在一个特定的区域(area)

里从邻居处收集网络信息,一旦路由信息都被收集齐以后,每个路由器开始通过使用Dijkstra

算法(SPF)独立计算到达目标网络的最佳路径

运行了链路状态路由协议的路由器跟踪以下信息:

1.它们各自的邻居

2.在同一个区域中的所有路由器

3.到达目标网络的最佳路径

RIP 协议的特点是：

(1)仅和相邻路由器交换信息。【注】如果两个路由器之间的通信不需要经过另一个路由器，那么这两个路由器就是相邻的。RIP协议规定，不相邻的路由器不交换信息。

(2)路由器交换的信息是当前本路由器所知道的全部信息，即自己的路由表。【注】交换的信息是：“我到本自治制系统中所有网路的(最短)距离，以及到每个网络应该经过的下一跳路由器。”

(3)按固定的时间间隔交换路由信息。【注】每个30秒，然后路由器根据收到的路由信息更新路由表。当网路拓扑发生变化时，路由器也及时向相邻路由器通告拓扑变化后的路由信息。

是一种 分布式的基于距 离矢量的路由选 择协议，是因特网的标准协议，其最大优点就是实现简单，开销较小。

但 缺点也较多。首先，其限制了网络的规模，能使用的最大距离为15(16表示不可达)。其次路由器交换的信息是路由器的完整路由表，因而随着网络规模的扩大，开销也就增加。最后，"坏消息传播得慢"，使更新过程的收敛时间过长。

根据路由算法对网络变化的适应能力，主要分为两种类型：

静态路由选择策略——即非自适应路由选择，其特点是简单和开销较小，但不能及时适应网络状态的变化。

动态路由选择策略——即自适应路由选择，其特点是能较好地适应网络状态的变化，但实现起来较为复杂，开销也比较大。

因特网的路由选择协议

有关路由选择算法的几个基本概念

分层次的路由选择协议

内部网关协议和外部网关协议

距离向量算法，链路状态算法

路由信息协议RIP(Routing Information Protocol)

开放最短路径优先OSPF(Open Shortest Path First)

外部网关协议EGP，BGP

路由选择算法的几个基本概念

理想的路由算法

算法必须是正确的和完整的。

算法在计算上应简单。

算法应能适应通信量和网络拓扑的变化，这就是说，要有自适应性。

算法应具有稳定性。

算法应是公平的。

算法应是最佳的。

费用或代价

在研究路由选择时，需要给每一条链路指明一定的费用或代价。

这里“代价”并不一定是仅指 “钱”，而是由一个或几个因素综合决定的一种度量(metric)，如链路长度、数据率、链路容量、是否要保密、传播时延等，甚至还可以是一天中某一个小时内的通信量、结点的缓存被占用的程度、链路差错率等。

不同的要求下，各种因素的权值可能不同。

因特网采用分层次的路由选择协议。

因特网的规模非常大。如果让所有的路由器知道所有的网络应怎样到达，则这种路由表将非常大，处理起来也太花时间。而所有这些路由器之间交换路由信息所需的带宽就会使因特网的通信链路饱和。

许多单位不愿意外界了解自己单位网络的布局细节和本部门所采用的路由选择协议（这属于本部门内部的事情），但同时还希望连接到因特网上。