Abstract:
An advance is made over the prior art in accordance with the principles of the present invention that is directed to a new approach for a system and method of Single Rate Three Color Marker (srTCM) and Two Rate Three Color Marker (trTCM) methodology. The invention eliminates deficiencies present in existing standards that allow a user to defeat the traffic meter that is used to ensure bandwidth usage is within limits imposed by the provider. Adoption of these invention will ensure compliance with the goals of an ideal Single Rate Three Color Marker (srTCM) and Two Rate Three Color Marker (trTCM) scheme.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application claims priority of Provisional Application Ser. No. 61/203,929 which was filed Dec. 30, 2008. 
    
    
     TECHNICAL FIELD 
     This invention relates generally to communications systems and more particularly to traffic conditioners for packet communications systems. 
     BACKGROUND OF THE INVENTION 
     RFC 2697 and RFC 2698 define a Single Rate Three Color Marker (srTCM) and Two Rate Three Color Marker (trTCM), respectively, which can be used as components in a Diffserv traffic conditioner [RFC2475, RFC2474]. 
     A meter and a marker process each incoming packet stream. The Meter operates in one of two modes. In the Color-Blind mode, the Meter assumes that the packet stream is uncolored. In the Color-Aware mode the Meter assumes that some preceding entity has pre-colored the incoming packet stream so that each packet is either green, yellow, or red. The Marker (re)colors an IP packet according to the results of the Meter. The color is coded in the DS field (RFC 2474) of the packet in a PHB (Per-Hop Behavior) specific manner 
     RFC 2697 provides the standard for existing solutions of the srTCM and RFC 2698 provides the standard for existing solutions of the trTCM. 
     SUMMARY OF THE INVENTION 
     An advance is made over the prior art in accordance with the principles of the present invention that is directed to a new approach for a system and method of Single Rate Three Color Marker (srTCM) and Two Rate Three Color Marker (trTCM) methodology. By adopting improved methodologies on bandwidth allocation, the present invention is able to ensure bandwidth usage is within limits imposed by the provider. 
     One embodiment of the invention includes a method of operating a traffic conditioner in a packet communications network. The traffic conditioner outputs a marked packet stream from an output of the traffic conditioner and includes at least one token bucket having respective first and second token counts and respective first and second token parameter sizes, wherein said token counts arc updated in accordance with at least one information rate. The method includes the steps of incrementing the first token count by one if the first token count is less than the first token parameter size and incrementing the second token count if the second token count is less than the second token parameter size. If the first token count is greater than or equal to the first parameter size then the first token count is not incremented and if said second token count is greater than or equal to the second token parameter size, then said second token count is not incremented. 
     When a packet of size B bytes arrives at time t, the traffic conditioner operates in a color blind mode as follows: if the first token count at time t minus B is greater than zero, the packet is colored green and both the first token count and second token count are decremented by B down to a minimum value of zero, else; if the second token count at time t minus B is greater than zero, the packet is colored yellow and both the first token count and second token count decremented by B down to a minimum value of zero, else; the packet is colored red and neither the first token count nor the second token count is decremented. 
     The traffic conditioner operates in a color aware mode when a packet of size B bytes arrives at time t, in accordance with the following steps: if the packet is pre-colored as green and the first token count at time t minus B is greater than zero, the packet is colored green and both the first token count and second token count are decremented by B down to a minimum value of zero, else; if the packet has been pre-colored as green or yellow and the second token count at time t minus B is greater than zero, the packet is colored yellow and both the first token count and second token count decremented by B down to a minimum value of zero, else; the packet is colored red and neither the first token count nor the second token count is decremented. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWING 
       The teachings of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which: 
         FIG. 1  shows an exemplary embodiment of a traffic conditioner for implementing the methodology of the present invention; 
         FIGS. 2A ,  2 B and  3 A and  3 B show marking results for exemplary packet streams inputted to the srTCM; 
         FIG. 4  shows an exemplary embodiment of a traffic conditioner for implementing the methodology of the present invention; and 
         FIGS. 5A and 5B  and  6 A and  6 B show marking results for exemplary packet streams inputted to the trTCM. 
     
    
    
     DETAILED DESCRIPTION 
     Exemplary embodiments of the invention will now he described while referring to the figures, several of which may be simultaneously referred to during the course of the following description. 
     SINGLE RATE THREE COLOR MARKER 
     Referring to  FIG. 1 , there is shown one exemplary embodiment of a traffic conditioner  100  that includes components of a meter  110  and marker  120  for use within the traffic conditioner. 
     As described in the background section, the meter  110  operates in one of two modes. In a Color-Blind mode, the meter assumes that a packet stream  130  entering the traffic conditioner is uncolored. In a Color-Aware mode the meter  110  assumes that some preceding entity has pre-colored the incoming packet stream  130  so that each packet is either green, yellow, or red as the communications traffic exits in a marked packet stream  140 . As would be understood by those skilled in the art, a traffic conditioner may operate in connection with a processor  150  that receives and processes instructions from memory  160  or some other source. The details of the pre-coloring process, including handling of error scenarios, and how the meter determines the color of a pre-colored packet are DS domain specific and outside the scope of this document. 
     The marker  120  (re)colors an IP packet according to the results of the meter  120 . The color is coded in the DS field (RFC 2474) of the packet in a PHB (per hop behavior) specific manner 
     Configuration 
     The srTCM is configured by setting its mode and by assigning values to three traffic parameters: a Committed Information Rate (CIR), a Committed Burst Size (CBS), and a Peak Burst Size (PBS). The goal is to always allow traffic at or below the CIR, and to permit a maximum packet burst of size CBS without any effect on the traffic (colored green). Packet bursts exceeding CBS, but not exceeding PBS, should still be permissible, but with caveats (colored yellow). Packet bursts exceeding PBS should be flagged as exceeding the parameters of the meter (colored red). 
     The CIR is measured in bytes of IP packets per second, i.e., it includes the IP header, but not link specific headers. The CBS and the PBS and are measured in bytes. The CBS and PBS must be configured so that at least one of them is larger than 0. It is recommended that when the value of the CBS or the PBS is larger than 0, it is larger than or equal to the size of the largest possible IP packet in the stream. 
     Metering 
     The behavior of the meter  12  is specified in terms of its mode and two token buckets, C and E, which both share the common rate CIR. The maximum size of the token bucket C is CBS and the maximum size of the token bucket E is PBS. 
     The token buckets C and E are initially (at time 0) full, i.e., the token count Tc(0)=CBS and the token count Tp(0)=PBS. Thereafter, the token counts Tc and Tp are updated CIR times per second as follows:
         1. If Tc is less than CBS, Tc is incremented by one.   2. If Tp is less than PBS, Tp is incremented by one.   3. If Tc&gt;=CBS (or Tp&gt;=PBS), then Tc (or Tp) is not incremented.       

     When a packet of size B bytes arrives at time t, the following happens if the srTCM is configured to operate in the Color-Blind mode:
         1. If Tc(t)−B&gt;=0, the packet is green and both Tc and Tp are decremented by B down to the minimum value of 0, else   2. if Tp(t)−B&gt;=0, the packet is yellow and both Tc and Tp are decremented by B down to the minimum value of 0, else   3. the packet is red and neither Tc nor Tp is decremented.       

     When a packet of size B bytes arrives at time t, the following happens if the srTCM is configured to operate in the Color-Aware mode:
         1. If the packet has been pre-colored as green and Tc(t)−B&gt;=0, the packet is green and both Tc and Tp arc decremented by B down to the minimum value of 0, else   2. If the packet has been pre-colored as green or yellow and if Tp(t)−B&gt;=0, the packets is yellow and both Tc and Tp are decremented by B down to the minimum value of 0, else   3. the packet is red and neither Tc nor Tp is decremented.
 
Difference from Related Work
       

     The above three algorithms (increasing counters, Color-Blind operation, Color-Aware operation) are improved from those presented in RFC 2697, and address the deficiencies found in the algorithms of the RFC. RFC 2697 refers to the PBS as Excess Burst Size (EBS). Here is why the algorithms in the RFC require improvement: 
     As the inventors have realized, the term EBS in RFC 2697 is not equal PBS−CBS, as the name ‘Excess Burst Size’ might lead one to believe. It is in fact the same as PBS. To see this, assume EBS=PBS−CBS. In RFC 2697, Tc and Te are not updated simultaneously. Tp is updated only if Tc is full (up to CBS). Given that the Te bucket size is EBS, let the initial values at time 0 for CBS and EBS be 100 and 10 bytes respectively. As illustrated in  FIG. 2A , a chart  200  is shown illustrating a sequence of packets and a corresponding token count as the sequence would be processed by the prior art traffic to conditioner of RFC 2697. As shown, if a burst of three packets of size 55, 50, 45 bytes each are presented at time 0, the first packet will he colored green, the second packet will be colored red and the third packet will be colored green. Referring to  FIG. 2B , a chart  210  is shown for the same sequence of packets described with respect to  FIG. 2A . Here a preferred srTCM marker in accordance with the present invention will color the first packet green, second packet yellow, and the third packet as red. Thus, one can construe that RFC 2697 does consider EBS=PBS. 
     However, if we assume this to be the case, then both the Color-Blind and Color-Aware metering algorithms presented in RFC 2697 (referred henceforth as old-CB and old-CA algorithms) will result in a maximum burst of size (CBS+EBS) being sent out of the meter marked green or yellow, as opposed to only a max burst of size EBS. 
     At time 0, for example, if a burst of size CBS+EBS was presented to the old-CB algorithm, then the first CBS bytes worth of packets will be colored green and the next EBS bytes worth of packets will be colored yellow. The same behavior is seen in the old-CA algorithm when the burst is colored green. The ideal behavior in this example is that the first CBS bytes worth of packets should be colored green, and the next (EBS−CBS) bytes worth of packets should be colored yellow, while the remaining CBS bytes worth of packets in the burst should be colored red. Our proposed algorithms (new-Updater, new-CB and new-CA) will ensure the correct behavior, as can be seen from the description of these above. 
     The situation can be exacerbated depending on the packet sizes and the size of the burst.  FIGS. 3A and 3B  show charts  300 ,  310  illustrated the processing of another exemplary sequence of packets utilizing, respectively, the old-CB and old-CA versus the new-CB and new-CA algorithms of the present invention. If Tc(t)=100, Te(t)=110, then let the burst, at time t, contain packets of size 51, 50, 25, 25, 13, 13, all of them colored green. The old-CB algorithm and old-CA algorithm will color these packets G, Y, G, Y, G, Y as shown by chart  300  of  FIG. 3A . In accordance with the present invention, a preferred coloring for a srTCM should he G, Y, R, R, R, R as in chart  310  of  FIG. 3B . 
     It is important to note that these differences, while subtle, can allow manipulation of traffic meters by malicious users. This can defeat the purpose of traffic metering and marking policies. Moreover, the prior art methodology has significant disadvantages when compared to the methodology of the present invention, because the order of errored packets is much different than what one would expect for a closer to ideal implementation. For instance, with respect to  FIG. 3A  and chart  300 , one can see that a user can end up sending more packets through the system than what the system intends (by the choice of Tc and Te). In  FIG. 3A  chart  300 , no packets will be dropped if the system was trying to drop only Red packets. If it was dropping yellow packets, three packets will get through. However, the correct quota for the user traffic burst is only two packets, if dropping only red, or one packet if dropping yellow and red. 
     Alternate Implementation 
     A different way of implementing this is to use a single bucket with two parameters: CBS and PBS. The behavior of the Meter is now specified in terms of its mode and one token bucket, C, with the rate CIR. The maximum size of the token bucket C is PBS. 
     TWO RATE THREE COLOR MARKER 
     With respect to the Two Rate Three Color Marker, there is shown in  FIG. 4 , a traffic conditioner  400  having a meter  410  and a marker  420  that processes each incoming packet stream  430  in order to produce a marked packet stream  440 . As with the Single Rate Three Color Marker, the Two Rate Three Color Marker traffic conditioner  400  may operate in connection with a processor  450  that receives and processes instructions from memory  460  or some other source. 
     The meter  410  operates in one of two modes. In the Color-Blind mode, the meter  410  assumes that the packet stream  430  is uncolored. In the Color-Aware mode the meter assumes that some preceding entity has pre-colored the incoming packet stream so that each packet is either green, yellow, or red. The details of the pre-coloring process, including handling of error scenarios, and how the meter determines the color of a pre-colored packet are DS domain specific and outside the scope of this document. 
     The marker  420  (re)colors an IP packet according to the results of the meter  410 . The color is coded in the DS field (RFC 2474) of the packet in a PHS specific manner. 
     Configuration 
     The trTCM is configured by setting its mode and by assigning values to four traffic parameters: a Peak Information Rate (PIR) and its associated Peak Burst Size (PBS) and a Committed Information Rate (CIR) and its associated Committed Burst Size (CBS). The goal is to always allow traffic at or below the CIR, and to permit a maximum packet burst of size CBS without any effect on the traffic (colored green). Packet bursts exceeding CBS, but not exceeding PBS, should still be permissible, but with caveats (colored yellow). The same applies for traffic coming in at a rate exceeding CIR, but not exceeding PIR (colored yellow). Packet bursts exceeding PBS, and packet rates exceeding PIR should be flagged as exceeding the parameters of the meter (colored red). 
     The PIR and CIR are measured in bytes of IP packets per second, i.e., this includes the IP header, but not link specific headers. The PIR must be equal to or greater than the CIR. The CBS and the PBS are measured in bytes. The CBS and PBS must be configured so that both of them are larger than 0. It is recommended that when the value of the CBS or the PBS is larger than 0, it is larger than or equal to the size of the largest possible IP packet in the stream. Note that PBS&gt;=CBS. 
     Metering 
     The behavior of the meter  410  is specified in terms of its mode and two token buckets, P and C, with rates PIR and CIR, respectively. The maximum size of the token bucket P is PBS and the maximum size of the token bucket C is CBS. 
     The token buckets P and C are initially (at time 0) full, i.e., the token count Tp(0)=PBS and the token count Tc(0)=CBS. Thereafter, the token count Tp is incremented by one PIR times per second up to PBS and the token count Tc is incremented by one CIR times per second up to CBS. 
     When a packet of size B bytes arrives at time t, the following happens if the trTCM is configured to operate in the Color-Blind mode:
         1. If Tc(t)−B&gt;=0, the packet is green and both Tc and Tp are decremented by B down to the minimum value of 0, else   2. if Tp(t)−B&gt;=0, the packet is yellow and both Tc and Tp is decremented by B down to the minimum value of 0, else   3. the packet is red and neither Tc nor Tp is decremented.
 
When a packet of size B bytes arrives at time t, the following happens if the trTCM is configured to operate in the Color-Aware mode:
   1. If the packet has been pre-colored as green and Tc(t)−B&gt;=0, the packet is green and both Tc and Tp are decremented by B down to the minimum value of 0, else   2. If the packet has been pre-colored as green or yellow and if Tp(t)−B&gt;=0, the packets is yellow and both Tc and Tp are decremented by B down to the minimum value of 0, else   3. the packet is red and neither Tc nor Tp is decremented.
 
Difference from Related Work
       

     The algorithms for Color-Blind operation and Color-Aware operation are improved from those presented in RFC 2698, and address the deficiencies found in the algorithms of the RFC. Here is why the algorithms in the RFC require improvement: 
     In RFC 2698, the Color-Blind and Color-Aware metering algorithms presented in RFC 2698 will be referred henceforth as old-CB and old-CA algorithms. At time 0, for example, let Tc(t)=100, Tp(t)=110, and let the burst, at time t, contains packets of size 51, 50, 19, all of them colored gem. Referring to  FIGS. 5A and 5B  and charts  500 ,  510 , it can be seen that the old-CB algorithm and old-CA algorithm will color these packets G, Y, G, while in accordance with the present invention and an essentially ideal algorithm, the coloring for a trTCM should be G, Y, R. This improved behavior is replicated by the algorithms set forth in accordance with the present invention. 
     RFC 4115 proposes an alternative to RFC 2698, attempting to address some of the issues in the previous standard. Here, the meter is specified in terms of a committed information rate (CIR) and an excess information rate (EIR). CIR and EIR define the token generation rate of a token bucket with a size that is equal to the committed burst size (CBS) and ‘excess’ burst size (EBS), respectively. The EIR and EBS are related to PIR and PBS as follows: EIR=PIR−CIR, EBS=PBS−CBS. 
     Now, let Tc(t)=100, Te(t)=20, (ignore EIR and CIR), with a burst of 4 packets of size 26 bytes each. As shown in  FIGS. 6A and 6B  and charts  600 ,  610 , the RFC 4115 algorithm colors the packets as G, G, G, R, while the algorithm in accordance with the present invention would color them as G, G, G, Y. If all these incoming packets were colored yellow, then the RFC 4115 algorithm would color them all red, but the ideal algorithm will color them all yellow. The methodology of the present invention replicates an essentially ideal algorithm behavior in all these cases. 
     In RFC 4115, if one interprets the EBS to be the same as PBS and EIR to be the same as PIR, then a worse problem arises, wherein the RFC 4115 algorithm will allow (i.e., color packets green or yellow) a maximum burst of PBS+CBS if presented at time 0, instead of the maximum burst of PBS. While both interpretations are possible, implementers use the former interpretation of EBS=PBS−CBS and EIR=PIR−CIR. 
     It is important to note that these differences, while subtle, can allow manipulation of traffic meters by malicious users. This can defeat the purpose of traffic metering and marking policies. As with the Single Rate Three Color Marker invention, the present invention is a significant improvement over the prior art, since the error order of a marked packet stream and the amount of information that is required to be retransmitted in the case of packets being dropped (colored red) may be significantly reduced. 
     Alternate Implementation 
     A different way of implementing this aspect of the present invention is to use a two token buckets, Tc and Te, with four parameters: CIR, EIR, CBS and EBS, where EIR=PIR−CIR, and EBS=PBS−CBS. The behavior of the Meter is now specified as follows: 
     The token buckets C and E are initially (at time 0) full; i.e., the token count Tc(0)=CBS and Te(0)=EBS. Thereafter, the token count Tc is incremented by one CIR times per second (up to CBS), and the token count Te is incremented by one EIR times per second (up to EBS). 
     The Color-Aware mode is specified as follows:
         1. If the packet has been pre-colored as green and Tc(t)−B&gt;=0, the packet is green and Tc is set to max(0, Tc(t)−B), else   2. If the packet has been pre-colored as green or yellow and if Tc(t)+Te(t)−B&gt;=0, the packet is yellow and Te is set to max(0, Te(t)−B) and Tc is set to max(0, min(Tc(t), Tc(t)−B+Te(t))), else   3. the packet is red and neither Tc nor Te is decremented.       

     In the Color-Blind mode of operation, all incoming packets are treated as colored green, and the above algorithm is applied. The benefit of using the EIR bucket instead of the PIR bucket is that the clock rates needed to support EIR are much slower and hence consume lower power and reduce processor load. 
     The foregoing description merely illustrates the principles of the invention. It will thus be appreciated that those skilled in the art will he able to devise various arrangements, which, although not explicitly described or shown herein, embody the principles of the invention, and are included within its spirit and scope. Furthermore, all examples and conditional language recited are principally intended expressly to be only for instructive purposes to aid the reader in understanding the principles of the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions. Moreover, all statements herein reciting principles, aspects, and embodiments of the invention, as well as specific examples thereof, are intended to encompass both structural and functional equivalents thereof. Additionally, it is intended that such equivalents include both currently known equivalents as well as equivalents developed in the future, i.e., any elements developed that perform the same function, regardless of structure. Many other modifications and applications of the principles of the invention will be apparent to those skilled in the art and are contemplated by the teachings herein. Accordingly, the scope of the invention is limited only by the claims.