Содержание к диссертации
Введение
Глава 1. Методы, протоколы и алгоритмы маршрутизации в современных IP сетях 9
1.1. Архитектура сети Интернет 9
1.2. Основные метрики динамических протоколов маршрутизации 11
1.3. Протоколы маршрутизации внутреннего шлюза 13
1.3.1. Протокол маршрутизации RIP 15
1.3.2. Протокол маршрутизации OSPF 17
1.4. Современные алгоритмы маршрутизации 20
1.4.1. Алгоритм маршрутизации на основе алгоритма Дейкстры 20
1.4.2. Алгоритм Суурбалле для поиска пары кратчайших независимых по рёбрам путей 23
1.4.3. Алгоритм Суурбалле для поиска пары кратчайших независимых по вершинам путей 26
1.4.4. Алгоритм многопутевой маршрутизации Шольмайера 27
1.4.5. Алгоритм многопутевой маршрутизации Райхерта 28
1.5. Основные типы сбоев в компьютерных сетях 32
1.6. Недостатки существующей IP маршрутизации 35
1.7. Постановка задачи 37
1.8. Выводы по первой главе 37
Глава 2. Графы маршрутизации 39
2.1. Моделирование маршрутизации на основе теории графов 39
2.2. Метод 02 многопутевой маршрутизации 41
2.3. Свойства топологий сетей совместимых с 02 многопутевой маршрутизацией 47
2.4. Алгоритм проверки совместимости топологий сетей с 02 многопутевой маршрутизацией 55
2.5. Алгоритм построения 02 совместимых топологий сетей 58
2.6. Выводы по второй главе 59
Глава 3. Алгоритмы многопутевой маршрутизации 60
3.1. Требования к 02 алгоритмам маршрутизации 60
3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе пошагового улучшения 61
3.3. Шаблонный подход построения многопутевой маршрутизации .. 63
3.3.1. Алгоритм построения графов многопутевой (02) маршрутизации на основе четырёх шаблонов 67
3.3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе шести шаблонов 74
3.4. Сравнение алгоритмов 78
3.5. Выводы по третьей главе 95
Глава 4. Пути практической реализации 02 многопутевой маршрутизации 97
4.1. Реализация механизма работы соединений-джокеров 98
4.2. Пакет программ для расчёта и анализа графов маршрутизации. 101
4.2.1. Программа для расчёта графов многопутевой маршрутизации 101
4.2.2. Программа для анализа графов многопутевой маршрутизации и топологий сетей 103
4.2.3. Программа для построения топологий сетей, совместимых с 02 многопутевой маршрутизацией 105
4.3. Выводы по четвёртой главе 106
Заключение 107
Список литературы 109
- Протокол маршрутизации OSPF
- Метод 02 многопутевой маршрутизации
- Шаблонный подход построения многопутевой маршрутизации
- Реализация механизма работы соединений-джокеров
Введение к работе
Актуальность проблемы. В настоящее время среди организаций, предлагающих сетевые услуги, существует жёсткая конкуренция. В этих условиях клиенты становятся особенно требовательными и ожидают высочайшего качества обслуживания, включая непрерывность обслуживания в течение всего оплаченного времени. Нарушение обслуживания вследствие сбоя в сети более не является допустимым, так как это может вызвать существенные потери прибыли в течение времени простоя. Подобные потери прибыли могут привести к негативной рекламе сетевого провайдера и к потере клиентуры.
Основными аспектами, необходимыми для успешной работы IP сети, являются выбор маршрута пакета и недопущение закупорки транспортных артерий. IP маршрутизация была разработана таким образом, чтобы восстановить маршрут передачи данных после практически любого отказа сетевых элементов. Однако современные реализации маршрутизации не могут сделать это в течение приемлемого интервала времени, так как реконфигурация сети может часто занять больше времени, чем десятые доли секунды, которые обычно являются приемлемым для пользователя интервалом времени. Задержки являются следствием недостаточно частых контрольных сообщений и того факта, что всегда определённое число сетевых узлов должно быть проинформировано о произошедшем сбое в сети, и эти узлы должны предпринять определённые контрмеры, для чего необходимо время. И хотя разрыв соединения на несколько секунд является абсолютно приемлемым для соединения компьютер - компьютер, это существенно ограничивает использование человеком существующих IP сетей для связи в режиме реального времени. В связи с этим
представляется актуальным разработка алгоритмов маршрутизации, обеспечивающих более надёжную передачу пакетов данных.
Таким образом, актуальность диссертационного исследования определяется тем, что современные средства IP маршрутизации не обеспечивают отказоустойчивой маршрутизации за допустимый интервал времени, что является сдерживающим фактором расширения использования IP сетей.
Цель и задачи работы. Целью данной работы является системный анализ процессов IP маршрутизации компьютерных сетей, разработка и обоснование многопутевой маршрутизации с целью повышения отказоустойчивости и эффективности использования имеющихся сетевых ресурсов. Для выполнения этой цели необходимо решить следующие задачи:
проанализировать известные методы многопутевой маршрутизации, а также свойства топологий компьютерных сетей, совместимых с многопутевой маршрутизацией;
разработать метод и алгоритмы многопутевой маршрутизации по адресу получателя, обеспечивающие повышение отказоустойчивости передачи IP пакетов по сравнению с предшествующими аналогами;
разработать критерии и алгоритм проверки совместимости топологии компьютерной сети с многопутевой маршрутизацией;
разработать алгоритм построения топологий компьютерных сетей, совместимых с многопутевой маршрутизацией;
проверить эффективность применения разработанного метода маршрутизации;
предложить способ практического использования созданных алгоритмов на базе современных протоколов маршрутизации.
Методы исследования. В ходе исследования были использованы подходы и методы теории графов, методы теории вероятности, комбинаторного анализа, системного и объектно-ориентированного анализа. В разработке программного обеспечения использовалась технология объектно-ориентированного программирования.
На защиту выносятся следующие результаты:
02 метод многопутевой маршрутизации по адресу получателя.
Шаблонные алгоритмы многопутевой маршрутизации на основе 4 и 6 шаблонов.
Метод принятия решения о совместимости топологии компьютерной сети с многопутевой (02) маршрутизацией.
Алгоритм построения топологий компьютерных сетей, совместимых с многопутевой (02) маршрутизацией.
Научная новизна:
Предложен 02 метод многопутевой маршрутизации по адресу получателя, позволяющий обеспечить применение многопутевой маршрутизации для максимально возможного числа узлов в заданной топологии сети.
Сформулирован шаблонный подход построения многопутевой маршрутизации. На основе этого подхода были разработаны алгоритмы многопутевой маршрутизации с применением 4 и 6 шаблонов, обеспечивающие более высокую отказоустойчивость маршрутизации и более равномерное распределение нагрузки на каналы связи по сравнению с предшествующими аналогами.
Разработан алгоритм для проверки совместимости топологии сети с многопутевой (02) маршрутизацией. Использование этого алгоритма позволяет быстро выявить недостатки топологии сети с точки зрения многопутевой маршрутизации.
4) Разработан алгоритм построения сетей, совместимых с многопутевой (02) маршрутизацией, который может быть использован при проектировании компьютерных сетей.
Обоснованность и достоверность научных положений, основных выводов и результатов диссертации обеспечивается за счет тщательного анализа состояния исследований в данной области и подтверждаются корректностью предложенных моделей, алгоритмов и согласованностью результатов, полученных при компьютерной реализации, апробацией основных теоретических положений диссертации в печатных трудах и докладах на международных научных конференциях, а также в патентном предложении.
Практическая ценность работы. Разработанные в диссертации способ и алгоритмы многопутевой маршрутизации предназначены для повышения отказоустойчивости компьютерных сетей (IP сетей) передачи данных. В случае отказа одного из сетевых элементов передача информации не будет приостановлена, что особенно важно для сетевых служб, работающих в режиме реального времени, как например Интернет-телефония (VoIP). Представленные алгоритмы могут заменить собой алгоритм поиска кратчайшего пути (алгоритм Дейкстры) в протоколах внутридоменной маршрутизации с учётом состояния канала.
Для оценки совместимости имеющихся сетей с многопутевой маршрутизацией могут быть использованы разработанные в диссертации геометрические критерии и основанный на них алгоритм проверки.
Для построения же новых компьютерных сетей, совместимых с многопутевой маршрутизацией, может быть использован алгоритм построения 02 совместимых сетей, представленный в данной работе.
Реализация результатов работы. Разработанные в рамках диссертации алгоритмы были реализованы в виде пакета программ для
расчёта и анализа многопутевой маршрутизации, а также анализа топологий компьютерных сетей. Данный пакет программ применяется СЦПС «Спектр», а также фирмой ОАО «Телекомпания Санкт-Петербургское кабельное телевидение», при проектировании новых и для анализа существующих каналов связи. Разработанные алгоритмы многопутевой маршрутизации были использованы Фраунхоферским институтом Открытых телекоммуникационных Систем Фокус в проекте KING, посвященном разработке компьютерных сетей следующего поколения. Разработанный метод многопутевой маршрутизации был оформлен в виде патентного предложения.
Апробации работы. Приведенные в диссертации результаты были представлены на VIII Санкт-Петербургской международной конференции "Региональная информатика 2002" (Санкт-Петербург, 25-28 ноября 2002), на III Санкт-Петербургской конференции «Информационная безопасность регионов России (ИБРР-2003)» (Санкт-Петербург, 25-27 ноября 2003), на «2003 IEEE Workshop on High Performance Switching and Routing» (Турин, Италия, 24-28 июня, 2003) и на «IPS-MoMe 2005» (Варшава, Польша, 14-17 марта 2005).
Публикации. Основные результаты диссертации опубликованы в 5 печатных работах.
Структура и объем работы. Диссертация содержит введение, четыре главы, заключение, список литературы (124 наименований); 12 таблиц и 41 рисунок (общий объем диссертации — 119 листов).
Протокол маршрутизации OSPF
Протокол OSPF (Open Shortest Path First) является протоколом маршрутизации с учётом состояния каналов. Он определён в документе RFC 1583 [78, 84]. В основе работы протокола OSPF лежит представление о множестве сетей, маршрутизаторов и линий связи в виде направленного графа, в котором каждой дуге поставлена в соответствие её цена. OSPF обеспечивает все маршрутизаторы сети полной информацией о топологии автономной системы. Каждый маршрутизатор может затем определить кратчайший маршрут (с точки зрения выбранной метрики) до каждого конечного пункта назначения и сохранить соответствующий IP адрес сетевого интерфейса для следующего шага в локальную таблицу маршрутизации. Алгоритм нахождения кратчайшего маршрута (Алгоритм Дейкстры), лежащий в основе этого протокола, автоматически гарантирует отсутствие циклов в маршрутизации, так как маршрут, содержащий цикл маршрутизации, не может быть короче другого маршрута без цикла.
При построении маршрутов протокол OSPF может использовать несколько метрик: ширину полосы пропускания, надёжность, нагрузку и задержку. Чаще всего OSPF использует лишь ширину полосы пропускания [31,92,113].
В обычном режиме работы, если существует несколько кратчайших маршрутов одинаковой стоимости, то обычно выбирается первый из них» но выбор непредсказуем, потому что использование различных реализаций алгоритма может приводить к различным результатам [85].
OSPF может также работать совместно с протоколом Equal-Cost Multi-Path (ЕСМР), который описан в стандарте IETF RFC 2992. Тогда если до пункта назначения имеется несколько маршрутов с одинаковой стоимостью, то маршрутизаторы могут использовать все эти маршруты. Балансировка нагрузки по ним происходит автоматически, а именно -трафик распределяется на равные доли. Если же маршруты имеют различную стоимость, то OSPF требует ручной настройки. ЕСМР чаще всего используется совместно протоколом маршрутизации OSPF, но многие современные маршрутизаторы поддерживают также совместную работу ЕСМР с другими протоколами маршрутизации, такими как RIP, BGP и IS-rS. Маршрутизаторы OSPF обмениваются с соседями приветственными сообщениями каждые 10 секунд. Маршрутизатор считает своего соседа вышедшим из строя, если не получет от него приветственного сообщения в течение четырёх интервалов, т.е. только после 40 секунд с момента отказа соседнего маршрутизатора.
После обнаружения разрывов соединений или появления новых маршрутов в сети маршрутизаторы быстро адаптируются к этим изменениям- Когда маршрутизатор обнаруживает разрыв соединения или новый канал, он сразу же генерирует сообщение о корректировке, инициируя лавинную рассылку, OSPF обладает многими преимуществами по сравнению с протоколами вектора состояния [112]. Например, OSPF использует многоадресную рассылку вместо широковещательной для распространения маршрутной информации среди соседних маршрутизаторов. Сообщения о корректировках посылаются, только если в сети происходят изменения, т.е. периодическая рассылка отсутствует, а все сообщения являются инициированными. Причём сообщения рассылаются всем маршрутизаторам OSPF (лавинная рассылка), что сокращает время сходимости. Каждое сообщение о корректировке включает в себя только изменение маршрутной информации, а не всю таблицу маршрутизации. Благодаря отсутствию ограничения на максимальное числом пересылок протокол OSPF способен работать в больших сетях. 1,4, Современные алгоритмы маршрутизации Для того, чтобы усовершенствовать существующие механизмы маршрутизации, необходимо рассмотреть их более подробно. Ниже приводятся ряд ниболее широко применяемых алгоритмов. Первый из них - это алгоритм Дейкстры [16, 48], лежащий в основе протокола OSPF и широко используемый в других алгоритмах маршрутизации. Два алгоритма Суурбалле предназначены для многопотоковой маршрутизации. Первый из них позволяет строить маршруты, независимые по рёбрам, а второй - по узлам. Особенностью этих двух алгоритмов является то, что они могут быть использованы только для маршрутизации с использованием адреса источника. Почти все существующие на данный момент алгоритмы многопутевой маршрутизации предназначены именно для этого типа маршрутизации, К сожалению, у маршрутизации с использованием адреса источника есть очень существенный недостаток, так как маршрутизатор должен анализировать ещё и адрес отправителя пакета, то это приводит к многократному увеличению таблиц маршрутизации. Следовательно, маршрутизация с учётом адреса источника малопригодна для больших сетей.
Метод 02 многопутевой маршрутизации
Если условие 2 выполняется, то для обработки отказов одиночных линий связи нет необходимости немедленно перерасчитывать все графы маршрутизации. Узлу, обнаружившему выход из строя одной из линий связи, достаточно будет перенаправить трафик на вторую исходящую линию связи по заранее просчитанному маршруту- Это подразумевает, что есть два или больше независимых по рёбрам пути между каждой парой различных узлов. Условие 2 называется 02 свойством. Узел х є V—{d}t для которого; toR (и) = /, т.е. 02 свойство для него не выполняется, называется 01 узлом.
Если условие 3 выполняется, то для обработки отказов одиночных узлов также достаточно реакции соседнего узла, обнаружившего этот сбой, по перенаправлению трафика по альтернативному, заранее просчитанному маршруту. Это подразумевает, что существуют два или более независимых по узлам путей между каждой парой различных узлов. Условие 3 называется SO свойством (граф маршрутизации не содержит разделительных узлов). Разделительный узел - это такой, удаление которого из графа разделяет граф на несколько частей. Такой узел называется также SO узлом, SO свойство подразумевает выполнение условий 1 и 2.
Условие 4 не позволяет использовать тривиальное решение, а именно - делать каждую связь джокером. Оно обосновывается тем, что дуги-джокеры, как уже было отмечено выше, используются для передачи трафика в качестве запасного исходящей линии связи только в том случае, если основная линия связи вышла из строя. Таким образом, для нормального режима работы каждый узел должен иметь хотя бы одну исходящую линию связи по направлению к адесату, которая не являлась бы дуто й-джокером. Так как дуги-джокеры по сути являются циклами, состоящими из двух ориентированных дуг, то примитивные алгоритмы поиска циклов в направленном графе всегда обнаружат их. Поэтому условие 5 разрешает использовать джокеры, но запрещает более длинные циклы, состоящие из трёх и более ориентированных дуг. Такие циклы могут также образовываться в результате использования джокеров, когда джокер используется вместо одной из неисправных линий связи. На Рис. 2.2 показан пример такой ситуации: использована дуга-джокер ху от х к у, таким образом образуя петлю xyzx Определение 23 (Топология сети совместимая с 02 многопутевой маршрутизацией) Топология сети N = (Vr Е) называется совместимой с 02 многопутееой маршрутизацией, если и только если для всех адресатов d є V существует многопутевая маршрутизация согласно определению 2.2. Таким образом, 02 метод многопутевой маршрутизации — это метод маршрутизации, основанный на применении 02 многопутевых графов маршрутизации, а именно; 1) Если для заданной топологии сети возможно построить 02 граф к заданному адресату, то этот граф используется в качестве графа маршрутизации. 2) Если для заданной топологии сети невозможно построить 02 граф к заданному адресату, то в качестве графа маршрутизации должен использоваться граф, максимально приближающийся своими свойствами к 02 графу маршрутизации. А именно, с минимальным числом 01 и SO узлов, а также с минимальным числом джокеров. В связи с этим особое значение приобретают алгоритмы построения 02 графов маршрутизации и максимально приближённых к ним, так как эффективность работы данного метода маршрутизации напрямую зависит от качества работы соответсвующих алгоритмов маршрутизации. Было разработано несколько таких алгоритмов, описанию которых посвящена третья глава данной работы. Представляется также очевидным, что не для каждой топологии сети можно построить 02 графы маршрутизации для всех адресатов. Соответственно, важно подробно изучить свойства, критерии, а такжи методы построения топологий компьютерных сетей, совместимых с 02 многопутевой маршрутизацией. Этому и посвящены остальные разделы данной главы, 2.3. Свойства топологий сетей совместимых с 02 многопутевой маршрутизацией Данный раздел посвящен описанию и обоснованию свойств топологий компьютерных сетей, совместимых с 02 многопутевой маршрутизацией. Описанные в данном разделе свойства используются для обоснования корректности работы разработанных алгоритмов. Утвервдение 2.2. Если N = (V, Е), содержащая узел d є V, это совместимая с 02 многопутевой маршрутизацией топология сети, то существуют также ие V и ve V, так что: du є Е, dv є Ef uv є E; т.е. в ТОПОЛОГИИ сети, совместимой с 02 маршрутизацией, каждый узел является вершиной треугольника. Обоснование. Так как N совместима с 02 маршрутизацией, то для V d є V можно построить 02 граф маршрутизации Rj = (V, Ег). Обозначим соседи узла d как U — {uj, U MJ, где п — это число узлов, имеющих общее ребро с d. Покажем правильность утверждения от противного. Предположим, что для Ь пары узлов иєі/и УЄІІНЄ существует (и, v) є Е\ т.е. узлы из множества U не имеют общих рёбер. Так как Rd это 02 граф маршрутизации, то он не содержит циклов, и все узлы, кроме df должны иметь два или более пути по направлению к узлу-адресату d. Каждый узел из множества U соединён напрямую с узлом-адресатом dt следовательно, каждый из узлов множества U должен обладать ещё одним путём к узлу d. Этот путь может проходить к узлу d только через какой-то другой узел множества U. Следовательно, каждый из п узлов множества U должен быть соединён с каким-то другим узлом множества U последовательностью ориентированных рёбер, что невозможно без образования цикла. Рис. 2.3 поясняет ситуацию. Как можно выдеть на рисунке, узел и„ не может построить второй маршрут до t/без образования цикла.
Шаблонный подход построения многопутевой маршрутизации
Результаты сравнения работы алгоритмов представленные в таблице 3.3, как и в случае с предыдущей топологией, демонстрируют превосходство алгоритмов PBRA4/PBRA6 над остальными алгоритмами.
Графы маршрутизации, построенные для данной топологии сети, содержат гораздо больше 01 и S0 узлов, чем графы маршрутизации, построенные для предыдущей топологии сети. Разница по сумме длин кратчайших путей для алгоритмов PBRA4/PBRA6 и модифицированного алгоритма ЕСМР также больше для данной топологии, чем для предыдущей. Она составляет 2,01%. Сравнение алгоритмов многопутевой маршрутизации для топологии сети Sprint 2001
Топология сети Sprint 2001 отображает её американский сектор по состоянию на 2001 год. Топология сети состоит из 18 узлов, соединённых 40 неориентированными рёбрами. Sprint 2001 несовместима с 02 маршрутизацией. Однако, как следует из таблицы 3.4, шаблонным алгоритмам почти удаётся построить 02 графы маршрутизации. В результате графы маршрутизации, построенные по шаблонным алгоритмам PBRA4/PBRA6, содержат в сумме всего 4 01 узла и не содержат S0 узлов, что неприминуло сказаться и на средней отказоустойчивости. Шаблонным алгоритмам, так же как и алгоритму Райхерта, удалось обеспечить стопроцентную отказоустойчивость на отказ одного из узлов. При этом по остальным показателям шаблонные алгоритмы значительно опережают алгоритм Райхерта.
Что касается результатов модифицированного алгоритма ЕСМР, то они уступают как результатам шаблонных алгоритмов, так и алгоритму Райхерта, Разница в длине кратчайших путей для модифицированного алгоритма ЕСМР и шаблонных алгоритмов составляет 3,94%. Сравнение алгоритмов многопутевой маршрутизации для топологии сети UUNET 1994
Сеть UUNET 1994 принадлежит одному из крупнейших американских Интернет провайдеров корпорации MCI WorldCom, Цифры «1994» в названии обозначают, что данная топология сети соответствует её состоянию на 1994 год. Топология сети состоит из 42 узлов и 79 неориентированных рёбер и тем самым является одной из самых крупных в этой главе. Данная топология сети несовместима с 02 маршрутизацией, что и отразилось на результате работы алгоритмов, представленном в таблице 3-5 Особенностью полученных результатов является то, что графы маршрутизации, построенные при помощи алгоритмов PBRA4 и PBRA6, различны. Алгоритму PBRA6 удалось добиться лучших результатов с точки зрения минимизации числа Ol и S0 узлов, используя при этом на семь дуг-джокеров больше, чем алгоритм PBRA4. Однако алгоритму PBRA6 не удаётся добиться большей средней отказоустойчивости, чем алгоритму PBRA4, как следует из таблицы 3,5. Более того, средняя отказоустойчивость графов маршрутизации, построенных при помощи алгоритма Райхерта, также выше средней отказоустойчивости графов, построенных при помощи алгоритма PBRA6. Модифицированный алгоритм ЕСМР так же как в предыдущих случаях строит наименее отказоустойчивые графы маршрутизации, но состоящие при этом из кратчайших путей. Наилучшим же алгоритмом маршрутизации для данной топологии сети с точки зрения отказоустойчивости является алгоритм PBRA4, который использует пути, кратчайшая длина которых больше аналогичных от модифицированного алгоритма ЕСМР на 5,5%. Сравнение алгоритмов многопутевой маршрутизации для топологии сети UUNET1997
Топология сети UUNET 1997 отображает состояние сети UUNET в 1997 году в её американской части. Топология сети состоит из 42 узлов и 80 неориентированных ребер. Данная топология сети несовместима с 02 маршрутизацией, так же как и её предшественница трёхлетней давности-Согласно полученным данным (см. таблицу 3.6) наиболее высокую отказоустойчивость для графов маршрутизации обеспечивает алгоритм PBRA4. Алгоритм PBRA6 уступил по этому критерию алгоритму Райхерта. Отсюда, принимая во внимание более высокую сложность алгоритма PBRA6 по сравнению со сложностью алгоритма PBRA4, можно сделать вывод о нецелесообразности использования алгоритма PBRA6, Не смотря на то, что алгоритм PBRA6 использует наименьшее число 01 и SO узлов в графах маршрутизации, это не приводит к повышению средней отказоустойчивости, так как на отказоустойчивость графа маршрутизации отказывает влияние не только число 01 и SO узлов, но и их расположение в графе маршрутизации. Сравнение алгоритмов многопутевой маршрутизации для топологии сети WorldCom Europe
Сеть Worldcom Europe является европейским сегментом сети компании WorldCom, Сеть состоит из 19 узлов, соединённых 41 неориентированной дугой. Топология сети совместима с 02 маршрутизацией, более того, для данной топологии можно построить 02 граф маршрутизации для любого узла-адресата, содержащий не более 1 джокера. Именно на таких топологиях шаблонные алгоритмы особенно хорошо проявляют себя (см. таблицу 3.7).
Реализация механизма работы соединений-джокеров
Проблема, однако, остаётся, когда оба узла джокера пытаются одновременно использовать его. Такая ситуация возникает, когда независимые маршруты, ведущие от обоих узлов джокера к узлу-адресату, одновременно выходят из строя. После этого оба узла отправят трафик, предназначенный теперь недостижимому узлу-адресату по направлению друг к другу, заполняя соединение пакетами и образуя цикл маршрутизации, как показано на Рис. 4.1. Это приводит к следующему:
Пропускная способность линии связи будет израсходована и линия связи становится фактически непригодной для доставки трафика другим адресатам. В процесс многократных пересылок зацикленных пакетов их TTL в конце концов опустится до нуля, и в конце концов пакеты будут уничтожены. Маршрутизатор, уничтожая пакет, должен будет послать назад отправителю специальное сообщение (ICMP Time Exceeded). Не смотря на то, что RFC1812 рекомендует ограничить норму частоты посылки ICMP сообщений, оконечные узлы джокера, как правило, генерируют поток ICMP сообщений. Этот может занять значительную часть полосы пропускания. Приводимая ниже простая модификация процедуры передачи решает эту проблему: Если входящий интерфейс, через который был принят пакет, является тем же интерфейсом, через который предполагается послать его далее по направлению к адресату, и этот интерфейс — это часть джокера в графе маршрутизации по направлению к адресату, тогда пакет должен быть уничтожен. Реализация второго режима работы соединения-джокера, а именно, когда соединение-джокер может использоваться как обычное соединение, может быть осуществлена по сходной схеме. Но с той разницей, что имя входящего интерфейса, через который был получен пакет, должно использоваться при выборе маршрута до цели: 1, Исходящий интерфейс для отправки пакета по направлению к адресату не может быть тем же, что и тот, через который данный пакет был получен. 2. Если же пакет может быть отправлен по направлению к адресату только через тот же сетевой интерфейс, через который он был получен, то пакет должен быть уничтожен. Данный подход, не смотря на внешнее сходство, принципиально отличается от подхода, предложенного для реализации режима работы дуги-джокера в качестве запасного соединения. Так как использование имени входящего сетевого интерфейса на данный момент не практикуется для выбора следующей пересылки из таблицы маршрутизации, т.е. это нестандартная операция, требующая изменения программного обеспечения маршрутизаторов, что затрудняет реализацию этого подхода. Однако необходимо отметить, что данная модификация не приводит к увелчению размеров таблиц маршрутизации, а также не приводит к серьёзному замедлению поиска в этих таблицах. Таким образом, данная модификация процедур маршрутизации и передачи пакетов позволяет использовать соединение-джокер в обоих направлениях даже в маршрутах к одному и тому же получателю, обеспечивая тем самым дополнительные возможности для распределения трафика. 4.2. Пакет программ для расчёта и анализа графов маршрутизации Данный пакет программ предназначен для анализа и построения топологий компьютерных сетей и графов маршрутизации. Программы реализованы на языке C++. Их компиляция может быть осуществлена при помощи свободно распространяемого компилятора gcc-2.95.3 Программа ygl_routing является программной реализацией рассматриваемых алгоритмов многопутевой маршрутизации.
