Dynamic routing protocols using database synchronization

Patent metadata

Field	Value
Publication number	US-9253075-B2
Application number	US-201213720736-A
Country	US
Kind code	B2
Filing date	Dec 19, 2012
Priority date	Dec 19, 2012
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

A network-connectivity system can receive a remote additive hash for a routing-data collection of a remote network node, and compares the remote additive hash with a local additive hash for a local routing-data collection. A respective additive hash represents one or more network-configuration items of a routing-data collection. Also, at least one of the network-configuration items of the routing-data collection includes reachability information for a network node of a computer network, such as a link-state advertisement. If the system determines that the remote additive hash does not match the local additive hash, the system synchronizes the local routing-data collection with the remote network node of the computer network.

First claim

What is claimed is:

1. A computer-implemented method, comprising:
receiving, by a local network node, a remote additive hash representing one or more network-configuration items of a routing-data collection of a remote network node, wherein at least one of the network-configuration items of the remote additive hash includes reachability information for a network node of a computer network;
computing a local additive hash representing contents of a local routing-data collection of the local network node, based on hashes for a plurality of individual network configuration items of the local routing-data collection;
comparing the local additive hash with the remote additive hash;
responsive to determining that the remote additive hash does not match the local additive hash,
synchronizing the local routing-data collection with the routing-data collection of the remote network node of the computer network, which involves:
comparing the remote additive hash to one or more historical additive hashes for the local routing-data collection;
responsive to determining that the remote additive hash does not match at least one historical additive hash of the local routing-data collection, identifying and obtaining one or more network-configuration items from the routing-data collection of the remote network node that are missing from the local routing-data collection; and
adding the missing one or more network-configuration items to the local routing-data collection.

2. The method of claim 1 , further comprising:
receiving a filter from the remote network node, wherein the filter indicates selection criteria for selecting network-configuration items that are desired by the remote network node;
determining, from the local routing-data collection, a set of network-configuration items that satisfy the filter's selection criteria; and
generating the local additive hash using the network-configuration items that satisfy the filter's selection criteria.

3. The method of claim 2 , wherein synchronizing the routing-data collection involves:
generating a filtered collection of network-configuration items that includes, from the network-configuration items that satisfy the filter's selection criteria, one or more network-configuration items that are missing from the remote routing-data collection; and
sending structured names for the network-configuration items of the filtered collection to the remote network node.

4. The method of claim 1 ,
wherein synchronizing the local routing-data collection further involves:
comparing the remote additive hash to one or more historical additive hashes of the local routing-data collection to determine a matching historical additive hash; and
determining, based on the matching historical additive hash, one or more network-configuration items to send to the remote network node.

5. The method of claim 1 , further comprising:
generating a network-configuration item that corresponds to a change in a network configuration of the computer network;
adding the network-configuration item to the local routing-data collection;
generating a new additive hash for the routing-data collection; and
responsive to adding the network-configuration item to the local routing-data collection, synchronizing the local routing-data collection with the remote network node of the computer network.

6. The method of claim 5 , wherein the network-configuration item includes a link-state advertisement (LSA) that reflects a change in state for a link of the computer network; and
wherein the method further comprises updating a forwarding table for the computer network to account for the link's updated state.

7. The method of claim 6 , wherein generating the new additive hash involves:
determining a hash for a previous LSA for the link;
subtracting the determined hash from the local additive hash for the local routing-data collection;
computing a hash for the obtained LSA; and
adding the computed hash to the local additive hash.

8. The method of claim 5 , wherein the network-configuration item includes an entry for a Prefix-to-Custodian table (PC table); and
wherein the method further comprises updating the PC table for the computer network to account for the network-configuration item.

9. The method of claim 5 , wherein the network-configuration item includes one or more entries for a Custodian-to-Endpoint table (CE table); and
wherein the method further comprises updating the CE table for the computer network to account for the network-configuration item.

10. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method, the method comprising:
receiving a remote additive hash representing one or more network-configuration items of a routing-data collection of a remote network node, wherein the remote additive hash represents one or more network-configuration items of the routing-data collection of the remote network node, and wherein at least one of the network-configuration items of the remote additive hash includes reachability information for a network node of a computer network;
computing a local additive hash representing contents of a local routing-data collection of the local network node, based on hashes for a plurality of individual network configuration items of the local routing-data collection;
comparing the local additive hash with the remote additive hash;
responsive to determining that the remote additive hash does not match the local additive hash,
synchronizing the local routing-data collection with the routing-data collection of the remote network node of the computer network, which involves:
comparing the remote additive hash to one or more historical additive hashes for the local routing-data collection;
responsive to determining that the remote additive hash does not match at least one historical additive hash of the local routing-data collection, identifying and obtaining one or more network-configuration items from the routing-data collection of the remote network node that are missing from the local routing-data collection; and
adding the missing one or more network-configuration items to the local routing-data collection.

11. The storage medium of claim 10 , further comprising:
receiving a filter from the remote network node, wherein the filter indicates selection criteria for selecting network-configuration items that are desired by the remote network node;
determining, from the local routing-data collection, a set of network-configuration items that satisfy the filter's selection criteria; and
generating the local additive hash using the network-configuration items that satisfy the filter's selection criteria.

12. The storage medium of claim 11 , wherein synchronizing the routing-data collection involves:
generating a filtered collection of network-configuration items that includes, from the network-configuration items that satisfy the filter's selection criteria, one or more network-configuration items that are missing from the remote routing-data collection; and
sending structured names for the network-configuration items of the filtered collection to the remote network node.

13. The storage medium of claim 10 ,
wherein synchronizing the local routing-data collection further involves:
comparing the remote additive hash to one or more historical additive hashes of the local routing-data collection to determine a matching historical additive hash; and
determining, based on the matching historical additive hash, one or more network-configuration items to send to the remote network node.

Assignees

• Palo Alto Res Ct Inc

Inventors

• Jacobson Van L
• Mosko Marc E

Classifications

• H04L45/021 Primary

  Ensuring consistency of routing table updates, e.g. by using epoch numbers · CPC title