STUDY OF BOUNDARY VALUES OF VPN TRAFFIC DELAYS CONSIDERING CROSS FLOWS

Full Text

Введение В настоящее время активно развивается концепция программно-конфигурируемых сетей SDN (Software-Defined Network) c использованием сетевой виртуализации NFV (Network Functions Virtualization), предлагаемая как следующий этап эволюции существующей концепции построения сетей NGN (Next Generation Networks) и 4G. Прототипом виртуализации послужили виртуальные частные сети VPN (Virtual Private Network), являющиеся одной из наиболее востребованных услуг в сетях NGN [1]. Сеть VPN представляет собой набор фиксированных маршрутов, проходящих через определенные сетевые узлы. Как правило, в сети оператора связи одновременно реализуется множество таких виртуальных сетей. Для каждой VPN оператором должны строго соблюдаться установленные в соглашении о гарантированном уровне сервиса SLA (Service Level Agreement) характеристики качества обслуживания QoS (Quality of Service) (например, задержка передачи пакетов, гарантированная полоса пропускания, доля потерянных пакетов и др.). В местах пересечения большого числа потоков трафика различных VPN возникают конфликты при совместном использовании ресурсов узлов и каналов связи. Поэтому при вводе каждой новой VPN оператору необходимо распределить ресурсы своей сети так, чтобы с одной стороны предоставить услугу VPN максимальному количеству клиентов с гарантированным QoS, а с другой стороны, обеспечить эффективное использование ресурсов узлов и каналов связи. Иными словами, оператор на этапе планирования новой VPN должен определить для нее один или несколько оптимальных сетевых маршрутов. По аналогии с алгоритмами маршрутизации в IP-сетях, оптимальный маршрут для VPN можно определить на основе различных метрик, например, его длины или сквозных характеристик QoS. Первый подход является достаточно простым и подразумевает выбор кратчайшего маршрута в сети как наиболее оптимального. Однако в этом случае возникает риск неэффективного использования сетевых ресурсов, так как при перегрузке такого маршрута пакеты трафика все равно будут передаваться по нему, создавая большие очереди в буферах узлов, в то время, как трафик можно было бы направить по более длинному, но менее загруженному маршруту. В таком случае второй подход выглядит более выгодным, если в качестве критерия выбора оптимального маршрута, например, использовать значение сквозной задержки. Классическими для анализа характеристик QoS в мультисервисных сетях связи являются модели на основе теории массового обслуживания (ТМО). При моделировании современных пакетных сетей данные модели имеют ограничения. Основным ограничением ТМО при анализе последовательно соединенных узлов является предположение о том, что потоки пакетов и дисциплины их обслуживания в узлах сети чаще всего описываются Марковскими процессами, что позволяет анализировать пакетные сети для простейших моделей трафика и дисциплин обслуживания. К тому же большое количество исследований показывает, что трафик в мультисервисных сетях имеет гораздо более сложный характер, например, проявляет свойства самоподобия. Модели на основе ТМО позволяют определять средние значения характеристик QoS, что является еще одним существенным ограничением. При расчете средних значений происходит недооценка возможных пиковых значений характеристик QoS. В то же время, ведущая международная организация по стандартизации в области телекоммуникаций - сектор стандартизации телекоммуникаций Международного союза электросвязи (МСЭ-Т) в своих рекомендациях регламентирует граничные значения QoS в мультисервисных сетях на основе протокола IP. Например, в Рекомендации G.1010 указано, что задержка при двухсторонней голосовой связи в норме не должна превышать 150 мс, а максимальная задержка должна быть меньше 400 мс. Указанные недостатки ТМО преодолены в теории сетевого исчисления NC (Network Calculus) [2], которая позволяет определять граничные значения характеристик QoS пакетных сетей с использованием моделей потоков трафика и сетевых узлов, максимально близких к реальным. Основы теории сетевого исчисления Математический аппарат теории NC основан на идемпотентных и алгебрах [3-4]. В идемпотентной алгебре базовые операции классической алгебры заменяются на их идемпотентные аналоги: умножение становится сложением, а сложение становится операцией нахождения максимума или минимума. Например, в -алгебре эти операции представляются, как: , . -алгеброй называют полукольцо , -алгеброй называют полукольцо . Важными операциями в идемпотентной алгебре являются свертка и обратная свертка функций. Например, в -алгебре свертку и обратную свертку двух произвольных функций и можно представить, соответственно, как: , , где inf обозначает точную нижнюю грань функций и , а sup - точную верхнюю грань этих функций. Математический аппарат идемпотентных алгебр, лежащий в основе NC, позволяет нелинейные задачи классической алгебры сводить к линейным над соответствующими идемпотентными полукольцами. Рис. 1. Модель узла сети в теории NC Модель сетевого узла в терминах NC представлена на рис. 1. Пусть входящий в узел поток трафика характеризуется кумулятивной функцией поступления пакетов . Поток обслуженных пакетов на выходе узла характеризуется кумулятивной функцией . Основная идея теории NC состоит в том, что граничные значения характеристик QoS можно получить путем определения максимального горизонтального и вертикального расстояния между кривыми функций и . В частности, граница задержки d в любой момент времени t определяется как максимальное горизонтальное расстояние между и , что можно представить, как: , где множество неотрицательных чисел. Граничное значение загрузки (числа пакетов в системе) b в любой момент времени t определяется как максимальное вертикальное расстояние между кривыми и , что можно представить, как: . Для всего потока пакетов граничные значения задержки и загрузки определяются, соответственно, как: ; . Для вычисления граничных значений характеристик QoS необходимо задать законы распределения, описывающие поступающий поток пакетов и дисциплину его обслуживания в узле. Для этого в NC используются кривая поступления , описывающая входящий в узел поток трафика, и, кривая обслуживания , описывающая дисциплину обслуживания этого потока в узле. Функция будет являться кривой поступления для потока трафика на входе узла при условии, что для некоторого наблюдаемого периода времени выполняется следующее неравенство: . Функция является кривой обслуживания для узла сети при условии, что для некоторого наблюдаемого периода времени : , где выражение в квадратных скобках означает -свертку . Функция, описывающая поток трафика на выходе узла, может быть определена, как , (1) где ° - символ свертки. Таким образом, граничные значения задержки пакетов потока трафика и загрузки узла будут определяться, соответственно, как максимальные горизонтальное и вертикальное расстояния между кривыми и . В цепочке последовательно соединенных узлов поток на выходе одного узла является входящим потоком в следующий узел и определяется путем -свертки кривой входящего потока с кривой обслуживания узла. Благодаря этому NC позволяет последовательность из N узлов анализировать как один узел (см. рис. 2) путем свертки кривых обслуживания узлов, входящих в эту последовательность: . Таким образом, зная кривую поступления трафика в первый узел и кривые обслуживания каждого узла можно определить сквозные характеристики QoS для потоков, проходящих через такую последовательность узлов. Рис. 2. Свертка последовательности сетевых узлов в один узел Для определения граничных значений задержки основного потока при прохождении через узел конкурирующего потока (см. рис. 3) необходимо определить остаточную кривую обслуживания узла. Для этого случая в [5] была доказана следующая теорема. Теорема 1. Пусть узел без потерь обслуживает основной и конкурирующий потоки в порядке FIFO. Предположим, что пакеты поступают мгновенно, и узел гарантирует минимальную кривую обслуживания для суммы двух потоков. Пусть конкурирующий поток характеризуется кривой поступления . Определим семейство кривых обслуживания для основного потока: . Если для любого функция является в широком смысле возрастающей, то узел будет обслуживать основной поток c остаточной кривой обслуживания . Выражение обозначает ; множитель является индикаторной функцией. Рис.3. Узел сети с основным и конкурирующим потоками Кривая поступления и кривая обслуживания могут быть заданы детерминированными или вероятностными функциями, поэтому NC получила развитие по детерминистическому [5] и стохастическому [6] направлениям. Модель VPN на основе теории сетевого исчисления В основу модели VPN положена методология LUDB (Least Upper Delay Bound) [7], которая использует математический аппарат детерминистической теории NC и позволяет определять наименьшую верхнюю границу задержки для потока трафика, проходящего через последовательность сетевых узлов с учетом конкурирующих потоков. Рассмотрим модель узла сети c основным потоком VPN и одним конкурирующим потоком, подобную представленной на рис. 3. Кривую поступления основного потока и кривую поступления конкурирующего потока зададим функциями вида : , (2) где максимальный всплеск потока, постоянная скорость потока при условии, что , , где n - общее число потоков, входящих в узел. Кривую обслуживания узла зададим функцией вида: , (3) где R - постоянная скорость обслуживания узла, - фиксированная задержка обработки пакета в узле при условии, что и . Графическое изображение данных кривых поступления и обслуживания показано на рис. 4. Рис. 4. Кривая поступления и кривая обслуживания Остаточную кривую обслуживания узла определим, используя следствие из теоремы 1, доказанное в [8]. Следствие 1. Пусть будет псевдо-аффинной кривой, смещенной по оси x на расстояние D и состоящей из n сегментов при . Пусть при . Если узел характеризуется минимальной кривой обслуживания для агрегата основного и конкурирующего потоков, который обслуживается в порядке FIFO, а конкурирующий поток характеризуется кривой поступления , то семейство функций будет являться остаточной кривой обслуживания узла при обслуживании основного потока и определяться как , (4) где символ обозначает свертку, s - свободный параметр; ; ; ; ; ; На рис. 5 изображена остаточная кривая обслуживания сетевого узла при обслуживании основного потока VPN с учетом одного конкурирующего потока. Рис. 5. Остаточная кривая обслуживания узла при обслуживании основного потока VPN c учетом одного конкурирующего потока Таким образом, граница задержки основного потока VPN в сетевом узле с n конкурирующими потоками определяется, как . Рассмотрим модель последовательности узлов VPN. Пусть все потоки, проходящие через эту последовательность, характеризуются кривыми поступления вида (2), а все узлы характеризуются кривыми обслуживания вида (3). Каждый поток будем обозначать как при условии, что , где обозначает узел входа потока, - узел выхода потока, N - общее количество узлов в последовательности. Если пути конкурирующих потоков не пересекаются и (или) вложены друг в друга, то такие потоки будем называть вложенными, а соответствующую последовательность узлов будем называть вложенной. Пример вложенной последовательности узлов изображен на рис. 6а. Рис. 6: а) вложенная последовательность узлов VPN; б) алгоритм определения остаточной кривой обслуживания вложенной последовательности узлов В противном случае потоки и последовательности узлов будем называть невложенными. Пример невложенной последовательности узлов изображен на рис. 7а. Каждый поток во вложенной последовательности будем характеризовать уровнем вложенности, то есть количеством конкурирующих потоков, в которые он вложен. Предположим что в каждом узле последовательности из N узлов при сумма скоростей всех потоков не превышает скорости обслуживания узла: . (5) Рассмотрим алгоритм вычисления остаточной кривой обслуживания для вложенной последовательности узлов на примере последовательности, изображенной на рис. 6б. 1. Используя (4) определим остаточные кривые обслуживания в узлах 1 и 3, через которые проходят конкурирующие потоки, имеющие наибольший уровень вложенности (это потоки с кривыми поступления и ): , , где и свободные параметры, введенные при исключении потоков и . 2. Произведем преобразование узла 2 и 3 в один узел 2-3 путем свертки кривой обслуживания узла 2 и остаточной кривой обслуживания узла 3, через которые проходит поток : . 3. Используя (3), вычислим остаточную кривую обслуживания узла 2-3, исключив при этом поток : . 4. Произведем преобразование узлов 1 и 2-3 в один узел 1-2-3 и определим его остаточную кривую обслуживания: Граничное значение сквозной задержки для основного потока VPN, проходящего через последовательность из N, узлов будет определяться как: . (6) Выражение (6) является задачей кусочно-линейной оптимизации, решение которой подробно рассматривается в [9]. Рис. 7: а) невложенная последовательность узлов VPN; б-в) вложенные последовательности узлов VPN, полученные путем разрезания невложенных конкурирующих потоков Для определения граничного значения сквозной задержки основного потока VPN в не-вложенной последовательности узлов, изображенной на рис. 7а, воспользуемся методом, разработанным в [7]: - из невложенной последовательности узлов получим вложенную путем разрезания конкурирующих потоков VPN и ; - определим границу сквозной задержки основного потока VPN для последовательности узлов, полученной в результате разрезания потока - см. рис. 7б. Для этого воспользуемся алгоритмом, разработанным в [7]: а) определим общую кривую поступления потоков и в узле 2, которая равна общей кривой потока на выходе узла 1. Используя (1), получим ; б) используя (4), определим остаточную кривую обслуживания потока : ; в) определим кривую поступления потока , которая равна кривой потока на выходе узла 2. Используя (1), имеем: ; г) определим границу сквозной задержки используя метод вычисления границы задержки для вложенной последовательности узлов VPN, рассмотренный выше; - определим границу сквозной задержки основного потока VPN для последовательности узлов, полученной в результате разрезания потока (рис. 7в). Алгоритм аналогичен определению ; - определим границу сквозной задержки основного потока VPN в не-вложенной последовательности узлов: . Таким образом, граница задержки для невложенной последовательности из N узлов VPN будет определяться как . Для невложенных последовательностей, состоящих из большого числа узлов с большим количеством потоков, может быть большое множество мест разрезов. Определение оптимального числа мест разрезов для невложенных последовательностей узлов подробно рассмотрено в [8]. Результаты экспериментов Экспериментальное исследование модели VPN проводилось для вложенной последовательности узлов, представленной на рис. 8, и не-вложенной последовательности узлов, представленной на рис. 7а. Для проведения экспериментов использовалась программа DEBORAH [10], основанная на методологии LUDB. Рис. 8. Вложенная последовательность узлов Целью экспериментального исследования являлась оценка степени влияния конкурирующих потоков на границу задержки d основного потока VPN при различных значениях параметров кривых поступления потоков и параметров кривых обслуживания узлов. На рис. 9 представлена зависимость границы задержки d основного потока VPN от доли конкурирующих потоков при увеличении их всплесков во вложенной последовательности узлов (см. рис. 8). Рис. 9. Зависимость границы задержки основного потока VPN от доли конкурирующих потоков при увеличении размера их всплесков В данном эксперименте постоянная скорость обслуживания каждого узла R принималась равной 10 Мбит/с, задержка каждого узла мс, скорость основного потока VPN , скорости конкурирующих потоков с учетом ограничения (5). Величина максимального всплеска трафика основного потока VPN и , конкурирующих потоков рассчитывались как , и , что соответствует малой, средней и большой загрузкам узлов. Затем для каждого варианта загрузки узлов всплески потоков задавались в пропорции соответственно соотношению долей основного и конкурирующих потоков VPN как 1/1, 1/2, 1/3 и 1/4. В таблице 1 приведены значения максимальных всплесков потоков при загрузке узлов , которые использовались при проведении эксперимента. Таблица 1. Значения максимальных всплесков потоков при загрузке узлов Доли основного потока VPN / Доля конкурирующих потоков , Кбит , Кбит , Кбит 1/1 200 100 100 1/2 200 200 200 1/3 200 300 300 1/4 200 400 400 По результатам эксперимента установлено, что задержка основного потока VPN линейно возрастает при линейном росте параметра максимального всплеска конкурирующих потоков. При различной загрузке узлов увеличение размера всплесков конкурирующих потоков VPN в 2, 3 и 4 раза приводит к увеличению границы задержки d основного потока VPN, соответственно, на 50%, 100% и 150%. При фиксированных равных загрузках узлов и фиксированной доле конкурирующих потоков (например, и 1/1) увеличение размера всплесков конкурирующих потоков ведет к пропорциональному увеличению границы задержки d основного потока VPN. В эксперименте по исследованию зависимости границы задержки d основного потока VPN от доли конкурирующих потоков при увеличении скорости во вложенной последовательности узлов (см. рис. 8) всплески потоков задавались как = 100 Кбит и == 50 Кбит. Скорости основного и конкурирующих потоков (соответственно, , и ) задавались аналогично параметрам всплесков в предыдущем эксперименте, но с учетом ограничения (5). Скорости и задержки узлов задавались такими же, как и в предыдущем эксперименте. По результатам эксперимента установлено, что зависимость границы задержки d основного потока VPN от доли конкурирующих потоков при увеличении их скорости аналогична зависимости, представленной на рис. 9. Однако при различной загрузке узлов увеличение скорости конкурирующих потоков приводит к незначительному увеличению задержки d основного потока VPN. При загрузке каждого узла увеличение скорости конкурирующих потоков в 2, 3 и 4 раза приводит к увеличению границы задержки d основного потока VPN, соответственно, лишь на 1%, 2% и 4%; при загрузке - на 5,5%, 11% и 17%; при загрузке - на 10%, 20% и 31%. При фиксированных загрузках узлов и доле конкурирующих потоков увеличение скорости конкурирующих потоков ведет к незначительному увеличению границы задержки d основного потока VPN. Например, при загрузках узлов и доле конкурирующих потоков 1/4 увеличение скорости конкурирующих потоков на 10…20% приводит к увеличению границы задержки d основного потока на 0,4…0,9%, а при загрузке узлов и доле 1/4 граница задержка возрастает на 3,5 - 7%. На рис. 10 представлена зависимость границы задержки d основного потока VPN от задержки узлов вложенной последовательности (см. рис. 8) при доле основного и конкурирующих потоков 1/1. Рис. 10. Зависимость границы задержки основного потока VPN от задержки узла при доле основного и конкурирующих потоков 1/1 В данном эксперименте постоянная скорость обслуживания каждого узла R принималась равной 10 Мбит/с, скорости с учетом ограничения (5) и всплески основного и конкурирующих потоков VPN задавались в зависимости от загрузки узлов и соотношения их долей аналогично предыдущим экспериментам. По результатам эксперимента установлено, что при различной загрузке узлов и различных долях конкурирующих потоков зависимость границы задержки d основного потока от задержки узла является линейной, граница задержки d увеличивается пропорционально увеличению задержки узлов . На рис. 11 представлена зависимость границы задержки d основного потока VPN от скорости узлов R во вложенной последовательности (см. рис. 8) при доле основного и конкурирующих потоков 1/1. Скорости (с учетом ограничения (5)) и всплески основного и конкурирующих потоков задавались в зависимости от загрузки узлов и соотношения их долей аналогично предыдущим экспериментам. По результатам эксперимента установлено, что граница задержки d основного потока VPN убывает нелинейно при увеличении скорости узлов. Рис. 11. Зависимость границы задержки d основного потока VPN от скорости узлов R во вложенной последовательности при доле основного и конкурирующих потоков 1/1 Экспериментальное исследование не-вложенной последовательности узлов проводилось с использованием тех же входных данных, что и для вложенной последовательности узлов. Результаты экспериментов аналогичны. Это можно объяснить тем, что граница задержки d основного потока VPN вычислялась для двух вложенных последовательностей, полученных путем разрезания не-вложенных конкурирующих потоков VPN. Выводы Результаты проведенного экспериментального исследования модели VPN позволяют сформулировать следующие выводы. 1. Значительное влияние на границу задержки планируемого потока VPN будет оказывать размер максимального всплеска конкурирующих потоков и/или уровня вложенности конкурирующих потоков. Поэтому если планируемый поток VPN имеет большие всплески трафика, то из нескольких маршрутов более оптимальным для данного потока будет маршрут с меньшим числом конкурирующих потоков и (или) меньшими размерами их максимальных всплесков. 2. Если все доступные маршруты в сети будут иметь большое число конкурирующих потоков с большими размерами всплесков, то в этом случае для удовлетворения требований границ задержек дополнительных потоков трафика других VPN в случае больших всплесков необходимо повысить скорость обслуживания трафика в узлах. 3. Скорость поступления конкурирующих потоков оказывает незначительное влияние на задержку трафика планируемой VPN при небольших загрузках узлов. Однако при больших загрузках наиболее оптимальным будет маршрут, в котором конкурирующие потоки имеют наименьшие скорости поступления пакетов трафика. При этом, всегда должно соблюдаться ограничение (5). 4. Технологическая задержка обработки пакетов в сетевом узле (без учета ожидания пакетов в буферах) зависит от скорости работы соответствующего программного обеспечения этого узла. Однако в современных узлах связи технологическая задержка обработки пакетов в узлах является очень малой величиной, которая практически не влияет на общую задержку передачи трафика через узел. Заключение В статье предложена модель VPN на основе теории сетевого исчисления, позволяющая определять наименьшую верхнюю границу задержки потока планируемой VPN с учетом конкурирующих потоков на отдельных маршрутах, состоящих из последовательно соединенных узлов. На основе анализа результатов проведенного экспериментального исследования модели VPN установлено, что наибольшее влияние на границу задержки планируемой VPN будут оказывать всплески и уровень вложенности конкурирующих потоков трафика при средних и высоких загрузках сетевых узлов. Скорости конкурирующих потоков будут оказывать заметное влияние на границу задержки потока планируемой VPN при высоких загрузках узлов и большого уровня вложенности конкурирующих потоков на анализируемых маршрутах. Полученные в результате проведенных экспериментов выводы могут быть использованы операторами связи на практике при планировании услуг VPN. Предложенная модель VPN может быть использована при разработке специализированного программного пакета планирования услуг VPN, который позволит операторам связи эффективно использовать имеющиеся сетевые ресурсы и обеспечить гарантированное качество обслуживания.

About the authors

Andrey Aleksandrovich Lysikov

Povolzhskiy State University of Telecommunications and Informatics

Email: lysikov_inc@mail.ru

References

Supplementary files