Asynchronous Transfer Mode (ATM) associates a traffic contract with every individual cell stream or virtual circuit. A traffic contract is a formal characterization of the desired emission behavior (if you are traffic shaping) or expected arrival behavior (if you are traffic policing) of an event stream. ATM isn't the only technology to use traffic contracts as one of the mechanisms to provide quality of service (QOS); Frame Relay comes to mind, and IP is also slowly providing similar capabilities, particularly for QOS sensitive applications like Voice Over IP (VOIP). But ATM is the one with which I am the most familiar, and its relatively simple traffic contracts are easily adaptable to other applications, from embedded systems to enterprise Service Oriented Architectures (SOA).
ATM offers several classes of service, but the three that I dealt with exclusively in my work were unspecified bit rate (UBR), constant bit rate (CBR), and variable bit rate (VBR). Each class of service has its own particular form of traffic contract.
The UBR contract is really no contract at all. The event stream makes no promises about how it will behave, and the network makes no promises that any of your events will get to their destination. If the network gets congested, the events in the UBR streams are the first to go. UBR event streams get no respect, but they are also the cheapest to lease from the network service provider, since everything is strictly best effort. Most IP traffic tunnelled over an ATM network is sent UBR. UBR is effectively what you are using if you are not policing or shaping traffic at all in your application.
The CBR contract is the simplest real traffic contract. The event stream guarantees that it will never send events above a specified rate, more or less, and the network guarantees that it will not drop the events in the stream as long as the stream abides by its contract. The problem with CBR contracts is that they are expensive. In order to meet the traffic contract, the network has to reserve the peak bandwidth specified in the traffic contract at all times. Customers paying for CBR service pay for the full bandwidth, 24x7, whether they use it or not. The only applications which really make sense for CBR service are highly time-synchronized event streams of a constant rate, like uncompressed voice, which is exactly what we used it for in the applications on which I worked. Voice encodings like G.711 send an eight-bit voice sample eight thousand times a second whether or not you are speaking. In ATM, because CBR traffic is often very jitter sensitive it typically is transmitted through the network at a very high priority, something like a Presidential motorcade with police escort running all the red lights.
Somewhere in between UBR and CBR is VBR. VBR is a complex traffic contract in which the event stream guarantees that it will never send events above a specified rate, that it will on average send at a typically much lower rate, and if it does send at the higher rate, it will limit the number of events it will send before returning to sending at a lower rate. VBR event streams get higher priority than UBR streams, cost less than CBR streams, and are allowed to occasionally burst at a higher rate when the situation demands it. In the application I worked on, we sent control messages through VBR streams. The control messages got priority over any UBR (typically IP) traffic, yet were guaranteed not to interfere with the CBR voice traffic. If some heavy-duty messaging was required, the VBR stream could briefly emit bursts of messages at a higher rate to clear its buffers. A typical application for the VBR class of service is compressed video.
The parameters of both the CBR and VBR traffic contracts are mapped into the parameters increment (i) and limit (l) of the Generic Cell Rate Algorithm (GCRA), which I described in such detail in my article by the same name that the reader's eyes will probably bleed. The literature uses the notation
GCRA(i,l)
when defining this mapping.
The traffic contract associated with the CBR class of service has two parameters: the peak cell rate (PCR) in cells per second, and the cell delay variation tolerance (CDVT) in microseconds. Of course, when you adapt the CBR traffic contract to your own application, you'll use whatever units you find convenient. The PCR places an upper bound on the bandwidth used by the event stream. The CDVT provides some slack in the contract to accommodate jitter.
The CBR traffic contract is simply mapped by computing the increment as
1/PCR
because the inverse of the rate is the inter-arrival time, which is what the increment is, and using the CDVT directly as the limit. This is represented as
GCRA(1/PCR, CDVT)
in our notation.
Of course we don't literally compute the reciprocal of the PCR, because that gives us a result in units of a fraction of a second. We divide it into the number of ticks per second in whatever time units we are using. If we are using microseconds in our implementation of the GCRA, then we compute
1 000 000/PCR
to get the increment in microseconds. The choice of time unit for a clock tick, or equivalently the choice of frequency, of our GCRA implementation depends on several factors, for example, the dynamic range of the data type we are using to store time durations in ticks, the maximum rates we need to support, the granularity of the underlying clock in our application, and the maximum time intervals we need to compute. I have implemented GCRA and other rate control algorithms using milliseconds, microseconds, nanoseconds, and CPU clock ticks, and used both 32-bit and 64-bit arithmetic. There is no right answer for all applications, and frequently the correct choice is a compromise that may limit the rate control algorithm in terms of its precision, accuracy, or performance.
The traffic contract associated with the VBR class of service has four parameters: the same PCR and CDVT as for CBR, plus the sustained cell rate (SCR) in cells per second, and the maximum burst size (MBS) in cells. The SCR is the long term average rate of the event stream. The MBS is the largest number of events the event stream can burst at PCR. The VBR contract uses two GCRAs, one that enforces the PCR and the CDVT, and one that enforces the SCR and the MBS. The VBR event stream must conform to both contracts simultaneously.
The first GCRA
GCRA(1/PCR, CDVT)
is the same as the contract used for the CBR class of service. The increment for the second contract is easy: it's the recipricol of the SCR, or
1/SCR
just as with the PCR. The event stream isn't restricted to just emitting at either PCR or SCR. It can emit events at any rate from zero to PCR. This is accommodated by computing a burst tolerance (BT). The BT is computed as
(MBS - 1) * ((1/SCR) - (1/PCR))
where
((1/SCR) - (1/PCR))
is the difference in inter-arrival times between events emitted at SCR and events emitted at PCR, and
(MBS - 1)
is the number of intervals between MBS cells. (There's actually a more complicated explanation for this formula that has to do with the fact that BT is not computed from MBS but rather vice versa, but let's stick with this simpler version for now.) The VBR contract is represented as
GCRA(1/SCR, CDVT + BT)
or equivalently
GCRA(1/SCR, CDVT + ((MBS-1) * ((1/SCR) - (1/PCR))))
where the quantity
CDVT + BT
is the limit. Why do we add CDVT? Because it is perfectly valid for SCR to equal PCR. (I remember vividly having to explain this at length to an engineer for another ATM switch vendor, and why this wasn't equivalent to the CBR class of service in typical ATM chip sets. I may have climbed on my soapbox and waved the TM 4.0 spec around. I apologize if you are reading this.) If this is the case, then unless we add CDVT, the second GCRA becomes
GCRA(1/SCR, 0)
or, because PCR==SCR, equivalently
GCRA(1/PCR, 0)
which is a more restrictive traffic contract than the first GCRA, which is clearly not our intent. What we really want is for the PCR==SCR case to degenerate to
GCRA(1/PCR, CDVT)
and adding the CDVT to the BT accomplishes this. (I didn't find the TM 4.0 specification to be terribly clear on this. It wasn't until I was debugging my traffic shaping firmware with a broadband network analyzer that cost more than I made in a year that I figured this out.)
The Digital Aggregates Buckaroo open source library of Java classes implements the GCRA as a Throttle in the class GenericCellRateAlgorithm with a tick of one microsecond, and that class can be used directly if you care to figure out your own increment and limit parameters. The class CellRateThrottle uses one or two GenericCellRateAlgorithm objects to provide either a CBR or a VBR traffic contract, depending on what constructor you use. These classes are useful for rate controlling in terms of events per second, for example messages per second, packets per second, and the like.
But if you want to emit variable length packets and rate control in terms of bytes per second, calling the methods in these classes for every byte in a packet is not efficient. The classes BandwidthAlgorithm and BandwidthThrottle extend the prior classes by allowing you to specify a traffic contract in terms of bytes per second, using a tick of one nanosecond, and indicate how many bytes you are going to emit in each packet. Because you are presumably handing your packet to some underlying operating system, or at least device driver, to emit at its own rate, these Throttles exhibit burstier behavior than their more ATM-centric counterparts, but the long term effective emission rate is correct.
The Digital Aggregates Desperado open source library of C++ classes has similar tools, but the Java versions represent a couple more years of pondering on my part. I consider the C++ classes to be deprecated, and will sooner or later port the Java implementations into the C++ library.
I believe that rate control becomes more and more crucial the bigger, more complex, and the more distributed your real-time system becomes. Even if you are implementing, say, an enterprise service bus (ESB) in a single JVM, applying traffic contracts to the various components that may interact with one another is an important step in delivering a scalable, reliable, and predictable system that can be debugged in the lab, troubleshot at a customer site, and understood by others. It is even more important if you are building a true distributed system where many traffic sources may be aggregated into a single traffic sink.
Sources
Buckaroo, Digital Aggregates Corp., 2007
Desperado, Digital Aggregates Corp., 2007
Chip Overclock, "The Generic Cell Rate Algorithm", January 2007
Chip Overclock, "Rate Control Using Throttles", January 2007
Chip Overclock, "Traffic Management", December 2006
N. Giroux, et al., Traffic Management 4.0, tm-0056.000, ATM Forum, April 1996, pp. 62-67
J. L. Sloan, "ATM Traffic Management", Digital Aggregates Corp., August 2005
Wednesday, January 17, 2007
Tuesday, January 16, 2007
The Generic Cell Rate Algorithm
The Generic Cell Rate Algorithm (GCRA) is remarkably adaptable. I first saw it described in the ATM Forum Traffic Management 4.0 specification about a decade ago, when I was writing traffic shaping firmware for ATM equipment at Bell Laboratories. But substitute just about anything for the word cell and you can use the GCRA to shape or police any kind of traffic, from data packets on a socket, to messages between tasks in an embedded system, to solicitations and notifications in a Service Oriented Architecture (SOA). This is why I like to talk about the GCRA as applying more generally to rate controlling events instead of cells, packets, or messages.
TM 4.0 offers two different explanations of how the GCRA works: the leaky bucket and the virtual scheduler. The two explanations are exactly equivalent, but to this day I really do not like term "leaky bucket", because for lots of folks it seems to suggest that there is some kind of data buffering going on when there isn't (or if there is, it isn't the GCRA doing the buffering). So I prefer to use the term "virtual scheduler", even though when I implement the GCRA, I tend to use the leaky bucket flowchart and terminology from TM 4.0.
As I mentioned briefly in my article "Rate Control Using Throttles", the GCRA has but two parameters: the increment and the limit. The increment is the expected inter-arrival time (IAT) between two successive events in an event stream. If you ideally want to transmit one hundred events evenly dispersed over every second, then you are describing a 100Hz event source whose emissions have an IAT of 1/100th of a second. Your increment would be 0.01 seconds. TM 4.0 specifies a time granularity of one microsecond as a standard for ATM traffic contracts, so in that case you would represent that increment as (1 000 000 / 100) or 10 000 microseconds. Of course, you can implement the GCRA in whatever time units you find appropriate for your application: nanoseconds, microseconds, milliseconds, or even some convenient time interval based on the frequency of your CPU clock. For this reason, I like to talk about time in the GCRA in units of ticks. So given an increment of i, the GCRA expects an ideal event source to emit an event every i ticks.
The increment assumes a smooth flow of data. Life is seldom that simple. Neither software, nor firmware, nor even hardware is capable of emitting events with perfect precision (although the old TDM-based land line telephone system sure tried). And once events are handled by other components, for example, nodes on a network, additional variation is inevitably inserted. This is especially true when multiple event sources are aggregated together. The aggregator (for example, a network router) can only emit one event at a time onto the aggregated output channel. So it selects an event from one input channel, hence delaying all the pending events on all the other input channels. It may select the next event to emit based on many factors, such as the quality of service parameters of the traffic contracts of the individual event streams, service level agreements with the event stream owners (a.k.a. paying customers), or simply round-robin.
Because small variations in the expected IAT of events, also known as jitter, are inevitable, a traffic policer implemented using the GCRA must provide for some slack in its traffic contract. This slack is the second parameter, the limit. The limit is the total cumulative time that successive events in an event stream may deviate from the expected IAT. The limit has a number of applications. When the GCRA is used for traffic policing incoming event streams, the limit prevents the policer from dropping events which have been jittered but are still within the tolerance of the limit. This allows, for example, a policer to pass otherwise well behaved event streams just because they got a little rowdy once in a while ("Events will be events" as my sainted mother never said). When used for traffic shaping, the limit allows the shaper to emit events in short bursts where the IAT between a small number of successive events is smaller than the specified increment. This allows, for example, a shaper to drain a perilously full memory buffer onto the network instead of dropping events on the floor.
I should mention here that jitter is quite different from drift, which is a more or less consistent, or at least larger, variation in the IAT than is associated with jitter. A frequent source of drift is a lack of a common time synchronization source between network nodes. This means each node has a different sense of the passage of time, kind of like that episode of Star Trek. Or maybe it was Twilight Zone. Anyway, because the nodes are timed to different clocks, the event source node believes it is emitting events more or less on time, while the event sink node may believe that every single event is arriving a little early. As we shall see, a GCRA used for traffic policing events streams on the sink node has limited patience with drift. Limited in fact by the limit. The limit is a time budget, and every single early event uses up more of that budget. Once the limit is exhausted, the traffic police will start dropping events, or at least marking them for possible deletion downstream, which is a kind of Scarlet Letter in the networking world.
Although it may sound complicated, the typical implementation of the GCRA is simple and efficient. This will be a little more obvious when we see how the increment and the limit play together, and see how little state the GCRA actually has to maintain and what simple calculations it has to do. The discussion below refers to the following set of diagrams, which show various scenarios of an event stream and a GCRA with an increment i and a limit l. (Click on the thumbnail to see a full size version.) Such a GCRA is typically represented in the literature using the notation GCRA(i, l). Yeah, the variables kinda suck, but I'm trying to stick with the TM 4.0 terminology.
Figure [1] shows a time line as the GCRA sees it. It expects to see events E0, E1, etc. arrive evenly spread exactly i ticks apart, where i is the increment.
Figure [2] shows just such a well behaved event stream, with the actual events A0, A1, etc. all arriving exactly on time. These are the kind of events that got beat up in school and called "mama's boys".
Figure [3] shows event A2 arriving j ticks late. A2 is always arriving late, and always has some good excuse: its car broke down, it had to drop the kids of at school, whatever. You would think the GCRA would give the event stream some credit by maybe increasing its limit by j ticks. Or maybe it would penalize event A2. But instead, when an event arrives late, the GCRA shifts the entire time line down so that the IAT of all subsequent events will be measured relative to the new time line established by the late arriving A2.
Figure [4] shows that event A2 has been somehow dropped by the network and was never seen by the GCRA. The GCRA doesn't care one whit about the fact that A2 was dropped. From its perspective, A3 is the next event, and it arrived i ticks late. So once again the time line is shifted down so that the IAT of all subsequent events will be measured relative to the new time line established by the arrival of A3.
Figure [5] shows that although A1 and A3 arrived right on schedule, A2 was jittered in its passage though the network. Because A2 arrived late, the time line is shifted down just as before. Now, even though A3 arrived right on time as far as the original time line was concerned, the GCRA sees it as arriving early from the perspective of the new time line, just k ticks after A2. So while A2 arrived j ticks late, it is A3, which arrived (i-k) ticks early, which may be penalized. The GCRA compares (i-k) to the limit l and if it is less, A3 is not dropped and the event stream goes on its merry way. However, something interesting happens to all subsequent events A4, A5 and on to infinity. Even through they are arriving spot on in terms of the original time line, they are all (i-k) ticks early from the perspective of the new time line. The limit l has been reduced by (i-k) ticks, and will remain so until an event arrives on or after its expected time on the new time line.
Because jitter is a more or less random mechanism, and it is about as likely that events in the same event stream arrive late as they do early, assuming they were emitted with the correct timing from their original event source, this works. When an event arrives early, part of the limit budget is consumed. But when a subsequent event in the same event stream arrives on time or late, the time line is shifted down and all prior sins are forgiven.
This is also why drift is a problem. If an event source is emitting events too quickly for any reason (drift being just a common one), each early event uses up part of the limit budget until it is exhausted. This can happen because a single event arrived very very early. But it can also happen gradually, as each successive event uses up a tiny fraction of the limit. This can result in network links that appear to work just fine for days, until they suddenly and mysteriously quit working altogether. This is one of the reasons that telephony networks carrying real-time voice samples are carefully time synchronized to each other and to common timing sources of very high precision, typically atomic clocks. Timing synchronization can be a big deal.
Figure [6] shows event A3 arriving early but within the limit of the GCRA. But A4 arrives equally early, and its expected arrival time E4 is beyond the limit of the GCRA. A4 is dropped, as would be all subsequent events, until one arrives at or after its expected time on the current time line. In this example, A5 arrives at its expected time E5, and the limit budget is restored.
Finally, it is instructive to show some code snippets for a GCRA implementation just to show how simple it is. Below are some Java snippets (with some distracting details removed) borrowed from the GenericCellRateAlgorithm class in the Digital Aggregates Buckaroo library. First, there is the state maintained by the GCRA. The Java class maintains this state in long variables because they contain time durations in ticks. Because ticks are typically in units of microseconds or nanoseconds, the large range of the 64-bit integer is necessary. Since most modern processors implement 64-bit integers directly, this isn't typically a problem (although I have implemented 32-bit versions of the GCRA on embedded systems).
This next snippet computes the delay (if any) for an event when the current time is now, and the prior event was emitted then. The difference between now and then is the IAT if the current event were to be emitted.
If the delay is zero, the event conforms to the traffic contract implemented by the GCRA and may be emitted, in which case the state of the GCRA has to be updated with the expected IAT of the next event. If the delay is greater than zero, the emission of the event must be delayed (traffic shaping) or the event violates the traffic contract of its event stream and may be dropped (traffic policing).
That's it! No loops. No complicated math. No floating point.
This has been a whirlwind tour of the Generic Cell Rate Algorithm. But the GCRA is seldom used directly. One or more GCRAs are typically combined, with their increment and limit parameters computed from traffic contract parameters in more useful forms, like events per second. We will talk about how traffic contracts are mapped into one or more GCRAs in a later article.
Sources
Buckaroo, Digital Aggregates Corp., 2007
Chip Overclock, "Rate Control Using Throttles", January 2007
N. Giroux, et al., Traffic Management 4.0, tm-0056.000, ATM Forum, April 1996, pp. 62-67
J. L. Sloan, "ATM Traffic Management", Digital Aggregates Corp., August 2005
TM 4.0 offers two different explanations of how the GCRA works: the leaky bucket and the virtual scheduler. The two explanations are exactly equivalent, but to this day I really do not like term "leaky bucket", because for lots of folks it seems to suggest that there is some kind of data buffering going on when there isn't (or if there is, it isn't the GCRA doing the buffering). So I prefer to use the term "virtual scheduler", even though when I implement the GCRA, I tend to use the leaky bucket flowchart and terminology from TM 4.0.
As I mentioned briefly in my article "Rate Control Using Throttles", the GCRA has but two parameters: the increment and the limit. The increment is the expected inter-arrival time (IAT) between two successive events in an event stream. If you ideally want to transmit one hundred events evenly dispersed over every second, then you are describing a 100Hz event source whose emissions have an IAT of 1/100th of a second. Your increment would be 0.01 seconds. TM 4.0 specifies a time granularity of one microsecond as a standard for ATM traffic contracts, so in that case you would represent that increment as (1 000 000 / 100) or 10 000 microseconds. Of course, you can implement the GCRA in whatever time units you find appropriate for your application: nanoseconds, microseconds, milliseconds, or even some convenient time interval based on the frequency of your CPU clock. For this reason, I like to talk about time in the GCRA in units of ticks. So given an increment of i, the GCRA expects an ideal event source to emit an event every i ticks.
The increment assumes a smooth flow of data. Life is seldom that simple. Neither software, nor firmware, nor even hardware is capable of emitting events with perfect precision (although the old TDM-based land line telephone system sure tried). And once events are handled by other components, for example, nodes on a network, additional variation is inevitably inserted. This is especially true when multiple event sources are aggregated together. The aggregator (for example, a network router) can only emit one event at a time onto the aggregated output channel. So it selects an event from one input channel, hence delaying all the pending events on all the other input channels. It may select the next event to emit based on many factors, such as the quality of service parameters of the traffic contracts of the individual event streams, service level agreements with the event stream owners (a.k.a. paying customers), or simply round-robin.
Because small variations in the expected IAT of events, also known as jitter, are inevitable, a traffic policer implemented using the GCRA must provide for some slack in its traffic contract. This slack is the second parameter, the limit. The limit is the total cumulative time that successive events in an event stream may deviate from the expected IAT. The limit has a number of applications. When the GCRA is used for traffic policing incoming event streams, the limit prevents the policer from dropping events which have been jittered but are still within the tolerance of the limit. This allows, for example, a policer to pass otherwise well behaved event streams just because they got a little rowdy once in a while ("Events will be events" as my sainted mother never said). When used for traffic shaping, the limit allows the shaper to emit events in short bursts where the IAT between a small number of successive events is smaller than the specified increment. This allows, for example, a shaper to drain a perilously full memory buffer onto the network instead of dropping events on the floor.
I should mention here that jitter is quite different from drift, which is a more or less consistent, or at least larger, variation in the IAT than is associated with jitter. A frequent source of drift is a lack of a common time synchronization source between network nodes. This means each node has a different sense of the passage of time, kind of like that episode of Star Trek. Or maybe it was Twilight Zone. Anyway, because the nodes are timed to different clocks, the event source node believes it is emitting events more or less on time, while the event sink node may believe that every single event is arriving a little early. As we shall see, a GCRA used for traffic policing events streams on the sink node has limited patience with drift. Limited in fact by the limit. The limit is a time budget, and every single early event uses up more of that budget. Once the limit is exhausted, the traffic police will start dropping events, or at least marking them for possible deletion downstream, which is a kind of Scarlet Letter in the networking world.
Although it may sound complicated, the typical implementation of the GCRA is simple and efficient. This will be a little more obvious when we see how the increment and the limit play together, and see how little state the GCRA actually has to maintain and what simple calculations it has to do. The discussion below refers to the following set of diagrams, which show various scenarios of an event stream and a GCRA with an increment i and a limit l. (Click on the thumbnail to see a full size version.) Such a GCRA is typically represented in the literature using the notation GCRA(i, l). Yeah, the variables kinda suck, but I'm trying to stick with the TM 4.0 terminology.
Figure [1] shows a time line as the GCRA sees it. It expects to see events E0, E1, etc. arrive evenly spread exactly i ticks apart, where i is the increment.
Figure [2] shows just such a well behaved event stream, with the actual events A0, A1, etc. all arriving exactly on time. These are the kind of events that got beat up in school and called "mama's boys".
Figure [3] shows event A2 arriving j ticks late. A2 is always arriving late, and always has some good excuse: its car broke down, it had to drop the kids of at school, whatever. You would think the GCRA would give the event stream some credit by maybe increasing its limit by j ticks. Or maybe it would penalize event A2. But instead, when an event arrives late, the GCRA shifts the entire time line down so that the IAT of all subsequent events will be measured relative to the new time line established by the late arriving A2.
Figure [4] shows that event A2 has been somehow dropped by the network and was never seen by the GCRA. The GCRA doesn't care one whit about the fact that A2 was dropped. From its perspective, A3 is the next event, and it arrived i ticks late. So once again the time line is shifted down so that the IAT of all subsequent events will be measured relative to the new time line established by the arrival of A3.
Figure [5] shows that although A1 and A3 arrived right on schedule, A2 was jittered in its passage though the network. Because A2 arrived late, the time line is shifted down just as before. Now, even though A3 arrived right on time as far as the original time line was concerned, the GCRA sees it as arriving early from the perspective of the new time line, just k ticks after A2. So while A2 arrived j ticks late, it is A3, which arrived (i-k) ticks early, which may be penalized. The GCRA compares (i-k) to the limit l and if it is less, A3 is not dropped and the event stream goes on its merry way. However, something interesting happens to all subsequent events A4, A5 and on to infinity. Even through they are arriving spot on in terms of the original time line, they are all (i-k) ticks early from the perspective of the new time line. The limit l has been reduced by (i-k) ticks, and will remain so until an event arrives on or after its expected time on the new time line.
Because jitter is a more or less random mechanism, and it is about as likely that events in the same event stream arrive late as they do early, assuming they were emitted with the correct timing from their original event source, this works. When an event arrives early, part of the limit budget is consumed. But when a subsequent event in the same event stream arrives on time or late, the time line is shifted down and all prior sins are forgiven.
This is also why drift is a problem. If an event source is emitting events too quickly for any reason (drift being just a common one), each early event uses up part of the limit budget until it is exhausted. This can happen because a single event arrived very very early. But it can also happen gradually, as each successive event uses up a tiny fraction of the limit. This can result in network links that appear to work just fine for days, until they suddenly and mysteriously quit working altogether. This is one of the reasons that telephony networks carrying real-time voice samples are carefully time synchronized to each other and to common timing sources of very high precision, typically atomic clocks. Timing synchronization can be a big deal.
Figure [6] shows event A3 arriving early but within the limit of the GCRA. But A4 arrives equally early, and its expected arrival time E4 is beyond the limit of the GCRA. A4 is dropped, as would be all subsequent events, until one arrives at or after its expected time on the current time line. In this example, A5 arrives at its expected time E5, and the limit budget is restored.
Finally, it is instructive to show some code snippets for a GCRA implementation just to show how simple it is. Below are some Java snippets (with some distracting details removed) borrowed from the GenericCellRateAlgorithm class in the Digital Aggregates Buckaroo library. First, there is the state maintained by the GCRA. The Java class maintains this state in long variables because they contain time durations in ticks. Because ticks are typically in units of microseconds or nanoseconds, the large range of the 64-bit integer is necessary. Since most modern processors implement 64-bit integers directly, this isn't typically a problem (although I have implemented 32-bit versions of the GCRA on embedded systems).
long increment;
long limit;
long now; // time of this event
long then; // time of prior event
long x = 0; // expected ticks
long x1 = 0; // actual ticks
This next snippet computes the delay (if any) for an event when the current time is now, and the prior event was emitted then. The difference between now and then is the IAT if the current event were to be emitted.
long delay = 0;
long iat = now - then;
if (x <= iat) {
x1 = 0;
} else {
x1 = x - iat;
if (x1 > limit) {
delay = x1 - limit;
}
}
if (delay == 0) {
then = now;
x = x1 + increment;
}
If the delay is zero, the event conforms to the traffic contract implemented by the GCRA and may be emitted, in which case the state of the GCRA has to be updated with the expected IAT of the next event. If the delay is greater than zero, the emission of the event must be delayed (traffic shaping) or the event violates the traffic contract of its event stream and may be dropped (traffic policing).
That's it! No loops. No complicated math. No floating point.
This has been a whirlwind tour of the Generic Cell Rate Algorithm. But the GCRA is seldom used directly. One or more GCRAs are typically combined, with their increment and limit parameters computed from traffic contract parameters in more useful forms, like events per second. We will talk about how traffic contracts are mapped into one or more GCRAs in a later article.
Sources
Buckaroo, Digital Aggregates Corp., 2007
Chip Overclock, "Rate Control Using Throttles", January 2007
N. Giroux, et al., Traffic Management 4.0, tm-0056.000, ATM Forum, April 1996, pp. 62-67
J. L. Sloan, "ATM Traffic Management", Digital Aggregates Corp., August 2005
Friday, January 12, 2007
Rate Control Using Throttles
In my article "Traffic Management", I talked about the need for rate control in real-time systems. I mentioned that there were efficient algorithms for implementing sophisticated rate control mechanisms. Such algorithms can be used for traffic policing on the consumer side and for traffic shaping on the producer side. They are frequently simple enough that they are implemented in off-the-shelf chip sets for networking technologies like Frame Relay and Asynchronous Transfer Mode (ATM).
They are also simple enough to be implemented efficiently in firmware or software and incorporated into applications ranging from embedded systems to enterprise Service Oriented Architectures. Several commercial telecommunications products contain proprietary rate control software that I developed. Digital Aggregates provides clean-room implementations of several rate control algorithms based on public standards. These are available in C++ in the open source (LPGL) Desperado library, and in Java in the open source (Apache 2.0) Buckaroo library.
Historically - in this case meaning in my personal history - rate control has been cast in terms of the emission of ATM cells. Much of the rate control software that I have developed has been based on the virtual scheduler described in the ATM Forum Traffic Management 4.0 specification. This is because I spent several years at Bell Laboratories immersed in the development of ATM devices, including an ATM network interface card that supported Voice and Telephony Over ATM (VTOA) with traffic shaping, and which to this day is still arguably the most complex single board ever produced by that organization, and an ATM network switch with a sophisticated Connection Admission Control (CAC) algorithm. Alas, ATM became the Sony Betamax of network technologies, along with all that implies. However, replace the word cell with buffer, packet, datagram, log message, event, or foo, and the same code works equally well in non-ATM applications. (You can replace cell with byte too, but calling this software for every single byte you want to transmit is not cost effective. Stay tuned for future developments.)
The basic abstraction for the Desperado and Buckaroo rate control classes is the Throttle. Throttles are objects that maintain internal state about the event stream they are rate controlling. Before emitting an event (whatever the words emit and event mean in context), the application calls the Throttle to ask if the event is admissible. If the Throttle says that it is, the application emits the event and commits the Throttle state. If it is not, the application does not emit the event and instead rolls back the Throttle state. What happens next depends on what kind of Throttle you have.
Throttles may be time-based or event-based. Time-based throttles base admission decisions on temporal factors such as the inter-arrival time between successive events. They are initialized with a specific traffic contract that formally describes the expected (traffic policing) or desired (traffic shaping) emission behavior of the event stream that they are rate controlling. Event-based throttles base admission decisions on something other than time, such as the number of events already admitted. Throttles may be compounded together to form composite Throttles that exhibit behavior that may be quite complex. Think of it as adding simple periodic waveforms together to get speech or music.
When using an event-based Throttle and the event is not admissible, the event is not emitted, and the application may try again later at some indeterminate time. The Geometric Throttle admits events following a geometric progression: it admits the first event, the second event, the fourth event, the eighth event, up to and including the thirtieth event, after which no more events are admitted until the Throttle is reset. This simple Throttle is very useful in embedded systems for controlling error messages to a log file or a console when a persistent failure has occurred. The application only emits the error message if it is admissible, and it resets the Throttle once the error clears, placing the Throttle back in its initial state. Several error messages will be emitted initially for a particular failure, then with ever decreasing frequency, until finally no more error messages appear. This is a good strategy whether the log is being watched in real-time or being written to a file, because it produces the occasional reminder that the error still exists without resulting in a fire hose of error messages.
When using a time-based Throttle and the event is not admissible, the event is not emitted, and the Throttle gives the application a delay interval, in units like microseconds, that indicates how far in the future the event will become admissible. The application can delay emitting the event until this interval has passed, at which point it asks again if the event is admissible to update the Throttle state, commits the state, and emits the event. Time-based throttles are ideal for shaping outgoing data streams to make a message producer a good citizen that plays well with others, and for policing incoming data streams to prevent a misbehaving message producer from fire hosing a message consumer.
Below is a Java code snippet (with some distracting details removed) that shows a trivial application initializing and then using a Throttle to control the rate at which events are emitted by doing a simple Thread sleep. Without going into too much explanation, this gives you the flavor of how a Throttle might be used.
The Generic Cell Rate Algorithm (GCRA) is a time-based Throttle which is based on the virtual scheduler. Its traffic contract consists of just two parameters, the increment, which is the expected or desired inter-arrival time between events, and the limit, which is the total variation from the inter-arrival time that the event stream may exhibit before being in violation of the traffic contract. Telecommunications folk will recognize this slack in the traffic contract as an accommodation for jitter, small variations in the inter-arrival time of events. It is impossible for firmware or even hardware to nail the emission of events exactly on the dot time-wise. And when aggregating multiple event streams into a single event stream, one event has to be emitted before another, regardless of their respective traffic contracts. Jitter happens. As someone once said, "perfection is the enemy of good enough", and rate control mechanisms have to take this into account. If you find it impossible to emit event streams in conformance with their individual traffic contracts, either your traffic contracts are unrealistic, or you have a network engineering problem that you need to solve.
However, there may be legitimate reasons to commit the Throttle state and emit an event even if the event is not admissible. It may well be better to emit an event at a time that violates its traffic contract and let it take its chances being dropped due to congestion by a downstream node in the network, than to guarantee that it is dropped due to, for example, a full buffer in the consumer, before it is ever emitted into the network. (It also may well be that this is not the case; your mileage may vary.) If the application commits the Throttle for an event which is not admissible, the Throttle becomes alarmed. The Throttle remains in the alarmed state until the event stream once again conforms to its traffic contract.
The Cell Rate Throttle is a composite Throttle made up of two GCRA Throttles. It implements a complex traffic contract based on parameters that may sound a little more approachable than increment and limit. The Peak Cell Rate (PCR) describes the maximum expected or desired rate of event emission in cells per second. The Cell Delay Variation Tolerance (CDVT) is the limit for jitter in the PCR, typically in microseconds. The Sustained Cell Rate (SCR) is the long term average rate of event emission in cells per second. The Maximum Burst Size (MBS) is the number of cells that maybe emitted at PCR (which is presumably greater than SCR) without violating the traffic contract. The math behind the GCRA and the virtual scheduler calculates the equivalent burst size for any emission rate between PCR and SCR. The Cell Rate Throttle allows an event stream to burst for short periods without violating its long term average rate. This may sound like rocket science, but once again, the implementation of this mechanism is actually very simple and efficient.
Each time-based Throttle implementation has a time granularity known as a tick. A tick may be a millisecond, microsecond, nanosecond, or even some arbitrary unit that may not even be representable as a whole number and is perhaps based on the underlying CPU clock. The inverse of this granularity, that is, the number of ticks per second, is known as the Throttle's frequency. A time-based Throttle may be queried as to its frequency, and each time-based Throttle provides a method that returns the current time in units appropriate to its frequency. The current time may be equivalent to wall clock time relative to some epoch, or merely a monotonically increasing counter with a consistent interval of change suitable for measuring arbitrary time durations. This flexibility in regards to how time is measured makes Throttles easily adaptable to many operating system platforms and hardware targets.
A few more minor details: Throttles may be reset at any time to return them to their initial state, causing them to forget any past sins of the event stream they are rate controlling. The first event for any Throttle is guaranteed to be admissible. Throttles are guaranteed not to alarm as long as their event streams conform to their traffic contracts.
This has been a brief introduction to Throttles. I believe that rate control is crucial for any real-time system that is to be robust, scalable, and supportable, and most especially one in which event streams must be aggregated. Using Throttles and other rate control mechanisms for traffic shaping and traffic policing make producers and consumers well behaved, and allows you to make useful assumptions about traffic, load, and quality of service when engineering a network, configuring a large distributed application, or troubleshooting a customer system. In the future I will discuss traffic contracts in more detail, and the theoretical underpinnings of the Generic Cell Rate Algorithm and the virtual scheduler.
Sources
Buckaroo, Digital Aggregates Corp., 2007
Desperado, Digital Aggregates Corp., 2007
Chip Overclock, "Traffic Management", December 2006
N. Giroux, et al., Traffic Management 4.0, tm-0056.000, ATM Forum, April 1996, pp. 62-67
J. L. Sloan, "ATM Traffic Management", Digital Aggregates Corp., August 2005
They are also simple enough to be implemented efficiently in firmware or software and incorporated into applications ranging from embedded systems to enterprise Service Oriented Architectures. Several commercial telecommunications products contain proprietary rate control software that I developed. Digital Aggregates provides clean-room implementations of several rate control algorithms based on public standards. These are available in C++ in the open source (LPGL) Desperado library, and in Java in the open source (Apache 2.0) Buckaroo library.
Historically - in this case meaning in my personal history - rate control has been cast in terms of the emission of ATM cells. Much of the rate control software that I have developed has been based on the virtual scheduler described in the ATM Forum Traffic Management 4.0 specification. This is because I spent several years at Bell Laboratories immersed in the development of ATM devices, including an ATM network interface card that supported Voice and Telephony Over ATM (VTOA) with traffic shaping, and which to this day is still arguably the most complex single board ever produced by that organization, and an ATM network switch with a sophisticated Connection Admission Control (CAC) algorithm. Alas, ATM became the Sony Betamax of network technologies, along with all that implies. However, replace the word cell with buffer, packet, datagram, log message, event, or foo, and the same code works equally well in non-ATM applications. (You can replace cell with byte too, but calling this software for every single byte you want to transmit is not cost effective. Stay tuned for future developments.)
The basic abstraction for the Desperado and Buckaroo rate control classes is the Throttle. Throttles are objects that maintain internal state about the event stream they are rate controlling. Before emitting an event (whatever the words emit and event mean in context), the application calls the Throttle to ask if the event is admissible. If the Throttle says that it is, the application emits the event and commits the Throttle state. If it is not, the application does not emit the event and instead rolls back the Throttle state. What happens next depends on what kind of Throttle you have.
Throttles may be time-based or event-based. Time-based throttles base admission decisions on temporal factors such as the inter-arrival time between successive events. They are initialized with a specific traffic contract that formally describes the expected (traffic policing) or desired (traffic shaping) emission behavior of the event stream that they are rate controlling. Event-based throttles base admission decisions on something other than time, such as the number of events already admitted. Throttles may be compounded together to form composite Throttles that exhibit behavior that may be quite complex. Think of it as adding simple periodic waveforms together to get speech or music.
When using an event-based Throttle and the event is not admissible, the event is not emitted, and the application may try again later at some indeterminate time. The Geometric Throttle admits events following a geometric progression: it admits the first event, the second event, the fourth event, the eighth event, up to and including the thirtieth event, after which no more events are admitted until the Throttle is reset. This simple Throttle is very useful in embedded systems for controlling error messages to a log file or a console when a persistent failure has occurred. The application only emits the error message if it is admissible, and it resets the Throttle once the error clears, placing the Throttle back in its initial state. Several error messages will be emitted initially for a particular failure, then with ever decreasing frequency, until finally no more error messages appear. This is a good strategy whether the log is being watched in real-time or being written to a file, because it produces the occasional reminder that the error still exists without resulting in a fire hose of error messages.
When using a time-based Throttle and the event is not admissible, the event is not emitted, and the Throttle gives the application a delay interval, in units like microseconds, that indicates how far in the future the event will become admissible. The application can delay emitting the event until this interval has passed, at which point it asks again if the event is admissible to update the Throttle state, commits the state, and emits the event. Time-based throttles are ideal for shaping outgoing data streams to make a message producer a good citizen that plays well with others, and for policing incoming data streams to prevent a misbehaving message producer from fire hosing a message consumer.
Below is a Java code snippet (with some distracting details removed) that shows a trivial application initializing and then using a Throttle to control the rate at which events are emitted by doing a simple Thread sleep. Without going into too much explanation, this gives you the flavor of how a Throttle might be used.
int pcr = 10; // Peak Cell Rate
int cdvt = 250; // Cell Delay Variation Tolerance
int scr = 1; // Sustained Cell Rate
int mbs = 10; // Maximum Burst Size
Throttle th =
new CellRateThrottle(pcr, cdvt, scr, mbs);
while (true) {
long delay = th.admissible();
while (delay > 0) {
th.rollback();
Thread.sleep(delay);
delay = th.admissible();
}
th.commit();
emit(event());
}
The Generic Cell Rate Algorithm (GCRA) is a time-based Throttle which is based on the virtual scheduler. Its traffic contract consists of just two parameters, the increment, which is the expected or desired inter-arrival time between events, and the limit, which is the total variation from the inter-arrival time that the event stream may exhibit before being in violation of the traffic contract. Telecommunications folk will recognize this slack in the traffic contract as an accommodation for jitter, small variations in the inter-arrival time of events. It is impossible for firmware or even hardware to nail the emission of events exactly on the dot time-wise. And when aggregating multiple event streams into a single event stream, one event has to be emitted before another, regardless of their respective traffic contracts. Jitter happens. As someone once said, "perfection is the enemy of good enough", and rate control mechanisms have to take this into account. If you find it impossible to emit event streams in conformance with their individual traffic contracts, either your traffic contracts are unrealistic, or you have a network engineering problem that you need to solve.
However, there may be legitimate reasons to commit the Throttle state and emit an event even if the event is not admissible. It may well be better to emit an event at a time that violates its traffic contract and let it take its chances being dropped due to congestion by a downstream node in the network, than to guarantee that it is dropped due to, for example, a full buffer in the consumer, before it is ever emitted into the network. (It also may well be that this is not the case; your mileage may vary.) If the application commits the Throttle for an event which is not admissible, the Throttle becomes alarmed. The Throttle remains in the alarmed state until the event stream once again conforms to its traffic contract.
The Cell Rate Throttle is a composite Throttle made up of two GCRA Throttles. It implements a complex traffic contract based on parameters that may sound a little more approachable than increment and limit. The Peak Cell Rate (PCR) describes the maximum expected or desired rate of event emission in cells per second. The Cell Delay Variation Tolerance (CDVT) is the limit for jitter in the PCR, typically in microseconds. The Sustained Cell Rate (SCR) is the long term average rate of event emission in cells per second. The Maximum Burst Size (MBS) is the number of cells that maybe emitted at PCR (which is presumably greater than SCR) without violating the traffic contract. The math behind the GCRA and the virtual scheduler calculates the equivalent burst size for any emission rate between PCR and SCR. The Cell Rate Throttle allows an event stream to burst for short periods without violating its long term average rate. This may sound like rocket science, but once again, the implementation of this mechanism is actually very simple and efficient.
Each time-based Throttle implementation has a time granularity known as a tick. A tick may be a millisecond, microsecond, nanosecond, or even some arbitrary unit that may not even be representable as a whole number and is perhaps based on the underlying CPU clock. The inverse of this granularity, that is, the number of ticks per second, is known as the Throttle's frequency. A time-based Throttle may be queried as to its frequency, and each time-based Throttle provides a method that returns the current time in units appropriate to its frequency. The current time may be equivalent to wall clock time relative to some epoch, or merely a monotonically increasing counter with a consistent interval of change suitable for measuring arbitrary time durations. This flexibility in regards to how time is measured makes Throttles easily adaptable to many operating system platforms and hardware targets.
A few more minor details: Throttles may be reset at any time to return them to their initial state, causing them to forget any past sins of the event stream they are rate controlling. The first event for any Throttle is guaranteed to be admissible. Throttles are guaranteed not to alarm as long as their event streams conform to their traffic contracts.
This has been a brief introduction to Throttles. I believe that rate control is crucial for any real-time system that is to be robust, scalable, and supportable, and most especially one in which event streams must be aggregated. Using Throttles and other rate control mechanisms for traffic shaping and traffic policing make producers and consumers well behaved, and allows you to make useful assumptions about traffic, load, and quality of service when engineering a network, configuring a large distributed application, or troubleshooting a customer system. In the future I will discuss traffic contracts in more detail, and the theoretical underpinnings of the Generic Cell Rate Algorithm and the virtual scheduler.
Sources
Buckaroo, Digital Aggregates Corp., 2007
Desperado, Digital Aggregates Corp., 2007
Chip Overclock, "Traffic Management", December 2006
N. Giroux, et al., Traffic Management 4.0, tm-0056.000, ATM Forum, April 1996, pp. 62-67
J. L. Sloan, "ATM Traffic Management", Digital Aggregates Corp., August 2005
Subscribe to:
Posts (Atom)
