Введение

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

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

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

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

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

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

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

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

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

Строгий минимальный сервис

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

Расчет минимум плюс

Существует несколько инструментов и библиотек, посвященных алгебре минимума и сложения. Интерпретатор сетевого исчисления — это онлайн-интерпретатор (min,+). Nancy — это библиотека на C#, реализующая операции min plus и max plus. MIN plus ExpRession VErification (Minerve) — это библиотека Coq, используемая для проверки корректности операций min plus. Все эти инструменты и библиотеки основаны на алгоритмах, представленных в.

События

WoNeCa – это семинар по сетевому исчислению. Он проводится каждые два года, чтобы объединить исследователей, интересующихся теорией сетевого исчисления, а также тех, кто хочет применить существующие результаты к новым областям применения. Семинар также способствует популяризации теории сетевого исчисления среди исследователей, заинтересованных в прикладных моделях очередей. WoNeCa6, организованный EPFL, запланирован на 8 и 9 сентября 2022 года в Лозанне, Швейцария. Прием заявок на выступления – здесь. WoNeCa5 был проведен в виртуальном формате из-за пандемии COVID-19 9 октября 2020 года. WoNeCa4 был организован совместно с 19-й Международной конференцией GI/ITG по измерению, моделированию и оценке вычислительных систем (MMB2018) 28 февраля 2018 года в Эрлангене, Германия. WoNeCa3 был проведен в рамках конференции MMB & DFT 2016 6 апреля 2016 года в Мюнстере, Германия. WoNeCa2 состоялся в рамках конференции MMB & DFT 2014 19 марта 2014 года в Бамберге, Германия. WoNeCa1 был организован Университетом Кайзерслаутерна и проведен в рамках MMB2012 21 марта 2012 года в Кайзерслаутерне, Германия. В 2018 году в Вене, Австрия, в рамках 30-го Международного конгресса по телетранспорту (ITC 30) состоялся Международный семинар по сетевому исчислению и приложениям (NetCal 2018). В 2024 году семинар по сетевому исчислению в Дагстуле (24141) был проведен с 1 по 4 апреля в Дагстуле, Германия.