9.4.Постановка задачи
При проектировании современных IP-сети принимаются меры для повышения их отказоустойчивости. Используются приёмы создания запасных каналов связи: дублирование связей, топологические кольца, утолщённые деревья. Если представить такую сеть в виде графа связности узлов (см. Приложение 1), то в нём обнаружится множество циклов. Это означает, что во многих случаях данные от источника к получателю могут быть переданы по альтернативному маршруту, минимально пересекающемуся по узлам и рёбрам графа с определённым сетью стандартным маршрутом передачи данных.
В протоколе IP заложена возможность передачи данных по нестандартным маршрутам. Для этого в заголовке IP-пакета можно указать специальную опцию маршрутизации от источника в виде списка IP-адресов маршрутизаторов сети, через которые данный пакет должен пересылаться при доставке адресату.
Одновременная передача данных по стандартному и альтернативным маршрутам позволит снизить нагрузку на стандартный маршрут передачи данных и повысить пропускную способность соединения с адресатом. Особенно выигрышным, в смысле повышения пропускной способности соединения, такой подход окажется в случае перегрузки каналов стандартного маршрута передачи данных.
Для реализации описанного подхода необходимо обладать знанием о наличии связности маршрутизаторов в используемых сетях (топологии сетей), уметь находить в графах связей альтернативные маршруты передачи данных, распределять данные между найденными маршрутами и передавать данные по нестандартным, в смысле правил маршрутизации, маршрутам.
В рамках дипломной работы решение задачи повышения пропускной способности соединений с заданными пользователями путём одновременного использования нескольких каналов передачи данных было разбито на подзадачи:
10.Разработать алгоритм определения связности узлов IP-сети в заданном направлении.
11.Разработать алгоритм поиска и выбора альтернативных маршрутов передачи данных в заданном направлении.
12.Создать программную реализацию способа динамического определения маршрутов движения трафика на основе разработанных алгоритмов и опций маршрутизации от источника протокола IP.
13.Провести эксперимент по оценке эффективности передачи данных с использованием разработанной программной реализации.
14.Решение 14.1.Описание подхода
Повышение пропускной способности сетевого соединения между двумя процессами, передающими данные по перегруженному каналу, достигается за счёт переноса части сетевой нагрузки с основного канала на обнаруженные в сети дополнительные.
Во время работы программы в направлении каждого целевого узла сети, с которыми ведётся обмен данными, происходит определение и сохранение топологии сети в виде графов. На графах выполняется поиск возможных маршрутов передачи данных. Среди обнаруженных маршрутов выбирается заранее определённое количество оптимальных, поочерёдно используемых для обмена данными с целевым узлом сети.
14.1.1.Алгоритм определения топологии сети
Заголовок IP-пакета имеет поле времени жизни TTL (Time To Live), хранящее максимальное допустимое количество пересылок данного пакета при доставке адресату. Каждый узел, получающий IP-пакет, уменьшает значение этого поля на единицу и пересылает пакет дальше. Если же время жизни становится равным нулю, то такой пакет отвергается, и, как правило, отправителю высылается ICMP [5] ответ об истечении времени жизни передаваемого пакета.
Для определения связности узлов сети используется так называемый подход трассировки маршрутов, основывающийся на отправке целевым узлам IP-пакетов с различными значениями времени жизни.
14.1.2.Трассировка маршрутов
Алгоритм отправляет целевому узлу IP-пакеты, последовательно увеличивая их время жизни (начиная с единицы). Отправив пакет со временем жизни N, алгоритм ожидает ICMP-ответа от N-го маршрутизатора в цепочке, передающей исходный пакет. По последовательности полученных ответов он строит эмпирическое представление о последовательности маршрутизаторов доставляющих пакет целевому узлу.
К сожалению, ICMP-ответы приходят не всегда, что мешает процессу трассировки. При разработке алгоритма трассировки были выделены три характерных типа возникающих нештатных ситуаций, связанных с отсутствием ICMP-ответа, и способов борьбы с ними:
Ответный ICMP-пакет был отправлен, но по неизвестным причинам не дошел до нас
На этот случай пакет переотправляется повторно заранее определённое фиксированное количество раз.
Промежуточный узел не отвечает или фильтрует запросы, приходящие на указанный порт
Отправляется второй пакет на другой порт. При получении непрерывной последовательности из заранее определённого фиксированного количества не ответивших хостов трассировка маршрута завершается.
Пакет начинает ходить по кругу
Трассировка маршрута заканчивается, последовательность выписывается в лог и не обрабатывается.
Из-за задержек сети возможна ситуация получения ICMP-ответов не в хронологическом порядке их отправления, что в свою очередь ведёт к построению неверного маршрута. Для исключения возможности таких событий все пакеты отправляются последовательно с заранее определённой фиксированной задержкой.
Также алгоритм трассировки позволяет определять маршруты доставки данных целевым узлам через произвольные промежуточные узлы сети путём добавления к отправляемым IP-пакетам опций маршрутизации от источника.
14.1.3.Построение графов связности узлов сети и автономных систем
Алгоритм строит графы связности узлов (IP-граф) и автономных систем (BGP-граф) сети на основе результатов трассировки целевых узлов через сторонние узлы сети. В зависимости от настройки, алгоритм может выполнять поиск маршрутов как внутри автономной системы, когда сторонние узлы выбираются случайно из диапазона IP-адресов автономной системы отправителя, так и вне её, когда сторонние узлы выбираются случайно из диапазона допустимых IP-адресов.
Из получаемых при трассировке маршрутов исключаются не ответившие узлы, а оставшиеся последовательности IP-адресов добавляются в IP-граф. Затем происходит разыменование IP-адресов в номера автономных систем и пополнение BGP-графа.
Для хранения каждого из IP и BGP графов связности узлов сети используются хэш-таблицы, сопоставляющие каждой вершине графа список смежных с ней, позволяющие быстро проводить проверку наличия вершины в графе и добавлять в него новые связи.
14.1.4.Поиск возможных маршрутов
Алгоритм поиска маршрутов опеделяет на графе набор путей, связывающих две заданные вершины (отправителя и получателя). Он представляет собой модификацию алгоритма двунаправленного поиска и выполняется в два этапа.
На первом этапе для отправителя и получателя итеративно строятся множества вершин, достижимых за N переходов по рёбрам графа. Изначально N = 0 и каждое из двух множеств состоит из одной вершины: отправителя или получателя. Затем на каждой итерации N увеличивается на единицу и множество пополняется вершинами, смежными с уже содержащимися в нём. Для каждой добавляемой в множество на шаге N+1 вершины сохраняется предшествующая смежная с ней вершина из множества шага N. Увеличение N происходит до тех пор, пока множества отправителя и получателя не перестанут расти или не начнут пересекаться больше, чем по заранее определённому количеству элементов.
На втором этапе, на основе сохранённого отображения предшествования вершин, для каждой вершины из пересечения множеств происходит восстановление пути, по которому она связана с отправителем и получателем.
В зависимости от настройки, алгоритм может выполнять как простой поиск путей на всём IP-графе, так и поиск путей на ограниченном наборе допустимых вершин. В качестве такого набора используется объединение диапазонов IP-адресов автономных систем, входящих в найденные при поиске на BGP-графе путей между автономными системами отправителя и получателя.
14.1.5.Определение оптимальных маршрутов
Для передачи данных из множества найденных алгоритмом поиска возможных маршрутов требуется выбрать определённое количество лучших. Необходимо, чтобы выбранные маршруты, по возможности, не имели общих каналов передачи данных, чтобы минимизировать возможность их перегрузки.
Процесс перебора и оценки оптимальности всех возможных подмножеств множества найденных маршрутов довольно трудоёмок для частого выполнения во время работы программы. Чтобы его избежать, было решено составлять набор маршрутов из стандартного, определяемого сетью, и альтернативных, по возможности, минимально пересекающихся со стандартным, маршрутов. Также при выборе маршрутов было решено отдавать предпочтение более коротким маршрутам, как потенциально более производительным.
При выборе альтернативных маршрутов производилось их упорядочение по значению специальной функции характеристики, отражающей долю совпавших рёбер альтернативного и стандартного маршрутов и длину альтернативного маршрута. Для её вычисления определялось количество совпавших рёбер С, количество уникальных рёбер у основного маршрута A и количество уникальных рёбер у альтернативного маршрута B. Характеристика альтернативного маршрута вычислялась по формуле 1.
Формула расчёта характеристики маршрута
Дробь  характеризует долю рёбер стандартного маршрута, присутствующих в альтернативном. Чем меньше это значение, тем больше отличается альтернативный маршрут от стандартного и тем он лучше. Член  является длиной альтернативного маршрута. Чем она меньше, тем короче маршрут.
Среди найденных маршрутов выбиралось заранее определённое фиксированное число маршрутов с наименьшим значением характеристики, которые затем использовались для передачи данных.
|
