SPF算法介绍
在路由选择领域里 ,很不幸的是Dijkstra算 法常常被认为是最短路径优先算法。毕竟每个路由选择协议的目标都是计算最短路径。 另一个不幸的是Dijkstra算法常常被描述的比实
际复杂得多，因为许多作者都使用集合论符号讨论它。最清晰的描述来自E.W.Dijkstra的原稿。这里将使用他的原话，并插入针对链路状态路由选择协议的解释 :
在我们给出的构造过程中，分枝被分成 3个集合:
Ⅰ.被明确分配给构造中的树的分枝（它们将在子树中）；
Ⅱ.这个分枝的隔壁分枝被添加到集合Ⅰ;
Ⅲ. 剩佘的分枝（抛弃或不考虑）。
节点被分成 2个集合：
A.被集合 Ⅰ中的分枝连接的节点；
B.剩余的节点（集合Ⅱ中有且仅有一个分枝将指向这些节点中的每一个节点 ）。
下面我们开始构造树，首先选择任意 一个节点作为集合A中仅有的成员 ，并将所有拿这个节点做端点的分枝放入集合Ⅱ中。
开始集合Ⅰ是空的。然后我们重复执行下面两步。
步骤1：集合Ⅱ中最短的分枝被移出并加入集合Ⅰ。结果，一个节点被从集合B传送到集合A。
步骤2：考虑从这个节点（刚才被传送到集合A中的节点）通向集合B中节点的分枝。如果构建中的分枝长于集合Ⅱ中相应的分枝，那么分枝被丢弃；否则，用它替代集合Ⅱ中相应的分枝，并且丢弃后者。
接着我们回到第1步并重复此过程直到集合Ⅱ和集合B为空。集合Ⅰ中的分枝形成所要求的树。
配合路由器的算法，第一点注意的是，Dijkstra描述了3个分枝集合：Ⅰ、Ⅱ和Ⅲ。在路由器中，使用3个数据库表示3个集合：
- 树数据库——树数据库用来表示集合Ⅰ。通过向数据库中添加分枝实现向最短路径树中添加链路（分枝）。当算法完成时，这个数据库将可以描述最短路径树。
- 候选对象数据库 —— 候选对象数据库对应集合Ⅱ。按照规定的顺序从链路状态数据库向该列表中复制链路，作为向树中添加的候选对象。
- 链路状态数据库 —— 按照前面的描述，这里保存所有链路，这个拓扑数据库对应集合Ⅲ。
Dijkstra还指定了两个节点集合 —— A和B。这里的节点是路由器。这些路由器被明确地用路由器链路三元组（路由器ID、邻居ID、代价）中的邻居ID表示。集合A由树数据库中链路所连接的路由器组成。集合B是所有其他的路由器。由于全要点是发现到每台路由器的最短路径，所以当算法结束时集合B应该为空。
下面是一 台路由器中采用的Dijkstra算法版本：
步骤1：路由器初始化树数据库，将自己作为树的根。这表明路由器作为它自己的邻居，代价为 0。
步骤2：在链路状态数据库中，所有描述通向根路由器邻居链路的三元组被添加到候选对象数据库中。
步骤3：计算从根到每条链路的代价，候选对象数据库中代价最小的链路被移到树数据库中。如果两个或更多的链路离根的最短代价相同，选择其中一条。
步骤4：检查添加到树数据库中的邻居ID。除了邻居ID已在树数据库中的三元组之外，链路状态数据库中描述路由器邻居的三元组被添加到候选对象数据库中。
步骤5：如果候选对象数据库中还有剩余的表项，回到第3步。如果候选数据库为空那么终止算法。在算法终止时，在树数据库中，每个单一的邻居ID表项将表示1台路由器，到此最短路径树构造完毕。
表1总结了应用Dijkstra算法为图1中的网络构建最短路径树的过程和结果。路由器RA正在运行算法，并使用链路状态数据库。图2给出了通过该算法为路由器RA构造的最短路径树。在每台路由器完成自己最短路径树的计算之后，它会检查其他路由器的网络链路信息，并且相当容易地把末梢网络添加到树中。根据这些信息，表项可以被制作为路由表。
表1
候选对象 | 到根的代价 | 树 | 描述 |
RA，RA，0 | 路由器A把自己作为树的根 | ||
RA，RB， 2 RA，RD，4 RA，RE， 4 | 2 4 4 | RA，RA，0 | 到所有RA邻居的链路被添加到候选对象列表 |
RA，RD，4 RA，RE，4 RB，RC，1 RB，RE，10 | 4 4 3 12 | RA，RA，0 RA，RB，2 | （RA，RB，2）是候选列表中代价最小的链路，所以被添加到 树中，所有RB的邻居除了已在树中的都被添加到候选列表， （RA，RE，4）到RE的代价比（RB，RE，10）小所以后者被 从候选列表中丢弃。 |
RA，RD，4 RA，RE， 4 RC，RF， 2 | 4 4 5 | RA，RA，0 RA，RB，2 RB，RC，1 | （RB，RC，1）是候选列表中代价最小的链路，所以被添加进 树中。所以RC的邻居除了已经在树中的都将变为候选对象。 |
RA，RE， 4 RC，RF， 2 RD，RE，3 RD，RG，5 | 4 5 7 9 | RA，RA，0 RA，RB，2 RB，RC，1 RA，RD，4 | （RA，RD，4）和（RA，RE，4）离RA的代价都为4， （RC，RF，2）代价为5，（RA，RD，4）被添加到树中，并且 它的邻居成为候选对象。在候选列表有两条路径到RE，从RA出 发（RD，RE，3）因代价更高而被丢弃。 |
RC，RF， 2 RD，RG，5 RE，RF，2 RE，RG，1 RE，RH，8 | 5 9 6 5 12 | RA，RA，0 RA，RB，2 RB，RC，1 RA，RD，4 RA，RE，4 | （RF，RE，1）被添加到树中并且它的邻居被添加进候选列表。 到RG代价最高的链路被丢弃。 |
RE，RF，2 RE，RG，1 RE，RH，8 RF，RH，4 | 6 5 12 9 | RA，RA，0 RA，RB，2 RB，RC，1 RA，RD，4 RA，RE，4 RC，RF，2 | （RC，RF，2）被添加进树中并且它的邻居被添加到候选列表。 由于从RA出发（RE，RG，1）代价相同（5），所以使用 （RE，RG，1）替代。到RH代价更高的链路被丢弃。 |
RF，RH，4 | 9 | RA，RA，0 RA，RB，2 RB，RC，1 RA，RD，4 RA，RE，4 RC，RF，2 RE，RG，1 | （RE，RG，1）被添加到树中，RG所有邻居都在树中，所以没有对象 被添加候选列表中。 |
RA，RA，0 RA，RB，2 RB，RC，1 RA，RD，4 RA，RE，4 RC，RF，2 RE，RG，1 RF，RH，4 | （RF，RH，4）是候选列表中代价最小的链路，所以被添加到树中， 候选列表不再有候选对象，所以算法终止，最短路径树构建完毕。 |
MPLS TE路径计算
TE使用CSPF算法，CSPF算法与SPF算法区别如下：
1，只在头端计算。
2，计算到尾端为止。
3，计算的结果，不放入FIB。
Tunnel的基本配置：
R1#show run int tun14
Building configuration...
Current configuration : 237 bytes
!
interface Tunnel14
ip unnumbered Loopback0 <<<<<<<<<<<<启用ip，允许IP包通过隧道
tunnel mode mpls traffic-eng <<<<<<<<指定Tunnel的模式为TE模式
tunnel destination 10.0.0.4 <<<<<<<<<
tunnel mpls traffic-eng priority 7 7 <<<<
tunnel mpls traffic-eng bandwidth 100000
tunnel mpls traffic-eng path-option 5 dynamic
end
TE隧道计算并建立成功后可以通过以下命令查看tunnel信息
R1#show mpls traffic-eng tunnels tunnel 14
Name: R1_t14 <<接口描述 (Tunnel14) Destination: 10.0.0.4
Status:
Admin: up Oper: up Path: valid<<<路径建立 Signalling: connected <<<信令可用
path option 5, type dynamic (Basis for Setup, path weight 16) <<<标识那个Option建立成功的隧道
Config Parameters:
Bandwidth: 100000 kbps (Global) <<<预留了Global资源池中的100M Priority: 7 7 Affinity: 0x0/0xFFFF <<<亲和属性及其亲和掩码
Metric Type: TE (default) <计算路径使用默认的TE 中的Metric
AutoRoute: disabled LockDown: disabled Loadshare: 100000 [20000] bw-based
auto-bw: disabled
Active Path Option Parameters:
State: dynamic path option 5 is active
BandwidthOverride: disabled LockDown: disabled Verbatim: disabled
InLabel : -
OutLabel : GigabitEthernet1, 200
Next Hop : 10.0.12.2
RSVP Signalling Info:
Src 10.0.0.1, Dst 10.0.0.4, Tun_Id 14, Tun_Instance 63
RSVP Path Info:
My Address: 10.0.12.1
Explicit Route: 10.0.12.2 10.0.27.7 10.0.47.4 10.0.0.4 <<<
Record Route: NONE
Tspec: ave rate=100000 kbits, burst=1000 bytes, peak rate=100000 kbits
RSVP Resv Info:
Record Route: NONE
Fspec: ave rate=100000 kbits, burst=1000 bytes, peak rate=100000 kbits
Shortest Unconstrained Path Info:
Path Weight: 16 (TE)
Explicit Route: 10.0.12.2 10.0.27.7 10.0.47.4 10.0.0.4
History:
Tunnel:
Time since created: 2 days, 32 minutes
Time since path change: 1 days, 8 hours, 27 minutes
Number of LSP IDs (Tun_Instances) used: 63
Current LSP: [ID: 63]
Uptime: 1 days, 8 hours, 27 minutes
Selection: reoptimization
Prior LSP: [ID: 62]
ID: path option unknown
Removal Trigger: reoptimization completed
R1#
CSPF计算示例
RA要计算一条BW为60Mbps到RD的TE隧道，使用CSPF算法。限制条件一：链路可用带宽（只看出向接口）
第一步，将RA自己放入到树中。
树 | 候选列表 |
RA 0 Null |
第二步，将树中的邻居放入到候选列表中。
树 | 候选列表 |
RA 0 Null | RB 5 RB RC 10 RC |
第三步，将候选列表中Metric最小的节点放入到树中。
树 | 候选列表 |
RA 0 Null RB 5 RB | RC 10 RC |
第四步，将新加入树的邻居加入到候选节点。因为RB到RC的BW不足60Mbps，所以不将RC 8 RB放入到候选节点。
树 | 候选列表 |
RA 0 Null RB 5 RB | RC 10 RC RC 13 RB |
第五步，将候选列表中Metric最小的节点放入到树中。
树 | 候选列表 |
RA 0 Null RB 5 RB RC 10 RC | RD 13 RB |
第六步，将新加入树的邻居加入到候选节点。放入时因为RD的Metirc比现在候选列表中的大，所以将其移除。
树 | 候选列表 |
RA 0 Null RB 5 RB RC 10 RC | RD 13 RB RD 14 RC |
第七步，将候选列表中Metric最小的节点放入到树中。
树 | 候选列表 |
RA 0 Null RB 5 RB RC 10 RC RD 13 RB |
第八步，因为已经计算到节点RD，所以算法停止，如果RD后面还有其他路由器，将不参与计算。
限制条件二：亲和属性（只看出向接口）
