Базовые принципы теории сетевого исчисления Network Calculus
Сетевое исчисление NC является системной теорией для анализа сетей связи. Как показано в [1], между традиционной теорией систем для линейных электри- ческий цепей и теорией NC можно провести аналогию. На рисунке 1 (а) представ- лена простая электрическая RC-цепь.
Рисунок 1 – а) Электрическая RC-цепь; б) модель системы обслуживания в теории NC
Если на вход этой цепи подается напряжение x (t)ÎR , где R – множество действительных чисел, то отклик y (t)ÎR на выходе этой цепи можно определить путем свертки входного воздействия x(t) с импульсной характеристикой h(t) этой цепи:
Теперь рассмотрим модель системы обслуживания в теории NC, представ- ленную на рисунке 1 (б). Входной сигнал A(t) здесь является кумулятивным пото- ком бит (пакетов, заявок), поступивших в узел за интервал времени [0,t] . Функция A(t) является непрерывной, возрастающей в широком смысле, и принимает ну- левые значения при t £ 0 . Откликом является кумулятивная функция выхода D(t), т.е. суммарное число бит, обслуженных узлом за интервал времени от [0, )t . Пред- положим, что трафик обрабатывается идеальным жадным формирователем (напри- мер, «дырявое ведро»), который ограничивает входной поток по скорости в соот- ветствии с некоторой функцией b . Функция D(t) может быть определена путем (min, +)-свертки функции входящего потока A(t) c функцией b , характеризующей работу формирователя:
Как видно из данного примера, различие состоит в применяемой математике: в теории электрических цепей используется классическая алгебра, а в теории NC используется (min, +)-алгебра. Теория NC имеет две ветви развития: детерминистическое (Deterministic Network Calculus, DNC) и стохастическое (Stochastic Network Calculus, SNC). DNC бе- рет свое начало в работах Р. Круза [2,3]. Важные результаты теории DNC были обобщены и опубликованы в [3, 4]. Теория DNC позволяет определять детерми- нистические границы, гарантирующие, что реальные параметры QoS в сети опера- тора (такие, как границы задержки, загрузки, потери пакетов, эффективная полоса пропускания) будут не хуже запрашиваемых пользователем параметров или будут в некоторых нормированных пределах. Это можно записать в виде выражения:
|
|
|
Таким образом, теорию DNC целесообразно применять в случае, если требуются строгие оценки граничных характеристик QoS, что также рассматривалось в. Тем не менее, анализ с использованием DNC будет всегда давать только пес- симистичные оценки, что может привести к необходимости излишнего резервирования сетевых ресурсов. Теория SNC развивалась параллельно с DNC, начиная с работ. В работе были обобщены важные положения теории SNC. SNC позволяет определять стохастические границы, гарантирующие, что реальные параметры QoS с не- которой допустимой вероятностью будут не хуже запрашиваемых пользователем параметров. Это можно записать в виде выражения:
|
|
|
где ɛ является допустимой вероятностью превышения границ характеристик QoS. Таким образом, модели теории SNC целесообразно использовать в случае, если не требуются строгие оценки граничных характеристик QoS и допустимы нарушения нормируемых параметров QoS, однако, при этом сетевые ресурсы используются более оптимально, что также рассматривалось в. В диссертационной работе используются модели теории DNC. Рассмотрим ее базовые модели.
Предположим, что сетевой узел является «черным ящиком», т.е. его дисци- плина обслуживания не известна. Пусть на вход этого узла поступает кумулятив- ный поток битов A(t), а на выходе узла кумулятивный поток обслуженных битов D(t). Очевидно, что каждый бит потока D(t) является по сути каждым битом потока A(t), прошедшим через узел и получившим некоторую временную задержку (рису- нок 8). Поэтому задержка любого бита в момент времени t может быть определена как горизонтальное расстояние между кривой входного потока A(t) и кривой вы- ходного потока D(t), что можно представить как:
Задержка потока A(t) за период времени [0, ]t определяется как максимальное горизонтальное расстояние между кривыми потоков A(t) и D(t), что можно пред- ставить как:
|
|
|
Аналогично может быть определена другая важная характеристика качества обслуживания – загрузка узла. Если система обслуживания (узел) состоит из одного обслуживающего устройства, то загрузкой является длина очереди.
Рисунок 2 – Определение задержки передачи бит (пакетов) и загрузки узла
В системе с N обслуживающими устройствами загрузкой будет являться число пакетов в системе при условии, что можно наблюдать входной и выходной потоки одновременно. Загрузка узла в любой момент времени t определяется как вертикальное расстояние между кривыми A(t) и D(t), что можно представить как:
Загрузка узла в период времени [0, ]t определяется как максимальное верти- кальное расстояние между кривыми A(t) и D(t), что можно представить как:
Как правило на практике функции распределения входного и выходного по- токов и функции распределения дисциплин обслуживания узлов неизвестны. Из- вестны только некоторые ограничения входящих потоков трафика и производи- тельности сетевых узлов. С этой целью в теории NC вводятся концепции кривой поступления и кривой обслуживания.
|
|
|
Функция a(t) , возрастающая в широком смысле, является кривой поступления для функции A(t) тогда и только тогда, когда для " 0£ s £ t справедливо неравенство:
Таким образом, кривой поступления моделирует границу максимального объема входящего в узел потока трафика. Кривая поступления α(t) может быть за- дана различными функциями, подробный обзор которых представлен в. Концепция кривой поступления изображена на рисунке 3. Из рисунка 3 видно, что поток A(t) должен быть всегда ниже своей кривой поступления a(t) , в какой бы точке потока она не начиналась.
Рисунок 3 – Концепция кривой поступления
Концепция кривой поступления сходна с принципом работы алгоритмов фор- мирования и ограничения трафика в соответствии с определенной политикой, например «маркерное ведро» и «дырявое ведро».
Функция β(t), возрастающая в широком смысле, является кривой обслуживания сетевого узла, тогда и только тогда, когда для 0 " ³t вы- полняется неравенство:
где выражение в правой части неравенства обозначает (min, +)-свертку функций (A Äb)(t) .
Таким образом, кривая обслуживания моделирует минимальный ресурс производительности, который может предоставить узел для обслуживания вхо- дящего потока трафика. Концепция кривой обслуживания показана на рисунке 4. Кривая обслуживания при условии в NC называется классической кривой обслуживания. Классическая кривая обслуживания предполагает, что поток на выходе узла может быть ниже его кривой обслуживания, но всегда будет больше либо равен нижней границе (min, +)-свертки функции входного потока с данной кривой обслуживания.
Рисунок 4 – Концепция кривой обслуживания
Кривая обслуживания позволяет моделировать дисциплину обслуживания сетевого узла, например, FIFO, PQ (приоритетное обслуживание) и т.п. Обзор функций, которыми может быть задана кривая обслуживания, приведен в. Используя кривую поступления и кривую обслуживания можно получить границы характеристик QoS, таких как задержка передачи пакетов через систему обслуживания и загрузка узла. Граница задержки определяется как горизонтальное расстояние h (a b) между кривой поступления и кривой обслуживания.
Пусть поток с кривой поступления α(t) поступает в си- стему с кривой обслуживания β(t). Тогда граница задержки определяется как:
Граница загрузки определяется как вертикальное расстояние между кривыми поступления и обслуживания
Граница загрузки. Пусть поток с кривой поступления α(t) по- ступает в систему с кривой обслуживания β(t). Тогда граница загрузки определя- ется как:
Поток обслуженных пакетов на выходе системы, описываемый функцией вы- хода D(t) благодаря свойству характеристики выхода может быть представлен мо- делью входного потока.
Пусть поток с кривой поступления α(t) поступает в си- стему с кривой обслуживания β(t). Тогда функция выходящего потока A * (t) огра- ничена кривой поступления * a a b ( ) ( ) t t = для " ³ s t, 0 и удовлетворяет неравен- ству:
NC позволяет определить ресурсы, которые узел может предоставить отдель- ному потоку с учетом ресурсов, используемых кросс-потоками
Рисунок 5 – Модель узла с кросс-потоком
Теорема 1.Пусть узел без потерь обслуживает потоки 1 и 2 в порядке FIFO. Предположим, что пакеты поступают мгновенно и узел гарантирует минималь- ную кривую обслуживания β(t) для агрегата двух потоков. Пусть поток 2 имеет кривую поступления α2(t). Определим семейство кривых обслуживания для потока 1:
Если для любого t ³ 0 функция 1 ( , ) eq b tt является в широком смысле возрастающей, то поток 1 имеет гарантированную эквивалентную кривую обслуживания 1 ( , ) eq b t
Таким образом, Теорема 1 для потока 1 определяет множество остаточных кривых обслуживания, в котором каждая кривая может быть получена путем зада- ния конкретного значения параметра t , характеризующего начальный отсчет вре- мени 0 t t Î[0, ] кривой поступления 2 a ( )t .
Благодаря свойству сцепления последовательность из N узлов можно анали- зировать как один узел, зная кривые обслуживания каждого узла.
Пусть поток трафика проходит через последователь- ность, состоящую из N. Предположим, что каждый узел имеет кривую обслужи- вания βn(t), где n i N =1,..., ..., , возрастающую в широком смысле. Тогда общая кри- вая обслуживания βS(t) будет определяться как:
На рисунке 6 проиллюстрирована концепция свойства сцепления последо- вательности N узлов
Рисунок 6 – Преобразование последовательности узлов в один узел
Таким образом, кривая поступления первого узла α1(t) и кривая выходящего потока N-го узла αN(t) будут являться кривой поступления и кривой выходящего потока для всей последовательности N узлов. Это позволяет определить границы характеристик сквозного QoS. Например, границы сквозной задержки DN(t) и сквозной загрузки BN(t) можно определить, как:
Заключение
После изучения основ теории сетевого исчисления Network Calculus можно сделать вывод,что:
Теория NC обеспечивает глубокое понимание проблем, возникающих в сети при обслуживании потоков трафика. Использование NC позволяет понять некоторые фундаментальные свойства работы механизмов обслуживания мультисервис- ного трафика, таких, как архитектура управления ресурсами IntServ (интегрированное обслуживание), оконное управление потоком (window flow control), планиров- щики пакетов, формирователи трафика. Модульность и масштабируемость NC делает ее ценным инструментом анализа сложных систем и сетей.
Список литературы
1. Росляков, А. В. Виртуальные частные сети. Основы построения и применения: научное издание / А. В. Росляков. – М.: Эко-Трендз, 2006. – 304 с.
2. Росляков, А. В. Разработка моделей и методов анализа виртуальных частных сетей с учетом особенностей их практической реализации: дисс. …д-ра тех. наук: 05.12.13 / Росляков Александр Владимирович. – Самара, 2008. – 353 с.
3. Росляков, А. В. Оценка потребностей корпоративных пользователей в услугах виртуальных частных сетей / А.В. Росляков // Тез. докл. на VIII Международной НТК «Проблемы техники и технологии телекоммуникаций», Уфа, 2007. – С. 126-128.
4. Лысиков, А. А. Теория сетевого исчисления и ее применение к VPN / А. А. Лысиков, А. В. Росляков // Тез. докл. на XVII Международной НТК "Проблемы техники и технологий телекоммуникаций", Самара, 2016 г. – С. 37-41.
5. Лысиков, А. А. Достоинства и недостатки теории Network Calculus при моделировании сетей VPN / А. А. Лысиков // Тез. докл. на XXII Российской НТК ПГУТИ, Самара, 2015. – С. 37-38.
Дата добавления: 2018-02-28; просмотров: 603; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!