Abstract:
A technique that seeks to direct and re-direct streams of packets through a packet network without adversely affecting the quality of service of existing streams is disclosed. In accordance with the illustrative embodiment of the present invention, streams of packets that are directed and re-directed through a packet network are initially put on probation. During the probation period, a quality-of-service measure for the stream is compared with a threshold whose value is initially high and decreases with time. This has the advantageous affect of noticing problems quickly so that they can be remediated quickly.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of U.S. Provisional Application 60/827,413, filed Sep. 28, 2006, entitled “Path Switching and Call Protection for Reliable IP Telephony” (Attorney Docket 630-266us), which application is also incorporated by reference. 
         [0002]    U.S. patent application Ser. No. 11/201,892, filed Aug. 11, 2005, entitled “Quality-of-Service Assurance for IP Telephony” (Attorney Docket 630-128us) is incorporated by reference. 
         [0003]    U.S. patent application Ser. No. 11/765,242, filed Jun. 19, 2007, entitled “Evaluating Feasible Transmission Paths in a Packet Network” (Attorney Docket 630-209us) is incorporated by reference. 
     
     FIELD OF THE INVENTION 
       [0004]    The present invention relates to telecommunications in general, and, more particularly, to the administration of packet networks. 
       BACKGROUND OF THE INVENTION 
       [0005]    The advantages of using relay nodes in packets networks to provide quality-of-service assurance in networks that do not provide quality-of-service guarantees are becoming clear, as is taught in U.S. patent application Ser. No. 11/201,892, filed Aug. 11, 2005, entitled “Quality-of-Service Assurance for IP Telephony” (Attorney Docket 630-128us). However, the prior art is not always sufficient, and, therefore, the need exists for inventions that help ensure satisfactory quality-of-service in networks that do not provide quality-of-service guarantees. 
       SUMMARY OF THE INVENTION 
       [0006]    The present invention is a technique that seeks to direct and re-direct streams of packets through a packet network without adversely affecting the quality of service of existing streams. In accordance with the illustrative embodiment of the present invention, streams of packets that are directed and re-directed through a packet network are initially put on probation. During the probation period, a quality-of-service measure for the stream is compared with a threshold whose value is initially high and decreases with time. This has the advantageous effect of noticing problems quickly so that they can be remediated quickly. Embodiments of the present invention are useful in both relay and non-relay networks. 
         [0007]    The illustrative embodiment comprises (1) at moment t 1 , directing a stream of packets from a source node to a destination node on a first path; (2) at moment t 2 , calculating that a quality-of-service score R(t) for the stream of packets is below a quality-of-service threshold T(t) for the stream of packets; and (3) at moment t 3 , re-directing the stream of packets from the source node to the destination node on a second path because the quality-of-service score R(t) for the stream of packets on the first path is below the quality-of-service threshold T(t); wherein the quality-of-service threshold T(t) varies and is greater at moment t 2  than at moment t 2 +Δ; wherein moment t 1  is before moment t 2 ; wherein moment t 2  is before moment t 3 ; and wherein Δ is a positive real number greater than zero. 
     
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0008]      FIG. 1  depicts a schematic diagram of a packet network in accordance with the illustrative embodiment of the present invention. 
           [0009]      FIG. 2  depicts a flowchart of the operation of the illustrative embodiment of the present invention. 
           [0010]      FIG. 3  depicts a graph of the threshold schedule in accordance with the illustrative embodiment of the present invention. 
           [0011]      FIG. 4  depicts a graph of the quality-of-service score R(t) for the stream of packets with respect to the threshold schedule in accordance with the illustrative embodiment of the present invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0012]      FIG. 1  depicts a schematic diagram of a packet network in accordance with the illustrative embodiment of the present invention. In packet network  100 , the quality of service of a stream of packets is attained by re-directing the stream off of one or more relay nodes between its source and destination. U.S. patent application Ser. No. 11/201,892, filed Aug. 11, 2005, entitled “Quality-of-Service Assurance for IP Telephony” (Attorney Docket 630-128us) is a tutorial on the use of relays nodes to attain quality of service goals for streams of packets. 
         [0013]    Packet network  100  comprises: source node  101 - 1 , destination node  101 - 2 , first relay node  101 - 3 , second relay node  101 - 4 , and network nodes  101 - 5  through  101 - 7 , interconnected as shown. Although the illustrative embodiment comprises seven nodes, it will be clear to those skilled in the art, after reading this specification, how to make and use alternative embodiments of the present invention that comprise any number of nodes. 
         [0014]    Packet network  100  is capable of conveying a stream of packets that represents:
       i. audio, or   ii. video, or   iii. data, or   iv. any combination of i, ii, and iii
 
between any two nodes. It is well known to those skilled in the art how to encode any combination of audio, video, and data into a stream of packets and how to decode the stream of packets to recover the original content.
       
 
         [0019]    In accordance with the illustrative embodiment, packet network  100  supports both connection-oriented sessions and connectionless (i.e., datagram) service between each pair of nodes. 
         [0020]    Source node  101 - 1  comprises hardware and software and is capable of performing the functionality described below and in the accompanying drawings. Destination node  101 - 2  comprises hardware and software and is well known to those skilled in the art. First relay node  101 - 3  and second relay node  101 - 4  each comprise hardware and software and are well known to those skilled in the art. In accordance with the present invention, the salient characteristic of first relay node  101 - 3  and second relay node  101 - 4  is that each is capable of relaying or re-directing a packet addressed to it to another node. Switching nodes  101 - 5  through  101 - 6  each comprise hardware and software and are well known to those skilled in the art. 
         [0021]      FIG. 2  depicts a flowchart of the operation of the illustrative embodiment of the present invention. Prior to the execution of task  201 , there are one or more streams of packets flowing through packet network  100 , and each of the streams originates at one of the nodes and terminates at another of the nodes. 
         [0022]    At task  201 , source node  101 - 1  directs a stream of packets to first relay node  101 - 3  on a first path with instructions that the stream is to be re-directed off of first relay node  101 - 3  en route to destination node  101 - 2 . Task  201  occurs at moment t 1  and resets a probationary timer that is associated only with the stream of packets. It will be clear to those skilled in the art, after reading this specification, how to make embodiments of the present invention that perform task  201 . 
         [0023]    At task  202 , source node  101 - 1  begins the function of (1) ensuring that the quality of service of the stream of packets as re-directed off of the first relay node remains acceptable, and (2) ensuring that the stream of packets as re-directed off of the first relay node does not destroy the quality of service of other streams of packets flowing in packet network  100 . To do this, source node  101 - 1  calculates two quantities: (1) a quality-of-service score R(t) for the stream of packets, and (2) a quality-of-service threshold T(t) for the stream of packets. Because each of these quantities changes with time, both quantities are calculated to be effective for the same moment t to ensure that they can be compared on an apples-to-apples basis. 
         [0024]    The calculation of the quality-of-service score R(t) for the stream of packets can be accomplished in any of many well-known ways. In accordance with the illustrative embodiment, the quality-of-service score R(t) for the stream of packets is given a score between 0 to 100 and is based on ITU-T Recommendation G.107, “The E Model: A computational model for use in transmission planning,” 2003. It will be clear to those skilled in the art, however, how to make and use alternative embodiments of the present invention in which the quality-of-service score R(t) is calculated in a different way. 
         [0025]    In accordance with the illustrative embodiment, the quality-of-service threshold T(t) for the stream of packets decreases with time. In accordance with the illustrative embodiment, the threshold T(t) decreases in discrete steps at moments d 1  and d 2 . An example threshold schedule is depicted in Table 1 and  FIG. 3 . 
         [0000]                                      TABLE 1                   Example Threshold Schedule                Probation Status   t   T                       On Probation -   t &lt; d 1     90           Probationary Call   d 1  ≦ t ≦ d 2     85           Off Probation -   t &gt; d 2     80           Established Call                        
The threshold schedule is a straightforward mechanism for initially putting the stream of packets on “probation” with respect to the other established streams of packets. In the event that the presence of the stream as relayed through relay node  101 - 3  is causing congestion and adversely affecting the quality of service of the other established streams of packets, the threshold schedule has the advantageous benefit of forcing the re-directing of the stream of packets before the quality of service of the other established streams of packets is irreparably affected. Although in accordance with the illustrative embodiment the threshold schedule comprises three discrete steps, it will be clear to those skilled in the art, after reading this disclosure, how to make and use alternative embodiments of the present invention in which the threshold decreases continuously or discretely in any number of steps.
 
         [0026]    Ideally, the probation interval is long enough that source node  101 - 1  can ascertain whether the quality of service of the other established streams of packets are adversely affected by the stream of packets and yet is short enough that source node  101 - 1  can re-direct the stream of packets before the quality of service of the other established streams of packets is irreparably affected. 
         [0027]    At task  203 , source node  101 - 1  compares the quality-of-service score R(t) for the stream of packets, calculated in task  202 , with the quality-of-service threshold T(t) for the stream of packet, as also calculated in task  202 . When the quality-of-service score R(t) is greater than or equal to the quality-of-service threshold T(t), then source node  101 - 1  infers that the quality of service for the stream of packets is good and control returns to task  202 . In contrast, when the quality-of-service score R(t) is less than the quality-of-service threshold T(t), then source node  101 - 1  infers that the quality of service for the stream of packets is not good. In other words, that the stream of packets needs to be re-directed. In this case, control passes to task  204 . A time-lapsed diagram comparing R(t) and T(t) is depicted in  FIG. 4 , which shows R(t) falling below T(t) at moment t 2 . 
         [0028]    At task  204 , source node  101 - 1  waits a random interval of time before proceeding to task  205 . This interval is depicted as between moment t 2  and moment t 3  in  FIG. 4 . The purpose of task  204  is to remediate the situation in which congestion in packet network  100  simultaneously causes many streams of packets to fall through their respective quality-of-service thresholds and many nodes try to simultaneously seek alternative paths for those streams. Put another way, the random interval is analogous to having soldiers break cadence when crossing a bridge. It will be clear to those skilled in the art how to make and use embodiments of the present invention that perform task  204 . 
         [0029]    At task  205 , at moment t 3  as depicted in  FIG. 4 , source node  101 - 1  seeks a second alternative path for the stream of packets and, as a consequence, re-directs the stream of packets to be re-directed off of second relay node  101 - 4  en route to destination node  101 - 2 . As part of task  205 , the probationary timer that is associated only with the stream of packets is reset and the probationary period begins again. It will be clear to those skilled in the art how to make and use embodiments of the present invention that perform task  205 . From task  205 , control returns to task  202 . 
         [0030]    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.