Method and apparatus for managing a network using link state information

A method is disclosed for managing a network having a plurality of network elements, where the network elements are configured to be interconnected to one another. A data structure is maintained that includes information about a link state for each network element in the plurality of network elements. The link state for each network element describes a connection between that network element and at least one other network element designated to be connected to that network element. A management policy is configured for the plurality of network elements by using link state information in the data structure to detect if any of the plurality of network elements are unreachable.

FIELD OF INVENTION

The present invention generally relates to managing elements of a network. The invention relates more specifically to managing elements of a network using link state information.

BACKGROUND OF THE INVENTION

Network management systems are programmatic tools, services, applications or devices that implement management functions, policies and controls on a network. In many cases, management systems are employed to facilitate human managers who supervise operations of the elements in the network. For example, networks may operate performance management to enhance network performance, configuration management to monitor and manage network configurations for interoperability between network elements, accounting management to manage availability of resources, fault management to detect and manage network problems, and security management to implement firewalls, authentication and authorization.

The actions carried out by such network management systems may be governed by one or more network management policies, which are abstract expressions about how a particular network is managed. Specific examples of commercial products that support creation and management of management policies for a network include CiscoAssure Policy Networking, and Cisco Quality-of-ServicePolicy Manager, from Cisco Systems, Inc.

In policy management systems, management policies are usually implemented through use of one or more workstations. The workstations are often operated separately than other network elements. One function performed on these workstations when implementing a management policy is to detect when elements of the network are down. In theory, elements that are down have lost connectivity with the network for some reason. The management systems may detect the unreachable elements, and implement management policies that account for or compensate for the unreachable elements. In this context, network elements may include routers, switches, gateways, hubs, bridges, switch controllers, etc.

Typically, management systems identify unreachable elements by repeatedly polling each pertinent element of the network. If a response is not detected from the element polled, the element is assumed to be down or failed. The polling is usually done using protocols such as Simple Network Management Protocol (SNMP), User Datagram Protocol (UDP), or Telnet. Internet Control Message Protocol (ICMP) may also be used to poll elements (i.e. “ping”).

Polling requires resources for sending roundtrip communications to the polled devices. Furthermore, protocols such as SNMP and UDP are unreliable on congested networks. Communications sent using these protocols may fail with too much traffic, and little feedback is provided to notify the elements exchanging the communication that the communication failed.

The result is that using polling to query managed devices often generates inaccurate results regarding the health of a network. Elements of the network may be indicated as failed, when in fact the system was too congested to be able to poll that element using a protocol such as SNMP or UDP. In addition, the polling performed on the managed devices adds to network congestion, and consumes network resources. The managed devices that are polled to detect the health of the network also add overhead and cost to operation of the network.

Based on the foregoing, there is a clear need for an efficient manner to determine the health of a network.

There is a specific need to accurately detect whether network elements are down or unavailable for the purpose of implementing a management policy.

SUMMARY OF THE INVENTION

Aspects of the invention provide a method and apparatus for managing a network using link state information. According to an aspect, link state information for network elements is accessed to determine whether any network elements are unreachable on the network. A management policy is configured to account for any unreachable network elements.

The link state information may be accessed from a management device, network element, or router. In one implementation, the link state information is provided as an inherent feature of using a link state protocol and/or router.

In other aspects, the invention encompasses a computer apparatus, a computer readable medium, and a carrier wave configured to carry out the foregoing steps.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

A method and apparatus for managing networks using link state information is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

Embodiments of the invention provide for managing network elements of a network using link state information. In an embodiment, the managed network includes a plurality of network elements that are communicatively coupled to one another. A data structure is accessed that includes information about a link state for individual network elements in the plurality of network elements. The link state information for each network element describes a connection between that network element and at least one network element designated to be connected to that network element. A management policy is configured for the plurality of network elements by using the data structure to detect if any of the plurality of network elements is unreachable from another network element.

In one embodiment, the link state information is collected at a network management system using a link state protocol, based on values that are created and maintained locally in each network element. For example, the link state information may be obtained using a link state protocol from link state tables that are maintained in a router for the purpose of enabling the router to select a next hop for a path by selecting a next hop router that is on an active link. In a managed device that uses SNMP, the link state information may be maintained in an existing Management Information Base (MIB). Such link state information is initially created and managed locally, at the network element, based on its immediate and local knowledge of the state of its links to other network elements, and then conveyed to the network management system using a link state protocol.

Using these embodiments, network elements may be managed with more accurate assumptions regarding the health of a network. Specifically, a management device may configure policies for network elements to account for unreachable network elements. The managed device does not have to poll network elements individually to identify that a network element is unreachable. As such, traffic congestion does not cause the managed device to configure a policy that mistakenly accounts for a network element as being unreachable, when in fact the network device is reachable. In particular, because the link state information is created and managed locally, and collected at the network management system using a reliable link state protocol, its accuracy and validity is not affected by the inherent unreliability of protocols such as UDP during polling. If congestion is sufficient to disrupt the link state protocol, the affected element(s) would, in fact, become unreachable. Furthermore, by using link state information, the management device avoids adding to traffic congestion on a network. Collecting the link state information may be an inherent aspect of the network, so that accessing such information does not add to traffic or overhead.

Network elements may also include routers, switches, gateways, hubs, bridges, switch controllers. Network elements may be managed, configured and/or controlled by managed devices. Managed devices may also include clients that can perform some networking functions for the network. The term interconnected or communicatively coupled means that two or more elements can exchange communications, either directly or indirectly. Specifically, interconnected network elements may exchange communications with no intermediate elements or components, or through the use of intermediate elements and components that forward a communication intended for a recipient.

A link state is the connectivity status of the network or the elements within the network. A link state of a network element describes whether the network element is connected to adjacent network elements. Link state information is information that describes the link state. The information may be indirect such as in the form of network addresses for network elements that are reachable. The information may also be direct, such as in the form of coded values that identify a particular state of a particular link.

In conventional usage, link state information is stored and processed by routers on a network. A router use the link state information to determine routes for communication packets that are processed by that router. The router may select a path for a communication packet by comparing network distances to the next hop or destination of the communication packet.

In contrast to conventional usage, embodiments of the invention use link state information to determine whether network elements are reachable to management devices of a network. The use of link state information in this manner may substitute or reduce the need for the management devices to determine the health of the network elements by consuming bandwidth and resources to continuously poll the network elements.

A network element that is unreachable means that the network element cannot be contacted if a communication is sent to that network element. An unreachable network element may be failed, overloaded, disconnected, or over-congested. If a network element is determined to be unreachable, it does not necessarily mean that the network element is in fact unreachable. Specifically, soon after the element's reachability has changed, other elements may have a stale, inaccurate view of the device's reachability. The determination that the network element is unreachable may be false, but the management device or other components may use the determination to configure a management policy on the assumption that the determination is true.

A management policy may be configured on network elements using an element management system or network management system. The term configured means that the policy may be initiated, implemented, discontinued, modified or reconfigured. The element management system may configure the policy on one or more of the network elements in the network. Examples of policies that can be implemented include a Quality-of-Service policy and a firewall policy. Other policies for features such as performance, fault, security, and configuration management may also be provided. According to an aspect, an element management system may be an integral component of the network. Alternatively, an element management system may be external to the network elements.

According to an embodiment, a data structure is maintained that includes information about a link state for each network element in the plurality of network elements. The data structure may be updated using information exchanged between adjacent network elements.

Adjacent network elements are network elements that are designated to be directly connected to one another. That is, adjacent network elements communicate with one another without intermediate network elements.

Another embodiment may provide for managing a network having a plurality of network elements. The network elements are configured to be interconnected to one another. The network elements include a first router that maintains link state information about the interconnectivity of the plurality of network elements.

The link state information may be accessed from the first router. A management policy is configured for the plurality of network elements by subsequently determining if one or more of the plurality of network elements is unreachable. The determination is made using the link state information from the first router.

Another element provides that the plurality of network elements are operated so that at least some of the network elements automatically provide link state information about connections with adjacent network elements. This may require that the network elements be operated using a protocol that causes network elements to generate link state information. Examples of such link state protocols include Open Shortest Path First (OSPF) protocol, and Enhanced Internet Gateway Routing Protocol (EIGRP).

Still further, the protocol may be implemented to maintain a structure such as a link state map as an inherent feature of the protocol. The link state map may be maintained on a router that manages operations of the network elements under the protocol.

Alternatively, the link state map may be maintained on one of the network elements in the network, or compiled from separate pieces of link state information provided by multiple network elements in the network.

B. System Description

FIG. 1is a block diagram that illustrates an overview of a network where link state information is used to manage network elements.

A network100includes a plurality of network elements110. The network elements110are interconnected by one or more links. An element management system (EMS)120manages one or more of the network elements110.

In an embodiment, the network elements110are operated under a link state protocol. As a result, the network elements110are configured to automatically provide link state information. The link state information from each network element110provides information about the status of the connection between that network element110and an adjacent network element. For example, the link state information for network element A may provide the status of element A's connection with elements B and C.

For some link state protocols such as OSPF and EIGRP, each network element110broadcasts to adjacent elements the link state information for that network element. If one network element fails, an adjacent network element will detect the failure and broadcast it. The network elements110that are operational pass the link state information on to other network elements110.

Alternatively, the link state information may be generated and passed on to a router that is authoritative to a network management workstation. The router for the network elements110may access the link state information to know which network elements are operational for purpose of routing communications to the network elements110.

The generation of link state information and its maintenance on network elements110or routers can be inherent functions of a link state protocol. An embodiment provides that the link state information is used to manage one or more network elements. In an embodiment such as shown withFIG. 1, link state information may be maintained on one of the network elements110, or on EMS120.

The EMS120configures a policy to manage network elements110. The policy may be configured by accessing link state information112for network elements110. The link state information112may be accessed from one of the plurality of network elements110, or from a router such as described withFIG. 2. The link state information112provides the status of the links for all of the network elements110.

Under one embodiment, EMS120receives the link state information112by communicating with only one network element110. This allows for EMS120to know the status of each network element110without having to expend resources and congest traffic by polling or otherwise communicating with each network element110separately.

In response to accessing the link state information, EMS120signals policy actions114to one or more network elements110. The policy actions114may configure a policy for network100. For example, if one of the network elements110is detected as being down, EMS120may communicate policy actions114to other network elements110to account for the unreachable network element. The workload of the unreachable network element may be distributed to other network elements110. Adjacent network elements may be configured to increase monitoring of the unreachable network element to see if the unreachable network element can recover.

In an embodiment, EMS120provides an operator interface122that provides feedback about the status of the network elements110. For example, EMS120may visually inform an operator that one or more network elements110were detected as being unreachable. The operator interface122may also receive commands or instructions that configure the policy being implemented on one or more of the network elements110.

FIG. 2is a block diagram that illustrates an overview of a network where link state information from a router is used to manage network elements.

A network200includes a device210that is part of an interconnected group of network elements. The device210may be managed by EMS230, operating on a workstation connected to or within the network200. A router220includes a routing engine224. The router220is also configured to include a health agent228that communicates with EMS230.

The routing engine224of router220functions to route communications such as data packets to different destinations within network200. The routing engine224receives link state information212from the interconnected network elements of network200as an inherent feature of the protocol being employed. The link state information212indicates which network elements110are reachable. The health agent228reports the status of reachable and/or unreachable items to EMS230.

In an embodiment, EMS230is initially configured to query routing engine224to receive a list of managed devices within network200. These managed devices correspond to network elements that provide link state information to routing engine224. The EMS230maintains a list of managed devices within network200from the initial query. Periodically, EMS230queries routing engine224to update the list.

There are several ways in which EMS230can use link state information212received from routing engine224to manage devices within network200. In one embodiment shown, router220is equipped with health agent228to receive or process link state information212that indicates one of the network elements of network200is unreachable. The health agent228signals a communication214to EMS230that includes information derived from link state information212.

For example, link state information212may indicate device210is unreachable. The health agent228may then send a communication214to EMS230to notify or instruct EMS230check device210. Alternatively, EMS230may assume device210is unreachable using link state information provided in communication214. The EMS230may then configure the management policy based on that assumption.

It is also possible for a combination of polling and notification to be used. For example, EMS230may still poll device210, but less frequently, relying in part on health agent228notifying EMS230of device210being unreachable. Also, EMS230may use link state information228to confirm that device210is unreachable after polling the device.

In another embodiment, EMS230queries router220about specific devices within network200. The queries are to determine whether those devices or reachable for purpose of receiving communications from EMS230. For example, EMS230may be configured to implement a policy for device210. The EMS230may periodically query routing engine224to determine whether device210is operational. EMS230may even poll device210, but the polling is made to a device that is outside of network200. Furthermore, EMS230needs to communicate with only one device to check on the status of multiple devices within network200. Therefore, the chance that network congestion would result in receiving false information is reduced by polling router220, rather than polling individual network elements of network200.

According to another embodiment, health agent228sends EMS230link state information for network elements of network200on a periodic basis. The link state information may be in the form of addresses for reachable network elements. The EMS230may be able to determine which network elements are not reachable for implementing the management policy.

A protocol for establishing communications between EMS230and router220may be established by enabling EMS230to declare itself to router220as another router. Other protocols may be implemented to enable link state information to be easily exchanged between router220and EMS230.

Still further embodiments allow for health agent228or router220to provide a summary of link state information, such as a table or other data structure that indicates the status of network elements of network200.

C. Methods for Implementing Embodiments

FIG. 3illustrates a method for accessing link state information to configure a management policy.FIG. 4illustrates a method for accessing link state information to identify the link status of a networkFIG. 5is a flow chart illustrating a method for using link state information to configure a management policy on a network operating a link state protocol.

For purpose of illustrating a simple example, the methods ofFIG. 3,FIG. 4, andFIG. 5are described herein in the context ofFIG. 1orFIG. 2, and elements ofFIG. 1orFIG. 2. However, the methods ofFIG. 3,FIG. 4, andFIG. 5are not limited to that specific context, but are broadly applicable for purposes identified in this disclosure.

FIG. 3is a flow chart illustrating a method for accessing link state information to configure a management policy. In step310, link state information is maintained for a network. The link state information describes the link state of each network element in the network. The link state information indicates whether those network elements are reachable or unreachable by a management device.

In step320, a determination is made as to whether the link state information indicates whether one of the network elements110has become unreachable. The determination may be general so as to not uniquely identify which network elements110are unreachable. The determination may be made by receiving link state information that describes the status of the interconnected network elements110as a whole. The link state information may be periodically updated by broadcasts from the network elements. The link state information may determine unreachable items exist if network elements indicate that one or more of their adjacent network elements are unreachable.

If step320determines that the link state information indicates all of the network elements are reachable, step330provides that the management policy is implemented without provisions for an unreachable item.

If step320determines that there is at least one network element110that is unreachable, then step340provides that the unreachable network element(s) are identified. This may be performed by polling each network element in response to detecting that there was an unreachable element.

Step350provides that the management policy accounts for the identified unreachable element(s). This may involve signaling policy actions to other network elements to account for or accommodate the unreachable item. The management policy may also signal policy actions to confirm through polling that the identified network element is unreachable. Alternatively, an operator may be informed of the unreachable item.

An embodiment described withFIG. 3provides that the unreachable network element is identified in a separate step from the determination of whether any unreachable items exist. In such an embodiment, the determination that a network element is unreachable is general, and not specific to any one network element. For example, step320may determine only that a chain of interconnected network elements110in the network100is broken. A subsequent determination is required to identify the particular network element110that is unreachable.

In another embodiment, the determination of whether any unreachable network elements exist is performed in conjunction with identifying all of the network elements110that are unreachable or reachable. This may be accomplished by maintaining a link state data structure that has information about all of the link states. An example of such a data structure is shown inFIG. 6.

FIG. 4is a flow chart illustrating a method for accessing link state information to identify the link status of a network. In step410, link state information is accessed for interconnected network elements110of network100.

In one embodiment, link state information may be accessed from a device such as a router. The router may be internal or external to network100. In another embodiment, link state information is accessed from one of the network elements110. Still, another embodiment provides that EMS120receives and maintains link state information broadcasted or announced from other network elements110.

In step420, a determination is made as to whether there are any unreachable network elements. This step may be performed when link state information is periodically updated. Link state information may be updated by compiling information from periodic announcements and broadcasts about the link state of each network element110in network100.

If step420determines that there are no unreachable items, then step430provides that a management policy for network elements110is configured by EMS120with no adjustments or accounting for unreachable items.

If step420determines that there are unreachable items, then step440provides that a management policy for network elements110is configured to account for the unreachable network elements. For example, policy actions114(FIG. 1) may be signaled to cause other network elements10to perform the functions of the unreachable network element10. The policy actions114may also be used to communicate the link state information to an operator or human manager.

FIG. 5is a flow chart illustrating a method for using link state information to configure a management policy on a network operating a link state protocol. In step510, elements of network100are operated using a link state protocol. Link state protocols require network elements to provide link state information as an automatic aspect of their operation. Examples of link state protocols include OPSF and EIGRP. Elements operating under a link state protocol may be employed with router220.

In step520, a link state data structure is maintained for interconnected network elements of network100. The link state data structure may provide information that indicates whether specific network elements are reachable and/or unreachable. For network200, link state data structure may be maintained with periodic communications with router220. For network100, one or more elements may maintain link state information for elements of network100, or provide that information to EMS120, which maintains the link state data structure.

In step530, unreachable elements are detected using the link state data structure. For example, in network200, EMS230may receive an update to the link state data structure from router220that indicates one of the elements of network200has changed link states, and is now unreachable. In network100, one of the network elements110may receive the update to the link state data structure, and EMS120may be notified of that update.

In step540, a management policy is configured to account for unreachable network elements. The management policy may be implemented by EMS230. If a management policy is in operation before one of the network elements becomes unreachable, the EMS230may reconfigure the management policy to account for the unreachable network element. For example, tasks performed by an unreachable element may be terminated and/or transferred to other network elements.

D. Illustrative Link State Structures

FIG. 6shows an illustrative link state data structure for identifying link states of individual network elements in a network.

A link state data structure600as shown may be compiled, maintained and/or updated using link state information provided by network elements operated under a link state protocol. In the example provided, link state data structure600provides link state information for a configuration of network elements110shown inFIG. 1. The link state data structure600may be maintained on router220(FIG. 2) for the network, one of the network elements110, or on EMS120that manages network elements110.

The link state data structure600includes a first column610listing identifiers to each network element110in network100. A plurality of adjacent columns are provided to describe a link and link state with another network element. Each interconnected network element110has one or more links. In an example such as provided withFIG. 1, each network element110includes two adjacent network elements. A greater or lesser number of adjacent network elements may be provided for each network element110.

The second column620and third column630identify the adjacent network elements for each network element listed in first column610. The second column620and third column630also list the connectivity status for the adjacent network elements of each network element listed in first column610. For example, HostA has HostB and HostC as adjacent network elements (SeeFIG. 1). As shown byFIG. 6, HostD and HostE have link status information that indicates HostF is unreachable.

The link and link status information may be represented in different ways. It is possible for the connectivity status to be integrated with the link identifier. For example, columns620and630may carry addresses of network elements110. If the addresses are present in columns620and630, the implication is that the item is reachable. The link status may also be separate from the identifier of the link. For example, columns620and630may list addresses of adjacent elements whether those elements are connected or not. A separate indication may be used to identify whether the link is reachable or unreachable.

The specific table format of link state data structure600is provided as an example, and is not required. Any suitable mapping of host names to links may be used.

E. Hardware Diagram

FIG. 7is a block diagram that illustrates a computer system upon which an embodiment may be implemented.

Computer system700includes a bus702or other communication mechanism for communicating information, and a processor704coupled with bus702for processing information. Computer system700also includes a main memory706, such as a random access memory (“RAM”) or other dynamic storage device, coupled to bus702for storing information and instructions to be executed by processor704. Main memory706also may be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor704. Computer system700further includes a read only memory (“ROM”)708or other static storage device coupled to bus702for storing static information and instructions for processor704. A storage device710, such as a magnetic disk or optical disk, is provided and coupled to bus702for storing information and instructions.

The invention is related to the use of computer system700for managing elements of a network using link state information. According to one embodiment of the invention, managing elements of a network using link state information is provided by computer system700in response to processor704executing one or more sequences of one or more instructions contained in main memory706. Such instructions may be read into main memory706from another computer-readable medium, such as storage device710. Execution of the sequences of instructions contained in main memory706causes processor704to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.

Computer system700also includes a communication interface718coupled to bus702. Communication interface718provides a two-way data communication coupling to a network link720that is connected to a local network722. For example, communication interface718may be an integrated services digital network (“ISDN”) card or a modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface718may be a local area network (“LAN”) card to provide a data communication connection to a compatible LAN. Wireless links may also be implemented. In any such implementation, communication interface718sends and receives electrical, electromagnetic or optical signals that carry digital data streams representing various types of information.

Computer system700can send messages and receive data, including program code, through the network(s), network link720and communication interface718. In the Internet example, a server730might transmit a requested code for an application program through Internet728, ISP726, local network722and communication interface718. In accordance with the invention, one such downloaded application provides for managing elements of a network using link state information, as described herein.

The received code may be executed by processor704as it is received, and/or stored in storage device710, or other non-volatile storage for later execution. In this manner, computer system700may obtain application code in the form of a carrier wave.