System and method for load balancing traffic in a mpls network

Abstract

A method and system for managing traffic between a first provider edge and a second provider edge in a network. The network includes logical paths between the first provider edge and the second provider edge. For each logical path, jitter, packet delay, and packet loss are identified. For each logical path, a path usage is calculated as a function of the identified jitter, packet delay, and packet loss. Most recent data received by the first provider edge is transmitted to the second provider edge via a selected logical path that has a highest path usage for which transmitting the received most recent data does not result in the selected logical path managing a higher percentage of network traffic than is dictated by the highest usage value for the selected logical path.

1 . A method for managing traffic in a network, said method comprising:
 identifying I label switch paths P i  (i=1, 2, . . . , I), each label switch path P i  beginning at a first provider edge and ending at a second provider edge, wherein the first provider edge and the second provider edge each reside in the network, and wherein I is a total number of paths in the network such that I is a positive integer of at least 2;   for each label switch path P i  (i=1, 2, . . . , I), identifying J logical paths LP i,j  (j=1, 2, . . . , J), wherein J=2 N  such that N is a positive integer of at least 2, and wherein said J logical paths for the I label switch paths consist of K logical paths such that K=I*J;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), identifying jitter J i,j  and packet delay D i,j  and packet loss L i,j ;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), calculating a path usage U i,j  as a first function of said J i,j  and said D i,j  and said L i,j , wherein U i,j  is a fraction denoting a highest percentage of total network traffic that logical path LP i,j  can manage;   said first provider edge receiving most recent data; and   transmitting said received most recent data from the first provider edge to the second provider edge via a selected logical path of the K logical path such that the selected logical path comprises a highest path usage for which said transmitting said received most recent data does not result in the selected logical path managing a higher percentage of network traffic than is dictated by said highest usage value comprised by said selected logical path.   
     
     
         2 . The method of  claim 1 , wherein said calculating the path usage U i,j  for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J) comprises:
 calculating a path rate Ri,j as a second function of said J i,j  and said D i,j  and said L i,j ;   calculating a weight per path (W i,j ) according to   
       
         
           
             
               
                 
                   W 
                   
                     i 
                     , 
                     j 
                   
                 
                 = 
                 
                   
                     R 
                     
                       i 
                       , 
                       j 
                     
                   
                   / 
                   
                     
                       ∑ 
                       
                         
                           i 
                           = 
                           1 
                         
                         , 
                         
                           j 
                           = 
                           1 
                         
                       
                       
                         I 
                         , 
                         J 
                       
                     
                      
                     
                         
                     
                      
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                   
                 
               
               ; 
             
           
         
         calculating a credit per path (C i,j ) according to C i,j =1/W i,j ; 
         calculating C i,j ) according to 
       
       
         
           
             
               
                 U 
                 
                   i 
                   , 
                   j 
                 
               
               = 
               
                 
                   C 
                   
                     i 
                     , 
                     j 
                   
                 
                 / 
                 
                   
                     ∑ 
                     
                       
                         i 
                         = 
                         1 
                       
                       , 
                       
                         j 
                         = 
                         1 
                       
                     
                     
                       I 
                       , 
                       J 
                     
                   
                    
                   
                       
                   
                    
                   
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
     
         3 . The method of  claim 2 , wherein R i,j  is calculated according to R i,j =D i,j *DN+J i,j *JN+L i,j *LN; and
 wherein DN, JN, and JN are proportionality constants for calculating R i,j .   
     
     
         4 . The method of  claim 3 , wherein the method further comprises:
 said first provider edge receiving DN, JN, and JN as user input for said calculating R i,j .   
     
     
         5 . The method of  claim 1 , wherein said received most recent data that is transmitted via the selected logical path comprises a plurality of packets, wherein each packet comprises a header that includes an EXP field consisting of N bits, and wherein the value of the N bits in the EXP field is the value of j pertaining to the selected logical path. 
     
     
         6 . A computer program product, comprising a computer readable storage medium having a computer readable computer readable program code stored therein, said program code containing instructions that when executed by a processor of a computer system implement a method for managing traffic in a network, said method comprising:
 identifying I label switch paths P i  (i=1, 2, . . . , I), each label switch path P i  beginning at a first provider edge and ending at a second provider edge, wherein the first provider edge and the second provider edge each reside in the network, and wherein I is a total number of paths in the network such that I is a positive integer of at least 2;   for each label switch path P i  (i=1, 2, . . . , I), identifying J logical paths LP i,j  (j=1, 2, . . . , J), wherein J=2 N  such that N is a positive integer of at least 2, and wherein said J logical paths for the I label switch paths consist of K logical paths such that K=I*J;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), identifying jitter J i,j  and packet delay D i,j  and packet loss L i,j ;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), calculating a path usage U i,j  as a first function of said J i,j  and said D i,j  and said L i,j , wherein U i,j  is a fraction denoting a highest percentage of total network traffic that logical path LP i,j  can manage;   said first provider edge receiving most recent data; and   transmitting said received most recent data from the first provider edge to the second provider edge via a selected logical path of the K logical path such that the selected logical path comprises a highest path usage for which said transmitting said received most recent data does not result in the selected logical path managing a higher percentage of network traffic than is dictated by said highest usage value comprised by said selected logical path.   
     
     
         7 . The computer program product of  claim 1 , wherein said calculating the path usage U i,j  for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J) comprises:
 calculating a path rate Ri,j as a second function of said J i,j  and said D i,j  and said L i,j ;   calculating a weight per path (W i,j ) according to   
       
         
           
             
               
                 
                   W 
                   
                     i 
                     , 
                     j 
                   
                 
                 = 
                 
                   
                     R 
                     
                       i 
                       , 
                       j 
                     
                   
                   / 
                   
                     
                       ∑ 
                       
                         
                           i 
                           = 
                           1 
                         
                         , 
                         
                           j 
                           = 
                           1 
                         
                       
                       
                         I 
                         , 
                         J 
                       
                     
                      
                     
                         
                     
                      
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                   
                 
               
               ; 
             
           
         
         calculating a credit per path (C i,j ) according to C i,j =1/W i,j ; 
         calculating) according to 
       
       
         
           
             
               
                 U 
                 
                   i 
                   , 
                   j 
                 
               
               = 
               
                 
                   C 
                   
                     i 
                     , 
                     j 
                   
                 
                 / 
                 
                   
                     ∑ 
                     
                       
                         i 
                         = 
                         1 
                       
                       , 
                       
                         j 
                         = 
                         1 
                       
                     
                     
                       I 
                       , 
                       J 
                     
                   
                    
                   
                       
                   
                    
                   
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
     
         8 . The computer program product of  claim 7 ,
 wherein R i,j  is calculated according to R i,j =D i,j *DN+J i,j *JN+L i,j *LN; and   wherein DN, JN, and JN are proportionality constants for calculating R i,j .   
     
     
         9 . The computer program product of  claim 8 , wherein the method further comprises:
 said first provider edge receiving DN, JN, and JN as user input for said calculating R i,j .   
     
     
         10 . The computer program product of  claim 6 , wherein said received most recent data that is transmitted via the selected logical path comprises a plurality of packets, wherein each packet comprises a header that includes an EXP field consisting of N bits, and wherein the value of the N bits in the EXP field is the value of j pertaining to the selected logical path. 
     
     
         11 . A computer system comprising a processor coupled to a computer-readable memory unit, said memory unit comprising program code, said program code comprising instruction that when executed by said processor, implement a method for managing traffic in a network, said method comprising:
 identifying I label switch paths P i  (i=1, 2, . . . , I), each label switch path P i  beginning at a first provider edge and ending at a second provider edge, wherein the first provider edge and the second provider edge each reside in the network, and wherein I is a total number of paths in the network such that I is a positive integer of at least 2;   for each label switch path P i  (i=1, 2, . . . , I), identifying J logical paths LP i,j  (j=1, 2, . . . , J), wherein J=2 N  such that N is a positive integer of at least 2, and wherein said J logical paths for the I label switch paths consist of K logical paths such that K=I*J;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), identifying jitter J i,j  and packet delay D i,j  and packet loss L i,j ;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), calculating a path usage U i,j  as a first function of said J i,j  and said D i,j  and said L i,j , wherein U i,j  is a fraction denoting a highest percentage of total network traffic that logical path LP i,j  can manage;   said first provider edge receiving most recent data; and   transmitting said received most recent data from the first provider edge to the second provider edge via a selected logical path of the K logical path such that the selected logical path comprises a highest path usage for which said transmitting said received most recent data does not result in the selected logical path managing a higher percentage of network traffic than is dictated by said highest usage value comprised by said selected logical path.   
     
     
         12 . The computer system of  claim 11 , wherein said calculating the path usage U i,j  for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J) comprises:
 calculating a path rate Ri,j as a second function of said J i,j  and said D i,j  and said L i,j ;   calculating a weight per path (W i,j ) according to   
       
         
           
             
               
                 
                   W 
                   
                     i 
                     , 
                     j 
                   
                 
                 = 
                 
                   
                     R 
                     
                       i 
                       , 
                       j 
                     
                   
                   / 
                   
                     
                       ∑ 
                       
                         
                           i 
                           = 
                           1 
                         
                         , 
                         
                           j 
                           = 
                           1 
                         
                       
                       
                         I 
                         , 
                         J 
                       
                     
                      
                     
                         
                     
                      
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                   
                 
               
               ; 
             
           
         
         calculating a credit per path (C i,j ) according to C i,j =1/W i,j ; 
         calculating C i,j ) according to 
       
       
         
           
             
               
                 U 
                 
                   i 
                   , 
                   j 
                 
               
               = 
               
                 
                   C 
                   
                     i 
                     , 
                     j 
                   
                 
                 / 
                 
                   
                     ∑ 
                     
                       
                         i 
                         = 
                         1 
                       
                       , 
                       
                         j 
                         = 
                         1 
                       
                     
                     
                       I 
                       , 
                       J 
                     
                   
                    
                   
                       
                   
                    
                   
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
     
         13 . The computer system of  claim 12 ,
 wherein R i,j  is calculated according to R i,j =D i,j *DN+J i,j *JN+L i,j *LN; and   wherein DN, JN, and JN are proportionality constants for calculating R i,j .   
     
     
         14 . The computer system of  claim 13 , wherein the method further comprises:
 said first provider edge receiving DN, JN, and JN as user input for said calculating R i,j .   
     
     
         15 . The computer system of  claim 11 , wherein said received most recent data that is transmitted via the selected logical path comprises a plurality of packets, wherein each packet comprises a header that includes an EXP field consisting of N bits, and wherein the value of the N bits in the EXP field is the value of j pertaining to the selected logical path. 
     
     
         16 . A process for supporting computer infrastructure, said process comprising providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer readable program code in a computing system, wherein the code in combination with the computing system is configured to perform a method for managing traffic in a network, said method comprising:
 identifying I label switch paths P i  (i=1, 2, . . . , I), each label switch path P i  beginning at a first provider edge and ending at a second provider edge, wherein the first provider edge and the second provider edge each reside in the network, and wherein I is a total number of paths in the network such that I is a positive integer of at least 2;   for each label switch path P i  (i=1, 2, . . . , I), identifying J logical paths LP i,j  (j=1, 2, . . . , J), wherein J=2 N  such that N is a positive integer of at least 2, and wherein said J logical paths for the I label switch paths consist of K logical paths such that K=I*J;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), identifying jitter J i,j  and packet delay D i,j  and packet loss L i,j ;   for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J), calculating a path usage U i,j  as a first function of said J i,j  and said D i,j  and said L i,j , wherein U i,j  is a fraction denoting a highest percentage of total network traffic that logical path LP i,j  can manage;   said first provider edge receiving most recent data; and   transmitting said received most recent data from the first provider edge to the second provider edge via a selected logical path of the K logical path such that the selected logical path comprises a highest path usage for which said transmitting said received most recent data does not result in the selected logical path managing a higher percentage of network traffic than is dictated by said highest usage value comprised by said selected logical path.   
     
     
         17 . The process of  claim 16 , wherein said calculating the path usage U i,j  for each logical path LP i,j  (i=1, 2, . . . , I and j=1, 2, . . . , J) comprises:
 calculating a path rate Ri,j as a second function of said J i,j  and said D i,j  and said L i,j ;   calculating a weight per path (W i,j ) according to   
       
         
           
             
               
                 
                   W 
                   
                     i 
                     , 
                     j 
                   
                 
                 = 
                 
                   
                     R 
                     
                       i 
                       , 
                       j 
                     
                   
                   / 
                   
                     
                       ∑ 
                       
                         
                           i 
                           = 
                           1 
                         
                         , 
                         
                           j 
                           = 
                           1 
                         
                       
                       
                         I 
                         , 
                         J 
                       
                     
                      
                     
                         
                     
                      
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                   
                 
               
               ; 
             
           
         
         calculating a credit per path (C i,j ) according to C i,j =1/W i,j ; 
         calculating C i,j ) according to 
       
       
         
           
             
               
                 U 
                 
                   i 
                   , 
                   j 
                 
               
               = 
               
                 
                   C 
                   
                     i 
                     , 
                     j 
                   
                 
                 / 
                 
                   
                     ∑ 
                     
                       
                         i 
                         = 
                         1 
                       
                       , 
                       
                         j 
                         = 
                         1 
                       
                     
                     
                       I 
                       , 
                       J 
                     
                   
                    
                   
                       
                   
                    
                   
                     
                       R 
                       
                         i 
                         , 
                         j 
                       
                     
                     . 
                   
                 
               
             
           
         
       
     
     
         18 . The process of  claim 17 ,
 wherein R i,j  is calculated according to R i,j =D i,j *DN+J i,j *JN+L i,j *LN; and   wherein DN, JN, and JN are proportionality constants for calculating R i,j .   
     
     
         19 . The process of  claim 18 , wherein the method further comprises:
 said first provider edge receiving DN, JN, and JN as user input for said calculating R i,j .   
     
     
         20 . The process of  claim 19 , wherein said received most recent data that is transmitted via the selected logical path comprises a plurality of packets, wherein each packet comprises a header that includes an EXP field consisting of N bits, and wherein the value of the N bits in the EXP field is the value of j pertaining to the selected logical path.