{"id":406223,"date":"2024-06-29T18:48:04","date_gmt":"2024-06-29T18:48:04","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=406223"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=406223","title":{"rendered":"Measuring Traffic Rate by Means of U-models<\/span>"},"content":{"rendered":"
<\/div>\n
\n
\n
\n
\"stream
Measuring of stream rate in an artist’s impression.<\/sup><\/p>\n

In one of our previous publications<\/a>, we talked about a way to measure event stream rate using a counter based on exponential decay. It turns out that the idea of such a counter has an interesting generalization. This paper by Artem Shvorin and Dmitry Kamaldinov, Qrator Labs, reveals it.
<\/a>
Our immersion plan is as follows. First, let us look at and analyze a few examples of how events are counted and the rate of the stream is estimated in general. The next step is to see a generalization, namely some class of counters, which we call the u-model. Next, we explore what useful properties u-models have and propose a technique for constructing an adequate rate estimate.<\/p>\n

1\u00a0\u00a0 Examples of Counters<\/h1>\n

Without limiting the generality, we may assume that an event counter is described by its state \"$s$\", which, upon the arrival of an event at time \"$t$\", is updated according to some rule: <\/p>\n

\"$<\/p>\n

The state is not necessarily expressed by a number, but for feasibility reasons we may assume that it is representable by a finite set of bits.<\/p>\n

In some cases, events are weighted, and the weight of the event \"$w$\" must be taken into account when updating the state: <\/p>\n

\"$<\/p>\n

But at first, we will consider simple unweighted events, and we will add weight later when we need it. That will not be difficult at all.<\/p>\n

In this article, we will limit ourselves to considering only deterministic counters, that is, those for which the update rule is given by a function \"$s'=update(s,t)$\". But in general, it may be useful to add some randomness to this mechanism; we recently talked about it [7] and will probably continue to do so.<\/p>\n

It should also be possible, knowing the state of the counter, to estimate the rate of the stream. Generally speaking, the notion of stream rate is non-trivial, and we will discuss it in more detail later. For now, we will just assume that the counter model has some nominal estimate as a function \"$r(s,t)$\", written out of some design considerations.<\/p>\n

1.1\u00a0\u00a0 Linear Counters: Counting All Events<\/h2>\n

The simplest thing one may think of is to just count the number of events that have occurred since we started. That is, when an event arrives, we do this: <\/p>\n

\"$<\/p>\n

We will call such counters linear<\/i>.<\/p>\n

The estimate is the average rate over the entire history: <\/p>\n

\"$<\/p>\n

Some problem may occur due to counter overflow. There are also questions about defining the estimate: here, very old events have the same effect on the rate estimate as recent ones.<\/p>\n

1.1.1\u00a0\u00a0 Sliding Window Event Counting<\/h3>\n

To eliminate the above drawbacks of linear counters, one may count the number of events not since the creation of the world but only those that occurred no more than \"$T$\" cycles ago. This time interval of length \"$T$\" is usually called a window, and it is sliding because it shifts a step forward with each cycle.<\/p>\n

A naive implementation assumes to remember all events in the window, thus requiring \"$O(T)$\" of memory. However, there are ways to save resources in trade-off for reduced precision, such as described in [6]. The update rule is expressed in a rather complicated way, while the average rate over time \"$T$\" serves as the estimate: <\/p>\n

\"$<\/p>\n

Unfortunately, such linear counters are unsuitable for our purposes: we can still tolerate a decrease in accuracy, but \"$O(\\log in memory and complexity is too costly, even for small \"$T$\".<\/p>\n

1.2\u00a0\u00a0 EDecay: the Exponential Decay<\/h2>\n

The idea of the decay counter is inspired by the well-known concept of radioactive decay [4]. Its essence is that the amount of undecayed matter decreases over time according to an exponential law: <\/p>\n

\"$v(t)<\/p>\n

where \"$v_0$\" is the amount of matter at the initial (zero) moment of time, \"$\\lambda$\" is some parameter, the so-called decay constant.<\/p>\n

It is more convenient to rewrite this expression in the following form: <\/p>\n

\"$v(t)<\/p>\n

replacing the parameter. For more details on parameterization of counter models, see Section A of the Appendix.<\/p>\n

Relying on this mechanism, we can build an event counter as described in our article [1]. <\/p>\n

By definition, we will assume that each type of event corresponds to the value of \"$v$\", which has a physical meaning of \u201cquantity of matter\u201d and depends on time in such a way that it sharply increases by one at the occurrence of the event and decreases in the remaining time in accordance with the exponential law shown above. <\/p><\/blockquote>\n

That is, to account for a new event arriving at time \"$t$\", one must first apply the decay and then increase the counter by one: <\/p>\n

\"$<\/p>\n

where \"$t_0$\" is the arrival time of the previous event.<\/p>\n

To be able to use this, we need to figure out how to store the counter in memory. The simplest way to represent the state of the counter is to use a pair of numbers \"$(v,, where \"$t_0$\" is the time of the last update, and \"$v$\" is the amount of matter at that time. In this case, the update rule and estimation may be written as follows: <\/p>\n

\"$<\/p>\n

In the article [1] we take a detailed look at such counters. An important idea that is relevant to mention here is a lower cost representation of the counter state as a single<\/i> number \"$s$\", the so-called absolute value<\/i>, which holds all the information needed to work with the counter. <\/p>\n

The value of \"$v$\" is not explicitly stored in memory but can be computed at any time. Instead, the value \"$s$\" is stored, such that at time \"$t$\" the value \"$v$\" is expressed as follows: <\/p>\n

\"$<\/p>\n

<\/p><\/blockquote>\n

Without going into detail, let us just say that with this approach, the update rule and estimation take the form: <\/p>\n

\"$<\/p>\n

1.3\u00a0\u00a0 QDecay: a Faster Decay<\/h2>\n

When looking at the exponential decay model, we can see that the decay function (in this case, the exponent) satisfies the differential equation: <\/p>\n

\"$\\frac{dv}{dt}<\/p>\n

In fact, from a physical point of view, it is instead the other way around: this is the equation describing radioactive decay, and the exponent is its solution.<\/p>\n

Indeed, the meaning of the equation is that the rate of decay is proportional to the amount of matter available. At some point, we intended to improve the model making decay faster, so we tried to take a quadratic law (QDecay) instead of a linear one: <\/p>\n

\"$\\frac{dv}{dt}<\/p>\n

The solution is a new decay function: <\/p>\n

\"$<\/p>\n

and it is really gotten steeper.<\/p>\n

As a matter of fact\u2026<\/b> <\/p>\n
It is hardly correct to say that a hyperbola is steeper than an exponent. However, large values decay indeed faster (and vice versa for small values). <\/div>\n<\/p><\/div>\n

Similar to the model discussed previously (with exponential decay), here, we can represent the counter state as a single number \"$s$\". The corresponding update rule and rate estimate look like this: <\/p>\n

\"$<\/p>\n

The great thing here is that calculating the update function is cheap: it requires only elementary arithmetic operations, with only one division. That is, all we originally wanted was a faster horse (faster decay), but we got a new useful feature (cheaper calculations).<\/p>\n

We could go further by providing a higher degree in the equation defining the decay function: \"$dv and so on, but the solution is more complicated, the calculations are more expensive, and the obvious benefit is somehow not noticeable. Rejected<\/p>\n

1.4\u00a0\u00a0 SW: Averaging of Interpacket Interval<\/h2>\n

Consider another approach to constructing counters, namely averaging. In this case, we will average the time interval between neighboring events. We call this value the interpacket interval<\/i>, because we deal with network traffic, where the event is the arrival of a network packet, and the word \u201cinter-event\u201d has somehow not caught on.<\/p>\n

Generally speaking, the point of this approach is that we have a sequence of values of some quantity (in this case, interpacket intervals) that changes too quickly to be used directly, and we want to smooth or average this sequence in some way.<\/p>\n

Averaging is\u2026<\/b> <\/p>\n
Let there be a sequence \"$\\langle, then its average at the \"$n$\"th step is defined as follows: <\/p>\n

\"$<\/p>\n

Here, we get the arithmetic mean of the last \"$n$\" members of the sequence.<\/p>\n

This definition may be generalized. The weighted average of a sequence \"$\\langle is the sum <\/p>\n

\"$<\/p>\n

where \"$\\omega_i$\" are some weights such that \"$\\omega_i\\ge. <\/div>\n<\/p><\/div>\n

Recall that the newer events are, the more interesting we find their contribution to the rate estimate. So it is natural to use weighted averaging instead of usual averaging, giving more weight to recent events. Weights may be chosen in different ways; now, let us try to take the weights as terms of a geometric progression. This way of summing up is called exponential moving average<\/i> (EMA).<\/p>\n

EMA averaging is\u2026<\/b> <\/p>\n
The exponential moving average of the \"$\\langle sequence is defined as follows: <\/p>\n

\"$<\/p>\n

where \"$\\beta\\in(0,1)$\" is a parameter, \"$B=\\sum_{i.<\/p>\n

Since there are very many events, i.e., \"$n$\" is large, we may assume that there were some dummy events \"$p_i$\", \"$i<0$\" in the dim and distant past, whose contributions are taken with negligible weights \"$q^{n-i}$\". Then it is more convenient to rewrite the definition as follows: <\/p>\n

\"$<\/p>\n

since in this case \"$B=\\sum_{i.<\/p>\n

One important advantage of EMA over other averaging methods is the ability to collapse a cumbersome sum into a recursive expression: <\/p>\n

\"$<\/p>\n

Thus, it is not necessary to store many old values of \"$p_n$\" for the calculations. By the way, it is the formula (3) is often taken as the definition of EMA [2]. <\/div>\n<\/p><\/div>\n

Applying the exponential averaging formula to the interpacket intervals, we get: <\/p>\n

\"$<\/p>\n

where \"$v_n$\" is the desired EMA-averaged interpacket interval, \"$t_n$\" is the moment when the \"$n$\"th event occurs.<\/p>\n

This model is mentioned again in Section 4.3, where, in particular, we show how to express the counter state by a single number and simplify the calculations. For now, let us just write out the result.<\/p>\n

Update the counter when an event occurs at time \"$t$\": <\/p>\n

\"$<\/p>\n

The reciprocal of the averaged interpacket interval serves as the rate estimate: <\/p>\n

\"$<\/p>\n

Remark<\/b> <\/p>\n
Using EMA averaging, we can also obtain a model exactly coinciding with the decay model from Section 1.2. Instead of averaging the interpacket intervals, this deals with the value \"$p_t$\", which could be called the momentary rate: <\/p>\n

\"$<\/p>\n

<\/div>\n<\/p><\/div>\n

<\/p>\n

1.5\u00a0\u00a0 Probabilistic Counters<\/h2>\n

The idea of probabilistic counters is to change the counter state when an event arrives, not always, but with some probability. This probability may be defined in various ways, e.g.<\/p>\n

    \n
  • stay constant (binomial counters);<\/li>\n
  • decrease by a factor of 2 after each successful update (Morris counters);<\/li>\n
  • change after every \"$X 1$» data-tex=»inline»\/> of successful updates.<\/li>\n<\/ul>\n

    Probability counters make very efficient use of memory. For example, the original 8-bit Morris counters may be used to account for up to \"$2^{256}$\" events. Their obvious disadvantage, however, is significant inaccuracy in estimating the number of events. We discuss such counters in detail in the article [7], and we also propose some extensions of known algorithms.<\/p>\n

    2\u00a0\u00a0 The Idea of the U-model<\/h1>\n

    If we look at the counters based on the idea of decay, we may notice this peculiarity: the state is described by a pair of numbers \"$(v,, but then it miraculously appears to be possible to express the state by a single number \"$s$\". Let us try to find a general principle by which this becomes possible for any counters of this type.<\/p>\n

    Let us temporarily forget the fact that in practice, the counter value must be discrete and represented by a relatively small number of bits, and, staying within the spherical cow concept, let us assume both the counter value and the event arrival time be real numbers, and the transformations over them also are real-valued functions. Later (see Section 3.3) we will learn how to discretize the models, making them usable in practice.<\/p>\n

    2.1\u00a0\u00a0 An Invariant of Decay<\/h2>\n

    Consider a section of the decay curve (see Fig. 1a). Let at time \"$t_0$\" an event was registered, and then on the interval \"$[t_0, there were no other events. Now we are at the point \"$t$\" going to account for a new event, or just to see what the value of \"$v$\" is, in order to estimate the rate. One may notice that from the point of view of an observer at the moment \"$t$\" there is absolutely no difference whether the last event occurred at the \"$(t_0, point on the plot or at \"$(t'_0,. This fact seems to hint that storing two numbers as the counter state is redundant. Thus, the two formally different versions of reality are functionally equipotent. That is, they give the same effect: <\/p>\n

    \"$<\/p>\n

    \"decay
    Generally speaking, we do not have a single decay curve, but a family \"$v=v_s(t)$\" (see Figure 1b). Each of these curves describes a state of the counter. They may be enumerated somehow, and we may take the index of the curve as the counter state.<\/p>\n

    Let us now see how such a counter should be updated. Let \"$s$\" be the current state of the counter. According to the decay model, this means that in the absence of events, the value of \"$v$\" changes over time, remaining on the curve \"$v_s(t)$\". Let an event occur at some point \"$t$\". This means that the value of \"$v$\" increases stepwise by one (see Fig. 1c), that is, among the whole family of curves we must find the one that passes through the point \"$(t, where \"$v'=v+1$\". Let \"$s'$\" be the index of the found curve, i.e., <\/p>\n

    \"$<\/p>\n

    then this is the value of \"$s'$\" to set as the new counter state.<\/p>\n

    Remark<\/b> <\/p>\n
    If one wants to count weighted events, the stepwise change should be not by one but by the weight of the event: \"$v'=v+w$\". <\/div>\n<\/p><\/div>\n

    It is not yet clear how to find the index of the desired curve, but it will come to light very soon.<\/p>\n

    2.2\u00a0\u00a0 Translational Symmetry<\/h2>\n

    In Fig. 1b decay curves \"$v_s(t)$\" are depicted in such a way that they differ from each other only by a horizontal shift. Scientifically, this is called translational symmetry of the time [8]. We want to take this property as an axiom for our counter model. Indeed, it is logical to expect that, within the model, the decay process goes today in exactly the same manner as it did yesterday.<\/p>\n

    Mathematically, this property may be written as follows: <\/p>\n

    \"$<\/p>\n

    that is, the curve \"$v_{s_2}(t)$\" is obtained from the curve \"$v_{s_1}(t)$\" by shifting it to the right by some \"$\\Delta$\".<\/p>\n

    In general, curves may be enumerated any way you like, and you just need to be able to find the index of the new curve during the update operation. But it is more convenient to enumerate them in order so that the index \"$s$\" represents something meaningful, namely, a real number corresponding to the horizontal distance between the \"$v_s(t)$\" curve and the curve with zero index \"$v_0(t)$\". Then, due to translational symmetry, any curve from the family may be very simply expressed as a shift of the curve number zero: <\/p>\n

    \"$<\/p>\n

    <\/p>\n

    Remark<\/b> <\/p>\n
    Here we introduce the notation \"$\\mu(x), which is convenient because the function \"$\\mu$\" increases monotonically. This will come in handy later in Section 2.4 in determining the rate. <\/div>\n<\/p><\/div>\n

    Now, the update rule on an event arrival at time \"$t$\" may be expressed from equation (5) as follows: <\/p>\n

    \"$<\/p>\n

    Thus, the update rule appears as <\/p>\n

    \"$<\/p>\n

    where \"$u(\\cdot)$\" is some function.<\/p>\n

    This rule looks so simple and universal that it may be taken as the definition. That is how we will define the u-model.<\/p>\n

    Remark<\/b> <\/p>\n
    If the decay function is given by a differential equation of such kind: <\/p>\n

    \"$<\/p>\n

    then it is always easy to find an invariant for that the property (6) holds.<\/p>\n

    Indeed, the solution of the differential equation may be written as <\/p>\n

    \"$<\/p>\n<\/p>\n

    Thus we can take \"$s as an invariant, and the corresponding curve is expressed as \"$v_s(t)=F^{-1}(t-s)$\". <\/div>\n<\/p><\/div>\n

    Section 3.1 lists the formal properties that the function \"$u$\" must satisfy in order to build a workable counter model on its basis.<\/p>\n

    2.3\u00a0\u00a0 Absolute and Relative<\/h2>\n

    We may say that \"$s$\" is the absolute<\/i> value of the counter, it is stored directly in memory, and \"$x=s-t$\" is the relative<\/i> value of the counter at time \"$t$\". Then it turns out that the update function works with the relative counter value: \"$x'.<\/p>\n

    The fact that the update function works with the relative counter value reflects the decay principle: if no events occur, then the absolute value of \"$s$\" does not change, and the relative value automatically decreases over time. And the rate estimate, accordingly, also degrades. From the calculation point of view, it is very convenient: as long as there are no events, there is no need to do anything. It is very similar to inflation in economics: the state of the counter stands for banknotes lying under the pillow, and the rate estimate stands for the purchasing power of these banknotes, which degrade itself.<\/p>\n

    2.4\u00a0\u00a0 Rate Estimate<\/h2>\n

    For the decay model, the value \"$\\mu(s-t)$\" by construction is the rate estimate, see formula (6). However, several problems arise with this definition. First, if we use the definition of the model through the function \"$u$\", it would be difficult to construct the function \"$\\mu$\" (the functional equation (7) would be needed to solve). Secondly, it would be nice to check experimentally how adequately a particular counter measures<\/i> the rate.<\/p>\n

    Preserving not the letter (from the formula (6)), but the spirit of the decay idea, we construct the rate estimate as a function of a single argument, namely, the relative value of the counter: \"$r(s,. Thus, the problem is set as follows: having an update function \"$u(x)$\", construct a function \"$r(x)$\" that would be an adequate estimator of the rate.<\/p>\n

    It turns out that the u-model approach consists of implementing the following plan (yes, it looks a bit punkish).<\/p>\n

      \n
    1. We take some models built from \u201cphysical considerations\u201d, and for each of them, we express the update rule through a u-function.<\/li>\n
    2. Then we abstract away from the physical sense, leaving only the bare u-function. Now we can, without worrying about the sense, boldly change the u-function, for example, by choosing a computationally cheaper one.<\/li>\n
    3. Finally, we figure out how to reintroduce meaning, i.e., to construct an adequate estimate of the rate.<\/li>\n
    4. PROFIT!<\/li>\n<\/ol>\n

      In order to make this plan possible (the snag, obviously, is only clause 3), some constraints on the u-function would have to be imposed, and now let us try to figure out which ones. The reader, however, may skip these motivational considerations and jump directly to the definition of those constraints (9) on the u-function in Section 3.<\/p>\n

      2.4.1\u00a0\u00a0 A Uniform Stream<\/h3>\n

      Our company studies network traffic, and we may need to count network packets arrivals as items. In this case, they form a stream, and its rate is measured in packets per second (pps). Alternatively, we have to take packet size into account, so the size is considered the weight of an event, and correspondingly, the rate of such a weighted stream is measured in bits per second (bps). It may also be important to distinguish packets by their contents (source and\/or destination IP address, port number, protocol, etc.), then we group events by their type and create separate counters for each type.<\/p>\n

      Since we discuss here how to evaluate the rate of an event flow, we must first formalize the notions of the event and the event stream.<\/p>\n

      Definition<\/b> (event). Let us call an event a triple \"$(id,, where \"$t$\" is the event arrival time, \"$w0$» data-tex=»inline»\/> is the event weight, \"$id$\" is the event type, some stream identifier. <\/p><\/blockquote>\n

      <\/p>\n

      Definition<\/b> (event stream). An event stream is defined as a sequence of events \"$\\mathcal{E}_k=(id_k,w_k,t_k)$\", \"$k\\in\\mathbb{Z}$\". And the events in the stream must be ordered by time: \"$t_i\\le at \"$i<j$\". <\/p><\/blockquote>\n

      In most implementations of event accounting systems, the time is considered a discrete value: \"$t_k\\in\\mathbb{Z}$\", but for theoretical reasoning, it may be convenient to generalize and consider the time continuous: \"$t_k\\in\\mathbb{R}$\".<\/p>\n

      If we are interested only in events as such, e.g., we measure the number of packets in pieces per second, then the weight \"$w$\" may be assumed to be unity. It is also assumed that a single counter counts events of the same type, i.e., the \"$id$\" field serves to distinguish different streams and does not play a role within a single counter.<\/p>\n

      Definition<\/b> (uniform stream). A deterministic uniform stream \"$\\langle is defined as follows: <\/p>\n

      \"$<\/p>\n

      Where \"$p0$» data-tex=»inline»\/> is the stream parameter, i.e., the period between events. Then the rate of such a stream, by definition, is expressed as \"$r=1\/p$\". <\/p><\/blockquote>\n

      Now we can express a way to measure the stream rate for any model. Consider a stream of some known rate \"$r$\" affecting a counter and observe how the relative value of the counter changes; let the measured counter value be \"$x_n$\" after the \"$n$\"th event.<\/p>\n

      We want the stream rate \"$r$\" and the sequence of \"$x_n$\" values to be somehow related. Then, being lucky, we could construct a rate estimation function \"$r(x)$\".<\/p>\n

      2.4.2\u00a0\u00a0 An Attractor<\/h3>\n

      Studying with concrete examples the behavior of the u-model under the influence of a deterministic stream, we found that (at least for those examples) there is a notion of an attractor, which is somewhat informally described by the following properties.<\/p>\n

        \n
      • For every rate value of the incoming stream \"$r$\", there exists an attractor, i.e., such a subset of the relative counter values that if any value \"$x_N$\" ended up in this attractor, then all subsequent values \"$x_n$\" for \"$n\\ge will also end up there. The attractor is an interval \"$[\\check{x}, (possibly degenerate, when both ends of it have merged).<\/li>\n
      • There is convergence: even if the relative value of the counter was outside the attractor, after several updates, it will get there or at least get as close to the attractor as possible.<\/li>\n
      • There is monotonicity: the position of the attractor depends monotonically on the rate of the incoming stream. That is, both ends of the segment \"$\\check{x}(r)$\" and \"$\\hat{x}(r)$\" are monotonically increasing functions.<\/li>\n<\/ul>\n

        Since we need to judge the rate of the stream by the value of the counter, we need to solve the inverse problem. This is possible due to monotonicity and continuity: there exist functions \"$\\check{r}(x), such that if \"$x$\" enters the attractor, we can guarantee that the true rate value lies in the interval \"$[\\check{r}(x),.<\/p>\n

        Of course, for these properties to be practically useful, first, the segment (attractor) must be short; otherwise, the accuracy will be low, and second, the convergence must be fast, or one will have to wait for a long time before the counter starts to show an adequate value. In any case, for a particular u-model, it is possible to write down the solution explicitly and evaluate the accuracy and speed of convergence.<\/p>\n

        Let us try to pass from the particular to the general. Now, ask a question: What conditions must be imposed on the u-function for the corresponding u-model to have an attractor with the above properties? An exhaustive answer is given in the next section.<\/p>\n

        3\u00a0\u00a0 Implementation of the U-model<\/h1>\n

        <\/p>\n

        3.1\u00a0\u00a0 Definition of the U-model<\/h2>\n

        Let the function \"$u\\colon\\mathbb{R}\\to\\mathbb{R}$\" satisfy the following conditions: <\/p>\n

        \"$<\/p>\n

        where \"$\\Delta.<\/p>\n

        Definition<\/b> (u-model). Consider a counter update method based on the function \"$u$\"
        having the properties (9), in which the counter update \"$s$\" on
        event arrival at time \"$t\\in\\mathbb{R}$\" is expressed by the rule (8): <\/p>\n

        \"$<\/p>\n

        This way of updating the counter will be called the u-model. <\/p><\/blockquote>\n

        A function \"$u$\" satisfying the conditions (9), has some useful properties. For example, the function \"$u$\" (and also \"$\\Delta) is continuous. This arises from the properties (9a) and (9c) having used the \"$\\varepsilon$\"—\"$\\delta$\"-formalism. Second, either \"$\\Delta0$» data-tex=»inline»\/> on \"$\\mathbb{R}$\", or there exists such \"$x_{max}\\in\\mathbb{R}$\" that \"$\\Delta0$» data-tex=»inline»\/> at \"$x<x_{max}$\", and \"$\\Delta at \"$x\\ge.<\/p>\n

        3.2\u00a0\u00a0 Rate Measurement<\/h2>\n

        Properties (9) are sufficient to ensure the existence of an attractor and to construct upper \"$\\hat{r}$\" and lower \"$\\check{r}$\" estimates of the rate. There are several theorems on this point, some of which are presented in this section and some of which are left out.<\/p>\n

        3.2.1\u00a0\u00a0 A Strict U-model<\/h3>\n

        We can observe that the conditions (9) do not forbid the case when the increment of the update function converts to zero at some point, that is, when \"$\\exists. In this case, \"$\\Delta will also convert to zero at all \"$xx_{zero}$» data-tex=»inline»\/>. Let us denote by <\/p>\n

        \"$0\\}\\\\ x_{max}=\\sup X,\\quad x_{max}\\in\\mathbb{R}\\cup\\{+\\infty\\}. \\end{gather*} $» data-tex=»display»\/><\/p>\n

        It is easy to prove that if we take \"$x_0\\in and apply a series of updates to it, then values larger than \"$x_{max}$\" will be unattainable, so the relative counter values will never go beyond \"$X$\". That is, \"$X=(-\\infty, may be called the operating range of the u-model. Outside this range, the u-function is arranged trivially, and we are not interested in its behavior. This caveat is needed to introduce the notion of a strict u-model.<\/p>\n

        Definition<\/b> (strict u-model). If, in addition to the properties (9) functions \"$u$\" and \"$\\Delta are strictly monotone on \"$X$\", then the corresponding u-model will be called strict.<\/i> <\/p><\/blockquote>\n

        Theorem<\/b> (fixed point theorem). For a strict u-model under the influence of a deterministic uniform rate stream \"$r$\", a sequence of values \"$x_n$\" is constant if an additional condition is satisfied: the function \"$u$\" is a compressive mapping, that is, \"$\\exists such that \"$\\forall. <\/p><\/blockquote>\n

        This directly follows from the Banach fixed-point theorem [5], which guarantees the existence and uniqueness of a fixed point in a compressible mapping. Then all terms of the sequence \"$x_n$\" will be equal to the value of this fixed point.<\/p>\n

        It turns out that in a strict u-model, the attractor consists of a single point.<\/p>\n

        In fact, not for all u-models we use the update function is a compressible mapping. For example, the EDecay model has an \u201calmost\u201d compressible update function, as for it, the constant \"$\\kappa$\" is equal to one. That means the Banach theorem does not work. But this is not a problem from the practical application point of view because there are other useful theorems.<\/p>\n

        For example, the following statement holds. <\/p>\n

        Statement.<\/b> If at some point in time the counter was in a state where its relative value was \"$x_0$\", and a deterministic stream of events began to arrive at it, then the sequence of its relative values \"$x_k$\" tends to some value of \"$x^*$\", and the convergence rate is known. In particular, for the EDecay model, the convergence looks like this: \"$|x_k-x^*|\\le, which, from a practical point of view, allows us to evaluate how quickly and adequately the model responds to changes in the traffic pattern. <\/p><\/blockquote>\n

        <\/p>\n

        3.2.2\u00a0\u00a0 A Non-strict U-model<\/h3>\n

        As for discretized models (see Section 3.3), they lose strict monotonicity, so instead of the fixed point theorem, a set of assertions (not given here) that require weaker conditions and give weaker, though still useful, results for rate estimation helps. For the non-strict model, instead of a one-to-one correspondence between the rate of the stream and the relative value of the counter, there is an interval estimate. That is, the attractor is a nondegenerate segment.<\/p>\n

        Using the proposed methodology, for a given u-model, all that remains is to construct upper \"$\\hat{r}$\" and lower \"$\\check{r}$\" estimates of the rate and find out how rapidly the \"$x_n$\" sequence converges to the attractor.<\/p>\n

        3.3\u00a0\u00a0 Discretization<\/h2>\n

        In order to use the u-model in practice, it must be discretized. That is, to make the set of counter states finite and preferably small in size. Why small? We need to keep billions of counters in memory; the more of them, the higher will be the quality of service. Indeed, why should we waste 64 bits per counter when we can do with 16?<\/p>\n

        Remark<\/b> <\/p>\n
        One may go for the trick of complicating the state representation by assuming it as a pair \"$s=(s_{local},, where \"$s_{local}$\" refers to a particular counter, and \"$s_{global}$\" is the common part of the state of a whole group of counters. We do use this technique, in particular, to deal with counter overflows, but we do not consider it in this paper. <\/div>\n<\/p><\/div>\n

        One obvious way to discretize is to select a finite subset of consecutive integers from the continuum of relative counter values and modify the u-function slightly to become an integer.<\/p>\n

        First, let us construct a function \"$u^\\sqcup\\colon such that:<\/p>\n