Abstract:
A routing method for a network burdens the network with less routing messages. According to said method, routing hellos for calculating the link metrics are used. The method thus removes the need for metric beacons.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application is based on and hereby claims priority to German Application No. 10 2006 014 911.3 filed on Mar. 30, 2006 and PCT Application No. PCT/EP2007/050798 filed on Jan. 26, 2007, the contents of which are hereby incorporated by reference. 
     
    
     BACKGROUND OF THE INVENTION 
       [0002]    The invention relates to a method for determining a path in a network and a quality value for the path and a network node. 
         [0003]    A network allows the routing of messages between its network nodes. However in a network not all the network nodes of the network are connected directly to all the further network nodes. A message from a sending network node to a receiving network node must therefore generally be forwarded by way of one or more intermediate nodes, to get from the sending network node to the receiving network node. The journey from the sending network node by way of the intermediate nodes to the receiving network node is hereby known as the path or route. 
         [0004]    In order to select a suitable path for a message from a large number of theoretically possible paths in the network, a routing method is used in conjunction with a routing metric. 
         [0005]    The routing method first determines at least one but expediently a plurality of candidate paths, along which the message could be routed. 
         [0006]    A path distance value or so-called route metric is assigned to the candidate paths by the routing metric. The path distance value is a measure of the quality of a candidate path. The path distance value in turn can be determined from link distance values for example, which in turn are a measure of the quality of individual links of the respective candidate path. The direct connection between two network nodes of the network is referred to as a link here. A known routing method is for example AODV (Ad-hoc On-demand Distance Vector). 
         [0007]    Utilization costs for a link in the path and/or the number of links in a path can be taken into account in the path distance value. It is also possible additionally or alternatively to take into account values for a transmission quality along the candidate path or a link in the candidate path and/or values for the transmission speed of the candidate path or a link in the candidate path. The candidate path with the optimum path distance value is then selected as the path. The message can now be routed along this path. 
         [0008]    Methods for determining the path distance value are referred to as routing metrics. One known routing metric is ETX (Expected Transmission Count). With the routing metric ETX the path for which the anticipated number of transmissions is lowest is selected. Transmissions here include both first transmissions and also repeat transmissions or retransmissions. A first transmission is the transmission of a packet by way of a link. A retransmission takes place if the first transmission was unsuccessful. To determine the link distance values with ETX, data packet arrival rates are used, which are determined by the two network nodes associated with the respective link. Metric messages, known as beacons, are sent at regular time intervals to determine the data packet arrival rates. 
         [0009]    The known combinations of routing method and routing metric have the disadvantage that they load the network with additional messages. 
       SUMMARY 
       [0010]    One potential object is to specify an improved method for determining a path in a network and a quality value for the path and a network node, which requires a smaller number of messages for its implementation or operation. 
         [0011]    The inventors propose a method for determining a path in a network and a quality value for the path, comprising a routing method for determining the path and a routing metric for determining the quality value, routing test messages, in particular so-called routing hellos, are sent at definable time intervals from at least one network node of the network in the context of the routing method. Also at least one data packet arrival rate is determined for at least one link in the path to determine the quality value of the path and the data packet arrival rate is determined based on at least one of the routing test messages. 
         [0012]    The routing test messages can be so-called AODV hellos for example. They can be used for example to determine or notify adjacent network nodes. 
         [0013]    The data packet arrival rate indicates the probability of a packet reaching its destination. The data packet arrival rate can for example be the quotient of a of routing test messages received within a time interval to routing test messages actually sent within the time interval. 
         [0014]    The method means that it is no longer necessary to send beacon messages. This means that the message load on the network is reduced. 
         [0015]    Preferably when determining the path at least one route determination message, in particular a route request message, is broadcast from at least a first network node and the route determination message contains information about a hitherto determined part of the path and about a data packet arrival rate of the first network node in respect of messages from a previous network node of the part of the path. 
         [0016]    The network node is embodied to implement a method for determining a path in a network by a routing method and a quality value for the path by a routing metric and has a transmit/receive facility for receiving routing test messages of the routing method and a processing facility. The processing facility is embodied in such a manner that a determination of at least one data packet arrival rate is carried out for a link between the network node and the further network node, to determine the quality value based on at least one routing test message sent from a further network node. 
         [0017]    Routing test messages are preferably sent from the network node at definable time intervals. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS  
         [0018]    These and other objects and advantages of the present invention will become more apparent and more readily appreciated from the following description of the preferred embodiments, taken in conjunction with the accompanying drawings of which: 
           [0019]      FIG. 1  shows a section of a network 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
       [0020]    Reference will now be made in detail to the preferred embodiments of the present invention, examples of which are illustrated in the accompanying drawings, wherein like reference numerals refer to like elements throughout. 
         [0021]      FIG. 1  shows an exemplary section of a network, having a first to fifth network node K 1  . . .  5 .  FIG. 1  also shows a first link L 1  between the first network node K 1  and the second network node K 2 , a second link L 2  between the second network node K 2  and the third network node K 3  and a third link L 3  between the third network node K 3  and the fourth network node K 4 . The three links L 1  . . .  3  form a path from the first network node K 1  to the fourth network node K 4 . The links L 1  . . .  3  shown as arrows indicate the respective transmission direction used for the path. The transmission directions are from the first network node K 1  to the second network node K 2  for the first link L 1 , from the second network node K 2  to the third network node K 3  for the second link L 2  and from the third network node K 3  to the fourth network node K 4  for the third link L 3 . 
         [0022]    In the exemplary embodiment of the invention the routing protocol AODV (Ad-hoc On-demand Distance Vector) is used as a basis. With AODV the network nodes K 1  . . .  5  send so-called hello messages at regular intervals, in this instance 1 second. Also AODV uses RREQ messages (RREQ=Route Request Packet) and RREP messages (RREP=Route Reply Packet) when determining a candidate path. 
         [0023]    On the one hand the hello messages serve to determine adjacencies between the network nodes K 1  . . .  5 . The network nodes K 1  . . .  5  of the network also determine data packet arrival rates from the hello messages. If for example the second network node K 2  receives nine out of ten of the hello messages from the first network node K 1 , it determines the data packet arrival rate for the first link as 9/10=90%. In this example the data packet arrival rates for the first two links L 1 , L 2  are 90% respectively, while the data packet arrival rate for the third link L 3  is 70%. The data packet arrival rates here relate to the respective transmission direction of the link L 1  . . .  3 . The values are referred to below as the data packet arrival rates in the transmission direction. 
         [0024]    A respective data packet arrival rate is therefore also determined for the respective other transmission direction of one of the links L 1  . . .  3 . The data packet arrival rates for the two transmission directions can differ from one another. The values for these, which are to be 80% for the first link L 1 , 90% for the second link L 2  and 70% for the third link L 3 , are referred to below as data packet arrival rates in the other transmission direction. 
         [0025]    In this example the first network node K 1  intends to send a message to the fourth network node K 4 . It is assumed that the first network node K 1  does not yet know the path to the fourth network node K 4  and must therefore determine it. To this end RREQ messages are sent, which reach the fourth network node K 4  by way of the second and third network nodes K 2 , K 3 . The fourth network node K 4  in turn responds with an RREP message, which is routed back to the first network node K 1 . 
         [0026]    In this embodiment of the invention the data packet arrival rates for the three links L 1  . . .  3  are transmitted back to the first network node K 1  along with the RREP message. The first network node K 1  can in turn determine a route metric for the path from the data packet arrival rates thus transmitted and can select a suitable path, if it has determined other paths to the fourth network node K 4 . 
         [0027]    The route metric can be determined for example using one of the following formulas: 
         [0000]    
       
         
           
             
               
                 
                   R 
                   = 
                   
                     
                       
                         ∏ 
                         Links 
                       
                        
                       LM 
                     
                     = 
                     
                       
                         ∏ 
                         Links 
                       
                        
                       
                         ( 
                         
                           
                             D 
                             r 
                           
                           × 
                           
                             D 
                             f 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
             
               
                 
                   R 
                   = 
                   
                     
                       ∏ 
                       Links 
                     
                      
                     
                       ( 
                       
                         D 
                         r 
                         2 
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
             
               
                 
                   R 
                   = 
                   
                     
                       ∑ 
                       Links 
                     
                      
                     
                       1 
                       D 
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where:
   R route metric   LM link metric   D r  data packet arrival rate in transmission direction   D f  data packet arrival rate in other transmission direction   Links number of links   
 
         [0033]    With the numerical examples the following route metric results according to the first formula (1) R=0.9×0.8×0.9×0.9×0.7×0.7=0.29, using the second formula (2) R=0.9×0.9×0.9×0.9×0.7×0.7=0.32. When the third formula (3) is used, R=3.7 results. 
         [0034]    If the first or second formula (1), (2) is used to determine the route metric, the path with the biggest route metric is the optimum path. When the third formula (3) is used, the path with the smallest route metric is the best path. 
         [0035]    A second embodiment of the invention results, when the link metrics are forwarded with the RREQ messages. In this instance the fourth network node K 4  can already decide about the path to be used based on the link metrics transmitted with the RREQ messages. 
         [0036]    It should be noted here that RREQ messages are broadcast, unlike RREP messages. This means that the respective sending network node K 1  . . .  5  does not know which of the other network nodes K 1  . . .  5  will receive the RREQ message. This means that the link metric for a link crossed by the RREQ message can only be indicated by the network node receiving this RREQ message in each instance. 
         [0037]    According to the procedure in the related art the network nodes K 1  . . .  5  transmit their respective data packet arrival rates respectively to their adjacent network nodes K 1  . . .  5  in the beacon messages, so that each network node K 1  . . .  5  knows the data packet arrival rates not only for one transmission direction of the links to its neighbor but for both transmission directions. 
         [0038]    Since beacons are not used in the inventive method however, the network nodes K 1  . . .  5  only know the respective data packet arrival rate in their direction. 
         [0039]    It is therefore not possible in this second embodiment of the invention to use the first formula (1) to determine the route metric. Only the second and third formulae (2), (3) can be used, as these only use the respectively available data packet arrival rate. 
         [0040]    The invention has been described in detail with particular reference to preferred embodiments thereof and examples, but it will be understood that variations and modifications can be effected within the spirit and scope of the invention covered by the claims which may include the phrase “at least one of A, B and C” as an alternative expression that means one or more of A, B and C may be used, contrary to the holding in  Superguide v. DIRECTV,  69 USPQ2d 1865 (Fed. Cir. 2004).