Abstract:
A method is disclosed for adaptively and intelligently partitioning traffic among a plurality of communications channels, without injecting probe traffic into any of the channels. In accordance with the illustrative embodiment, a source node transmits traffic to a receiving node via K communications channels in accordance with partition coefficients α 1 , . . . , α K , and the source node receives information regarding the quality of service (QoS) provided by each of the communications channels. The source node adjusts the values of the partition coefficients α 1 , . . . , α K  adaptively based on: the current channel QoS information, prior channel QoS information, the prior values of α 1 , . . . , α K , and a measure of channel independence for one or more pairs of communications channels.

Description:
FIELD OF THE INVENTION 
     The present invention relates to telecommunications in general, and, more particularly, to adaptive traffic partitioning. 
     BACKGROUND OF THE INVENTION 
     When information is transmitted from one node (e.g., a computer, a telecommunications terminal, a switch, a router, etc.) to another node via a communications channel, the performance of the channel can vary unpredictably due to channel loss, jitter, noise, and so forth. A well-known technique for monitoring the performance of a communications channel, and how the performance varies over time, is to inject additional traffic, known as probe traffic, into the transmission. A disadvantage of this technique, however, is the associated overhead and reduced throughput that results from the introduction of additional traffic into the communications channel. 
     SUMMARY OF THE INVENTION 
     The present invention pertains to situations in which there is a plurality of communications channels available for a source node to transmit information to a receiving node. In particular, the present invention provides a technique for adaptively and intelligently partitioning traffic among the communications channels, without injecting probe traffic into any of the channels. The present invention is therefore capable of adjusting the partitioning of traffic over time in order to maintain maximum performance, without any of the disadvantages associated with the introduction of probe traffic. 
     In accordance with the illustrative embodiment of the present invention, a source node transmits traffic to a receiving node via K communications channels in accordance with partition coefficients α 1 , . . . , α K , and the source node receives information regarding the quality of service (QoS) provided by each of the communications channels. The source node adjusts the values of the partition coefficients α 1 , . . . , α K  adaptively based on:
         the current channel QoS information,   prior channel QoS information,   the prior values of α 1 , . . . , α K , and   a measure of channel independence for one or more pairs of communications channels
 
where the measure of channel independence is based on at least one of:
   the extent to which traffic in a first channel affects traffic in a second channel,   the extent to which traffic in a first channel affects quality of service of a second channel, and   the extent to which a change in quality of service of a first channel affects the quality of service of a second channel.       

     In accordance with the illustrative embodiment, the channel QoS information is expressed as values of a quality-of-service metric (e.g., throughput, jitter, error rate, re-transmission frequency, some combination of two or more such metrics, etc.) for each of the channels. In addition, in the illustrative embodiment the measure of channel independence is a real-valued coefficient where a value of zero indicates that two channels are completely independent—i.e., that traffic and changes in QoS in one of the channels does not affect traffic or QoS in the other channel. Finally, in the illustrative embodiment partition coefficients α 1 , . . . , α K  are real numbers in [0, 1] that indicate the fraction of traffic that is transmitted over each of the K communications channels 
     
       
         
           
             
               ( 
               
                 
                   i 
                   . 
                   e 
                   . 
                 
                 , 
                 
                   
                     
                       ∑ 
                       
                         i 
                         = 
                         1 
                       
                       K 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       α 
                       i 
                     
                   
                   = 
                   1 
                 
               
               ) 
             
             . 
           
         
       
     
     The illustrative embodiment comprises: receiving values q 1 , . . . , q K  of a quality-of-service metric for K communications channels, wherein K is an integer greater than one, and wherein the values q 1 , . . . , q K  are obtained without injecting any probe traffic into any of the K communications channels; and determining values for K coefficients α 1 , . . . , α K  that quantify how subsequent traffic is to be partitioned among the K communications channels; wherein the determination of the coefficients α 1 , . . . , α K  is based on: (i) the values q 1 , . . . , q K , (ii) one or more previous values of the coefficients α 1 , . . . , α K , and (iii) a measure of channel independence for one or more pairs of the K communications channels. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  depicts a schematic diagram of the salient elements of telecommunications system  100 , in accordance with the illustrative embodiment of the present invention. 
         FIG. 2  depicts a schematic diagram of the salient elements of source node  101 , as shown in  FIG. 1 , in accordance with the illustrative embodiment of the present invention. 
         FIG. 3  depicts a flowchart of a method for adaptively partitioning traffic among communications channels  102 - 1  through  102 -K, as shown in  FIG. 1 , in accordance with the illustrative embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  depicts a schematic diagram of the salient elements of telecommunications system  100 , in accordance with the illustrative embodiment of the present invention. As shown in  FIG. 1 , telecommunications system  100  comprises source node  101 , communications channels  102 - 1  through  102 -K, where K is an integer greater than one, and receiving node  103 , interconnected as shown. 
     Communications channels  102 - 1  through  102 -K are conduits for the transmission of information from source node  101  to receiving node  103 , as is well-known in the art. In accordance with the illustrative embodiment, communications channels  102 - 1  through  102 -K are bidirectional, and thus enable receiving node  103  to transmit information to source node  101  as well. As will be appreciated by those skilled in the art, however, in some embodiments of the present invention communications channels  102 - 1  through  102 -K might instead be unidirectional (i.e., enabling transmission in only one direction from source node  101  to receiving node  103 ), and it will be clear to those skilled in the art, after reading this disclosure, how to adapt the method of  FIG. 3 , described below, for such embodiments of the present invention. 
     Source node  101  is one of a computer, a telecommunications terminal, a switch, a router, etc. that is capable of transmitting and receiving traffic via communications channels  102 - 1  through  102 -K, and of performing tasks  310 ,  360 , and  370 , described below and with respect to  FIG. 3 . As will be appreciated by those skilled in the art, in alternative embodiments of the present invention in which communications channels  102 - 1  through  102 -K are unidirectional, source node  101  is capable of transmitting, but not receiving, traffic via the channels. 
     Receiving node  103  is one of a computer, a telecommunications terminal, a switch, a router, etc. that is capable of transmitting and receiving traffic via communications channels  102 - 1  through  102 -K, and of performing tasks  320  through  350 , described below and with respect to  FIG. 3 . As will be appreciated by those skilled in the art, in alternative embodiments of the present invention in which communications channels  102 - 1  through  102 -K are unidirectional, receiving node  103  is capable of receiving, but not transmitting, traffic via the channels. 
       FIG. 2  depicts a schematic diagram of the salient elements of source node  101 , in accordance with the illustrative embodiment of the present invention. As shown in  FIG. 2 , source node  101  comprises receiver  201 , processor  202 , memory  203 , and transmitter  204 , interconnected as shown. 
     Receiver  201  is capable of receiving signals via communications channels  102 - 1  through  102 -K and of forwarding information encoded in these signals to processor  202 , in well-known fashion. 
     Processor  202  is a general-purpose processor that is capable of receiving information from receiver  201 , of reading data from and writing data into memory  203 , of executing instructions stored in memory  203 , and of forwarding information to transmitter  204 , in well-known fashion. As will be appreciated by those skilled in the art, in some alternative embodiments of the present invention processor  202  might be a special-purpose processor, rather than a general-purpose processor. 
     Memory  203  is capable of storing data and executable instructions, in well-known fashion, and might be any combination of random-access memory (RAM), flash memory, disk drive, etc. In accordance with the illustrative embodiment, memory  203  stores executable instructions corresponding to tasks  310 ,  360 , and  370 , described below and with respect to  FIG. 3 . 
     Transmitter  204  is capable of receiving information from processor  202 , and of transmitting signals that encode this information via communications channels  102 - 1  through  102 -K, in well-known fashion. 
       FIG. 3  depicts a flowchart of a method for adaptively partitioning traffic among communications channels  102 - 1  through  102 -K, in accordance with the illustrative embodiment of the present invention. It will be clear to those skilled in the art, after reading this disclosure, which tasks depicted in  FIG. 3  can be performed simultaneously or in a different order than that depicted. 
     At task  310 , partition coefficients α 1 , . . . , α K  are initialized. As will be appreciated by those skilled in the art, in some embodiments of the present invention the coefficients might be initialized with equal values (e.g., 1/K, etc.), while in some other embodiments of the present invention the coefficients might be initialized based on information such as historical quality of service (QoS) data for the channels, parameter specifications of the channels (e.g., bandwidth, etc.), etc. 
     At task  320 , QoS metric values q 1 , . . . , q K  are estimated for communications channels  102 - 1  through  102 -K, in well-known fashion. As will be appreciated by those skilled in the art, in some embodiments of the present invention in which traffic is composed of Voice over Internet Protocol (VoIP) packets, the delay, loss, and jitter of the packets might be estimated, and an R-factor QoS metric that combines these parameters into a single value might then be computed. Alternatively, in some other embodiments of the present invention, other traffic characteristics such as latency or measured bandwidth might be estimated, and another type of QoS metric based on these characteristics might then be computed. 
     Task  330  determines whether F(q 1 ), . . . , F(q K ), where F is a function, differ from their previous values by more than a threshold  6 . As will be appreciated by those skilled in the art, in some embodiments F might simply be the identity function, while in some other embodiments F might be another type of function; moreover, the difference between new and previous values of F(q 1 ), . . . , F(q K ) might be computed in a variety of ways, such as the sum of the differences of the individual F(q i ), the sum of the squares of the differences of the individual F(q i ), the minimum difference over all of the F(q i ), the maximum difference over all of the F(q i ), and so forth. As will further be appreciated by those skilled in the art, the selection of an appropriate threshold value δ is a design decision that is typically best determined in each particular implementation. 
     If the new values differ from the old values by more than threshold δ, then execution continues at task  350 , otherwise execution proceeds to task  340 . 
     Task  340  checks whether at least Δ seconds have elapsed since the last time values q 1 , . . . , q K  were transmitted to source node  101  at task  350 —or, if task  350  has not yet been executed, since the method of  FIG. 3  began. If Δ or more seconds have elapsed, then execution proceeds to task  350 , otherwise execution continues at task  370 . As will be appreciated by those skilled in the art, Δ is a positive real number whose value is best determined in each particular implementation. 
     At task  350 , values q 1 , . . . , q K  are transmitted to source node  101 , in well-known fashion. In accordance with the illustrative embodiment, values q 1 , . . . , q K  are transmitted to source node  101  via communications channels  102 - 1  through  102 -K. However, as will be appreciated by those skilled in the art, in some other embodiments of the present invention values q 1 , . . . , q K  might be transmitted in an alternative fashion (e.g., via some other communications channel or network not depicted in the drawings, etc.), and it will be clear to those skilled in the art, after reading this disclosure, how to make and use such embodiments of the present invention. 
     At task  360 , new values for partition coefficients α 1 , . . . , α K  are determined based on:
         the new values of q 1 , . . . , q K  transmitted to source node  101 ,   previous values of q 1 , . . . , q K ,   previous values of α 1 , . . . , α K , and   a measure of channel independence for one or more pairs of communications channels  102 - 1  through  102 -K.       

     In accordance with illustrative embodiment, previous values of α 1 , . . . , α K  are considered at task  360  in order to smooth out changes of α 1 , . . . , α K  over time. As will be appreciated by those skilled in the art, there are a variety of techniques known in the art for achieving such smoothing, such as a moving average, a maximum incremental change, and so forth, and the parameters associated with such techniques (e.g., the size of the moving average window, the value of the maximum incremental change, etc.) can be set to control the degree of smoothing (or alternatively, how aggressively the values of α 1 , . . . , α K  change over time). Similarly, previous values of q 1 , . . . , q K  are also considered at task  360  to smooth out changes over time. 
     In accordance with illustrative embodiment, the measure of channel independence is based on at least one of:
         the extent to which traffic in a first channel affects traffic in a second channel,   the extent to which traffic in a first channel affects quality of service of a second channel, and   the extent to which a change in quality of service of a first channel affects the quality of service of a second channel.       

     In particular, in the illustrative embodiment the measure of channel independence is a real number ρ, where ρ=0 indicates that two channels are completely independent, which means that:
         an increase in traffic in one of the channels has no effect on the traffic or quality of service of the other channel, and   a change in quality of service of one of the channels has no effect on the quality of service of the other channel.
 
Conversely, a non-zero value of ρ indicates that two channels are dependent, where ρ=1 means that:
   an increase in traffic in one of the channels results in an equal decrease of traffic in the other channel, and   a decrease in quality of service in one of the channels results in an equal decrease of quality of service in the other channel.
 
Similarly, an arbitrary non-zero value of ρ reflects how much a change in traffic/QoS in one channel affects traffic/QoS in the other channel, where both ρ&lt;1 and ρ&gt;1 are possible.
       

     As will be appreciated by those skilled in the art, the measure of channel independence might be either non-symmetric or symmetric, where the former case corresponds to an ordered pair of channels, and the latter case corresponds to an un-ordered pair of channels. Moreover, as will be appreciated by those skilled in the art, some other embodiments of the present invention might employ a different measure of channel independence than that of the illustrative embodiment, and it will be clear to those skilled in the art, after reading this disclosure, how to make and use such embodiments. 
     As will further be appreciated by those skilled in the art, there are a variety of ways in which the particular values of partition coefficients α 1 , . . . , α K  might be set. For example, in some embodiments values α 1 , . . . , α K  might be set proportional to the QoS values q 1 , . . . , q K  (subject, possibly, to the smoothing influences of prior values), while in some other embodiments of the present invention the values of α 1 , . . . , α K  might be based on a ranking of values q 1 , . . . , q K , irrespective of the relative magnitudes of q 1 , . . . , q K . For example, suppose K=3, q 1 =2 (the particular units are immaterial), q 2 =5, and q 3 =3. In the former case, the partition coefficients would be set as α 1 =0.2, α 2 =0.5, and α 3 =0.3, while in the latter case, the partition coefficients might be set as, say, α 1 =0.3, α 2 =0.37, and α 3 =0.33. 
     As will appreciated by those skilled in the art, there are yet other ways that the values of partition coefficients α 1 , . . . , α K  might be set. For example, in some embodiments of the present invention, a geometric partition might be employed so that a disproportionately large fraction of traffic is transmitted over the channel with the best quality of service. Furthermore, in some embodiments of the present invention, values α 1 , . . . , α K  might be set so that a very small fraction, or even zero, traffic is transmitted over one or more particular channels. In the case that zero traffic is transmitted over a particular channel (i.e., α i =0 for some 1≦i≦N), it might be advantageous to periodically set α i &gt;0 so that the quality of service of the channel is periodically measured. 
     At task  370 , source node  101  transmits traffic via communications channels  102 - 1  through  102 -K in accordance with partition coefficients α 1 , . . . , α K  (i.e., the traffic is distributed among the channels such that communications channel  102 - i  receives fraction α i  of the traffic, for all i∈{1, . . . , K}). 
     As will be appreciated by those skilled in the art, although in the illustrative embodiment tasks  310 ,  360 , and  370  are performed by source node  101 , in some other embodiments of the present invention some or all of these tasks might be performed by some other entity, such as a third node that is capable of communicating with source node  101  and receiving node  103 . Similarly, although in the illustrative embodiment tasks  320  through  350  are performed by receiving node  103 , in some other embodiments of the present invention some or all of these tasks might be performed by some other entity—perhaps the same as the entity that performs tasks  310 ,  360 , and  370 , or perhaps yet another entity (e.g., a fourth node, etc.). In any case, it will be clear to those skilled in the art, after reading this disclosure, how to make and use such alternative embodiments of the present invention. 
     It is to be understood that the disclosure teaches just one example of the illustrative embodiment and that many variations of the invention can easily be devised by those skilled in the art after reading this disclosure and that the scope of the present invention is to be determined by the following claims.