Сетевое исчисление - Network calculus

Сетевое исчисление представляет собой "набор математических результатов, которые дают представление о созданных человеком системах, таких как параллельные программы, цифровые схемы и сети связи."^[1] Сетевой расчет дает теоретическую основу для анализа гарантий производительности в компьютерная сеть. Поскольку трафик проходит через сеть, он подлежит ограничения налагается компонентами системы, например:

• ссылка на сайт емкость
• формирователи трафика (дырявые ведра )
• контроль перегрузки
• фоновый трафик

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

В исчислении используются «альтернативные алгебры ... для преобразования сложных нелинейных сетевых систем в аналитически поддающиеся обработке линейные системы».^[2]

В настоящее время в сетевом исчислении существует две ветви: одна обрабатывает детерминированные ограничения, а другая - стохастические границы.^[3]

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

Поток моделирования и сервер

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

Кривая прибытия и отправления на входе и выходе сервера.

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

${ displaystyle forall u, t in mathbb {R} ^ {+}: u$

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

Моделирование отставания и задержки

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

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

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

${ Displaystyle d (A, D, t): = inf left {d in mathbb {R} ^ {+} ~ st ~ 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} ^ {+} ~ st ~ D (t + d ) geq A (t) right } right }}$

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

Мин-плюс алгебра

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

${ Displaystyle (е аст г) (т): = int _ {0} ^ {т} е ( тау) cdot г (т- тау) д тау}$

В мин-плюс алгебра то сумма заменяется на минимум соответственно инфимум оператор и товар заменяется сумма. Итак, свертка мин-плюс двух функций ${ displaystyle f}$ и ${ displaystyle g}$ становится

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

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

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

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

например как используется в определении конвертов трафика.

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

${ Displaystyle б (е, г) = (е oslash г) (0)}$

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

Конверты трафика

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

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

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

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

${ Displaystyle forall тау, т ин mathbb {R} ^ {+}: А ( тау + т) -А ( тау) Leq E (т)}$

(1)

${ displaystyle A leq A otimes E}$

(2)

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

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

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

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

Позволять А быть потоком прибытия, поступающим на вход сервера, и D быть потоком, уходящим на выходе. Считается, что система обеспечивает простая минимальная кривая обслуживания S к паре (А, Б), если для всех т он считает, что${ Displaystyle D (t) geq (A otimes S) (t).}$

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

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

Считается, что система обеспечивает строгая минимальная кривая обслуживания S к паре (А, Б) если только ${ Displaystyle forall s, т in mathbb {R} ^ {+}}$, так что ${ displaystyle s leq t}$, если ${ displaystyle (s, t]}$ период отставания, тогда ${ Displaystyle D (т) -D (s) geq S (т-с)}$.

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

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

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

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

${ Displaystyle б (А, D) leq б (Е, S)}$

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

Кроме того, кривая вылета имеет огибающую ${ displaystyle E '= E oslash S}$.

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

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

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

Затем, если первый (соответственно второй) сервер предлагает простой минимальный сервис ${ 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 (Икс время S_ {2}) время 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})}$.

Этот результат известен как Оплата только один раз (PBOO).

инструменты

Есть несколько инструментов, основанных на сетевом исчислении.

• В DiscoDNC является академической Java-реализацией инфраструктуры сетевого исчисления.^[6]
• В Панель инструментов RTC академическая Java /MATLAB реализация структуры исчисления в реальном времени, теории, квазиэквивалентной сетевому исчислению.^[4]
• В CyNC^[7] инструмент академический MATLAB / Набор инструментов Symulink, основанный на Панель инструментов RTC. Инструмент был разработан в 2004-2008 гг. И в настоящее время используется для обучения в Ольборгский университет.
• В RTaW-PEGASE это промышленный инструмент, предназначенный для временного анализа коммутируемых сетей Ethernet (AFDX, промышленный и автомобильный Ethernet) на основе сетевых вычислений.^[8]
• В Интерпретатор сетевых вычислений он-лайн (мин, +) переводчик.
• В WOPANets это академический инструмент, сочетающий анализ на основе сетевых вычислений и анализ оптимизации.^[9]
• DelayLyzer - это промышленный инструмент, предназначенный для вычисления границ сетей Profinet.^[10]
• ДЕБОРА это академический инструмент, посвященный сетям FIFO.^[11]
• NetCalBounds это академический инструмент, посвященный тандемным сетям слепых и FIFO.^[12][13]
• NCBounds это инструмент сетевого расчета на Python, опубликованный под лицензией BSD 3-Clause License. Он учитывает серверы скорость-задержка и кривые поступления токенов. Работает с любой топологией, в том числе и с циклической.^[14].
• Планировщик сети Сименс (SINETPLAN ) использует сетевое исчисление (среди других методов), чтобы помочь в разработке PROFINET сеть.^[15]

Рекомендации

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

• С.-С. Чанг: Гарантии производительности в сетях связи, Спрингер, 2000.
• Ж.-Й. Ле Будек и П. Тиран: Сетевое исчисление: теория детерминированных систем массового обслуживания в Интернете, Спрингер, LNCS, 2001.
• А. Буйяр, М. Бойер, Э. Ле Коррон: Детерминированное сетевое исчисление: от теории к практической реализации, Wiley-ISTE, 2018 г.
• Ю. Цзян и Ю. Лю: Стохастическое сетевое исчисление, Springer, 2008.
• А. Кумар, Д. Манджунатх и Дж. Кури: Коммуникационные сети: аналитический подход, Эльзевир, 2004.
• С. Мао и С. Панвар: Обзор процессов конверта и их применения в качестве предоставления услуг, IEEE Communications Surveys and Tutorials, 8 (3): 2-20, July 2006.
• М. Фидлер: Обзор детерминированных и стохастических моделей кривой обслуживания в сетевом исчислении, IEEE Communications Surveys and Tutorials, 12 (1): 59-86, January 2010.
• Ч. Линь, Ю. Дэн и Ю. Цзян: О применении стохастического сетевого исчисления, Frontiers Computer Science, 7 (6): 924-942, 2013 г.
• М. Фидлер и А. Ризк: Руководство по стохастическому сетевому исчислению, IEEE Communications Surveys and Tutorials, 17 (1): 92-105, March 2015.

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

• Р. Т. Рокафеллар: Выпуклый анализ, Princeton University Press, 1972.
• Ф. Баччелли, Дж. Коэн, Дж. Дж. Олсдер и Ж.-П. Квадрат: Синхронизация и линейность: алгебра дискретных событийных систем, Wiley, 1992.
• Колокольцов В.Н., Маслов Виктор Петрович: Идемпотентный анализ и его приложения, Springer, 1997. ISBN  0792345096.

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

• Р. Л. Круз: Расчет сетевой задержки. Часть I. Сетевые элементы в изоляции и Часть II: Сетевой анализ, IEEE Transactions on Information Theory, 37 (1): 114-141, январь 1991 г.
• А. К. Парех и Р. Г. Галлагер: Обобщенный подход к управлению потоком с совместным использованием процессора: случай с несколькими узлами, IEEE Transactions on Networking, 2 (2): 137-150, апрель 1994.
• С.-С. Чанг: Устойчивость, длина очереди и задержка детерминированных и стохастических сетей массового обслуживания, IEEE Transactions on Automatic Control, 39 (5): 913-931, May 1994.
• Д. Э. Врег, Э. В. Найтли, Х. Чжан и Дж. Либехерр: Детерминированные границы задержки для видео VBR в сетях с коммутацией пакетов: фундаментальные ограничения и практические компромиссы, IEEE / ACM Transactions on Networking, 4 (3): 352-362, июнь 1996.
• Р. Л. Круз: SCED +: эффективное управление гарантиями качества обслуживания, IEEE INFOCOM, стр. 625–634, март 1998 г.
• Ж.-Й. Ле Будек: Применение сетевого исчисления к сетям с гарантированным обслуживанием, IEEE Transactions on Information Theory, 44 (3): 1087-1096, May 1998.
• С.-С. Чанг: О детерминированном регулировании движения и гарантиях услуг: систематический подход путем фильтрации, IEEE Transactions on Information Theory, 44 (3): 1097-1110, May 1998.
• Р. Агравал, Р. Л. Круз, К. Окино и Р. Раджан: Границы производительности для протоколов управления потоком, IEEE / ACM Transactions on Networking, 7 (3): 310-323, июнь 1999.
• Ж.-Й. Ле Будек: Некоторые свойства формирователей пакетов переменной длины, IEEE / ACM Transactions on Networking, 10 (3): 329-337, июнь 2002 г.
• С.-С. Чанг, Р. Л. Круз, Ж.-Й. Ле Будек и П. Тиран: Системная теория Min, + для ограниченного регулирования трафика и динамических гарантий обслуживания, IEEE / ACM Transactions on Networking, 10 (6): 805-817, декабрь 2002 г.
• Ю. Цзян: Связь между сервером гарантированной скорости и сервером скорости задержки, Компьютерные сети 43 (3): 307-315, 2003.
• М. Фидлер и С. Рекер: Сопряженное сетевое исчисление: двойной подход с применением преобразования Лежандра, Computer Networks, 50 (8): 1026-1039, июнь 2006 г.
• Эйтан Альтман, Костя Авраченков и Чади Баракат: Расчет сети TCP: случай большого произведения пропускной способности и задержки, В трудах IEEE INFOCOM, Нью-Йорк, июнь 2002 г.
• Я. Либехерр: Двойственность сетевого исчисления Max-Plus и Min-Plus, Основы и тенденции в сети 11 (3-4): 139-282, 2017.

Сетевые топологии, сети прямого распространения

• А. Чарни, Ж.-Й. Ле Будек: Границы задержки в сети с агрегированным расписанием, QoFIS, стр. 1–13, сентябрь 2000 г.
• Д. Старобинский, М. Карповский, Л. Закревский: Применение сетевого исчисления к общим топологиям с использованием запрета поворота, IEEE / ACM Transactions on Networking, 11 (3): 411-421, июнь 2003 г.
• М. Фидлер: Управление доступом на основе параметров для сетей с дифференцированными услугами, Computer Networks, 44 (4): 463-479, март 2004 г.
• Л. Лензини, Л. Марторини, Э. Мингоцци и Г. Стеа: Жесткие границы сквозной задержки для каждого потока в сетях FIFO с мультиплексированием на основе дерева приемников, Оценка эффективности, 63 (9-10): 956-987, октябрь 2006 г.
• Дж. Шмитт, Ф. Здарский и М. Фидлер: Границы задержки при произвольном мультиплексировании: когда сетевое исчисление оставляет вас в беде ..., Проф. IEEE Infocom, апрель 2008 г.
• А. Буйяр, Л. Жуэ, Э. Тьерри: Жесткие границы производительности при анализе сетей с прямой связью в худшем случае, Proc. IEEE Infocom, апрель 2010 г.

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

• К. Четинкая, В. Канодиа и Э. В. Найтли: Масштабируемые услуги за счет контроля допуска на выходе, IEEE Transactions on Multimedia, 3 (1): 69-81, март 2001 г.
• С. Валаи и Б. Ли: Распределенный контроль допуска звонков для одноранговых сетей, Proc. of IEEE VTC, pp. 1244–1248, 2002.
• А. Ундхейм, Ю. Цзян, П. Дж. Эмстад. Подход сетевого расчета к моделированию маршрутизатора с помощью внешних измерений, Proc. Второй международной конференции IEEE по коммуникациям и сетям в Китае (Chinacom), август 2007 г.
• Дж. Либехерр, М. Фидлер и С. Валаи: Теоретико-системный подход к оценке пропускной способности, IEEE Transactions on Networking, 18 (4): 1040-1053, август 2010 г.
• М. Бредель, З. Бозаков и Ю. Цзян: Анализ производительности маршрутизатора с использованием сетевых вычислений с внешними измерениями, Proc. IEEE IWQoS, июнь 2010 г.
• Р. Люббен, М. Фидлер и Дж. Либехерр: Стохастическая оценка пропускной способности в сетях со случайным обслуживанием, IEEE Transactions on Networking, 22 (2): 484-497, апрель 2014 г.

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

• О. Ярон и М. Сиди: Производительность и стабильность сетей связи с помощью надежных экспоненциальных границ, IEEE / ACM Transactions on Networking, 1 (3): 372-385, июнь 1993.
• Д. Старобинский и М. Сиди: Стохастически ограниченная пиковая скорость для сетей связи, IEEE Transactions по теории информации, 46 (1): 206-212, январь 2000 г.
• С.-С. Чанг: Устойчивость, длина очереди и задержка детерминированных и стохастических сетей массового обслуживания, IEEE Transactions on Automatic Control, 39 (5): 913-931, May 1994.
• Р.-Р. Бурстин, А. Бурчард, Дж. Либехерр и К. Оттамакорн: Статистические гарантии обслуживания для алгоритмов планирования трафика, Журнал IEEE по избранным областям коммуникаций, 18 (12): 2651-2664, декабрь 2000 г.
• К. Инь, Ю. Цзян, С. Цзян, П. Ю. Конг: Анализ обобщенного стохастически ограниченного пакетного трафика для сетей связи, IEEE LCN, стр. 141–149, ноябрь 2002 г.
• К. Ли, А. Бурчард и Дж. Либехерр: Сетевое вычисление с эффективной пропускной способностью, Университет Вирджинии, Технический отчет CS-2003-20, ноябрь 2003 г.
• Ю. Цзян: Базовое стохастическое сетевое исчисление, ACM SIGCOMM 2006.
• А. Бурчард, Дж. Либехерр и С. Д. Патек: Расчет Min-Plus для сквозных гарантий статистических услуг, IEEE Transactions on Information Theory, 52 (9): 4105–4114, сентябрь 2006 г.
• Ф. Чуку, А. Бурчард и Дж. Либехерр: Подход кривой сетевого обслуживания для стохастического анализа сетей, IEEE / ACM Transactions on Networking, 52 (6): 2300–2312, июнь 2006 г.
• М. Фидлер: Сквозное вероятностное сетевое исчисление с функциями создания моментов, IEEE IWQoS, июнь 2006 г.
• Ю. Лю, Ч.-К. Там и Ю. Цзян: Расчет для стохастического анализа QoS, Оценка эффективности, 64 (6): 547-572, 2007.
• Ю. Цзян и Ю. Лю: Стохастическое сетевое исчисление, Springer, 2008.

Расчет беспроводной сети

• М. Фидлер: Сетевой расчетный подход к вероятностному анализу качества обслуживания каналов с замиранием, Proc. IEEE Globecom, ноябрь 2006 г.
• К. Махмуд, А. Ризк и Ю. Цзян: О задержке на уровне потока в беспроводном канале MIMO с пространственным мультиплексированием, Proc. IEEE ICC, июнь 2011 г.
• К. Махмуд, М. Вехкаперя и Ю. Цзян: Анализ пропускной способности с ограничением задержки для коррелированного беспроводного канала MIMO, Proc. IEEE ICCCN, 2011.
• К. Махмуд, М. Вехкаперя и Ю. Цзян: Анализ пропускной способности CDMA с ограничением задержки с использованием стохастического сетевого расчета, Proc. IEEE ICON, 2011 г.
• К. Махмуд, М. Вехкаперя и Ю. Цзян: Производительность многопользовательских CDMA-приемников с ограничениями импульсного трафика и задержки, Proc. ICNC, 2012.
• Ю. Чжан и Ю. Цзян: Качество передачи данных по гауссовскому каналу с дисперсией, Proc. ISWCS, 2012.
• Х. Аль-Зубайди, Дж. Либехерр и А. Бурчард: Расчет сети A (min, ×) для многоскачковых каналов с замираниями, Proc. IEEE Infocom, стр. 1833–1841, апрель 2013 г.
• К. Чжэн, Ф. Лю, Л. Лэй, К. Линь и Ю. Цзян: Стохастический анализ характеристик беспроводного конечного марковского канала, IEEE Trans. Беспроводная связь 12 (2): 782-793, 2013.
• J.-w. Чо и Ю. Цзян: Основы процесса отсрочки передачи в 802.11: дихотомия агрегации, IEEE Trans. Теория информации 61 (4): 1687-1701, 2015.
• М. Фидлер, Р. Люббен и Н. Беккер: Границы емкости – задержки – ошибки: составная модель источников и систем, Транзакции о беспроводной связи, 14 (3): 1280-1294, март 2015 г.
• Ф. Сунь и Ю. Цзян: Статистическая характеристика пропускной способности беспроводного канала: теория и применение, Proc. Работа ИФИП, 2017.