Method and apparatus for increasing reliability of packet delivery by dynamic packet cloning and route selection

Abstract

Various embodiments relate to a method for increasing the reliability of a packet delivery by using dynamic packet cloning on a source node and an intermediate node, the method comprising the steps of calculating an achieved reliability, calculating a calculated reliability using the achieved reliability, determining which of a plurality of first routes that have a reliability greater than the calculated reliability, selecting a first route from the determined first routes wherein the selected first route has the lowest reliability of the determined first routes, when there is at least one determined first routes, selecting a first route from the plurality of first routes wherein the selected first route has highest reliability of the plurality of first routes, when there are no determined first routes, updating a required reliability in the packet header to the reliability of the selected first route and sending the packet on the selected first route.

What is claimed is: 
     
       1. A method for increasing reliability of packet delivery comprising:
 calculating, for each route of a plurality of first routes, an achieved reliability; 
 
       obtaining a required reliability from a packet header;
 calculating, for each route of the plurality of first routes, a calculated reliability based upon both the achieved reliability and the required reliability; 
 comparing a respective reliability of each route of the plurality of first routes to the calculated reliability; 
 after determining that a subset of the plurality of first routes have respective reliabilities greater than the calculated reliability, selecting a first route from the subset, wherein the selected first route has a lowest reliability of the subset; 
 after determining that none of the plurality of first routes have respective reliabilities greater than the calculated reliability, selecting a first route from the plurality of first routes wherein the selected first route has a highest reliability of the plurality of first routes; 
 updating the required reliability in the packet header to the reliability of the selected first route, and 
 sending the packet on the selected first route. 
 
     
     
       2. The method of  claim 1 , further comprising:
 determining whether an expected reliability has been met. 
 
     
     
       3. The method of  claim 2 , further comprising:
 determining whether the plurality of first routes to a destination node exist when the expected reliability has not been met. 
 
     
     
       4. The method of  claim 3 , further comprising:
 determining whether a current packet cloning level is greater than or equal to a maximum packet cloning level when the plurality of routes to the destination node exist. 
 
     
     
       5. The method of  claim 4 , further comprising:
 cloning the packet when the current packet cloning level is less than the maximum packet cloning level. 
 
     
     
       6. The method of  claim 5 , further comprising:
 incrementing the current packet cloning level in the packet header after cloning the packet. 
 
     
     
       7. The method of  claim 6 , further comprising:
 calculating, for each route of a plurality of second routes, an achieved reliability; 
 calculating, for each route of the plurality of first routes, a calculated reliability based upon both the achieved reliability and the required reliability; 
 comparing a respective reliability of each route of the plurality of second routes to the calculated reliability; 
 after determining that a subset of the plurality of second routes have respective reliabilities greater than the calculated reliability, selecting a second route from the subset wherein the selected second route has a lowest reliability of the subset; 
 after determining that none of the plurality of first routes have respective reliabilities greater than the calculated reliability, selecting a second route from the plurality of second routes wherein the selected second route has a highest reliability of the plurality of second routes; 
 updating the required reliability in the packet header to the reliability of the selected second route, and 
 sending the packet on the selected second route. 
 
     
     
       8. The method of  claim 1 , wherein the achieved reliability is calculated by p ach     j   =1−Π k=0   j−1  (1−p P     k   ), where P k  is a route selected in iteration k, where k takes values from 0 to j−1 and where p P     k    is a reliability of P k . 
     
     
       9. The method of  claim 1 , wherein the calculated reliability is calculated by 
       
         
           
             
               
                 
                   p 
                   
                     cal 
                     j 
                   
                 
                 = 
                 
                   1 
                   - 
                   
                     
                       ( 
                       
                         1 
                         - 
                         
                           p 
                           req 
                         
                       
                       ) 
                     
                     
                       ( 
                       
                         1 
                         - 
                         
                           p 
                           
                             ach 
                             j 
                           
                         
                       
                       ) 
                     
                   
                 
               
               , 
             
           
         
       
       where p req  is the required reliability and p ach     j    is the achieved reliability. 
     
     
       10. The method of  claim 1 , wherein the packet header includes a current packet cloning level, a maximum packet cloning level, and the required reliability. 
     
     
       11. A network node for increasing reliability of packet delivery comprising:
 a memory; and 
 a processor configured to:
 calculate, for each route of a plurality of first routes, an achieved reliability; 
 obtain a required reliability from a packet header; 
 calculate, for each route of the plurality of first routes, a calculated reliability based upon both the achieved reliability and a required reliability; 
 compare a respective reliability of each route of the plurality of first routes to the calculated reliability; 
 after determining that a subset of the plurality of first routes have respective reliabilities greater than the calculated reliability, select a first route from the subset, wherein the selected first route has a lowest reliability of the subset; 
 after determining that none of the plurality of first routes have respective reliabilities greater than the calculated reliability, select a first route from the plurality of first routes wherein the selected first route has a highest reliability of the plurality of first routes; update the required reliability in the packet header to the reliability of the selected first route, and 
 
 send the packet on the selected first route. 
 
     
     
       12. The network node of  claim 11 , wherein the processor is further configured to determine whether the expected reliability has been met. 
     
     
       13. The network node of  claim 12 , wherein the processor is further configured to determine whether the plurality of routes to a destination node exist when the expected reliability has not been met. 
     
     
       14. The network node of  claim 13 , wherein the processor is further configured to determine whether a current packet cloning level is greater than or equal to a maximum packet cloning level when the plurality of routes to the destination node exist. 
     
     
       15. The network node of  claim 14 , wherein the processor is further configured to clone the packet when the current packet cloning level is less than the maximum packet cloning level. 
     
     
       16. The network node of  claim 15 , wherein the processor is further configured to increment the current packet cloning level in the packet header after cloning the packet. 
     
     
       17. The network node of  claim 16 , wherein the processor is further configured to:
 calculate, for each route of a plurality of second routes, an achieved reliability; 
 calculate, for each route of the plurality of second routes, a calculated reliability based upon both the achieved reliability and the required reliability; 
 compare a respective reliability of each route of the plurality of second routes to the calculated reliability; 
 after determining that a subset of the plurality of second routes have respective reliabilities greater than the calculated reliability, select a second route from the subset, wherein the selected second route has a lowest reliability of the subset; 
 after determining that none of the plurality of second routes have respective reliabilities greater than the calculated reliability, select a second route from the plurality of second routes, wherein the selected second route has a highest reliability of the plurality of second routes; 
 update the required reliability in the packet header to the reliability of the selected second route, and 
 send the packet on the selected second route. 
 
     
     
       18. The network node of  claim 11 , wherein the achieved reliability is calculated by p ach     j   =1−Π k=0   j−1  (1−p P     k   ), where P k  is a route selected in iteration k, where k takes values from 0 to j−1 and where p P     k    is a reliability of P k . 
     
     
       19. The network node of  claim 11 , wherein the calculated reliability is calculated by 
       
         
           
             
               
                 
                   p 
                   
                     cal 
                     j 
                   
                 
                 = 
                 
                   1 
                   - 
                   
                     
                       ( 
                       
                         1 
                         - 
                         
                           p 
                           req 
                         
                       
                       ) 
                     
                     
                       ( 
                       
                         1 
                         - 
                         
                           p 
                           
                             ach 
                             j 
                           
                         
                       
                       ) 
                     
                   
                 
               
               , 
             
           
         
       
       where p req  is the required reliability and p ach     j    is the achieved reliability. 
     
     
       20. The network node of  claim 11 , wherein the packet header includes a current packet cloning level, a maximum packet cloning level, and the required reliability.