Method and apparatus for managing network status information using multiple degree of precision graph

Patent metadata

Field	Value
Publication number	US-11909627-B2
Application number	US-202117140668-A
Country	US
Kind code	B2
Filing date	Jan 4, 2021
Priority date	Jan 4, 2021
Publication date	Feb 20, 2024
Grant date	Feb 20, 2024

Abstract

A method and apparatus for routing packets in a network, such as a satellite mesh network. Network nodes maintain network status information (e.g. link availability information) for the entire network. However, the information is maintained to a higher level of precision for some network regions than for others. For example, the network node can be informed of network events in some regions with lower latency than in other regions. Routing information is generated based on the network status information. Multiple different mechanisms can be used to provide network status updates at different levels of precisions. Nodes which generate or relay network status updates can inhibit (e.g. block or delay) passing the updates toward a target node in order to reduce the level of precision of network status information at that target node.

First claim

What is claimed is:

1. A method for managing a link state database in a network, comprising, by a network node of a communication network with dynamically changing topology:
maintaining network status information for a plurality of different portions of the network, each of said different portions defined by a different respective set of network nodes and links, wherein said network status information for one of the different portions is updated with a higher latency than said network status information for another one of the different portions, said higher latency being due at least in part to active inhibition of notifications indicative of the network status information by one or more other network nodes; and
updating the link state database based on the network status information for the plurality of different portions of the network, the link state database indicative of link states within the plurality of different portions of the network, wherein the link state database includes a first portion indicative of link states for said one of the different portions of the network and a second portion indicative of link states for said other one of the different portions of the network, and an indication that the first portion is tracked with a lower precision than the second portion due to said higher latency.

2. The method of claim 1 , wherein updating the link state database comprises updating the link state database separately for a given portion of the plurality of different portions of the network, in response to receiving one of said notifications indicative of the network status information for said one of the plurality of different portions.

3. The method of claim 2 , further comprising, following said updating the link state database for said given portion, generating routing information for said given portion, the routing information indicating desired routing paths through said given portion to reach specified nodes of the network within said given portion, and integrating said routing information with routing information for other ones of the plurality of different portions to generate routing information for the network.

4. The method of claim 1 , wherein the higher latency corresponds to a time between an occurrence of a network event and the network node being notified of the network event, said active inhibition including one or more of: notification mechanism selecting actions, notification inhibiting actions, and notification delaying actions, performed by one or more network nodes handling the notifications.

5. The method of claim 1 , further comprising generating routing information based on contents of said link state database, wherein generating the routing information comprises generating an indication of where to route the packet based on a specified destination of the packet, the specified destination falling within or reachable by a node within one of the different portions of the network, the routing information reflecting a plurality of different levels of precision of link state information corresponding to the plurality of different portions of the network.

6. The method of claim 1 , further comprising generating routing information based on contents of said link state database, wherein generating the routing information comprises combining multiple topology graphs, each topology graph indicating available nodes of the network and available links between said available nodes, each topology graph corresponding to a different one of said different portions of the network, said different portions being overlapping, non-overlapping, or a combination thereof.

7. The method of claim 6 , wherein generating the routing information further comprises generating a tree having sufficient path performance based on the combined topology graphs, the tree having sufficient path performance indicating desired routing paths through the network to reach different nodes of the network.

8. The method of claim 1 , further comprising generating routing information based on contents of said link state database, wherein generating the routing information comprises:
generating or obtaining multiple topology graphs, each topology graph indicating available nodes of the network and available links between said available nodes, each topology graph corresponding to a different one of said different portions of the network, said different portions being overlapping, non-overlapping, or a combination thereof;
generating multiple trees having sufficient path performance each based on a different one of the multiple topology graphs, each tree having sufficient path performance indicating desired routing paths through the network to reach different nodes of the network; and
combining the trees having sufficient path performance to define an overall tree having sufficient path performance for the network.

9. The method of claim 1 , further comprising updating routing information based on contents of said link state database in response to receipt of network status information for one of the different portions, wherein generating the routing information comprises:
computing, for said one of the different portions separately from other ones of the different portions, a tree indicating desired routing paths through said one of the different portions; and integrating the tree with other trees for said other ones of the different portions to create a tree indicating desired routing paths through the network.

10. The method of claim 1 , further comprising generating routing information based on contents of said link state database, wherein generating the routing information comprises combining network status information for different ones of the plurality of different portions of the network, said different portions being overlapping, non-overlapping, or a combination thereof.

11. A method for managing information in a network, comprising, by a network node of a communication network with dynamically changing topology:
generating or receiving an indication of a network event, the network event pertaining to status of a node or link of the network;
transmitting the indication of the network event toward a first one or more other network nodes to notify the first one or more other network nodes of a change in network status with a first level of precision; and
actively inhibiting transmission of the indication of the network event toward a second one or more other network nodes to notify the second one or more other network nodes of the change in network status with a second level of precision lower than the first level of precision, such that transmission of the indication of the network event toward the second one or more network nodes is delayed compared to transmission of the indication of the network event toward the first one or more network nodes.

12. The method of claim 11 , wherein inhibiting transmission of the indication of the network event toward a second one or more other network nodes comprises delaying transmission of the indication by holding the indication and transmitting the indication toward the second one or more other network nodes after a predetermined time period, or causing the transmission to be forwarded by an alternative and higher-latency mechanism.

13. A network node comprising a network interface, a processor and a non-transitory memory, the network node belonging to a communication network with dynamically changing topology and configured to:
maintain, using the processor and the memory, network status information for a plurality of different portions of the network, each of said different portions defined by a different respective set of network n

Assignees

• Akhavain Mohammadi Mehdi Arashmid
• Huawei Tech Co Ltd

Inventors

• Akhavain Mohammadi Mehdi Arashmid

Classifications

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/123 Primary

  Evaluation of link metrics (techniques for monitoring network metrics H04L43/08) · CPC title

• H04L45/14

  Routing performance; Theoretical aspects · CPC title

• H04L45/64

  using an overlay routing layer · CPC title