Method and apparatus for fast failure detection in switched LAN networks

A switch detects port failures and identifies a MAC address associated with the port failure. The switch then sends a failure notification message to other ports on the switch that identifies the MAC address associated with the port failure. The network processing devices on the other ports use the failure notification message to quickly determine if routes need to be reconfigured around an adjacency on the switch.

BACKGROUND

Routers maintain topological information about a network in order to determine the correct paths for routing packets. The routers derive this topological information by continuously communicating with other routers or other network processing devices in the network (peers). An adaptive routing algorithm is used by the routers to identify communication failures and adaptively compute new routes around the failure. An adjacency is formed whenever a router communicates with a peer and is defined as a relationship with a neighboring network processing device. The router continuously determines which adjacencies are up and which are down. The longer is takes for the router to detect that an adjacency has gone down and route around it, the greater the chance a significant number of packets will get sent over the wrong routes, or sent to a down router and hence be lost.

There are two primary reasons why packets may not be successfully sent to an adjacency. The interface or link to the adjacency may have failed or the adjacency itself may have failed. Some links, such as digital TDM (Time Division Multiplexed) channels, SONET, and direct point-to-point Ethernet connections provide fast failure detection using hardware indications such as loss-of-light, missed heartbeat, etc. Failures can also be detected using a low-level link protocol mechanism such as OAM (Operation, Administration, and Maintenance) headers in Sonet (Synchronous Optical Network). In these detection schemes, there are direct links between the two network processing devices. This allows layer 1 physical interfaces to quickly identify failures which are then identified to the layer 3 routing algorithms which route around the identified failure.

In some common network configurations, routers are not connected directly together but are connected through a layer 2 switch. For example, a switched LAN (Local Area Network) may use a Gigabit Ethernet switch that includes different ports connected to PCs and to layer 3 routers. The routers connected to different switch ports can not immediately identify failures either of other routers or of the ports and links by which they are connected to the switch. The routers currently have to rely on slow timeout mechanisms, such as missed hello packets, to detect failures on other links connected to the switch.

For example, an IGP (Interior Gateway Protocol) uses “hello” message exchanges to discover and maintain link connectivity. If one of the routers fails to receive a “hello” acknowledge message after some period of time, the router failing to acknowledge the “hello” message is assumed to have gone down. The router sending the hello message then routes around the failed link.

A substantial amount of time is required to send and wait for replies to “hello” messages. For example, in one implementation hello messages are sent once every second. A failure is assumed only after three hello message go unacknowledged. Thus, upwards of three seconds are required to detect an adjacent link or adjacent router failure. The time required to detect failures can and often does dominate the time required for a routing algorithm to determine a new network topology around a detected failure (convergence time).

The hello message failure detection process takes much longer than layer 1 protocols used for detecting failures, but because the routers in switched networks are not connected directly together, the layer 1 failure protcols cannot be used.

The present invention addresses this and other problems associated with the prior art.

SUMMARY OF THE INVENTION

A switch detects port failures and identifies a MAC address associated with the port failure. The switch then sends a failure notification message to other ports on the switch that identifies the MAC address associated with the port failure. The network processing devices on the other ports use the failure notification message to quickly determine if routes need to be reconfigured around an adjacency on the switch.

DETAILED DESCRIPTION

FIG. 1shows a Fast Failure Detection (FFD) scheme that significantly improves the convergence time and responsiveness of IP routing algorithms. A network12includes a switch14coupled to multiple routers #1–#4. The switch14in one embodiment is an Ethernet layer 2 switch and the routers #1–#4 are layer 3 routers. However, the invention is applicable to any network architecture where network processing devices operating at layer 3 of the OSI (Open Systems Interconnection) reference model are coupled together through another network processing device operating at layer 2 of the OSI model. Each router #1–#4 is coupled to an associated port #1–#4, respectively, on the switch14.

Each port on switch14learns the MAC addresses of all network elements attached to that switch port, using conventional techniques such as the IEEE 802.1D transparent bridging method. Usually there is only one MAC address accessible through a switch port, but if downstream layer-1 repeaters are used, or the switch is connected to other switches in a spanning tree, there could be than one.

In the example shown inFIG. 1, the ports #1–#4 in switch14have currently associated with them routers #1–#4. These routers in turn each have a network adapter15with a corresponding MAC address MAC R1-MAC R4. The routers #1–#4 communicate through the switch14by including their own MAC address as the source address, and the MAC address of the adjacent router in the destination address, of transmitted layer 2 frames.

Referring toFIGS. 1 and 2, the switch14in block20monitors ports #1–#4 for any failures. The switch14uses existing hardware or software mechanisms to determine when a device attached to a port, or the port itself, is no longer operational. For example, loss-of-light detection can be used for optical links and heartbeats signals can be used for copper connections.

If a failure is detected in block22, the switch identifies the MAC address(es) associated with the failed port or failed router in block24. It is not sufficient to simply indicate a port has gone down. The active routers need to know the exact MAC address that is unreachable, so the right adjacency can be identified and routed around.

In the example shown inFIG. 1, a failure18occurs either in router #2 or on port #2. The switch14in block26(FIG. 2) informs the still-active switch ports #1, #3 and #4 of the failure by sending a failure notification message16(FIG. 1). The failure notification message16includes the MAC address MAC R2 of the router associated with port #2 on switch14.

FIGS. 1 and 3show the operations taken by the active routers after receiving the failure notification message16. The active router or routers in block28each receive the failure notification message16from the switch14over their active switch ports. Each active router in block30searches through the adjacency table for the LAN interface over which the failure message arrived to determine if any adjacencies on that interface match the MAC address reported in the failure notification message16.

If any adjacencies are identified that are currently “up” in block32, they are immediately declared down and a route recomputation is initiated in block34. For example, the routers on ports #1, #3 and #4 each receive the MAC address MAC R2 in block28associated with failed port #2. Each router #1, #3 and #4 compares the received MAC address MAC R2 with adjacencies in their individual per-interface adjacency tables. If the MAC address MAC R2 matches one of the adjacencies, that router routes around the MAC R2 address. If the MAC address MAC R2 does not match any adjacencies in block32, the router does not reconfigure routes.

The FFD scheme described above is particularly useful in switched LANs (Local Area Networks) where router arrays in service provider POPs (Point Of Presence) and in large enterprise offices are often constructed out of routers attached to switches as opposed to connected directly in a mesh, or via a shared Ethernet channel.

Network Processing Devices Coupled to Multiple Switch Ports

Referring toFIG. 4, a router may be attached to the switch14through multiple ports. For example, a router #1 is connected to the switch14though both port #1 and port #3. Port #1 has an associated MAC address MAC R1A and port #3 has an associated MAC address MAC RIB.

When a failure36occurs on port #1, router #2 does not necessarily have to reroute around router #1. Router #2 can still route packets to router #1 through port #3. Similarly, when a failure40occurs on port #3, router #2 may still be able to route packets to router #1 over port #1. However, when failures36and40occur on ports #1 and #3 at the same time, or a failure38occurs on router #1, then router #2 has to reroute packets around router #1. Accordingly, router #2 only needs to reroute around router #1 when failure notifications37and39are received for MAC addresses MAC R1A and MAC R1B associated with both port #1 and port #3.

FIG. 5describes how router #2 processes failure notifications from switch14for multiple MAC adjacencies for the same router. In block42the router #2 receives a failure notification message. The router #2 in block44checks the MAC address in the failure notification with MAC adjacencies. If the MAC address in the failure notification does not match any adjacencies for that LAN interface, then the router #2 in block46does not reconfigure routes around router #1. If the MAC address matches an adjacency, then the router #2 in block50determines if there are multiple active MAC addresses associated with the same adjacency. If there is only one active MAC address associated with the same adjacency, the router #2 reconfigures routes around the down adjacency in block54.

If there are multiple active MAC addresses for the same adjacency, then the router #2 in block52uses one of the other identified active MAC addresses to route packets to router #1. If all of the MAC addresses for the adjacency are down, then the router #2 reconfigures the routes around router #1 in block54.

Referring back toFIG. 4, some of the devices connected to the ports of switch14may not be routing devices. For example, ports #4–#6 are connected to PCs (Personal Computers)41. The switch14may be configured to not send failure notification messages37or39to PCs41since these devices are not used for routing packets over a packet switched network.

FIG. 6shows in further detail the functional elements in the switch14needed to perform FFD. A CPU (Central Processing Unit)60communicates with multiple ports66in the switch14. A heartbeat, or other failure detection signal67, is constantly sent between the ports66and the connected network processing devices. Whenever, the signal67indicates a failure, the port66associated with the signal notifies CPU60.

The switch14includes a table62that identifies the one or more MAC addresses associated with each port66. The switch14may optionally include a port configuration table64that identifies which ports need to be notified when a port failure is detected. For example, port #3 is coupled to a PC68and therefore may not need to be notified of port failures. The table64is therefore configurable to disable failure notifications to port #3. The CPU60will then send out failure notification messages16only to the ports66that are enabled in table64.

FIG. 7shows in further detail the functional elements in one of the routers #2 or other network processing devices that process a failure notification message16from the switch14. The failure notification message16is received over one of the ports72in the router #2 and sent to the CPU70. The CPU70refers to an adjacency table74to determine if the MAC address in failure notification message16affects any of the router adjacencies.

The CPU70looks at all adjacencies that are reachable over the port that received the failure notification message16. For example, if there were three routers #1–#3 connected to the switch14, there could be two MAC address adjacencies MAC R1 and MAC R3 in the adjacency table74in router #2 for port #1. If the failure notification message16includes a MAC address matching an adjacency, the router #2 declares the adjacency down and the CPU70routes around the down adjacency.

Failure Notification Messages

Any number of different protocols can be used by the switch to notify routers that a MAC address is no longer reachable via a switch port. In one example, a proprietary protocol such as CDP (Cisco Discovery Protocol) is enhanced to generate the failure notification message16(FIG. 1).

In another implementation, an existing Internet ARP (Address Resolution Protocol) is used by the switch14to notify routers of port failures. Referring toFIG. 8, the switch14reports the failure of a particular MAC address by issuing a “gratuitous ARP reply”76. The ARP reply76includes the MAC address associated with the down port, and a holding time of zero. If the switch provides layer3functionality, then the ARP reply76may also include the IP (Internet Protocol) address for the router associated with the failed MAC address along with a null MAC address.

Router #1 receives the ARP reply76. As a security measure router #1 may check the source MAC address of the ARP reply76to ensure it came from the switch14. The zero hold time in the ARP reply76causes the router to immediately disassociate the MAC address in the ARP reply76with the associated IP address in the router #1 ARP entry78.

In one implementation, the router #1 will immediately route around the MAC address if it is identified as an adjacency. In another implementation, the disassociated ARP entry78causes the router #1 to immediately broadcast an ARP request80. The ARP request80includes the IP address associated with the nulled ARP MAC entry. When no ARP reply is received in response to the ARP request80, any adjacency currently deemed “up” for the ARP entry78that no longer exists, is declared down, and route computation is initiated.

A switch implementing VLANs (Virtual Local Area Networks) can perform a separate instance of the failure detection scheme for each VLAN to prevent falsely reporting failures across VLAN boundaries.

The system described above can use dedicated processor systems, micro controllers, programmable logic devices, or microprocessors that perform some or all of the operations. Some of the operations described above may be implemented in software and other operations may be implemented in hardware.

Having described and illustrated the principles of the invention in a preferred embodiment thereof, it should be apparent that the invention may be modified in arrangement and detail without departing from such principles. I claim all modifications and variation coming within the spirit and scope of the following claims.