High availability architecture for network devices

A method and apparatus allows for continued operation of one or more applications running at a network device with reduced delay despite crashes or failures at that device. The network device includes two or more supervisor cards for running the applications and a plurality of line cards. According to the invention, one supervisor card is designated the active supervisor card and one supervisor card is designated the standby supervisor card. As changes in state and other operating conditions take place on the active supervisor events are generating for passing at least some of this information to the standby supervisor where it is stored. Following a crash or failure of the active supervisor card, the standby becomes the newly active supervisor card. The standby supervisor performs a consistency check with the line cards and resets those that fail the check. The standby supervisor also determines which data records and state information stored at the standby supervisor are valid, and begins running the applications loaded onto the device. Those data records and state information determined by the standby supervisor to be valid are utilized by the applications in continuing their operation, while invalid data records and state information are discarded.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates generally to computer networks, and more specifically, to a method and apparatus for quickly resuming the operation of selected applications and processes despite crashes and failures.

2. Background Information

A computer network typically comprises a plurality of interconnected entities. An entity may consist of any device, such as a computer or end station, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication protocol (LAN standard), such as Ethernet, FDDI or token ring, that defines the functions performed by the data link and physical layers of a communications architecture (i.e., a protocol stack). In many instances, several LANs may be interconnected by point-to-point links, microwave transceivers, satellite hook-ups, etc. to form a wide area network (“WAN”) or intranet that may span an entire country or continent.

One or more intermediate network devices are often used to couple LANs together and allow the corresponding entities to exchange information. For example, a bridge may be used to provide a “bridging” function between two or more LANs. Alternatively, a switch may be utilized to provide a “switching” function for transferring information between a plurality of LANs or end stations. Bridges and switches may operate at various levels of the communication protocol stack. For example, a switch may operate at layer 2 which, in the Open Systems Interconnection (OSI) Reference Model, is called the data link layer and includes the Logical Link Control (LLC) and Media Access Control (MAC) sub-layers. Data frames at the data link layer typically include a header containing the MAC address of the entity sourcing the message, referred to as the source address, and the MAC address of the entity to whom the message is being sent, referred to as the destination address. To perform the switching function, layer 2 switches examine the MAC destination address of each data frame received on a source port. The frame is then switched onto the destination port(s) associated with that MAC destination address.

Other network devices, commonly referred to as routers, may operate at higher communication layers, such as layer 3 of the OSI Reference Model, which in TCP/IP networks corresponds to the Internet Protocol (IP) layer. Data frames at the IP layer also include a header which contains an IP source address and an IP destination address. Routers or layer 3 switches may re-assemble or convert received data frames from one LAN standard (e.g., Ethernet) to another (e.g. token ring). Thus, layer 3 devices are often used to interconnect dissimilar subnetworks.

Bridges, switches and routers, like computers, typically have one or more processing elements and memory elements interconnected by a bus. They also include one or more line cards each defining a plurality of ports that couple the respective devices to each other, to the LANs and/or to end stations of the computer network. Ports that are used to couple two network devices together are generally referred to as a trunk ports, whereas ports used to couple a network device to a LAN or an end station(s) are generally referred to as access ports. The switching and bridging functions include receiving data from a sending entity at a source port and transferring that data to at least one destination port for forwarding to the receiving entity.

Switches and bridges typically learn which destination port to use in order to reach a particular entity by noting on which source port the last message originating from that entity was received. This information is then stored by the bridge in a block of memory referred to as a filtering database. Thereafter, when a message addressed to a given entity is received on a source port, the bridge looks up the entity in its filtering database and identifies the appropriate destination port to reach that entity. If no destination port is identified in the filtering database, the bridge floods the message out all ports, except the port on which the message was received. Messages addressed to broadcast or multicast addresses are also flooded.

To perform their bridging, switching, and/or routing functions, network devices run a plurality of applications and/or protocols. In particular, a network device may run a protocol, such as the Dynamic Trunk Protocol (DTP), that causes its trunk ports to automatically negotiate with the trunks ports of the second network device to which it is coupled and decide upon a message encapsulation or tagging format in order to support Virtual Local Area Networks (VLANs). For example, the trunk ports may decide to encapsulate messages pursuant to the InterSwitch Link (ISL) protocol from Cisco Systems, Inc. of San Jose, Calif. or the 802.1Q standard from the Institute of Electrical and Electronics Engineers (IEEE).

Network devices may also run the Port Aggregation Protocol (PAgP) from Cisco Systems, Inc. to identify and aggregate redundant trunk and access ports, i.e., two or more trunks that couple the same two network devices or two or more access ports that coupled a device to the same LAN or end station, so as to permit load balancing, among other advantages. In particular, PAgP, which relies on packets exchanged between neighboring devices or with itself, groups redundant ports or links into a single, logical channel.

Many network devices also run a protocol or algorithm to detect and eliminate circuitous paths or loops within the corresponding computer network. In particular, most computer networks are either partially or fully meshed. That is, they include redundant communications paths so that a failure of any given link or device does not isolate any portion of the network. The existence of redundant links, however, may cause the formation of circuitous paths or “loops” within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely. Furthermore, because switches and bridges replicate (i.e., flood) frames whose destination port is unknown or which are directed to broadcast or multicast addresses, the existence of loops may cause a proliferation of data frames that effectively overwhelms the network.

To avoid the formation of loops, most bridges and switches execute a spanning tree algorithm which allows them to calculate an active network topology that is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). The Institute of Electrical and Electronics Engineers (IEEE) has promulgated a standard (the 802.1D standard) that defines a spanning tree protocol to be executed by 802.1D compatible devices. In general, by executing the IEEE spanning tree protocol, bridges elect a single bridge within the bridged network to be the “root” bridge, and each bridge selects one port (its “root port”) which gives the lowest cost path to the root. In addition, for each LAN coupled to more than one bridge, only one (the “designated bridge”) is elected to forward frames to and from the respective LAN. The root ports and designated bridge ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto the corresponding paths or links of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames will not be forwarded to or received from the port. To obtain the information necessary to run the spanning tree protocol, network devices exchange special messages called configuration bridge protocol data unit (BPDU) messages.

To facilitate the management of VLANs, a network device may run the VLAN Trunk Protocol (VTP) from Cisco Systems, Inc. VTP is a Layer 2 messaging protocol that maintains VLAN configuration consistency by managing the addition, deletion, and renaming of VLANs across the network. With VTP, a network administrator can make VLAN configuration changes at a single network device and have those changes propagated to most if not all of the network devices in the corresponding computer network or domain.

U.S. Pat. No. 6,049,834 to Khabardar, et al describes a Layer 3 Unicast Shortcut Protocol that may be run by a network device. This protocol allows routers to download shortcut decisions to switches so that they can make certain layer 3 routing decisions.

These applications and protocols typically execute on a supervisor card disposed within the network device and/or on one or more line cards or modules disposed within the network device. To carry out their various functions, these applications or protocols transition among a plurality of states and save configuration and state information in one or more data structures. If the supervisor card crashes or fails, the network device is generally rendered inoperative and must be re-started or replaced. This may result in significant disruption to the network including a potential loss of connectivity for one or more entities.

To provide redundancy, some network devices include a second supervisor card. As described inUsing Redundant Supervisor Enginesfrom Cisco Systems, Inc., the Catalyst 5500 and 6000 series of network devices from Cisco Systems, Inc. include two supervisor cards. Each of these cards, moreover, includes a network management processor (NMP) and memory resources, among other components, for running these applications and protocols. One of the supervisor cards is designated the active card while the other is designated the standby card. If a crash or failure occurs on the active supervisor card, the standby card takes over and begins running the applications and protocols. Each application and protocol, however, must be started from its initialization state on the back-up supervisor card. That is, each application and protocol begins as if the network device were just powered-up.

For example, the PAgP protocol begins transmitting packets to see whether the network device has any redundant trunk or access ports that can be aggregated into a single, logical channel. This occurs even though the PAgP protocol, as it ran on the failed supervisor card, may have previously identified several redundant links or ports and aggregated them into corresponding channels. The STP protocol similarly re-starts its computations for each port of the network device. That is, the STP protocol running on the back-up card transitions all ports to the blocking or listening states and begins transmitting BPDU messages assuming it is the root.

This process of re-starting all of the applications and protocols from an initialization state following a failure or crash at the active supervisor card can delay the forwarding of messages by the network device for a significant amount of time. In particular, it may take on the order of 30 seconds or more for the device to begin forwarding messages again. Such delays can seriously affect performance of the network. Indeed, such delays can be catastrophic for audio, video and other types of network traffic that cannot accommodate delays in transmission.

Furthermore, short duration failures or crashes of a supervisor card is not an infrequent problem. Failures or crashes can occur due to power fluctuations, glitches in the running of one or more applications or protocols, hardware faults, etc. Accordingly, significant time is often lost re-starting applications and protocols following a failure or crash of the active supervisor card, even though no change in network topology has occurred and the device, including its ports, may ultimately be returned to their original states.

SUMMARY OF THE INVENTION

Briefly, the invention relates to a method and apparatus for continuing the operation of one or more applications, protocols or processes running at a network device with reduced delay despite crashes or failures at that device. The network device includes a plurality of line cards having ports for receiving and forwarding network messages, and two or more supervisor cards for processing at least some of those messages. According to the invention, one supervisor card is designated the active supervisor card and one supervisor card is designated the standby supervisor card. Applications loaded onto the device are run by the active supervisor card and/or the line cards. Disposed on the network device are a series of cooperating facilities for sharing certain application related information, such as data records and state information, with the standby supervisor card which stores that information.

Following a crash or failure of the active supervisor card, the standby becomes the newly active supervisor card, and begins running the applications, protocols and processes loaded onto the device. The standby supervisor also determines which data records and state information stored at the standby supervisor are valid. In particular, the standby determines which events are complete and which remain unfinished. The standby supervisor also queries the line cards to determine which of their state and other information is consistent with the corresponding information stored at the standby supervisor. Data records and state information that are determined by the standby supervisor card to be valid are utilized by the applications in resuming their operation, while invalid data records and state information are discarded. The applications resume operation on the standby supervisor utilizing the state and data record information that was determined to be valid, thereby avoiding significant disruption.

DETAILED DESCRIPTION OF AN ILLUSTRATIVE EMBODIMENT

FIG. 1illustrates a computer network100, which may be a bridged network. The network100preferably comprises a plurality of local area networks (LANs)102–112and servers114,116, such as file servers, print servers, etc. Attached to the LANs102–112are one or more hosts or end stations, such as end station118coupled to LAN108, which may source or sink data frames over the network100. LANs102–112and servers114,116are preferably interconnected through one or more intermediate network devices, such as switches120–126. An end station, such as end station130, may also be connected directly to a switch, such as switch126. Switches120–126, in turn, are interconnected through a series of links128, such as point-to-point links or trunks. More specifically, each switch120–126includes a plurality of ports that are coupled to corresponding LANs, servers, end stations and trunk links, and each port, such as the ports at switch126, may be identified by a corresponding port number (e.g., port1, port2, port3, etc.) Switches120–126are thus able to associate their specific ports with the LANs, switches, servers, etc. that are coupled thereto or otherwise accessible through a given port.

It should be understood that the bridged network100ofFIG. 1is meant for illustrative purposes only and that the present invention will operate with other network designs having possibly far more complex topologies.

FIG. 2is a partial block diagram of switch126in accordance with the present invention. Switch126preferably includes a plurality of supervisor cards202and204(e.g., supervisor cards0and1), and a plurality of line cards or modules206and208(e.g., line cards2and3). Supervisor cards202and204and line cards206and208are interconnected by a high speed message bus210. Each line card206and208comprises a plurality of ports P (e.g., P0–P2)203, a microprocessor (μp)205, a local target logic (LTL) memory207and an up/down link (UDLINK)209, which operates as an interface circuit. The microprocessors205may be configured to run or participate in running of one or more applications, protocols or processes. The ports203of each line card206and208, are interconnected with each other and with the respective UDLINK209by a local bus212that is disposed on the respective line card206and208. The supervisor cards202and204may similarly include their own ports203, LTL memory207, UDLINK209and local bus212.

In order to render forwarding decisions that can be implemented by the switch126, each supervisor card202,204preferably includes an encoded address recognition logic (EARL) circuit214coupled to its UDLINK209. The EARL circuit214executes all forwarding decisions between the ports203of the line cards206and208and the supervisor cards202and204. To that end, each EARL circuit214contains a forwarding engine (FE)216and at least one forwarding table (FWD TBL)218configured to produce a unique destination port index value. The LTL memories207implement “local” forwarding decisions, i.e., forward decisions among the ports203of the same line card or supervisor card.

High speed message bus210is preferably a switching matrix employed to control the transfer of data among the various cards202,204,206and208plugged into the switch126. The UDLINK209of each card basically interfaces between the local bus212at the respective card and the message bus210. Inputs to the various LTL memories207may be received over the respective local buses212, which are driven by the corresponding UDLINKs209. Switch126also includes a common bus220that similarly interconnects the line cards206and208and the supervisor cards202and204to support additional message handling.

Each supervisor card202and204further includes a network management processor (NMP)222and224that may be configured to run or participate in the running of a plurality of applications, protocols or processes implemented at and/or loaded onto switch126. Each supervisor202and204also includes both a run-time memory242and244, such as a random access memory (RAM), and a non-volatile memory246and248, such as a non-volatile RAM (NVRAM). The NMPs222and224are in communicating relationship with the corresponding memories230and234and232and236, in order to store and retrieve information therefrom. Each NMP222and224is also coupled to high-speed bus210, e.g., via the UDLINKs209, and common bus220so that information may be exchanged between and among the NMPs222and224and the line cards206and208.

As indicated above, the NMPs222and224and the microprocessors205can run a plurality of applications, protocols and processes to facilitate the performance of switch126. More specifically, the NMPs222and224may be configured to run the spanning tree protocol (STP), the VLAN Trunk Protocol (VTP), the Unicast Shortcut Protocol, a multicast shortcut protocol, the Port Aggregation Protocol (PAgP) and the Dynamic Trunk Protocol (DTP), among others. The microprocessors205at line cards206and208either alone or in cooperation with the NMPs222and224may be configured to run other applications, protocols and processes which may be in the form of firmware.

Suitable intermediate network device platforms for use with the present invention include but are not limited to the commercially available Catalyst 5000 and 6000 series of switches from Cisco Systems, Inc. of San Jose, Calif.

FIG. 3is a highly schematic, functional block diagram of switch126. In accordance with the present invention, a high availability entity302and304is loaded onto and implemented at each supervisor card202and204. Also running on each supervisor202and204is a communication engine306and308. Running on each line card206and208are a communication engine310and312and a line card manager314and316, which are in communicating relationship with each other. The line card managers314and316also have access to a line card (LC) database318and320and a sequence database322and324. The communications engines306,308,310and312at each card, moreover, are each in communicating relationship with bus220so that messages may be exchanged among the various cards202,204,206and208of switch126.

Each high availability entity302and304includes a plurality of facilities that allow applications, protocols and processes running on switch126to continue operation despite crashes or failures. In the illustrative embodiment, an event-based communication architecture is used to pass information from one supervisor to the other. An event is basically a message containing information about a change, such as a change in state, that took place somewhere on the switch126. In accordance with the invention, there are three basic types of events:

“protocol events”, which are produced by an application, protocol or process running at switch126in response to a change in its operating state or condition;

“system events”, which are caused in response to some un-commanded network change, such as a port or link going from a down condition to an up condition or vice versa; and

“external events”, which are caused in response to some intentional network change, such as a network administrator executing a command at a Command Line Interface (CLI) terminal or screen or automatically by the well-known Simple Network Management Protocol (SNMP).

To implement this event-based architecture, each high availability entity302and304includes a high availability manager326and328, a synchronization (sync) manager330and332, an event manager334and336, an event database338and340and a sequence database342and344. Each high availability entity302and304, moreover, is coupled to the respective communication engine306and308. The synch managers330and332include a synchronization queue (SYNC_Q)350and351. As described below, the SYNC_Qs350and351are used to sequentially buffer messages that are to be transmitted between the supervisors202and204.

The high availability managers326and328, the sync managers330and332and the event managers334and336may each comprise programmed or programmable program instructions or processing elements, such as software programs, modules or libraries, pertaining to the methods described herein that are executable by the respective NMPs or by other processors, processing elements or integrated circuits. These program instructions may be stored at one or more memories, such as memories242,244,246and/or248, or at other computer readable media in order to store and/or transmit the program instructions. The high availability managers326and328, the sync managers330and332and the event managers334and336may also be implemented in hardware through a plurality of registers and combinational logic configured to produce sequential logic circuits and cooperating state machines. Those skilled in the art will also recognize that various combinations of hardware and software components may also be utilized to implement the present invention.

FIGS. 4,7and10–12are flow diagrams of the preferred methods for achieving the high availability objects of the present invention. Prior to its activation, switch126is preferably configured with default information which may be used to run one or more applications, protocols and processes, such as the spanning tree protocol. For example, a network administrator, working either locally or remotely from switch226, in addition to loading executable instructions for running the spanning tree protocol, may set various spanning tree parameters, e.g., bridge priority, root path costs, hello time, maximum age time, forward delay time, etc., and this configuration information may be stored at the switch's non-volatile memories246and248. The network administrator may similarly load executable instructions and may set configuration parameters in order to run other applications or protocols at switch126.

When a supervisor, e.g., supervisor202, is initialized or starts running, it first determines whether there are any other supervisors in the switch126, as indicated at block402(FIG. 4A). If so, the two (or more) supervisors202and204elect or designate one of them to be the “active supervisor”, as indicated at block404. The supervisors202and204may employ any suitable criteria for use in electing one of them to be the active supervisor, such as electing the supervisor card that is inserted into the lowest (or highest) slot number in the switch's chassis. Each supervisor202and204, moreover, may include some mechanism, such as an elector circuit (not shown), to perform the designation. Suppose, for example, that supervisor202is elected to be the active supervisor. All or at least one of the other supervisor cards at switch126, i.e., supervisor204, are then designated “standby supervisors”, as indicated at block406. Upon being designated the active supervisor, the high availability entity302at the active supervisor202preferably synchronizes its default configuration information to the standby supervisor(s), as indicated at block408. For example, with regard to STP configuration information, the active supervisor202sends a copy of the spanning tree parameter values from its non-volatile memory246to standby supervisor204. The standby supervisor204utilizes this information to update the contents of its non-volatile memory248, thereby making them consistent with the information at the active supervisor202.

Next, the applications, processes and protocols loaded onto the active supervisor202, which may hereafter simply be referred to as applications, are initialized and run, as indicated at block410. More specifically, applications352,353and354may be initialized and run on the active supervisor card202. Exemplary applications or protocols represented by blocks352,353and354may include STP, VTP and the Unicast Shortcut Protocol, respectively. Other exemplary applications or protocols include DTP and PAgP. DTP is described in copending, commonly owned U.S. patent application Ser. No. 09/141,231, filed Aug. 27, 1998, and is hereby incorporated by reference in its entirety. PAgP is described in commonly owned U.S. patent application Ser. No. 08/902,638, filed Jun. 30, 1997, now U.S. Pat. No. 5,959,968, and is hereby incorporated by reference in its entirety.

The applications loaded onto the standby supervisor204are not initialized or run, as indicated at block412. Instead, the applications at the standby supervisor204are kept in a dormant or sleeping mode.

One or more applications, processes or protocols may also be run on the line cards206and208by the respective line card managers314and316. These line card-level applications may access the LC databases318and320in order to store and retrieve information and/or data used by the line card-level applications.

Those skilled in the art will recognize that additional and/or other applications, processes or protocols may be running on switch126and that they may or may not take advantage of the high availability objects of the present invention.

Those applications, e.g. applications352,353and354, at the active supervisor202that wish to take advantage of the high availability functions provided by switch126then perform several steps. Specifically, each such application352,353and354defines a logical synchronization database356,358and360, as indicated at block414. Within its logical synchronization database356,358and360, the application then defines one or more synchronization records, which may generally be referred to by reference numbers362,364and366, as indicated at block416. Synchronization records362,364and366contain the data or information that the application wishes to have synchronized to its counterpart application on the standby supervisor204. Specifically, the application developer identifies that data or information which is to be used by the counterpart application on the standby supervisor204in order to continue operation of the application following a crash or failure of the active supervisor202. The logical synchronization databases356,358and360will typically model the state of the respective applications352,353and354.

The synchronization databases356,358and360are “logical” in that they are not a duplicate copy of the information maintained by the application, but preferably a designation that certain of the application's information, as stored in a portion of run-time memory allocated to the application, represents its logical synchronization database. This conserves the switch's memory resources. In the preferred embodiment, logical synchronization databases356,358and360contain only a subset of the entire set of data or information associated with the respective applications so as to conserve processing and communications resources at the switch126.

For example, although the STP defines state variables for the identity of the root bridge, the identity of designated bridge(s), the identity of designated ports and the spanning tree port state of each port, among other things, it preferably only defines a sync record for the spanning tree port state for each port230of switch126. As a result, the identity of the root bridge and the designated bridge(s), among other things, are not synchronized to the standby supervisor202. PAgP preferably defines synchronization records for the PAgP state of each port230, among other information. DTP preferably defines synchronization records for the operational status and operational type of trunk ports and for the negotiation status of trunk ports, among other information.

As described below, although the applications are not running on the standby supervisor204(i.e., they remain in a sleeping mode), synchronization databases370,372,374and376having sync records378,380,382and384, similar to their counterparts on the active supervisor202, are established and maintained on the standby204as well.

Next, each application352,353and354defines or creates one or more event types that the application will use to synchronize data to the standby supervisor204, as indicated at block418. The application also specifies the attributes for each defined event type. For each event type that is defined, the application also specifies whether a sequence number should be generated for instances of that event type, as described below. As a general rule, if an instance of a given event type will result in some action being taken at one or more of the line cards206and208, then the application preferably requests that a sequence number be generated for instances of this event type.

The STP application352, for example, may define a PORT_CHANGE_STATE event type for use in notifying the standby supervisor204that a particular port on a particular line card has changed its spanning tree port state. The PORT_CHANGE_STATE event type may include as its attributes the line card and port number identifying the port whose state is being changed, the VLAN designation associated with the change, if relevant, and the new port state. It may also request a sequence number. The VTP application353may define a MOVE_PORT_TO_VLAN event type whose attributes may include the line card and port number of a port whose VLAN designation is being changed. Additional attributes may include the old VLAN designation and the new VLAN designation. Another application, such as a link/module up/down application or process, may define an ADD_DELETE_PORT event type for use in notifying the standby204whenever a port is added to or deleted from the switch126. Attributes for this event type may include the line card and port number of the port, the VLAN designation of the port and a flag signifying whether the port is being added or deleted. The PAgP and DTP applications may each define NEGOTIATION events for use in notifying the standby204when a port begins negotiating with a neighboring device. One of them may also define an ADD_TO_STP event for use when a given port(s) is ready to be considered by the STP application352.

The applications352,353and354running at the active supervisor202may also register with the event manager334in order to listen to or be notified of the occurrence of specific instances of event types, as indicated at block420. An application, for example, may wish to be notified of the events that it produces and/or one or more events that are produced by other applications running at the active supervisor202. The STP application352, for example, may wish to know whenever a port is added to or deleted from the switch126or whenever a port changes its VLAN association. Accordingly, the STP application352registers with the event manager334so as to be notified of the occurrence of any ADD_DELETE_PORT and MOVE_PORT_TO_VLAN events. As the applications352,353and354define event types and/or register as listeners for existing event types, the event manager334may establish an event queue (not shown) for each application352,353and354and may assign each queue a unique identifier, i.e., an event queue identifier (EQID), as indicated at block422. Alternatively, the EQIDs may be statically defined.

In order to register as a listener for an event type, applications352,353and354preferably use the system or task calls defined by an Application Programming Interface (API) layer that is implemented by the event manager334on the active supervisor302. The available API system calls may include the following:eventRegister( ) andeventDeregister( ),
which are used to register for and deregister from events, andnewEvent( ) andeventComplete( ),
which are used to initiate and finish events, as described below.

The arguments of the eventRegister( ) API call include the event type and the listening application's EQID. As each event type is defined and applications register as listeners of the various event types, the event manager334at the active supervisor202builds and fills in an event registration table at its event database338, as indicated at block424(FIG. 4B).

FIG. 5is a highly schematic representation of a preferred event registration table500. Event registration table500is preferably logically arranged as an array having a plurality of columns and rows whose intersections define corresponding cells or records for storing data. The table500has a first column502whose cells or records contain the event types defined by the applications352,353and354running on the active supervisor202, as described above, which may be identified by the abbreviations, E1, E2, E3, etc. Table500further includes a second column504whose records or cells contain an identifier of the application(s) that may produce instances or occurrences of the corresponding event types of column502. A third column506identifies the application(s) that have registered as listeners to the event types of column502. Third column506may consist of a plurality of sub-columns506a–f, one or each application. When a particular application registers to listen to a specified event type by issuing an eventRegister( ) API, the event manager334responds by designating the corresponding sub-column506a–ffor that event type. For example, the event manager334may assert or deassert, e.g., place an “X” in, the respective cell or record. Application “A0”, for example, has registered to listen to event types “E4” and “E7”, application “A1” has registered to listen to event types “E2”, “E3”, “E7” and “E8”, and so on. Applications may alternatively be identified within columns504and506by their EQIDs. In addition to the event registration table500, the event manager334also creates a pending events table, as indicated at block426. The pending events table is described in more detail below.

Each application that defines an event type or registers to listen for a particular event type must also define or provide to the high availability entity302a function, which may be termed an “event_recovery_func( )”, that may be called should the active supervisor202fail before an instance of that event type is completed by the respective producer or listener application. Possible event_recovery_func( )s include “reset” or “redo” operations, but preferably not “undo” operations. In the illustrative embodiment, the event_recovery_func( )s and EQID for each application are statically defined at each supervisor202and204.

If an application wishes to stop receiving instances of a specific event type, it preferably issues the eventDeregister( ) API call to the event manager334. The arguments of this API call include event type and listener's EQID. In response, the event manager334clears the corresponding cell or record of the respective sub-column506a–fassociated with the deregistering application from the event registration table500for that event type.

The active supervisor202may also notify the standby supervisor304of eventRegister( ) and eventDeregister( ) APIs, as indicated at block426(FIG. 4B). More specifically, in response to receiving an eventRegister( ) API, the event manager334on the active supervisor202generates a REGISTER_NOTIFY message that contains the event type for which registration is being requested, an identifier of the application registering for the event type and the application's EQID. The REGISTER_NOTIFY message is then passed by the event manager334to the synch manager330which places it in the SYNC_Q350. Similarly, in response to an eventDeregister( ) API, the event manager334creates a DEREGISTER_NOTIFY message, which is placed in the SYNC_Q350. As messages reach or near the head of the SYNC_Q350, they are preferably encapsulated within a packet or frame and transmitted to the standby supervisor204via communication engine306and bus220.

FIG. 6is a highly schematic block diagram illustrating the format of a preferred packet or frame600traversing bus220. Bus220preferably operates in accordance with the well-known Ethernet data communication standard. Accordingly, frame600includes an Ethernet header portion602having Destination Address (DA) and Destination Service Access Point (DSAP) fields (not shown), among others. Frame600further includes a header604corresponding to another data communication layer, such as a Serial Communication Protocol (SCP), that defines and includes one or more operation code (opcode) fields for specifying the type or class of information that is being carried in the frame600. The SCP header604may also define and include one or more command fields for specifying specific actions that are to be carried out on the contents of the frame600. Following the SCP header604is a data portion606. Data portion606may include one or more messages608a–d, such as a REGISTER_NOTIFY and/or a DEREGISTER_NOTIFY messages, among others, from the SYNC_Q350. The order of messages608a–dwithin data the portion606of a given SCP frame600preferably corresponds to the order of the messages608a–din the SYNC_Q350. That is, the message, e.g., message608a, at the head of the SYNC_Q350is the first message in the data portion606and so on. The number of messages608a–dthat can be loaded into data portion606depends on their size as constrained by the maximum size of Ethernet frames.

SCP frame600is received at the synch manager332of the standby supervisor204and may be placed at least temporarily in its SYNC_Q351. The high availability entity304at the standby supervisor204uses the contents of REGISTER_NOTIFY and/or DEREGISTER_NOTIFY messages from received SCP frames600to update its event database with the applications registered for particular events. Should the standby supervisor204become the active supervisor, as described below, it will use this information to monitor and track events.

After registering for event types of interest, defining corresponding event_recovery_func( )s, and configuring their logical synchronization databases356,358and360, the applications352,353and354at the active supervisor204begin performing their respective functions, as indicated at block428. As part of their operation, applications352,353and354may modify or change one or more of the state variables or other conditional information maintained by them. As indicated above, such changes are considered to be protocol events which are acted upon by the high availability entities302and304at supervisors202and204.

Processing of Protocol Events

FIG. 7is a flow diagram of the preferred steps of the present invention in response to a change in the operating state or condition of an application running on the active supervisor202, i.e., a protocol event. Suppose, for example, that the STP application352running at the active supervisor202detects some change in its operating state such as a port changing spanning tree state, as indicated at block702(FIG. 7A). As part of its response to this change, application352is programmed or otherwise configured to issue a newEvent( ) API call to the event manager334, as indicated at block704. The arguments of the newEvent( ) API include the event type, the producer's EQID, the event data, if any, and the size of the data. In response to the newEvent( ) API call, the event manager334creates an instance of the event type specified in the API call, which may be referred to herein as an event instance or simply an event, as indicated at block706. The event manager334also assigns an identifier, e.g., an eventID, to the event instance. If a sequence number has been requested for events of this event type, the event manager334also assigns a unique sequence number to the event, as indicated at block708.

To generate a sequence number, the event manager334preferably accesses the sequence database342and retrieves the next available sequence number. The sequence database342may be implemented as counter that can be operated, e.g., incremented or decremented, by the event manager334in order to obtain a new sequence number. The event manager334then performs a look-up of event registration table500to determine which other applications, if any, have registered as listeners for events of this type, as indicated at block710. Suppose, for example, that the event type is E1and that it was produced by application A1, e.g., the STP application352. In this case, the event manager334determines that application A2, e.g., the VTP application353, has registered for events of type E1. Accordingly, the event manager334also places a copy of the event instance, including the eventID, the sequence number, if any, and the data into the EQID for application A2, as also indicated at block710. The event manager334next returns a copy of the event instance, including the eventID, the sequence number, if any, and the specified data to the producing application, as indicated at block712.

It should be understood that the producing application could also have requested that a copy of the event be placed in its EQID. The producing application may also omit its EQID from the newEvent( ) API call.

Next, the event manager334creates an entry for the event in its pending events table that is preferably maintained in the event database338, as indicated at block714. As described herein, the pending events table is used to keep track of which event instances have yet to be completed by all of the interested applications.

FIG. 8is a highly schematic, block diagram of a pending events table800. In the illustrative embodiment, table800comprises a first table element802and a second table element804each of which is made up of a series of bit maps or bit strings. First table element802identifies those event instances that have been started and specifies the producing application and listening applications, if any, for each event instance. Second table element804identifies which applications have completed their processing of each pending event instance. As indicated above, first table element802is made up of a sequence of individual bit maps806–810each one corresponding to a different event instance. Each of the individual bit maps806–810includes an eventID cell812that specifies the identifier that has been assigned to the respective event instance, e.g., “E1.45”, “E1.23”, “E4.11”, etc. Each individual bit map806–810further includes a corresponding cell814a–gfor each application running on the active supervisor202, e.g., applications A0–An, that may use the high availability facilities or objects of the present invention. Second table element804is also made up of a sequence of individual bit maps816–820each one corresponding to a different event instance. Each of the individual bit maps816–820includes an eventID cell822and a corresponding cell824a–gfor each application.

When a new event instance is created, the event manager334preferably creates a corresponding bit map, e.g., bit maps810and820, within the first and second table elements802and804. In the eventID cell of these two bit maps810and820, the event manager334loads the eventID assigned to this event. The event manager334then sets, e.g., asserts, those application cells814a–gand824a–gfor the application(s) that will be processing the event and are thus expected to notify the event manager334when their processing of the event is complete. Specifically, the event manager334asserts, e.g., sets to “1”, the application cells, e.g., cells814a,814b,824aand824b, that correspond to the producing application and to the listening application(s), if any, and de-asserts, e.g., sets to “0”, all other application cells for the given event instance. The event manager334may refer to the information in its event registration table500in order to assert/de-assert the application cells814a–gand824a–gof the respective bit maps810and820.

As described below, as individual applications notify the event manager334that they have completed their processing of an event, the event manager de-asserts the application cell for that application from the respective bit map of the second table element804. Thus, by comparing, e.g., applying one or more Boolean operations to, the bit maps from the first and second table elements802and804that correspond to the same event instance (as indicated by the eventIDs), the event manager334can determine which applications have yet to complete their processing of the event instance.

Those skilled in the art will understand that other arrangements can be used to store the information of table800.

In addition to returning the event instance to the producing application, placing copies of the event into the EQIDs of the listening applications and updating its pending events table800, the event manager334notifies the standby supervisor of the occurrence of the event, as indicated at block716. In particular, the event manager334generates an EVENT_BEGIN message. The EVENT_BEGIN message contains the event type, the bit map generated for the first table element802for the event (which includes the event's eventID and designates the producing and listing applications, if any), the sequence number, if any, and the data specified by the producing application. The event manager334passes the EVENT_BEGIN message to the sync manager330, which, in turn, places it in the SYNC_Q350. When the EVENT_BEGIN message reaches (or nears) the head of the SYNC_Q350, it is encapsulated within an SCP frame600and transmitted to the standby supervisor204via communication engine306and bus220in a similar manner as described above. At the standby supervisor204, the EVENT_BEGIN message is received by the sync manager332. The event manager336at the standby supervisor204stores the sequence number, if any, from the EVENT_BEGIN message in its sequence database344, and copies the bit map into the first and second table elements802and804of its pending events table800, as indicated at block718.

Returning to the active supervisor202, upon receiving the event instance that was returned to it by the event manager334, the producing application, i.e., application352or A1, processes the event, as indicated at block720. That is, the application takes the appropriate, i.e.; programmed, action in response to the event. Suppose this action includes commanding a line card, e.g., line card206, to take some action, such as changing some state or condition associated with one or more of its ports, e.g., port P1. Suppose this action further includes modifying the contents of one or more of the application's sync records362so as to store this new state or condition. If so, the application352preferably generates an SCP command message for transmission to the line card206. The SCP command message preferably identifies the affected port and the new state or condition to which the port should be transitioned. The command message further includes the sequence number that was generated by the event manager334and returned to the application352with the copy of the event instance. The application352passes the SCP command message to communication engine306, which sends it to line card206via bus220. The SCP command message from the application352is preferably not placed in or routed through the SYNC_Q350.

The SCP command message is received by the line card's communication engine310, which provides it to the line card manager314. Manager314takes the corresponding action, e.g., changing the state or condition of port P1. The line card manager314also stores the sequence number from the command message at its sequence database322, as indicated at block722(FIG. 7B). The line card manager314may or may not return an acknowledgment message to the application352at the active supervisor202.

In accordance with the preferred embodiment of the present invention, the line card managers314and316only store at their respective sequence databases322and324the single, highest sequence number they have received. To the extent the line card manager314was storing a previous sequence number at the time it received the SCP command message containing the new sequence number, the previous, e.g., lower, sequence number is discarded and only the sequence number that was just received is saved by the line card manager314. If a received sequence number happens to be lower than the currently stored sequence number, the line card manager314carries out the action of the SCP message, but retains the higher sequence number. In other words, the line card manager314and316at each line card206and208only stores the highest sequence number that it has received.

Since it is modifying or changing, e.g., writing to, the contents of one or more of its sync records362, the application352also causes the standby supervisor204to be informed of the new value(s) for each modified synch record362, as indicated at block724. In particular, the application352creates a SYNC_RECORD_MESSAGE for transmission to the standby supervisor204.

FIG. 9is a highly schematic block diagram of a preferred SYNC_RECORD_MESSAGE900. Message900has a plurality of fields including an entity identifier (ID) field902, a record ID field904, a length (len) field906, a fragment field908and a data field910that contains the particular data, e.g., the sync record362, that is to be synchronized to the standby supervisor204. In the entity ID field902, the application352preferably loads a unique identifier that has been assigned to it. In the record ID field904, the application352preferably loads a value, such as memory address, that identifies which record of its synchronization database356has been modified. The application352may use the length field906to specify the length of data field910. Within data field910, the application352loads the new value for the sync record specified within field904. The application352may use a get function, which may be termed “record_sync_func( )”, in order to pack the data to be loaded into field910into a known format for the standby supervisor204.

Once it has created the SYNC_RECORD_MESSAGE, the application352preferably causes it to be sent to the standby supervisor204. In particular, the application352calls a transmit function, which may be referred to as the “ha_tx_sync( ) function”. The ha_tx_sync( ) function takes the SYNC_RECORD_MESSAGE900and places it in the SYNC_Q350at the active supervisor202. When the message900reaches or nears the head of the SYNC_Q350, it is encapsulated in an SCP frame600and transmitted to the standby supervisor204in a similar manner as described above.

The SCP frame600is received at standby's communication308and is passed to the high availability entity304, based on the message's Destination Address (DA) and/or Destination Service Access Point (DSAP). The sync manager332preferably recovers the SYNC_RECORD_MESSAGE900from the SCP message600. The sync manager332then uses the entity ID and the record ID from fields802and804of the sync record900to index a database and derive a put function, which may also be the record_sync_func( ) described above.

Specifically, the sync manager332may be statically configured with the particular record_sync_func( )s corresponding to each possible entity ID and record ID pair. On the standby204, execution of the record_sync_func( ), causes the data in the data portion810of the sync record900to be recovered. It also causes the recovered data to be stored at the specified sync record378at the logical synchronization database370for the application352, as indicated at block726. In particular, the record_sync_func( ) uses the values from the entity and record ID fields802and804to locate the correct synchronization database370and synchronization record378. The record_sync_func( ) then writes the unpacked data of field810to that record.

Upon completing all of its programmed action(s), e.g., issuing the SCP set command message to line card206, updating its own sync record362and transmitting the new sync record to the standby supervisor204, the application352preferably issues an eventComplete( ) API call to the event manager334, as indicated at block728. The arguments of the eventComplete( ) API call include the event's eventID and an identifier of the application issuing the eventComplete( ) API call, e.g., its EQID. In response to the eventComplete( ) API call, the event manager334modifies its pending events table800to reflect that application352has completed its processing of the subject event, as indicated at block730. In particular, the event manager334accesses the particular bit map, e.g., bit map820, from second table element804that corresponds to the event instance specified by the eventID of the eventComplete( ) API call. The event manager334then de-asserts the application cell, e.g., cell824b, that corresponds to the EQID from the eventComplete( ) API call so as reflect that the event manager334is no longer waiting for application A1to complete this event.

The event manager334also notifies the standby supervisor204that application352has completed its processing of this event, as indicated by block732. In particular, the event manager334creates an EVENT_COMPLETE message for use in notifying the standby supervisor204. The EVENT_COMPLETE message includes the bit map, i.e., bit map820, from second table element802that it has modified. The EVENT_COMPLETE message is provided to the sync manager330which places it in the SYNC_Q350for transmission to the standby supervisor204. The EVENT_COMPLETE message is received at the standby's communication engine308which passes the message to the high availability entity304. The event manager336then updates its pending events table800to reflect that application A1has completed its processing of the event, as indicated at block734. In particular, the event manager336uses the eventID to identify the corresponding bit map, i.e., bit map820, from the standby's second table element804and replaces that bit map with the modified bit map that was received in the EVENT_COMPLETE message from the active supervisor202, i.e., the bit map820having application cell824bde-asserted.

Other applications that received a copy of the event instance in their EQIDs similarly perform their programmed processing of the event. These applications may similarly update one or more of their sync records in response to the event and, if so, issue sync record messages to the standby supervisor204. These applications may also issue one or more events in response to the first event. As a result, events may become nested within each other. As each of these other applications complete their processing of the first event, they similarly issue an eventComplete( ) API call to the event manager334, which de-asserts the respective application cells from bit map820, as indicated at block736. The event manager334then sends an EVENT_COMPLETE message with a copy of the modified bit map820to the standby supervisor204, as indicated at block738, and the standby supervisor204clears the respective application from its pending events table, as indicated at block740(FIG. 7C).

When the producing application and all listening applications of a particular event have issued eventComplete( ) API calls, the event manager334preferably closes the corresponding event, as indicated at block742. In particular, the event manager334removes the bit map that was established for this event from both the first and second table elements802and804of its pending events table800. The event manager336at the standby supervisor204similarly closes events that have been processed by the producing and all listening applications, as indicated at block744.

Processing of System Events

FIG. 10is a flow diagram of the preferred steps of the present invention in response to a system generated event. Suppose, for example, that a link up condition is detected at port P3of line card208. That is, a new link is installed at port P3. In response to this system event, the line card manager316generates an unsolicited SCP message, which may generally have the format of frame600(with or without the Ethernet header), for transmission to the active supervisor202to notify it of this new condition, as indicated at block1002. The unsolicited SCP message is transmitted by communication engine310to the active supervisor202via bus220where it may be provided to the link/module up/down application. The link/module up/down application preferably issues an newEvent( ) API call to the event manager334for a LINK_UP event type, as indicated at block1004, that it previously defined in a similar manner as described above.

In response, the event manager334preferably creates an instance of this event and returns it along with a new sequence number, which it obtains from the sequence database342, to the link/module up/down application, as indicated at block1006. It also places the event in the EQIDs for any applications that registered as listeners to this event type, as also indicated by block1006. The event manager334also updates its pending events table800, as indicated at block1008, by creating a new bit map in each of the first and second table elements802and804. The event manager334also generates an EVENT_BEGIN message containing the sequence number and the new bit map, among other information, and sends this message to the standby supervisor204via the SYNC_Q350, as indicated at block1010. The standby supervisor204updates its pending events table, as also indicated at block1010.

The link/module up/down application preferably generates an SCP acknowledgement message to line card208containing the sequence number generated by the event manager334, as indicated at block1012. The acknowledgement is sent to the line card208via communication engine306and bus200. The acknowledgement preferably does not get placed in the SYNC_Q350. When the acknowledgment is received at line card208, the line card manager316updates its sequence database324with the new sequence number, as indicated at1014. The line card manager316preferably does not consider the link to be in an up condition until the acknowledgement from the link/module is up/down application on the supervisor202is received. To the extent a sync record of the link/module up/down application is modified, the application generates a SYNC_RECORD_MESSAGE with the new sync record and sends it to the standby supervisor204via the SYNC_Q350.

When the link/module up/down application completes its processing of the event, it issues an eventComplete( ) API call to the event manager334, as indicated at block1016. The event manager334modifies its pending events table800by updating the corresponding event finished bit map established for this event, generates an EVENT_COMPLETE message containing the new bit map and sends the EVENT_COMPLETE message to the standby supervisor204via the SYNC_Q350, as indicated at block1018. The event manager336at the standby supervisor204, in turn, updates its pending events table, as indicated at block1020.

To the extent other applications registered as listeners for this type of event, they process the event and issue eventComplete( ) API calls to the event manager334. The event manager334updates the corresponding bit map in its pending events table800accordingly and sends EVENT_COMPLETE messages to the standby supervisor204containing the update.

Processing of External Events

FIG. 11is a flow diagram of the preferred steps of the present invention in response to an externally generated (relative to switch126) event. Suppose, for example, that a network administrator working at a network management console issues a command line interface (CLI) command for updating some information at switch126, as indicated at block1102(FIG. 11A). Suppose further that application354, in response to the update, needs to direct one or more ports of line card206to change state. In response to the command, a CLI task or manager (not shown) operating on the active supervisor202first updates the corresponding information. The CLI task then issues an newEvent( ) API call to the event manager334, as indicated at block1104, for an event type that it previously defined. Since a change will be made at a line card, the event type includes a request for a sequence number. The event manager334, in turn, generates an instance of the corresponding event and updates its pending events table800by creating a pair of new bit maps, as indicated at block1106. The event manager334also obtains a new sequence number for the event.

The event manager334returns a copy of the event, including the new sequence number, to the CLI task and places a copy of the event in the EQID for application354, as indicated at block1108. The event manager334also issues an EVENT_BEGIN message that includes the new sequence number to the standby supervisor204, as indicated at block1110. The standby supervisor204adds the new bit map from the EVENT_BEGIN message to its pending events table800and stores the new sequence number, as indicated at block1112. The application354meanwhile, if required as part of its processing of the event, issues a SCP set command, which includes the sequence number, to line card206directing it to take the corresponding action, as indicated at block1114. Line card206executes the corresponding action and stores the new sequence number at its sequence database322, as indicated at block1116. The application354may then modify one or more of its sync records366to reflect the new condition, as indicated at block1118. The new sync record is then transmitted to the standby supervisor204in a similar manner as described above, as indicated at block1120.

Upon completing their processing of the event, the CLI task and application354each issue an eventComplete( ) call to the event manager334, as indicated at block1122(FIG. 11B). The event manager334clears the CLI task and application354from its pending events table800, as indicated at block1124, and sends EVENT_COMPLETE messages to the standby supervisor204, as indicated at block1126. The standby supervisor clears the CLI task and application354from its pending events table, as indicated at block1128. The active and the standby supervisors202and204then close the event, as indicated at block1130.

As shown, the synchronization of information from the active to the standby supervisors202and204in response to protocol, system and external events preferably takes place asynchronously so as to minimize their effects on the run-time performance of the switch126. Furthermore, the existence of a single SYNC_Q350at the active supervisor202ensures consistent ordering between the active and the standby supervisors202and204. That is, the order in which changes take place on the active supervisor202is the same as the order in which those changes take place on the standby supervisor204.

Switchover from Active to Standby Supervisors

If a failure occurs at the active supervisor202, the standby supervisor204preferably continues the switching and other operations of the switch126with little or no disruption to the bridged computer network200.FIG. 12is a flow diagram of the preferred steps taken by switch126during a switchover of supervisor cards. First, the active supervisor202crashes or fails, and that crash or failure is detected by the standby supervisor(s), e.g., supervisor202, as indicated at block1202. It should be understood that the supervisors202and204may each include failure detection modules or circuits for this purpose. If there are multiple standby supervisors, one of them is elected to be the newly active supervisor, as indicated at block1204.

The standby supervisor(s)204, in addition to processing events, as described above, also keeps track of which line cards or modules of switch126are running, i.e., which line cards are on-line. Following the crash or failure of the active supervisor202, the high availability manager328at the standby204notifies each line card206and208that it is the newly active supervisor and that the line cards206and208should, from this point forward, send messages to supervisor204, as indicated at block1206. The newly active supervisor204also conducts a “consistency check” on each line card206and208. In particular, supervisor204queries each line card206and208for their sequence numbers, as indicated at block1208. To perform these tasks, the newly active supervisor204may send a SWITCH_SEQ SCP command message to each of the line cards206and208, which contains the address of supervisor card204. Each line card206and208responds by sending its current sequence number to the newly active supervisor card204.

The high availability manager328then compares the retrieved sequence numbers to the sequence number stored at its sequence database344. More specifically, the high availability manager328determines whether any of the sequence numbers from the line cards206and208is greater than its sequence number, as indicated at decision block1210. Suppose, for example, that the last sequence number provided to the standby supervisor204before the active supervisor202crashed was sequence number “21”. If the sequence number stored at each of the line cards206and208is less than or equal to this sequence number (i.e., “21”), then the high availability manager328“knows” that all of the state or condition information stored at each line card206and208is consistent with the state or condition information stored in the sync records378,380,382and384of the synchronization databases370,372,374and376at the newly active supervisor204.

If, however, a line card, such as line card208, returns a sequence number (e.g., “22”) that is greater than the sequence number at sequence database344of the newly active supervisor204, then the high availability manager328concludes that at least one change was implemented by line card206, but was never received by the newly active supervisor204. Since the newly active supervisor204cannot “recover” this change, it preferably responds by directing the respective line card (i.e., line card208) to reset all of its state or condition information, as indicated by Yes arrow1212leading to block1214.

Following the line card “consistency check” and the resetting of those line cards, if any, that failed the consistency check, the high availability manager328at the newly active supervisor204next proceeds to determine whether any events are still “open”, as indicated at block1218. In particular, the high availability manager328examines the pending events table800at its event database340. As described above, when producing and listening applications complete their processing of event instances, they issue eventComplete( ) API calls, which result in those applications being cleared from the pending events table800for the respective event at both supervisor cards202and204.

After a crash or failure of the active supervisor, an event may be open at the newly active supervisor204for several reasons. For example, the application at the previously active supervisor202may not have completed its processing of the subject event prior to the supervisor202crashing or failing. Alternatively, the application may have completed its processing of the subject event but not yet issued an eventComplete( ) API call or, if the eventComplete( ) call was issued, the previously active supervisor202may not yet have issued a corresponding EVENT_COMPLETE message to the then standby204. In either case, the newly active supervisor204considers the subject event to be an open event. By applying one or more Boolean operations to the two bit maps created for each event, the high availability manager328can quickly determine which applications, if any, did not complete their processing of each event. If there are one or more applications which have yet to be cleared for any event, as reflected in the pending events table800at the newly active supervisor204, then the high availability manager328preferably takes some recovery action.

More specifically, as described above, for each event type that an application defines or registers as a listener, the application also defines an event_recovery_func( ). For each open event that was identified at step1216, the high availability manager328executes or calls for execution by the application the event_recovery_func( ) specified by the application that had yet to complete the event prior to the crash or failure of the previously active supervisor202, as indicated at block1218. The event_recovery_func( ) preferably restores the logical synchronization database for the respective application to a consistent state. For the Spanning Tree Protocol (STP), for example, the event_recovery_func( ) may be a redo operation. Specifically, if the STP application has not completed a PORT_CHANGE_STATE event at the time the active supervisor202crashes or fails, the new spanning tree port state from the open event is saved at the standby supervisor204, and an SCP set command is sent to the line card for the respective port in order to set the port's state to the new spanning tree port state. Even if the active supervisor202had sent such an SCP set command before crashing or failing, re-sending it is harmless. For DTP and PAgP, the event_recovery_func( )s may be reset operations. Thus, if a DTP or PAgP NEGOTIATION event is open following a crash or failure of the active supervisor202, the respective port(s) or line card(s) are preferably reset.

The newly active supervisor204, as part of its recovery functions following the crash or failure of the active supervisor206, may also build one or more switchover databases. The switchover database may indicate which line cards, if any, failed the consistency check and thus must be re-stared. It may also list all of the open events and specify the corresponding event_recovery_func( )s that must be executed.

Upon completing the consistency check and responding to any open events, the newly active supervisor204starts or wakes up the applications loaded onto supervisor204, as indicated at block1220(FIG. 12B). Rather than starting from an initialization state, however, these applications start running based on the contents of their corresponding synchronization databases at the newly active supervisor204, as indicated at block1222. That is, the applications begin running based on the state or other condition information that was synchronized to the newly active supervisor204before it became the active supervisor and determined to be valid. Accordingly, the applications do not waste time starting over from initialization states. Switch126can thus resume forwarding messages with little disruption despite the crash or failure of the previously active supervisor202.

As part of the switchover process, the high availability manager328at the newly active supervisor204preferably creates a table or other data structure that has a record or cell for each port230at switch126. As each application performs its recovery functions, e.g., the event_recovery_func( ), it may determine that one or more ports230should be brought down and reinitialized. If so, the application preferably identifies or marks that port in the data structure created by the high availability manager328, unless that port has already been marked by some other application. When the applications have all completed their recovery functions, the high availability manager328checks this table or data structure and brings down and reinitializes all of the designated ports. For example, one application, e.g., DTP, may conclude that no action need be taken in response to the active supervisor crashing or failing, while a second application, e.g., PAgP, may determine that a port or an entire line card must be restarted. The applications, e.g., DTP, may also check this data structure so as to learn whether any ports or line cards are to be restarted.

Hot-Swapping of Supervisor Cards/Global Synchronization

The present invention is also able to support the hot swapping of supervisor cards. The term hot swapping refers to the replacement of components, in this case supervisor cards, without having to shut-down and restart the affected equipment, in this case the switch. Suppose, for example, after failing, that supervisor card202is removed, and later on a new supervisor card, which will also be referred to by designation number202for simplicity, is installed into switch126. Each application that utilizes the high availability facilities of the present invention, in addition to defining an event_recovery_func( ) among others, also defines a global_sync_func( ) which is used to synchronize all of the application's sync records to the standby supervisor. Furthermore, the high availability managers also maintain a global_sync_done flag for each sync record. Initially, the global_sync_done flag for every sync record is deasserted or set to false.

When the high availability manager328at the currently active supervisor204determines that a new supervisor202has been inserted, e.g., “hot” inserted, it begins calling the global_sync_func( ) defined by each application so as to synchronize the synch records for each application to the current standby supervisor202. Execution of the global_sync_func( ) for a given application may result in the application calling a series of ha_tx_sync( ) functions. Each of the ha_tx_sync( ) functions may take a particular sync record, generate a corresponding SYNC_RECORD_MESSAGE900containing that sync record and place the SYNC_RECORD_MESSAGE900in the SYNC_Q351.

From the SYNC_Q351the SYNC_RECORD_MESSAGE900is sent to the current standby supervisor202where it is unpacked. That is, the SYNC_RECORD_MESSAGE causes the corresponding sync record at the current standby supervisor202to be updated. After the application has synchronized a given sync record to the current standby supervisor202, it may call a get function and a set function in order to assert or set to true the global_sync_done flag for the given sync record. This process is repeated by each application at the current active supervisor204. Once a given sync record has been synchronized to the standby supervisor202and the corresponding flag has been set to true, the application can, in response to one or more protocol events, call the ha_tx_sync( ) function in order to update that record. Until the global_sync_done flag is set to true for a given sync record, the application is preferably precluded from issuing any ha_tx_sync( ) functions (other than in connection with a global sync operation) for that sync record.

It should be understood that multiple sync records may be merged or grouped into a composite record. All of the sync records of this composite record may then be synchronized to the current standby supervisor204by calling a single instance of the ha_tx_sync( ) function on the composite record.

It should be further understood that the high availability entities302and304and/or the sequence databases342and344preferably implement some type of wrap-around function or process when the sequence number wraps around from its highest value to its lowest value. Suitable wrap-around solutions for use with the present invention are well-known to those skilled in the art.

Although the invention has been described in connection with applications operating at layers 2 and 3 of the Open Systems Interconnection (OSI) Reference Model, it should be understood that it may be used with applications, protocols or processes operating at other layers. In addition, the high availability facilities of the present invention could be used by two separate intermediate network devices or entities in order to share or synchronize information between them.

The foregoing description has been directed to specific embodiments of this invention. It will be apparent, however, that other variations and modifications may be made to the described embodiments, with the attainment of some or all of their advantages. For example, other communication architectures or paradigms, besides event-based architectures, such as primitives, commit protocols, etc., may be employed by the active and standby supervisor cards to exchange information relating to the spanning tree protocol. Therefore, it is an object of the appended claims to cover all such variations and modifications as come within the true spirit and scope of the invention.