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

Сетевое исчисление (англ. Network Calculus) — совокупность математических результатов, которые позволяют исследовать граничные значения характеристик функционирования таких сложных технических систем, как сети связи, цифровые электрические цепи, конкурирующие программы. Сетевое исчисление даёт теоретическую основу для анализа гарантированной производительности телекоммуникационных пакетных сетей. Потоки трафика, проходящие через сеть, имеют различные ограничения, обусловленные такими свойствами и механизмами, используемыми в сети, как пропускная способность канала связи, формирователи трафика (например, «дырявое ведро»), управление трафиком и доступом, фоновый трафик. Эти ограничения могут быть выражены и проанализированы с использованием методов теории сетевого исчисления. Сетевое исчисление основано на использовании функций (кривых) входящего и исходящего трафика, а также функций обслуживания в сетевых узлах. Эти функции могут быть получены с использованием свёртки в min-плюс алгебре. Сетевое исчисление использует альтернативную идемпотентную алгебру, позволяющую преобразовать сложные нелинейные сетевые системы в линейные, легко поддающиеся аналитическому исследованию.

Основоположником теории NC является профессор Калифорнийского университета Р. Л. Круз (1959—2013), который опубликовал в 1991 году две части своей знаменитой статьи

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

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

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

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

Кривые (функции) поступления и убытия как вход и выход обслуживающей системы

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

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

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

Моделирование загрузки и задержки

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

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

$b(A,D,t):=A(t)-D(t)$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$b(f,g)=(f\oslash g)(0)$

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

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

На этапе проектирования реальное поведение кумулятивных кривых поступления и обслуживания не известно. Обычно известно только некоторое ограничение. Сетевое исчисление использует понятие огибающей трафика, также известной как кривая поступления. Говорят, что кумулятивная кривая A соответствует огибающей (или кривой поступления) E, если для всех t выполняется неравенство

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

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

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

$A\leq A\otimes E$

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

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

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

Минимальная кривая обслуживания

Пусть A является потоком, поступающим на вход обслуживающей системы (сервера), и D — исходящим потоком из сервера. Система реализует простую минимальную кривую обслуживания S для пары (A,B), если для любого момента времени t выполняется неравенство $D(t)\geq (A\otimes S)(t).$

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

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

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

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

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

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

Пусть A — поток, поступающий на вход сервера, D — поток на выходе сервера. Если поток поступающего трафика имеет огибающую E и сервер реализует минимальную кривую обслуживания S, тогда загрузка сервера (объём данных в нём) и задержка будут ограничены:

$b(A,D)\leq b(E,S)$

$d(A,D)\leq d(E,S)$

Более того, кривая выходного потока имеет огибающую $E'=E\oslash S$.

Кроме того, эти границы строгие, то есть при заданных огибающей E и кривой S можно подобрать такие входящий и выходящий потоки, что b(A,D) = b(E,S) and v(A,D)=v(E,S).

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

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

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

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

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

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

Этот результат известен в литературе как плата за пачечность только один раз (PBOO, Pay Burst Only Once).

Программные пакеты

Известны несколько программных пакетов, основанных на сетевом исчислении:

• DiscoDNC — исследовательский пакет, реализован на Java.
• RTC Toolbox — исследовательский пакет на Java/MATLAB, использующий Real-Time модификацию теории сетевого исчисления.
• CyNC — исследовательский пакет на MATLAB/Symulink toolbox. Проект, возможно, заморожен (последнее обновление на этом сайте от июля 2005).
• RTaW-PEGASE — промышленный пакет для анализа коммутируемой сети Ethernet (AFDX, индустриальный Ethernet), основанный на сетевом исчислении.
• Network calculus interpreter — онлайн (min,+) интерпретатор .
• WOPANets — исследовательский пакет, сочетающий сетевое исчисление и оптимальный анализ.
• DelayLyzer — индустриальный пакет, предназначенный для оценки Profinet сетей.

Литература

Книги, обзоры и руководства по сетевому исчислению

• C.-S. Chang: Performance Guarantees in Communications Networks, Springer, 2000.
• J.-Y. Le Boudec and P. Thiran: Network Calculus: A Theory of Deterministic Queuing Systems for the Internet, Springer, LNCS, 2001.
• Y. Jiang and Y. Liu: Stochastic Network Calculus, Springer, 2008.
• A. Kumar, D. Manjunath, and J. Kuri: Communication Networking: An Analytical Approach, Elsevier, 2004.
• S. Mao and S. Panwar: A survey of envelope processes and their applications in quality of service provisioning, IEEE Communications Surveys and Tutorials, 8(3):2-20, July 2006.
• M. Fidler: Survey of deterministic and stochastic service curve models in the network calculus, IEEE Communications Surveys and Tutorials, 12(1):59-86, January 2010.
• M. Fidler and A. Rizk: A guide to the stochastic network calculus, IEEE Communications Surveys and Tutorials, 17(1):92-105, March 2015.
• L. Maile, K. Hielscher and R. German: Network Calculus Results for TSN: An Introduction, IEEE Information Communication Technologies Conference(1): 131—140, May 2020.

Книги, связанные с max-plus алгеброй или с выпуклой минимизацией

• R. T. Rockafellar: Convex analysis, Princeton University Press, 1972.
• F. Baccelli, G. Cohen, G. J. Olsder, and J.-P. Quadrat: Synchronization and Linearity: An Algebra for Discrete Event Systems, Wiley, 1992.
• V. N. Kolokol’tsov, Victor P. Maslov: Idempotent Analysis and Its Applications, Springer, 1997. ISBN 0-7923-4509-6.

Детерминированное сетевое исчисление

• A. K. Parekh and R. G. Gallager: A Generalized Processor Sharing Approach to Flow Control : The Multiple Node Case, IEEE Transactions on Networking, 2 (2):137-150, April 1994.
• C.-S. Chang: Stability, Queue Length and Delay of Deterministic and Stochastic Queueing Networks, IEEE Transactions on Automatic Control, 39(5):913-931, May 1994.
• D. E. Wrege, E. W. Knightly, H. Zhang, and J. Liebeherr: Deterministic delay bounds for VBR video in packet-switching networks: Fundamental limits and practical tradeoffs, IEEE/ACM Transactions on Networking, 4(3):352-362, Jun. 1996.
• R. L. Cruz: SCED+: Efficient Management of Quality of Service Guarantees, IEEE INFOCOM, pp. 625—634, Mar. 1998.
• J.-Y. Le Boudec: Application of Network Calculus to Guaranteed Service Networks, IEEE Transactions on Information Theory, 44(3):1087-1096, May 1998.
• C.-S. Chang: On Deterministic Traffic Regulation and Service Guarantees: A Systematic Approach by Filtering, IEEE Transactions on Information Theory, 44(3):1097-1110, May 1998.
• R. Agrawal, R. L. Cruz, C. Okino, and R. Rajan: Performance Bounds for Flow Control Protocols, IEEE/ACM Transactions on Networking, 7(3):310-323, Jun. 1999.
• J.-Y. Le Boudec: Some properties of variable length packet shapers, IEEE/ACM Transactions on Networking, 10(3):329-337, Jun. 2002.
• C.-S. Chang, R. L. Cruz, J.-Y. Le Boudec, and P. Thiran: A Min, + System Theory for Constrained Traffic Regulation and Dynamic Service Guarantees, IEEE/ACM Transactions on Networking, 10(6):805-817, Dec. 2002.
• M. Fidler and S. Recker: Conjugate network calculus: A dual approach applying the Legendre transform, Computer Networks, 50(8):1026-1039, Jun. 2006.
• Eitan Altman, Kostya Avrachenkov, and Chadi Barakat: TCP network calculus: The case of large bandwidth-delay product, In proceedings of IEEE INFOCOM, NY, June 2002.

Сетевые топологии

• A. Charny and J.-Y. Le Boudec: Delay Bounds in a Network with Aggregate Scheduling, QoFIS, pp. 1-13, Sep. 2000.
• D. Starobinski, M. Karpovsky, and L. Zakrevski: Application of Network Calculus to General Topologies using Turn-Prohibition, IEEE/ACM Transactions on Networking, 11(3):411-421, Jun. 2003.
• M. Fidler: A parameter based admission control for differentiated services networks, Computer Networks, 44(4):463-479, March 2004.
• L. Lenzini, L. Martorini, E. Mingozzi, and G. Stea: Tight end-to-end per-flow delay bounds in FIFO multiplexing sink-tree networks, Performance Evaluation, 63(9-10):956-987, October 2006.
• J. Schmitt, F. Zdarsky, and M. Fidler: Delay bounds under arbitrary multiplexing: when network calculus leaves you in the lurch …, Prof. IEEE Infocom, April 2008.
• A. Bouillard, L. Jouhet, and E. Thierry: Tight performance bounds in the worst-case analysis of feed-forward networks, Proc. IEEE Infocom, April 2010.

Основанные на измерении системы идентификации

• C. Cetinkaya, V. Kanodia, and E.W. Knightly: Scalable services via egress admission control, IEEE Transactions on Multimedia, 3(1):69-81, March 2001.
• S. Valaee, and B. Li: Distributed call admission control for ad hoc networks, Proc. of IEEE VTC, pp. 1244—1248, 2002.
• J. Liebeherr, M. Fidler, and S. Valaee: A system-theoretic approach to bandwidth estimation, IEEE Transactions on Networking, 18(4):1040-1053, August 2010.
• M. Bredel, Z. Bozakov, and Y. Jiang: Analyzing router performance using network calculus with external measurements, Proc. IEEE IWQoS, June 2010.
• R. Lubben, M. Fidler, and J. Liebeherr: Stochastic bandwidth estimation in networks with random service, IEEE Transactions on Networking, 22(2):484-497, April 2014.

Стохатическое сетевое исчисление

• O. Yaron and M. Sidi: Performance and Stability of Communication Networks via Robust Exponential Bounds, IEEE/ACM Transactions on Networking, 1(3):372-385, Jun. 1993.
• D. Starobinski and M. Sidi: Stochastically Bounded Burstiness for Communication Networks, IEEE Transactions on Information Theory, 46(1):206-212, Jan. 2000.
• C.-S. Chang: Stability, Queue Length and Delay of Deterministic and Stochastic Queueing Networks, IEEE Transactions on Automatic Control, 39(5):913-931, May 1994.
• R.-R. Boorstyn, A. Burchard, J. Liebeherr, and C. Oottamakorn: Statistical Service Assurances for Traffic Scheduling Algorithms, IEEE Journal on Selected Areas in Communications, 18(12):2651-2664, Dec. 2000.
• Q. Yin, Y. Jiang, S. Jiang, and P. Y. Kong: Analysis of Generalized Stochastically Bounded Bursty Traffic for Communication Networks, IEEE LCN, pp. 141—149, Nov. 2002.
• C. Li, A. Burchard, and J. Liebeherr: A Network Calculus with Effective Bandwidth, University of Virginia, Technical Report CS-2003-20, Nov. 2003.
• A. Burchard, J. Liebeherr, and S. D. Patek: A Min-Plus Calculus for End-to-end Statistical Service Guarantees, IEEE Transactions on Information Theory, 52(9):4105-4114, Sep. 2006.
• F. Ciucu, A. Burchard, and J. Liebeherr: A Network Service Curve Approach for the Stochastic Analysis of Networks, IEEE/ACM Transactions on Networking, 52(6):2300-2312, Jun. 2006.
• M. Fidler: An End-to-End Probabilistic Network Calculus with Moment Generating Functions, IEEE IWQoS, Jun. 2006.

Беспроводное сетевое исчисление

• M. Fidler: A Network Calculus Approach to Probabilistic Quality of Service Analysis of Fading Channels, Proc. IEEE Globecom, November 2006.
• K. Mahmood and A. Rizk: On the Flow-Level Delay of a Spatial Multiplexing MIMO Wireless Channel, Proc. IEEE ICC, June 2011.
• H. Al-Zubaidy, J. Liebeherr, and A. Burchard: A (min, ×) network calculus for multi-hop fading channels, Proc. IEEE Infocom, pp. 1833—1841, April 2013.
• M. Fidler, R. Lubben, and N. Becker: Capacity-Delay-Error Boundaries: A Composable Model of Sources and Systems, Transactions on Wireless Communications, 14(3):1280-1294, March 2015.