Abstract:
The present invention provides a system and method for prioritizing delay-sensitive packets relative to each other for transmission from a router in a network, based on a delay variation estimated for each delay-sensitive packet by a quality of service monitor. In accordance with the present invention, late delay-sensitive packets are assigned a higher priority than, and are transmitted before, other delay-sensitive packets, thereby reducing the level of jitter and improving the quality of the packet streams that comprise late delay-sensitive packets.

Description:
RELATED APPLICATION 
     This application claims the benefit of priority of U.S. provisional application Ser. No. 60/638,368, filed Dec. 20, 2004, which is relied on and incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to network routing systems and methods. More specifically, the present invention relates to a system and method for prioritizing packets at a router for transmission in a network. 
     BACKGROUND OF THE INVENTION 
     Multimedia traffic, such as Voice over IP, can experience quality problems due to network congestion. This typically results in an increase in jitter—the variation in transmission delay of individual packets. Jitter can lead to degradation in the quality of a transmitted voice or video signal being transported in packet format over an IP network. 
     To improve the quality multimedia signals, it is known to prioritize delay-sensitive, real-time traffic, such as Voice over IP data that uses RTP (Real Time Transfer Protocol) or another suitable real-time protocol, over less time critical traffic, such as web access, email, or other data traffic.  FIG. 1  shows a conventional system  10  for implementing such a class-based prioritization scheme. Packets  3  arrive in an input queue  2  at a router  4  and wait to be processed. During processing of each packet  3 , the router  4  inspects information in a header of the packet to determine a destination address for the packet (e.g., a destination IP address). The router  4  then compares the destination address to a routing table that lists known destination addresses. The routing table associates each known destination address with an output link at the router  4  and with an output priority. After finding an entry in the routing table that includes the destination address for the packet, the router  4  stores the packet in an output queue that is associated with the output link and the output priority listed for the destination address. 
     In a conventional class-based queuing system, the router  4  also classifies the packet based on the type of data the packet contains and stores the packet in an output queue associated with the class of the packet. Thus, the router  4  may include multiple output queues, one for each class of packet or for each priority of traffic. For instance, the router  4  may include an RTP class queue  6  and a data class queue  8 , wherein the RTP class queue  6  is given priority over the data class queue  8 . 
     This approach can be effective, provided the proportion of real-time traffic is relatively low. If the proportion of real-time traffic is relatively high, this approach is ineffective because the delay-sensitive packets are not prioritized relative to each other and may be indiscriminately dropped in response to congestion. An ideal method would be to prioritize packets at an individual stream level, however this has been impractical to implement. 
     A need therefore exists for an improved solution to this problem that is scalable to very large networks. 
     SUMMARY OF THE INVENTION 
     The present invention answers this need by providing a system and method wherein delay-sensitive packets are identified and prioritized relative to each other, based on a delay variation estimated for each delay-sensitive packet by a quality of service monitor. 
     It is thus an object of the present invention to provide a system and method for prioritizing packets at a router for transmission in a network wherein late delay-sensitive packets are assigned a higher priority than, and are transmitted before, other delay-sensitive packets, thereby reducing the level of jitter and improving the quality of the packet streams that comprise late delay-sensitive packets. 
     Further objects, features and advantages will become apparent upon consideration of the following detailed description of the invention when taken in conjunction with the drawing and the appended claims. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a relational diagram showing a conventional system for implementing a class-based packet prioritization scheme. 
         FIG. 2  is a relational diagram showing a system for prioritizing packets in an embodiment of the present invention. 
         FIG. 3  is a relational diagram showing a system for prioritizing packets in another embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     With reference to  FIG. 2 , a system  20  in accordance with the present invention is shown for prioritizing packets received by a router  36  in a network. The router  36  may be any commercially available router that stores and forwards packets from one network, such as a LAN (Local Area Network) or WAN (Wide Area Network), to another. Thus, as previously described, packets  21  are received in an input queue  22  on the router  36  and each packet is processed by the router  36  for routing to its destination address. 
     In accordance with the present invention, a monitor  32  is provided at the router  36  for monitoring individual streams of packets for quality. Further, a priority manager  34  is provided at the router  36  for prioritizing the transmission of the packets from the router  36  based on quality measurements obtained by the monitor  32 . 
     Monitor. 
     The monitor  32  analyzes each packet and determines whether the packet is delay-sensitive, i.e., whether the packet uses RTP or another suitable real-time protocol. If the packet is delay-sensitive, the monitor  32  estimates a delay variation for the packet. The delay variation, or jitter, for a packet is a metric that describes and quantifies whether the packet arrived early, on-time, or late with respect to an “ideal” arrival time. 
     As known in the art, delay-sensitive packets are transmitted from a source, such as an IP phone, a media gateway, a videoconferencing system, or the like, to a destination at regular intervals in a continuous packet stream. Accordingly, the packets are evenly spaced apart and have a constant delay when they leave the source. However, due to congestion or other problems in the network the delay between each packet may vary at when they reach the router  36 , located between the source and the destination. Timestamps and sequence numbers transmitted with each packet are used by the monitor  32  at the router  36  to determine the ideal arrival time, based on a constant delay. The monitor  32  then compares the ideal arrival time with an actual arrival time at the router  36  to determine whether any variation in the delay between packets in the individual packet stream has occurred. 
     Thus, in accordance with an embodiment of the present invention, the monitor  32  calculates the ideal arrival time for a packet by subtracting the timestamp for an earlier packet in the packet stream from the timestamp for the current packet, and then adding this time difference to the actual arrival time measured for the packet. Using this information, the monitor  32  estimates the delay variation for the packet by subtracting the actual arrival time of the packet from the ideal arrival time of the packet. The monitor  32  then outputs the delay variation to the priority manager  34  for use in prioritizing the delay-sensitive packet, as described in further detail below. 
     The delay variation may also be used by the monitor  32  to perform various quality of service monitoring functions as known in the art. Because it is advantageous to provide a quality of service monitor at a router for monitoring the quality of delay-sensitive traffic and to estimate the delay variation of packets as part of such monitoring functionality, the present invention may provide beneficial priority management functions using existing quality of service information. 
     In various embodiments, the monitor  32  is a commercially available quality of service monitor such as VQmon, which is available from Telchemy, Incorporated. (“VQmon” is a trademark of Telchemy, Incorporated.) VQmon is more fully described in U.S. Pat. No. 6,741,569 entitled “Quality of Service Monitor for Multimedia Communications System,” U.S. patent application Ser. No. 09/574,472 entitled “Dynamic Quality of Service Monitor,” and U.S. patent application Ser. No. 10/802,536 entitled “Quality of Service Monitor for Multimedia Communications System,” which are incorporated herein by reference. 
     Priority Manager. 
     The priority manager  34  uses the delay variation estimated by the monitor  32  to prioritize the delay-sensitive packet for transmission from the router. In one embodiment, the priority manager  34  prioritizes the delay-sensitive packet using a plurality of sub-class output queues. In another embodiment, the priority manager  34  prioritizes the delay-sensitive packet using at least one insertion queue. 
     1. Sub-Class Queues. 
     With continuing reference to  FIG. 2 , the priority manager  34 , or the router  36  using a known class-based priority scheme, assigns the delay-sensitive packet to a delay-sensitive class and passes the delay-sensitive packet to a delay-sensitive queue associated with the delay-sensitive class. The priority manager  34 , or the router  36 , assigns each packet determined by the monitor  32 , or the router  34 , not to be delay-sensitive, i.e., to be a data packet, to one of a plurality of data classes and passes the data packet to a data queue  44  associated with the data class. 
     The delay-sensitive queue comprises a plurality of sub-class queues  41 , wherein each sub-class queue  41  is associated with a weight. The weight is associated with the estimated delay variation of the delay-sensitive packet. The priority manager  34  assigns the delay-sensitive packet to the appropriate sub-class queue  41  based on the delay variation estimated by the monitor  32 . 
     For example, the following Weights may be used: 
     
       
         
               
               
               
             
           
               
                   
                   
               
               
                   
                 Weight 
                 Delay Variation 
               
               
                   
                   
               
             
             
               
                   
                 0 
                 Less than 10 milliseconds 
               
               
                   
                 1 
                 11-20 milliseconds 
               
               
                   
                 2 
                 21-40 milliseconds 
               
               
                   
                 3 
                 41-80 milliseconds 
               
               
                   
                 4 
                  81-120 milliseconds 
               
               
                   
                 5 
                 121 or more milliseconds 
               
               
                   
                   
               
             
          
         
       
     
     In accordance with such an embodiment, the delay-sensitive queue would comprise six sub-class queues, one sub-class queue associated with each weight. The sub-class queue having a weight of 5 is given the highest priority. Thus, for example, a first delay-sensitive packet having an estimated delay variation of 130 milliseconds would be transmitted from the router  36  before a second delay-sensitive packet having an estimated delay variation of 89 milliseconds. 
     2. Insertion Queue 
     In another embodiment, and with reference to  FIG. 3 , the priority manager  34  passes each delay-sensitive packet to an insertion queue  42  based on the delay variation estimated by the monitor  32 . In particular, the priority manager  34  may compare the delay variation of the delay-sensitive packet to the delay variation of the delay-sensitive packets previously passed to the insertion queue and insert the delay-sensitive packet into the insertion queue ahead of any delay-sensitive packets having a lower positive or a negative delay variation. Thus, delay-sensitive packets with the highest delay variation are transmitted first from the router  36 . The priority manager passes each packet determined by the monitor  32 , or the router  34 , not to be delay-sensitive, i.e., to be a data packet, to one of a plurality of data queues  44 , wherein the delay-sensitive queue  42  is given a higher priority than the data queues  44 . 
     Consequently, the present invention identifies individually late delay-sensitive packets and effectively shares the delay across multiple packet streams. Although such a solution may make the quality of each stream slightly worse, if there are a sufficient number of packet streams such an impact is minimal. 
     While this invention has been described with reference to preferred embodiments thereof, it is to be understood that variations and modifications can be affected within the spirit and scope of the invention as described herein and as described in the appended claims.