Network Calculus. Part 2. Practical Use

Full Text

Для исследования систем массового обслуживания (СМО) аналитическими методами тра-диционно использовалась теория массового об-служивания (ТМО) [1]. В последние годы наряду с имитационным моделированием [2] все бол-шую популярность приобретает перспективное направление анализа СМО - теория сетевого исчисления NC (Network Calculus) [3; 4]. Каче-NC (Network Calculus) [3; 4]. Качественное сравнение величин задержек трафика в СМО, полученных с использованием методов ТМО, теории NC и имитационного моделирования, с задержками в реальной системе показано на рисунке 1. Очевидно, что в общем случае в реальной системе задержка трафика может быть в принципе любой в пределах от наименьшего до наибольшего значения. При использовании имитационного моделирования получаются частные значения величин задержек в этих же пределах в зависимости от исходных данных, принятых при проведении статистических испытаний. Результаты, полученные с помощью методов классической ТМО, отображают чаще всего среднюю величину задержки, так как на практике трудно получить аналитически точную функцию распределения задержек в системе. А вот результаты, получен-ные с помощью методов теории сетевого исчисления, дают граничные оценки задержек трафика в системе. Причем при использовании методов детерминированного сетевого исчисления DNC(Deterministic Network Calculus) полученные верхние и нижние границы задержек являются фиксированными, и они сколь угодно близки к реальным максимальным и минимальным значениям, но всегда больше их и меньше их соответственно. В случае же анализа системы с использованием теории стохастического сетевого исчисления SNC (Stochastic Network Calculus) может быть получено множество верхних и нижних граничных оценок задержки, которые могут быть превышены реальными граничными характеристиками с определенной заданной вероятностью. Возможность получения граничных значений характеристик функционирования СМО с помощью теории NC является очень полезным на практике для исследования инфокоммуникационных сетей и систем. Так, для пакетных сетей связи в международных рекомендациях (например, ITU-T Y.1541, ITU-T G.114, ITU-T G.1010, ETSI TS101329, 3GPP TS 22.105, 3GPP TS 23.107 и др.) в качестве нормативных указаны допусти-мые (максимально возможные) значения задержек, вариаций задержек и потерь пакетов в зависимости от класса трафика. В первой части статьи [5] были рассмотрены основные теоретические положения, современное состояние и перспективы развития теории сетевого исчисления. Во второй части приведены примеры практического использования методов DNC и SNC для исследования граничных характеристик функционирования современных инфокоммуникационных сетей. Рисунок 1. Сравнение результатов анализа задержек в СМО различными методами Сенсорные сети В настоящее время во всем мире активно разрабатываются и внедряются разнообразные технологии Интернета вещей, IoT (InternetofThings) [6]. Для связи различных устройств IoT часто используются беспроводные сенсорные сети WSN (Wireless Sensor Network). Они позволяют эффективно передавать данные от различных датчиков (сенсоров) через сенсорные узлы во внешнюю сеть и команды в обратном направлении для управления всевозможными исполнительными устройствами (актуаторами). Поскольку сенсорные сети по многим аспектам отличаются от традиционных проводных пакетных сетей, существующие результаты NC не могут использоваться для их анализа напрямую. В частности, сенсорные сети имеют такие особенности, как ограниченное время работы сенсорных узлов с батарейным питанием и использование перестраиваемых топологий при их связи. Поэтому была разработана специальная ветвь сетевого исчисления, получившая название Sensor Network Calculus (SeNC) [7; 9-11] и учитывающая особенности сенсорных сетей, такие как: взаимозависимость между потреблением энергии сенсорным узлом, требованиями к буферу узла и задержкой передачи информации в сети, специальные топологии сетей, расположение шлюзовых узлов и др. SeNC позволяет определить граничные оценки характеристик WSN, например максимальную задержку потоков данных в WSN, требуемые объемы буферов в сенсорных узлах, максимальное время жизни сети и др. Чаще всего в исследованиях на базе SeNC рассматривается сенсорная сеть с одним шлюзом во внешнюю сеть. Как правило, исследуемый трафик WSN учитывает только данные, получаемые от сенсоров/датчиков. Трафик, генерируемый шлюзом в направлении сенсорных узлов (например, для настройки сетевой структуры и настройки узлов), обычно не учитывается. Это считается допустимым, исходя из предположения, что трафик, передаваемый по направлению к сенсорным узлам, имеет значительно меньшую величину, чем трафик, вызванный обнаружениями контролируемых событий в сенсорных узлах. Кроме того, предполагается, что используемый протокол маршрутизации формирует дерево в сети сенсоров. Следовательно, сенсорную сеть можно моделировать направленным ациклическим графом с древовидной топологией и вершиной в узле, соответствующему шлюзу во внешнюю сеть (см. рисунок 2). Рисунок 2. Структура сенсорной сети WSN Каждый сенсорный узел i обслуживает свою внешнюю среду и, таким образом, описывается входной функцией ,ia соответствующей ее входному трафику от подключенных к узлу сенсоров/датчиков (см. рисунок 3). Если сенсорный узел i не является конечным узлом дерева (листом), тогда он получает также измеренные данные от всех его дочерних узлов child (i, 1), ..., child (i, ni), где ni - число дочерних узлов i-го сенсорного узла. Сенсорный узел i обрабатывает входную информацию от своих сенсоров и направляет ее на выход вместе с транзитной информацией от дочерних узлов, что приводит к выходной функции *iaот узла i к его родительскому узлу.Определим для WSN основные компоненты SeNC - кривую поступления и кривую обслуживания. Кривая поступления для i-го сенсорного ia описывается суммарным трафиком на его входах:1*(, ).iniichild i jj=a=a+ a∑(1) В [7] предложено несколько видов кривых поступления для WSN, которые могут использоваться на практике. Простейшим вариантом ограничения входного трафика в сенсорном узле является использование максимальной скорости ввода информации в узел ,r тогда кривая поступления имеет вид ( )( )0,.tt tra =r=γ Однако в зависимости от приложения сенсорной сети такой вид кривой поступления может привести к завышенным границам, если максимальная скорость редко является фактической скоростью поступления данных в узел. В этой ситуации более эффективной будет кривая, основанная на средней скорости поступления данных. Например, кривая поступления, которая фиксирует среднюю скорость rс кратковременными ее колебаниями s,имеет вид ( )( ),.tttsra =r +s=γ(2) Эта аффинная кривая поступления аналогична известной кривой для технологий маркерного («дырявого») ведра, которые широко используются для управления трафиком в IP-сетях [5]. Она обеспечивает более высокую скорость, чем ,r в течение коротких периодов времени, но в конечном итоге позволяет передавать данные только со средней скоростью .r Такая кривая поступления может использоваться на практике для описания ситуаций, когда сенсоры обычно передают данные с низкой скоростью. Однако если контролируемое явление обнаружено вблизи сенсора, скорость передачи данных увеличивается в течение фиксированного периода времени. Рисунок 3. Модель сенсорной сети (слева) и сенсорного узла (справа) Кривая обслуживания сенсорного узла отражает его возможности по передаче входных данных, полученных от собственных сенсоров или от других сенсорных узлов, по направлению к шлюзу. Часто она абстрагируется от специфики и особенностей реализации беспроводного канала связи и характеризует минимальное обслуживание, которое может быть реализовано узлом в наихудшем случае. Кривая обслуживания «скорость - задержка» является типичным и хорошо известным примером кривой обслуживания в традиционных сетях с коммутацией пакетов, например в пакетном планировщике «взвешенная справедливая очередь» WFQ (Weighted Fair Queuing) [5], и имеет вид( ),[],RTtRt T+b=- где R - постоянная скорость обслуживания; Т - фиксированная задержка. Хотя для сенсорных сетей часто нет необходимости или отсутствуют требуемые ресурсы (например, энергия,вычислительная мощность, емкость памяти) для реализации сложного алгоритма планирования, такого как WFQ, класс кривых обслуживания «скорость - задержка» представляет для WSN определенный интерес. Связано это с тем, что задержка хорошо отражает характеристики, вызванные применением концепции рабочего цикла сенсорного узла. В этом случае существует вероятность того, что входные данные собственных сенсоров или данные, которые должны передаваться от других узлов, часто поступают после того, как рабочий цикл сенсорного узла закончен, и, таким образом, возникает фиксированная задержка до тех пор, пока снова не будет доступна возможность приема, обработки и передачи данных в радиоканал. При простой схеме реализации рабочего цикла сенсорного узла эта задержка должна учитываться для всех передач данных, поскольку длина преамбулы фиксирована. В более сложных схемах, где передача данных сенсорным узлом повторяется многократно в течение определенного промежутка времени до получения положительного подтверждения от приемника, этот промежуток будет представлять худший случай задержки. Пропускная способность сенсорного узла может быть ограничена снизу фиксированной скоростью, которая зависит от скорости приемопередатчика, выбранного протокола канала связи и длительности рабочего цикла сенсорного узла. Таким образом, с некоторыми новыми параметрами получается следующая кривая обслуживания в сенсорном узле:,()()() ,RTtt Rt T+b=b = - где Rи T обозначают скорость передачи данных через узел и постоянную задержку при обработке данных в сенсорном узле соответственно. Кривая обслуживания сенсорного узла во многом зависит также от того, как принятые данные планируется передавать в радиоканал, и, следовательно, она зависит от характеристик канального уровня. Например, кривая обслуживания моделирует периодическую доступность сенсорного узла к полной скорости радиоканала C после некоторой начальной задержки T, обусловленной приемом и обработкой данных в узле. Это близко отражает характеристики технологии множественного доступа к среде передачи с времен-ным разделением TDMA (Time Division Multiple Access). Форма такой кривой для узла, принимающего на обслуживание трафик в течение промежутка времени s в кадре с длительностью f, показана на рисунке 4 [8]. Кривая аналогична предложенной в [9] для беспроводных сетей на базе стандарта IEEE 802.15.4. Эта кривая обслу-IEEE 802.15.4. Эта кривая обслуживания может быть аппроксимирована кривой «скорость - задержка» ( ),RTtb=()()0max,,Rt T-где sRCf=и T fs= -. Она показана на рисунке 4 в виде прямой с наклоном β, и ее можно считать непрерывным приближением кривой обслуживания TDMA. Рисунок 4. Кривая обслуживания TDMA и ее непрерывное приближение SeNC позволяет с наихудшей точки зрения связать следующие локальные характеристики отдельных сенсорных узлов: - сенсорную активность (описывается кривой поступления сенсорного узла); - требования к буферам каждого узла (описываются граничным значением загрузки узла),со следующими глобальными характеристиками сенсорной сети в целом: - задержкой передачи информации в каждом узле (описывается граничной оценкой задержки); - временем жизни сенсорной сети, обусловленным потреблением энергии сенсорным узлом от батареи питания (описывается рабочим ци-клом, учитываемым в кривой обслуживания сенсорного узла). SeNC позволяет определить значения этих ха- позволяет определить значения этих характеристик для заданного сценария приложения сенсорной сети. Сам сценарий характеризуется дополнительными ограничениями, такими как топология сенсорной сети и алгоритм маршрутизации трафика в ней. Зная кривые поступления и кривые обслуживания i-го сенсорного узла, с помощью (min+)-свертки можно определить поток данных на выходе этого узла, то есть трафик, который передается в родительский узел дерева [7]:1**(, ).iniiiichild i jij=a =a ⊗b = a + a⊗b Чтобы определить характеристики всей сенсорной сети, такие как максимальная задержка передачи информации или требования к локальным буферам, особенно на наиболее проблемном сенсорном узле чуть ниже шлюза (который назовем узлом с номером 1), используется следующая итерационная процедура для вычисления внутренних потоков в сенсорной сети [7]. 1. Предположим, что заданы кривые поступления сенсорных данных ia и кривые обслуживания ib для сенсорного узла i, i = 1, ..., N. 2. Для всех конечных (листовых) узлов граница выходного потока *ia может быть рассчитана с помощью свертки *.i iia =a ⊗b Каждый конечный (листовой) узел теперь помечен как «рассчитан». 3. Для всех узлов, имеющих только узлы-потомки, которые отмечены «рассчитан», граница выходного потока *ia может быть рассчитана согласно (3), и они могут быть тоже отмечены как «рассчитан». 4. Если узел 1 отмечен «рассчитан», алгоритм завершается, в противном случае - переход к шагу 3. После расчета внутренних потоков в сенсорной сети вычисляются граничные оценки объема буфера bi и задержки di для каждого сенсорного узла i соответственно: bss≥= a -b(4){}{}00sup inf:( )() .iiisdss≥=t≥ a ≤b +t (5) Чтобы определить наибольшую полную задержку передачи данных id от сенсорного узла i до шлюза, нужно сложить граничные оценки задержек в каждом узле на пути P(i) к шлюзу:().iii Pidd∈=∑(6) Максимальная задержка передачи данных в сенсорной сети может быть рассчитана как 1,...,max.iiiNdd==(7) Учитывая свойства DNC [5], возникает естественный вопрос: можно ли вычислить сквозную задержку из конца в конец в сенсорной сети через получение эквивалентной кривой обслуживания всей сети на основе свертки кривых обслуживания последовательно включенных сенсорных узлов? Хотя из-за агрегации трафика внутри сенсорной сети свертка не может быть применена напрямую, на самом деле существует способ получения кривой обслуживания всей сети на основе модифицированных кривых обслуживания, которые учитывают влияние перекрестного трафика на исследуемый поток данных [3]. Однако оценки, полученные таким образом, не обязательно ниже, чем вычисленные по формуле (7). Это зависит от фактических параметров кривых поступления и обслуживания. Следует отметить, что на практике часто сенсорные сетевые приложения рассматривают задержку передачи сообщений только как ограничение и в первую очередь требуют максимизации срока службы сенсорной сети. Длительность рабочего цикла и, следовательно, свойства энергопотребления сенсорных узлов, обычно включаются в кривую обслуживания сенсорных узлов. Поэтому вместо расчетов границ задержки и требований к буферам, как описано выше, часто планирование сенсорных сетей начинается с задания требований к задержке и объему буфера сенсорных узлов и сводится к определению длительности рабочего цикла, а следовательно, уровня энергопотребления и срока службы отдельных узлов и всей сенсорной сети [12-14]. Программно-конфигурируемые сети Перспективным направлением развития инфо-коммуникаций является использование программно-конфигурируемых сетей SDN (Software Defined Networking) [15]. В SDN уровень управления сетью физически отделён от уровня передачи данных за счет переноса функций управления сетевыми устройствами (маршрутизаторами, коммутаторами и т. п.) в программные приложения, работающие на отдельном сервере (контроллере), часто называемом сетевой операционной системой (см. рисунок 5). В результате получается гибкая, управляемая, адаптивная и экономичная архитектура, которая способна эффективно подстраиваться под передачу больших потоков разнородного трафика. Модель SDN-коммутатора представляет собой сетевой элемент с информационным входом A, управляющим входом для коррекции таблиц коммутируемых потоков данных C и выходом F, таким, что F = C(A(t)), где A(t) - кумулятивное число пакетов, поступивших на вход коммутатора к моменту времени t; C(n) - число поступивших пакетов управления потоками (например, в протоколе OpenFlow это команда Flow_Mod), которые являются первыми пакетами в группе из n пакетов, относящихся к одному потоку; F(t) - кумулятивное число пакетов на выходе коммутатора к моменту времени t. В случае протокола OpenFlow, когда контроллер уже сформировал запись в таблице потоков коммутатора, все последовательные пакеты (кроме первого) одного потока, которые соответствуют имеющейся записи, не будут перенаправляться в контроллер OpenFlow, а сразу поступят на выход коммутатора. Таким образом, действие протокола OpenFlow следует учитывать только в определении функции C(n). Для идеального SDN-коммутатора, если входящий поток ( ),Asrограничен сверху и поток управления ( ),Ñδγ тоже ограничен сверху, то исходящий поток (),Fγs + δ γr также будет ограничен сверху [16]. Таким образом, SDN-коммутатор можно моделировать сервером с постоянной скоростью обслуживания m (задаваемой целым положительным числом) для входящего потока, описываемого традиционной в DNC моделью [5]:0( )( )(),,At Ast ss t- ≤s+r -≤ ≤где ,sr - верхние границы бёрстности и скорости поступления входящего потока соответственно. Для учета особенностей функционирования сети SDN в [16] введено понятие остановленной последовательности At в момент времени t, которая для любой возрастающей последовательности (например, кумулятивного процесса поступления пакетов) определяется как (рисунок 6):( ),,()( ),.åñëèâ ïðîòèâíîì ñëó÷àåAttAtAt≤t=t (8) Согласно (8), для остановленной последовательности At, если A - процесс поступления пакетов, то нет поступлений пакетов после момента времени t. В [16] показано, что остановленная последовательность At имеет ( ),sr-верхние границы, где бёрстность потока в момент времени tравна[]00( )max max( )( )() .tstAt Ast s≤ ≤t ≤ ≤s t =- -r - При этом период занятости SDN-коммутатора начинается с момента времени s и заканчивается в момент t, если очередь SDN-коммутатора в моменты времени (s - 1) и t была пуста, а во время указанного периода очередь не пуста, то есть ( )10;qs-=0() ;as>0()qr> для srt≤≤ и ( )0,qt= где q(t) - длина очереди SDN-коммутатора на временном интервале t, ( )1()()a tAt At= -- - число поступивших пакетов в момент времени t. Таким образом, продолжительность периода занятости коммутатора в единицах времени равна B = t - s. Состояние очереди SDN-коммутатора в момент (t + 1) определяется выражением1100()(()())(),ïðèqtqt atq++ = + + -m= где запись (...)+ означает, что выражение в скобках оценивается, когда оно положительно и равно нулю в противном случае. Используя индукцию, можно доказать, что в момент времени t длина очереди равна{}0() max ()( )() .stqtAt Ast s≤≤=- -m -(9) Если предположить, что процесс поступления пакетов A(t) имеет ( ),sr-верхние границы бёрстности и скорости и если ,m≥r то из уравнения (9) следует, что ( )0.qtt≤s∀ ≥ . Заметим, что эта верхняя граница очереди не зависит от скорости обслуживания. Используя (9), можно вычислить верхнюю границу длины очереди в буфере коммутатора SDN. Кумулятивный выходной поток SDN-коммутатора: { } 0 0 () () () ( ) ( ) . min st Ft At qt As t s t ≤≤ = - = +m - ∀ ≥ Основываясь на определении периода занятости B, на выходе SDN-коммутатора должно быть m пакетов в каждом периоде B на интервале {s, …, t - 1}. Также должен быть по крайней мере один пакет в очереди в момент времени t - 1. Кроме того, в интервале времени {s, …, t - 1} по крайней мере (mB + 1)пакетов должны поступить на вход SDN-коммутатора, чтобы обеспечить интервал его занятости. Поскольку имеются верхние ограничения параметров входящего потока ( ) ,, A sr  то в течение периода занятости B на коммутатор поступит не более ( ) B s+r -пакетов. Таким образом, справедливо неравенство 1 , BB m + ≤s+r которое можно переписать в виде (заметим, что B представляется в целочисленном виде) 1 . B  s- ≤  m-r  (10) Зная верхнюю границу периода занятости,можно просто найти границу задержки пакетов в очереди, которая определяется как интервал между моментом времени, когда пакет покидает SDN-коммутатор, и моментом времени, когда он поступил в коммутатор (и потенциально был перенаправлен в SDN-контроллер). Тогда задержка любого пакета всегда меньше или равна длительности периода занятости коммутатора. Поэтому верхняя граница времени задержки пакетов, не зависящая от дисциплины обслуживания пакетов в коммутаторе, равна B и определяется выражением (10). Рисунок 5. Архитектура SDN Рисунок 6. Графическая интерпретация кумулятивного входящего потока А(t) и остановленной последовательности At(t) Рассмотрим модель сети SDN, основанную на DNC, которая позволяет получить замкнутую форму верхней границы очереди в SDN-контроллере (см. рисунок 7). С учетом правила мультиплексирования потоков в DNC можно рассмотреть входящие в контроллер потоки пакетов (команд запроса протокола OpenFlow) от других SDN-коммутаторов в дополнение к коммутатору, который изображен на рисунке 7. Тогда кумулятивный входящий поток A2 представляет собой пакетные данные от всех SDN-коммутаторов, которые управляются централизованно данным SDN-контроллером. Аналогично часть команд управления потоками контроллер отправляет в коммутатор с номером 1 (S1), а остальная часть передается в другие коммутаторы, которые входят в состав сети SDN (не показаны на рисунке 7) и управляются данным контроллером. Поток пакетов на выходе коммутатора S1 (то есть FS (t)) разделяется на две части. Одна часть пакетов, для которых коммутатор не имеет записи в своей таблице потоков, отправляется на контроллер (на рис. 7 это поток S12(FS(t))). Другая часть представляет поток пакетов, для которых в таблице потоков коммутатора имеется необходимая запись. Предполагается, что оба кумулятивных входных потока (то есть A1 и A2) ограничены сверху, а скорости обслуживания очередей в коммутаторе и контроллере равны C1 и C2 соответственно. Функции управления пото- ками ( ) 12 12 12 , S δγ  и ( ) 21 21 21 , S δγ  ограничены сверху. В [16] получены формулы для верхних границ длин очередей в SDN-контроллере и SDN-коммутаторе соответственно: 1 21 2 21, S Q ≤s +γ s +δ  2 12 1 12 , C Q ≤s +γ s +δ  где 1 21 2 21 12 21 1 12 21 1 s +γ s +γ δ +δ s= -γ γ  , 2 12 1 12 21 12 2 12 21 1 s +γ s +γ δ +δ s= -γ γ  . Стоит отметить, что верхние границы очередей в буферах не зависят от момента времени t и в основном зависят от верхних границ бёрстности потоков пакетов, поступающих в коммутаторы и в контроллер. Поэтому, зная характеристики входных потоков и режим работы SDN-контроллера (посредством мониторинга или моделирования), с помощью методов теории DNC можно легко вычислить верхние границы очередей и требования к размерам буферов контроллера и коммутаторов. Рисунок 7. Модель сети SDN (пример с одним коммутатором) Рисунок 8. Архитектура мобильной сети LTE Мобильные сети LTE Мобильная сеть четвертого поколения на базе технологии LTE (Long Term Evolution) включает в себя улучшенную сеть радиодоступа E-UTRAN (Evolved Universal Terrestrial Radio Access Network) и усовершенствованное пакетное ядро EPC (Evolved Packet Core). E-UTRAN построена как совокупность улучшенных базовых станций eNodeB (Evolved NodeB), подключенных в EPC. EPC включает различные шлюзы GW (Gateway), блоки управления мобильностью MME (Mobility Management Entity) и ряд серверов (HSS, PCRF, серверы приложений и др.), которые связаны между собой через пакетную транспортную IP- сеть на базе маршрутизаторов (рисунок 8). В [17] приведен метод оценки стохастической границы задержки из конца в конец при передаче данных от пользовательского терминала UE (User Equipment) через базовую станцию eNodeB и EPC с использованием теории SNC. Предположим, что в сети LTE передается два типа трафика: реального времени RT (например, VoIP и потоковое видео) и нереального времени NRT (например, загрузка Web-страниц и FTP). Потоки трафика, передаваемые из конца в конец через множество маршрутизаторов сети EPC, будем называть сквозными (для них в обозначениях различных переменных будет использоваться индекс 1). Потоки, пересекающие только некоторые маршрутизаторы EPC сквозного потока, будем называть перекрестными потоками (у них индекс 2). При этом такие потоки также могут передавать как трафик RT (обозначается в индексе дополнительным символом t), так и трафик NRT(обозначается в индексе дополнительным симво- лом с). Предположим, что трафик в сети LTE имеет длиннохвостное распределение интервалов между заявками в потоках и в SNC его можно модели- SNC его можно модели- его можно моделировать стохастической функцией, описываемой c помощью обобщенной стохастически ограниченной бёрстности gSBB (generalized Stochastically Bounded Bursty) [18]: () , vb At f t r  , где ρ - максимальная скорость потока трафика; f - некоторая граничная функция бёрстности потока трафика, которая часто аппроксимируется экспоненциальной функцией. Тогда стохастическая кривая поступления i-го сквозного потока трафика RT 1 , it A  11 1 ,, ii i vb t t t ft r +s  где 1 i t r и 1 i t s - скорость и бёрстность потока соответственно; 1 () i t fx = i bx i ae - = - граничная функция бёрстности. Аналогично для j-го сквозного потока трафика NRT 2 , jt A  22 2 ,, jj j vb t t t ft r +s где 2 () j t fx = . j nx j me - Аналогичные стохастические кривые поступления с соответствующими параметрами можно определить для перекрестных потоков трафика RT и NRT. Пусть N1t и N2t обозначают число всех сквозных потоков трафика RT и NRT соответственно. Используя теорему о мультиплексировании потоков [19], можно получить агрегированный процесс поступления всех сквозных потоков трафика RT S1t : 1 11 () , , t vb t t At f a  где 1 1 11 1 t N tt t ff f = ⊗⋅⋅⋅⊗ и ( ) 1 1 11 () . t ii t tt iS tt ∈ a = r +s ∑ Аналогично агрегированный процесс поступления всех сквозных потоков трафика NRT S2t : 2 22 () , , t vb t t At f a  где 2 1 22 2 t N tt t ff f = ⊗⋅⋅⋅⊗ и ( ) 2 2 22 () . jj t t tt jS tt ∈ a = r +s ∑ Предположим, что в EPC каждый маршрутизатор d является системой с сохранением работы и постоянной скоростью обработки трафика R. Пусть маршрутизатор d имеет два отдельных буфера с очередью FIFO для потоков трафика RT и NRT и общий планировщик трафика со строгим приоритетом SP (Strict Priority) - см. рисунок 9. На основании приоритета планировщик маршрутизатора d реализует детерминированную кривую обслуживания для всех потоков трафика RT: 1 . d Rt b= Следовательно, для всех потоков трафика NRT маршрутизатор d реализует детерминированную кривую остаточного обслуживания: 2 1 1 , , d d d iS i Rt ∈  b= - r   ∑ где 1 d S - функция, описывающая все потоки трафика RT в маршрутизаторе d. Детерминированные кривые обслуживания, реализуемые маршрутизатором d суммарным сквозным потоком трафика RT и NRT, равны соответственно: 111 11 11 ∈∈  b =b -a = - r - s   ∑∑ ,, , dd dd dd tc iS iS ñc i ñ ic d Rt 2 222 1 2 2 1 2 , , , . c tc dd d c ddd dd iS jS jc i d jS jc Rt ∈∈ ∈ b =b -a =  = - r- r -   -s ∑∑ ∑ С учетом описанных выше моделей сквозных и перекрестных потоков трафика RT и NRT и модели обслуживания этих потоков в маршрутизаторе вероятностные границы сквозных задержек для потоков трафика RT и NRT в опорной сети EPC оцениваются следующими неравенствами [17]: 11 11 1 1 , , ( ), tc tt t t cn x PD f g x r q  +s +s  > ≤⊗    22 22 2 2 , , ( ), tc tt t t cn x PD f g x r q  +s +s  > ≤⊗    где 11 , i tt iS ∈ s= s ∑ 22 j tt jS ∈ s= s ∑ - бёрстность суммарных сквозных потоков трафика RT и NRT соответственно; 1 11 , , d c d c ic d iS ∈ ∈ s= s ∑∑ R 2 22 , d c d c jc d jS ∈ ∈ s= s ∑∑ R - бёрстность суммарных перекрестных потоков трафика RT и NRT соответственно; { } 1 11 1 1 1 , , min ( ) , n c nn ic iS nN t r nt ∈ ≤≤ q  = b- r - - q  ∑ { } 2 22 1 2 1 , , min ( ) n c nn ic iS nN t r nt ∈ ≤≤ q  = b- r - - q  ∑ - скорости обслуживания маршрутизатором сквозных потоков трафика RT и NRT соответственно; q - свободный параметр граничной функции скорости обслуживания трафика в маршрутизаторе d; N - число всех потоков в маршрутизаторе d; R - набор маршрутизаторов CN при обслуживании сквозных потоков трафика. Граничные функции обслуживания маршрутизатором сквозных потоков трафика RT и NRT равны между собой и определяются как 2 2 12 , , () () (), N N t tc c gx gx f f x q q = = ⊗⋅⋅⋅⊗ где ( ) 1 1 1 , () () n n n n ax cc c n x n f f x f y dy ke a ∞ q - = + =+q q ∫ - граничная функция бёрстности n-го перекрестного потока трафика, n = 1, …, N - 1; k, a - коэффициенты экспоненциальной аппроксимации граничной функции бёрстности входящего трафика; , () N N c fx q = () . N ax c f x ke - = В сети доступа LTE используется радиосистема MIMO с M × N-радиоканалами, которая реализует для входного потока слабую стохастическую кривую обслуживания , ws Sg b  с граничной функцией скорости обслуживания () vx g x ue - = и кривой обслуживания , Ct b= где С - усредненная производительность радио- системы E-UTRAN на базе технологии MIMO, которая в [17] определена с помощью Марковской цепи и модели Гильберта - Элиотта для од- - Элиотта для од- Элиотта для од- ного радиоканала. Тогда стохастическая граница задержки любого потока в сети доступа E-UTRAN определяется из неравенства ( ), an x P D f gx C  > ≤⊗   где 112 2 ' '' () , tt t t fx f g f g qq =⊗⊗⊗ в которой граничные функции обслуживания для трафика RT и NRT равны соответственно: 11 1 1 ' ' () () () tt t x g x g x g y dy ∞ q = + q ∫ и 22 2 1 '' '' () () () , tt t x g x g x g y dy ∞ q = + q ∫ где q' и q" - свободные параметры граничных функций скорости обслуживания в сети доступа потоков трафика RT и NRT соответственно. Зная граничные оценки задержек в опорной сети CN и в сети доступа AN, можно определить стохастические границы задержки в целом в сети LTE для сквозных потоков трафика RT и NRT соответственно: { } { } { } 11 11 0 ,, ,, inf , t cn t an t cn t an xd PD D d PD d PD d x ≤≤ + >≤  ≤ > + >-  { } { } { } 22 22 0 ,, ,, inf , t cn t an t cn t an xd PD D d PD d PD d x ≤≤ + >≤  ≤ > + >-  где 1 , t cn D и 1 , t an D - границы сквозной задержки потоков трафика RT в сети EPC и в cети E-UTRAN, соответственно, а 2 , t cn D и 2 , t an D - аналогичные границы сквозной задержки потоков трафика NRT. Рисунок 9. Модель маршрутизатора d CN Выводы Ограниченный объем статьи не позволяет представить больше примеров практического применения теории сетевого исчисления для исследования различных инфокоммуникационных сетей и систем. Детерминированные модели и методы NC использовались для анализа гранич- NC использовались для анализа граничных характеристик функционирования различных пакетных сетей связи (ATM, Ethernet, NGN, IMS), сетей на кристалле, бортовых сетей самолетов, автомобилей и спутников, дорожных сетей (автомобильных, железнодорожных), индустриальных сетей, оптических сетей (WDM, PON) и др. Стохастический подход на базе теории NC применялся для исследования различных систем и сетей с радиоканалами, прежде всего мобильных сетей 4G/5G, сетей WiFi, беспроводных сенсорных сетей Интернета вещей, интеллектуальных энергетических сетей Smart Grid, сетей дата-центров и облачных вычислений и др. Проведенный анализ ряда работ в различных областях применения теории NC позволяет сформулировать следующие выводы. 1. Большая часть исследований инфокоммуникационных сетей и систем основана на детерминированном NC, при этом в качестве кривых поступления входящих потоков чаще всего используются (s, ρ)-кривые с максимальной бёрстностью потока s и постоянной скоростью поступления данных в потоке ρ (формирователь трафика типа «дырявое ведро»), а типичные кривые обслуживания потоков в узлах имеют вид «скорость - задержка» (R, T). Полученные оценки на основе таких моделей DNC дают верхние границы сетевых характеристик, но иногда они слишком завышены, особенно в системах и сетях со стохастическими процессами. 2. Появившиеся в последние годы модели стохастического NC для исследования инфокоммуникационных сетей и систем в качестве кривых поступления чаще всего используют стохастические (s(q), ρ(q))-модели с граничной функцией на основе экспоненциально ограниченной бёрстности, а кривые обслуживания имеют граничную функцию с экспоненциально ограниченными колебаниями скорости обслуживания. Такие модели лучше учитывают стохастичность процессов поступления и обслуживания потоков трафика, но получаемые верхние границы сетевых характеристик всегда имеют определенную вероятность их превышения, которую часто сложно оценить на практике. 3. В целом теория сетевого исчисления NC позволяет с помощью концепций детерминированных или стохастических кривых поступления и кривых обслуживания строить модели сетей и систем массового обслуживания различного назначения. Используя теоремы о последовательной свертке узлов обслуживания и мультиплексировании потоков в узле, можно достаточно просто определить верхние граничные оценки характеристик качества обслуживания трафика в таких сетях и системах, например сквозные задержки, которые зачастую и требуются на практике.

About the authors

A. V Roslyakov

Povolzhskiy State University of Telecommunications and Informatics

Email: arosl@mail.ru
Samara, Russian Federation

A. A Lysikov

Povolzhskiy State University of Telecommunications and Informatics

Email: arosl@mail.ru
Samara, Russian Federation

References

Supplementary files