Link-state advertisement LSA sending method, apparatus, and system

Patent metadata

Field	Value
Publication number	US-11411853-B2
Application number	US-202016818606-A
Country	US
Kind code	B2
Filing date	Mar 13, 2020
Priority date	Sep 14, 2017
Publication date	Aug 9, 2022
Grant date	Aug 9, 2022

Abstract

This application discloses a link-state advertisement LSA sending method, an apparatus, and a system, to reduce a quantity of LSA sending times. The method includes: generating, by a first router, a first path table based on level location information of the first router, level location information of a second router, and level location information of at least one third router; sending, by the first router, a first link state update LSU message to the second router; receiving, by the second router, the first link state update LSU message from the first router; updating, by the second router, a link state database LSDB of the second router based on a first LSA; and sending, by the second router, the first LSA to a router corresponding to an identifier in the first path table.

First claim

What is claimed is:

1. A method, comprising:
determining, by a first router, that a second router is a non-leaf node;
generating, by the first router, a first link state update (LSU) message comprising a first link state advertisement (LSA) and a first path table, wherein:
the first router generates the first LSU message to include the first path table, in response to the first router determining that the second router is a non-leaf node;
the first router generates the first path table based on level location information of the first router, level location information of the second router, and level location information of a third router;
the second router is a neighbor router of the first router that has a valid link with the first router, the third router is a neighbor router of the second router and has a valid link with the second router, and the third router is a different router than the first router; and
the first path table comprises an identifier of the third router, the identifier of the third router being usable to instruct to send the first LSA to the third router, the first LSA comprising information of a valid link between an advertisement router and a neighbor router of the advertisement router, the advertisement router being a router that generates an LSA when a link state changes or a link state is periodically updated; and

sending, by the first router, the first LSU message to the second router; and
determining, by the first router, that a fourth router is a leaf node, the fourth router being a neighbor router of the first router that has a valid link with the first router, the fourth router being a different router than the second router;
generating, by the first router, a second LSU message comprising the first LSA but not the first path table, in response to the first router determining that the fourth router is a leaf node; and
sending, by the first router, the second LSU message to the fourth router.

2. The method according to claim 1 , further comprising:
receiving, by the first router, a third LSU message from a fifth router, wherein the third LSU message comprises the first LSA, the fifth router is a neighbor router of the first router and has a valid link with the first router, and the fifth router is a different router than the second router and the fourth router; and
updating, by the first router, a link state database (LSDB) of the first router based on the first LSA.

3. The method according to claim 2 , wherein sending, by the first router, the first LSU message to the second router comprises:
in response to the third LSU message further comprising a second path table, sending, by the first router, the first LSU message to the second router, wherein the second path table comprises an identifier of the second router, and the identifier of the second router in the second path table is usable to instruct to send the first LSA to the second router.

4. The method according to claim 1 , wherein the first router is the advertisement router.

5. The method according to claim 1 , wherein the first LSA comprises level location information of the advertisement router or level location information of the neighbor router of the advertisement router, and the neighbor router of the advertisement router has a valid link with the advertisement router.

6. The method according to claim 1 , wherein before generating, by the first router, the first LSU message that comprises the first path table, the method further comprises:
receiving, by the first router, a second LSA from the second router, wherein the second LSA comprises the level location information of the second router or the level location information of the third router.

7. The method according to claim 1 , wherein before generating, by the first router, the first LSU message that comprises the first path table, the method further comprises:
sending, by the first router, a first Open Shortest Path First (OSPF) negotiation message to the second router; and
receiving, by the first router, a second OSPF negotiation message from the second router, wherein the first OSPF negotiation message comprises the level location information of the first router, the second OSPF negotiation message comprises the level location information of the second router, and the first OSPF negotiation message and the second OSPF negotiation message are usable to establish and maintain a neighbor relationship between the first router and the second router.

8. A first router, comprising:
a non-transitory memory storing executable instructions; and
a processor coupled to the non-transitory memory to execute the instructions, the instructions including instructions to:
determine that a second router is a non-leaf node;
generate a first link state update (LSU) message comprising a first link state advertisement (LSA) and a first path table, wherein:
the first LSU message includes the first path table, in response to a determination that the second router is a non-leaf node;
the first path table is generated based on level location information of the first router, level location information of the second router, and level location information of a third router;
the second router is a neighbor router of the first router and has a valid link with the first router, the third router is a neighbor router of the second router and has a valid link with the second router, and the third router is a different router than the first router; and
the first path table comprises an identifier of the third router, the identifier of the third router in the first path table being usable to instruct to send the first LSA to the third router, the first LSA comprises a valid link between an advertisement router and a neighbor router of the advertisement router, and the advertisement router generates an LSA when a link state changes or a link state is periodically updated; and

send the first LSU message to the second router; and
determine that a fourth router is a leaf node, the fourth router being a neighbor router of the first router that has a valid link with the first router, the fourth router being a different router than the second router;
generate a second LSU message comprising the first LSA but not the first path table, in response to a determination that the fourth router is a leaf node; and
send the second LSU message to the fourth router.

9. The first router according to claim 8 , wherein the instructions further include instructions to:
receive a third LSU message from a fifth router, wherein the third LSU message comprises the first LSA, and the fifth router is a neighbor router of the first router and has a valid link with the first router, and the fifth router is a different router than the second router and the fourth router; and
update a link state database (LSDB) of the first router based on the first LSA.

10. The first router according to claim 9 , wherein the instructions further include instructions to:
when the third LSU message further comprises a second path table, send the first LSU message to the second router, wherein the second path table comprises an identifier of the second router, and the identifier in the second path table is usable to instruct to send the first LSA to the second router.

11. The first router according to claim 8 , wherein the first LSA comprises level location information of the advertisement router or level location information of the neighbor router of the advertisement router that has the valid link with the advertisement router.

12. The first router according to claim 8 , wherein the instructions further include instructions to:
receive a second LSA from the second route

Assignees

• Huawei Tech Co Ltd

Inventors

• Zheng Xiuli
• Xu Xiaohu
• Hu Nongda
• Wang Chuang
• Chen Zhe
• Liu Bingyang

Classifications

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/03

  by updating link state protocols · CPC title

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L45/026 Primary

  Details of "hello" or keep-alive messages · CPC title

• H04L45/04 Primary

  Interdomain routing, e.g. hierarchical routing · CPC title