Теория сетевого анализа

• Ширина канала 
• Формирователь трафика («дырявое ведро» - leaky buckets) 
•  Управление перегрузкой 
•  Фоновый трафик 

Эти ограничения могут быть выражены и проанализированы при помощи методов теории сетевого анализа. Ограничивающие кривые могут быть скомбинированы (сложены) , используя свертку «min-plus» алгебры. Теория сетевого анализа также может быть использована для выражения поступающего и выходящего трафиков функциями, также кривые обслуживания.

Теория сетевого исчисления использует «альтернативную алгебру … для преобразования комплексных нелинейных сетевых систем в легко поддающиеся аналитическому анализу линейные системы» 

Сейчас существуют два направления в теории сетевого анализа: детерминированное и стохатическое.В данной статье только про детерминированное. 

Моделирование системы

Моделирование потока и сервера

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

Поступающие и выходящие кривые н

${\displaystyle }$

${\displaystyle }$

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

Отставание моделирование и задержки

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

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

${\displaystyle }$

${\displaystyle }$

${\displaystyle }$

${\displaystyle }$

В основном, потоки не точно известны, и только некоторые ограничения потоков и серверов известны ( такие как максимальное число пакетов, отправленных некоторый период; максимальный размер пакетов; минимальная полоса пропускания канала). Цель теории сетевого анализа – вычисление границ задержки и отставания, основанные на этих ограничениях. Для этого используется «min-plus» алгебра.

«Min-plus» алгебра

В теории фильтра и теории линейных систем свёртка двух функций f и g обозначается, как

${\displaystyle }$

В «min-plus» алгебре сумма заменяется минимум соответственно оператором  инфинимум оператора и и произведение заменятся суммой. Так «min-plus» свёртка двух функций f и g становится

${\displaystyle }$

Например, увидим определение кривой обслуживания. Свёртка и «min-plus» свёртка схожи по многим алгебраическим свойствам. В частности обе коммуникативны и ассоциативны.

Так называемый оператор обратный свёртке обозначается как

${\displaystyle }$

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

Вертикальное и горизонтальное отклонение может быть выражено в терминах «min-plus» операторах.

${\displaystyle }$

${\displaystyle }$

Огибающая трафика

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

Кумулятивная кривая А, как говорят, соответствует огибающей (или кривой поступления) Е, если для всех t выполняется

${\displaystyle }$

Два эквивалентных определения могут быть даны

${\displaystyle }$

Таким образом, Е является верхней границей потока А. Подобные функции Е могут быть увидены, как основа, которая определяет верхнюю границу числа бит потока в интервале продолжительности t, начиная с произвольного τ, см. выр.  (1).

Кривая обслуживания

Для того, чтобы обеспечить гарантии исполнения транспортных потоков, необходимо указать некоторую минимальную производительность сервера (в зависимости от бронирования в сети или политики планировщика, и т.д.). Кривая обслуживания служит средством выражения доступности ресурсов. Существуют несколько видов кривых обслуживания, например, слабо строгая, узел переменной ёмкости и т.д. Смотреть    для обзора.

Минимальное обслуживание

Пусть А будет прибывающим потоком, поступающий на вход сервера, и D будет выходящим потоком. Система предоставляет простую минимальную кривую обслуживания S в паре (А,В), если для всех t выполняется ${\displaystyle }$

Строго минимальное обслуживание

Пусть А будет прибывающим потоком, поступающий на вход сервера, и D будет выходящим потоком. Период отставания I такой, что на любом t ∈ I, A(t)>D(t).

Система предоставляет строго минимальную кривую обслуживания S в паре (А,В)   ${\displaystyle }$такие , что ${\displaystyle }$если ${\displaystyle }$ период отставания, тогда ${\displaystyle }$.

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

Основные результаты: границы производительности и огибающая распространения

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

Пусть А – поступаемый поток, поступающий на вход сервера, D – поток, выходящий с выхода сервера. Если поток трафика имеет огибающую Е, и сервер предлагает минимальную кривую обслуживания S, тогда отставание и задержка будут ограничены:

${\displaystyle }$

${\displaystyle }$

Более того, кривая выходного потока будет определяться как ${\displaystyle }$.

Кроме того, эти границы строгие то есть учитывая E и S, можно построить поступление и отбытие так, что b(A,D)=b(E,S) и v(A,D)=v(E,S).

Конкатенация/ PBOO

Рассмотрим последовательность двух серверов, где выход первого является входом второго. Эта последовательность может быть рассмотрена как новый сервер, построенный на конкатенции двух других.

Тогда, если первый (соответственно, второй) сервер предлагает простую минимальную кривую обслуживания ${\displaystyle }$ (соответственно ${\displaystyle }$), тогда конкатенция обоих предлагает простую минимальную кривую обслуживания ${\displaystyle }$.

Последовательность из двух серверов

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

Заинтересованность в этих результатах состоит в том, что граница сквозной задержки не больше, чем сумма локальных задержек: ${\displaystyle }$.

Эти результаты известны как Pay burst only once (плати бёрстностью только раз).