Quasi-deterministic gateway selection algorithm for multi-domain source routed networks

Abstract

A system and a method of selecting gateways using stored metrics associated with each route out of the domain and with each destination is presented. The metrics represent some measure to be minimized by the routing system, such as cost or delay. The route is selected quasi-deterministically. A first selection is made deterministically based on the stored metrics in order to attempt to use the optimum path. If a connection can not be established through the deterministically selected gateway, an alternate gateway is selected randomly from among the remaining gateways capable of reaching the destination at a reasonable cost.

We claim:  
     
         1 . A method for a node to select a gateway from among at least two gateways, comprising the steps of: 
 storing information associating a metric with each gateway with respect to each of one or more destinations;    upon receiving a connection request to a destination, the further steps of: 
 i) deterministically selecting a first gateway having an optimum metric with respect to the destination,  
 ii) sending a connection request to the first gateway,  
 iii) if a connection can not be established to the destination via the first gateway, randomly selecting a second gateway from among the gateways other than the first gateway, and  
 iv) sending a connection request to the second gateway.  
   
     
     
         2 . The method of  claim 1  wherein the connection request contains zero or more identifiers identifying domains through which the connection route has already passed, the step of deterministically selecting a first gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request, and the step of randomly selecting a second gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         3 . The method of  claim 1  wherein if more than one gateway have the optimum metric with respect to the destination, the step of deterministically selecting a first gateway randomly selects the first gateway from among the gateways having the optimum metric.  
     
     
         4 . The method of  claim 1  wherein the step of randomly selecting a second gateway applies a weighting factor to each gateway, the weighting factor taking into account the metric of each gateway with respect to the destination.  
     
     
         5 . The method of  claim 1  wherein the step of randomly selecting a second gateway is further limited to the gateways whose metric with respect to the destination is within a preset range.  
     
     
         6 . The method of  claim 1  wherein the step of randomly selecting a second gateway is repeated if a connection can not be established via the second gateway first selected randomly, and the selection is limited to the gateways through which a connection has not already been attempted.  
     
     
         7 . The method of  claim 1  wherein the step of deterministically selecting a first gateway is repeated if a connection can not be established via the first gateway first selected deterministically, and the selection is limited to the gateways through which a connection has not already been attempted.  
     
     
         8 . The method of  claim 3  wherein the connection request contains zero or more identifiers identifying domains through which the connection route has already passed, the step of deterministically selecting a first gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request, and the step of randomly selecting a second gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         9 . The method of  claim 4  wherein the connection request contains zero or more identifiers identifying domains through which the connection route has already passed, the step of deterministically selecting a first gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request, and the step of randomly selecting a second gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         10 . The method of  claim 5  wherein the connection request contains zero or more identifiers identifying domains through which the connection route has already passed, the step of deterministically selecting a first gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request, and the step of randomly selecting a second gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         11 . The method of  claim 6  wherein the connection request contains zero or more identifiers identifying domains through which the connection route has already passed, the step of deterministically selecting a first gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request, and the step of randomly selecting a second gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         12 . The method of  claim 7  wherein the connection request contains zero or more identifiers identifying domains through which the connection route has already passed, the step of deterministically selecting a first gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request, and the step of randomly selecting a second gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         13 . The method of  claim 1  wherein the metric represents an approximation to a cost of reaching the destination with which the metric is associated through the gateway with which the metric is associated.  
     
     
         14 . The method of  claim 1  wherein the metric represents an approximation to the delay that would be experienced by a user if the connection route was established to the destination with which the metric is associated through the gateway with which the metric is associated.  
     
     
         15 . The method of  claim 1  wherein the metric represents an approximation to the number of domains through which the connection route would pass in reaching the destination with which the metric is associated through the gateway with which the metric is associated.  
     
     
         16 . In a communication network containing a plurality of domains, electronic hardware for use in a node in a domain, the electronic hardware containing circuitry for carrying out steps to select a gateway, the domain having at least two gateways, the node having stored information associating a metric with each gateway with respect to each of one or more destinations, and the steps comprising the steps of: 
 deterministically selecting a first gateway having an optimum metric with respect to a destination,    sending a connection request to the first gateway,    if a connection can not be established to the destination via the first gateway, randomly selecting a second gateway from among the gateways other than the first gateway, and    sending a connection request to the second gateway.    
     
     
         17 . The electronic hardware of  claim 16  wherein the circuitry selects a gateway upon receiving a connection request, the connection request containing zero or more identifiers identifying domains through which the connection route has already passed, the step of deterministically selecting a first gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request, and the step of randomly selecting a second gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         18 . A node comprising: 
 memory for storing information associating a metric with each of one or more gateways with respect to each of one or more destinations reachable through the respective gateways,    means for launching a connection request to a selected gateway,    means for selecting the selected gateway which deterministically selects a first gateway having an optimum metric with respect to a destination, and if a connection can not be established to the destination via the first gateway, randomly selects a second gateway from among the gateways other than the first gateway.    
     
     
         19 . The node of  claim 18  wherein the means for selecting the selected gateway selects a first gateway upon receiving a connection request, the connection request containing zero or more identifiers identifying domains through which the connection route has already passed, and the means for selecting the selected gateway does not select a gateway leading to a domain indicated by the identifiers in the connection request.  
     
     
         20 . A method for making a routing decision in a communication network, comprising the steps of: 
 deterministically making a first routing decision, and    if a connection can not be established, randomly making a second routing decision.