Измерение интенсивности трафика при помощи u-моделей02.07.2021 23:47

stream rate art
Измерение интенсивности потоков в представлении художника.

В одной из наших предыдущих публикаций мы рассказывали о способе измерения интенсивности потока событий при помощи счетчика на основе экспоненциального распада. Оказывается, идея такого счетчика имеет интересное обобщение, о котором в этой публикации расскажут сотрудники компании Qrator Labs Артем Шворин и Дмитрий Камальдинов.
План погружения у нас следующий. Для начала рассмотрим и проанализируем несколько примеров того, как вообще считают события и оценивают интенсивность потока. Дальнейший шаг — увидеть обобщение, а именно — некоторый класс счетчиков, который мы называем u-моделью. После мы исследуем, какими полезными свойствами обладают u-модели, и предлагаем методику построения адекватной оценки интенсивности.


Без ограничения общности можно считать, что счетчик событий описывается своим состоянием $s$, которое по приходе события в момент времени $t$ обновляется по некоторому правилу:

$ s\mathop{\mapsto}^t s'. $


Состояние не обязательно выражается числом, но из соображений практической реализуемости можно считать, что оно представляется конечным набором битов.

В некоторых случаях события являются взвешенными, и при обновлении состояния требуется учитывать вес события $w$:

$ s\mathop{\mapsto}^{t,w} s'. $


Но для начала будем рассматривать простые невзвешенные события, а учет веса добавим потом, когда понадобится. Это будет совсем не сложно.

В этой статье мы ограничимся рассмотрением только детерминированных счетчиков, то есть таких, для которых правило обновления задается функцией $s'=update(s,t)$. Но вообще в этот механизм бывает полезно добавить немного рандома, об этом мы недавно рассказывали [7] и, вероятно, продолжим еще.

Также должна быть возможность, зная состояние счетчика, оценить интенсивность потока. Вообще говоря, понятие интенсивности потока нетривиально, и позже мы его обсудим подробнее. Пока же будем просто считать, что к модели счетчика прилагается некоторая номинальная оценка в виде функции $r(s,t)$, выписанная из каких-то конструктивных соображений.

1.1   Линейные счетчики: подсчет всех событий


Самое простое, что можно придумать, — простой подсчет количества событий, произошедших с момента запуска. То есть по приходе события делаем вот так:

$ s \mapsto s + 1. $


Будем называть такие счетчики линейными.

Оценка представляет собой среднюю интенсивность за всю историю:

$ r(s,t) = s/t. $


Некоторую проблему может составлять то, что счетчик может переполниться. Также есть вопросы к тому, как задать оценку — очень старые события оказывают такое же влияние на оценку, как и недавние.

1.1.1   Подсчет событий в скользящем окне


Для устранения вышеописанных недостатков линейных счетчиков можно подсчитывать количество событий не с сотворения мира, а только тех, что произошли не более чем $T$ тактов назад. Этот временной интервал длины $T$ обычно называется окном, причем скользящим, поскольку с каждым тактом смещается вперед.

Наивная реализация предполагает запоминать все события в окне, что требует $O(T)$ памяти. Однако есть способы сэкономить ресурсы в обмен на снижение точности, как это делают, например, здесь [6]. Правило обновления выражается довольно сложно, а в роли оценки будет средняя интенсивность за время $T$:

$ r(s,t) = s/T. $


К сожалению, и эта разновидность линейных счетчиков для наших целей не подходит: снижение точности еще можно потерпеть, а $O(\log T)$ по памяти и по сложности выходит слишком накладно даже при небольших $T$.

1.2   EDecay: экспоненциальный распад


Идея распадных счетчиков навеяна известной концепцией радиоактивного распада [4]. Ее суть состоит в том, что с течением времени количество нераспавшегося вещества уменьшается со временем по экспоненциальному закону:

$v(t) = v_0 e^{-\lambda t},$


где $v_0$ — количество вещества в начальный (нулевой) момент времени, $\lambda$ — некоторый параметр, так называемая постоянная распада.

Удобней переписать это выражение в таком виде:

$v(t) = v_0 \alpha^{-t},$


заменив параметр. Более подробно о параметризации моделей счетчиков см. раздел A приложения.

На основе этого механизма можно построить счетчик событий, как было описано в нашей статье [1].

Будем по определению считать, что каждому типу события соответствует величина $v$, имеющая физический смысл «количества вещества» и зависящая от времени, которая при наступлении события скачком увеличивается на единицу, а в остальное время уменьшается по приведенному выше экспоненциальному закону.

То есть, чтобы учесть новое событие, пришедшее в момент времени $t$, сначала нужно применить распад, а затем увеличить счетчик на единицу:

$ \begin{equation*} v_{new}(t) = v(t) + 1 \equiv v(t_0)\alpha^{-(t - t_0)} + 1, \end{equation*} $


где $t_0$ — время прихода предыдущего события.

Чтобы этим можно было пользоваться, нужно придумать, как хранить счетчик в памяти. Самый простой способ представления состояния счетчика — пара чисел $(v, t_0)$, где $t_0$ — время последнего обновления, а $v$ — количество вещества в этот момент. В этом случае правило обновления и оценку можно записать так:

$ \begin{align*} (v, t_0) &\mathop{\mapsto}^t (v \alpha^{-(t - t_0)} + 1, t) \\ r((v, t_0), t) &= v \alpha^{-(t - t_0)}. \end{align*} $


В статье [1] мы детально разбираем такие счетчики. Важной идеей, которую здесь уместно упомянуть, является более экономичное предстваление состояние счетчика в виде одного числа $s$, так называемого абсолютного значения, несущего в себе всю необходимую информацию для работы со счетчиком.
Величина $v$ не хранится явно в памяти, но может быть вычислена в любой момент. Хранится же значение $s$, такое что в момент времени $t$ величина $v$ выражается следующим образом:

$ v = \alpha^{s-t}. $


Не вдаваясь в подробности, скажем лишь, что при таком подходе правило обновления и оценка принимают вид:

$ \begin{align} s &\mathop{\mapsto}^t t+\log_\alpha(1 + \alpha^{s - t}) \tag{1}\\ r(s, t) &= \alpha^{s - t}.\nonumber \end{align} $

1.3   QDecay: более быстрый распад


При рассмотрении модели экспоненциального распада можно заметить, что функция распада (в данном случае экспонента) удовлетворяет дифференциальному уравнению:

$\frac{dv}{dt} = -\lambda v.$


На самом деле, с физической точки зрения, скорее, наоборот — именно это уравнение описывает радиоактивный распад, а экспонента — его решение.

Действительно, смысл уравнения состоит в том, что скорость распада пропорциональна количеству имеющегося вещества. В какой-то момент нам захотелось, чтобы распад в модели происходил побыстрее, для этого мы попробовали взять не линейную, а квадратичную зависимость (quadratic decay, QDecay):

$\frac{dv}{dt} = -\lambda v^2.$


Решение — новая функция распада:

$ v(t) = \frac{1}{\lambda t + 1/v_0}, $


и она действительно стала покруче.
На самом деле…
Вряд ли корректно говорить, что гипербола круче экспоненты. Но распад больших значений теперь и правда происходит быстрее (а малых — медленнее).

Аналогично рассмотренной ранее модели (с экспоненциальным распадом), здесь можно представить состояние счетчика в виде одного числа $s$. Соответствующее правило обновления и оценка интенсивности выглядят так:

$ \begin{align} s &\mathop{\mapsto}^t t - \frac{t-s}{1 + \lambda(t - s)} \tag{2} \\ r(s, t) &= \frac{1}{\lambda(t - s)}.\nonumber \end{align} $


Здесь замечательно то, что вычисление функции обновления обходится дешево — оно требует только элементарных арифметических операций, причем деление только одно. То есть изначально мы хотели всего лишь более быструю лошадь (распад), а получили новое полезное качество (меньше вычислений).

Можно пойти дальше, взяв бо́льшую степень в уравнении на функцию распада: $dv = -\lambda v^3 dt,$ и так далее, но решение получается сложнее, вычисления дороже, а явной выгоды как-то не заметно. Не пригодилось.

1.4   SW: усреднение межпакетных интервалов


Рассмотрим еще один подход к построению счетчиков, а именно — усреднение. В данном случае будем усреднять интервал времени между соседними событиями. Мы называем эту величину межпакетным интервалом, поскольку имеем дело с сетевым трафиком, где в качестве события выступает приход сетевого пакета, а слово «межсобытийный» как-то не прижилось.

Вообще говоря, смысл этого подхода заключается в том, что у нас есть последовательность значений некоторой величины (в данном случае межпакетных интевалов), которая слишком быстро меняется, чтобы ее можно было использовать непосредственно, и хочется эту последовательность каким-то образом сгладить или усреднить.

Определение усреднения

Напомним, что чем новее события, тем интереснее нам их вклад в оценку интенсивности. Поэтому вместо обычного усреднения естественно использовать взвешенное, давая больший вес недавним событиям. Выбирать веса можно по-разному, сейчас попробуем взять веса в виде членов геометрической прогрессии. Такой способ суммирования называется экспоненциальным скользящим средним (EMA).

Определение EMA-усреднения

Применяя формулу экспоненциального усреднения к межпакетным интервалам, получим:

$ v_n = \beta\cdot (t_n-t_{n-1}) + (1-\beta)\cdot v_{n-1}, $


где $v_n$ — искомый EMA-усредненный межпакетный интервал, $t_n$ — момент наступления $n$-го события.

Эта модель еще раз упоминается в разделе 4.3, где, в частности, показано, как выразить состояние счетчика одним числом и упростить вычисления. Пока же просто выпишем результат.

Обновление счетчика по приходе события в момент времени $t$:

$ \begin{equation}\tag{4} s \mathop{\mapsto}^t t + \beta\cdot(s-t). \end{equation} $


В качестве оценки интенсивности берется обратная величина усредненного значения межпакетного интервала:

$ r(s,t) = -\frac{\beta}{1-\beta}\cdot\frac{1}{s-t}. $


Замечание
При помощи EMA-усреднения можно получить модель, в точности совпадающую с распадной моделью из раздела 1.2. Для этого надо усреднять не межпакетные интервалы, а величину $p_t$, которую можно было бы назвать мгновенной интенсивностью:

$ p_t = \left\{ \begin{array}{ll}1, & \mbox{если в момент t произошло событие},\\ 0, & \mbox{иначе}. \end{array} \right. $



1.5   Вероятностные счетчики


Идея вероятностных счетчиков — менять состояние счетчика по приходе события не всегда, а с некоторой вероятностью. Эту вероятность можно задавать по-разному, например
  • держать ее постоянной (биномиальные счетчики);
  • уменьшать в 2 раза после каждого успешного обновления (счетчики Морриса);
  • менять после каждых $X > 1$» /> успешных обновлений.</li> </ul><br />Вероятностные счетчики позволяют очень эффективно использовать память. Например, оригинальные 8-битные счетчики Морриса можно использовать для учета до <img src= событий. Очевидным же их недостатком является значительная ошибка при оценке числа событий. Мы подробно разбираем такие счетчики в статье [7], а также предлагаем некоторые расширения известных алгоритмов.
    Если посмотреть на счетчики, основанные на идее распада, то можно заметить такую особенность: состояние описывается парой чисел $(v, t)$, но потом чудесным образом удается выразить состояние одним числом $s$. Попробуем найти общий принцип, по которому это становится возможно для любых счетчиков такого типа.

    Временно забудем тот факт, что на практике значение счетчика должно быть дискретно и описываться сравнительно небольшим количеством бит, и, оставаясь в рамках вакуумной сфероиппологии, положим, что и значение счетчика, и время прихода событий являются вещественными числами, а также преобразования над ними будут, соответственно, вещественнозначными. Потом (см. раздел 3.3) научимся дискретизировать модели, делая их пригодными на практике.

    2.1   Инвариант распада


    Рассмотрим участок кривой распада (см. рис. 1a). Пусть в момент времени $t_0$ было зарегистрировано событие, и потом на интервале $[t_0, t)$ других событий не было. Сейчас находимся в точке $t$ и собираемся учесть новое событие или хотя бы просто посмотреть, какова величина $v$ в этот момент, чтобы оценить интенсивность. Можно заметить, что с точки зрения наблюдателя, находящегося в моменте $t$, нет совершенно никакой разницы, находится ли последнее событие на графике в точке $(t_0, v_0)$ или же в точке $(t'_0, v'_0)$. Сей факт как бы намекает, что хранить два числа в качестве состояния — явно избыточно. Таким образом, два формально разных варианта реальности функционально эквиалентны, то есть дают один и тот же эффект:

    $ (t_0,v_0) \sim (t'_0, v'_0). $


    decay curves
    Вообще говоря, у нас не одна распадная кривая, а целое семейство $v=v_s(t)$ (см. рис. 1b). Каждая из этих кривых описывает одно и то же состояние. Их можно некоторым образом занумеровать, и в качестве состояния счетчика взять номер, точнее, индекс кривой.

    Посмотрим теперь, как должно происходит обновление такого счетчика. Пусть $s$ — текущее состояние счетчика. Согласно распадной модели, это значит, что при отсутствии событий значение $v$ с течением времени будет меняться, оставаясь на кривой $v_s(t)$. Пусть в некоторый момент времени $t$ происходит событие. Это значит, что величина $v$ скачком увеличивается на единицу (см. рис. 1c), то есть среди всего семейства кривых надо найти ту, которая проходит через точку $(t, v')$, где $v'=v+1$. Пусть $s'$ — индекс этой кривой, то есть

    $ \begin{equation}\tag{5} v_{s'}(t) = v_s(t) + 1, \end{equation} $


    тогда именно это значение $s'$ нужно записать в качестве нового состояния счетчика.
    Замечание
    Если нужно учитывать взвешенные события, то изменение происходит не на единицу, а на вес события: $v'=v+w$.

    Пока не очень понятно, как находить индекс нужной кривой, но совсем скоро это прояснится.

    2.2   Трансляционная симметрия


    На рис. 1b распадные кривые $v_s(t)$ изображены так, что они отличаются друг от друга только сдвигом по горизонтали. По-научному это называется трансляционная симметрия времени [8]. Мы хотим взять это свойство в качестве аксиомы для нашей модели счетчика. Действительно, логично ожидать, что в рамках модели распад сегодня происходит в точности так же, как вчера.

    Математически это можно свойство записать так:

    $ \forall t\in\mathbb{R}\colon v_{s_2}(t) = v_{s_1}(t-\Delta), $


    то есть кривая $v_{s_2}(t)$ получается из кривой $v_{s_1}(t)$ сдвигом вправо на некоторую величину $\Delta$.

    Вообще кривые можно занумеровать как попало, нужно лишь уметь находить индекс новой кривой при операции обновления. Но удобнее всё же нумеровать по порядку, так чтобы индекс $s$ представлял собой что-то осмысленное, а именно — вещественное число, соотвествующее расстоянию по горизонтали между данной кривой $v_s(t)$ и кривой с нулевым индексом $v_0(t)$. Тогда, благодаря трансляционной симметрии, любая кривая из семейства очень просто выражается через кривую номер ноль:

    $ \begin{equation} \forall t,s\in\mathbb{R}\colon v_s(t) = v_0(t-s)\equiv \mu(s-t).\tag{6} \end{equation} $

    Замечание
    Здесь введено обозначение $\mu(x) := v_0(-x)$, которое удобно тем, что функция $\mu$ монотонно возрастает. Это потом пригодится в разделе 2.4 при определении интенсивности.

    Теперь правило обновления по приходе события в момент времени $t$ можно выразить из уравнения (5) следующим образом:

    $ s' = t + u(s-t),\quad \text{где } $

    $ \begin{equation} u(x) = \mu^{-1}(\mu(x) + 1).\tag{7} \end{equation} $

    Таким образом, правило обновления представляется в виде

    $ \begin{equation}\tag{8} s \mathop{\mapsto}^t t + u(s-t), \end{equation} $


    где $u(\cdot)$ — некоторая функция.

    Это правило выглядит настолько просто и универсально, что его можно взять в качестве определения. Именно так мы будем определять u-модель.

    Замечание
    Если распадная функция задается дифференциальным уравнением вида

    $ \frac{dv}{dt} = f(v), $


    то для нее всегда легко находится инвариант, который обладает свойством (6).

    Действительно, решение дифференциального уравнения можно записать в виде

    $ F(v) - F(v_0) = t - t_0,\quad\mbox{где } F(v) = \int \frac{dv}{f(v)}. $


    Тогда в качестве инварианта можно взять $s = t_0-F(v_0)$, а соответствующая кривая выражается как $v_s(t)=F^{-1}(t-s)$.

    В разделе 3.1 перечислены формальные свойства, которым должна удовлетворять функция $u$, чтобы на ее основе построить работоспособную модель счетчика.

    2.3   Абсолютное и относительное


    Можно сказать, что $s$ — это абсолютное значение счетчика, оно хранится непосредственно в памяти, а $x=s-t$ — относительное значение счетчика в момент времени $t$. Тогда получается, что функция обновления работает с относительным значением счетчика: $x' = u(x)$.

    Тот факт, что функция обновления работает с относительным значением счетчика, отражает принцип распада: если события не происходят, то абсолютное значение $s$ не меняется, а относительное — автоматически убывает с течением времени. И оценка интенсивности, соответственно, тоже будет падать. С точки зрения вычислений очень удобно — пока событий нет, ничего делать не надо. Очень похоже на инфляцию в экономике: состояние счетчика — это банкноты, лежащие под подушкой, а оценка интенсивности — покупательная способность этих банкнот, которая сама собой деградирует.

    2.4   Оценка интенсивности


    Для распадной модели значение $\mu(s-t)$ по построению является оценкой интенсивности (см. формулу (6)). Однако с таким определением возникают некоторые проблемы. Во-первых, если мы используем определение модели через функцию $u$, построить функцию $\mu$ будет затруднительно (пришлось бы решать функциональное уравнение (7)). Во-вторых, было бы неплохо проверить экспериментально, насколько адекватно конкретный счетчик измеряет интенсивность.

    Сохраняя не букву (из формулы (6)), но дух идеи распда, будем строить оценку интенсивности как функцию от одного аргумента, а именно — от относительного значения счетчика: $r(s, t) = r(s-t)$. Таким образом, задача ставится так: имея функцию обновления $u(x)$, построить фукнцию $r(x)$, которая была бы адекватной оценкой интенсивности.

    Получается, что подход u-модели состоит в реализации следующего плана (да, выглядит несколько по-панковски).

    1. Берем какие-нибудь модели, построенные из «физических соображений», и для каждой из них выражаем правило обновления через u-функцию.
    2. Затем абстрагируемся от физического смысла, оставляя только голую u-функцию. Теперь можно, не заботясь о смысле, смело менять u-функцию, например, выбирая более вычислительно дешевую.
    3. Наконец, придумываем, как заново внести смысл — построить адекватную оценку интенсивности.
    4. PROFIT!

    Для того, чтобы этот план стал возможным — загвоздка, очевидно, только в пункте 3, — потребуется наложить какие-то ограничения на u-функцию, и сейчас попробуем выяснить, какие именно. Эти мотивационные рассуждения, однако, можно пропустить и сразу перейти к определению ограничений (9) на u-функцию.

    2.4.1   Равномерный поток


    Наша компания занимаемся изучением трафика в сети, и мы можем считать приход сетевых пакетов штуками — это будет поток, интенсивность которого измеряется в пакетах в секунду (pps, packets per second). А можем учитывать размер пакетов, тогда размер выступает в качестве веса события, соответственно, интенсивность такого взвешенного потока будет измеряться в битах в секунду (bps, bits per second). Бывает также важным различать пакеты по их содержимому (IP-адреса источника и/или получателя, номера портов, протокол и т.п.), тогда мы группируем события по типам и для каждого типа заводим отдельные счетчики.

    Поскольку мы здесь занимаемся оценкой интенсивности потока событий, нужно вначале формализовать понятия события и потока событий.

    Определение (событие). Событием назовем тройку $(id, w, t)$, где $t$ — время прихода события, $w>0$» /> — вес события, <img src= — тип события, некоторый идентификатор потока.
    Определение (поток событий). Поток событий определяется как последовательность событий $\mathcal{E}_k=(id_k,w_k,t_k)$, $k\in\mathbb{Z}$. Причем события в потоке должны быть упорядочены по времени: $t_i\le t_j$ при $i<j$.

    В большинстве реализаций систем учета событий время считается дискретной величиной: $t_k\in\mathbb{Z}$, однако для теоретических рассуждений бывает удобно обобщить и считать время непрерывным: $t_k\in\mathbb{R}$.

    Если нас интересуют только события как таковые, например, мы измеряем количество пакетов штуками в секунду, то вес $w$ можно полагать равным единице. Предполагается также, что отдельный счетчик учитывает события одного типа, то есть поле $id$ служит для различения разных потоков и не играет роли рамках одного счетика.

    Определение (равномерный поток). Детерминированный равномерный поток $\langle t_k\rangle$ определяется следующим образом:

    $ t_k = pk,\quad k\in\mathbb{Z}, $


    где $p>0$» /> — параметр потока — период между событиями. Тогда интенсивность такого потока, по определению, выражается как <img src=.

    Теперь можно выразить способ измерения интенсивности потока для любой модели. Пусть на счетчик набегает поток некоторой известной интенсивности $r$, и мы наблюдаем, как меняется относительное значение счетчика — пусть после $n$-го события измеренное значение счетчика равно $x_n$.

    Хочется, чтобы интенсивность потока $r$ и последовательность значений $x_n$ были как-то связаны между собой. Тогда, если повезет, мы могли бы построить функцию оценки интенсивности $r(x)$.

    2.4.2   Аттрактор


    Изучая на конкретных примерах поведение u-модели под воздействием детерминированного потока, мы обнаружили, что (по крайней мере для этих примеров) существует понятие аттрактора, который не вполне формально описывается следующими свойствами.

    Поскольку нам нужно по значению счетчика судить об интенсивности потока, требуется решить обратную задачу. Это возможно в силу монотонности и непрерывности — существуют функции $\check{r}(x), \hat{r}(x)$, такие что при попадании $x$ в аттрактор, можно гарантировать, что истинное значение интенсивности лежит в интервале $[\check{r}(x), \hat{r}(x)]$.

    Разумеется, для того чтобы эти свойства были практически полезными, нужно, чтобы, во-первых, отрезок-аттрактор был коротким, иначе точность будет низкой, во-вторых, чтобы сходимость была быстрой, иначе придется долго ждать, прежде чем счетчик начнет показывать адекватное значение. В любом случае для конкретной u-модели можно записать решение в явном виде и оценить точность и скорость сходимости.

    Теперь попробуем перейти от частного к общему. Зададимся вопросом: какие условия нужно наложить на u-функцию, чтобы у соответствующей u-модели появился аттрактор с указанными выше свойствами? Исчерпывающий ответ изложен в следующем разделе.


    3.1   Определение u-модели


    Пусть функция $u\colon\mathbb{R}\to\mathbb{R}$ удовлетворяет следующим условиям:
    \begin{gather}
    u (x)\text{ возрастает},\tag{9a}\\
    \Delta u (x) \ge 0\text{ при всех }x,\tag{9b}\\
    \Delta u (x)\text{ убывает},\tag{9c}\\
    \Delta u (+\infty)=0,\tag{9d}
    \end{gather}
    где $\Delta u(x) = u(x)-x$.
    Определение (u-модель). Рассмотрим способ обновления счетчика, построенный на основе функции $u$, обладающей свойствами (9), при котором обновление счетчика $s$ по приходе события в момент времени $t\in\mathbb{R}$ выражается правилом (8):

    $ s\mathop{\mapsto}^t t + u(s-t). $


    Такой способ обновления счетчика назовем u-моделью обновления.

    Функция $u$, удовлетворяющая условиям (9), обладает некоторыми полезными свойствами. Например, функция $u$ (а также $\Delta u$) непрерывна. Это доказывается из свойств (9a) и (9c) с помощью $\varepsilon$-$\delta$-формализма.

    3.2   Измерение интенсивности


    Свойств (9) оказывается достаточно, чтобы обеспечить существование аттрактора и построить верхнюю $\hat{r}$ и нижнюю $\check{r}$ оценки интенсивности. На этот счет есть несколько теорем, часть из которых представлена в этом разделе, а часть осталась за кадром.

    3.2.1   Строгая u-модель


    Можно заметить, что условия (9) не запрещают случай, когда приращение функции обновления обращается в ноль в некоторой точке, то есть когда $\exists x_{zero}\colon \Delta u(x_{zero})=0$. В этом случае $\Delta u$ будет обращаться в ноль и при всех $x>x_{zero}$» />. Обозначим<br />\begin{gather*}<br />X = \{x\mid \Delta u (x)>0\}\\<br />x_{max}=\sup X,\quad x_{max}\in\mathbb{R}\cup\{+\infty\}.<br />\end{gather*}<br />Несложно доказать, что если взять <img src= и применить к нему серию обновлений, то значения, бо́льшие чем $x_{max}$, будут недостижимы — относительные значения счетчика никогда не выйдут за пределы $X$. То есть $X=(-\infty, x_{max})$ можно назвать рабочим диапазоном u-модели. Вне этого диапазона u-функция устроена тривиально, и ее поведение нам не интересно. Эта оговорка нужна, чтобы ввести понятие строгой u-модели.
    Определение (строгая u-модель). Если в дополнение к свойствам (9) функции $u$ и $\Delta u$ являются строго монотонными на $X$, то соответствующую u-модель обновления назовем строгой.
    Теорема (теорема о неподвижной точке). Для строгой u-модели при воздействии детерминированного равномерного потока интенсивности $r$ последовательность значений $x_n$ является константной, если выполнено дополнительное условие: функция $u$ является сжимающим отображением, то есть $\exists \kappa\in(0,1)$, такое что $\forall a \forall b\colon |u(a) - u(b)| < \kappa|a-b|$.

    Идея доказательства заключается в применении теоремы Банаха [5], которая гарантирует существование и единственность неподвижной точки у сжимающего отображения. Тогда все члены последовательности © Habrahabr.ru