REDUNDANCY OPTIMIZATION FOR PACKET-SWITCHED NETWORKS

Full Text

Введение Одной из основных задач при эксплуатации сетей с коммутацией пакетов является обеспечение их бесперебойной работы, поскольку отказы могут приводить к весьма значительным финансовым и репутационным потерям. С целью повышения отказоустойчивости работы пакетных производится резервирование соединительных линий и коммутационного оборудования, это требует вложения значительных средств. Для обеспечения резервирования за длительный период развития пакетных сетей было предложено множество различных технологий резервирования, которые были разработаны такими организациями как IEEE, IETF и компаниями Cisco, Juniper, DEC, HP и др. Наиболее широкое развитие получили такие протоколы обеспечения отказоустойчивости как STP, RSTP, PVST и MST. В основе большинства данных технологий лежит использование остовных деревьев графов для определения беспетлевых путей передачи пакетов в коммутируемой сети [1-2]. Главными недостатками использования остовных деревьев для передачи пакетов являются [2-4]: - низкая эффективность использования ресурсов сети, поскольку для передачи пакетов используется единственный путь, а пропускная способность альтернативных путей никак не задействуется; - в общем случае неоптимальная маршрутизация пакетов по сети, поскольку кратчайшие пути между коммутаторами определяются только относительно одного корневого коммутатора. Для устранения перечисленных недостатков предлагается ряд решений для повышения эффективности резервирования пакетных сетей с целью увеличения использования их ресурсов. Использование неэквивалентных остовных деревьев для определения путей передачи пакетов Как было уже отмечено, в большинстве современных технологий резервирования для определения путей передачи пакетов используются остовные деревья графов. Остовное (покрывающее) дерево представляет собой ациклический связный подграф данного связанного неориентированного графа, в который входят все его вершины [5-6]. Остовные деревья обладают следующими свойствами: - для любых двух вершин существует единственный соединяющий их простой путь; - граф дерева перестает быть связным, если удалить любое его ребро; - граф дерева является ациклическим, но добавление любого ребра к нему порождает цикл В общем случае заданный граф может содержать множество остовных деревьев. В наиболее распространенных технологиях резервирования, таких как STP, RSTP и PVST, для определения путей передачи пакетов используются деревья кратчайших путей (ДКП). Каждое ДКП представляет собой остовное дерево, такое что путь от вершины-корня до любой другой вершины является кратчайшим путем между этими вершинами [5-8]. Для построения ДКП в заданных графах наиболее часто применяют алгоритмы Беллмана-Форда и Дейкстры. Алгоритмы Беллмана-Форда имеет более простую реализацию, однако алгоритм Дейкстры является одним из наиболее быстрых алгоритмов построения остовных деревьев и поэтому более предпочтителен для применения в современных сетях [7]. Низкая эффективность традиционных технологий резервирования связана с тем, что для передачи пакетов используется только один путь, который рассчитывается с использованием одного остовного дерева, построенного относительно одного корневого коммутатора. Для повышения эффективности разработаны технологии, основанные на маршрутизации пакетов по сети (TRILL), а также использования нескольких эквивалентных (с одинаковой стоимостью) остовных деревьев (SPB). Основным недостатками первого подхода являются сложность реализации, высокие требования к сетевому оборудованию и несовместимость с традиционными технологиями резервирования. Второй способ повышения эффективности может совместно использоваться с традиционными протоколами, однако, в общем случае, заданный граф сети может не иметь нескольких эквивалентных остовных деревьев, что ограничивает область применения данного способа. В связи с выше сказанным, представляется перспективным использования неэквивалентных остовных деревьев для определения путей передачи пакетов, поскольку данный подход будет иметь наибольшую область применения [2-4]. Рассмотрим наиболее общие моменты, которые могут повлиять на определения путей передачи пакетов в коммутируемых сетях: - для отказоустойчивости сети необходимо иметь несколько путей передачи пакета от узла-источника к узлу назначения (конечным узлам); - общая скорость передачи пакетов от одного конечного узла к другому может делиться между несколькими путями; - помимо конечных узлов, в сетях могут быть узлы, задачей которых является только перенаправление пакетов между конечными узлами, так называемые транзитные узлы; - часть путей передачи пакетов может быть либо недоступной, либо нежелательной для использования, например, с точки зрения безопасности. Общая рекомендация при проектирование пакетных сетей заключается в максимальном использовании пропускной способности и ресурсов транзитных узлов, поскольку на конечные узлы, во-первых, возлагается задача обработки пользовательского трафика, а во-вторых их использование для транзитной передачи может быть либо невозможным, в том случае, если они находятся под контролем другой организации, либо представлять угрозу для конфиденциальности транзитного трафика. Поскольку при использовании остовных деревьев большая часть трафика передается через корневой коммутатор, то наиболее целесообразным представляется использования в качестве корневых транзитных коммутаторов данной сети. Рассмотрим расчет путей передачи пакетов при помощи остовных деревьев в сети, представленной на рис. 1, где коммутаторы S0, S1, S2 и S3 составляют ядро сети, не генерируют трафик и таким образом представляют собой транзитные узлы. Коммутаторы S4, S5, S6 и S7 являются коммутаторами уровня распределения для пользовательских сегментов сети, они генерируют и обрабатывают пользовательский трафик и таким образом являются конечными узлами. Также на рис. 1 приведена условная стоимость отдельных линий, соединяющих коммутаторы. Рис. 1. Пример коммутируемой сети Используя алгоритм Дейкстры мы получим остовное ДКП, представленное на рис. 2, при использовании транзитного коммутатора S0 в качестве корневого. Рис. 2. Остовное дерево коммутатора S0 Для данного остовного дерева, путь между конечными коммутаторами S4 и S5 будет проходить через транзитные коммутаторы S0 и S3, и будет представлять последовательность S4-S0-S3-S5. Путь между коммутаторами S5 и S7 можно представить в виде последовательности S5-S3-S0-S7. Для других пар конечных коммутаторов пути могут быть представлены аналогичным образом. Для реализации предложенного способа определения путей передачи пакетов была разработана программа на языке программирования Python. Рассчитанные пути для графа сети, представленного на рис. 1, приведены в таблице 1. Таблица 1. Пути передачи пакетов Коммутаторы Путь S4-S5 1) S4-S0-S3-S5 2) S4-S1-S5 3) S4-S0-S2-S1-S5 4) S4-S1-S3-S5 S4-S6 1) S4-S0-S2-S6 2) S4-S1-S3-S6 S4-S7 1) S4-S0-S7 2) S4-S1-S2-S7 3) S4-S0-S2-S7 4) S4-S1-S3-S0-S7 S5-S6 1) S5-S3-S0-S2-S6 2) S5-S1-S3-S6 3) S5-S1-S2-S6 4) S5-S3-S6 S5-S7 1) S5-S3-S0-S7 2) S5-S1-S2-S7 S6-S7 1) S6-S2-S0-S7 2) S6-S3-S1-S2-S7 3) S6-S2-S7 4) S6-S3-S0-S7 Оптимизация сетевого трафика при резервировании Получения оптимальных потоков трафика в сети относится к известному классу задач оптимального распределения мультипродуктовых потоков (multi-commodity flow problem) между узлами-источниками и узлами-поглотителями в транспортной (потоковой) сети (flow network). Применительно к телекоммуникационным сетям данная задача может быть сформулирована следующим образом. Пусть задан ориентированный граф сети G, состоящий из V-вершин (узлов) и Е-ребер (соединительных линий). Между парами узлов данного графа необходимо передать D-потоков трафика величиной hd. Для каждой линии задается переменная xed, которая определяет ту часть hd для требования d, которая будет передаваться по линии е. Переменные для входящих в сетевой узел потоков будут являться положительными, а переменные для исходящих потоков будут отрицательными. Для узла-источника сумма всех потоков должна быть равна по величине hd. Для узла, на котором данный поток заканчивается, сумма переменных должна быть равна -hd, для остальных узлов (транзитных), не относящихся ни к источникам, ни конечным узлам, сумма всех переменных для потоков должна быть равна нулю [9]. В обобщенном виде данное ограничение носит название правила сохранения потоков [9]: (1) где aev = 1 когда линия e является исходящей из узла v, 0 в противном случае; bev = 1, если линия e заканчивается на узле v, 0 в противном случае; sd - узел-источник для требования d; td - конечный узел для требования d; e обозначает соединительные линии (ребра графа), е = 1, 2, 3, ... Е; d - номер потока трафика между парой узлов, d = 1, 2, 3, ... D. Кроме правила сохранения потоков необходимо также, чтобы общая сумма долей всех потоков на данной линии не превышала ее пропускной способности [6]: (2) Для решения задачи распределения мультипродуктовых потоков необходимо найти переменные, которые, во-первых, удовлетворяли бы всем выше представленным ограничениям, а во-вторых отвечали бы дополнительному критерию оптимальности. В качестве, которого, наиболее часто при оптимизации сетей используется минимизация общей стоимости пропускной способности используемых линий [6]: (3) где ξe - стоимость использования единицы пропускной способности линии e; уе - используемая пропускная способность линии e за счет передачи всех потоков. Задача распределения мультипродуктовых потоков, выраженная при помощи (1)-(3) применима только к ориентированным сетевым графам и неявно подразумевает использование всех возможных путей передачи трафика по сети между узлом-источником и узлом-окончанием для заданного потока. Для практических задач такая формулировка не всегда является удобной, поскольку часть путей в сети может быть по каким-либо причинам недоступной или нежелательной для использования. В этом случае необходимо введение дополнительных условий, которые каким-либо образом ограничивают использование части путей. Альтернативой формой задачи распределения потоков является использование формулировки явно выраженной через пути передачи между узлами. В ней переменная - это часть потока, приписанная для заранее определенного пути между узлами, для которых определен общий поток. Соответственно xdp - доля потока d, приписанная к пути p. В такой формулировке правило сохранения потоков (1) меняется на условие [9]: (4) где p = 1, 2, 3, ..., P - номер пути, реализующего поток d. Ограничение для пропускной способности линий при данной формулировки имеет вид: (5) где δepd = 1 в том случае, если линия e является частью пути p для потока d. При выражении потоков через пути их передачи предполагается симметрия исходящего и входящего потоков в обоих направлениях, что позволяет использовать данную формулировку для неориентированных графов. В связи с этим переменные, реализующие потоки, должны быть неотрицательными по величине, что вводит дополнительное ограничение: xdp ≥ 0. Для решения задачи распределения потоков, выраженной посредством (4)-(5), необходимо на первом этапе получить набор путей для реализации передачи потоков между конечными узлами, а затем найти решение в виде вектора x = (x1, x2, ..., xD), распределяющего потоки по заданным путям [9]. Поскольку для оптимизации резервирования в пакетных сетях предполагается вначале определить пути передачи трафика между узлами, то формулировка задачи оптимизации посредством путей представляется наиболее удобной для использования с целью повышении эффективности технологии резервирования. Задача оптимального распределения мультипродуктовых потоков при резервировании представляет собой систему линейных уравнений и неравенств, и поэтому может быть решена методами линейного программирования. Одним из основных алгоритмов решения задач линейного программирования является симплекс-метод, основанный на переборе базисных решений, который был предложен Г. Данцигом в 1947 году. Алгоритм начинает с некоторого базисного решения и пытается улучшить значение целевой функции, путем замены одной базисной переменной на другую. Алгоритм завершается, если значение целевой функции является оптимальным при данных ограничениях. В общем случае симплекс-метод позволяет решить задачу за полиномиальное время, однако при использовании специальных методов подбора начальных значений время работы данного алгоритма может быть значительно ускорено [7; 9]. Для решения задач линейного программирования было разработано большое число программного обеспечения (ПО). К наиболее известным относятся такие пакеты как lpsolve, CPLEX, Gurobi, XPRESS, Optimization Toolbox для MATLAB [9]. Методика оптимизации резервирования в пакетных сетях Для оптимизации технологии резервирования в коммутируемых пакетных сетях предлагается методика, которую можно представить в виде последовательности следующих действий. 1. На основе общих требований к сети или путем сбора статистики определяются требования по передаче трафика между оконечными коммутаторами. 2. На основе множества неэквивалентных остовных деревьев кратчайших путей рассчитываются все доступные пути между оконечными коммутаторами, агрегирующими пользовательский трафик. 3. Подбирается критерий оптимальности и при помощи какого-либо пакета оптимизационных программ рассчитываются величины потоков трафика для доступных путей между оконечными коммутаторами. 4. На основе значений переменных для найденного оптимума производится конфигурация сетевого оборудования, на котором должны работать усовершенствованные протоколы резервирования. 5. В том случае, если оптимальное решение не найдено, рассматривается возможность внесения изменений в топологию сети или замена оборудования на более производительное. После внесения изменений повторяются действия 2-5. В качестве примера практической реализации предложенной методики оптимизации технологии резервирования рассмотрим сеть, представленную на рис. 3. Рассматриваемая сеть состоит из восьми коммутаторов, из которых коммутаторы S0-S3 являются транзитными, а коммутаторы S4-S7 представляют собой оконечные коммутаторы. Пропускная способность соединительный линий, выраженная условно в Гбит/c, указана на рис. 3. Стоимость линий при расчете деревьев кратчайших путей указана на рис. 1. Рис. 3. Пример оптимизируемой сети Имена переменных, соответствующих формулировке (3)-(5) и критерия оптимальности (2), задаются в виде: X_(коммутатор 1)_(коммутатор 2)_(номер пути). Поскольку в рассматриваемом примере число узлов и линий в сети небольшое, и соответственно число переменных будет невелико, то для решения данной задачи предлагается использовать свободный пакет оптимизации lpsolve. Полученное решение представлено в таблице 2. Таблица 2. Решение для примера реализации предложенной методики оптимизации технологии резервирования Переменная Скорость потока, Гбит/c X_S4_S5_P1 3,0 X_S4_S5_P2 7,0 X_S4_S5_P3 0 X_S4_S5_P4 0 X_S4_S6_P1 4,0 X_S4_S6_P2 3,0 X_S4_S7_P1 3,0 X_S4_S7_P2 0 X_S4_S7_P3 0 X_S4_S7_P4 0 X_S5_S6_P1 0 X_S5_S6_P2 0 X_S5_S6_P3 0 X_S5_S6_P4 6,0 X_S5_S7_P1 1,0 X_S5_S7_P2 3,0 X_S6_S7_P1 0 X_S6_S7_P2 0 X_S6_S7_P3 6,0 X_S6_S7_P4 0 Из представленных в таблице 2 данных можно заключить, что для достижения минимальной стоимости, необходимо разделить требуемый трафик 10 Гбит/c между коммутаторами S4 и S5 на два потока: первый поток со скоростью 3 Гбит/c направить по пути с номером 0, а второй со скоростью 7 Гбит/c по пути с номером 1. Трафик между коммутаторами S4 и S6 7 Гбит/c необходимо также разделить на два потока: первый со скоростью 4 Гбит/c направить по пути с номером 0, а второй поток со скоростью 3 Гбит/c направить по пути 1. Весь трафик между коммутаторами S4 и S7 со скоростью 3 Гбит/c необходимо направить по пути 0. Весь трафик между коммутаторами S5 и S6 необходимо направить по пути 3. Трафик между коммутаторами S5 и S6 должен быть разделен на два потока в 1 Гбит/с (путь 0) и 3 Гбит/с (путь 1). Весь трафик между коммутаторами S4 и S7 должен быть направлен по пути 2. Заключение Предложена методика оптимизации резервирования в пакетных сетях, основанная на использовании неэквивалентных остовных деревьев графов для определения путей передачи пакетов, а также оптимизации передаваемого трафика. Полученные результаты могут быть использованы при разработке перспективных протоколов резервирования.

About the authors

Alexander Victotovich Troshin

Povolzhsky State University of Telecommunication and Informatics

Email: a.v.troshin77@yandex.ru

References

Supplementary files