Rapid response method for the failure of links between different routing domains

Abstract

The invention relates to a rapid response method for the failure of a link between two routing domains in a packet-oriented network. Once the failure of a link has been identified, substitute routes are provided for the interrupted routes by the local selection of alternative routes and by the propagation of messages along the substitute routes. In contrast to conventional inter-domain protocols such as the BGP (Iborder gateway protocol) the transmission of messages and the associated modification to the routing only involves routing domains that lie along the replacement routes. In one embodiment, a network-wide propagation of messages takes place if the failure of the link represents a persistent breakdown. As a consequence, optimal routes are re-determined in the entire network. The invention provides breakdown compensation that is appropriate for temporary breakdowns and prevents instabilities that occur as a result of the use of conventional inter-domain protocols.

1 - 11 . (canceled)  
     
     
         12 . A method for rapidly responding to the failure of a link between two routing domains in a packet-oriented network, comprising: 
 detecting the failure of the link by one of the routing domains; and    providing at least one substitute route to a destination point for at least one route to the destination point, which passes via the failed link, wherein    a message about the link failure is propagated only along the at least one substitute route, by means of which routing domains lying along the substitute route are notified, and wherein    routing domains which have been notified and which lie along the at least one substitute route adjust their inter-domain routing to give a routing to the destination point along the at least one substitute route, until all the routing domains on the at least one substitute route have adjusted their inter-domain routing to give a routing to the destination point along the at least one substitute route.    
     
     
         13 . The method in accordance with  claim 12 , further comprising: 
 notifying a router in a routing domain about the link failure;    selecting an alternative route to the route which passes via the failed link, which does not pass via the failed link by the router;    specifying an address of a router in the next routing domain on the alternative route as the next destination for the inter-domain routing to the destination point; and    sending a message to the next routing domain on the alternative route, notifying the next routing domain about the link failure.    
     
     
         14 . The method in accordance with  claim 12 , wherein 
 a router in a routing domain is notified about the link failure, wherein    for a route which passes via the failed link, the router checks whether a substitute route has already been set up, and wherein,    if there is such a substitute route, no message about the link failure will be sent to the next routing domain on the substitute route.    
     
     
         15 . The method in accordance with  claim 13 , wherein 
 a router in a routing domain is notified about the link failure, wherein    for a route which passes via the failed link, the router checks whether a substitute route has already been set up, and wherein,    if there is such a substitute route, no message about the link failure will be sent to the next routing domain on the substitute route.    
     
     
         16 . The method in accordance with  claim 12 , wherein 
 a router in a routing domain is notified about the link failure, wherein    for each of the routes which pass via the failed link, the router selects alternative routes which do not pass via the failed link, and wherein    the address of a router belonging to the next routing domain along the alternative route concerned is determined as the next destination for the inter-domain routing to the destination point of the route concerned which has failed.    
     
     
         17 . The method in accordance with  claim 13 , wherein 
 a router in a routing domain is notified about the link failure, wherein    for each of the routes which pass via the failed link, the router selects alternative routes which do not pass via the failed link, and wherein    the address of a router belonging to the next routing domain along the alternative route concerned is determined as the next destination for the inter-domain routing to the destination point of the route concerned which has failed.    
     
     
         18 . The method in accordance with  claim 14 , wherein 
 a router in a routing domain is notified about the link failure, wherein    for each of the routes which pass via the failed link, the router selects alternative routes which do not pass via the failed link, and wherein    the address of a router belonging to the next routing domain along the alternative route concerned is determined as the next destination for the inter-domain routing to the destination point of the route concerned which has failed.    
     
     
         19 . The method in accordance with  claim 12 , wherein 
 a router selects more than one alternative route to a route which passes via the failed link, such that the selected alternative routes do not pass via the failed link, and wherein    an address of a router which belongs to the next routing domain on an alternative route is determined as the next destination for the routing to the destination point of the failed link and for at least one second alternative route the address of a router which belongs to the next routing domain on the second alternative route is determined as the alternative next destination for the inter-domain routing to the destination point.    
     
     
         20 . The method in accordance with  claim 13 , wherein 
 a router selects more than one alternative route to a route which passes via the failed link, such that the selected alternative routes do not pass via the failed link, and wherein    an address of a router which belongs to the next routing domain on an alternative route is determined as the next destination for the routing to the destination point of the failed link and for at least one second alternative route the address of a router which belongs to the next routing domain on the second alternative route is determined as the alternative next destination for the inter-domain routing to the destination point.    
     
     
         21 . The method in accordance with  claim 14 , wherein 
 a router selects more than one alternative route to a route which passes via the failed link, such that the selected alternative routes do not pass via the failed link, and wherein    an address of a router which belongs to the next routing domain on an alternative route is determined as the next destination for the routing to the destination point of the failed link and for at least one second alternative route the address of a router which belongs to the next routing domain on the second alternative route is determined as the alternative next destination for the inter-domain routing to the destination point.    
     
     
         22 . The method in accordance with  claim 16 , wherein 
 a router selects more than one alternative route to a route which passes via the failed link, such that the selected alternative routes do not pass via the failed link, and wherein    an address of a router which belongs to the next routing domain on an alternative route is determined as the next destination for the routing to the destination point of the failed link and for at least one second alternative route the address of a router which belongs to the next routing domain on the second alternative route is determined as the alternative next destination for the inter-domain routing to the destination point.    
     
     
         23 . The method in accordance with  claim 12 , wherein 
 a router selects more than one alternative route to a route which passes via the failed link, whereby the selected alternative routes do not pass via the failed link, wherein    an address of a router which belongs to the next routing domain on a first alternative route is determined as the next destination for the routing to the destination point of the route which passes via the failed link, and for at least one second alternative route the address of a router which belongs to the next routing domain on the second alternative route is also determined as the next destination for the inter-domain routing to the destination point, and wherein    for inter-domain routing over a substitute route for the route which passes via the failed link, the next destination is determined by reference to parameters which relate to data packets.    
     
     
         24 . The method in accordance with  claim 13 , wherein 
 a router selects more than one alternative route to a route which passes via the failed link, whereby the selected alternative routes do not pass via the failed link, wherein    an address of a router which belongs to the next routing domain on a first alternative route is determined as the next destination for the routing to the destination point of the route which passes via the failed link, and for at least one second alternative route the address of a router which belongs to the next routing domain on the second alternative route is also determined as the next destination for the inter-domain routing to the destination point, and wherein    for inter-domain routing over a substitute route for the route which passes via the failed link, the next destination is determined by reference to parameters which relate to data packets.    
     
     
         25 . The method in accordance with  claim 12 , further comprising: 
 providing a protocol which provides a network-wide propagation of messages for determining or calculating optimal routes, wherein,    after a link failure, any redetermination of the optimal routes for inter-domain routing to take into account the link failure is suppressed for a time period by the protocol.    
     
     
         26 . The method in accordance with  claim 25 , wherein, after the time period has expired, a network-wide propagation of messages for the determination of optimal routes for inter-domain routing is then undertaken if the link failure is still extant.  
     
     
         27 . The method in accordance with  claim 25 , wherein the protocol used for the redetermination of optimal routes is the Border Gateway Protocol (BGP) protocol.  
     
     
         28 . The method in accordance with  claim 12 , wherein a route which has been replaced by an alternative route is marked with respect to its possible reconnection or restoration to service.  
     
     
         29 . A router comprising mechanisms for carrying out the method of the  claim 12.