This invention relates to the field of communication systems, and in particular to network management and network simulation.
Routers are used in networks to forward messages from one node to another in the network until the message reaches its intended destination. Routers use “forwarding tables”, or “routing tables” to facilitate the determination of the appropriate node to forward each message. For ease of reference, the term ‘router’ is used herein to refer to any device or system that is used to forward messages based on an address associated with the communication, including communication switches and the like. In like manner, the terms ‘forwarding table’ or ‘routing table’ are used herein to refer to any directives or indices that the router uses to select a communication path for each message or group of messages, regardless of whether these directives or indices are in the form of a table, and include, for example, virtual routing tables, forwarding information bases (FIBs), and so on.
FIG. 1 illustrates an example network, and an example set of forwarding tables 101A-101E corresponding to the routers A-E of this network. In this example, circles are used to indicate routers, and squares are used to indicate destination sub-networks. As illustrated in FIG. 1, each entry in each router's forwarding table includes a prefix 110, a source protocol 120, a next hop 130, and a metric 140. The prefix 110 is the network address corresponding to a range of destination addresses. The source protocol 120 is the communication protocol for use of this entry in the forwarding table. The next hop 130 identifies the router to which the message will be transmitted if this entry is used. The metric 140 identifies the “cost” associated with transmitting the message to the destination if this entry is used.
In the example forwarding table, symbols A-H are used to indicate the addresses of the routers, and W-Z are used to indicate the sub-network prefix addresses. In an actual forwarding table, actual addresses, such as an IP address, would appear. Also in actual tables, ranges of addresses are used in lieu of individual prefixes 110, and, optionally, a default (“def”) or “last resort” entry 111 may be used to identify a next-hop for prefixes that are not explicitly included in the forwarding table. In like manner, the symbol P is used in the example forwarding tables to indicate a protocol, although the actual protocol, such as “OSPF” or “BGP” would appear in an actual forwarding table. Other information may also appear in a forwarding table.
In the example of FIG. 1, the links between routers include a figure/metric that represents the example cost of communicating a message unit between the routers. For example, to send a message unit between routers A and B, the cost is “1”, whereas to send a message between routers A and F, the cost is “2”. Also in this example, the cost of communications between a sub-network and its supporting router is assumed to be zero.
Typically, each router broadcasts its forwarding table to each other router in the network. If the network is large, network ‘areas’ may be defined to limit the ‘flooding’ of this information throughout the network, and/or other hierarchical structures may be used. The receiving router selectively updates its forwarding table based on the entries of each of the received other forwarding tables. The cost of using each route in a neighbor's forwarding table is determined from the neighbor's metric entry 140, plus the cost of reaching that neighbor. Based on these metrics, and perhaps other criteria, depending upon the particular protocol, each router determines a preferred next-hop for each address and/or each range of addresses, including the ‘last resort’ next-hop.
Once a network is established, all of the forwarding tables achieve a ‘steady state’, or ‘converged’ condition, wherein each router includes a preferred next-hop entry for each destination address. For example, based on the link cost/metrics illustrated in FIG. 1, a message at router F with a destination address having a prefix W has a total cost/metric of “3” 141, based on an F-A link cost of “2” plus an A-C link cost of 1. To achieve this cost/metric of “3”, the message should be routed from node F to preferred next-hop “A” 131. This steady state does not change unless and until a change occurs in the network. Such changes may be intentional or unintentional, where unintentional changes include mistaken or unintentional reconfigurations of routing parameters, undetected component or link failures, and so on.
Conventional routing protocols are purposely designed to be robust, and provide for dynamic updating of the routing tables when faults occur. Often, a network's performance degrades gradually over time, to the point that the performance becomes unacceptable; but, because of the fault-masking provided by dynamic routing protocols, the cause(s) of the problem may not be readily apparent.
It is an objective of this invention to provide a method and system for identifying potential causes of degradations in network system performance. It is a further objective of this invention to provide a method and system for identifying intentional and unintentional changes to routing table entries.
These objectives and others are achieved by providing a simulator that simulates routing system protocols to build routing tables corresponding to a modeled network, and comparing the routing tables in the actual network to these simulator-created routing tables. Because the modeled system represents a fault-free version of the actual system, and assuming that the modeled routing system protocols are representative of the algorithms used in the actual routers, these simulator-produced routing tables will represent the ‘ideal’ routing tables that should be present in the routers of the actual network. By querying each router in the actual network for its routing table and comparing each routing table to the corresponding simulator-produced routing table, any differences from the ‘ideal’ can be identified.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.
USPTO Backgrounds
USPTO Backgrounds