Embodiments of the present invention relate to networking, and more particularly to techniques for updating routing table information in a network device such as a router.
A networking environment typically comprises multiple networks. The networks may be of the same or different types and may use the same or different communication protocols for communication of data. Communication of data within the networks and also between the networks is typically facilitated by network devices such as routers, switches, etc. A network device may be referred to as a node. A node may be connected to one or more other nodes. A node may also be connected to one or more networks. A network may also be referred to as a leaf.
In a typical network environment, the number of network devices (i.e., the number of nodes) is generally far less than the number of networks (i.e., the number of leaves) that are connected by the nodes. For example, the number of nodes in a network environment may be in the order of hundreds while the number of leaves or networks is typically in the order of ten thousand, hundred thousand, etc. The number of leaves in a network environment is thus typically several orders of magnitude greater than the number of nodes.
In order to facilitate communication of data, a node, such as a router, needs to know the topology of the overall network environment. The topology information is used by the node to determine how data packets received by the node are to be forwarded to facilitate communication of the data packets from the sender of the packets to the intended destination for the data packets. Various different protocols are presently used to distribute topology information between the various nodes. For example, in a link state protocol (e.g., Intermediate System-Intermediate System (IS-IS), Open Shortest Path First (OSPF)), each node in the network environment advertises connectivity information to its neighbors including information identifying links to neighboring nodes and costs associated with the links. The cost associated with a link may be based upon various different metrics such as link bandwidth, delay, etc. The cost associated with a link while carrying data in one direction may be different from the cost associated with the same link while carrying data in the opposite direction.
A node then determines an optimum route from the node to each other node in the network environment based upon the advertised information received by the node from other nodes. A Shortest Path First (SPF) algorithm (e.g., using Dijkstra's algorithm) is commonly used to determine these optimum routes. The SPF algorithm generates a shortest path tree (SPT) that is rooted at the node executing the SPF algorithm and identifies an optimum path from the root node to each other available node (which may be a router) in the network environment. An optimum path from the root node to another node may comprise intermediate nodes.
Further, a node may also “own” or advertise one or more leaves. A node owning or advertising a leaf provides connectivity to that leaf. A node may own or advertise multiple leaves. A leaf may be advertised by multiple nodes.
Information regarding nodes and leaves advertised by the nodes is used to supplement the nodes in the SPT. In this manner, the SPT is expanded to add leaves information for the nodes in the SPT. The expanded SPT is then used to determine routing information for the root node (i.e., the node generating the SPT). The routing information for the root node includes information regarding routes from the root node to one or more leaves, which may be advertised by the root node or by other nodes. For example, the routing information may include information identifying zero or more leaves advertised by the root node. For a leaf not advertised by the root node, the routing information may identify a next hop node from the root node for reaching the leaf. The next hop node may be a node advertising the leaf or some other intermediate node.
The routing information for the root node is typically stored in a routing information database in the root node. This stored information is commonly referred to as the routing information base (RIB). The information in the RIB stored by a node thus indicates routes from the node to leaves in the network environment. Since the number of leaves in a network environment can be very large, (e.g., in the tens of hundreds of thousands), the number of routes for which information is stored in the RIB is usually very large, even though the number of nodes in the network environment may be small.
When a node receives information indicating a change in the topology of the network environment, the node recalculates its SPT (by running a full or incremental SPF algorithm) and updates its RIB based upon the recalculated SPT and the leaves information. In a typical conventional implementation, as part of the RIB updates, each node and leaf in the RIB has to be visited and processed to see if information related to the node or leaf is to be updated. However, due to the very large number of leaves that are typically present in the network environment, updating the routes information in the RIB is a very time consuming process that uses valuable processing and memory resources of the node.
USPTO Backgrounds
USPTO Backgrounds