Methods and systems for providing redundant connectivity across a network using a tunneling protocol

[0001] The present invention relates to methods and systems for providing redundant connectivity across a network. More particularly, the present invention relates to methods and systems for providing redundant connectivity across a network using a tunneling protocol.

[0002] In the computer networking field, a tunnel generally refers to a logical connection in which lower layer protocol data units or packets are transported across a network in higher layer packets. The packets being transported through the tunnel are not used in making routing decisions across the network. Only the encapsulating packet of the tunneling protocol is used to make routing decisions. As a result, the packets being tunneled are transmitted transparently across the underlying network. Such transparent communication enables logical networks to be set up across diverse geographic areas.

[0003] One example of a protocol that can be used to establish a tunnel across an IP network is multi-protocol label switching or MPLS. MPLS is a protocol defined by the Internet Engineering Task Force to transport packets across a network using label switching. A label is a fixed-length identifier included in a shim header that may be located between layer 2 and 3 headers in a packet. MPLS routers, referred to as label switching routers or LSRs, make routing decisions based on the labels, rather than network layer addresses. Labels are assigned to packets by label edge routers when packets enter the MPLS network. Once a label is assigned to a packet, routing in the MPLS network is based only on the MPLS label. Each LSR receives a packet, makes a forwarding decision based on the label, and replaces the label in the outgoing packet with a new label. The path that a packet follows through the MPLS network is referred to as a label switched path or LSP. Label switched paths may be set up in advance by MPLS routers using a protocol referred to as the label distribution protocol or LDP.

[0004] Label switched paths may be used to set up tunnels that interconnect geographically diverse networks. One type of logical network that may be interconnected using tunnels is a virtual local area network or VLAN. FIG. 1 illustrates the VLAN concept. In FIG. 1, local area networks 100 and 102 may be physical local area networks, such as Ethernets. A switch 104 interconnects local area networks 100 and 102. PCs 106 and 108 are located on different physical local area networks. However, PC 106 and PC 108 may be on the same logical network or VLAN using a VLAN identifier located in the layer 2 information in a packet header. Thus, box 110 represents a virtual local area network that spans two physical local area networks.

[0005] Virtual local area networks allow logical networks to be established within an organization for groups of individuals whose terminals are not on the same physical network. For example, the marketing department in a company may span several floors or buildings, each with its own physical network. In order to facilitate seamless communications between these individuals without requiring a restructuring of the organization's physical network, a VLAN may be established by assigning a VLAN identifier to the marketing department. The switches between the physical networks include VLAN forwarding tables used to forward packets to the proper physical LAN. Thus, VLANs facilitate seamless communication between different physical networks at the local level.

[0006] In large organizations, groups within the organization may be located in geographically diverse sites. Accordingly, it may be desirable to seamlessly interconnect logical networks or VLANs in the geographically diverse sites using tunnels. Once a tunnel has been established, two or more geographically diverse networks can communicate transparently and securely with each other over the tunnel.

[0007] FIG. 2 illustrates conventional VLAN interconnection using tunnels. In FIG. 2, the first VLAN 200 communicates with a geographically diverse VLAN 202 via MPLS network 204. VLAN 200 has a single logical connection 206 with its local label edge router 208. Connection 206 may be a VLAN connection. Similarly, VLAN 202 has a single logical connection with its local label edge router 212. Connection 210 may also be a VLAN connection.

[0008] In order to communicate VLAN traffic over MPLS network 204, label edge routers 208 and 212 may establish unidirectional label switched paths 214 and 216 across MPLS network 204 and a bi-directional tunnel 218 over LSPs 214 and 216. One specific example of a tunneling protocol suitable for use as bi-directional tunnel 218 is described in IETF Internet Drafts Draft-Martini-12-circuit-encap-MPLS-04.text, “Encapsulation Methods for Transport of Layer 2 Frames Over IP and MPLS Networks,” November 2001, and Draft-Martini-12-circuit-trans-MPLS-08.text, “Transport of Layer 2 Frames Over MPLS,” November 2001, the disclosures of each of which are incorporated herein by reference in their entirety. Bi-directional tunnels used to carry layer 2 traffic over MPLS networks are referred to as transparent LAN services (TLS) or virtual circuit (VC) tunnels.

[0009] While the above-referenced IETF Internet Draft documents describe tunneling protocols for sending layer 2 frames over an MPLS network, neither specifies a method by which redundant connectivity can be provided across the MPLS network. If a tunnel between label edge routers fails, e.g., due to a network connectivity or system failure, the standards to not provide any mechanism for detecting this failure or establishing a backup tunnel. Accordingly, there exists a long-felt need for methods and systems for providing redundant connectivity across a network using a tunneling protocol.

[0010] In light of the above-described shortcomings of tunneling protocols, the present invention includes a method for detecting tunnel failure and establishing a backup tunnel using redundant label edge routers to provide redundant connectivity across a network, such as an MPLS network. According to one aspect, the present invention provides redundant connectivity across a network using a tunneling protocol. As used herein, the term “tunneling protocol” refers to any protocol that may be used to carry packets across a network using tunnels. Examples of tunneling protocols suitable for use with the present invention include MPLS, VC or TLS over MPLS, generic route encapsulation (GRE), and IP-sec.

[0011] A method for providing redundant connectivity across a network using a tunneling protocol includes configuring pairs of switches at each endpoint of a wide area network to provide redundant connections between the wide area network and a local area network located at each endpoint. One switch in each pair is initially configured to be in a master state, and the other switch in each pair is configured to be in a slave state. The master switch in each pair advertises a movable IP address to switches in the wide area network to establish LSPs and a bi-directional VC tunnel over the LSPs between the master switches. The slave switches do not advertise the movable IP address. However, the slave switches monitor the label advertisements by the master switch in the other pair and each slave switch establishes an outgoing LSP to the master switch in the other pair.

[0012] The master and slave switches at each endpoint exchange relative connectivity information using a standby routing protocol. In response to detecting that the connectivity between the master switch in one pair falls below that of the slave switch in the same pair, the master switch withdraws the IP address and any labels associated with the IP address. The slave switch transitions to master state and begins to advertise a route to the IP address and a label for the IP address. An incoming LSP and a bi-directional VC tunnel are then established between the master switch at the other endpoint and the new master switch that advertised the IP address. Traffic from the local area network can then proceed over the tunnel between the newly established master switch and the master switch at the other endpoint.

[0013] The present invention is particularly well-suited to provide redundant connectivity between remote VLANs. As such, switches according to the present invention preferably include VLAN capabilities.

[0014] Because the present invention monitors relative connectivity between switches and moves the IP address of a tunnel endpoint between switches based on the relative connectivity, the likelihood of a traffic or service interruption between geographically diverse local area networks is reduced.

[0015] Accordingly, it is an object of the invention to provide methods and systems for providing redundant connectivity over a network using a tunneling protocol.

[0016] Some of the objects of the invention having been stated hereinabove, other objects will become evident as the description proceeds when taken in connection with the accompanying drawings as best described hereinbelow.

[0025] FIG. 3 illustrates a system for providing redundant connectivity across a network using a tunneling protocol according to an embodiment of the present invention. In FIG. 3, switches are provided at each local network endpoint and redundant logical connections are provided between local network equipment and the switches. For example, in FIG. 3, switches 300 and 302 include redundant VLAN connections 304 and 306 to end user equipment 308. Similarly, switches 310 and 312 include redundant VLAN connections 314 and 316 to end user equipment 318. Switches 300, 302, 310, and 312 may each include Ethernet, MPLS, VLAN, and IP routing capabilities. With regard to MPLS functionality, because switches 300, 302, 310, and 312 are located at the edge of a network, these switches preferably include label edge router functionality. Exemplary commercially available hardware platforms for use as switches 300, 302, 310, and 312 include the BlackDiamond™ 6800 switch with one or more MPLS modules, available from Extreme Networks, Inc., of Santa Clara, Calif. A description of exemplary hardware and software of the BlackDiamond™ switch suitable for use with embodiments of the present invention will be described in detail below.

[0026] In the example illustrated in FIG. 3, end user equipment 308 on VLAN1 may desire to communicate with end user equipment 318 on VLAN1. In order to establish such communication, according to the present invention, switch 300 is initially configured as a master and switch 302 is initially configured as a slave. Similarly, switch 310 is initially configured as a master and switch 312 is initially configured as a slave. As used herein, the terms “master” and “slave” refer to states of the switch with regard to communicating across MPLS network 320. In master state, a switch establishes ingress and egress LSPs and a TLS or VC tunnel with a remote master switch and communicates VLAN traffic over the tunnel. In slave state, a switch establishes a redundant outgoing LSP for a VLAN but no incoming LSP or TLS tunnel. The redundant outbound LSP is not used for VLAN communications until the slave switch transitions to the master state.

[0027] According to an important aspect of the invention, a switch transitions dynamically between master and slave states based on relative connectivity to either the end user equipment or MPLS network 320. For example, switch 300 may initially be in the master state and switch 302 may initially be in slave state for VLAN1. On the side of user equipment 308, switch 300 may include a predetermined number of physical Ethernet interfaces that map to VLAN1. Similarly, switch 302 may also include a predetermined number of Ethernet interfaces that map to VLAN1. Table 1 shown below illustrates an example of a VLAN Ethernet connectivity table that may be used at each of switches 300 and 302 to monitor their local Ethernet connectivity interfaces to each VLAN.

[0028]

TABLE 1
VLAN to Ethernet Interface Mappings
VLAN ID	Ethernet Interfaces	Status
VLAN1	eth0	Up
	eth1	Up
VLAN4	eth2	Up
	eth3	Up
VLAN5	eth0	Up
	eth3	Up

In Table 1, each VLAN identifier is associated with multiple Ethernet interfaces. Since VLANs are logical networks, some VLANs may share Ethernet interfaces. These Ethernet interfaces are one measure of connectivity provided by each of switches 300 and 302 and the MPLS network.

[0029] Switches 300 and 302 may communicate connectivity information to each other via any suitable communication method. For example, switches 300 and 302 may communicate the connectivity information to each other via messages sent over a dedicated layer 2 connection between switches 300 and 302. In another example, switches 300 and 302 may exchange connectivity information via a user network. If a user network is used to exchange relative connectivity information, connectivity information exchange messages may be distinguished from user messages by establishing a separate VLAN between master and slave switches 300 and 302 via the user network.

[0030] Switches 300 and 302 continuously evaluate the connectivity information to make decisions as to which should be the master and which should be the slave. For example, if the number of available Ethernet interfaces for a particular VLAN on master switch 300 falls below the number of active interfaces for the VLAN available via slave switch 302, master switch 300 may transition to slave state and slave switch 302 may transition to master state.

[0031] Another example of a connectivity measurement that may be used to determine which switch functions as the master is relative connectivity to the MPLS network. For example, each switch 300 and 302 may maintain a table of IP address tracking data containing remote IP addresses to track on a perVLAN basis. Table 2 shown below is an example of IP address tracking data that may be maintained by switches 300 and 302 according to an embodiment of the present invention.

[0032]

TABLE 2
IP Address Tracking Data
VLAN ID	IP Address to Track	Label for outgoing LSP
VLAN1	10.10.221	17
	10.30.221	55
VLAN4	10.40.221	15
	10.50.221	13
VLAN5	10.70.221	7

[0033] In Table 2, each local VLAN is represented by a VLAN ID. Each VLAN ID has one or more remote IP addresses to track. If the switch has connectivity to the remote IP address via the MPLS network, a label will exist in the column labeled “Label for Outgoing LSP.” If connectivity between the VLAN and the remote IP address does not exist, the entry in column 3 of Table 2 will not have a label. The absence of a label may be caused by failure of a link or of a switch in the MPLS network connecting either master switch 300 or slave switch 302 and the remote endpoint IP address.

[0034] Switches 300 and 302 may use the connectivity information in Table 1, the connectivity information illustrated in Table 2, or the connectivity information in both Tables 1 and 2 to make the relative connectivity determination. In the event that the connectivity of slave switch 302 becomes better than that of master switch 300 for a particular VLAN, master switch 300 preferably switches to slave mode, and slave switch 302 switches to master mode. This action causes an incoming label switched path and a bi-directional VC tunnel to be established between master switch 310 and new master switch 302. New master switch 302 then sends data to and receives data from label edge router 310 via the newly established tunnel.

[0035] According to an important aspect of the invention, master and slave switches are configured to dynamically move an IP address between each other based on relative connectivity. Traditionally, IP addresses are associated with fixed network interfaces. According to the present invention, a movable IP address resides with the label edge router that is configured in master state and moves to the other label edge router when that label edge router becomes the new master. Movement of the IP address will be discussed in further detail below.

[0036] FIG. 4 is a state diagram illustrating exemplary states of a tunnel endpoint switch according to an embodiment of the present invention. In FIG. 4, the state diagram includes a master state 400 and a slave state 402. In master state 400, a tunnel endpoint switch advertises a route for the IP address for a particular VLAN, a label for an incoming LSP, and a label for a VC tunnel to MPLS label switched routers in MPLS network 320. The IP route advertisement may be performed using any suitable routing protocol, such as Open Shortest Path First (OSPF). The MPLS label advertisements may be performed using any suitable label distribution protocol, such as LDP. In master state 400, outgoing and incoming LSPs are established between the ingress master switch associated with the source VLAN and the egress master switch associated with the destination VLAN. A bi-directional layer 2 tunnel may then be set up between the master switches over the incoming and outgoing LSPs. An exemplary protocol suitable for establishing a bi-directional layer 2 tunnel over MPLS LSPs is targeted LDP, as described in IETF RFC 3036: “Label Distribution Protocol,” January 2001, the disclosure of which is incorporated herein by reference in its entirety. According to the LDP specification, a label switch router may send a targeted hello message to a specific address rather than to the “all routers” group multicast address in order to establish a label switched path with one specific router. According to the present invention, master switches preferably exchange targeted hello messages in order to establish the bi-directional layer 2 tunnel. Once the bi-directional layer 2 tunnel is established, the master switches exchange layer 2 traffic, such as VLAN traffic, over the tunnel.

[0037] In slave state, a tunnel endpoint switch establishes outgoing label switched paths with the master switch associated with the other VLAN endpoint but does not forward traffic received from its local VLAN over the outgoing label switched path. A redundant outgoing label switched path may be formed by listening to label advertisements from the master switch at the remote endpoint for its incoming label switched path for the local VLAN and storing the label mapping in a database resident in the slave switch.

[0038] FIG. 5 is a flow chart illustrating an exemplary standby routing protocol algorithm executed by a switch, such as master switch 300 or slave switch 302, according to an embodiment of the present invention in transitioning between the master and slave states illustrated in FIG. 4. Referring to FIG. 5, in step ST1, each switch sends connectivity information to the other local switch on a per VLAN basis. As stated above, such connectivity information may include the number of active Ethernet ports for each VLAN and/or the number of label switched paths for a remote endpoint with which the local VLAN desires to communicate. In step ST2, the standby routing protocol algorithm determines whether the switch on which it is executing is in master state. If the switch is in master state, control proceeds to step ST3, where the algorithm determines whether the switch should remain in master state. As discussed above, this decision may be made based on relative connectivity information, such as active ports and/or LSPs on a per VLAN basis. If the algorithm determines that the switch should remain in master state, no state transition occurs and control returns to step ST1. If the algorithm determines that the switch should transition to slave state, in step ST4, the switch transitions to slave state. Upon entering slave state, the switch withdraws MPLS labels for the local endpoint IP address (ST5), sends OSPF update messages to LSRs indicating that the IP address is unreachable (ST6), and tears down any VC tunnels associated with the VLAN (ST7).

[0039] Returning to step ST2, if the standby routing protocol algorithm determines that the switch on which the algorithm is executing is in slave state, control proceeds to step ST8, where the algorithm determines whether the switch should remain in slave state. This decision may be made based on relative connectivity information on a per VLAN basis, as discussed above. Another basis for determining whether or not to remain in slave state may be loss of standby routing protocol communications between the master and slave switches. If communications are lost or the relative connectivity of the current switch exceeds that of its companion switch, control the switch transitions to master state (ST9). If the algorithm determines that the switch should remain in slave state, no state transition occurs, and control returns to step ST1.

[0040] Upon entering the master state, in step ST10, the switch adds the local endpoint address to its OSPF layer and sends an OSPF update message advertising the IP address to LERs in the MPLS network. This step effectively moves the IP address from the former master switch to the new master switch. In step ST11, the algorithm advertises an MPLS label for the local endpoint IP address in order to set up an LSP for the IP address. In step ST12, the algorithm signals VC tunnels to TLS tunnel egress points configured for this VLAN. This step may be accomplished using targeted LDP. Thus, by continuously monitoring and exchanging relative connectivity information and switching between master and slave states in response to the relative connectivity information, the present invention allows seamless switching of tunnels across a wide area network with minimal disruption to service between endpoint local area networks.

[0041] FIG. 6 is a network diagram illustrating in more detail an example of transmitting packets between geographically diverse local area networks between master switches according to embodiment of the present invention. In FIG. 6, label master switch 300 advertises the IP address IP1 and the MPLS label 15 to LSR 602. LSR 602 advertises the label 17 to LSR 604. LSR 604 advertises the label 42 to remote master switch 310. This advertisement of labels sets up an outgoing label switched path from master switch 300 to master switch 310. Master switch 310 performs similar operations to set up a reverse label switched path to master switch 300. Master switches 300 and 310 each advertise the VLAN label 78 via targeted LDP to set up a VC tunnel over the underlying label switched paths.

[0042] Once the VC tunnel is set up, packets having a two-label stack can be transmitted over the tunnel between master switches 300 and 310. In FIG. 6, the packet structure for each segment is illustrated in block diagram format. For example, packets transmitted from master switch 300 to LSR 602 include a MAC destination address corresponding to LSR 602, a MAC source address corresponding to master switch 300, an MPLS outer label of 15 and an inner label of 78. LSR 602 uses the outer label to determine the next-hop LSR, which in this case is LSR3 604. Accordingly, LSR2 602 swaps the outer label of 15 for the outer label of 17 and forwards the packet to LSR3 604. LSR2 602 does not touch the inner label 78. LSR3 604 replaces the outer label 17 with a new outer label 42 and forwards the packet to master switch 310. Because master switch 310 is the VC tunnel endpoint, master switch 310 pops the outer label and reads the inner label 78. Since the label 78 was established to carry traffic from between instances 600 and 603 of VLAN1, master switch 310 forwards the data to local VLAN instance 603 of VLAN1.

[0043] The net result of creating a tunnel and switching packets over the tunnel is that layer 2 data can be transparently transmitted between instances 600 and 603 of VLAN1. Monitoring relative connectivity information and automatically switching between redundant local endpoints based on the relative connectivity information in the manner described above greatly increases the reliability of the connection between remote VLANs.

[0044] As stated above, the methods and systems described herein for providing redundant connectivity over a network can be implemented on any suitable switch with layer 2, IP, and MPLS capabilities, such as the BlackDiamond™ gigabit Ethernet switch available from Extreme Networks of Santa Clara, Calif. Physically, such a switch includes a rack with a plurality of card slots. Cards that perform different functions plug into the card slots. The card slots are connected via a high-speed switch fabric. One particular card that is of importance to the present invention is the management switching module (MSM). The MSM includes hardware and software that control the overall operations of other cards within the switch. These functions include the above-described standby routing protocol algorithm for providing redundant connectivity across a network.

[0045] FIG. 7 illustrates an exemplary hardware platform on which the methods and systems for providing redundant connectivity across a network using a tunneling protocol may be implemented. In FIG. 7, switch 300 includes a plurality of input/output modules 700-705 that provide connectivity to external networks. For example, input/output module 700 may be an Ethernet module that connects switch 300 to switch 302 to carry standby routing protocol messages over an Ethernet. Input/output modules 701 and 702 may also be Ethernet modules that connect switch 300 to the MPLS network. In addition to Ethernet capabilities, input/output modules 701 and 702 may also include MPLS label switching capabilities, VC tunneling capabilities, and LDP label distribution capabilities. Input/output modules 703-705 may connect switch 300 to a user VLAN, such as VLAN1 illustrated in FIG. 4. Accordingly, input/output modules 703-705 may be Ethernet modules with VLAN capabilities.

[0046] Modules 700-705 may be interconnected within switch 300 by a switch fabric 706. Switch fabric 706 switches packets received from external networks to the appropriate module or card for processing or routing to a destination network. In one exemplary implementation, switch fabric 706 may be a shared memory switch fabric controlled by a central processing unit 707. Alternatively, switch fabric 706 may be a shared medium switch fabric including one or more high-speed buses.

[0047] MSM 708 processes standby routing protocol messages received from switch 302. Accordingly, MSM 708 includes a standby routing protocol module 709 for implementing the standby routing protocol algorithm described above with respect to FIGS. 4 and 5. MSM 708 may also perform operations administration and maintenance functions, which are not of importance to explaining the present invention.

[0048] In operation, when switch 300 receives an SRP message from switch 302, the SRP message arrives via an Ethernet frame to input/output module 700. Input/output module 700 forwards the SRP message to switch fabric 706. Switch fabric 706 determines that the appropriate destination for the SRP message is MSM 708. Accordingly, switch fabric 706 forwards the SRP message to MSM 708. MSM 708 receives the SRP message and SRP module 709 processes the message. For example, SRP module 709 may extract connectivity information from the message and compare the connectivity information to the connectivity information of switch 300. The connectivity information of switch 300 may be stored in memory on MSM 708. Alternatively, MSM 708 may poll input/output modules 701-705 to determine the relative connectivity information. If SRP module 709 determines that a change in state is required, SRP module 709 may instruct the appropriate input/output modules to perform the functions required for changing states. For example, if SRP module 709 determines that switch 300 should switch from master state to slave state, SRP module 709 may instruct input/output modules 701 and 702 to advertise a route of unreachable to the movable IP address and withdraw labels associated with the outgoing LSP and the VC tunnel. SRP module 709 may also forward connectivity information regarding switch 300 to switch 302 via input/output module 700.

[0049] Thus, the present invention provides redundant connectivity between remote networks using a tunneling protocol. According to the invention, master and slave switches are provided at tunnel endpoints. The master switch at each tunnel endpoint establishes incoming and outgoing LSPs and a bi-directional tunnel with the master switch at the other tunnel endpoint. The slave switch at each tunnel endpoint generates an outgoing LSP with the master switch associated with the other tunnel endpoint. The master and slave switches at each tunnel endpoint exchange relative connectivity information. Based on the relative connectivity information, the master and slave switches dynamically move an IP address between each other. When the slave switch transitions to the master state, the new master switch establishes a tunnel with the master switch associated with the remote tunnel endpoint. Bi-directional communications can then occur over the new tunnel with minimal service interruption between remote VLANs.

[0050] It will be understood that various details of the invention may be changed without departing from the scope of the invention. Furthermore, the foregoing description is for the purpose of illustration only, and not for the purpose of limitation—the invention being defined by the claims.