Source: http://www.google.com/patents/US7869350?dq=6272333
Timestamp: 2014-08-29 11:04:44
Document Index: 345337238

Matched Legal Cases: ['application No. 2004311004', 'application No. 2004311004', 'application No. 2004311004', 'application No. 200480033007', 'Application No. 04795045', 'Application No. 04795045', 'application No. 200480033007']

Patent US7869350 - Method and apparatus for determining a data communication network repair ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsA method is disclosed for determining a repair strategy for a data communication network. The data communication network has as components nodes and links. The method comprises a step of implementing a link repair strategy for an adjacent link to an adjacent node. The method further monitors for a probe...http://www.google.com/patents/US7869350?utm_source=gb-gplus-sharePatent US7869350 - Method and apparatus for determining a data communication network repair strategyAdvanced Patent SearchPublication numberUS7869350 B1Publication typeGrantApplication numberUS 10/346,051Publication dateJan 11, 2011Filing dateJan 15, 2003Priority dateJan 15, 2003Publication number10346051, 346051, US 7869350 B1, US 7869350B1, US-B1-7869350, US7869350 B1, US7869350B1InventorsStewart Frederick Bryant, Kevin George Miles, Ian Michael Charles ShandOriginal AssigneeCisco Technology, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (95), Non-Patent Citations (29), Referenced by (1), Classifications (9), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for determining a data communication network repair strategyUS 7869350 B1Abstract A method is disclosed for determining a repair strategy for a data communication network. The data communication network has as components nodes and links. The method comprises a step of implementing a link repair strategy for an adjacent link to an adjacent node. The method further monitors for a probe packet to the adjacent node and, if such a packet is received, implements a node repair strategy.
1. A method of determining a repair strategy for a data communication network of nodes and links comprising the steps of:
at an originator node:
in response to detecting a failure in communicating with a destination node, implementing a link repair strategy by computing a first repair path around an adjacent link connected to the destination node;
creating timer period for testing the first repair path;
sending a first probe packet along the first repair path to the destination node, the first probe packet having the originator node as a source and the destination node as a destination;
monitoring for a second probe packet having the destination node as a destination, sent by the destination node in response to receiving the first probe packet from the originator node; and
in response to receiving the second probe packet, from the destination node during the timer period, forwarding data traffic to the destination node via the first repair path;
in response to not receiving the second probe packet from the destination node during the timer period, computing a second repair path around the adjacent link to the destination node;
2. A method as claimed in claim 1, wherein the received probe packet having the destination node as the destination has one of the nodes other than the destination node or the originator node as a source.
receiving a probe packet having a source node as a source and the destination node as a destination; and
looping the probe packet having a source node as a source and the destination node as a destination back to the source node.
4. A method as claimed in claim 2 further comprising:
sending a probe packet having the destination node as a destination to the source node.
monitoring for an acknowledgement to the first probe packet having the originator node as a source and the destination node as a destination; and
in response to not receiving the acknowledgement during the timer period, implementing a node repair strategy for the destination node.
6. A method as claimed in claim 5 in which the step of implementing the node repair strategy comprises implementing a node repair path.
7. A method as claimed in claim 5 in which the step of implementing the node repair strategy comprises disabling a link repair strategy.
8. A method as claimed in claim 1 in which the first probe packet having the destination node as a destination encapsulates an acknowledgement packet.
9. A non-transitory computer readable volatile or non-volatile storage medium storing one or more sequences of instructions for determining a repair strategy for a data communication network of nodes and links which instructions, when executed by one or more processors, cause the one or more processors to perform the steps of:
creating a timer period for testing the first repair path;
in response to receiving the second probe packet from the destination node during the timer period, along the first repair path from the second probe packet having the destination node as the destination, forwarding data traffic to the destination node via the first repair path;
in response to not receiving the second probe packet from the destination node during the timer period, computing a second repair path around the adjacent link to the destination node.
10. The non-transitory computer readable medium as recited in claim 9, wherein the received probe packet having the destination node as the destination has one of the nodes other than the destination node or the originator node as a source.
11. The non-transitory computer readable medium as recited in claim 9, wherein the one or more sequences of instructions further comprise instructions for:
in response to not receiving the acknowledgement during a timer period, implementing the node repair strategy for the destination node.
12. The apparatus as recited in claim 11, wherein the instructions in the non-transitory computer readable medium for implementing the node repair strategy comprise instructions for implementing a node repair path.
13. An apparatus for determining a repair strategy for a data communication network of nodes and links comprising:
means for the originator node implementing a link repair strategy by computing a first repair path around an adjacent link connected to a destination node in response to detecting a failure in communicating with the destination node;
means for the originator node creating a timer period for testing the first repair path;
means for the originator node sending a first probe packet along the first repair path to the destination node, the first probe packet having the originator node as a source and the destination node as a destination;
means for the originator node monitoring for a second probe packet having the destination node as a destination, sent by the destination node in response to receiving the first probe packet from the originator node; and
means for the originator node forwarding data traffic to the destination node via the first repair path in response to receiving the second probe packet from the destination node during the timer period, along the first repair path, the second probe packet having the destination node as the destination;
means for the originator node computing a second repair path around the adjacent link to the destination node in response to not receiving the second probe packet from the destination node during the timer period.
14. An apparatus as claimed in claim 13 wherein the received probe packet having the destination node as the destination has one of the nodes other than the destination node or the originator node as a source.
15. An apparatus as claimed in claim 14 further comprising:
means for receiving a probe packet having a source node as a source and the destination node as a destination; and
means for looping the probe packet having a source node as a source and the destination node as a destination back to the source node.
16. An apparatus as claimed in claim 14 further comprising:
means for sending a probe packet having the destination node as a destination to the source node.
17. An apparatus as claimed in claim 13 further comprising:
means for monitoring for an acknowledgement to the first probe packet having the originator node as a source and the destination node as a destination; and
means for implementing the node repair strategy for the destination node in response to is not receiving the acknowledgement during the timer period.
18. An apparatus as claimed in claim 17 in which the means for implementing the node repair strategy comprises means for implementing a node repair path.
19. An apparatus as claimed in claim 17 in which the means for implementing the node repair strategy comprises means for disabling the link repair strategy.
20. An apparatus as claimed in claim 13 in which the first probe packet having the destination node as a destination encapsulates an acknowledgement packet.
21. An apparatus for determining a repair strategy for a data communication network of nodes and links, the apparatus comprising:
a non-transitory computer readable volatile or non-volatile storage medium storing one or more sequences of instructions for determining a repair strategy for a data communication network of nodes and links, which instructions, when executed by the one or more processors, cause the one or more processors to perform the steps:
sending a first probe packet along the first repair path to the destination node from the first probe packet having the originator node as a source and the destination node as a destination;
monitoring for a second probe packet from the destination node, having the adjacent node as a destination, sent by the destination node in response to receiving the first probe packet from the originator node; and
in response to receiving the second probe packet as from the destination node during the timer period, implementing a node repair strategy for forwarding data traffic to the destination node via the first repair path;
22. The apparatus as recited in claim 21, wherein the received probe packet having the destination node as the destination has one of the nodes other than the destination node or the originator node as a source.
23. The apparatus as recited in claim 22, wherein the non-transitory computer readable medium further comprises instructions for:
receiving a probe packet having a source node as a source and the destination node as a destination; and looping the probe packet having a source node as a source and the destination node as a destination back to the source node.
24. The apparatus as recited in claim 22, wherein the non-transitory computer readable medium further comprises instructions for:
receiving a probe packet having a source node as a source and the destination node as a destination; and sending a probe packet having the destination node as a destination to the source node.
FIELD OF THE INVENTION The present invention generally relates to data communication networks. The invention relates more specifically to a method and apparatus for determining a data communication network repair strategy.
De-activation of a network component, i.e. a link or a node, either by component failure or by planned downtime, needs to be managed in order to avoid the risk of packet loss. In known systems, such de-activations cause routing transitions to take place, during which distributed routing algorithms may open up an alternative route. However such transitions can be slow, of the order of seconds before convergence and in the interim data can be lost. Although packet loss is commonly dealt with by higher level protocols that re-send packets, the inherent delays can adversely affect time critical functions such as voice and pseudo-wire traffic.
One solution for providing backup routes is described in a co-pending patent application entitled �Method and Apparatus for Constructing a Backup Route in a Data Communications Network,� Ser. No. 10/340,371 filed 9 Jan. 2003, of Clarence Filsfils et al., Attorney Docket No. 50325-0734 (�Filsfils 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 Filsfils et al., a repairing node re-computes a repair path for each adjacent component such that if component failure is detected the repair path can be instituted. The adjacent component can be a link or a node. If the adjacent component is a link then the repair path only needs to be computed to the node at the far side of the failed link from the repairing node. If the failed component is an adjacent node then a repair path must be formed to each neighbor of the failed node. Accordingly it is preferable to perform link repair, as it is simpler. Also, if an adjacent node is a �single point of failure�, i.e. it is the only node providing a path from the repairing node to some or all nodes on the network, then unless a link repair strategy can be adopted those nodes will not be reachable.
However such an approach can give rise to �forwarding loops� as can be better understood with reference to FIG. 1, which is a network diagram showing implementation of a repair strategy. The network is designated generally 10 and includes a repairing node A designated 12 an adjacent node B designated 14 and an adjacent link 16 joining nodes A and B. Node B has two further neighbor nodes, node C designated 18 and node D designated 20. Node A has an alternative route to node C via node X (designated 22) along repair path 24. The link between node C and node B is designated 26.
If node A detects a failure of an adjacent component, which can either be link 16 or node B, and assumes that it is a link failure, then it will invoke its pre-computed link repair strategy and forward data to node B via nodes X and C. If the assumption is correct and link 16 has failed then the traffic will be successfully forwarded to node B from which it can continue to its destination. However if, in fact, node B has failed then, assuming that node C is acting independently as a repairing node, it too will have invoked a repair strategy using the repair path CXAB. As a result when a packet from node A reaches node C it will be returned from node C via node A with destination node B. On receiving this packet node A will try to forward it to node C once again, thus looping the packet. This is termed a forwarding loop.
When a failure is detected by the repairing node it is not possible to determine immediately whether it is the adjacent link or the adjacent node that has failed. Accordingly a safe approach is to institute a node repair strategy as, if a link repair strategy is implemented and in fact it is the adjacent node that has failed, then data traffic will be forwarded to a failed node and lost. Although it is undesirable to set up incorrectly a link repair strategy when in fact node failure has occurred, if it is possible to adopt a link repair strategy then components on the network to which the adjacent node is a single point of failure are reachable. This can also be seen in FIG. 1. In particular node D is reachable only via node B and so, if possible, it would be desirable for node A to forward packets to node B destined for node D via path AXCB by implementing a link repair strategy.
One known approach to loop detection is described in document �A probe method in MPLS loop avoidance� by Wang Yahong (�Wang�) which is available at the time of writing on the file �draft-wang-mpls-loop-probe-00.txt� in the directory �pub/id� of the domain �watersprings.org� on the World Wide Web. The approach of Wang relates to loop detection when a next hop at a node is changed for a given destination. In that case the node sends a specific probe packet via the new next hop. If the probe packet is subsequently intercepted by the originating node then this signifies that a loop is occurring. The Wang approach recites two methods, an optimistic and a pessimistic method. In the optimistic method, if no loop is detected before a timer expires then the node assumes that the next hop path is loop free. In the pessimistic method the probe message requires an acknowledge message from a destination node. In this case if a probe packet is subsequently intercepted within a time out period or no acknowledgement message is received from the destination node in that period then a loop is assumed. If a loop is detected then an alternative repair path is attempted.
Various problems arise with the Wang approach. In particular the manner in which paths are adopted is trial and error and there is no guarantee that, if a loop is detected on the first path, similar problems will not arise on subsequently attempted paths. Furthermore, in the pessimistic method, all possible destination nodes need to be configured to recognise a probe message and return a probe acknowledgement, increasing the processing overhead and the number of routers that need to understand the loop detection protocol.
A further known approach is described in U.S. patent application Ser. No. 10/171,395, filed Jun. 12, 2002, entitled �Distinguishing Between Link and Node Failure to Facilitate Fast Reroute,� of Anna Charny et al. (Charny et al.), according to which nodes exchange RSVP hellos with neighbour nodes, such that if no response is received it is inferred that the neighbour node has failed.
FIG. 1 is a network diagram showing implementation of a repair strategy;
FIG. 2 is a flow diagram illustrating a high level review of a method for determining a repair strategy;
FIG. 3 is a flow diagram illustrating in more detail a method for determining a repair strategy;
FIG. 4 is a flow diagram illustrating the behavior of a neighbor node in a method for determining a repair strategy; and
FIG. 5 is a block diagram that illustrates a computer system upon which a method for determining a repair strategy may be implemented.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT A method and apparatus for determining a data communication network repair strategy is described. In the following description, for the purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be apparent, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.
3.0 Method of Determining a Data Communication Network Repair Strategy
The needs identified in the foregoing Background, and other needs and objects that will become apparent for the following description, are achieved in the present invention, which comprises, in one aspect, a method for determining a data communication network repair strategy for a data communications network of nodes and links. The method includes the step of implementing a link repair strategy for an adjacent link connected to an adjacent node. The method further comprises the step of monitoring for a probe packet to the adjacent node. The method further comprises the step of implementing a node repair strategy if said probe packet is received.
Returning to FIG. 1 which is a network diagram showing implementation of a repair strategy, the approach adopted can be understood with reference to FIG. 2 which is a flow diagram illustrating a high level overview of a method for determining a repair strategy. For purposes of illustrating a clear example, the process of FIG. 2 is described herein with reference to FIG. 1. However, the process of FIG. 2 is not limited to the context of FIG. 1, and may be applied to any network to solve the problems contemplated by this disclosure.
In block 50 of FIG. 2, node A of FIG. 1 detects a failure along the link 16 which may be the adjacent link 16 itself or the adjacent node, node B to which it is connected. In block 52 node A implements a link repair strategy along repair path 24 and link 26. Before any normal data packets are transmitted over the repair path 24 a loop detection packet or probe is sent along the repair path in block 54. At the same time, in block 56 a timer is started with period t. In block 58 the node monitors to see if a packet is received. If it is then a loop detection subroutine starts at block 60. If node B has not failed and is still reachable then the probe will be received by node B and an acknowledgement sent to node A. Accordingly if, in block 60, an acknowledgement is received this means that the link repair strategy is appropriate; therefore, the link repair strategy is maintained in block 62. Otherwise, at block 64 node A monitors for a return of the probe from another node (rather than an acknowledgement from node B). If this is received then this implies that the node has failed as what has actually been detected is that a packet addressed to B loops back to A. This implies that some intermediate node on the path from A to B (say C) has noticed that node B has failed and has implemented a repair strategy which involved packets addressed to B being forwarded via A. Accordingly in block 66 a node repair strategy is implemented. This node repair strategy may be to construct repair paths to all neighbors of the failed node or may be another strategy such as awaiting normal convergence. Any other packet received is forwarded as normal in block 73 and the system then checks for time out at block 68 as discussed below.
It is possible that a loop is occurring, but because of severe congestion the loop detection packet itself is lost. In this case node A will receive neither a response from node B nor a return of the probe. Accordingly at block 68, if the timer times out after time t then it is assumed that there is node failure and the node failure strategy is invoked. Otherwise the routine returns to block 58 to monitor for further packets. In an optimization, rather than assuming node failure after the timer has timed out once, the process can be repeated n successive times, for example 3 times, a probe being sent each time. If the timer expires n successive times without a response it is assumed that node B has failed. This reduces the probability of the probe detector generating a false negative and declaring a node failure, when there is only a link failure.
In a further optimization, if the failure of link 16 has been detected by node B it may have implemented its own probe. If node A identifies this in optional block 70 then it can infer that node B is alive and maintain the link repair strategy in block 62.
In a still further optimization if node A receives a probe from another node destined for node B then in block 72 it can infer once again that node B has failed (as another neighbor node is presumed to be implementing a link repair strategy such that the likelihood is that node B, rather than multiple links to node B, has failed). Accordingly in optional block 72, when such a probe packet is received, a node failure repair strategy is implemented in block 66.
Where it is detected that link repair is failing the repair path is disabled in block 66. The repair path is disabled for two reasons, first of all to stop the waste of network resource incurred by needlessly sending undeliverable packets over the network, but more significantly in order to break any loops.
As discussed above in overview, once a link repair strategy is initiated then as a first step a loop detection packet or probe is sent by the repairing node. The link repair strategy is withdrawn if the probe is looped back to the sender. In an optimization the probe is a packet addressed to node B with source address A encapsulating a second packet with source address B and destination address A. The complete packet is transmitted over the link repair path 24 to node B and is subject to repair path tunneling where necessary. In one embodiment, the probe is of the form: A B(loop detect ack B A). This has the following meaning:
(loop detect ack B A) is a loop-detection acknowledgement message addressed from B to A. This is sent by B, to indicate that it has received A's loop detection message and that B is alive.
A B(loop detect ack B A) is therefore B's loop-detection acknowledgement message encapsulated in a packet addressed from A to B.
As a result a simple protocol is adopted which does not require formulation of a specific acknowledgement packet. Instead, if node B is still reachable, the probe is received by node B, decapsulated and the inner packet returned to A.
FIG. 3 is a flow diagram illustrating in more detail a method for determining a repair strategy. In block 80 a repairing node first detects a failure and in block 82 implements a link repair strategy as discussed in more detail above. In block 84 node A first sends a probe packet. In one embodiment, the probe packet is in the form A B(loop detect ack B A). By transmitting the first loop detecting packet in advance of any other data, the probability of congestion loss is minimized.
In block 85 a timer is started with time t, as discussed above. The repairing node A then monitors for receipt of the message (loop detect ack B A) in block 86. If this is received then node B is alive and the link repair strategy is maintained at block 88.
If the link 16 has indeed failed, then node B may be probing to see if node A is alive. Accordingly, in block 90 node A further monitors for a packet B A(loop detect ack A B), i.e. the probe packet from node B. If the probe packet from node B is received, then in block 88 the link repair strategy is maintained in block 88.
If A does not get a response before t expires in block 92, it resends the probe to node B at block 84 and restarts the timer at block 85. If the timer has timed out then, in block 94, if n, for example 3, attempts have failed then A assumes that B has failed, disables the link repair strategy and implements the node repair strategy in block 96. Appropriate strategies are discussed in more detail below. Otherwise the procedure is repeated, and the probe message is resent in block 84.
In an optimization the probes are issued periodically during normal data traffic via the repair path 42 in case B is in the process of failing.
As discussed above, in block 88, if the repairing node A determines that node B is alive it maintains the link repair strategy.
It will be seen, therefore, that the approach of FIG. 3 allows implementation of an appropriate repair strategy also taking into account additional factors. In some instances even though B is alive the repair path is disabled, principally when the timer times out.
Where node B has in fact failed, then in a further optimization the method makes use of other neighbor nodes of the failed node, in the current embodiment, node C (designated 18 in FIG. 1). This can be illustrated by considering various possible cases.
In a first case where node B has failed, node C is not aware of failure of the node B, nor of the link 26 between them. This case can be understood with reference to FIG. 4, which is a flow diagram illustrating the behavior of a neighbor node in a method for determining a repair strategy.
In block 108 it is assumed that C has not detected the failure. In block 110 node C receives the probe packet from node A destined to node B. In one embodiment, the probe packet is in the form A B(loop detect ack B A). In block 112 node C forwards the probe message to B as it does any other traffic to B. The message is discarded. There is no packet looping and the traffic volumes everywhere are the same as if B were functional. Eventually in block 114 at node A the timer at time nt expires and, as discussed above, in block 96 in FIG. 3 node A removes the link repair path in relation to the traffic to node D (designated 20) via node C.
In the second case node C has detected the failure as represented by block 116. In block 117 node C originates a probe. In block 118, node C monitors for the probe and if it receives it then a loop is occurring and the node repair strategy is implemented and the link repair strategy disabled in block 120. In block 122 if node C receives a packet from another originator destined for node B (or more generally for the repair target of a link repair strategy that it is currently implementing) then there is the risk of the probe packet being looped back to its originator as discussed in more detail above.
One approach to dealing with this is simply to forward the packet as normal, in which case the probe packet will be received once again by the originator, which will detect a loop and take the necessary steps as discussed above. This is shown in block 124.
Alternatively, at block 128 node C can send its own probe to node B via the originator node (in this case, node A) of the received probe packet. As discussed above in block 72 in FIG. 2, such a probe packet is received by the originator node and recognized as designating a loop such that the originator implements the appropriate strategy. The preferred implementation is that described with reference to block 124, as this is less likely to trigger successive responses between nodes A and C. In one embodiment, to avoid the risk of repeat messages triggered between the nodes, node C sends its probe as soon as it has modified its routing table entry for node B but not before, and when about to tear down the repair path should start with the entry that points to node B.
Of course when other traffic is received then the packet should be forwarded as normal over the regular forwarding path or the appropriate repair path as designated by block 130.
It will be appreciated that the method discussed above can be implemented on all nodes or on a sub-set of nodes, in the case for example of asymmetric routing. Accordingly, in one embodiment it is sufficient for a node merely to monitor for probe traffic between itself and the potentially failed node. Alternatively the repairing node can also monitor for appropriate traffic from the neighbor nodes to the potentially failed node.
Where a loop is detected as a result of node failure, the appropriate repair strategy subsequently can be dependent on various factors. As examples, two particular cases are now considered.
Firstly where node B is a single point of failure for all traffic assigned to the link repair path, that is to say, the only traffic assigned to the link repair path is for destinations reachable only via B, all these destinations will be unreachable even after normal convergence has completed. Accordingly having made use of the link repair path will not have made matters worse in terms of packet delivery, but continued looping is undesirable in any event. Accordingly the repair path is withdrawn and packets discarded at node A.
In the second case some traffic is assigned to the link repair path because it is not possible to compute a repair path to a neighbor of node B, for example because the underlying repair path strategy is unable to compute an appropriate path. After normal convergence these destinations will be reachable but in the meantime packets directed to them will loop as discussed above. Accordingly, in this event, normal convergence is immediately initiated in the appropriate manner.
In other cases a pre-determined node repair strategy can be adopted as soon as it is inferred that node B has failed. In order to break any loops in the meantime any appropriate approach can be adopted. For example the repairing node can delete from its forwarding information base (FIB) all prefixes that have a normal next-hop equal to the destination address of the loop-detection packet (i.e. the failed node) and also flush the loop-detect packet.
The mechanism by which the repair paths are stored and implemented and the detection, monitoring and forwarding of probes and other data packets will be apparent to the skilled reader such that a detailed description is not required here. Although any appropriate protocol can be adopted, assigning the loop discovery protocol an IP protocol type will make packet discrimination in the repair path easier, and for the specific probe form discussed above a packet protocol that supports tunneling is required.
FIG. 5 is a block diagram that illustrates a computer system 140 upon which the method may be implemented. The method is implemented using one or more computer programs miming on a network element such as a router device. Thus, in this embodiment, the computer system 140 is a router.
The computer system 140 implements as a router acting as a repairing node the above described method of determining a repair strategy or a link 159 or the router 160 connected to it comprises the adjacent component. The implementation is provided by computer system 140 in response to processor 144 executing one or more sequences of one or more instructions contained in main memory 146. Such instructions may be read into main memory 146 from another computer-readable medium, such as storage device 150. Execution of the sequences of instructions contained in main memory 146 causes processor 144 to perform the process steps described herein. One or more processors in a multi-processing arrangement may also be employed to execute the sequences of instructions contained in main memory 146. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention are not limited to any specific combination of hardware circuitry and software.
The network link typically provides data communication through one or more networks to other data devices. For example, the network link may provide a connection through a local network to a host computer or to data equipment operated by an Internet Service Provider (ISP). The ISP in turn provides data communication services through the world wide packet data communication network now commonly referred to as the �Internet�.
Computer system 140 can send messages and receive data, including program code, through the network(s), network link and interface 159. In the Internet example, a server might transmit a requested code for an application program through the Internet, ISP, local network and communication interface 158. In accordance with the invention, one such downloaded application provides for the method as described herein.
Any appropriate routing protocol and mechanism can be adopted to implement the invention. The method step set out can be carried out in any appropriate order and aspects from the examples and embodiments described juxtaposed or interchanged as appropriate.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4956835 *Oct 19, 1988Sep 11, 1990Alberta Telecommunications Research CentreMethod and apparatus for self-restoring and self-provisioning communication networksUS5243592Oct 15, 1990Sep 7, 1993Digital Equipment CorporationMethod and apparatus for distance vector routing on datagram point-to-point linksUS5253248Jul 3, 1990Oct 12, 1993At&T Bell LaboratoriesCongestion control for connectionless traffic in data networks via alternate routingUS5825772Apr 2, 1996Oct 20, 1998Cabletron Systems, Inc.Distributed connection-oriented services for switched communications networksUS5959968Jul 30, 1997Sep 28, 1999Cisco Systems, Inc.Port aggregation protocolUS5999286 *Jan 9, 1997Dec 7, 1999AlcatelMethod and system for restoring a distributed telecommunications networkUS6002674Jun 27, 1997Dec 14, 1999Oki Electric Industry Co., Ltd.Network control system which uses two timers and updates routing informationUS6032194Dec 24, 1997Feb 29, 2000Cisco Technology, Inc.Method and apparatus for rapidly reconfiguring computer networksUS6044075Dec 15, 1994Mar 28, 2000International Business Machines CorporationApparatus and method for routing a communication in a networkUS6098107Oct 31, 1997Aug 1, 2000Lucent Technologies Inc.Dynamic algorithms for shortest path tree computationUS6111257Nov 21, 1997Aug 29, 2000Picker International, Inc.Support assembly for scintillating crystalUS6128750Jun 26, 1998Oct 3, 2000Emc CorporationFail-over switching systemUS6148410 *Sep 15, 1997Nov 14, 2000International Business Machines CorporationFault tolerant recoverable TCP/IP connection routerUS6185598Feb 10, 1998Feb 6, 2001Digital Island, Inc.Optimized network resource locationUS6243754Jan 8, 1999Jun 5, 2001International Business Machines CorporationDynamic selection of network providersUS6246669 *Nov 17, 1998Jun 12, 2001Cisco Technology, Inc.Method and system for optimizing connection set-up operations in a high speed digital networkUS6256295Sep 25, 1997Jul 3, 2001Nortel Networks LimitedMethod and apparatus for determining multiple minimally-overlapping paths between nodes in a networkUS6295275Aug 19, 1998Sep 25, 2001Mci Communications CorporationDynamic route generation for real-time network restoration using pre-plan route generation methodologyUS6321271Dec 22, 1998Nov 20, 2001Lucent Technologies Inc.Constrained shortest path routing methodUS6343122Jun 28, 1996Jan 29, 2002Telefonaktiebolaget L M EricssonMethod and apparatus for routing traffic in a circuit-switched networkUS6347078Aug 11, 1998Feb 12, 2002Lucent Technologies Inc.Multiple path routingUS6349091Nov 7, 2000Feb 19, 2002Itt Manufacturing Enterprises, Inc.Method and apparatus for controlling communication links between network nodes to reduce communication protocol overhead trafficUS6356546Aug 11, 1998Mar 12, 2002Nortel Networks LimitedUniversal transfer method and network with distributed switchUS6389764Feb 24, 1999May 21, 2002Freyssinet International (Stup)Method for making prefabricated structural elements, and prestressed structure produced with the structuralUS6473421Mar 29, 1999Oct 29, 2002Cisco Technology, Inc.Hierarchical label switching across multiple OSPF areasUS6507577Nov 12, 1998Jan 14, 2003Nortel Networks LimitedVoice over internet protocol network architectureUS6535481Aug 20, 1999Mar 18, 2003Nortel Networks LimitedNetwork data routing protection cycles for automatic protection switchingUS6578086Sep 27, 1999Jun 10, 2003Nortel Networks LimitedDynamically managing the topology of a data networkUS6668282Aug 2, 2000Dec 23, 2003International Business Machines CorporationSystem and method to monitor and determine if an active IPSec tunnel has become disabledUS6690671Aug 17, 1998Feb 10, 2004Marconi Communications, Inc.Load balanced UBR routing in ATM networksUS6697325Dec 7, 1999Feb 24, 2004Nortel Networks LimitedSystem, device, and method for expediting reconvergence in a communication networkUS6704320Mar 24, 1999Mar 9, 2004Lucent Technologies Inc.Dynamic algorithm for determining a shortest path tree between network nodesUS6711125Aug 2, 1999Mar 23, 2004Extreme NetworksProvisioning networks for reliable quality of serviceUS6714551Jul 19, 2000Mar 30, 2004Alvarion Israel (2003) Ltd.Method and apparatus for maintaining a predefined transmission quality in a wireless network for a metropolitan areaUS6718382 *Feb 11, 1999Apr 6, 2004Yunzhou LiTechnique for detecting leaky points within a network protocol domainUS6778531Sep 29, 2000Aug 17, 2004Lucent Technologies Inc.Multicast routing with service-level guarantees between ingress egress-points in a packet networkUS6829215Mar 27, 2001Dec 7, 2004Marconi Intellectual Property (Ringfence) Inc.IP multi-homingUS6928484Jan 18, 2000Aug 9, 2005Cisco Technology, Inc.Method and apparatus for discovering edge-disjoint shortest path pairs during shortest path tree computationUS6944131Dec 30, 2003Sep 13, 2005Nortel Networks LimitedState information and routing table updates in large scale data networksUS6950870 *Feb 6, 2002Sep 27, 2005Harris CorporationMethod and apparatus for loop detection and dissolution in a communication networkUS6982951Jul 19, 2001Jan 3, 2006At&T Corp.Method for selecting a restoration path in a mesh networkUS6996065Jul 5, 2001Feb 7, 2006Lucent Technologies Inc.Dynamic backup routing of network tunnel paths for local restoration in a packet networkUS7058016Oct 12, 2000Jun 6, 2006Cisco Technology, Inc.Method and system for accelerating route calculation in link state routing protocolsUS7099286May 22, 2002Aug 29, 2006Cisco Technology, Inc.Method and system for finding shared risk diverse pathsUS7113481Nov 29, 2001Sep 26, 2006AlcatelInformed dynamic path protection for optical networksUS7158486Mar 12, 2002Jan 2, 2007Opcoast LlcMethod and system for fast computation of routes under multiple network states with communication continuationUS7177295Mar 8, 2002Feb 13, 2007Scientific Research CorporationWireless routing protocol for ad-hoc networksUS7242664May 30, 2002Jul 10, 2007Lucent Technologies Inc.Hybrid protection using mesh restoration and 1:1 protectionUS7260645 *Apr 26, 2002Aug 21, 2007Proficient Networks, Inc.Methods, apparatuses and systems facilitating determination of network path metricsUS7274654Jun 20, 2002Sep 25, 2007Electronics And Telecommunications Research InstituteMethod for sharing backup path in MPLS network, label switching router for setting up backup in MPLS network, and system thereforUS7274658Mar 1, 2002Sep 25, 2007Akamai Technologies, Inc.Optimal route selection in a content delivery networkUS7349427Aug 21, 2002Mar 25, 2008Nortel Networks LimitedRouting method and apparatus for optimising auto-tunnelling in a heterogeneous networkUS7420989Sep 30, 2004Sep 2, 2008Lucent Technologies Inc.Technique for identifying backup path for shared mesh protectionUS7490165Jul 18, 2001Feb 10, 2009Cisco Technology, Inc.Method and apparatus for computing a path in a system with nodal and link diverse constraintsUS20020021671 *Aug 8, 2001Feb 21, 20023Com CorporationDiagnosis of link failures in a networkUS20020037010Sep 5, 2001Mar 28, 2002Nec CorporationMPLS-VPN service networkUS20020062388 *Dec 1, 2000May 23, 2002Ogier Richard G.System and method for disseminating topology and link-state information to routing nodes in a mobile ad hoc networkUS20020093954Jul 2, 2001Jul 18, 2002Jon WeilFailure protection in a communications networkUS20020112072Feb 7, 2002Aug 15, 2002Maple Optical Systems, Inc.System and method for fast-rerouting of data in a data communication networkUS20020116669 *Feb 7, 2002Aug 22, 2002Maple Optical Systems, Inc.System and method for fault notification in a data communication networkUS20020131362Mar 16, 2001Sep 19, 2002Ross CallonNetwork routing using link failure informationUS20020136223Dec 19, 2000Sep 26, 2002Ho Ka K.Method and apparatus for interworking PNNI with the signalling and routing protocols used in MPLS networksUS20020171886Mar 4, 2002Nov 21, 2002Quansheng WuAutomatic control plane recovery for agile optical networksUS20020172157Mar 12, 2002Nov 21, 2002Rhodes David L.Method and system for fast computation of routes under multiple network states with communication continuationUS20030063613Sep 28, 2001Apr 3, 2003Carpini Walter JosephLabel switched communication network and system and method for path restorationUS20030079040Oct 19, 2001Apr 24, 2003Nitin JainMethod and system for intelligently forwarding multicast packetsUS20030117950Dec 26, 2001Jun 26, 2003Huang Gail GLink redial for mesh protectionUS20030123457Dec 27, 2001Jul 3, 2003Koppol Pramod V.N.Apparatus and method for distributed software implementation of OSPF protocolUS20030193958Apr 11, 2002Oct 16, 2003Vidya NarayananMethods for providing rendezvous point router redundancy in sparse mode multicast networksUS20030193959Jul 26, 2002Oct 16, 2003General Instrument CorporationMethod and apparatus for priority-based load balancing for use in an extended local area networkUS20030210705 *May 12, 2003Nov 13, 2003Nabil SeddighSystem and method for distributed resource reservation protocol-traffic engineering (RSVP-TE) hitless restart in multi-protocol label switching (MPLS) networkUS20040001497Jun 27, 2002Jan 1, 2004Nokia, Inc.Dynamic routing over secure networksUS20040001508Jun 28, 2002Jan 1, 2004Haihong ZhengMethod and system for transmitting data in a packet based communication networkUS20040071089Nov 12, 2001Apr 15, 2004Daniel BauerCosts in data networksUS20040085894Dec 20, 2002May 6, 2004Linghsiao WangApparatus for link failure detection on high availability Ethernet backplaneUS20040117251Dec 17, 2002Jun 17, 2004Charles Shand Ian MichaelMethod and apparatus for advertising a link cost in a data communications networkUS20040151181Feb 4, 2003Aug 5, 2004Chu Thomas P.Methods and systems for providing MPLS-based layer-2 virtual private network servicesUS20050007950Jul 7, 2003Jan 13, 2005Liu Hua AutumnMethods and devices for creating an alternate path for a bi-directional LSPUS20050013241Jul 8, 2004Jan 20, 2005AlcatelNetwork restorationUS20050031339Jul 9, 2004Feb 10, 2005Chumning QiaoEfficient trap avoidance and shared protection method in survivable networks with shared risk link groups and a survivable networkUS20050038909Jun 6, 2003Feb 17, 2005Harumine YoshibaStatic dense multicast path and bandwidth managementUS20050071709Sep 30, 2003Mar 31, 2005Rosenstock Harold N.InfiniBand architecture subnet derived database elementsUS20050097219Oct 7, 2003May 5, 2005Cisco Technology, Inc.Enhanced switchover for MPLS fast rerouteUS20050265228Jul 25, 2005Dec 1, 2005Fredette Andre NAutomatic protection switching using link-level redundancy supporting multi-protocol label switchingUS20060018253Jul 23, 2004Jan 26, 2006Windisch Kurt JSystem and method for preserving multicast data forwarding during control failures in a routerUS20060221962Apr 5, 2005Oct 5, 2006Stefano PrevidiMulticast routing over unidirectional linksUS20060291446Nov 9, 2005Dec 28, 2006Donald CaldwellSystems, methods, and devices for managing routingUS20070011284Feb 17, 2003Jan 11, 2007France Telecom SaDynamic distributed method for local protection of a label switching pathUS20070011351Jul 7, 2006Jan 11, 2007Aurelien BrunoMethod and system for gateway selection in inter-region communication on IP networksUS20070038767Jan 9, 2003Feb 15, 2007Miles Kevin GMethod and apparatus for constructing a backup route in a data communications networkUS20080025203Jul 25, 2006Jan 31, 2008Francois TalletAlternate spanning tree for faster indirect link failure recoveryUS20080089227Oct 11, 2006Apr 17, 2008Jim GuichardProtecting multi-segment pseudowiresCN1440159AMar 31, 2003Sep 3, 2003中国科学院计算机网络信息中心Control method for layered switching network node regionWO2001078278A1Apr 10, 2001Oct 18, 2001Genuity IncRadio network routing apparatusWO2002006918A2Jun 6, 2001Jan 24, 2002Telcordia Tech IncA method, system, and product for preventing data loss and forwarding loops when conducting a scheduled change to the topology of a link-state routing protocol network* Cited by examinerNon-Patent CitationsReference1AU Examiner's First Report for foreign patent application No. 2004311004 dated Jun. 23, 2008 (1 pg).2AU Examiner's Second Report for foreign patent application No. 2004311004 dated Aug. 18, 2008 (1 pg).3Claims, application No. EP 04795045, 4 pages.4CLAIMS, application No. EP 04812468, 4 pages.5Claims, application No. EP 06720965, 4 pages.6Claims, filing No. 200680001652.0, 4 pages.7Claims, international application No. PCT/US06/28083, 3 pages.8Current claims for AU foreign patent application No. 2004311004 (6 pgs).9Current claims for CN foreign patent application No. 200480033007.8 (6 pgs).10Current Claims, Application No. 04795045.6-2416, 5 pages.11Current Claims, PCT/US04/33827, 6 pages.12European Patent Office, "Communication pursuant to Article 94(3) EPC", Application No. 04795045.6-2416, dated Sep. 7, 2009, 5 pages.13European Patent Office, "Supplementary European Search Report", application No. EP 04795045, May 27, 2009, 4 pages.14European Patent Office, "Supplementary European Search Report", application No. EP 06720965, dated Jul. 21, 2009, 6 pages.15European Patent Office, "Supplementary Search Report", application No. EP 04812468, dated May 27, 2010, 4 pages.16 *http://en.wikipedia.org/wiki/IP-protocol, Oct. 28, 2006.17 *http://en.wikipedia.org/wiki/IP�protocol, Oct. 28, 2006.18 *http://en.wikipedia.org/wiki/Ping, Jan. 17, 2007.19International Searching Authority, "Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration", international application No. PCT/US06/28083, Received Nov. 30, 2007, 11 pages.20International Searching Authority, International Search Report, PCT/US04/33827, dated Mar. 28, 2005, 8 pages.21Mikkel Thorup, "Fortifying OSPF/IS-IS against link-failure," Sep. 7, 2001, pp. 1-10.22Moy, J et al., "OSPF Version 2", IETF Standard, Network Working Group, Internet Engineering Task Force, IETF, Apr. 1998, XP015008112, NFC 2328, 245 pages.23Notification of Transmittal of the International Search Report and the Written Opinion of the International Searching Authority, or the Declaration as received in corresponding International application No. PCT/US06/06238.24Office Action from CN for foreign application No. 200480033007.8 dated Apr. 11, 2008 (10 pgs) with English translation (11 pgs).25Pending claims in PCT/US06/06238.26Raju et al., "A New Approach to On-Demand Loop-Free Multipath Routing", Computer Communications and Networks, 1999, IEEE, Oct. 1999, XP010359531, ISBN: 978-0-7803-5794-5, 6 pages.27State Intellectual Property Office of the People'S Republic of China, "The First Office Action", filing No. 200680001652.0, May 8, 2009, 15 pages.28U.S. Appl. No. 10/719,003, filed Nov. 21, 2003, Office Action Mailing Date May 9, 2007.29Wang, Zheng et al., "Shortest Path First with Emergency Exits," ACM 089791-405-8/90/0009/0166, 1990, pp. 166-176.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8484163 *Dec 16, 2010Jul 9, 2013Netapp, Inc.Cluster configuration backup and recovery* Cited by examinerClassifications U.S. Classification370/228, 242/225, 242/248International ClassificationH04J1/16Cooperative ClassificationH04L43/10, H04L41/0654European ClassificationH04L12/24D3, H04L43/10, H04L41/06CLegal EventsDateCodeEventDescriptionJan 15, 2003ASAssignmentEffective date: 20030109Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:BRYANT, STEWART FREDERICK;MILES, KEVIN GEORGE;MICHAEL, IAN;AND OTHERS;REEL/FRAME:013670/0608Owner name: CISCO TECHNOLOGY, CALIFORNIARotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google