CN109510768B - 链路状态通告lsa发送方法、装置和系统 - Google Patents

Abstract

本申请公开了一种链路状态通告LSA发送方法、装置和系统，涉及通信领域，用于减少LSA发送次数。该方法包括：第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表；第一路由器向第二路由器发送第一链路状态更新LSU消息；第二路由器从第一路由器接收第一链路状态更新LSU消息；第二路由器根据第一LSA更新其链路状态数据库LSDB；第二路由器向第一路径表中的标识对应的路由器发送第一LSA。本申请实施例应用于叶脊拓扑或胖树拓扑中LSA的发送。

Description

链路状态通告LSA发送方法、装置和系统

技术领域

本申请涉及通信领域，尤其涉及一种链路状态通告(Link State Advertisement，LSA)泛洪方法、装置和系统。

背景技术

叶脊(Leaf-Spine)或胖树(Fat-Tree)作为两种特殊的层次化、结构化拓扑，在数据中心中有着广泛的应用。参照图1中所示，为Leaf-Spine的拓扑示意图，包括脊(Spine)节点11和叶子(Leaf)节点12。参照图2中所示，为Fat-Tree 的结构示意图，包括核心网络21、汇聚网络22和边缘网络(叶子节点)23，边缘网络23和汇聚网络22可以被划分为不同的集群(Pod)，每个集群中的拓扑等效于Leaf-Spine拓扑。

开放式最短路径优先(Open Shortest Path First，OSPF)协议，是目前网络中使用最广泛的内部网关(Interior Gateway Protocol，IGP)协议。其基本原理是：位于网络中的每台路由器通过Hello报文与它的邻居路由器建立邻接关系；每台路由器向每个邻居路由器发送LSA，每个邻居路由器在收到LSA之后要依次向它的邻居路由器转发这些LSA，即泛洪；每台路由器在各自链路状态数据库(Link State Database，LSDB)保存一份所收到的LSA的备份，所有路由器保存的LSDB 相同；每台路由器依照拓扑数据库通过最短路径优先(Shortest Path First，SPF) 算法计算出到网络上每个节点的最短路径，并将结果输出形成路由选择表。

对于Leaf-Spine拓扑或Fat-Tree拓扑，每对叶子节点之间存在多条等价路径，因此，现有技术中OSPF协议泛洪LSA的机制存在以下问题：首先，LSA在网络中泛洪时会产生大量的重复或冗余，会进一步产生LSA反弹现象；其次，当相邻节点之间发生链路故障时，仍然会通过其他节点接收到对方的LSA，但是这两个节点之间并不会有数据传输，因此没有必要维护完全相同的LSDB。

发明内容

本申请的实施例提供一种LSA发送方法、装置和系统，用于减少LSA发送次数。为达到上述目的，本申请的实施例采用如下技术方案：

第一方面，提供了一种链路状态通告LSA发送方法，该方法包括：第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表，其中，第二路由器是与第一路由器之间链路有效的邻居路由器，第三路由器是与第二路由器之间链路有效的邻居路由器中，除了第一路由器以外的路由器，第一路径表包括至少一个第三路由器的标识，第一路径表中的标识用于指示向对应路由器发送第一LSA，第一LSA包括通告路由器与其邻居路由器之间的有效链路，通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器；第一路由器向第二路由器发送第一链路状态更新LSU消息，其中，第一LSU消息中包括第一LSA和第一路径表。本申请实施例提供的LSA发送方法，发送LSA的路由器根据其层次位置信息、下一跳路由器的层次位置信息和下下一跳路由器的层次位置信息，生成路径表，发送LSA的路由器向下一跳路由器发送LSA的同时发送该路径表，由于该路径表中包括下下一跳路由器的标识，指示下一跳路由器向对应的下下一跳路由器转发LSA，直到作为叶子节点的路由器接收到LSA后不作转发。通过发送LSA的路由器指示下一跳路由器有选择地向下下一跳路由器转发LSA，减少了LSA的发送次数，避免下下一跳路由器重复收到LSA。

在一种实施方式中，该方法还包括：第一路由器从第四路由器接收第二LSU 消息，第二LSU消息中包括第一LSA，其中，第四路由器是与第一路由器之间链路有效的邻居路由器中，除了第二路由器以外的路由器；第一路由器根据第一LSA 更新其链路状态数据库LSDB。该实施方式提供了第一LSA的一种可能的来源。

在一种实施方式中，第一路由器向第二路由器发送第一链路状态更新LSU消息，包括：当第二LSU消息中还包括第二路径表时，第一路由器向第二路由器发送第一LSU消息，其中，第二路径表中包括至少一个第二路由器的标识，第二路径表中的标识用于指示向对应路由器发送第一LSA。该实施方式提供了发送LSU 消息的一种可能的条件。

在一种实施方式中，第一路由器为通告路由器。该实施方式提供了第一路由器的一种可能的实现方式。

在一种实施方式中，第一LSA包括通告路由器的层次位置信息和/或与通告路由器链路有效的邻居路由器的层次位置信息。该实施方式提供了各路由器的层次位置信息的一种可能传递方式。

在一种实施方式中，在第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表之前，该方法还包括：第一路由器从第二路由器接收第二LSA，第二LSA包括第二路由器的层次位置信息和/或至少一个第三路由器的层次位置信息。该实施方式提供了各路由器的层次位置信息的另一种可能传递方式。

在一种实施方式中，在第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表之前，该方法还包括：第一路由器向第二路由器发送第一开放式最短路径优先OSPF协商消息；第一路由器从第二路由器接收第二OSPF协商消息；其中，第一OSPF协商消息中包括第一路由器的层次位置信息，第二OSPF协商消息中包括第二路由器的层次位置信息，第一OSPF协商消息和第二OSPF协商消息用于建立和维护第一路由器与第二路由器的邻居关系。该实施方式提供了各路由器的层次位置信息的又一种可能传递方式。

第二方面，提供了一种链路状态通告LSA发送方法，该方法包括：第二路由器从第一路由器接收第一链路状态更新LSU消息，其中，第一LSU消息中包括第一LSA和第一路径表，第一LSA包括通告路由器与其邻居路由器之间的有效链路，通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器，第一路径表包括至少一个第三路由器的标识，第二路由器是与第一路由器之间链路有效的邻居路由器，第三路由器是与第二路由器之间链路有效的邻居路由器中，除了第一路由器以外的路由器；第二路由器根据第一LSA更新其链路状态数据库 LSDB；第二路由器向第一路径表中的标识对应的路由器发送第一LSA。本申请实施例提供的LSA发送方法，发送LSA的路由器根据其层次位置信息、下一跳路由器的层次位置信息和下下一跳路由器的层次位置信息，生成路径表，发送LSA 的路由器向下一跳路由器发送LSA的同时发送该路径表，由于该路径表中包括下下一跳路由器的标识，指示下一跳路由器向对应的下下一跳路由器转发LSA，直到作为叶子节点的路由器接收到LSA后不作转发。通过发送LSA的路由器指示下一跳路由器有选择地向下下一跳路由器转发LSA，减少了LSA的发送次数，避免下下一跳路由器重复收到LSA。

在一种实施方式中，该方法还包括：第二路由器根据其层次位置信息、第三路由器的层次位置信息和至少一个第五路由器的层次位置信息，生成第二路径表，其中，第二路径表包括至少一个第五路由器的标识，第二路径表中的标识用于指示向对应路由器发送第一LSA，第五路由器是与第三路由器之间链路有效的邻居路由器中，除了第二路由器以外的路由器；第二路由器向第一路径表中的标识对应的路由器发送第一LSA，包括：第二路由器向第一路径表中的标识对应的路由器发送第二LSU消息，其中，第二LSU消息中包括第一LSA和第二路径表。该实施方式提供了在发送LSA时还可以同时携带路径表。

在一种实施方式中，在第二路由器根据其层次位置信息、第三路由器的层次位置信息和至少一个第五路由器的层次位置信息，生成第二路径表之前，该方法还包括：第二路由器从第三路由器接收第二LSA，第二LSA包括第三路由器的层次位置信息和/或至少一个第五路由器的层次位置信息。该实施方式提供了各路由器的层次位置信息的一种可能传递方式。

在一种实施方式中，第一LSA包括通告路由器的层次位置信息和/或与通告路由器链路有效的邻居路由器的层次位置信息。该实施方式提供了各路由器的层次位置信息的另一种可能传递方式。

在一种实施方式中，第一路由器为通告路由器。该实施方式提供了第一路由器的一种可能的实现方式。

在一种实施方式中，在第二路由器从第一路由器接收第一链路状态更新LSU 消息之前，该方法还包括：第二路由器向第一路由器发送第一开放式最短路径优先OSPF协商消息；第二路由器从第一路由器接收第二OSPF协商消息；其中，第一OSPF协商消息中包括第二路由器的层次位置信息，第二OSPF协商消息中包括第一路由器的层次位置信息，第一OSPF协商消息和第二OSPF协商消息用于建立和维护第一路由器与第二路由器的邻居关系。该实施方式提供了各路由器的层次位置信息的又一种可能传递方式。

第三方面，提供了一种第一路由器，该路由器包括：生成单元，用于根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表，其中，第二路由器是与第一路由器之间链路有效的邻居路由器，第三路由器是与第二路由器之间链路有效的邻居路由器中，除了第一路由器以外的路由器，第一路径表包括至少一个第三路由器的标识，第一路径表中的标识用于指示向对应路由器发送第一链路状态通告LSA，第一LSA包括通告路由器与其邻居路由器之间的有效链路，通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器；发送单元，用于向第二路由器发送第一链路状态更新 LSU消息，其中，第一LSU消息中包括第一LSA和第一路径表。基于同一发明构思，由于该第一路由器解决问题的原理以及有益效果可以参见上述第一方面和第一方面的各可能的方法实施方式以及所带来的有益效果，因此该第一路由器的实施可以参见上述第一方面和第一方面的各可能的方法的实施方式，重复之处不再赘述。

第四方面，提供了一种第二路由器，该路由器包括：接收单元，用于从第一路由器接收第一链路状态更新LSU消息，其中，第一LSU消息中包括第一链路状态通告LSA和第一路径表，第一LSA包括通告路由器与其邻居路由器之间的有效链路，通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器，第一路径表包括至少一个第三路由器的标识，第二路由器是与第一路由器之间链路有效的邻居路由器，第三路由器是与第二路由器之间链路有效的邻居路由器中，除了第一路由器以外的路由器；更新单元，用于根据第一LSA更新其链路状态数据库LSDB；发送单元，用于向第一路径表中的标识对应的路由器发送第一LSA。基于同一发明构思，由于该第二路由器解决问题的原理以及有益效果可以参见上述第二方面和第二方面的各可能的方法实施方式以及所带来的有益效果，因此该第二路由器的实施可以参见上述第二方面和第二方面的各可能的方法的实施方式，重复之处不再赘述。

第五方面，本申请实施例提供一种路由器，包括：处理器、存储器、总线和通信接口；该存储器用于存储计算机执行指令，该处理器与该存储器通过该总线连接，当该路由器运行时，该处理器执行该存储器存储的该计算机执行指令，以使路由器执行上述第一方面中任意一项或第二方面中任意一项所述的方法。

第六方面，本申请实施例提供了一种计算机存储介质，包括指令，当其在计算机上运行时，使得计算机执行如第一方面中任意一项或第二方面中任意一项所述的方法。

第七方面，本申请实施例提供了一种包含指令的计算机程序产品，当其在计算机上运行时，使得该计算机执行如第一方面中任意一项或第二方面中任意一项所述的方法。

第八方面，本申请实施例提供了一种通信系统，包括如第三方面所述的第一路由器和如第四方面所述的第二路由器。

另外，第五方面至第八方面中所带来的技术效果可参见第一方面中任意一项或第二方面中任意一项中不同设计方式所带来的技术效果，此处不再赘述。

附图说明

为了更清楚地说明本申请实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍。

图1为本申请的实施例提供的Leaf-Spine拓扑的通信系统的结构示意图；

图2为本申请的实施例提供的Fat-Tree拓扑的通信系统的结构示意图；

图3为本申请的实施例提供的LSA发送方法的流程示意图一；

图4为本申请的实施例提供的LSA报文格式的示意图一；

图5为本申请的实施例提供的扩展后的LSU消息报文格式的示意图；

图6为本申请的实施例提供的LSA发送方法的流程示意图二；

图7为本申请的实施例提供的LSA发送方法的流程示意图三；

图8为本申请的实施例提供的LSA发送方法的流程示意图四；

图9为本申请的实施例提供的HELLO消息报文格式的示意图；

图10为本申请的实施例提供的LSA发送方法的流程示意图五；

图11为本申请的实施例提供的LSA报文格式的示意图二；

图12为本申请的实施例提供的LSA发送方法的流程示意图六；

图13为本申请的实施例提供的LSA发送方法的流程示意图七；

图14为本申请的实施例提供的完备拓扑下的Level_2层路由器作为通告路由器进行周期性LSA更新的示意图；

图15为本申请的实施例提供的LSA发送方法的流程示意图八；

图16为本申请的实施例提供的非完备拓扑下的Level_2层路由器作为通告路由器进行周期性LSA更新的示意图；

图17为本申请的实施例提供的LSA发送方法的流程示意图九；

图18为本申请的实施例提供的完备拓扑下的Level_1层路由器作为通告路由器进行周期性LSA更新的示意图；

图19为本申请的实施例提供的LSA发送方法的流程示意图十；

图20为本申请的实施例提供的非完备拓扑下的Level_1层路由器作为通告路由器进行周期性LSA更新的示意图；

图21为本申请的实施例提供的LSA发送方法的流程示意图十一；

图22为本申请的实施例提供的完备拓扑下的Level_0层路由器作为通告路由器进行周期性LSA更新的示意图；

图23为本申请的实施例提供的LSA发送方法的流程示意图十二；

图24为本申请的实施例提供的非完备拓扑下的Level_0层路由器作为通告路由器进行周期性LSA更新的示意图；

图25为本申请的实施例提供的LSA发送方法的流程示意图十三；

图26为本申请的实施例提供的非完备拓扑下的Level_0层路由器作为通告路由器进行周期性LSA更新的示意图；

图27为本申请的实施例提供的LSA发送方法的流程示意图十四；

图28为本申请的实施例提供的非完备拓扑下的Level_1层路由器与Level_2 层路由器之间链路故障进行事件性LSA更新的示意图；

图29为本申请的实施例提供的LSA发送方法的流程示意图十五；

图30为本申请的实施例提供的完备拓扑下的Level_1层路由器与Level_0层路由器之间链路故障进行事件性LSA更新的示意图；

图31为本申请的实施例提供的LSA发送方法的流程示意图十六；

图32为本申请的实施例提供的非完备拓扑下的Level_1层路由器与Level_0 层路由器之间链路故障进行事件性LSA更新的示意图；

图33为本申请的实施例提供的LSA发送方法的流程示意图十七；

图34为本申请的实施例提供的完备拓扑下的Level_2层路由器故障进行事件性LSA更新的示意图；

图35为本申请的实施例提供的LSA发送方法的流程示意图十八；

图36为本申请的实施例提供的完备拓扑下的Level_1层路由器故障进行事件性LSA更新的示意图；

图37为本申请的实施例提供的LSA发送方法的流程示意图十九；

图38为本申请的实施例提供的完备拓扑下的Level_0层路由器故障进行事件性LSA更新的示意图；

图39为本申请的实施例提供的LSA发送方法的流程示意图二十；

图40为本申请的实施例提供的路由器的结构示意图一；

图41为本申请的实施例提供的路由器的结构示意图二；

图42为本申请的实施例提供的路由器的结构示意图三。

具体实施方式

下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述。

为便于描述，本申请实施例将图2中所示的Fat-Tree拓扑中的核心网络21 称为层次2(Level_2)，将汇聚网络22称为层次1(Level_1)，将边缘网络(叶子节点)23称为层次0(Level_0)。由于Fat-Tree拓扑每个集群中的拓扑等效于图1中所示的Leaf-Spine拓扑，因此，可以将图1中所示的Leaf-Spine拓扑中脊 (Spine)节点11称为层次1，将叶子(Leaf)节点12称为层次0。示例性的，本申请实施例将以Fat-Tree拓扑中LSA的传播为例进行说明，其同样也可以应用于 Leaf-Spine拓扑或其他具有类似树形结构的拓扑中。

本申请实施例所述的层次位置信息指路由器在上述分层树形拓扑结构中的层次位置。示例性的，如图2中所示，路由器224的层次位置信息为层次2(Level_2)，路由器412的层次位置信息为层次1(Level_1)，路由器404的层次位置信息为层次0(Level_0)。

本申请实施例所述的完备拓扑指按规则Fat-Tree拓扑组网的拓扑。本申请实施例所述的非完备拓扑指相对于规则Fat-Tree拓扑，缺失其中某些链路或者节点的拓扑。本申请实施例所述的北向指从Level_0至Level_2方向，南向指从Level_2 至Level_0方向。

本申请实施例所述的第一路由器、第二路由器、第三路由器、第四路由器、第五路由器等，是根据在LSA传输路径上的相对位置(例如下一跳、上一跳、下下一跳、上上一跳等)来分类的路由器。示例性的，如图2中所示，路由器404、 412、224、111、101可以构成从路由器404至路由器101的一条LSA传输路径，路由器404、411、221、111、101可以构成从路由器404至路由器101的另一条 LSA传输路径。在实际传输过程中，可以根据算法从中选择一条路径进行传输。对于路由器404来说，可以选择向路由器411或412发送LSA，即路由器411或412均为路由器404的下一跳路由器，则路由器411和412可以归为一类路由器，示例性的，可以令路由器404作为第一路由器，令路由器411和412作为第二路由器。另外需要说明的是，该LSA传输路径可以是最短路径优先(Shortest Path First，SPF)路径。

本申请实施例所述的叶子节点指在LSA传输路径上不再转发LSA的路由器节点。本申请实施例所述的非叶子节点或者中间节点指在LSA传输路径上继续转发LSA的路由器节点。示例性的，如图2中所示，路由器404、412、224、111、 101可以构成从路由器404至路由器101的一条LSA传输路径，则路由器101为叶子节点，路由器412、224、111为非叶子节点。

本申请实施例所述的周期性进行链路状态更新指路由器周期性检查其与邻居路由器之间的链路状态。本申请实施例所述的邻居路由器指与本路由器直连的路由器，示例性的，参照图2中所示，路由器412与224互为邻居路由器，路由器 412与112互相不为邻居路由器。本申请实施例所述的链路状态发生改变包括邻居路由器之间的链路断开、路由器节点故障、路由器接入网络等。

本申请实施例所述的路径表也可以被称为洪泛优化路径表(FloodingOptimization Reflector List，FORL)。

本申请实施例所述的LSA发送方法、装置和系统，应用于上述Fat-Tree拓扑、Leaf-Spine拓扑或其他类似树形拓扑结构中，当链路状态发生改变或周期性进行链路状态更新时，通告路由器生成LSA，该LSA中包括通告路由器与其邻居路由器之间的有效链路。通告路由器向邻居路由器发送该LSA，由邻居路由器根据LSA 更新其LSDB后，继续转发LSA。本申请实施例的目的在于在LSA转发过程中尽量减少LSA发送次数。

本申请实施例提供一种LSA发送方法，参照图3中所示，该方法包括：

S101、当第一路由器判断第二路由器是非叶子节点时，执行步骤S102-S106，当第一路由器判断第二路由器是叶子节点时，执行步骤S107-S109。

第二路由器是与第一路由器之间链路有效的邻居路由器。在LSA传输路径上，第一路由器作为发送LSA的路由器，第二路由器作为从第一路由器接收LSA 的下一跳路由器。

第二路由器为非叶子节点，是指第二路由器还可以继续转发由第一路由器发送的LSA；第二路由器为叶子节点，是指第二路由器不能继续转发由第一路由器发送的LSA。

判断第二路由器为叶子节点或非叶子节点的方式可以包括：第二路由器位于Level_0层，此时第二路由器可以作为叶子节点；第二路由器除了第一路由器没有其他链路有效的邻居路由器，此时第二路由器可以作为叶子节点，否则第二路由器可以作为非叶子节点；在LSA传输路径上，多个第二路由器具有共同的下一跳邻居路由器，则可以选择其中至少一个第二路由器作为非叶子节点，其余第二路由器作为叶子节点。

S102、第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表。

第三路由器是与第二路由器之间链路有效的邻居路由器中，除了第一路由器以外的路由器。在LSA传输路径上，第一路由器作为发送LSA的路由器，第二路由器作为从第一路由器接收并转发LSA的下一跳路由器，第三路由器作为从第二路由器接收并转发LSA的下下一跳路由器。

限定第三路由器与第一路由器不同是为了防止通过第二路由器转发后，将 LSA回传至第一路由器。示例性的，如图2中所示，假设路由器404为第一路由器，路由器412为第二路由器，路由器221和224均可以作为第三路由器，但是路由器404不能作为第三路由器，可以防止LSA回传至路由器404。

第一路径表包括至少一个第三路由器的标识，第一路径表中的标识用于指示向对应路由器发送第一LSA。第一路径表可以包括部分或全部第三路由器的标识。第一路径表中的标识实际对应第二路由器的下一跳邻居路由器的标识。示例性的，如图2中所示，假设路由器404为第一路由器，路由器412为第二路由器，路由器221和224为第三路由器，如果生成的第一路径表中只包括路由器221的标识，则表明路由器404指示路由器412仅向路由器221转发第一LSA，如果生成的第一路径表中包括路由器221和224的标识，则表明路由器404指示路由器412向路由器221和224均转发第一LSA。

第一LSA包括通告路由器与其邻居路由器之间的有效链路，通告路由器指当链路状态发生改变或周期性进行链路状态更新而生成LSA的路由器。示例性的，参照图2中所示，如果路由器101是通告路由器，则其所生成的LSA中包括路由器101与111之间的有效链路以及路由器101与112之间的有效链路。参照图4 中所示，为LSA报文格式的示意图，LSA包括通告路由器的标识和与该通告路由器链路有效的邻居路由器的标识(即图中的Link ID)链路ID。

可选的，第一路由器可以为通告路由器，即第一LSA由第一路由器生成，则第一LSA中包括第一路由器与其邻居路由器之间的有效链路；或者，第一路由器也可以为LSA传输路径上的中间节点的路由器，即第一LSA不由第一路由器生成，而是由第一路由器进行转发。示例性的，参照图2中所示，假设路由器404 为第一路由器并且为通告路由器，则第一LSA中包括：路由器404的标识，以及与路由器404链路有效的邻居路由器411和412的标识。假设路由器412为第一路由器，路由器404为通告路由器，第一LSA中同样包括：路由器404的标识，以及与路由器404链路有效的邻居路由器411和412的标识。

对于第一路由器如何获取第二路由器的层次位置信息以及第三路由器的层次位置信息将在后面进行详细介绍。

S103、第一路由器向第二路由器发送第一链路状态更新(Link State Update，LSU)消息，其中，第一LSU消息中包括第一LSA和第一路径表。

LSU消息是OSPF协议中的一种报文，可以用于封装LSA。本申请实施例对 LSU消息进行扩展，参照图5中所示，扩展后的LSU消息报文包括OSPF报头、路径表和LSA。路径表包括标志位F、路由器ID数量N以及路由器ID0至路由器ID(N-1)。

其中，标志位F用于表示是否携带路径表信息，例如，F＝0可以表示不携带路径表信息，F＝1可以表示携带路径表信息，或者相反地，F＝1可以表示不携带路径表信息，F＝0可以表示携带路径表信息。

路由器ID数量N用于表示路径表中包括路由器ID的数量。

路由器ID0至路由器ID(N-1)用于表示具体的路由器ID，如前所述，其可以包括第三路由器中的部分或全部路由器的标识。

需要说明的是路径表也可以位于LSA之后。

S104、第二路由器从第一路由器接收第一LSU消息。

S105、第二路由器根据第一LSA更新其LSDB。

具体的，第二路由器用通告路由器所产生的第一LSA更新第二路由器保存的LSDB。LSDB通过不断更新可以获得整个网络的拓扑。

S106、第二路由器向第一路径表中的标识对应的路由器发送第一LSA。

该第一LSA同样可以在LSU消息中携带。

如前面示例所述，假设路由器404为第一路由器，路由器412为第二路由器，如果路由器404向路由器412发送的第一路径表中只包括路由器221的标识，则路由器412仅向路由器221转发第一LSA，如果第一路径表中包括路由器221和 224的标识，则路由器412向路由器221和224均转发第一LSA。

需要说明的是，步骤S105和S106没有先后执行顺序。

以上步骤S102-S106是第二路由器为非叶子节点的分支，下面的步骤 S107-S09是第二路由器为叶子节点的分支。

S107、第一路由器向第二路由器发送第二LSU消息，其中，第二LSU消息中包括第一LSA。

该步骤与步骤S103的区别在于，由于不需要第二路由器按照路径表转发 LSA，所以不需要在LSU消息中携带路径表。

S108、第二路由器从第一路由器接收第二LSU消息。

S109、第二路由器根据第一LSA更新其LSDB。

该步骤与S105相同。

本申请实施例提供的LSA发送方法，发送LSA的路由器根据其层次位置信息、下一跳路由器的层次位置信息和下下一跳路由器的层次位置信息，生成路径表，发送LSA的路由器向下一跳路由器发送LSA的同时发送该路径表，由于该路径表中包括下下一跳路由器的标识，指示下一跳路由器向对应的下下一跳路由器转发LSA，直到作为叶子节点的路由器接收到LSA后不作转发。通过发送LSA 的路由器指示下一跳路由器有选择地向下下一跳路由器转发LSA，减少了LSA的发送次数，避免下下一跳路由器重复收到LSA。

可选的，在一种实施方式中，参照图6中所示，当第一路由器为LSA传输路径上的中间节点的路由器时，该方法还包括步骤S121和S122：

S121、第一路由器从第四路由器接收第三LSU消息，第三LSU消息中包括第一LSA，其中，第四路由器是与第一路由器之间链路有效的邻居路由器中，除了第二路由器以外的路由器。

第四路由器可以是通告路由器，第一LSA由第四路由器生成；或者，与第一路由器一样是LSA传输路径上的中间节点的路由器，即第一LSA不由第四路由器生成，而是由第四路由器进行转发。与步骤S102中对第三路由器的限定类似的，限定第四路由器与第二路由器不同同样是为了防止通过第一路由器转发后，LSA 回传至第四路由器。

S122、第一路由器根据第一LSA更新其LSDB。

该步骤与S105类似，在此不再赘述。需要说明的是，步骤S122与步骤 S101-S109之间没有先后执行顺序。

该实施方式提供了第一路由器不是通告路由器时，如何获取LSA的一种方式。

基于图6所述方法进一步可选的，在一种实施方式中，参照图7中所示，步骤S103具体包括：

S1031、当第二LSU消息中还包括第二路径表时，第一路由器向第二路由器发送第一LSU消息，其中，第二路径表中包括至少一个第二路由器的标识，第二路径表中的标识用于指示向对应路由器发送第一LSA。

该步骤相当于第一路由器根据接收到的LSU消息中是否有路径表，来决定是否可以继续转发其中的LSA。当接收到LSU消息中有路径表时，根据路径表转发 LSU消息中的LSA；当接收到LSU消息中没有路径表时，不转发LSU消息中的 LSA。

第二路径表可以包括部分或全部第二路由器的标识。第二路径表中的标识实际对应第一路由器的下一跳邻居路由器的标识。

可选地，当第二LSU消息中不包括第二路径表时，第一路由器不向第二路由器发送第一LSU消息，即不转发LSA。

该实施方式提供了第一路由器根据接收到的LSU消息中是否有路径表，来决定是否转发其中的LSA。

可选的，在一种实施方式中，参照图8中所示，该方法还包括步骤S151，步骤S106具体包括步骤S1061：

S151、第二路由器根据其层次位置信息、第三路由器的层次位置信息和至少一个第五路由器的层次位置信息，生成第三路径表。

其中，第三路径表包括至少一个第五路由器的标识，第三路径表中的标识用于指示向对应路由器发送第一LSA，第五路由器是与第三路由器之间链路有效的邻居路由器中，除了第二路由器以外的路由器。

该步骤与S102类似，在此不再赘述。

S1061、第二路由器向第一路径表中的标识对应的路由器发送第四LSU消息，其中，第四LSU消息中包括第一LSA和第三路径表。

该步骤与S103类似，在此不再赘述。

该实施方式提供了第二路由器向第三路由器发送LSA和路径表的一种方式。

下面介绍本路由器如何获取其他路由器的层次位置关系：

可选的，在一种实施方式中，对于邻居路由器之间来说，本申请实施例对OSFP 协商消息——HELLO消息进行扩展，HELLO消息用于建立和维护邻居路由器之间的邻居关系，路由器的所有接口周期性向外发送HELLO消息。

参照图9中所示，为HELLO消息报文格式的示意图，其中的可选项共8比特位，其中有5个比特位已经使用，还剩余3个比特位(图中*所示)，本申请实施例将其中两个比特位表示为层次位置信息LC，剩余一个比特位表示为标志位 H。

其中，标志位H用于表示本路由器是否需要层次化设置，例如，H＝0可以表示本路由器无需层次化设置，H＝1可以表示本路由器需要层次化设置，或者相反地，H＝1可以表示本路由器无需层次化设置，H＝0可以表示本路由器需要层次化设置。

层次位置信息LC用于表示本路由器位于分层树形拓扑结构中的层次位置，例如，LC＝1可以表示本路由器位于Level_0层，LC＝2可以表示本路由器位于 Level_1层，LC＝3可以表示本路由器位于Level_2层。或者LC可以按照其他方式取0-3中不同值来表示本路由器位于不同层，本申请实施不作限定。

参照图10中所示，在步骤S101之前，该方法还包括步骤S161-S164：

S161、第一路由器向第二路由器发送第一OSPF协商消息。

其中，第一OSPF协商消息中包括第一路由器的层次位置信息。第一OSPF 协商消息可以是上述HELLO消息。该步骤使得第二路由器获知第一路由器的层次位置信息。

S162、第二路由器从第一路由器接收第一OSPF协商消息。

S163、第二路由器向第一路由器发送第二OSPF协商消息。

其中，第二OSPF协商消息中包括第二路由器的层次位置信息。第二OSPF 协商消息可以是上述HELLO消息。第一OSPF协商消息和第二OSPF协商消息用于建立和维护第一路由器与第二路由器的邻居关系。该步骤使得第一路由器获知第二路由器的层次位置信息。

S164、第一路由器从第二路由器接收第二OSPF协商消息。

需要说明的是，本申请实施例虽然仅示例性地说明以第一路由器与第二路由器之间互相发送和接收HELLO消息的方式，来获取对方的层次位置信息，但是可以理解的是，对于其他互为邻居路由器的路由器之间同样可以通过该方式来获取对方的层次位置信息。

该实施方式提供了邻居路由器之间互相获取对方层次位置信息的一种方式。

可选的，在另一种实施方式中，对于间隔了一个邻居路由器的非邻居路由器之间来说，本申请实施例对图4中所示的LSA报文格式进行扩展：参照图11中所示，一方面，在LSA中添加通告路由器的层次位置信息的字段。另一方面，由于Link ID用于标识与通告路由器链路有效的邻居路由器的标识，因此可以针对每个Link ID添加一个层次位置信息的字段，来表示与通告路由器链路有效的邻居路由器的层次位置信息。需要说明的是，LSA可以同时包括这两个字段，或者可以只包括其中一个字段，最终使得LSA中包括通告路由器的层次位置信息和/ 或与通告路由器链路有效的邻居路由器的层次位置信息。

对于步骤S102中所述的第一路由器获取第二路由器的层次位置信息以及第三路由器的层次位置信息来说，可选的，参照图12中所示，在步骤S102之前，该方法还包括S171：

S171、第一路由器从第二路由器接收第二LSA，第二LSA包括第二路由器的层次位置信息和/或至少一个第三路由器的层次位置信息。

可以将第二路由器作为通告路由器，将第三路由器作为与第二路由器链路有效的邻居路由器，由第二路由器生成并向第一路由器发送LSA，该LSA中携带第二路由器的层次位置信息和/或至少一个第三路由器的层次位置信息。或者，可以将第三路由器作为通告路由器，将第二路由器作为与第三路由器链路有效的邻居路由器，由第二路由器向第一路由器转发由第三路由器生成的LSA，该LSA中携带第二路由器的层次位置信息和/或至少一个第三路由器的层次位置信息。

对于步骤S151中所述的第二路由器获取第三路由器的层次位置信息以及第五路由器的层次位置信息来说，可选的，参照图13中所示，在步骤S151之前，该方法还包括S181：

S181、第二路由器从第三路由器接收第三LSA，第三LSA包括第三路由器的层次位置信息和/或至少一个第五路由器的层次位置信息。

该步骤与S171类似，在此不再赘述。

该实施方式提供了间隔一个邻居路由器的非邻居路由器之间互相获取对方层次位置信息的一种方式。

如表1所示，下面结合一些具体实施方式对上述方法进行详细说明。

表1

方式一、参照图14中所示，为完备拓扑下的Level_2层路由器作为通告路由器进行周期性LSA更新的示意图，结合图15中所示，该LSA发送方法可以包括：

S201、Level_2层路由器224作为通告路由器生成LSA。

该LSA中包括路由器224的标识以及路由器112、212、312、412的标识。该LSA还可以包括路由器224的层次位置信息以及路由器112、212、312、412 的层次位置信息。

S202、因为Level_1层路由器112、212、312、412是非叶子节点，因此路由器224针对邻居路由器112、212、312、412分别生成路径表。

也就是说，针对每个邻居路由器所生成的路径表都不相同。

示例性的，对于针对路由器112生成的路径表来说，路由器224需要结合其位于Level_2层，路由器112位于Level_1层，路由器101-104位于Level_0层来生成路径表，该路径表中包括路由器101-104的标识。针对其他邻居路由器生成路径表的方法类似，具体不再赘述。

此时，Level_2层路由器224对应步骤S102中所述的第一路由器，Level_1 层路由器112、212、312、412对应步骤S102中所述的第二路由器，Level_0层路由器224对应步骤S102中所述的第三路由器。

S203、路由器224向南向Level_1层路由器112、212、312、412分别发送 LSU消息，各LSU消息中包括LSA以及针对邻居路由器112、212、312、412分别生成的路径表。

也就是说，针对每个邻居路由器所发送的LSU消息中LSA相同，但路径表都不相同。

示例性的，路由器224向路由器112发送的LSU消息中的路径表包括路由器 101-104的标识，路由器224向路由器212发送的LSU消息中的路径表包括路由器201-204的标识，依此类推。

此时，Level_2层路由器224对应步骤S103中所述的第一路由器，Level_1 层路由器112、212、312、412对应步骤S103中所述的第二路由器。

S204、Level_1层路由器接收到上述LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

示例性的，路由器112接收到针对其发送的LSU消息后，根据LSA更新本地LSDB。

此时，Level_1层路由器对应步骤S104和S105中所述的第二路由器。

S205、因为Level_0层路由器是叶子节点，因此Level_1层路由器向路径表的标识对应的南向Level_0层路由器发送LSU消息，LSU消息中只包括LSA不包括路径表。

示例性的，Level_1层路由器112接收到针对其发送的LSU消息后，根据LSA 更新本地LSDB。Level_0层路由器为叶子节点，因此路由器112向路由器101-104 发送LSU消息，该LSU消息中包括LSA但不包括路径表。

此时，Level_1层路由器112可以对应步骤S106中所述的第二路由器，Level_0 层路由器对应步骤S106中所述的第三路由器；Level_1层路由器112还可以对应步骤S107中所述的第一路由器，Level_0层路由器对应步骤S107中所述的第二路由器。

S206、Level_0层路由器接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

示例性的，路由器101-104分别收到LSU消息中LSA后，仅根据LSA更新本地LSDB，终止该LSA进一步转发。

此时，Level_0层路由器对应S108和S109中所述的第二路由器。

方式一的技术效果：

(1)确保了Level_0层路由器知道通过Level_2层路由器224可以到达其他集群(Pod)的哪些Level_0层路由器。

(2)与Level_2层路由器224不是邻居的Level_1层路由器(包括111、211、 311、411)不用接收到其发送的LSA，因为这些路由器上的路由表项不会根据路由器224发送的LSA发生任何更改，即经过这些路由器处理的数据包下一跳不会经过路由器224，也不会直接从路由器224接收到数据包。

(3)其他Level_2层路由器(如221、222、223)不用接收到路由器224发送的LSA，因为这些路由器上的路由表项不会根据224发送的LSA发生任何更改，即经过这些路由器处理的数据包下一跳不会经过路由器224，也不会直接从路由器224接收到数据包。

该实施例既保证了Level_2层路由器224生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式一区别于现有技术的改进之处包括：

(1)不需要每个路由器维护完全相同的LSDB信息。

(2)某个路由器生成的LSA不一定需要泛洪至其他所有路由器。

(3)避免了某个路由器重复接收相同的LSA。

方式二、参照图16中所示，为非完备拓扑下的Level_2层路由器作为通告路由器进行周期性LSA更新的示意图，与图14相比较，缺少路由器224与212之间的链路。结合图17中所示，该LSA发送方法可以包括：

S301、Level_2层路由器224作为通告路由器生成LSA。

该LSA中包括路由器224的标识以及路由器112、312、412的标识。该LSA 还可以包括路由器224的层次位置信息以及路由器112、312、412的层次位置信息。

S302、因为Level_1层路由器112、312、412是非叶子节点，路由器224针对邻居路由器112、312、412分别生成路径表。

该步骤与S202的区别在于不需要针对路由器212生成路径表。

S303、路由器224向南向Level_1层路由器112、312、412分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器112、312、412分别生成的路径表。

该步骤与S203的区别在于不需要向路由器212发送LSU消息。

S304、Level_1层路由器接收到上述LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

该步骤与S204的区别在于路由器212不会收到LSU消息，不会更新本地 LSDB。

S305、因为Level_0层路由器是叶子节点，Level_1层路由器向路径表的标识对应的南向Level_0层路由器发送LSU消息，LSU消息中只包括LSA不包括路径表。

该步骤与S205的区别在于路由器212不会向南向Level_0层邻居路由器发送 LSA。

S306、Level_0层路由器接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

该步骤与S206的区别在于路由器201-204不会收到LSA。

方式二的技术效果：

(1)确保了Level_0层路由器知道通过Level_2层路由器224可以到达其他集群(Pod)的哪些Level_0层路由器。

(2)不是Level_2层路由器下下一跳邻居的Level_0层路由器(包括201、 202、203及204)不用接收到其发送的LSA，因为这些路由器处理的数据包下下一跳不会经过路由器224，也不会接收从路由器224经过2跳发来的数据包，即这些叶子节点到其他集群(Pod)的数据包不会经过路由器224转发。

(3)与Level_2层路由器224不是邻居的Level_1层路由器(包括111、211、 212、311、411)不用接收到其发送的LSA，因为这些路由器上的路由表项不会根据路由器224发送的LSA发生任何更改，即经过这些路由器处理的数据包下一跳不会经过路由器224，也不会直接从路由器224接收到数据包。

(4)其他Level_2层路由器(如221、222、223)不用接收到路由器224发送的LSA，因为这些路由器上的路由表项不会根据224发送的LSA发生任何更改，即经过这些路由器处理的数据包下一跳不会经过224路由器，也不会直接从224 路由器接收到数据包。

该实施例既保证了Level_2层路由器224生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式二区别于现有技术的改进之处见方式一，在此不再赘述。

方式三、参照图18中所示，为完备拓扑下的Level_1层路由器作为通告路由器进行周期性LSA更新的示意图，结合图19中所示，该LSA发送方法可以包括：

S401、Level_1层路由器412作为通告路由器生成LSA。

该LSA中包括路由器412的标识以及路由器224、222、401-404的标识。该 LSA还可以包括路由器412的层次位置信息以及路由器224、222、401-404的层次位置信息。

Level_1层路由器生成LSA后，判断是否为它与北向Level_2层路由器间的链路故障触发的LSA更新，如果是，则不需要向Level_2层路由器发送该LSA，如果不是，才需要发送LSA。

需要说明的是，路由器222与224是等价的，可以选择其中一个作为叶子节点，另一个作非叶子节点。

S402、因为Level_2层路由器224以及Level_0层路由器401-404是叶子节点，因此路由器412向路由器224、401-404分别发送LSU消息，各LSU消息中仅包括上述LSA不包括路径表。

此时，路由器412对应步骤S107中所述的第一路由器，Level_2层路由器224 以及Level_0层路由器401-404对应步骤S107中所述的第二路由器。

S403、路由器224、401-404分别接收到LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_2层路由器224以及Level_0层路由器401-404对应步骤S108 和S109中所述的第二路由器。

S404、因为Level_2层路由器222是非叶子节点，因此路由器412针对邻居路由器222生成路径表。

示例性的，对于针对路由器222生成的路径表来说，路由器412需要结合其位于Level_1层，路由器222位于Level_2层，路由器112、212、312位于Level_1 层来生成路径表，该路径表中包括路由器112、212、312的标识。

此时，Level_1层路由器412对应步骤S102中所述的第一路由器，Level_2 层路由器222对应步骤S102中所述的第二路由器，Level_1层路由器112、212、 312对应步骤S102中所述的第三路由器。

S405、路由器412向路由器222发送LSU消息，LSU消息中包括LSA以及上述路径表。

通过该路径表，路由器412告知路由器222将接收到的LSA进一步发送到其南向Level_1层邻居路由器112、212及312。

此时，Level_1层路由器412对应步骤S103中所述的第一路由器，Level_2 层路由器222对应步骤S103中所述的第二路由器。

S406、路由器222接收到LSU消息后，根据LSA更新本地LSDB，并根据 LSU消息中包括路径表确定转发LSA。

此时，Level_2层路由器222对应步骤S104和S105中所述的第二路由器。

S407、因为Level_1层路由器112、212及312是非叶子节点，因此路由器 222针对邻居路由器112、212及312分别生成路径表。

示例性的，对于针对路由器112生成的路径表来说，路由器222需要结合其位于Level_2层，路由器112位于Level_1层，路由器101-104位于Level_0层来生成路径表，该路径表中包括路由器101-104的标识。针对其他邻居路由器生成路径表的方法类似，具体不再赘述。

此时，Level_2层路由器222对应步骤S102中所述的第一路由器，Level_1 层路由器112、212及312对应步骤S102中所述的第二路由器，Level_0层路由器对应步骤S102中所述的第三路由器。

S408、路由器222向南向Level_1层路由器112、212、312分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器112、212、312分别生成的路径表。

此时，Level_2层路由器222对应步骤S103中所述的第一路由器，Level_1 层路由器112、212及312对应步骤S103中所述的第二路由器。

S409、Level_1层路由器112、212、312接收到上述LSU消息后，根据LSA 更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

此时，Level_1层路由器112、212及312对应步骤S104和S105中所述的第二路由器。

S410、因为Level_0层路由器是叶子节点，Level_1层路由器112、212、312 向路径表的标识对应的南向Level_0层路由器发送LSU消息，LSU消息中只包括 LSA不包括路径表。

此时，Level_1层路由器112、212及312对应步骤S106中所述的第二路由器，Level_0层路由器对应步骤S106中所述的第三路由器；或者，Level_1层路由器112、212及312对应步骤S107中所述的第一路由器，Level_0层路由器对应步骤S107中所述的第二路由器。

S411、Level_0层路由器接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_0层路由器对应S108和S109中所述的第二路由器。

方式三的技术效果：

(1)确保了Level_0层路由器知道Level_1层路由器的最新状态信息，以便调整自己到其他Level_0层路由器的路由表项。

(2)与Level_1层路由器412不是邻居的Level_2层路由器(包括221、223) 不用接收到其发送的送LSA，因为这些路由器上的路由表项不会根据路由器412 发送的LSA发生任何更改，即经过这些路由器处理的数据包下一跳不会经过路由器412，也不会直接从路由器412接收到数据包。

(3)不是路由器412下下一跳的Level_1路由器(如111、211、311)不用接收到路由器412生成的LSA，因为这些节点上的路由表项不会根据路由器412 生成的LSA发生任何更改，即经过这些路由器处理的数据包下下一跳不会经过路由器224，也不会接收到从路由器224经由2跳发来的数据包；尽管从拓扑上看路由器411是路由器412的下下一跳节点，但是实际的集群(Pod)4中的流量不会经过Level_0层路由器、411、Level_0层路由器、412、Level_0层路由器这样迂回传送，集群(Pod)4中的Level_0层路由器间的流量要么只经过路由器411 中转，要么只经过路由器412中转，所以路由器411也没有必要接收到路由器412生成的LSA。

该实施例既保证了Level_1层路由器412生成的LSA在网络中的必要更新，又避免了不必要的重复/冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式二区别于现有技术的改进之处见方式一，在此不再赘述。

方式四、参照图20中所示，为非完备拓扑下的Level_1层路由器作为通告路由器进行周期性LSA更新的示意图，与图18相比较，缺少路由器222与312之间的链路。结合图21中所示，该LSA发送方法可以包括：

S501、Level_1层路由器412作为通告路由器生成LSA。

该步骤与S401相同，在此不再赘述。

S502、因为Level_0层路由器401-404是叶子节点，因此路由器412向路由器401-404分别发送LSU消息，各LSU消息中仅包括上述LSA不包括路径表。

该步骤与S402的区别在于，由于缺少了路由器222与312之间的链路，仅有路由器224与312之间的链路，因此路由器224作为非叶子节点。

S503、路由器401-404分别接收到LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

该步骤与S403的区别在于此时路由器224不会收到LSU消息。

S504、因为Level_2层路由器222、224是非叶子节点，因此路由器412针对邻居路由器222、224分别生成路径表。

该步骤与S404的区别在于此时路由器412还要针对路由器224生成路径表。

S505、路由器412向路由器222、224分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器222、224分别生成的路径表。

该步骤与S405的区别在于此时路由器412向路由器224发送的LSU消息中包括路径表。

S506、路由器222、224分别接收到LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

该步骤与S406的区别在于此时路由器224也会接收到LSU消息。

S507、因为Level_1层路由器112、212及312是非叶子节点，因此路由器 222针对邻居路由器112、212分别生成路径表，路由器224针对邻居路由器312 生成路径表。

该步骤与S407的区别在于此时路由器312在路由器224的下一跳。

S508、路由器222向南向Level_1层路由器112、212分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器112、212分别生成的路径表，路由器224向南向Level_1层路由器312发送LSU消息，LSU消息中包括LSA以及针对邻居路由器312生成的路径表。

该步骤与S408的区别在于此时路由器312在路由器224的下一跳。

步骤S509-S511与步骤S409-S411相同，在此不再赘述。

方式四的技术效果：

(1)确保了Level_0层路由器知道Level_1层路由器的最新状态信息，以便调整自己到其他Level_0层路由器的路由表项。

(2)与Level_1层路由器412不是邻居的Level_2层路由器(包括221、223) 不用接收到其发送的LSA，因为这些路由器上的路由表项不会根据412发送的 LSA发生任何更改，即经过这些路由器处理的数据包下一跳不会经过路由器412，也不会直接从路由器412接收到数据包。

(3)不是路由器412下下一跳的Level_1层路由器(如111、211、311)不用接收到路由器412生成的LSA，因为这些路由器上的路由表项不会根据412生成的LSA发生任何更改，即经过这些路由器处理的数据包下下一跳不会经过路由器224，也不会接收到从路由器224经由2跳发来的数据包；尽管从拓扑上看路由器411是412的下下一跳路由器，但是实际的集群(Pod)4中的流量不会经过 Level_0层路由器、411、Level_0层路由器、412、Level_0层路由器这样迂回传送，集群(Pod)4中的Level_0层路由器间的流量要么只经过路由器411中转，要么只经过路由器412中转，所以路由器411也没有必要接收到路由器412生成的 LSA。

该实施例既保证了Level_1层路由器412生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式四区别于现有技术的改进之处见方式一，在此不再赘述。

方式五、参照图22中所示，为完备拓扑下的Level_0层路由器作为通告路由器进行周期性LSA更新的示意图，结合图23中所示，该LSA发送方法可以包括：

S601、Level_0层路由器404作为通告路由器生成LSA。

该LSA中包括路由器404的标识以及路由器411、412的标识。该LSA还可以包括路由器404的层次位置信息以及路由器411、412的层次位置信息。

S602、因为Level_2层路由器411、412是非叶子节点，因此路由器404针对邻居路由器411、412分别生成路径表。

示例性的，对于针对路由器412生成的路径表来说，路由器404需要结合其位于Level_0层，路由器412位于Level_1层，路由器222、224位于Level_2层，路由器403位于Level_0层来生成路径表，该路径表中包括路由器222、224、403 的标识。

此时，Level_0层路由器404对应步骤S102中所述的第一路由器，Level_1 层路由器411对应步骤S102中所述的第二路由器，Level_2层路由器221、223 和Level_0层路由器401、402对应步骤S102中所述的第三路由器；Level_1层路由器412对应步骤S102中所述的第二路由器，Level_2层路由器222、224和Level_0 层路由器403对应步骤S102中所述的第三路由器。

需要说明的是，路由器401-403是等价的，路由器411-412是等价的，因此二者之间的组合是任意的。例如，可以路由器401-403与411组合；或者，路由器401和403与411组合，路由器402与422组合。路由器222与224是等价的，因此可以选择其中一个作叶子节点，另一个作非叶子节点。路由器221与223是等价的，因此可以选择其中一个作叶子节点，另一个作非叶子节点。

S603、路由器404向Level_1层路由器411、412发送LSU消息，LSU消息中包括LSA以及上述路径表。

通过上述路径表，路由器404告知路由器411将接收到的LSA进一步发送到其北向Level_1层邻居路由器221、223以及南向Level_1层邻居路由器401、402；路由器404告知412将接收到的LSA进一步发送到其南向Level_0层邻居路由器 403及北向Level_2层邻居路由器222、224。

此时，Level_0层路由器404对应步骤S103中所述的第一路由器，Level_1 层路由器411、412对应步骤S103中所述的第二路由器，Level_2层路由器221-224 和Level_0层路由器401-403对应步骤S103中所述的第三路由器。

S604、Level_1层路由器411、412接收到LSU消息后，根据LSA更新本地 LSDB，并根据LSU消息中包括路径表确定转发LSA。

此时，Level_1层路由器411、412对应步骤S104和S105中所述的第二路由器。

S605、因为Level_0层路由器以及Level_2层路由器224和223是叶子节点， Level_1层路由器411、412向路径表的标识对应的路由器发送LSU消息，LSU消息中只包括LSA不包括路径表。

Level_1层路由器411向路径表的标识对应的路由器401、402和北向Level_0 层路由器223发送LSU消息，LSU消息中只包括LSA不包括路径表；Level_1层路由器412向路径表的标识对应的南向Level_0层路由器403以及北向Level_2 层路由器224发送LSU消息，LSU消息中只包括LSA不包括路径表。

此时，Level_1层路由器411、412对应步骤S106中所述的第二路由器，Level_0 层路由器401-403以及Level_2层路由器224和223对应步骤S106中所述的第三路由器；或者，Level_1层路由器411、412对应步骤S107中所述的第一路由器， Level_0层路由器401-403以及Level_2层路由器224和223对应步骤S107中所述的第二路由器。

S606、Level_0层路由器及路由器223、224接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_0层路由器及路由器223、224对应S108和S109中所述的第二路由器。

S607、因为Level_2层路由器221是非叶子节点，因此路由器411针对邻居路由器221生成路径表；因为Level_2层路由器222是非叶子节点，因此路由器 412针对邻居路由器222生成路径表。

示例性的，对于针对路由器222生成的路径表来说，路由器412需要结合其位于Level_1层，路由器222位于Level_2层，路由器112、212、312位于Level_1 层来生成路径表，该路径表中包括路由器112、212、312的标识。针对其他邻居路由器生成路径表的方法类似，具体不再赘述。

此时，Level_1层路由器411和412对应步骤S102中所述的第一路由器， Level_2层路由器221和222对应步骤S102中所述的第二路由器，Level_1层路由器对应步骤S102中所述的第三路由器。

S608、Level_1层路由器411、412向北向Level_2层路由器分别发送LSU消息，各LSU消息中包括LSA以及针对各路由器分别生成的路径表。

Level_1层路由器411向北向Level_2层路由器221发送LSU消息，LSU消息中包括LSA以及针对邻居路由器221生成的路径表；Level_1层路由器412向北向Level_2层路由器222发送LSU消息，LSU消息中包括LSA以及针对邻居路由器222生成的路径表

此时，Level_1层路由器411、412对应步骤S103中所述的第一路由器，Level_2 层路由器221和222对应步骤S103中所述的第二路由器。

S609、Level_2层路由器221和222接收到上述LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

此时，Level_2层路由器221和222对应步骤S104和S105中所述的第二路由器。

S610、因为Level_1层路由器112、211、311是非叶子节点，因此路由器221 针对邻居路由器211、211、311生成路径表，路由器222针对邻居路由器112、 212、312生成路径表。

此时，Level_2层路由器221和222对应步骤S102中所述的第一路由器， Level_1层路由器112、211、311对应步骤S102中所述的第二路由器，Level_0 层路由器对应步骤S102中所述的第三路由器。

S611、Level_2层路由器221向南向Level_1层路由器111、211、311分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器111、211、311分别生成的路径表。Level_2层路由器222向南向Level_1层路由器112、212、312分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器112生成的路径表。

此时，Level_2层路由器221和222对应步骤S103中所述的第一路由器， Level_1层路由器111、211、311、112、212、312对应步骤S103中所述的第二路由器。

S612、Level_1层路由器111、211、311、112、212、312接收到上述LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

此时，Level_1层路由器111、211、311、112、212、312对应步骤S104和 S105中所述的第二路由器。

S613、因为Level_0层路由器是叶子节点，Level_1层路由器111、211、311、 112、212、312向路径表的标识对应的南向Level_0层路由器发送LSU消息，LSU 消息中只包括LSA不包括路径表。

此时，Level_1层路由器111、211、311、112、212、312对应步骤S106中所述的第二路由器，Level_0层路由器对应步骤S106中所述的第三路由器；或者， Level_1层路由器111、211、311、112、212、312对应步骤S107中所述的第一路由器，Level_0层路由器对应步骤S107中所述的第二路由器。

S614、Level_0层路由器接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_0层路由器对应S108和S109中所述的第二路由器。

方案五的技术效果

确保了其他Level_0层路由器知道通告路由器Level_0层路由器的最新状态信息，以便调整自己到其他Level_0层路由器的路由表项。

该实施例既保证了Level_0层路由器404生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式五区别于现有技术的改进之处见方式一，在此不再赘述。

方式六、参照图24中所示，为非完备拓扑下的Level_0层路由器作为通告路由器进行周期性LSA更新的示意图，与图22相比较，缺少路由器221与311之间的链路、路由器222与312之间的链路、路由器223与211之间的链路、路由器224与212之间的链路、路由器111与104之间的链路、路由器112与101之间的链路、路由器311与304之间的链路、路由器312与301之间的链路、路由器412与401之间的链路、路由器412与402之间的链路、路由器311与221之间的链路。结合图25中所示，该LSA发送方法可以包括：

步骤S701-S704与步骤S601-S604相同，在此不再赘述。

S705、因为Level_0层路由器是叶子节点，Level_1层路由器411、412向路径表的标识对应的路由器发送LSU消息，LSU消息中只包括LSA不包括路径表。

Level_1层路由器411向路径表的标识对应的南向Level_0层路由器401、402 发送LSU消息，LSU消息中只包括LSA不包括路径表；Level_1层路由器412向路径表的标识对应的南向Level_0层路由器403发送LSU消息，LSU消息中只包括LSA不包括路径表

该步骤与S605的区别在于，由于缺少了路由器222与312之间的链路，仅有路由器224与312之间的链路，因此路由器224作为非叶子节点；由于缺少了路由器311与221之间的链路，仅有路由器223与311之间的链路，因此路由器 223作为非叶子节点。

S706、Level_0层路由器接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

该步骤与S606区别在于，此时路由器223、224不会接收到上述只包括LSA 不包括路径表的LSU消息。

S707、因为Level_2层路由器221、223是非叶子节点，因此路由器411针对邻居路由器221、223分别生成路径表；因为Level_2层路由器222、224是非叶子节点，因此路由器412针对邻居路由器222、224分别生成路径表。

该步骤与S607区别在于，此时路由器411针对路由器223生成路径表，路由器412针对路由器224生成路径表。

S708、Level_1层路由器411、412向北向Level_2层路由器分别发送LSU消息，各LSU消息中包括LSA以及针对各路由器分别生成的路径表。

Level_1层路由器411向北向Level_2层路由器221、223分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器221、223分别生成的路径表；Level_1 层路由器412向北向Level_2层路由器222、224分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器222、224分别生成的路径表

该步骤与S608区别在于，此时会向路由器223、224发送包括LSA和路径表的LSU消息。

步骤S705和S708没有先后执行顺序。

S709、Level_2层路由器221-224接收到上述LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

该步骤与S609区别在于，此时路由器223、224根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

S710、因为Level_1层路由器111、112、211、311、312是非叶子节点，因此路由器221针对邻居路由器111、211生成路径表，路由器222针对邻居路由器 112、212生成路径表，路由器223针对邻居路由器311生成路径表，路由器224 针对邻居路由器312生成路径表。

该步骤与S610区别在于，此时路由器223针对邻居路由器311生成路径表，路由器224针对邻居路由器312生成路径表，路由器221针对邻居路由器111生成路径表。

S711、Level_2层路由器221-224向南向Level_1层路由器分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器111、112、211、212、311、312 分别生成的路径表。

该步骤与S611区别在于，此时路由器223向路由器311发送LSU消息，而路由器221不再向路由器311发送LSU消息；路由器224向路由器312发送LSU 消息，而路由器222不再向路由器312发送LSU消息。

S712、Level_1层路由器111、112、211、212、311、312接收到上述LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

该步骤与S612区别在于，此时路由器312从路由器224接收LSU消息，路由器311从路由器223接收LSU消息。

S713、因为Level_0层路由器是叶子节点，Level_1层路由器111、112、211、 212、311、312向路径表的标识对应的南向Level_0层路由器发送LSU消息，LSU 消息中只包括LSA不包括路径表。

S714、Level_0层路由器接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

方式六的技术效果：

确保了其他Level_0层路由器知道通告路由器Level_0层路由器的最新状态信息，以便调整自己到其他Level_0层路由器的路由表项。

该实施例既保证了Level_0层路由器404生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式六区别于现有技术的改进之处见方式一，在此不再赘述。

方式七、参照图26中所示，为完备拓扑下的Level_1层路由器与Level_2层路由器之间链路故障进行事件性LSA更新的示意图，结合图27中所示，该LSA 发送方法可以包括：

S801、当链路故障发生在Level_1层路由器与Level_2层路由器之间(如路由器412与224之间)时，该事件关联的两个路由器412及224均作为通告路由器生成LSA。

路由器412生成的LSA中包括路由器412的标识以及路由器401-404的标识。该LSA还可以包括路由器412的层次位置信息以及路由器401-404的层次位置信息。

路由器224生成的LSA中包括路由器224的标识以及路由器112、212、312 的标识。该LSA还可以包括路由器224的层次位置信息以及路由器112、212、312 的层次位置信息。

S802、因为Level_0层路由器是叶子节点，Level_1层路由器412向南向 Level_0层路由器401-404发送LSU消息，LSU消息中只包括LSA不包括路径表。

此时，Level_1层路由器412对应步骤S107中所述的第一路由器，Level_0 层路由器401-404对应步骤S107中所述的第二路由器。

S803、Level_0层路由器401-404接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_0层路由器401-404对应S108和S109中所述的第二路由器。

S804、因为Level_1层路由器112、212、312是非叶子节点，因此路由器224 针对邻居路由器112、212、312分别生成路径表。

此时，Level_2层路由器224对应步骤S102中所述的第一路由器，Level_1 层路由器112、212、312对应步骤S102中所述的第二路由器，Level_0层路由器101-304对应步骤S102中所述的第三路由器。

S805、Level_2层路由器224向南向Level_1层路由器112、212、312分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器112、212、312分别生成的路径表。

此时，Level_2层路由器224对应步骤S102中所述的第一路由器，Level_1 层路由器112、212、312对应步骤S102中所述的第二路由器。

S806、Level_1层路由器112、212、312接收到上述LSU消息后，根据LSA 更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

此时，Level_1层路由器112、212、312对应步骤S104和S105中所述的第二路由器。

S807、因为Level_0层路由器是叶子节点，Level_1层路由器112、212、312 向路径表的标识对应的南向Level_0层路由器101-304发送LSU消息，LSU消息中只包括LSA不包括路径表。

此时，Level_1层路由器112、212、312对应步骤S106中所述的第二路由器， Level_0层路由器101-304对应步骤S106中所述的第三路由器；或者，Level_1层路由器112、212、312对应步骤S107中所述的第一路由器，Level_0层路由器101-304对应步骤S107中所述的第二路由器。

S808、Level_0层路由器101-304接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_0层路由器101-304对应S108和S109中所述的第二路由器。

方式七的技术效果：

确保了Level_0层路由器知道故障链路情况，以便基于最新拓扑计算或刷新到受故障影响Level_0层路由器的路径。

该实施例既保证了故障关联Level_1层路由器412及Level_2层路由器224 生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低 LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式七区别于现有技术的改进之处见方式一，在此不再赘述。

方式八、参照图28中所示，为非完备拓扑下的Level_1层路由器与Level_2 层路由器之间链路故障进行事件性LSA更新的示意图，与图26相比较，缺少路由器224与212之间的链路。结合图29中所示，该LSA发送方法可以包括：

步骤S901-S903与步骤S801-S803相同，在此不再赘述。

S904、因为Level_1层路由器112、312是非叶子节点，因此路由器224针对邻居路由器112、312分别生成路径表。

该步骤与S804的区别在于，路由器224不再针对邻居路由器212生成路径表。

S905、Level_2层路由器224向南向Level_1层路由器112、312分别发送LSU 消息，各LSU消息中包括LSA以及针对邻居路由器112、312分别生成的路径表。

该步骤与S805的区别在于，路由器224不再向路由器212发送LSU消息。

S906、Level_1层路由器112、312接收到上述LSU消息后，根据LSA更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

该步骤与S806的区别在于，路由器212不再接收LSU消息。

S907、因为Level_0层路由器是叶子节点，Level_1层路由器112、312向路径表的标识对应的南向Level_0层路由器101-104、301-304发送LSU消息，LSU 消息中只包括LSA不包括路径表。

该步骤与S807的区别在于，路由器212不向201-204发送LSU消息。

S908、Level_0层路由器101-104、301-304接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

该步骤与S808的区别在于，路由器201-204不再接收LSU消息。

方式八的技术效果：

(1)确保了Level_0层路由器知道故障链路情况，以便基于最新拓扑计算或刷新到受故障影响Level_0层路由器的路径。

(2)不是Level_2层路由器下一跳邻居的Level_1层路由器(包括111、211、 212、311、411)不用接收到其发送的LSA，因为这些路由器处理的数据包下一跳不会经过224路由器，也不会接收直接从224路由器发来的数据包。

该实施例既保证了故障关联Level_1层路由器412及Level_2层路由器224 生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低 LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式八区别于现有技术的改进之处见方式一，在此不再赘述。

方式九、参照图30中所示，为完备拓扑下的Level_1层路由器与Level_0层路由器之间链路故障进行事件性LSA更新的示意图，结合图31中所示，该LSA 发送方法可以包括：

S1001、当链路故障发生在Level_0层路由器与Level_1层路由器之间(如路由器404与412之间)时，该事件关联的两个路由器404与412均作为通告路由器生成LSA。

对于Level_0层路由器404而言，其仅作本地LSDB更新，不向Level_1层路由器发送该LSA。

对于Level_1层路由器412而言，其生成的LSA与步骤S401中生成的LSA 的区别在于，不包括路由器404的标识。也不包括路由器404的层次位置信息。

S1002、因为Level_2层路由器224以及Level_0层路由器401-403是叶子节点，因此路由器412向路由器224、401-403分别发送LSU消息，各LSU消息中仅包括上述LSA不包括路径表。

该步骤与S402的区别在于，路由器412不会向路由器404发送LSU消息。

S1003、路由器224、401-403分别接收到LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

该步骤与S403的区别在于，路由器404不会接收到LSU消息。

步骤S1004-S1011与步骤S404-S411相同，在此不再赘述。

方式九的技术效果：

确保了Level_0层路由器知道故障链路情况，以便基于最新拓扑计算或刷新到受故障影响Level_0层路由器的路径。

该实施例既保证了故障关联Level_1层路由器412及Level_0层路由器404 生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低 LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式九区别于现有技术的改进之处见方式一，在此不再赘述。

方式十、参照图32中所示，为非完备拓扑下的Level_1层路由器与Level_0 层路由器之间链路故障进行事件性LSA更新的示意图，结合图33中所示，该LSA 发送方法可以包括：

步骤S1101-S1103与步骤S1001-S1003相同，在此不再赘述。

步骤S1104-S11011与步骤S504-S5011相同，在此不再赘述。

方式十的技术效果：

确保了Level_0层路由器知道故障链路情况，以便基于最新拓扑计算/刷新到受故障影响Level_0层路由器的路径。

该实施例既保证了故障关联Level_1层路由器412及Level_0层路由器404 生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低 LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式十一、参照图34中所示，为完备拓扑下的Level_2层路由器故障进行事件性LSA更新的示意图，结合图35中所示，该LSA发送方法可以包括：

S1201、当Level_2层路由器(例如图中的路由器224)失效时，等效于多条链路同时发生故障，其南向Level_1层邻居路由器(例如图中的路由器112、212、 312、412)均作为通告路由器生成LSA。

示例性的，路由器112生成的LSA中包括路由器112的标识以及路由器 101-104的标识。该LSA还可以包括路由器112的层次位置信息以及路由器 101-104的层次位置信息。

S1202、因为Level_0层路由器是叶子节点，Level_1层路由器112、212、312、 412向对应的南向Level_0层路由器101-404发送LSU消息，LSU消息中只包括 LSA不包括路径表。

此时，Level_1层路由器112、212、312、412对应步骤S106中所述的第二路由器，Level_0层路由器101-404对应步骤S106中所述的第三路由器；或者， Level_1层路由器112、212、312、412对应步骤S107中所述的第一路由器，Level_0 层路由器101-404对应步骤S107中所述的第二路由器。

S1203、Level_0层路由器101-404接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_0层路由器及路由器101-404对应S108和S109中所述的第二路由器。

方式十一的技术效果：

确保了Level_0层路由器知道路由器失效情况，以便基于最新拓扑计算或刷新至受故障影响Level_0层路由器的路径。

该实施例既保证了故障关联Level_1层路由器112、212、312、412生成的 LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在 Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式十一区别于现有技术的改进之处见方式一，在此不再赘述。

方式十二、参照图36中所示，为完备拓扑下的Level_1层路由器故障进行事件性LSA更新的示意图，结合图37中所示，该LSA发送方法可以包括：

S1301、当Level_1层路由器(如图中的路由器412)失效时，等效于多条链路同时发生故障，其邻居路由器222、224、401-404均作为通告路由器生成LSA。

对于Level_0层路由器401-404而言，其仅作本地LSDB更新，不向Level_1 层路由器发送该LSA。

Level_2层路由器222生成的LSA中包括路由器222的标识以及路由器112、 212、312的标识。该LSA还可以包括路由器222的层次位置信息以及路由器112、212、312的层次位置信息。

Level_2层路由器224生成的LSA中包括路由器224的标识以及路由器112、 212、312的标识。该LSA还可以包括路由器224的层次位置信息以及路由器112、 212、312的层次位置信息。

S1302、因为Level_1层路由器112、212、312是非叶子节点，因此路由器 222针对邻居路由器112、212、312分别生成路径表，路由器224针对邻居路由器112、212、312分别生成路径表。

此时，Level_2层路由器222、224对应步骤S102中所述的第一路由器，Level_1 层路由器112、212、312对应步骤S102中所述的第二路由器，Level_0层路由器 101-304对应步骤S102中所述的第三路由器。

S1303、Level_2层路由器222、224向南向Level_1层路由器112、212、312 分别发送LSU消息，各LSU消息中包括LSA以及针对邻居路由器112、212、312 分别生成的路径表。

此时，Level_2层路由器222、224对应步骤S103中所述的第一路由器，Level_1 层路由器112、212、312对应步骤S103中所述的第二路由器。

S1304、Level_1层路由器112、212、312接收到上述LSU消息后，根据LSA 更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

此时，Level_1层路由器112、212、312对应步骤S104和S105中所述的第二路由器。

方式十二的技术效果：

确保了Level_0层路由器知道路由器失效情况，以便基于最新拓扑计算或刷新到受故障影响Level_0层路由器的路径。

该实施例既保证了故障关联Level_2层路由器222、224生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

方式十三、参照图38中所示，为完备拓扑下的Level_0层路由器故障进行事件性LSA更新的示意图，结合图39中所示，该LSA发送方法可以包括：

S1401、当Level_0层路由器(如图中的路由器404)失效时，等效于多条链路同时发生故障，其邻居路由器(如图中的路由器411、412)均作为通告路由器生成LSA。

路由器412的处理过程参照步骤S1001-S1011的描述，在此不再赘述，下面只对路由器411的处理过程进行描述。

路由器411生成的LSA中包括路由器411的标识以及路由器221、223、 401-403的标识。该LSA还可以包括路由器411的层次位置信息以及路由器221、 223、401-403的层次位置信息。

路由器221与223是等价的，因此可以选择其中一个作叶子节点，另一个作非叶子节点。

S1402、因为Level_0层路由器401-403和Level_2层路由器223是叶子节点，因此路由器411向路由器401-403、223分别发送LSU消息，各LSU消息中仅包括上述LSA不包括路径表。

此时，路由器411对应步骤S107中所述的第一路由器，Level_2层路由器223 以及Level_0层路由器401-403对应步骤S107中所述的第二路由器。

S1403、路由器401-403、223分别接收到LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_2层路由器223以及Level_0层路由器401-403对应步骤S108 和S109中所述的第二路由器。

S1404、因为Level_2层路由器221是非叶子节点，因此路由器411针对邻居路由器221生成路径表。

示例性的，路由器411需要结合其位于Level_1层，路由器221位于Level_2 层，路由器111、211、311位于Level_1层来生成路径表，该路径表中包括路由器111、211、311的标识。

此时，Level_1层路由器411对应步骤S102中所述的第一路由器，Level_2 层路由器221对应步骤S102中所述的第二路由器，Level_1层路由器111、211、 311对应步骤S102中所述的第三路由器。

S1405、路由器411向路由器221发送LSU消息，LSU消息中包括LSA以及上述路径表。

通过该路径表，路由器411告知路由器221将接收到的LSA进一步发送到其南向Level_1层邻居路由器111、211、311。

此时，Level_1层路由器411对应步骤S103中所述的第一路由器，Level_2 层路由器221对应步骤S103中所述的第二路由器。

S1406、路由器221接收到LSU消息后，根据LSA更新本地LSDB，并根据 LSU消息中包括路径表确定转发LSA。

此时，Level_2层路由器221对应步骤S104和S105中所述的第二路由器。

S1407、因为Level_1层路由器111、211、311是非叶子节点，因此路由器 221针对路由器111、211、311分别生成路径表。

示例性的，对于针对路由器111生成的路径表来说，路由器221需要结合其位于Level_2层，路由器111位于Level_1层，路由器101-104位于Level_0层来生成路径表，该路径表中包括路由器101-104的标识。针对其他邻居路由器生成路径表的方法类似，具体不再赘述。

此时，Level_2层路由器221对应步骤S102中所述的第一路由器，Level_1 层路由器111、211、311对应步骤S102中所述的第二路由器，Level_0层路由器对应步骤S102中所述的第三路由器。

S1408、路由器221向南向Level_1层路由器111、211、311分别发送LSU 消息，各LSU消息中包括LSA以及针对邻居路由器111、211、311分别生成的路径表。

此时，Level_2层路由器221对应步骤S103中所述的第一路由器，Level_1 层路由器111、211、311对应步骤S103中所述的第二路由器。

S1409、Level_1层路由器111、211、311接收到上述LSU消息后，根据LSA 更新本地LSDB，并根据LSU消息中包括路径表确定转发LSA。

此时，Level_1层路由器111、211、311对应步骤S104和S105中所述的第二路由器。

S1410、因为Level_0层路由器是叶子节点，Level_1层路由器111、211、311 向路径表的标识对应的南向Level_0层路由器发送LSU消息，LSU消息中只包括 LSA不包括路径表。

此时，Level_1层路由器111、211、311对应步骤S106中所述的第二路由器， Level_0层路由器对应步骤S106中所述的第三路由器；或者，Level_1层路由器 111、211、311对应步骤S107中所述的第一路由器，Level_0层路由器对应步骤 S107中所述的第二路由器。

S1411、Level_0层路由器接收到上述LSU消息后，根据其中不包括路径表确定不转发LSA，仅根据LSA更新本地LSDB。

此时，Level_0层路由器对应S108和S109中所述的第二路由器。

方式十三的技术效果：

确保了Level_0层路由器知道路由器失效情况，以便基于最新拓扑计算/刷新到受故障影响Level_0层路由器的路径。

该实施例既保证了故障关联Level_1层路由器401、402生成的LSA在网络中的必要更新，又避免了不必要的重复或冗余，大幅度降低LSA在Fat-Tree网络中的传送量，减轻了路由器处理LSU消息的负担。

本申请实施例提供一种路由器，用于执行上述方法。本申请实施例可以根据上述方法示例对终端设备进行功能模块的划分，例如，可以对应各个功能划分各个功能模块，也可以将两个或两个以上的功能集成在一个处理模块中。上述集成的模块既可以采用硬件的形式实现，也可以采用软件功能模块的形式实现。需要说明的是，本申请实施例中对模块的划分是示意性的，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式。

在采用对应各个功能划分各个功能模块的情况下，图40示出了上述实施例中所涉及的路由器的一种可能的结构示意图，路由器100包括：接收单元1011、生成单元1012、更新单元1013、发送单元1014、判断单元1015。接收单元1011用于支持路由器100执行图3中的过程S104、S108，图6中的过程S104、S108、 S121，图7中的过程S104、S108、S121，图9中的过程S104、S108，图8中的过程S104、S108，图10中的过程S104、S108、S162、S164，图12中的过程S104、 S108，图13中的过程S104、S108、S181，图15中的过程S204、S206，图17中的过程S304、S306，图19中的过程S403、S406、S409、S411，图21中的过程 S503、S506、S509、S511，图23中的过程S604、S606、S609、S612、S614，图 25中的过程S704、S706、S709、S712、S714，图27中的过程S803、S806、S808，图29中的过程S903、S906、S908，图31中的过程S1003、S1006、S1009、S1011，图33中的过程S1103、S1106、S1109、S1111，图35中的过程S1203，图37中的过程S1304，图39中的过程S1403、S1406、S1409、S1411；生成单元1012用于支持路由器100执行图3中的过程S102，图6中的过程S102，图7中的过程 S102，图8中的过程S102、S151，图10中的过程S102，图12中的过程S102，图13中的过程S102、S151，图15中的过程S201、S202，图17中的过程S301、 S302，图19中的过程S401、S404、S407，图21中的过程S501、S504、S507，图23中的过程S601、S602、S607、S610，图25中的过程S701、S702、S707、 S710，图27中的过程S801、S804，图29中的过程S901、S904，图31中的过程 S1001、S1004、S1007，图33中的过程S1101、S1104、S1107，图35中的过程 S1201，图37中的过程S1301、S1302，图39中的过程S1401、S1404、S1407；更新单元1013用于支持路由器100执行图3中的过程S105、S109，图6中的过程S105、S109、S122，图7中的过程S105、S109、S122，图10中的过程S105、 S109，图12中的过程S105、S109，图13中的过程S105、S109，图15中的过程 S204、S206，图17中的过程S304、S306，图19中的过程S406、S409、S411，图21中的过程S506、S509、S511，图23中的过程S604、S606、S609、S612、 S614，图25中的过程S704、S706、S709、S712、S714，图27中的过程S803、 S806、S808，图29中的过程S903、S906、S908，图31中的过程S1003、S1006、 S1009、S1011，图33中的过程S1103、S1106、S1109、S1111，图35中的过程 S1203，图37中的过程S1304，图39中的过程S1403、S1406、S1409、S1411；发送单元1014用于支持路由器100执行图3中的过程S103、S106、S107，图6 中的过程S103、S106、S107，图7中的过程S1031、S106、S107，图8中的过程S1061、S107，图10中的过程S103、S106、S161、S163，图12中的过程S103、 S106、S171，图13中的过程S103、S1061，图15中的过程S203、S205，图17 中的过程S303、S305，图19中的过程S402、S405、S408、S410，图21中的过程S502、S505、S508、S510，图23中的过程S603、S605、S608、S611、S613，图25中的过程S703、S705、S708、S711、S713，图27中的过程S802、S805、S807，图29中的过程S902、S905、S907，图31中的过程S1002、S1005、S1008、 S1010，图33中的过程S1102、S1105、S1108、S1110，图35中的过程S1202，图37中的过程S1303，图39中的过程S1402、S1405、S1408、S1410；判断单元 1015用于支持路由器100执行图3中的过程S101，图6中的过程S101，图7中的过程S101，图8中的过程S101，图10中的过程S101，图12中的过程S101，图13中的过程S101。其中，上述方法实施例涉及的各步骤的所有相关内容均可以援引到对应功能模块的功能描述，在此不再赘述。

在采用集成的单元的情况下，图41示出了上述实施例中所涉及的路由器的一种可能的结构示意图。路由器100包括：处理模块1022和通信模块1023。处理模块1022用于对路由器100的动作进行控制管理，例如，处理模块1022用于支持路由器100执行上述生成单元、更新单元、判断单元的功能。通信模块1023用于支持路由器与其他实体的通信，例如与图1中示出的功能模块或网络实体之间的通信。路由器100还可以包括存储模块1021，用于存储路由器的程序代码和数据。

其中，处理模块1022可以是处理器或控制器，例如可以是中央处理器(Centralprocessing unit，CPU)，通用处理器，数字信号处理器(Digital Signal Processor，DSP)，专用集成电路(Application-Specific Integrated Circuit，ASIC)，现场可编程门阵列(Field Programmable Gate Array，FPGA)或者其他可编程逻辑器件、晶体管逻辑器件、硬件部件或者其任意组合。其可以实现或执行结合本申请公开内容所描述的各种示例性的逻辑方框，模块和电路。所述处理器也可以是实现计算功能的组合，例如包含一个或多个微处理器组合，DSP和微处理器的组合等等。通信模块1023可以是收发器、收发电路、网络接口或通信接口等。存储模块1021 可以是存储器。

具体的，处理模块1022可以为图42中的处理器1032 ，通信模块1023可以为图4 2中的网络接口 1033 ，存储模块1021可以为图4 2中的存储器1031 。

当处理模块1022为处理器，通信模块1023为网络接口，存储模块1021为存储器时，本申请实施例所涉及的路由器可以为图42所示的路由器100。

参阅图42所示，该路由器100包括：处理器1032、网络接口1033、存储器 1031、总线1034。其中，网络接口1033、处理器1032、存储器1031通过总线1034 相互连接；总线1034可以是外设部件互连标准总线或扩展工业标准结构总线等。所述总线可以分为地址总线、数据总线、控制总线等。为便于表示，图中仅用一条粗线表示，但并不表示仅有一根总线或一种类型的总线。

应理解，在本申请的各种实施例中，上述各过程的序号的大小并不意味着执行顺序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应对本申请实施例的实施过程构成任何限定。

本领域普通技术人员可以意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、或者计算机软件和电子硬件的结合来实现。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本申请的范围。

所属领域的技术人员可以清楚地了解到，为描述的方便和简洁，上述描述的系统、装置和单元的具体工作过程，可以参考前述方法实施例中的对应过程，在此不再赘述。

在本申请所提供的几个实施例中，应该理解到，所揭露的系统、设备和方法，可以通过其他的方式实现。例如，以上所描述的设备实施例仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些接口，设备或单元的间接耦合或通信连接，可以是电性，机械或其他的形式。

所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。

在上述实施例中，可以全部或部分地通过软件、硬件、固件或者其任意组合来实现。当使用软件程序实现时，可以全部或部分地以计算机程序产品的形式来实现。该计算机程序产品包括一个或多个计算机指令。在计算机上加载和执行计算机程序指令时，全部或部分地产生按照本申请实施例所述的流程或功能。所述计算机可以是通用计算机、专用计算机、计算机网络、或者其他可编程装置。所述计算机指令可以存储在计算机可读存储介质中，或者从一个计算机可读存储介质向另一个计算机可读存储介质传输，例如，所述计算机指令可以从一个网站站点、计算机、服务器或者数据中心通过有线(例如同轴电缆、光纤、数字用户线 (Digital Subscriber Line，DSL))或无线(例如红外、无线、微波等)方式向另一个网站站点、计算机、服务器或数据中心进行传输。所述计算机可读存储介质可以是计算机能够存取的任何可用介质或者是包含一个或多个可以用介质集成的服务器、数据中心等数据存储设备。所述可用介质可以是磁性介质(例如，软盘、硬盘、磁带)，光介质(例如，DVD)、或者半导体介质(例如固态硬盘(Solid State Disk，SSD))等。

以上所述，仅为本申请的具体实施方式，但本申请的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本申请揭露的技术范围内，可轻易想到变化或替换，都应涵盖在本申请的保护范围之内。因此，本申请的保护范围应以所述权利要求的保护范围为准。

Claims (26)

1.一种链路状态通告LSA发送方法，其特征在于，包括：

第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表，其中，所述第二路由器是与所述第一路由器之间链路有效的下一跳邻居路由器，所述第三路由器是与所述第二路由器之间链路有效的邻居路由器中，所述第二路由器的下一跳路由器或所述第一路由器的下下一跳路由器，所述第一路径表包括至少一个所述第三路由器的标识，所述第一路径表中的标识用于指示向对应路由器发送第一LSA，所述第一LSA包括通告路由器与其邻居路由器之间的有效链路，所述通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器；其中，所述第一路由器、所述第二路由器、以及所述至少一个第三路由器根据所述路由器在所述第一LSA上的相对位置分类；

所述第一路由器向所述第二路由器发送第一链路状态更新LSU消息，其中，所述第一LSU消息中包括所述第一LSA和所述第一路径表。

2.根据权利要求1所述的方法，其特征在于，所述方法还包括：

所述第一路由器从第四路由器接收第二LSU消息，所述第二LSU消息中包括所述第一LSA，其中，所述第四路由器是与所述第一路由器之间链路有效的邻居路由器中，除了所述第二路由器以外的路由器；

所述第一路由器根据所述第一LSA更新其链路状态数据库LSDB。

3.根据权利要求2所述的方法，其特征在于，所述第一路由器向所述第二路由器发送第一链路状态更新LSU消息，包括：

当所述第二LSU消息中还包括第二路径表时，所述第一路由器向所述第二路由器发送所述第一LSU消息，其中，所述第二路径表中包括至少一个所述第二路由器的标识，所述第二路径表中的标识用于指示向对应路由器发送所述第一LSA。

4.根据权利要求1所述的方法，其特征在于，所述第一路由器为所述通告路由器。

5.根据权利要求1所述的方法，其特征在于，所述第一LSA包括所述通告路由器的层次位置信息和/或与所述通告路由器链路有效的邻居路由器的层次位置信息。

6.根据权利要求1所述的方法，其特征在于，在所述第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表之前，所述方法还包括：

所述第一路由器从所述第二路由器接收第二LSA，所述第二LSA包括所述第二路由器的层次位置信息和/或至少一个所述第三路由器的层次位置信息。

7.根据权利要求1-6任一项所述的方法，其特征在于，在所述第一路由器根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表之前，所述方法还包括：

所述第一路由器向所述第二路由器发送第一开放式最短路径优先OSPF协商消息；

所述第一路由器从所述第二路由器接收第二OSPF协商消息；

其中，所述第一OSPF协商消息中包括所述第一路由器的层次位置信息，所述第二OSPF协商消息中包括所述第二路由器的层次位置信息，所述第一OSPF协商消息和所述第二OSPF协商消息用于建立和维护所述第一路由器与所述第二路由器的邻居关系。

8.一种链路状态通告LSA发送方法，其特征在于，包括：

第二路由器从第一路由器接收第一链路状态更新LSU消息，其中，所述第一LSU消息中包括第一LSA和第一路径表，所述第一LSA包括通告路由器与其邻居路由器之间的有效链路，所述通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器，所述第一路径表包括至少一个第三路由器的标识，所述第二路由器是与所述第一路由器之间链路有效的下一跳邻居路由器，所述第三路由器是与所述第二路由器之间链路有效的邻居路由器中，所述第二路由器的下一跳路由器或所述第一路由器的下下一跳路由器；其中，所述第一路由器、所述第二路由器、以及所述至少一个第三路由器根据所述路由器在所述第一LSA上的相对位置分类；所述第二路由器根据所述第一LSA更新其链路状态数据库LSDB；

所述第二路由器向所述第一路径表中的标识对应的路由器发送所述第一LSA。

9.根据权利要求8所述的方法，其特征在于，

所述方法还包括：所述第二路由器根据其层次位置信息、第三路由器的层次位置信息和至少一个第五路由器的层次位置信息，生成第二路径表，其中，所述第二路径表包括至少一个所述第五路由器的标识，所述第二路径表中的标识用于指示向对应路由器发送所述第一LSA，所述第五路由器是与所述第三路由器之间链路有效的邻居路由器中，除了所述第二路由器以外的路由器；

所述第二路由器向所述第一路径表中的标识对应的路由器发送所述第一LSA，包括：所述第二路由器向所述第一路径表中的标识对应的路由器发送第二LSU消息，其中，所述第二LSU消息中包括所述第一LSA和所述第二路径表。

10.根据权利要求9所述的方法，其特征在于，在所述第二路由器根据其层次位置信息、第三路由器的层次位置信息和至少一个第五路由器的层次位置信息，生成第二路径表之前，所述方法还包括：

所述第二路由器从所述第三路由器接收第二LSA，所述第二LSA包括所述第三路由器的层次位置信息和/或至少一个所述第五路由器的层次位置信息。

11.根据权利要求8所述的方法，其特征在于，所述第一LSA包括所述通告路由器的层次位置信息和/或与所述通告路由器链路有效的邻居路由器的层次位置信息。

12.根据权利要求8所述的方法，其特征在于，所述第一路由器为所述通告路由器。

13.根据权利要求8-12任一项所述的方法，其特征在于，在所述第二路由器从第一路由器接收第一链路状态更新LSU消息之前，所述方法还包括：

所述第二路由器向所述第一路由器发送第一开放式最短路径优先OSPF协商消息；

所述第二路由器从所述第一路由器接收第二OSPF协商消息；

其中，所述第一OSPF协商消息中包括所述第二路由器的层次位置信息，所述第二OSPF协商消息中包括所述第一路由器的层次位置信息，所述第一OSPF协商消息和所述第二OSPF协商消息用于建立和维护所述第一路由器与所述第二路由器的邻居关系。

14.一种第一路由器，其特征在于，包括：

生成单元，用于根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表，其中，所述第二路由器是与所述第一路由器之间链路有效的下一跳邻居路由器，所述第三路由器是与所述第二路由器之间链路有效的邻居路由器中，所述第二路由器的下一跳路由器或所述第一路由器的下下一跳路由器，所述第一路径表包括至少一个所述第三路由器的标识，所述第一路径表中的标识用于指示向对应路由器发送第一链路状态通告LSA，所述第一LSA包括通告路由器与其邻居路由器之间的有效链路，所述通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器；其中，所述第一路由器、所述第二路由器、以及所述至少一个第三路由器根据所述路由器在所述第一LSA上的相对位置分类；

发送单元，用于向所述第二路由器发送第一链路状态更新LSU消息，其中，所述第一LSU消息中包括所述第一LSA和所述第一路径表。

15.根据权利要求14所述的第一路由器，其特征在于，所述第一路由器还包括：

接收单元，用于从第四路由器接收第二LSU消息，所述第二LSU消息中包括所述第一LSA，其中，所述第四路由器是与所述第一路由器之间链路有效的邻居路由器中，除了所述第二路由器以外的路由器；

更新单元，用于根据所述第一LSA更新其链路状态数据库LSDB。

16.根据权利要求15所述的第一路由器，其特征在于，所述发送单元具体用于：

当所述第二LSU消息中还包括第二路径表时，向所述第二路由器发送所述第一LSU消息，其中，所述第二路径表中包括至少一个所述第二路由器的标识，所述第二路径表中的标识用于指示向对应路由器发送所述第一LSA。

17.根据权利要求14所述的第一路由器，其特征在于，所述第一路由器为所述通告路由器。

18.根据权利要求14所述的第一路由器，其特征在于，所述第一LSA包括所述通告路由器的层次位置信息和/或与所述通告路由器链路有效的邻居路由器的层次位置信息。

19.根据权利要求14所述的第一路由器，其特征在于，所述第一路由器还包括接收单元，

所述接收单元，用于在所述生成单元根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表之前，从所述第二路由器接收第二LSA，所述第二LSA包括所述第二路由器的层次位置信息和/或至少一个所述第三路由器的层次位置信息。

20.根据权利要求14-19任一项所述的第一路由器，其特征在于，所述第一路由器还包括接收单元，

所述发送单元，还用于在所述生成单元根据其层次位置信息、第二路由器的层次位置信息和至少一个第三路由器的层次位置信息，生成第一路径表之前，向所述第二路由器发送第一开放式最短路径优先OSPF协商消息；

所述接收单元用于从所述第二路由器接收第二OSPF协商消息；

其中，所述第一OSPF协商消息中包括所述第一路由器的层次位置信息，所述第二OSPF协商消息中包括所述第二路由器的层次位置信息，所述第一OSPF协商消息和所述第二OSPF协商消息用于建立和维护所述第一路由器与所述第二路由器的邻居关系。

21.一种第二路由器，其特征在于，包括：

接收单元，用于从第一路由器接收第一链路状态更新LSU消息，其中，所述第一LSU消息中包括第一链路状态通告LSA和第一路径表，所述第一LSA包括通告路由器与其邻居路由器之间的有效链路，所述通告路由器指链路状态发生改变或周期性进行链路状态更新的路由器，所述第一路径表包括至少一个第三路由器的标识，所述第二路由器是与所述第一路由器之间链路有效的下一跳邻居路由器，所述第三路由器是与所述第二路由器之间链路有效的邻居路由器中，所述第二路由器的下一跳路由器或所述第一路由器的下下一跳路由器；其中，所述第一路由器、所述第二路由器、以及所述至少一个第三路由器根据所述路由器在所述第一LSA上的相对位置分类；

更新单元，用于根据所述第一LSA更新其链路状态数据库LSDB；

发送单元，用于向所述第一路径表中的标识对应的路由器发送所述第一LSA。

22.根据权利要求21所述的第二路由器，其特征在于，所述第二路由器还包括生成单元，

所述生成单元用于：根据其层次位置信息、第三路由器的层次位置信息和至少一个第五路由器的层次位置信息，生成第二路径表，其中，所述第二路径表包括至少一个所述第五路由器的标识，所述第二路径表中的标识用于指示向对应路由器发送所述第一LSA，所述第五路由器是与所述第三路由器之间链路有效的邻居路由器中，除了所述第二路由器以外的路由器；

所述发送单元具体用于：向所述第一路径表中的标识对应的路由器发送第二LSU消息，其中，所述第二LSU消息中包括所述第一LSA和所述第二路径表。

23.根据权利要求22所述的第二路由器，其特征在于，

所述接收单元，还用于在所述生成单元根据其层次位置信息、第三路由器的层次位置信息和至少一个第五路由器的层次位置信息，生成第二路径表之前，从所述第三路由器接收第二LSA，所述第二LSA包括所述第三路由器的层次位置信息和/或至少一个所述第五路由器的层次位置信息。

24.根据权利要求22所述的第二路由器，其特征在于，所述第一LSA包括所述通告路由器的层次位置信息和/或与所述通告路由器链路有效的邻居路由器的层次位置信息。

25.根据权利要求22所述的第二路由器，其特征在于，所述第一路由器为所述通告路由器。

26.根据权利要求21-25任一项所述的第二路由器，其特征在于，

所述发送单元，还用于在所述接收单元从第一路由器接收第一链路状态更新LSU消息之前，向所述第一路由器发送第一开放式最短路径优先OSPF协商消息；

所述接收单元，还用于从所述第一路由器接收第二OSPF协商消息；

其中，所述第一OSPF协商消息中包括所述第二路由器的层次位置信息，所述第二OSPF协商消息中包括所述第一路由器的层次位置信息，所述第一OSPF协商消息和所述第二OSPF协商消息用于建立和维护所述第一路由器与所述第二路由器的邻居关系。

Images