Source: https://patents.google.com/patent/US8902728
Timestamp: 2018-02-23 20:46:10
Document Index: 200494032

Matched Legal Cases: ['§120', 'application No. 2004311004', 'application No. 2004311004', 'Application No. 200880105670', 'application No. 2004311004', 'Application No. 2', 'application No. 200680001652', 'application No. 200480033007', 'application No. 04812468', 'application No. 2004', 'application No. 06', 'application No. 08', 'application No. 200880105670', 'application No. 200880105670', 'application No. 200880105670', 'application No. 08', 'application No. 06720965', 'Application No. 04795045', 'Application No. 200880105670', 'application No. 04', 'application No. 04812468', 'application No. 04795045', 'application No. 06', 'application No. 08', 'application No. 04', 'application No. 06720965', 'application No. 08', 'application No. 200480033007', 'Application No. 2', 'application No. 200880105670', 'application No. 200880105670', 'application No. 200880105670', 'application No. 2004']

US8902728B2 - Constructing a transition route in a data communications network - Google Patents
Constructing a transition route in a data communications network
US8902728B2
US8902728B2 US13546971 US201213546971A US8902728B2 US 8902728 B2 US8902728 B2 US 8902728B2 US 13546971 US13546971 US 13546971 US 201213546971 A US201213546971 A US 201213546971A US 8902728 B2 US8902728 B2 US 8902728B2
US13546971
US20120275298A1 (en )
This application claims the benefit under 35 U.S.C. §120 as a Divisional of application Ser. No. 11/968,499, filed Jan. 2, 2008 now U.S. Pat. No. 8,238,232, which is a Divisional of application Ser. No. 10/442,589, filed May 20, 2003 now U.S. Pat. No. 7,330,440 the entire contents of which are hereby incorporated by reference as if fully set forth herein. The applicant(s) hereby rescind any disclaimer of claim scope in the parent application(s) or the prosecution history thereof and advise the USPTO that the claims in this application may be broader than any claim in the parent application(s).
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB) which is a map of the entire network topology and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning tree rooted at any other node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately.
As a result when a packet for a destination node arrives at a node (which we term here the “first node”), the first node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth. In some circumstances it is desirable to have more control over the route that a packet takes in which case “tunneling” can be used. According to this scheme if a node A receives a packet destined for node Z and for some reason it is desired that the packet should travel via node Y, under normal circumstances node A would have no control over this (unless Y was an adjacent node), as the route is dependent on the forwarding table generated as a result of the SPF at node A and any intermediate nodes as well. However node A can “tunnel” the packet to node Y by encapsulating the received packet within a packet having destination node Y and sending it to node Y which acts as the tunnel end point. When the packet is received at node Y it is decapsulated and Y then forwards the original packet to node Z according to its standard forwarding table. Yet further control is available using directed forwarding in which the encapsulated packet includes a specific instruction as to which neighboring node of the end point of the tunnel the encapsulated packet should be sent, which comprises the “release point”.
One solution for avoiding loops during a routing transition is described in co-pending patent application Ser. No. 10/323,358, filed 17 Dec. 2002, entitled “Method and Apparatus for Advertising a Link Cost in a Data Communications Network” of Michael Shand (Shand), the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to the solution put forward in Shand, when a node detects deactivation of an adjacent link or node, then instead of advertising the failure of the component, for example by simply removing the link from the LSP, the node that detects deactivation increments the associated link costs and advertises the incremented cost. As a result even when nodes have different LSDBs because of finite propagation and processing time of the LSP carrying the incremented link cost, loops are not set up in the remainder of the network. Once all nodes have updated their LSDBs, the detecting node increments the cost and advertises the incremented cost again. However in some circumstances it is desirable to converge on a common view of a network more quickly than is permitted by this incremental approach.
One alternative approach to dealing with link failure is described in document “Fortifying OSPF/IS-IS Against Link-Failure” by Mikkel Thorup (“Thorup”) which is available at the time of writing on the file “1f_ospf.ps” in the directory “˜mthorup\PAPERS” of the domain “research.att.com” on the World Wide Web. The approach of Thorup is to pre-compute the SPF at each node for each possible link failure. When a link failure is advertised the node forwards along its pre-computed updated path whilst updating the LSDB in the background.
FIG. 8 is a representation of the network of FIG. 1 showing transition and repair paths removed and new paths installed; and
The manner in which the backup route is computed is described in co-pending patent application Ser. No. 10/340,371, filed 9 Jan. 2003, entitled “Method and Apparatus for Constructing a Backup Route in a Data Communications Network” of Kevin Miles et al., (“Miles et al.”), the entire contents of which are incorporated by reference for all purposes as if fully set forth herein and discussed in more detail below. In particular, node A computes a first set of nodes comprising the set (which can be termed the “P-space”) 38 of all nodes reachable according to its routing protocol from node A, other than nodes reachable by traversing node B. Node A then computes a second set of nodes comprising the set of all nodes from which node D is reachable without traversing node B represented by space 40 (the “Qd-space”). In one embodiment the P-space and Q-space are pre-computed.
The method then determines whether any intermediate nodes exist in the intersection between P-space and Q-space or a one hop-extension thereof. For example in FIG. 1 nodes P and Q are within one hop of one another. As a result, in the event of the failure of node B packets of data can be sent from node A via path 32 as far as the intermediate node P then via link 34 node Q and thence via path 36 to the target node Y. The links 32, 34 and 36 can be viewed together as a “virtual” link forming a repair path in the event that node B fails or an alternative route is otherwise required.
All nodes pre-compute backup routes for all adjacent components as a result of which, as soon as a node detects de-activation of an adjacent component or otherwise needs an alternative route, that route is immediately available (although computation can alternatively be done in real time). As a result packet loss is minimized. Because the link state protocol is effectively undisturbed according to this method the fact that a repair path has been used is transparent to the remainder of the network. The labels “P-space”, “Q-space” and “T-space” are arbitrary and used for convenience and other embodiments may use any other label for the respective sets of nodes.
FIG. 2 is a flow diagram illustrating a high level view of a method of constructing a transition route in a data communications network which addresses the looping problem, with reference to the network shown in FIG. 1. In block 60 node A implements its repair paths on detection of a failure, and issues a “covert announcement” or transition notification that the path AB is no longer available, signaling the start of phase 1, a notification transition period. The network is considered to be made up of cooperating nodes, that is nodes such as nodes X, X′, X″ that support the appropriate protocols for implementing the method described herein and non-cooperating nodes, that is, those which continue to operate and forward in a conventional manner during the routing transition. In block 62 the cooperating nodes receive and recognize the covert announcement (non co-operating nodes do not recognize the covert announcement but merely pass it on). In block 64 each cooperating node constructs its transition routes. In particular it calculates its respective P-space, that is, the set of nodes reachable according to its routing protocol other than nodes reachable by traversing node B, in exactly the same manner as node A calculates its P-space. In the same manner each cooperating node calculates Q-space, that is, the set of nodes from which the target node is reachable without traversing node B which will be the same irrespective of the identity of the calculating node. Once again, using the same techniques as node A, the cooperating node hence constructs and implements a set of transition routes.
The Q-space 40 is constructed in a similar manner. Where the failed node B has a single downstream neighbor node D, as shown in FIG. 1, the reverse spanning tree (or “sink tree”) is computed showing the routes for each node from which node D is reachable, again excising all nodes from which node D is reached via the failed node B. In the case of multiple downstream neighbor nodes, the Q-space is derived for each of them. It will be appreciated that instead of extending the P-space to include additional nodes one hop away, Q-space can be extended instead, in conjunction with directed forwarding. In addition it would be possible to run the SPF algorithm to obtain P and Q-space in any order. In some instances it will not be necessary to construct a Q-space as the target node is found in P-space—this is more likely to happen for non-neighboring nodes.
Once the least cost repair path is assigned, there may still be multiple repair paths, one for each neighbor of the failed component which is a repair path target. To identify which repair path should be used it is necessary to assess the final destination of an incoming packet to the repairing node. This is achieved by recording which neighbor node would be used to reach each destination via the failed component in normal operation and assigning the traffic to the repair path generated with the appropriate neighbor as target. Of course any destination, not reachable via any of the neighbor nodes, will not require a repair path (as they do not traverse the failed component).
In order to establish whether the failure is a link failure or a node failure, any appropriate failure detection mechanism can be adopted, for example as described in co-pending patent application Ser. No. 10/346,051, filed 15 Jan. 2003, entitled “Method and Apparatus for Determining a Data Communication Network Repair Strategy”, of Stewart Bryant et al., (Bryant et al.), the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to the solution put forward in Bryant et al, and referring to FIG. 1 hereof, when a node A (“the detecting node”) detects a failure along an adjacent link which may be the link itself or the node to which it is connected, the detecting node implements a repair path around the link to node B as discussed in more detail above, sends a loop detection packet along the repair path and starts a timer with period t. The detecting node monitors for receipt of a packet. If the received packet is an acknowledgement from node B then evidently node B has not failed and the link repair strategy can be maintained. If, however, the received packet is the loop detection packet this implies that node B has failed and the loop detection packet has looped back to the detecting node via another node that has noticed that node B has failed. In those circumstances a node repair strategy is implemented. If the timer times out without the detecting node receiving any packet, because of severe congestion, then it is assumed that there is node failure and the node failure strategy is invoked. In either case the nature of the failed component is announced together with the covert announcement.
In the case of link repair from node F the set of nodes that can reach node B without traversing the link A, B is {BCDEGVZ}. The intersection of the set with router A's set of achievable release points is:
FIG. 5 is a flow diagram illustrating in more detail a method for constructing a transition route. In particular FIG. 5 illustrates the steps taken by a cooperating node in constructing a transition route. In block 110 the cooperating node receives a covert announcement identifying a failed or otherwise untraversable component. At block 112 the cooperating node identifies all nodes for which a destination node is reached via the failed components and either for which the next hop will change as a result of the failure or the next hop does not change but is a non-cooperating router. In block 104, for all of the identified nodes transition routes are computed as discussed above. It will be noted that this approach is an optimization—transition routes could be computed for every possible destination node. However, as discussed above, there is evidently no need to compute transition routes for nodes whose normal routing path is unaffected by the transition. Indeed if no traffic was flowing over the failed component prior to its failure there would be no need to implement any transition tunnels.
The above discussion assumes that it is possible to establish repair paths to all the necessary targets (“primary repair paths”) but it may be possible otherwise that targets unreachable via a primary repair path can be repaired from at least one other target which can be reached from the cooperating or neighboring node (“secondary repair path”). Accordingly if a cooperating node cannot install primary repair paths for some set of targets then it should install a transition tunnel with an end point of node A, the neighboring node to the failed component, for the set of nodes reachable through otherwise unreachable targets on the assumption that A will have computed appropriate secondary repair paths. The phase 3 timer is required to ensure that the neighboring node (e.g. node A) does not remove its repair paths before the cooperating nodes have removed their transition tunnels and replaced them with their new paths, as otherwise any cooperating nodes relying on secondary repair paths via the neighboring node would continue to forward leading to the potential formation of loops. However neighboring nodes with a complete set of primary repair paths can replace their repair paths with the new path at the end of phase 1. This is because if the neighboring node has a complete set of primary repair paths then it can be shown that all of the other nodes must as well such that none of the cooperating nodes will be relying on node A to provide secondary repair paths and tunneling to node A. Indeed this can be adopted as an optimization whereby all traffic from cooperating nodes is tunneled to the neighboring node that issued the covert announcement whose repair paths are then relied on, although this increases the encapsulation burden on the neighboring node. As discussed above, allocation of which repair path or transition path to use for a given packet is achieved by assessing which target node it would have traversed if the failed component were operational, and sending it down the tunnel to that target node. If traffic is being tunneled only to the neighboring node then its own allocation routine can be relied on and it is only necessary at a cooperating node to identify the destination which previously would have been reached by traversing the failed component and tunneling all traffic for that destination to a neighboring node with repair paths installed.
In the case of multiple concurrent failures then the cooperating node will receive multiple covert announcements. In the event that the covert announcements are in relation to the same failure then the transition routes can be installed as described above. However if it is established that more than one component has failed then the cooperating node proceeds to phase 3—in other words it installs its new path in a conventional manner.
1. A method of constructing a route in a data communication network comprising the steps of: in response to receiving a notification, identifying a transition of a first component of the data communication network, at a non-neighboring node of the first component from a neighboring node of the first component, constructing, at the non-neighboring node, a tunnel from the non-neighboring node to the neighboring node;
wherein the non-neighboring node is not directly connected to the neighboring node; wherein the neighboring node of the first component is configured to build a repair path around the first component; wherein the non-neighboring node is configured not to build the repair path around the first component, and is configured to use the tunnel and the repair path of the neighboring node to forward data around the first component; wherein the method is performed by one or more computing devices.
2. A method as claimed in claim 1, further comprising constructing another repair path around the first component from an adjacent component upon detection of the first component transition.
3. A method as claimed in claim 2, wherein the tunnel from the non-neighboring node is constructed for a destination that was reachable from the non-neighboring node via the first component.
4. A method as claimed in claim 2, wherein the tunnel from the non-neighboring node is constructed for a destination for which a next hop changes upon receipt of the notification identifying the first component transition.
5. A method as claimed in claim 2, wherein the tunnel from the non-neighboring node is removed upon expiry of a transition period.
6. An apparatus for constructing a route in a data communications network, the apparatus comprising: one or more processors; a network interface communicatively coupled to the processors and configured to communicate one or more packet flows among the processors and a data communications network; a computer readable storage medium storing one or more sequences of instructions for constructing a route in the data communication network, which instructions, when executed by the one or more processors, cause the one or more processors to perform: in response to receiving a notification identifying a transition of a first component of the data communications network, at a non-neighboring node of the first component from a neighboring node of the first component, constructing, at the non-neighboring node, a tunnel from the non-neighboring node to the neighboring node; wherein the non-neighboring node is not directly connected to the neighboring node; wherein the neighboring node of the first component is configured to build a repair path around the first component; wherein the non-neighboring node is configured not to build the repair path around the first component, and is configured to use the tunnel and the repair path of the neighboring node to forward data around the first component.
7. An apparatus of claim 6, further comprising instructions which, when executed, cause the one or more processors to perform: constructing another repair path around the first component from an adjacent component upon detection of the first component transition.
8. An apparatus of claim 7, wherein the tunnel from the non-neighboring node is constructed for a destination that was reachable from the non-neighboring node via the first component.
9. An apparatus of claim 7, wherein the tunnel from the non-neighboring node is constructed for a destination for which a next hop changes upon receipt of the notification identifying the first component transition.
10. An apparatus of claim 7, wherein the tunnel from the non-neighboring node is removed upon expiry of a transition period.
11. A non-transitory computer-readable storage medium storing one or more instructions which, when executed by one or more processors, cause the one or more processors to perform: in response to receiving a notification identifying a transition of a first component of a data communications network, at a non-neighboring node of the first component from a neighboring node of the first component, constructing, at the non-neighboring node, a tunnel from the non-neighboring node to the neighboring node; wherein the non-neighboring node is not directly connected to the neighboring node; wherein the neighboring node of the first component is configured to build a repair path around the first component; wherein the non-neighboring node is configured not to build the repair path around the first component, and is configured to use the tunnel and the repair path of the neighboring node to forward data around the first component.
12. A computer-readable storage medium as claimed in claim 11, further comprising instructions which, when executed, cause the one or more processors to perform: constructing another repair path around the first component from an adjacent component upon detection of the first component transition.
13. A computer-readable storage medium as claimed in claim 12, wherein the tunnel from the non-neighboring node is constructed for a destination that was reachable from the non-neighboring node via the first component.
14. A computer-readable storage medium as claimed in claim 12, wherein the tunnel from the non-neighboring node is constructed for a destination for which a next hop changes upon receipt of the notification identifying the first component transition.
15. A computer-readable storage medium as claimed in claim 12, wherein the tunnel from the non-neighboring node is removed upon expiry of a transition period.
US13546971 2003-05-20 2012-07-11 Constructing a transition route in a data communications network Active 2023-08-11 US8902728B2 (en)
US10442589 US7330440B1 (en) 2003-05-20 2003-05-20 Method and apparatus for constructing a transition route in a data communications network
US11968499 US8238232B2 (en) 2003-05-20 2008-01-02 Constructing a transition route in a data communication network
US13546971 US8902728B2 (en) 2003-05-20 2012-07-11 Constructing a transition route in a data communications network
US11968499 Division US8238232B2 (en) 2003-05-20 2008-01-02 Constructing a transition route in a data communication network
US20120275298A1 true US20120275298A1 (en) 2012-11-01
US8902728B2 true US8902728B2 (en) 2014-12-02
ID=39031498
US10442589 Active 2026-03-07 US7330440B1 (en) 2003-05-20 2003-05-20 Method and apparatus for constructing a transition route in a data communications network
US11968499 Active 2026-03-16 US8238232B2 (en) 2003-05-20 2008-01-02 Constructing a transition route in a data communication network
US13546971 Active 2023-08-11 US8902728B2 (en) 2003-05-20 2012-07-11 Constructing a transition route in a data communications network
US (3) US7330440B1 (en)
ES2385011B1 (en) 2010-10-25 2013-05-20 Telefónica, S.A. Procedure for establishing routes on the transmission network effectively.
FR2775492B1 (en) 1998-02-27 2000-05-05 Freyssinet Int Stup prefabricated building components, prestressed book realized with such Elements and method for manufacturing such Elements
AU Examiner's First Report for foreign patent application No. 2004311004 dated Jun. 23, 2008, 1 page.
AU Examiner's Second Report for foreign patent application No. 2004311004 dated Aug. 18, 2008, 1 page.
Balon et al., "A Scalable and Decentralized Fast-Rerouting Scheme With Efficient Bandwidth Sharing" dated Dec. 2004, 21 pages.
Balon, Simon, "A Scalable and Decentralized Fast-Rerouting Scheme With Efficient Bandwidth Sharing", Computer Networks, Science Direct, Dated Jan. 31, 2005, 18 pages.
Bryant, S. et al., "IP Fast Reroute Using Not-via Addresses", Network Working Group, Internet Draft, dated Jul. 2007, 24 pages.
Chinese Patent Office, CN Office Action received in International Application No. 200880105670.2 dated Dec. 23, 2011 (4 pages).
Claims, application No. EP 04795045, dated May 2007 4 pages.
Claims, application No. EP 04812468, dated May 2010, 4 pages.
Claims, application No. EP 06720965, dated Jul. 2009, 4 pages.
Claims, filing No. 200680001652.0, dated May 2009, 3 pages.
Current Claims for AU patent application No. 2004311004, dated Aug. 2008, 6 pages.
Current claims for CA Application No. 2,537,898. Dated Feb. 2010, (6 pgs).
Current claims for CN application No. 200680001652.0., dated Oct. 2010.
Current Claims for CN foreign patent application No. 200480033007.8, dated Apr. 2008, 6 pages.
Current claims for European application No. 04812468.9, Applicant: Cisco Technology, Inc., Feb. 2011 (6 pages).
Current claims for Foreign Office Action in patent application No. 2004-80026214.0., 4 pages, dated May 2011.
Current Claims in application No. 06 720 965.0-1505, dated Apr. 2013, 5 pages.
Current Claims in application No. 08 798 837.4-1525, dated Feb. 2013, 3 pages.
Current Claims in application No. 200880105670.2 dated May 2013, 2 pages.
Current Claims in application No. 200880105670.2, dated Nov. 2013, 2 pages.
Current Claims in application No. 200880105670.2, dated Oct. 2012, 2 pages.
Current claims in EP for foreign patent application No. 08 798 837.4-1525, Applicant: Cisco Systems Inc, dated Jul. 2011. (3 pgs).
Current claims in for foreign patent application No. 06720965.0.-1525, Applicant: Cisco Technology, Inc. dated May 2011, 3 pages.
Current Claims, Application No. 04795045.6-2416, dated Sep. 2009, 5 pages.
Current Claims, Application No. 200880105670.2, dated Dec. 2011, ( 3 pages).
European Claims in application No. 04 812 468.9-1862, dated Aug. 2014, 5 pages.
European Office Action application No. 04812468.9, Applicant: Cisco Technology, Inc., dated Feb. 28, 2011 (6 pages).
European Patent Offfice, Oral Hearing for foreign patent application No. 04795045.6-2416, Applicant: Cisco Technology, Inc., dated May 17, 2011, 4 pages.
European Patent Office, "Office Action" in application No. 06 720 965.0-1505, dated Apr. 25, 2013, 6 pages.
European Patent Office, "Office Action", in application No. 08 798 837.4-1525, dated Feb. 5, 2013, 8 pages.
European Patent Office, "Search Report" In application No. 04 812 468.9-1862, dated Aug. 8, 2014, 5 pages.
European Patent Office, Office Action for foreign patent application No. 06720965.0-1525, Applicant: Cisco Technology, Inc., dated May 2, 2011, 5 pages.
European Patent Office, Office Action from EP for foreign patent application No. 08 798 837.4-1525, Applicant: Cisco Systems Inc., dated Jul. 1, 2011 (4 pgs).
Moy, J. "Network Working Group" Network Working Group, Ascend Communications, Inc., Internet Society, Dated Apr. 1998 (245 pages).
Office Action from CN for foreign application No. 200480033007.8, dated Apr. 11, 2008, 10 pages with English translation, 11 pages.
Office Action, Canadian Application No. 2,537,898 dated Feb. 15, 2010 (2 pgs).
Previdi, Stefano, "IP FAST ReRoute Technologies", Cisco Systems, dated 2006, 60 pages.
S. Bryant et al., entitled "Internet Draft IP Fast Reroute Using Notvia Addresses" dated Mar. 2005 (13 pages).
State Intellectual Property Office of the People's Republic of China, "The Fourth Office Action" in application No. 200880105670.2, dated Nov. 27, 2013, 4 pages.
State Intellectual Property Office of the People's Republic of China, "Third Office Action" in application No. 200880105670.2 dated May 10, 2013, 16 pages.
The Patent Office of the People's Republic of China, "The Second Office Action", in application No. 200880105670.2, dated Oct. 10, 1012, 7 pages.
The Patent Office of the People's Republic of China, Office Action received in foreign patent application No. 2004-80026214.0 dated May 10, 2011, 4 pages.
US20080101259A1 (en) 2008-05-01 application
US8238232B2 (en) 2012-08-07 grant
US7330440B1 (en) 2008-02-12 grant
US20120275298A1 (en) 2012-11-01 application