Source: https://patents.google.com/patent/US7535826B1/en
Timestamp: 2019-04-19 05:20:24
Document Index: 384593372

Matched Legal Cases: ['§ 119', '§ 112', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4']

US7535826B1 - Routing protocols for accommodating nodes with redundant routing facilities - Google Patents
Routing protocols for accommodating nodes with redundant routing facilities Download PDF
US7535826B1
US7535826B1 US10/014,323 US1432301A US7535826B1 US 7535826 B1 US7535826 B1 US 7535826B1 US 1432301 A US1432301 A US 1432301A US 7535826 B1 US7535826 B1 US 7535826B1
routing facility
US10/014,323
Anthony Joseph Li
2000-12-11 Priority to US25459300P priority Critical
2001-12-10 Application filed by Juniper Networks Inc filed Critical Juniper Networks Inc
2001-12-10 Priority to US10/014,323 priority patent/US7535826B1/en
2002-04-16 Assigned to JUNIPER NETWORKS, INC. reassignment JUNIPER NETWORKS, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: LI, ANTHONY JOSEPH, COLE, BRUCE
2009-05-19 Publication of US7535826B1 publication Critical patent/US7535826B1/en
Graceful restart in routers having redundant routing facilities may be accomplished by replicating network (state/topology) information.
Benefit is claimed, under 35 U.S.C. § 119(e)(1), to the filing date of provisional patent application Ser. No. 60/254,593, entitled “ROUTING PROTOCOLS FOR ACCOMMODATING NODES WITH REDUNDANT ROUTING FACILITIES”, filed on Dec. 11, 2000 and listing Bruce Cole as the inventor, for any inventions disclosed in the manner provided by 35 U.S.C. § 112, ¶1. This provisional application is expressly incorporated herein by reference.
Many large networks are made up of interconnected nodes (referred to as “routers” below without loss of generality). The routers may be geographically distributed throughout a region and connected by links (e.g., optical fiber, copper cable, wireless transmission channels, etc.). In such a network, each router typically interfaces with (e.g., terminates) multiple input links and multiple output links. Addressed data (referred to as “packets” below without loss of generality) traverse the network by being forwarded from router to router until they reach their destinations (as typically specified in by so-called layer-3 addresses in the packet headers). Unlike nodes in a “circuit-switched” network, which establish a connection for the duration of a “call” or “session” to send data received on a given input port out on a given output port, routers determine the destination addresses of received packets and, based on these destination addresses, determine, in each case, the appropriate output link on which to send them. Since, unlike nodes in a “circuit-switched” network, routers are not connection-based, packets having the same destination address may actually traverse different paths through the network.
The present invention may be used to effect at least a part of a routing protocol between two nodes, at least one of which including redundant routing facilities. Basically, in one embodiment, the present invention converts each router to router peering session to a one to N peering session, where N is the number of redundant routing engines. In another embodiment, (i) active and standby routing engines share system identifiers and SNPAs, (ii) standby routing engine(s) runs a routing protocol, but certain messages are suppressed, (iii) standby routing engine(s) may form partial adjacencies with remote nodes (e.g., receive, but don't give network information), (iv) the designated routing engine floods its database information to the standby routing engine(s), and (v) the standby routing engine(s) accept link state packets with its system identifier.
The present invention involves novel methods, apparatus and data structures for effecting at least a part of a routing protocol between two nodes, at least one of which includes redundant routing facilities. The following description is presented to enable one skilled in the art to make and use the invention, and is provided in the context of particular applications and their requirements. Various modifications to the disclosed embodiments will be apparent to those skilled in the art, and the general principles set forth below may be applied to other embodiments and applications. Thus, the present invention is not intended to be limited to the embodiments shown and the inventor regards his invention as the described methods, apparatus and data structures and any other patentable subject matter.
In the following, an exemplary environment in which the present invention may operate is described in § 4.1. Then, functions that may be performed by the present invention are introduced in § 4.2. Then, exemplary operations, apparatus, methods and data structures that may be used to effect those functions are described in § 4.3. Examples of operations of an exemplary embodiment of the invention are then provided in § 4.4. Finally, some conclusions regarding the present invention are set forth in § 4.5.
§ 4.1 ENVIRONMENT IN WHICH THE PRESENT INVENTION MAY OPERATE § 4.1.1 Exemplary Network Environment
FIG. 1 illustrates an internet in which the present invention may be used. As illustrated in FIG. 1, an internet 100 may be viewed as a number of sub-networks or “autonomous systems” (also referred to as “AS”) 110, 150. Different entities may own and/or operate different autonomous systems. A routing algorithm for use within an autonomous system is called an “interior gateway protocol” (or “IGP”), while a routing algorithm for use between autonomous systems is called an “exterior gateway protocol”. Known interior gateway protocols have been classified as distance vector routing protocols (e.g., the “routing information protocol” (or “RIP”)), and link state protocols (e.g., the “open shortest path first” (or “OSPF”) protocol and the “intermediate system-to-intermediate system” (or “IS-IS”) protocol). Known exterior gateway protocols include the “border gateway protocol” (or “BGP”), which is a path vector routing protocol.
Referring to the autonomous system 150 of FIG. 1, the OSPF interior gateway protocol may divide the autonomous system 150 into a number of areas 154, each of which is connected with a backbone area 152. Routers can be classified as follows. “Internal routers” are wholly within one area (See, e.g., routers 153, 160.), “area border routers” connect two or more areas (See, e.g., router 158.), “backbone routers” are in the backbone (See, e.g., router 153.), and “AS boundary routers” neighbor routers in other autonomous systems (See, e.g., routers 112 and 156.). Notice that a given router may belong to more than one class.
§ 4.1.2 Exemplary Network Node
To address (hardware and/or software) routing failures, some network nodes include redundant routing operations that share a single forwarding operation (which may itself include redundant forwarding operations). For example, as illustrated in the process bubble diagram of FIG. 3, some nodes may include redundant routing operations (also referred to as “routing engines” or “REs” without loss of generality) 220 a′ and 220 b′. Both routing operations 220 a′ and 220 b′ may maintain their own network topology information 240 a′ and 240 b′, respectively, and both may accept and disseminate network state information. However, only one routing operation 220 a′ or 220 b′ will be used to generate forwarding information used to populate the forwarding table 250′. This routing operation 220 a′ or 220 b′ may be referred to as a designated routing engine (or “DRE”) below, without loss of generality. A routing engine designator 305 may be used to select the designated routing engine (DRE), for example based on an accepted designated routing engine selection signal. The other(s) routing engine(s) may be referred to as a “standby” routing engine(s).
The present invention may function to define new routing protocols, or to extend known routing protocols, such as BGP and IS-IS for example, to consider and accommodate nodes with redundant routing engines. The present invention may function to replicate network state information used by a routing protocol so that, in the event of failover, a newly designated routing engine does not need to establish new connections and learn network state information “starting from scratch” (which may take on the order of 20 minutes in a complex ISP network).
In the context of a path vector, exterior gateway routing protocol, such as BGP for example, the present invention may operate to (i) allow nodes with redundant routing engines to advertise that fact (e.g., using a “redundancy router identifier”) to other nodes, (ii) allow nodes to signal which of a plurality of routing engines is its current designated routing engine, (iii) allow remote nodes to distinguish information sent by a designated routing engine from information sent by a standby routing engine(s), and/or (iv) allow remote nodes to handle all paths advertised, but to not use paths advertised by a standby routing engine(s) of a redundancy router. Further, in the event that the designated routing engine fails, the present invention may operate to (i) have the node (e.g., the “redundancy router”) select a new designated routing engine, (ii) signal to external (e.g., peering) nodes the new designated routing engine, and (iii) have external nodes update their route information database (e.g., “RIB”) to reject paths learned from the former designated routing engine and to accept paths learned from the new designated routing engine.
In the following, operations which may be performed by the present invention are introduced in § 4.3.1 below. Then, architecture, methods and data structures which may be used to effect these processes are described in § 4.3.2.
The present invention may operate in network nodes, such as those illustrated in FIGS. 2 and 3, to extend routing protocol operations to effect one or more of the functions introduced in § 4.2 above.
Exemplary systems on which the functions introduced in § 4.2 above may be effected are described in § 4.3.2.1 below. Then exemplary methods that may be used to effect these functions, and exemplary data structures that may be used by these methods, are described in § 4.3.2.2 below.
§ 4.3.2.1 Exemplary Architectures
§ 4.3.2.2 Exemplary Methods and Data Structures
Exemplary methods and data structures for effecting a link state routing protocol operation which considers and accommodates nodes with redundant routing engines are described in § 4.3.2.2.1 below with reference to FIG. 5. Then, exemplary methods and data structures for effecting a path or distance vector routing protocol operation which considers and accommodates nodes with redundant routing engines are described in § 4.3.2.2.2 below with reference to FIGS. 6 and 7.
§ 4.3.2.2.1 Exemplary Link State Routing Protocols for Accommodating Nodes with Redundant Routing Engines
In the context of the IS-IS link state protocol, the method may operate to (i) generate constrained shortest path first (“CSPF”) protocol data units (“PDUs”) (e.g., on a control plane) for the designated routing engine (“DRE”), (ii) drop the IS-IS Hellos (“IIHs”) generated by the standby routing engine(s) before they are actually transmitted, (iii) suppress link state packet(s) (“LSP”) and complete sequence number packet (“CSNP”) transmissions by the standby routing engine(s), and/or suppress partial sequence number packet (“PSNP”) transmissions for all interfaces, except the control plane, for the standby routing engine(s).
In the extension to the IS-IS protocol, note that the state of the system is not affected. Further, since both the designated routing engine and the standby routing engine(s) use the same domain-unique system identifier (“sysid”) and the same sub-net point of attachments (“SNPAs”) (e.g., media access control or MAC addresses), adjacencies (to external nodes) should come up on the standby routing engine(s), even though no adjacency actually exists.
In the extension to the IS-IS protocol, state transfer to the standby routing engine(s) may be accomplished by having the designated routing engine perform flooding on the redundancy router's control plane (e.g., run on an internal Ethernet of the node). In effect, the designated routing engine is elected as the designated intermediate system (“DIS”) and uses CSPN PDUs to transmit its network topology (e.g., link state database) state. The standby routing engine(s) is free to use PSNP PDUs to insure that it has a complete set of LSPs.
Since there is a chance that the standby routing engine(s) may generate an LSP that differs from that of the designated routing engine, either in content or in sequence number, it may be desired to modify the LSP generation code so that the standby routing engine(s) simply accepts LSPs that appear to have its own system identifier (“sysid”). In the event of a failover, full LSP generation should be triggered on the newly selected designated routing engine. At failover, the newly designated routing engine may take on the identity (e.g., Layer 2 (MAC) address in the case of IS-IS failover) of the former designated routing engine.
§ 4.3.2.2.2 Other Exemplary Protocols, Including Path and Distance Vector Routing Protocols for Accommodating Nodes with Redundant Routing Engines
The method 230′″ illustrated in FIG. 6, or instances thereof, may be performed by individual routing engines of the node. It is conceivable, however, that some acts of the method 230′″ may be centrally performed by the node. As indicated by block 610, the node (e.g., using each of its routing engines) may inform an external node(s) that the node is a “redundancy router”. As indicated by block 630, the routing engine informs an external node(s) as to whether it is the designated routing engine. Alternatively, the node may, itself, identify its designated routing engine to an external node(s) using a centralized signaling operation. As indicated by block 640, the routing protocol is executed by each routing engine as it would normally be executed otherwise. Finally, as indicated by decision branch point 650 and block 655, if the designated routing engine fails, such a failure is reported so that the redundancy node may select a new designated routing engine and so that external nodes (e.g., peers) may be informed of the new designated routing engine.
Referring now to FIG. 7, a node interacting (e.g., peering) with a node having redundant routing engines (“the redundancy router”) may accept a message or messages conveying that the external node is a “redundancy router”, and that a given routing engine of the node (e.g., having a unique IP address) is the designated routing engine, as indicated by block 710. The node may accept further signaling from the routing engines of the redundancy router node as indicated by block 730. As indicated by decision branch point 740, it is determined whether the accepted signaling is from the designated routing engine or from a standby routing engine. If the signaling is from the designated routing engine, any paths signaled are accepted as indicated by block 750. If, on the other hand, the signaling is from a standby routing engine, any paths signaled are rejected as indicated by block 760. Such rejected paths may, however, be stored (but not immediately used). Such storage may be considered important if it cannot be assumed that each of the redundant routing engines are synchronized. If, however, it can be assumed that the redundant routing engines are synchronized, then (rejected) paths from the standby routing engine(s) needn't be stored (although the failover should be signaled).
Notice also that if a message indicating a new designated routing engine is received, the node will update its routing information (e.g., its “RIB”) to reject paths learned from the former designated routing engine and to accept paths learned from the new designated routing engine (via new messages or using stored, but previously rejected, paths), as indicated by decision branch point 720 and block 725.
In the extension to the BGP protocol, the remote node (e.g., peer) may treat all BGP paths advertised by the standby routing engine(s) as though they were rejected by import policy. When the remote node learns of a new designated routing engine (e.g., through a DESIGNATED_ROUTER message), it may update its routing information database (“RIB”) to reject the paths learned from the former designated routing engine and to accept the paths learn from the newly elected designated routing engine. During this change, any route damping figure of merits should not be increased. Thus, the remote node may be configured to peer with all of the routing engines of a redundancy router. Each routing engine in the redundancy group may share the same local and remote autonomous system (“AS”) numbers. The redundant routing engines may be assigned unique IP addresses for peering purposes. Thus, the remote node does not need to be explicitly configured to know the set of routing engines that form the redundancy group. Each routing engine in the redundancy group may share identical BGP configurations, except for the local IP address used for peering purposes. The redundancy router identifier may be configured on each of the redundant routing engines (e.g., in a routing-options section command of a node with the JUNOS operating system from Juniper Networks). This part of the configuration may also be shared.
§ 4.4 EXAMPLES OF OPERATIONS IN AN EXEMPLARY EMBODIMENT
FIG. 8 is a high-level block diagram illustrating a peering between two nodes 830 and 840 in two different autonomous systems 810 and 820. (Recall, for example, nodes 156 and 112 b, 194 and autonomous systems 110′ and 150′ in FIG. 1.) In the following example, it is assumed that the peering takes place using a path vector routing protocol, such as BGP for example. It is further assumed that the first node 830 has a forwarding facility 832, multiple routing facilities 834, each routing facility having associated routing information 836 and forwarding information 838, and a controller 839 which, among other things, may select a designated routing facility (or “engine”), and may perform system or node level signaling. Further, each routing facility 834 may share a common redundancy router identifier, as well as local and remote autonomous system identifiers, but each 834 may have its own layer 3 (e.g., IP) address. The second node 840 has a forwarding facility 842, a routing facility (or “engine”) 844, associated routing information 846 a (and 846 b), and forwarding information 848. The second set of routing information 846 b needn't be stored if it can be assumed that the redundant routing engines 834 are synchronized, in which case the routing information 846 b would be the same as the routing information 846 a.
The nodes 830 and 840 are coupled via a physical link 850 (e.g., facilitating optical, electrical, and/or wireless communications), or a multi-hop path (e.g., BGP peering). Logical communications are denoted with dashed lines, even though such communications occur via the physical link 850.
FIG. 9 is a messaging diagram illustrating a peering session between two nodes, at least one having redundant routing facilities. (See, e.g., the nodes 830 and 840 of FIG. 8.) So-called “NOTIFICATION” and “KEEPALIVE” BGP messages are not shown in order to simplify the drawing. Operations of the first node 830′, operating in accordance with the method illustrated in FIG. 6, and operations of the second node 840′, operating in accordance with the method of FIG. 7, are illustrated.
Referring to both block 610 and communications 910 and 920, the first node 830′, and more specifically, each of the routing facilities 834′ of the first node 830, may inform the second node 840′ that it (i.e., the first node 830′) is a “redundancy router” in “OPEN” messages 910 and 920. The “BGP identifier” parameter of a BGP “OPEN” message may include the router identifier (12) shared by the REs. The “option data” parameter of a BGP “OPEN” message may indicate that the routing engine is a part of a redundancy router. The second node 840′ may send its own “OPEN” messages 915 and 925 in which it indicates that it supports a protocol supporting nodes with redundant routing facilities, such as a protocol described by the present invention. Such an indication may be carried in the “option data” parameter of a BGP “OPEN” message.
In this example, the first routing facility 834 a′ has be selected, by whatever means, as the designated routing engine. This fact is communicated to the second node 840′ as indicated by the “DESIGNATED_ROUTER” communication 930. (Recall, e.g., block 630 of FIG. 6.) Recall that this communication may include an election number.
Recall from block 750 of FIG. 7 that the remote (e.g., peer) node will accept paths from the designated routing engine. Such paths may be included in BGP “UPDATE” messages. These messages are not shown in order to simplify FIG. 9.
At some point, the designated routing engine may fail, as indicated by event 940. In such an event, it is assumed that the second routing facility 834 b′ is elected, by whatever means, as the new designated routing engine. This fact is communicated to the second node 840′ as indicated by the second “DESIGNATED_ROUTER” communication 950. (Recall, e.g., block 630 of FIG. 6.) Recall that this communication may include an election number, which should be larger than the election number in the previous “DESIGNATED_ROUTER” communication 930. Recall from FIG. 7 that the remote (e.g., peer) node will now reject the paths from the former designated routing engine, and will now accept the (new and/or previously rejected, but stored) paths from the newly elected designated routing engine. Again, such paths may be included in BGP “UPDATE” messages. These messages are not shown in order to simplify FIG. 9.
1. For use in a router adapted to interact with an external router having, at a given time, a currently designated routing facility and a current standby routing facility, a method comprising:
a) accepting, from the external router, the identity of the currently designated routing facility;
b) accepting, from the currently designated routing facility of the external router when it is in a state of being the designated routing facility, network information;
c) using the network information accepted from the currently designated routing facility of the external router for determining routes; and
d) accepting, from the current standby routing facility of the external router when it is in a state of being the standby routing facility, network information, but not using it for determining routes.
e) storing the network information accepted from the current standby routing facility of the external router.
f) accepting, from the external router, an indication that the currently designated routing facility has failed;
g) accepting, from the external router, an indication that the formerly current standby routing facility has been elected as a new designated routing facility; and
h) using the network information from the formerly current standby routing facility that is now the newly elected new designated routing facility.
e) accepting, from the external router, an indication that the currently designated routing facility has failed;
f) accepting, from the external router, an indication that the formerly current standby routing facility has been elected as a new designated routing facility; and
g) using path information from the newly elected new designated routing facility.
5. A machine-readable medium having machine readable instructions stored thereon which, when executed by a machine, effect the method of claim 1.
6. The method of claim 1 wherein the router and the external router belong to different autonomous systems.
7. A router adapted to interact with an external router having, at a given time a currently designated routing facility and a current standby routing facility, the router comprising:
a) an input for
i) accepting, from the external router, the identity of the currently designated routing facility, and
ii) accepting, from the currently designated routing facility of the external router when it is in a state of being the designated routing facility, network information; and
b) a routing facility for
i) using the network information accepted from the currently designated routing facility of the external router for determining routes, and
ii) accepting, from the current standby routing facility of the external router when it is in a state of being the standby routing facility, network information, but not using it for determining routes.
8. The router of claim 7 further comprising:
c) a storage device for storing the network information accepted from the current standby routing facility of the external router.
9. The method of claim 8 wherein the input is further adapted for
iii) accepting, from the external router, an indication that the currently designated routing facility has failed, and
iv) accepting, from the external router, an indication that the formerly current standby routing facility has been elected as a new designated routing facility, and
wherein the routing facility is further adapted to use the network information that was accepted from the formerly current standby routing facility and that was stored, if it is newly elected as the new designated routing facility.
10. The router of claim 7 wherein the input is further adapted for
wherein the routing facility is further adapted to use path information from the newly elected new designated routing facility when the input accepts the indication that the formerly current standby routing facility has been elected as the new designated routing facility.
11. The router of claim 7 wherein the router and the external router belong to different autonomous systems.
US10/014,323 2000-12-11 2001-12-10 Routing protocols for accommodating nodes with redundant routing facilities Active 2024-02-07 US7535826B1 (en)
US25459300P true 2000-12-11 2000-12-11
US10/014,323 US7535826B1 (en) 2000-12-11 2001-12-10 Routing protocols for accommodating nodes with redundant routing facilities
US12/422,103 US8391134B2 (en) 2000-12-11 2009-04-10 Routing protocols for accommodating nodes with redundant routing facilities
US13/782,812 US9054956B2 (en) 2000-12-11 2013-03-01 Routing protocols for accommodating nodes with redundant routing facilities
US14/715,489 US9825886B2 (en) 2000-12-11 2015-05-18 Routing protocols for accommodating nodes with redundant routing facilities
US12/422,103 Continuation US8391134B2 (en) 2000-12-11 2009-04-10 Routing protocols for accommodating nodes with redundant routing facilities
US7535826B1 true US7535826B1 (en) 2009-05-19
ID=40636013
US10/014,323 Active 2024-02-07 US7535826B1 (en) 2000-12-11 2001-12-10 Routing protocols for accommodating nodes with redundant routing facilities
US12/422,103 Active 2022-05-31 US8391134B2 (en) 2000-12-11 2009-04-10 Routing protocols for accommodating nodes with redundant routing facilities
US13/782,812 Active 2022-02-27 US9054956B2 (en) 2000-12-11 2013-03-01 Routing protocols for accommodating nodes with redundant routing facilities
US14/715,489 Active 2022-07-31 US9825886B2 (en) 2000-12-11 2015-05-18 Routing protocols for accommodating nodes with redundant routing facilities
US (4) US7535826B1 (en)
US20100008222A1 (en) * 2006-09-25 2010-01-14 Jean-Louis Le Roux Routing Method in a Label Switching Network
US20110255417A1 (en) * 2007-10-12 2011-10-20 Nortel Networks Limited Automatic mep provisioning in a link state controlled ethernet network
US20120057868A1 (en) * 2009-05-11 2012-03-08 Zte Corporation Method and System for Implementing Alternate Routes in Optical Transmission Network of Wavelength Switched Optical Network (WSON)
US20170214609A1 (en) * 2016-01-21 2017-07-27 Fujitsu Limited Forwarding method and forwarding device
CN101707537B (en) * 2009-11-18 2012-01-25 华为技术有限公司 Positioning method of failed link and alarm root cause analyzing method, equipment and system
US20020191547A1 (en) * 2000-11-30 2002-12-19 Bora Akyol Scalable and fault-tolerant link state routing protocol for packet-switched networks
US7031252B1 (en) * 2000-03-27 2006-04-18 Cisco Technology, Inc. Reflector communications channel for automatic protection switching
SE504766C2 (en) * 1994-08-18 1997-04-21 Telia Ab Arrangements for providing lokalnätsemuleringstjänst over public connectionless ATM network
2001-12-10 US US10/014,323 patent/US7535826B1/en active Active
2009-04-10 US US12/422,103 patent/US8391134B2/en active Active
2013-03-01 US US13/782,812 patent/US9054956B2/en active Active
2015-05-18 US US14/715,489 patent/US9825886B2/en active Active
US8218432B2 (en) * 2006-09-25 2012-07-10 France Telecom Routing method in a label switching network
US8918538B2 (en) * 2007-10-12 2014-12-23 Rockstar Consortium Us Lp Automatic MEP provisioning in a link state controlled ethernet network
US9301028B2 (en) * 2009-05-11 2016-03-29 Zte Corporation Method and system for implementing alternate routes in optical transmission network of wavelength switched optical network (WSON)
US9054956B2 (en) 2015-06-09
US9825886B2 (en) 2017-11-21
US20090219804A1 (en) 2009-09-03
US20130176843A1 (en) 2013-07-11
US20150256488A1 (en) 2015-09-10
US8391134B2 (en) 2013-03-05
AU2004308327B2 (en) 2009-07-16 System and method for distributing route selection in an implementation of a routing protocol