BASIC PRINCIPLES AND PERSPECTIVES OF NETWORK CALCULUS APPLICATION

Full Text

Введение С началом нового тысячелетия наметился активный переход от классических сетей общего пользования с коммутацией каналов (TDM) к мультисервисным сетям следующего поколения (Next Generation Network - NGN), в основе которых лежит коммутация пакетов. На заре развития TDM-сетей (прежде всего телефонных) использовалась теория телетрафика, которая послужила в дальнейшем основой классической теории массового обслуживания (ТМО) [1], сыгравшей важную роль при моделировании, анализе и расчете характеристик функционирования различных систем массового обслуживания (СМО). ТМО позволяет установить количественную связь между числом и типом приборов обслуживания, характеристиками входящего потока заявок и качеством их обслуживания в СМО. Например, в системах с очередями под качеством обслуживания понимается своевременность обслуживания поступивших в систему заявок (среднее число заявок, находящихся в очереди на обслуживание, среднее время ожидание в очереди и т.д.), в системах с потерями - вероятность потерь заявок. Стоит отметить, что число заявок (вызовов, пакетов, ячеек и т.п.), поступающих в реальную сеть связи (в отдельный узел сети или в сеть в целом) за определенный промежуток времени, является случайной величиной. Более того, и длительности обслуживания заявок в узлах сети также представляют собой случайные величины с различными законами распределения. Следовательно, узел реальной сети связи справедливо представлять моделью СМО общего вида G/G/1 в обозначениях Кендалла-Башарина. Однако точный анализ такой модели возможен только с использованием имитационного моделирования, и при теоретических исследованиях обычно принимается ряд допущений. Например, в большинстве случаев поток заявок рассматривается как Пуассоновский и анализируемые СМО, моделирующие отдельные узлы сети, описываются более простыми моделями типа M/G/1, M/D/1, M/M/1 и т.д. Такое упрощение значительно облегчает проведение аналитических исследований, но не соответствует реальному трафику и дисциплинам обслуживания нагрузки в узлах современных мультисервисных пакетных сетей NGN. Игнорирование данного факта может привести к большим недооценкам реальных характеристик качества обслуживания QoS. Таким образом, смена одного типа сетей связи на другой должна повлечь за собой и смену математических моделей и методов расчета характеристик качества работы этих сетей. Особенности трафика мультисервисных пакетных сетей При попытке применить классическую ТМО к исследованию трафика мультисервисных пакетных сетей NGN возникает ряд трудностей. 1. Разнообразные заявки на обслуживание в мультисервисных пакетных сетях представляют собой пакеты различной длины. Длина пакета зависит главным образом от типа передаваемого трафика: голос, видео, трафик данных, служебный сигнальный трафик и др. С другой стороны, в сетях TDM обычно имеется только один тип заявок, которые поступают в систему и либо остаются ждать момента обслуживания (СМО с «Инфокоммуникационные технологии» Том 11, № 3, 2013 Кудрявцева Е.Н., Росляков А.В. 35 ожиданием), либо покидают систему сразу в случае занятости обслуживающих приборов (СМО с потерями). 2. Для передачи пользовательских и служебных данных в сетях NGN используются различные протоколы (TCP/IP, UDP, RTP/RTCP, FTP, HTTP, H.323, SIP, SIGTRAN и др.). При передаче пользовательских данных могут использоваться разнообразные аудио- и видеокодеки (G.711, G.723, G.729, H.261, H.263 и др.). Соответственно, при анализе таких сетей необходимо учитывать различные длины пакетов и требуемые полосы пропускания, необходимые для того или иного кодека. Обслуживание пакетов может осуществляться в соответствии с различными методами обеспечения гарантии качества QoS (IntServ, DififServ и т.д.). Все это значительно усложняет расчеты пакетных сетей при использовании классической ТМО. 3. В рекомендациях международных организаций по стандартизации в области телекоммуникаций (например, рекомендации МСЭ-Т Y.1541, G.114, G.1010, ETSI TS101329, 3GPP TS 22.105, 3GPP TS 23.107 и др.) указаны допустимые (максимально возможные) значения показателей качества обслуживания трафика (например, задержек, вариаций задержек пакетов) в зависимости от класса трафика. Теория массового обслужи вания позволяет вычислить в основном только средние значения характеристик QoS. 4. Методы расчета характеристик пакетных сетей (пропускной способности каналов, емкости буферов, величин задержек, числа потерянных пакетов и пр.), основанные на классической ТМО с простейшими потоками вызовов, которые с успехом использовались при анализе телефонных сетей, дают неоправданно оптимистические оценки. Обусловлено это тем, что реальный IP-трафик носит самоподобный (фрактальный) характер, то есть выглядит качественно одинаково при различных масштабах времени. Также пакетный трафик характеризуется высокой пачечностью (группированием пакетных данных в «пачки»). Из-за этого в мультисервисном пакетном трафике при сравнительно небольшом среднем значении могут присутствовать относительно большие всплески интенсивности поступления запросов (большие значения дисперсии) - см. рис. 1. Учитывая вышеизложенное, можно сделать вывод о том, что классические модели и методы ТМО не могут обеспечить необходимую точность анализа мультисервисных сетей NGN. Для исследования сложных пакетных сетей в начале 1990-х гг. была предложена качественно новая концепция - теория сетевого исчисления (Network Calculus) [2]. ü с; у iz IГ Время Рис. 1. Зависимость интенсивности поступления пакетов от времени Основы теории сетевого исчисления (Network Calculus) Сетевое исчисление Network Calculus представляет собой теоретическую основу для определения граничных оценок параметров качества обслуживания заявок в пакетных сетях [4; 12]. Основы сетевого исчисления берут свое начало из математической теории диоидов (диоид - алгебра с двумя операциями) [5], в частности, «мин-плюс / макс-плюс» диоида. Теорию также называют «мин-плюс / макс-плюс» алгеброй, относящейся к классу идемпотентных алгебр. «Макс-плюс» алгебра двойственна «мин-плюс» алгебре с подобными концепциями и результатами, когда минимум заменяется максимумом, а инфимум - супремумом. Основные положения теории сетевого исчисления в большинстве случаев используют «мин-плюс» алгебру. В отличие от традиционной алгебры в «мин-плюс» алгебре операции изменяются следующим образом: сложение превращается в расчет инфимума (или минимума, если он существует), умножение превращается в сложение. Стоит отметить, что использование таких «Инфокоммуникационные технологии» Том 11, № 3, 2013 36 Кудрявцева Е.Н., Росляков А.В. подходов существенно упрощает определение граничных оценок. Детальная трактовка «мин-плюс» и «макс-плюс» алгебр представлена в [5]. Рассмотрим некоторую систему обслуживания S (см. рис. 2), на вход которой поступают заявки (отдельные пакеты данных, биты), описываемые некоторой входной функцией поступления x{t) , и появляются на выходе системы с некоторой переменной задержкой. Выходную функцию, описывающую выходной поток, обозначим через Y{t). В качестве системы S можно рассматривать отдельный буфер, сложный коммутационный узел, совокупность нескольких узлов или даже всю сеть. Сетевое исчисление предоставляет возможность оценить границы двух очень важных для обеспечения соответствующего уровня качества обслуживания (QoS) характеристик системы (см. рис. 2). Рис. 2. Система обслуживания 1. Виртуальная задержка в момент времени t: D(t) = inf {г > 0 : Х(ґ) < Т(? + z-)} для любых 0 < х < D{t). 2. Загрузка (backlog) в момент времени t: B(t)= X(t)-Y(t + т). Загрузка - это количество заявок (сообщений, пакетов, бит и т.д.), которые находятся в системе. Для отдельного буфера загрузка представляет собой длину очереди, если система более сложная, то загрузка - это число заявок в системе в предположении, что можно одновременно наблюдать вход и выход. Чтобы упростить описание процессов поступления и обслуживания заявок, используются их границы, которые в дальнейшем анализируются. В основе теории сетевого исчисления лежат два понятия: кривая (функция) поступления и кривая (функция) обслуживания. 1. При заданной неубывающей функции а, определенной для всех t>0 (а є F), говорят, что входящий поток X ограничен функцией а тогда и только тогда, когда для всех x<t выполняется неравенство X{t)~ Х{г)< a(t-r). В этом случае говорят, что а - кривая поступления для потока X. 2. Рассмотрим СМО S и поток, проходящий через систему, с входной функцией x(t) и выходной функцией Y {t). СМО S реализует для потока кривую (функцию) обслуживания *S(V) тогда и только тогда, когда S є F и , где ® - операция свертки случайных функций (см. рис. 3); S(t) - неубывающая функция, *S(o) =0 и для всех t> 0 выполняется неравенство Y{t)> in f(x(r)+S(^-r)). T<t Y(t) Рис. 3. Иллюстрации кривых поступления и обслуживания В зависимости от характера этих кривых различают детерминированное и стохастическое сетевые исчисления [4; 6-7; 12]. Если известны кривые обслуживания каждого 7-го узла сети, то можно определить общую кривую обслуживания последовательной цепочки из n узлов в виде Sm(f) = (S, ® S2 в... в S, в... 0 SМ Таким образом, теория сетевого исчисления представляет собой достаточно простой и вместе с тем эффективный аппарат для расчета граничных значений параметров качества обслуживания в пакетных мультисервисных сетях NGN. Обзор работ в области теории сетевого исчисления Основоположником теории сетевого исчисления был Р.Л. Круз, опубликовавший первые работы в этом направлении [2-3], где был предложен метод расчета границ задержки и требуемого размера буфера в отдельно взятых узлах [2] и в сетях с пакетной коммутацией [3]. В методе использовался входной детерминированный поток данных в предположении, что он не превышает определенной ( заданной) границы. Чтобы выполнялось это условие, было введено несколько дополнительных сетевых элементов: «Инфокоммуникационные технологии» Том 11, № 3, 2013 Кудрявцева Е.Н., Росляков А.В. 37 - элемент с постоянной задержкой D, в ко -тором поток на выходе Y(t) в момент времени t связан с потоком на входе X(t) следующим выражением Y(t) = X(t-D); - буфер приема, на вход которого посту- 00 пает поток вида *(')=с£ ^{тк-t-Tk +Lk/C) ’ где Lk - длина k-го пакета в битах, который начинал передаваться в момент времени тк ; 1А - функция-индикатор истинности состояния А; С - скорость поступления потока. На выходе такого буфера поток определяется как 00 Y(t)-^LkS(t-tk), где 8 - дельта-функция к=1 , Дирака, а tk = тк + Lk/C для всех k. Очевидно, что любой бит данных, проходящих через этот сетевой элемент, обладает максимальной задержкой, ограниченной значением Lj С ; - {сг,р) -регулятор трафика выступает в качестве элемента, реализующего функцию «ограничителя пачечности». Более подробное описание можно найти в [1; 6]. Обобщением [2-3] и ряда других работ является [4], где проведена аналогия теории сетевого исчисления (см. рис. 4б) с теорией цепей (см. рис. 4а). R + О 1 I-1-о + x(t) h(t) -|- С y(t) (б) Рис. 4. RC-цепь (а), СМО (б) Для обеих систем нахождение функции на выходе осуществляется вычислением свертки входной функции и функции, характеризующей систему: а) в случае теории цепей - это свертка входной функции и импульсной характеристики цепи t y{t) - (х * h^t) - x{t)h{t - т)сіт ; о б) в случае теории сетевого исчисления - это «мин-плюс» свертка входной функции и функции обслуживания S = с 9 характеризующей СМО inf Wr)+s(f-r)}. reR,0<T<t С 1991 г. до настоящего времени над теорией сетевого исчисления работало множество исследователей в разных странах. Работы велись в различных направлениях: первоначально развивалось направление детерминированного сетевого исчисления [2-4; 16; 20], в котором анализ основных параметров качества обслуживания пакетов QoS (загрузки и задержки) производился при фиксированных кривых (функциях) поступления и обслуживания трафика. В дальнейшем получило развитие и стохастическое сетевое исчисление [12-14; 17; 24], которое позволяет получить оценку того, что реальные значения параметров QoS не будут превышать граничные величины с некоторой вероятностью PtßoSw<QoSin))üe. В большей части работ [4; 6-18; 20-24] исследовались кривые трафика и обслуживания в пространственной области, что подразумевает рассмотрение количества поступивших и обслуженных системой заявок на интервале времени, где [г, t) 9 где t> О и 0<T<t. Однако в [19] рассматривались модели и во временной области, учитывающие промежутки времени между пакетами в потоке. Кривая поступления в этом случае имеет вид Г(m9n)= а(п) -а(т)9 где a(i) - время прибытия i-го пакета в систему, кривая обслуживания п - A(m,n)=^Atk для любых 0 <т<п, где к=т Att - время обслуживания i-го пакета. Там же были показаны возможности преобразования между моделями во временной и пространственной областях. Трудности и возможности применения теории сетевого исчисления для исследования не FIFO систем рассмотрены в работах [11; 22]. В работах [5; 23; 25] для анализа систем использовалось преобразование Лежандра, аналогичное преобразованию Фурье, для упрощения вычислений «мин-плюс» сверток функций. Это позволило перенести модели в скоростную область теории сетевого исчисления, где рассматривается частота поступления заявок в систему и их ухода из системы. Следует отметить, что в последние годы теория сетевого исчисления охватила широкий круг областей исследования. Создававшаяся изна «Инфокоммуникационные технологии» Том 11, № 3, 2013 38 Кудрявцева Е.Н., Росляков А.В. чально для анализа проводных пакетных сетей теория была распространена и на беспроводные сети, оптические сети. Большое количество работ посвящено исследованию самоорганизующихся нейронных сетей на основе теории сетевого исчисления. Рассматриваемая теория не обошла даже авиационную промышленность, где на основе методов теории сетевого исчисления [9] была произведена оценка распределения сквозных задержек в бортовой вычислительной сети современного аэробуса A380. Аналогичный подход использовался для анализа функционирования промышленной вычислительной сети атомной электростанции [26]. Заключение С учетом вышеизложенных особенностей пакетного трафика сетей следующего поколения очевидно, что теория сетевого исчисления в наибольшей степени подходит к определению показателей качества обслуживания мультисерви-сного трафика в сетях NGN. С использованием данной теории могут быть получены граничные оценки параметров QoS не только отдельных узлов сетей NGN (гибкие коммутаторы, шлюзы, SIP-серверы и т.д.), но и целых участков или даже всей сети в целом. Стоит отметить, что данная теория позволяет получить оценки QoS не просто для потока пакетных данных, а для конкретного вида мультисервисного трафика в общем потоке.

About the authors

E. N Kudryavtseva

Email: kenzayac@rambler.ru

A. V Roslyakov

Email: arosl@mail.ru

References

Supplementary files