Сетевое исчисление

В сетевом исчислении поток моделируется накопительной функцией A, где A(t) — количество данных (например, число битов), переданных потоком за интервал времени [0,t). Такие функции неотрицательны и неубывающи. Временная область часто представляется неотрицательными вещественными числами.

${\displaystyle A:\mathbb {R} ^{+}\rightarrow \mathbb {R} ^{+}}$

${\displaystyle \forall u,t\in \mathbb {R} ^{+}:u<t\implies A(u)\leq A(t)}$

Сервер может быть каналом, планировщиком, формирователем трафика или даже целой сетью. Он моделируется как отношение между некоторой накопительной кривой прихода A и накопительной кривой выбытия D. Требуется, чтобы A \geq D, что отражает невозможность ухода данных до их появления.

Для заданных кривых прихода A и выбытия D, запас (backlog) в момент t, обозначается b(A,D,t), определяется как разность между A(t) и D(t). Задержка в момент t, d(A,D,t), — это минимальное время, через которое функция выбытия достигает значения функции прихода. Для всего потока используется супремум этих величин.

Горизонтальное и вертикальное отклонения между накопительными кривыми прихода и выбытия

${\displaystyle b(A,D,t):=A(t)-D(t)}$

${\displaystyle d(A,D,t):=\inf \left\{d\in \mathbb {R} ^{+}~\mathrm {s.t.} ~D(t+d)\geq A(t)\right\}}$

${\displaystyle b(A,D):=\sup _{t\geq 0}\left\{A(t)-D(t)\right\}}$

${\displaystyle d(A,D):=\sup _{t\geq 0}\left\{\inf \left\{d\in \mathbb {R} ^{+}~\mathrm {s.t.} ~D(t+d)\geq A(t)\right\}\right\}}$

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

Сетевое исчисление широко использует min-плюс полукольцо (иногда называемое мин-плюс алгеброй).

В теории фильтров и линейных систем свёртка двух функций ${\displaystyle f}$ и ${\displaystyle g}$ определяется как

${\displaystyle (f\ast g)(t):=\int _{0}^{t}f(\tau )\cdot g(t-\tau )d\tau }$

В мин-плюс полукольце операция сложения заменяется минимумом (или инфимумом), а операция умножения — обычным сложением. Мин-плюс свёртка двух функций ${\displaystyle f}$ и ${\displaystyle g}$ задаётся выражением

${\displaystyle (f\otimes g)(t):=\inf _{0\leq \tau \leq t}\left\{f(\tau )+g(t-\tau )\right\}}$

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

Операция мин-плюс деконволюции определяется как

${\displaystyle (f\oslash g)(t):=\sup _{\tau \geq 0}\left\{f(t+\tau )-g(\tau )\right\}}$

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

Вертикальные и горизонтальные отклонения могут быть выражены через мин-плюс операторы:

${\displaystyle b(f,g)=(f\oslash g)(0)}$

${\displaystyle d(f,g)=\inf\{w:(f\oslash g)(-w)\leq 0\}}$

Накопительные кривые отражают реальные траектории, неизвестные при проектировании. Заданы лишь некоторые ограничения. Сетевое исчисление оперирует понятием общееограничителя трафика, также называемого кривой прихода.

Накопительная функция A считается удовлетворяющей ограничителю E (также кривой прихода, α), если для любого t выполняется

${\displaystyle E(t)\geq \sup _{\tau \geq 0}\{A(t+\tau )-A(\tau )\}=(A\oslash A)(t).}$

Возможно два эквивалентных определения:

${\displaystyle \forall t,d\in \mathbb {R} ^{+}:A(t+d)-A(t)\leq E(d)}$

${\displaystyle A\leq A\otimes E}$

Таким образом, E накладывает верхнее ограничение на поток A. Такая функция E — это "конверт", задающий верхнюю границу на объём передачи за любой интервал длины d, начиная с произвольного t.

Для обеспечения гарантий производительности потокам трафика требуется задать минимальный уровень обслуживания со стороны сервера (в зависимости от резервирования ресурсов в сети, политики планирования и т.п.). Сервисные кривые позволяют выразить доступность ресурсов. Существует несколько видов сервисных кривых — строго минимальная, с переменной пропускной способностью и др^[3].^[4]

Пусть A — поток прихода на вход сервера, а D — поток на выходе. Система обеспечивает простую минимальную сервисную кривую S для пары (A,D), если для любого t выполняется: ${\displaystyle D(t)\geq (A\otimes S)(t).}$

Пусть A — поток прихода, D — поток выбытия. Период запаса — это интервал I, где для любого момента t \in I, A(t)>D(t).

Система обеспечивает строго минимальную сервисную кривую S для (A,D), если для всех s, t \in \mathbb R^+, где s \leq t, и если (s,t] — период запаса, то D(t)-D(s) \geq S(t-s).

Если сервер предоставляет строго минимальную сервисную кривую S, то он также предоставляет и простую минимальную сервисную кривую S.

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

Основные обозначения в сетевом исчислении

Название понятия	Обозначения	Комментарии
Накопительная кривая	${\displaystyle R,A,F}$	В первых публикациях применялось ${\displaystyle R}$[1], ${\displaystyle F}$ — для "flow" (поток), ${\displaystyle A}$ — для "arrival" (приход).
Входная/выходная пары кривых	${\displaystyle (R_{in},R_{out})}$, ${\displaystyle (R,R^{*})}$, ${\displaystyle (A,D)}$, ${\displaystyle (F^{in},F^{out})}$	Изначально — ${\displaystyle (R,R^{*})}$. ${\displaystyle (A,D)}$ — "arrival/departure". ${\displaystyle (F^{in},F^{out})}$ — входящий/исходящий потоки.
Ограничитель/кривая прихода	${\displaystyle E,\alpha }$	При употреблении "ограничитель" используют ${\displaystyle E}$, при "кривая прихода" — ${\displaystyle \alpha }$.
Сервисная кривая	${\displaystyle S,\beta }$	Обычно используются либо ${\displaystyle E,S}$, либо ${\displaystyle \alpha ,\beta }$.
Задержка, горизонтальное отклонение	${\displaystyle d(A,D),h(A,D),hDev(A,D)}$	"Горизонтальное отклонение" — математическое определение, "задержка" — смысловое.
Запас, вертикальное отклонение	${\displaystyle b(A,D),v(A,D),vDev(A,D)}$	"Вертикальное отклонение" — математика, "запас" (backlog) — семантика.
Свёртка	${\displaystyle *,\otimes }$
Деконволюция	${\displaystyle \oslash }$

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

Пусть A — поток прихода на вход сервера, D — поток на выходе, E — ограничитель (кривая прихода), S — сервисная кривая. Тогда:

${\displaystyle b(A,D)\leq b(E,S)}$

${\displaystyle d(A,D)\leq d(E,S)}$

Кроме того, кривая выбытия имеет ограничитель ${\displaystyle E'=E\oslash S}$.

Эти оценки точны: при заданных E, S можно построить такие кривые прихода и выбытия, что {{{1}}} и {{{1}}}.

Рассмотрим последовательность из двух серверов: выход первого является входом второго. Тогда этот каскад можно рассматривать как новый сервер, полученный конкатенацией двух других.

Если первый (соответственно второй) сервер обеспечивает простую минимальную сервисную кривую ${\displaystyle S_{1}}$ (соответственно ${\displaystyle S_{2}}$), то вся последовательность обеспечивает простую минимальную сервисную кривую ${\displaystyle S_{e2e}=S_{1}\otimes S_{2}}$.

Доказательство использует итерацию определений сервисной кривой ${\displaystyle X\geq A\otimes S_{1}}$, ${\displaystyle D\geq X\otimes S_{2}}$ и свойства свёртки — изотоничность (${\displaystyle D\geq (X\otimes S_{2})\otimes S_{1}}$), ассоциативность (${\displaystyle D\geq X\otimes (S_{2}\otimes S_{1})}$).

Важность этого результата в том, что сквозная оценка максимальной задержки не превышает суммы локальных задержек: ${\displaystyle d(E,S_{2}\otimes S_{1})\leq d(E,S_{1})+d(E\oslash S_{1},S_{2})}$

Этот результат известен как оплатить всплеск только один раз (Pay burst only once, PBOO).

Существует ряд инструментов, основанных на сетевом исчислении. Их сравнение приведено в работе^[5].

Существуют инструменты и библиотеки для работы с мин-плюс алгеброй:

• Network calculus interpreter — онлайн-интерпретатор (min,+).
• Nancy — C#-библиотека, реализующая мин-плюс и макс-плюс операции.
• MIN-plus ExpRession VErification (Minerve) — библиотека Coq для проверки корректности мин-плюс операций^[6].

Все эти инструменты и библиотеки реализуют алгоритмы из статьи^[7].

• DiscoDNC — научная Java-реализация фреймворка сетевого исчисления^[8].
• RTC Toolbox — академическая реализация Real-Time calculus на Java/MATLAB, теория близка к сетевому исчислению^[3].^[9]
• CyNC^[10] — MATLAB/Symulink toolbox, базируется на RTC Toolbox; используется в обучении в Ольборгском университете.
• RTaW-PEGASE — промышленный инструмент анализа временных характеристик коммутируемых сетей Ethernet (AFDX, промышленные и автомобильные Ethernet), базируется на сетевом исчислении^[11].
• DYRECTsn — научный Python-инструмент для анализа динамических потоков в Time-Sensitive Networking (TSN); включает офлайн-оптимизацию и онлайн контроль допуска реального времени^[12].
• WOPANets — академический инструмент, совмещающий анализ на основе сетевого исчисления и оптимизации^[13].
• DelayLyzer — промышленный инструмент для вычисления оценок задержек в сетях Profinet.
• DEBORAH — инструмент для анализа сетей FIFO.
• NetCalBounds — инструмент для анализа "слепых" и FIFO-каскадных сетей.
• NCBounds — инструмент на Python; поддерживает топологии с циклами, учитывает rate-latency серверы и token-bucket ограничители трафика.
• Siemens Network Planner (SINETPLAN) использует сетевое исчисление для проектирования сетей PROFINET^[14].
• experimental modular TFA (xTFA) — Python-код, поддержка PhD-диссертации L. Thomas^[15]
• Panco — Python-реализация вычисления границ сетевого исчисления с помощью методов линейного программирования.
• Saihu — Python-интерфейс интеграции инструментов xTFA, DiscoDNC и Panco.
• CCAC — SMT-основанный инструмент для проверки свойств производительности алгоритмов управления перегрузкой с использованием модели, близкой к сетевому исчислению.
• AFDX Performance Analysis Tool — набор инструментов для анализа и оптимизации сетей AFDX с поддержкой разных дисциплин обслуживания (FIFO, SPQ, DRR, WRR), созданный в рамках PhD Аакаша Сони^[16].

Мастер-класс WoNeCa — Workshop on Network Calculus — проводится раз в два года и объединяет исследователей теории сетевого исчисления и практиков. Также служит площадкой для популяризации сетевого исчисления среди специалистов по прикладным моделям очередей.

• WoNeCa7, прошёл в Тронхейме, Норвегия, в рамках 36-го Международного телетрафик-конгресса (ITC 36).
• WoNeCa6 состоялся на базе EPFL 8–9 сентября 2022 г. в Лозанне, Швейцария.
• WoNeCa5 прошёл в онлайн-формате из-за пандемии COVID-19 9 октября 2020 г.
• WoNeCa4 — 19-я Международная конференция по измерениям, моделированию и оценке вычислительных систем (MMB2018), 28 февраля 2018 г., Эрланген, Германия.
• WoNeCa3 — в рамках MMB & DFT 2016, 6 апреля 2016, Мюнстер, Германия.
• WoNeCa2 — в рамках MMB & DFT 2014, 19 марта 2014, Бамберг, Германия.
• WoNeCa1 — Университет Кайзерслаутерна, в рамках MMB2012, 21 марта 2012, Кайзерслаутерн, Германия.

В 2018 г. Международный мастер-класс по сетевому исчислению и приложениям (NetCal 2018) проходил в Вене, Австрия, как часть 30-го Международного телетрафик-конгресса (ITC 30).

В 2024 году семинар Dagstuhl по сетевому исчислению (24141) проходил с 1 по 4 апреля в Дагстуле, Германия.