1. Field
This disclosure is generally related to computer networks. More specifically, this disclosure is related to propagating routing information across network nodes of a computer network using database synchronization operations.
2. Related Art
Link-based routing protocols, such as Intermediate System to Intermediate System (IS-IS) and Open Shortest Path First (OSPF), propagate link state information across a network by sending link-state advertisements (LSAs) to neighboring network nodes. When a network node receives an LSA, the network node can create an updated graph for the map of the network, and updates a routing table to indicate a first node along a shortest path to each network node.
In link-based routing protocols, it is important that all nodes of a computer network operate under the same network map to prevent forwarding packets in a routing loop within the network. To maintain a synchronized network map, network nodes propagate a received LSA to other neighboring nodes of the computer network, which allows other neighboring nodes to update their routing table.
Oftentimes, an LSA is propagated to a network node that has previously received and propagated the same LSA. Unfortunately, to avoid propagating the LSA in a forwarding loop, a typical network node has to store state information that indicates which neighboring nodes have received which LSAs from the network node. Further, when the network node receives an LSA, the network node has to search through this state information to determine which nodes have not received the LSA, and avoids sending the LSA to all other neighboring nodes. Thus, network nodes experience an undesirable storage cost and computation cost to synchronize link state information across the network.