автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка метода и алгоритмов многопутевой маршрутизации для повышения отказоустойчивости IP сетей

На правах рукописи

ГЛИКМАН Юрий Константинович

РАЗРАБОТКА МЕТОДА И АЛГОРИТМОВ МНОГОПУТЕВОЙ МАРШРУТИЗАЦИИ ДЛЯ ПОВЫШЕНИЯ ОТКАЗОУСТОЙЧИВОСТИ 1Р

СЕТЕЙ

Специальность 05.13.01. - Системный анализ, управление и обработка информации (технические системы)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2005

Работа выполнена в Санкт-Петербургском институте информатики и автоматизации Российской академии наук.

Научный руководитель

• доктор технических наук, профессор Воробьев Владимир Иванович

Официальные оппоненты:

■ доктор технических наук, профессор Тимофеев Адиль Васильевич

кандидат технических наук

Зима Владимир Михайлович

Ведущая организация: - Санкт-Петербургский Государственный

Электротехнический университет им. В.И. Ульянова (Ленина) «ЛЭТИ»

Защита диссертации состоится "11" октября 2005 г. в 13 часов на заседании Специализированного совета Д.002.199.01 при Санкт-Петербургском институте информатики и автоматизации Российской академии наук по адресу: 199178, Санкт-Петербург, В.О., 14 линия, 39.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского института информатики и автоматизации Российской академии наук.

Автореферат разослан "9" сентября 2005 г.

Ученый секретарь

Диссертационного совета Д.002.199.01 кандидат технических наук

А.Л. Ронжин

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. В настоящее время среди организаций, предлагающих сетевые услуги, существует жёсткая конкуренция. В этих условиях клиенты становятся особенно требовательными и ожидают высочайшего качества обслуживания, включая непрерывность обслуживания в течение всего оплаченного времени. Нарушение обслуживания вследствие сбоя в сети более не является допустимым, так как это может вызвать существенные потери прибыли в течение времени простоя. Подобные потери прибыли могут привести к негативной рекламе сетевого провайдера и к потере клиентуры.

Основными аспектами, необходимыми для успешной работы 1Р сети, являются выбор маршрута пакета и недопущение закупорки транспортных артерий. 1Р маршрутизация была разработана таким образом, чтобы восстановить маршрут передачи данных после практически любого отказа сетевых элементов. Однако современные реализации маршрутизации не могут сделать это в течение приемлемого интервала времени, так как реконфигурация сети может часто занять больше времени, чем десятые доли секунды, которые обычно являются , приемлемым для пользователя интервалом времени. Задержки являются следствием недостаточно частых контрольных сообщений и того факта, что всегда определённое число сетевых узлов должно быть проинформировано о произошедшем сбое в сети, и эти узлы должны предпринять определённые контрмеры, для чего необходимо время. И хотя разрыв соединения на несколько секунд является абсолютно приемлемым для соединения компьютер - компьютер, это существенно ограничивает использование человеком существующих 1Р сетей для связи в режиме реального времени. В связи с этим представляется актуальным разработка алгоритмов маршрутизации, обеспечивающих более надёжную передачу пакетов данных.

Таким образом, актуальность диссертационного исследования определяется тем, что современные средства 1Р маршрутизации не обеспечивают отказоустойчивой маршрутизации за допустимый интервал времени, что является сдерживающим фактором расширения использования 1Р сетей.

Цель и задачи работы. Целью данной работы является системный анализ процессов 1Р маршрутизации компьютерных сетей, разработка и обоснование многопутевой маршрутизации с целью повышения отказоустойчивости и эффективности использования имеющихся сетевых ресурсов. Для выполнения этой цели необходимо решить следующие задачи: 1) проанализировать известные методы многопутевой маршрутизации, а также свойства топологий компьютерных сетей, совместимых с многопутевой маршрутизацией;

3

/

2) разработать метод и алгоритмы многопутевой маршрутизации по адресу получателя, обеспечивающие повышение отказоустойчивости передачи 1Р пакетов по сравнению с предшествующими аналогами;

3) разработать критерии и алгоритм проверки совместимости топологии компьютерной сети с многопутевой маршрутизацией;

4) разработать алгоритм построения топологий компьютерных сетей, совместимых с многопутевой маршрутизацией;

5) проверить эффективность применения разработанного метода маршрутизации;

6) предложить способ практического использования созданных алгоритмов на базе современных протоколов маршрутизации. Методы исследования. В ходе исследования были использованы

подходы и методы теории графов, методы теории вероятности, комбинаторного анализа, системного и объектно-ориентированного анализа. В разработке программного обеспечения использовалась технология объектно-ориентированного программирования.

На защиту выносятся следующие результаты:

1) 02 метод многопутевой маршрутизации по адресу получателя.

2) Шаблонные алгоритмы многопутевой маршрутизации на основе 4 и 6 шаблонов.

3) Метод принятия решения о совместимости топологии компьютерной сети с многопутевой (02) маршрутизацией.

4) Алгоритм построения топологий компьютерных сетей, совместимых с многопутевой (02) маршрутизацией.

Научная новизна:

1) Предложен 02 метод многопутевой маршрутизации по адресу получателя, позволяющий обеспечить применение многопутевой маршрутизации для максимально возможного числа узлов в заданной топологии сети.

2) Сформулирован шаблонный подход построения многопутевой маршрутизации. На основе этого подхода были разработаны алгоритмы многопутевой маршрутизации с применением 4 и 6 шаблонов, обеспечивающие более высокую отказоустойчивость маршрутизации и более равномерное распределение нагрузки на каналы связи по сравнению с предшествующими аналогами.

3) Разработан алгоритм для проверки совместимости топологии сети с многопутевой (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 листов).

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована важность и актуальность темы диссертации, сформулированы цели работы и основные задачи, которые необходимо решить для ее достижения, характеризуется научная новизна и практическая ценность работы, кратко излагаются основные результаты работы.

В первой главе приводится классификация и анализ современных протоколов IP маршрутизации. Особое внимание уделяется алгоритмам, лежащим в их основе. По существу, современная маршрутизация является однопутевой: из широко распространённых протоколов маршрутизации только протокол OSPF предлагает некое подобие многопутевой маршрутизации. В связи с этим, можно выделить два основных недостатка современной маршрутизации:

1) Отказ одного из каналов передачи данных часто требует достаточно продолжительного времени для перенаправления трафика, что не является приемлемым для трафика со строгими требованиями к качеству обслуживания (QoS).

2) Установление одиночного маршрута между двумя узлами не обеспечивает какой-либо защиты против динамической перегрузки, даже если соседние маршруты могут иметь достаточно свободной пропускной способности, чтобы нести часть трафика.

Эти проблемы могут быть решены использованием двух или более непересекающихся маршрутов, когда маршрутизатор может выбрать два (или более) маршрута, даже если они имеют различную стоимость. Кроме того, определённые меры должны быть приняты, чтобы избежать зацикливания при использовании непересекающихся маршрутов.

Подобную возможность предоставляет только режим работы Equal-Cost Multi Path (ЕСМР) протокола маршрутизации OSPF. Суть этого режима работы состоит в том, что OSPF позволяет использовать несколько маршрутов для доставки данных до цели, но при непременном условии, что эти маршруты имеют одинаковую стоимость, и не существует более дешёвого (короткого) маршрута. На практике же будет часто невозможно назначить цену рёбрам таким образом, чтобы было возможно иметь одинаковую стоимость для нескольких маршрутов. Таким образом, для большинства сетей невозможно гарантировать непересекающиеся маршруты по направлению ко всем целям для каждого маршрутизатора. И как следствие, в то время как современные IP сети очень успешно восстанавливаются от потери связности, они слишком медлительны для многих интерактивных приложений.

Быстрое обнаружение отказа канала передачи данных и улучшение распределения трафика являются конфликтующими друг с другом

требованиями. Если оставить в стороне проблему выбора цены дуг таким образом, чтобы использовать требуемое число дуг и при этом экономно использовать пропускную способность, то наиболее важными и в то же время практически обязательными требованиями для более совершенной маршрутизации являются:

1) наличие нескольких маршрутов от каждого узла до каждой цели, чтобы способствовать преодолению отказа одного из маршрутов;

2) маршрутизация без зацикливания (без циклов маршрутизации), основанная на адресе цели.

Первое требование есть не что иное, как фундаментальная идея увеличения надёжности, а второе требование - это практический аспект сохранения маршрутизации в рабочем состоянии.

Необходимо отметить, что существующие на данный момент алгоритмы многопутевой маршрутизации, за исключением рассматриваемых в этой диссертации, могут бьпъ реализованы только при условии анализа маршрутизаторами не только адреса получателя, но и адреса источника. В первой главе приводятся два наиболее характерных алгоритма подобной маршрутизации. Первый из них позволяет строить маршруты независимые по рёбрам, а второй - по узлам. Однако у'подобной маршрутизации имеется один существенный недостаток: поскольку 1Р пакет при использовании этой маршрутизации содержит ещё и адрес отправителя пакета, то это приводит к многократному увеличению таблиц маршрутизации, что не позволяет осуществлять поиск в этих таблицах за приемлемый промежуток времени.

Следовательно, маршрутизация с анализом 1Р адреса источника мало пригодна для больших сетей. Стремясь решить эти проблемы вместе с проблемой распределения нагрузки, в заключение первой главы ставится цель разработать метод и алгоритмы маршрутизации, удовлетворяющие перечисленным выше требованиям.

Во второй главе производится моделирование маршрутизации на основе теории графов. В начале главы приводятся основные обозначения, и даётся ряд определений, на основе которых строится всё дальнейшее исследование.

Топология компьютерной сети представлена как ориентированный граф N = (V, Е), где V - конечное множество узлов (называемых также вершинами), и Е с:У хУ-набор ориентированных рёбер (называемых также дугами) без петель, так что (и, и) 0 Е для любых и е V. Так как рассматриваемые линии связи в сетях обычно двунаправлены, предполагается, что если направленное ребро (и, V) е Е тогда также направленное ребро (V, и) е Е. Степень выхода (и) = |Аф (и)\ вершины и определяется как число исходящих дуг из узла и в графе (7. Точно так же степень входа 1а (и) это число входящих дуг узла и в графе б. Для сетей с двунаправленными линиями связи со(и) = г(и) для всех и.

Для заданного узла совокупность записей в таблицах маршрутизации других узлов, посвящённых путям до узла образует граф маршрутизации для 1/ в сети, который может быть определён следующим образом:

Определение 1 (Граф маршрутизации) Пусть N = (V, Е) это топология сети, где с1 е К это вершина в N. Граф маршрутизации Ка = (V, Е') с Е' аЕ для адресата с/ это ориентированный подграф графа N. содержащий все его вершины такой, что Уи е V: и

Чтобы избежать зацикливания при передаче пакетов, графы маршрутизации обычно обязаны быть ациклическими. Необходимо заметить, что может существовать много различных графов маршрутизации для заданного адресата в сети. Далее, для каждого узла мы подразумеваем, что и * (/, <Оц (и) > 1, и а)я (ф = 0. Для однопутевой маршрутизации, графы маршрутизации являются остовными входными деревьями по направлению к адресату, и, как правило, деревьями кратчайших путей.

Для того чтобы повысить отказоустойчивость сети, необходимо, чтобы у каждого узла графа маршрутизации и * г/ (где ^ - это узел-адресат) имелось не менее двух исходящих дуг по направлению к цели. В данной работе такая маршрутизация называется многопутевой маршрутизацией. Узлы же, у которых имеется только одна исходящая дуга по направлению к цели, называются 01 узлами.

х у

Рисунок 1: Двухпутевой граф маршрутизации для адресата О с использованием джокера.

Необходимо прилагать особые усилия при использовании многопутевой маршрутизации для того, чтобы избежать образования циклов маршрутизации. Рисунок 1 поясняет ситуацию на простом примере. Если передача по ребру ху разрешена в обоих направлениях, то х и у имеют два пути к с1, но при этом образуется цикл маршрутизации с длиной два. Как решить проблему цикла маршрутизации с длиной два, подробно рассказано в четвёртой главе, пока же можно только отметить, что существование подобных циклов в графе маршрутизации является допустимым. Дуга ху называем джокером, более подробное определение и свойства которого приводятся во второй главе. Использование джокеров объясняется невозможностью обеспечить многопутевую маршрутизацию для всех узлов без их использования для топологий сетей, содержащих только одно ребро между двумя узлами. Другой причиной их использования является стремление оставить определённую степень свободы в управлении динамической системой, а именно маршрутизацией компьютерной сети.

Также в этой главе даётся определение и анализ свойств метода многопутевой маршрутизации с использованием дуг-джокеров, называемого также методом 02 многопутевой маршрутизации (от англ. „Output 2"). В основе метода лежит использование 02 графов маршрутизации.

Определение 2 (02 граф маршрутизации) Пусть N= (V, Е) это топология сети. Тогда 02 многопутевой граф маршрутизации Rj = (У, Е'), где Е' с Е для узла-получателя d е V это ориентированный подграф графа N, содержащий все его вершины, такой, что:

1) Vu е V: и ->R d.

Узел-получатель должен быть достижим всеми остальными узлами.

2) V и & V-fd}: coR (и) <> 2. Каждый узел кроме узла-получателя должен иметь степень выхода не менее чем 2.

3) Vи е V-{d} Vv е V-fu, d}: v —>r~u d. Если любой узел кроме узла-получателя удален, то узел-получатель должен быть достижим всеми оставшимися узлами. В противном случае, такой узел и называется SO узлом.

4) Vu е V-fd} 3v е V: (и, v) eE'u(v, и) 0 Е'.

Каждый узел кроме узла-получателя должен иметь, по крайней мере, одну исходящую дугу, которая не является джокером.

5) и -*rv uv -*ru => uv eE'. Если два узла и и v взаимно достижимы в R, то они являются соседями, а связь между ними - это дуга-джокер, то есть джокеры не создают цикла маршрутизации, содержащего более двух дуг.

Разработка алгоритмов построения 02 графов маршрутизации является главной задачей в данной диссертации и подробно описана в следующей главе.

Особое внимание во второй главе уделено исследованию свойств топологий компьютерных сетей, совместимых с 02 маршрутизацией, т.е. тех, для которых можно обеспечить такую маршрутизацию.

В этой же главе приводятся геометрические критерии совместимости топологий компьютерных сетей с 02 маршрутизацией, использование которых позволяет оценить возможность использования 02 маршрутизации для конкретной сети. Эти критерии могут быть также применены для модернизации топологии существующей компьютерной сети, чтобы сделать её совместимой с 02 маршрутизацией. На основе этих критериев был разработан алгоритм для проверки совместимости топологии компьютерной сети с 02 маршрутизацией.

Если же перед сетевым оператором стоит цель создать новую компьютерную сеть, топология которой была бы совместима с 02 маршрутизацией, то может быть использован алгоритм построения таких топологий, который приводится и доказывается также во второй главе.

Третья глава посвящена разработке и анализу алгоритмов 02 многопутевой маршрутизации. В главе приводится описание шаблонного подхода к многопутевой (02) маршрутизации, а также нескольких алгоритмов 02 маршрутизации, разработанных на его основе и служащих примером применения данного метода. Всего приводятся три различных алгоритма построения 02 маршрутизации, которые анализируются совместно с алгоритмами других авторов, кратко рассмотренных в первой главе.

Суть подхода состоит в построении графа маршрутизации путём расширения имеющегося графа маршрутизации предопределёнными шаблонами. Шаблон графа маршрутизации - это маленький подграф, содержащий по крайней мере один узел с одной исходящей дугой, который может использоваться как основной элемент в процессе построения графа Я<). На первом шаге граф маршрутизации содержит только узел-адресат. На последующих шагах соседние с графом маршрутизации К^ узлы добавляются к нему в составе шаблонов. После этого узлы и дуги шаблона становятся частью графа маршрутизации

В основе подхода лежат четыре основных типа шаблонов графа маршрутизации. Выбор шаблонов не случаен, он основан на свойствах 02 графов маршрутизации и операциях над ними, рассмотренных во второй главе.

Любой 02 граф маршрутизации может быть представлен как набор следующих шаблонов:

1) 02 + шаблон маршрутизации - это узел и е V с двумя или более исходящими дугами к неполному графу маршрутизации Я',1 (см. Рисунок 2). Если ориентированный граф Л'а является 02 графом без БО узлов и без циклов, то после добавления 02 + шаблона маршрутизации, он по-прежнему останется 02 графом без вО узлов и циклов.

Рисунок 2: 02 + шаблон маршрутизации.

2) Джокерный шаблон маршрутизации - это два узла и и V, связанные вместе джокером XIV и соединённые с неполным графом маршрутизации дугами (и, х) и (v, у) соответственно, где х * у. Рисунок 3 иллюстрирует ситуацию.

Рисунок 3: Джокерный шаблон маршрутизации.

Если ориентированный граф Л'а - это 02 граф без БО узлов и без циклов, то после добавления джокерного шаблона маршрутизации это будет 02 граф без БО узлов и циклов, но с еще одним джокером.

3) БО шаблон маршрутизации - это два узла и и V, связанные вместе джокером цу и соединённые с неполным графом маршрутизации Я'а гранями (и, х) и (у, х) соответственно (см. Рисунок 4). БО шаблон маршрутизации не содержит БО узел непосредственно, но добавление БО шаблона маршрутизации к графу маршрутизации формирует БО узел (см. узел х на Рисунке 4) в графе маршрутизации.

Рисунок 4: 80 шаблон маршрутизации.

Если ориентированный граф К'а является 02 графом без БО узлов и без циклов, то после добавления БО шаблона маршрутизации это будет граф без 01 узлов и без циклов, но с одним БО узлом и с еще одним джокером.

Любой граф маршрутизации может быть представлен комбинацией предыдущих трех компонентов и нижеследующего:

4) 01 шаблон маршрутизации - это узел, связанный только одной исходящей дугой с неполным графом маршрутизации Я'а (см. Рисунок 5).

Рисунок 5: 01 шаблон маршрутизации.

Если ориентированный граф Я'а - это 02 граф без циклов, то после добавления 01 шаблона маршрутизации это будет граф без циклов, но с одним 01 узлом.

Примером использования шаблонного подхода многопутевой (02) маршрутизации является алгоритм маршрутизации на основе 4 базовых

шаблонов (РВ11А4), приведённых выше. В любой момент времени множество узлов графа разделено на три подмножества, неформально обозначенных как чёрные, серые и белые:

• Чёрные узлы уже содержатся в графе маршрутизации = (V', Е'); множество черных узлов соответственно и есть V'.

• Серые узлы не содержатся в но один из их соседей содержится в нём. Серые узлы действуют как своеобразные точки закрепления шаблонов, описанных выше. Серые узлы хранятся в упорядоченном множестве А по возрастанию расстояния до узла-адресата.

• Белые узлы - это все остальные, ещё неиспользованные узлы. АЛГОРИТМ РВКА4 (С, <0

1 delta <— длина кратчайших путей(£?, d)

2 R+- ({</}, 0) => Изначально только узел d чёрный -

3 A *-Adj(G, d) => Соседи узла d серые

4 while А Ф0

5 do if LLLABJI0H_02_PLUS

6 then continue

7 if ДЖОКЕРНЫЙШ АБ JIOH S then continue

9 if SO_LLIABJIOH

10 then continue

11 01_ШАБЛ0Н

12 return R

В первой строке кратчайшие расстояния от всех узлов графа до узла-адресата d сохраняются в упорядоченном по возрастанию списке delta, который будет использоваться для сортировки узлов множества Л. Во второй строке результирующий граф маршрутизации инициализируется как одиночный чёрный узел d, а упорядоченное множество А содержит всех соседей узла d после строки 3. Цикл while начинает свою работу в строке 4 и выполняется до тех пор, пока существуют серые узлы. Внутри цикла для каждого шаблона вызывается соответствующая процедура, возвращающая TRUE, если шаблон можно применить, или FALSE в противном случае. Если шаблон был применён, то немедленно начинается следующая итерация цикла.

Соответствующая процедура для каждого шаблона использует следующую подпрограмму для расширения существующего графа маршрутизации R, когда шаблон можно применить:

EXTEND(K)

1 А

2 V[R] V[R] и {и}

3 forail V е Adj(G, и)

4 do if v é A and v í => Узел v белый ?

5 then i-А и {v}

Данный узел и удаляется из списка узлов А в строке 1 и добавляется к множеству узлов графа /? во второй строке, становясь, таким образом, чёрным. Цикл, начинающийся в третьей строке, проверяет все соседние узлы узла и и добавляет все белые из них в список А и меняя их цвет на серый. Эта процедура добавляет только узлы. Дуги, содержащиеся в шаблонах, добавляются непосредственно в граф маршрутизации соответствующими для каждого шаблона процедурами.

В качестве примера соответствующей для каждого шаблона процедуры ниже приведена процедура для 02+ шаблона (см. Рисунок 2). Остальные процедуры очень похожи на неё и отличаются только условиями применения, а также числом узлов и дуг, которыми имеющийся граф должен быть дополнен.

ШАБЛ0Н_02_РЬив

1 forail и е А, по возрастанию расстояния до узла-адресата

2 do S <=- Adj{G, и) n V[R\ => Чёрные соседи узла и

3 if |<S| > 1

4 then EXTEND(w) 3 forail v e S

6 {(и, v)}

7 return TRUE

8 return FALSE

Цикл в первой строке проверяет все серые узлы в порядке возрастания расстояния до узла-адресата. После второй строки множество S содержит всех чёрных соседей узла и. Если множество S содержит по крайней мере два элемента (линия 3), тогда 02+ шаблон может быть применён. В этом случае граф R дополняется узлом и в строке 4, а все дуги (и; v), ведущие к чёрным узлам, добавляются к графу в строках 5 и 6. В заключении процедура возвращает TRUE, показывая, что шаблон был применён, или FALSE в противном случае.

Сложность построения графов маршрутизаций для всех адресатов при помощи этого алгоритма приблизительно равна О (|V|3 + |V || Е |).

В добавлении к теоретическому анализу разработанных алгоритмов в третьей главе производится также сравнение применения разработанных алгоритмов для различных топологий компьютерных сетей, часть из которых реально существует. При этом только некоторые из этих сетей совместимы с 02 многопутевой маршрутизацией. Сравнение производится по следующим основным критериям:

1) Суммарное число узлов, имеющих только один путь до цели (Ol узлов), т.е. это число узлов у которых степень выхода coR (u) = 1. Чем меньше число таких узлов, тем лучше.

2) Суммарное число узлов, отказ одного из которых превращает граф в несвязный (число SO узлов). Чем меньше число таких узлов, тем лучше.

3) Число дуг-джокеров. Чем меньше их число, тем лучше.

4) Средняя отказоустойчивость графов маршрутизации для заданной топологии сети в ответ на отказ одного или нескольких элементов сети. Эта характеристика является средним процентным соотношением узлов в графах маршрутизации, сохранивших путь к адресату после произошедшего сбоя, к изначальному числу узлов, имевших путь к адресату. Данная характеристика вычисляется по формуле: • В случае отказа одного из узлов

и — 1ЛП__100-ЛГ

"1-1ии и-гм>ги

• В случае отказа двух узлов

п2 =100-

• В случае отказа одного из рёбер

/, = 100 -

юо х

\v\ty\-m

В случае отказа двух рёбер

7 = Ю0--

• В случае одновременного отказа одного из узлов и одного из рёбер

К = 100--, „„

где X - это суммарное число пар узлов источник - адресат для всех графов маршрутизации, где источник потерял связь с адресатом в результате соответствующего отказа; \У\ - это число узлов в исходном графе топологии

сети; — - это число неориентированных ребер в топологии сети.

Разработанные алгоритмы были сравнены с алгоритмом Райхерта и алгоритмом неравных кратчайших путей (модифицированным ЕСМР) протокола ОБРР. Рисунок 6 демонстрирует на примере шести топологий сетей разницу результатов работы алгоритма РВЯА4, разработанного в данном диссертационном исследовании, по сравнению с двумя вышеперечисленными алгоритмами. Из рисунка 6 следует, что графы маршрутизации, построенные при помощи алгоритма РВ11А4, обладают более высокой отказоустойчивостью на отказ одного из рёбер, чем графы, построенные алгоритмами Райхерта или модифицированным ЕСМР.

Сравнение алгоритмов по другим критериям также показало превосходство алгоритмов данного диссертационного исследования над предшествующими аналогами. Главным же преимуществом разработанных по шаблонному подходу алгоритмов многопутевой (02) маршрутизации является то, что они, в отличие от алгоритмов-конкурентов, способны всегда

обеспечить многопутевую маршрутизацию, если это возможно для заданной топологии сети.

11 оо ■«.•11

жИ°лг

АЛЛ |пРВКА4 ■ Рвймрт

1ЛМВГ1М4

И, • Прммтк

Рисунок 6: Сравнение средней отказоустойчивости графов маршрутизации на отказ одного из рёбер (в процентах).

Четвёртая глава описывает пути практической реализации предложенного метода многопутевой маршрутизации, а также набор разработанных программ для расчёта и анализа графов маршрутизации. Наиболее сложным моментом практического применения метода 02 многопутевой маршрутизации является реализация механизма поддержки соединений-джокеров.

По существу, джокеры могут быть реализованы путём задания различных приоритетов для записей в таблице маршрутизации для одного и того же получателя. Если приоритеты не равны, то только маршрут с более высоким приоритетом должен использоваться в течение нормальной операции, и только если маршрут с высоким приоритетом даёт сбой, то маршрут с более низким приоритетом будет использован вместо него. Таким образом, джокеры реализуются как маршруты с более низким приоритетом. Подобная реализация может быть осуществлена при помощи стандартных механизмов 1Р маршрутизации.

ЗАКЛЮЧЕНИЕ

Применение предлагаемых в диссертационной работе алгоритмов многопутевой маршрутизации позволяет существенно повысить отказоустойчивость 1Р сетей. В ходе исследований, представленных в работе, были получены следующие результаты:

1. Был предложен метод 02 многопутевой маршрутизации по адресу получателя, позволяющий обеспечить применение многопутевой маршрутизации для максимально возможного числа узлов в заданной топологии сети. Данный метод может быть использован вместо существующих методов многопутевой маршрутизации.

2. Был сформулирован шаблонный подход к построению многопутевой маршрутизации, на основе которого были разработаны алгоритмы маршрутизации с применением 4 и 6 шаблонов. Данные алгоритмы

могут быть использованы вместо алгоритмов нахождения кратчайших путей в динамических протоколах маршрутизации внутреннего шлюза, отслеживающих состояния соединений. Они обеспечивают значительное повышение отказоустойчивости маршрутизации IP сетей.

3. Был разработан алгоритм для проверки совместимости топологии компьютерных сетей с предлагаемой многопутевой маршрутизацией. Алгоритм позволяет быстро оценить топологию компьютерной сети и выявить возможные недостатки с точки зрения алгоритмов многопутевой маршрутизации.

4. Были разработаны принципы и предложен алгоритм построения топологий сетей, совместимых с 02 многопутевой маршрутизацией. Алгоритм позволяет быстро построить топологию компьютерной сети, для которой возможно обеспечить многопутевую маршрутизацию для всех узлов.

5. Был предложен способ практического использования созданных алгоритмов на базе современных протоколов маршрутизации.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ю.Гликман "Выбор и усовершенствование генератора WEB трафика для тестирования поведения маршрутизатора в состоянии перегрузки", Труды СПИИРАН / Под ред. P.M. Юсупова вып. 1 т. 3 -СПб.: «Анатолия», 2003, С 49-56.

2. Y.Glickman, A.Kirstaedter et al. "Improving the Resilience in IP Networks", Proceedings of the 2003 IEEE Workshop on High Performance Switching and Routing, Spring-Verlag, 2003, pp. 91-96.

3. C.Reichert, Y.Glickman, T.Magedanz "Two Routing Algortihms for Failure Protection in IP Networks", Proceedings of the 10th IEEE Symposium on Computers and Communications, IEEE Press, 2005, pp. 97-102.

4. Y.Glickman "Method for computing routing graphs for multi-path routing" European patent application No 04011420.9,2004.

5. R.Chaparadza, Y.Glickman "RTLG -RSVP enabled Traffic Load Generator for Intra-Domain and Inter-Domain QoS Signalling Tests", Proceedings of the IPS-MoMe 2005, Warsaw: Warsaw University of Technology, 2005, pp. 132-140.

I

t

ô

L

\

>4â

Р1693 /

РНБ Русский фонд

2006-4 11558

Отпечатано с готового оригинал-макета, предоставленного автором. Подписано в печать 07.09.2005. Формат 60x84 1/16. Бум. офсетная. Усл. печ. л. 1. Тираж 100 экз. Заказ 67.

ООО "Анатолия" 199178, Санкт-Петербург, 14 лин., 39.

Введение

Глава 1. Методы, протоколы и алгоритмы маршрутизации в современных IP сетях.

1.1. Архитектура сети Интернет.

1.2. Основные метрики динамических протоколов маршрутизации

1.3. Протоколы маршрутизации внутреннего шлюза.

1.3.1. Протокол маршрутизации RIP.

1.3.2. Протокол маршрутизации OSPF.

1.4. Современные алгоритмы маршрутизации.

1.4.1. Алгоритм маршрутизации на основе алгоритма Дейкстры

1.4.2. Алгоритм Суурбалле для поиска пары кратчайших независимых по рёбрам путей.

1.4.3. Алгоритм Суурбалле для поиска пары кратчайших независимых по вершинам путей.

1.4.4. Алгоритм многопутевой маршрутизации Шольмайера.

1.4.5. Алгоритм многопутевой маршрутизации Райхерта.

1.5. Основные типы сбоев в компьютерных сетях.

1.6. Недостатки существующей IP маршрутизации.

1.7. Постановка задачи.

1.8. Выводы по первой главе.

Глава 2. Графы маршрутизации.

2.1. Моделирование маршрутизации на основе теории графов.

2.2. Метод 02 многопутевой маршрутизации.

2.3. Свойства топологий сетей совместимых с 02 многопутевой маршрутизацией.

2.4. Алгоритм проверки совместимости топологий сетей с 02 многопутевой маршрутизацией.

2.5. Алгоритм построения 02 совместимых топологий сетей.

2.6. Выводы по второй главе.

Глава 3. Алгоритмы многопутевой маршрутизации.

3.1. Требования к 02 алгоритмам маршрутизации.

3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе пошагового улучшения.

3.3. Шаблонный подход построения многопутевой маршрутизации.

3.3.1. Алгоритм построения графов многопутевой (02) маршрутизации на основе четырёх шаблонов.

3.3.2. Алгоритм построения графов многопутевой (02) маршрутизации на основе шести шаблонов.

3.4. Сравнение алгоритмов.

3.5. Выводы по третьей главе.

Глава 4. Пути практической реализации 02 многопутевой маршрутизации.

4.1. Реализация механизма работы соединений-джокеров.

4.2. Пакет программ для расчёта и анализа графов маршрутизации.

4.2.1. Программа для расчёта графов многопутевой маршрутизации.

4.2.2. Программа для анализа графов многопутевой маршрутизации и топологий сетей.

4.2.3. Программа для построения топологий сетей, совместимых с 02 многопутевой маршрутизацией.

4.3. Выводы по четвёртой главе.

Актуальность проблемы. В настоящее время среди организаций, предлагающих сетевые услуги, существует жёсткая конкуренция. В этих условиях клиенты становятся особенно требовательными и ожидают высочайшего качества обслуживания, включая непрерывность обслуживания в течение всего оплаченного времени. Нарушение обслуживания вследствие сбоя в сети более не является допустимым, так как это может вызвать существенные потери прибыли в течение времени простоя. Подобные потери прибыли могут привести к негативной рекламе сетевого провайдера и к потере клиентуры.

Основными аспектами, необходимыми для успешной работы IP сети, являются выбор маршрута пакета и недопущение закупорки транспортных артерий. IP маршрутизация была разработана таким образом, чтобы восстановить маршрут передачи данных после практически любого отказа сетевых элементов. Однако современные реализации маршрутизации не могут сделать это в течение приемлемого интервала времени, так как реконфигурация сети может часто занять больше времени, чем десятые доли секунды, которые обычно являются приемлемым для пользователя интервалом времени. Задержки являются следствием недостаточно частых контрольных сообщений и того факта, что всегда определённое число сетевых узлов должно быть проинформировано о произошедшем сбое в сети, и эти узлы должны предпринять определённые контрмеры, для чего необходимо время. И хотя разрыв соединения на несколько секунд является абсолютно приемлемым для соединения компьютер - компьютер, это существенно ограничивает использование человеком существующих IP сетей для связи в режиме реального времени. В связи с этим представляется актуальным разработка алгоритмов маршрутизации, обеспечивающих более надёжную передачу пакетов данных.

Таким образом, актуальность диссертационного исследования определяется тем, что современные средства IP маршрутизации не обеспечивают отказоустойчивой маршрутизации за допустимый интервал времени, что является сдерживающим фактором расширения использования IP сетей.

Цель и задачи работы. Целью данной работы является системный анализ процессов IP маршрутизации компьютерных сетей, разработка и обоснование многопутевой маршрутизации с целью повышения отказоустойчивости и эффективности использования имеющихся сетевых ресурсов. Для выполнения этой цели необходимо решить следующие задачи:

1) проанализировать известные методы многопутевой маршрутизации, а также свойства топологий компьютерных сетей, совместимых с многопутевой маршрутизацией;

2) разработать метод и алгоритмы многопутевой маршрутизации по адресу получателя, обеспечивающие повышение отказоустойчивости передачи IP пакетов по сравнению с предшествующими аналогами;

3) разработать критерии и алгоритм проверки совместимости топологии компьютерной сети с многопутевой маршрутизацией;

4) разработать алгоритм построения топологий компьютерных сетей, совместимых с многопутевой маршрутизацией;

5) проверить эффективность применения разработанного метода маршрутизации;

6) предложить способ практического использования созданных алгоритмов на базе современных протоколов маршрутизации.

Методы исследования. В ходе исследования были использованы подходы и методы теории графов, методы теории вероятности, комбинаторного анализа, системного и объектно-ориентированного анализа. В разработке программного обеспечения использовалась технология объектно-ориентированного программирования.

На защиту выносятся следующие результаты:

1) 02 метод многопутевой маршрутизации по адресу получателя.

2) Шаблонные алгоритмы многопутевой маршрутизации на основе 4 и 6 шаблонов.

3) Метод принятия решения о совместимости топологии компьютерной сети с многопутевой (02) маршрутизацией.

4) Алгоритм построения топологий компьютерных сетей, совместимых с многопутевой (02) маршрутизацией.

Научная новизна:

1) Предложен 02 метод многопутевой маршрутизации по адресу получателя, позволяющий обеспечить применение многопутевой маршрутизации для максимально возможного числа узлов в заданной топологии сети.

2) Сформулирован шаблонный подход построения многопутевой маршрутизации. На основе этого подхода были разработаны алгоритмы многопутевой маршрутизации с применением 4 и 6 шаблонов, обеспечивающие более высокую отказоустойчивость маршрутизации и более равномерное распределение нагрузки на каналы связи по сравнению с предшествующими аналогами.

3) Разработан алгоритм для проверки совместимости топологии сети с многопутевой (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 листов).

4.3. Выводы по четвёртой главе

1) Предложен способ практического использования разработанных алгоритмов многопутевой маршрутизации на базе современных протоколов маршрутизации.

2) Разработан набор программ для расчёта и анализа графов маршрутизации, а также топологий компьютерных сетей.

Заключение

Применение предлагаемых в диссертационной работе алгоритмов многопутевой маршрутизации позволяет существенно повысить отказоустойчивость IP сетей. В ходе исследований, представленных в работе, были получены следующие результаты:

1. Был предложен метод 02 многопутевой маршрутизации по адресу получателя, позволяющий обеспечить применение многопутевой маршрутизации для максимально возможного числа узлов в заданной топологии сети. Данный метод может быть использован вместо существующих методов многопутевой маршрутизации.

2. Был сформулирован шаблонный подход к построению многопутевой маршрутизации, на основе которого были разработаны алгоритмы маршрутизации с применением 4 и 6 шаблонов. Данные алгоритмы могут быть использованы вместо алгоритмов нахождения кратчайших путей в динамических протоколах маршрутизации внутреннего шлюза, отслеживающих состояния соединений. Они обеспечивают значительное повышение отказоустойчивости маршрутизации IP сетей.

3. Был разработан алгоритм для проверки совместимости топологии компьютерных сетей с предлагаемой многопутевой маршрутизацией. Алгоритм позволяет быстро оценить топологию компьютерной сети и выявить возможные недостатки с точки зрения алгоритмов многопутевой маршрутизации.

4. Были разработаны принципы и предложен алгоритм построения топологий сетей, совместимых с 02 многопутевой маршрутизацией. Алгоритм позволяет быстро построить топологию компьютерной сети, для которой возможно обеспечить многопутевую маршрутизацию для всех узлов. 5. Был предложен способ практического использования созданных алгоритмов на базе современных протоколов маршрутизации.

1. Белоцерковский Д.Л., Вишневский В.М. Новый алгоритм генерации остовных двусвязных подграфов для оптимизации топологии сетей передачи данных // Автоматика и телемеханика. 1997. - №1. -С.108-120.

2. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. М: Мир, 1989. - 544с.

3. Вишневский В.М. Теоретические основы проектирования компьютерных сетей. М: Техносфера, 2003. - 512с.

4. Вишневский В.М., Воробьев Д.Л. Архитектура IP-сети для качественной пакетной телефонии // Электросвязь. 2000. - №10. - С. 14-15.

5. Вишневский В.М., Левнер Е.В., Федотов Е.Б. Математические модели исследования алгоритмов маршрутизации в сетях передачи данных // Информационные процессы. 2001. - Т.1, №2. - С.103-126.

6. Вишневский В.М., Пороцкий С.М. Динамическая маршрутизация в ATM сетях проблемы и решения // Автоматика и телемеханика. -2003.-№6.-С. 20-23.

7. Вишневский В.М., Федотов Е.Б. Анализ методов маршрутизации при проектировании сетей пакетной коммутации // Proceedings of 3-rd I.S. "Teletrafflc Theory and Computing Modeling". София: 1992. - С. 8693.

8. Воробьев В.И., Гликман Ю.К. Повышение безопасности IP сети при помощи многопутевой маршрутизации // Proceedings of Материалы конференции "Региональная информатика 2002". - СПб: 2002.

9. Гликман Ю.К. "Выбор и усовершенствование генератора WEB трафика для тестирования поведения маршрутизатора в состоянииперегрузки", Труды СПИИРАН / Под ред. P.M. Юсупова вып. 1 т. 3. -СПб.: «Анатолия», 2003. С. 49-56.

10. Зайченко Ю.П. Задачи проектирования структуры распределенных вычислительных сетей // Автоматика. 1981. - №3. - С.35-44.

11. Зима В.М., Молдавян Н.А., Молдавян А.А. Безопасность сетевых технологий. СПб.: СПбГУ, 1999. - 368с.

12. Зима В.М., Молдовян А.А., Молдовян Н.А. Безопасность глобальных сетевых технологий. СПб.: "БХВ-Петербург", 2000. - 320с.

13. Камер Д., Э. Сети TCP/IP, том 1. Принципы, протоколы и структура, 4-е изд.: пер. с англ. М.: Издательский дом "Вильяме", 2003. - 880с.

14. Касьянов В.Н., Евстигнеев В.А. Графы в программировании: обработка, визуализация и применение. СПб: БХВ-Петербург, 2003. - 1004с.

15. Коннов В.В., Клековкин Г.А., Коннова Л.П. Геометрическая теория графов. М: Народное образование, 1999. - 240с.

16. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ: пер. с англ. М.: МЦНМО, 2001. - 960с.

17. Круглый З.П. Алгоритмы расчета моделей структур вычислительных систем с различными классами заданий // Управляющие системы и машины. 1980. - № 4. - С. 73-79.

18. Кульчин М. Технологии корпоративных сетей. СПб: Изд-во "Питер", 2000. - 704с.

19. Купиллари А. Трудности доказательств: пер. с англ. М: Техносфера, 2002. - 304с.

20. Лазарев В.Г. Интеллектуальные цифровые сети. М: Финансы и статистика, 1996. - 382с.

21. Макконнелл Д. Анализ алгоритмов. Вводный курс: пер. с англ. М: Техносфера, 2002. - 304с.

22. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети коммутации пакетов. М: Радио и связь, 1986. - 408с.

23. Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. М: Наука, 1990. - 488с.

24. Олифер В., Олифер Н. Новые технологии и оборудование IP-сетей. -СПб: Изд-во "Питер", 2000. 512с.

25. Остерлох X. Маршрутизация в IP- сетях. Принципы, протоколы, настройка: пер. с англ. СПб.: ООО «ДиаСофт», 2002. - 512с.

26. Сатовский Б.Л. MPLS технология маршрутизации для нового поколения сетей общего пользования // Сети и системы связи. - 2001.- № 3. С.29.

27. Таненбаум Э. Компьютерные сети: пер. с англ. СПб.: Питер, 2002. -848с.

28. Тимофеев А.В. Методы высококачественного управления, интеллектуализации и функциональной диагностики автоматических систем // Международный теоретический и прикладной научно-технический журнал «Мехатроника, автоматизация и управление». -2004. С. 2-9.

29. Тимофеев А.В. Проблемы и методы адаптивного управления потоками данных в телекоммуникационных системах // «Информатизация и связь». 2003. - №№1-2. - С. 68-74.

30. Шварц М. Сети связи: протоколы, моделирование и анализ. М: Наука, 1992. - 263с.

31. Al-Fuqaha A., Chaudhry G.M. Routing and wavelength assignment in all-optical DWDM networks with sparse wavelength conversion capabilities.- Kansas City: University of Missouri, 2004. 161p.

32. Anand V., Chakrabarty K. Cisco IP routing protocols: troubleshooting techniques, 1st ed. Hingham, Mass.: Charles River Media, 2004. - 409p.

33. Apostolopoulos G., Guerin R., Kamat S., Tripathi S. Improving QoS Routing Performance under Inaccurate Link State Information // ITC. -1999.- 16.-pp.32-37.

34. Ash G.R. Dynamic routing in telecommunications networks. New York: McGraw Hill, 1998. - 746p.

35. Bak S. Load-Balanced routing. Houston: University of Houston, 2000. -145p.

36. Baker F., "RFC1812 Requirements for IP Version 4 Routers," IEEE, 1995.

37. Bedrosian E., Rand Corporation. A routing algorithm for digraphs. Santa Monica: Rand Corporation, 1976. - 4 p.

38. Bhandari R. Survivable networks: algorithms for diverse routing. -Boston; London: Kluwer Academic Publishers, 1999. 200p.

39. Black U. IP routing protocols: RIP, OSPF, BGP, PNNI, and Cisco routing protocols. London: Prentice-Hall International, 2000. - 287p.

40. Blaunstein N., Andersen J.B. Multipath phenomena in cellular networks. -Boston, Mass.; London: Artech House, 2002. 296 p.

41. Cantor D.G., Gerla M. Optimal routing in a packet-switched computer network // IEEE Trans, on Computers. 1974. - V. C-23, N 10. - pp. 10621068.

42. Chao H.J., Guo X. Quality of service control in high-speed networks. -New York: Wiley, 2002. 432p.

43. Chaparadza R., Glickman Y. RTLG -RSVP enabled Traffic Load Generator for Intra-Domain and Inter-Domain QoS Signalling Tests // Proceedings of Internet Performance, Simulation, Monitoring and Measurments (IPS-MoMe 2005). Warsaw: 2005. - pp. 132-140.

44. Chen S., Nahrstedt K. An Overview of Quality-of-Service Routing for the Next Generation High-Speed Networks: Problems and Solutions // IEEE

45. Network Magazine, Special Issue on Transmission and Distribution of Digital Video. 1998. - V.12, No.6. - pp.64-79.

46. Cidon I., Rom R., Shawitt Y. Analysis of Multi-Path Routing // IEEE Transaction on Networking. 1999. - V.7. - pp.885-896.

47. Clark M.P. Data networks, IP and the Internet: protocols, design and operation. Chichester: Wiley, 2003. - 848 p.

48. Das R., Chakrabarty K. Enabling IP routing with Cisco routers, 1 st ed. -Hingham, Mass.: Charles River Media, 2004. 486p.

49. Dijkstra E.W. A note on two problems in connexion with graphs // Numerische Mathematik. 1959. - V.l. - pp.269-271.

50. Dror M. Arc routing: theory, solutions, and applications. Boston, Mass.; London: Kluwer Academic, 2000. - 483 p.

51. Evans J.R., Minieka E., Minieka E. Optimization algorithms for networks and graphs, 2nd ed. New York: M. Dekker, 1992. - 470p.

52. Floyd R.W. Algorithm 97: Shortest path // Comm. ACM. 1997. - N3. -pp.320-327.

53. Forouzan B.A. TCP/IP protocol suite, 2nd ed. Boston: McGraw-Hill, 2003. - 942 p.

54. Fotz В., Rexford J., Thorup M. Traffic Engineering with Traditional IP Routing Protocols // IEEE Communications Magazin. 2002. - No. 10. -pp. 118-124.

55. Fotz В., Thorup M. Optimizing OSPF/IS-IS Weights in a Changing World // IEEE J. Select. Areas Commun. 2002. - V.20. - pp.756-767.

56. Frigioni D., Marchetti-Spaccamela A., Nanni U. Fully dynamic shortest paths and negative cycle detection on digraphs with arbitrary arc weights. Saarbruecken: Max-Planck-Institut fuer Informatik, 1998. - 18p.

57. Gafni M., Berstsekast D. Asymptotic Optimality of Shortest Path Routing Algorithms // IEEE Trans, on Information Theory. 1987. - no.l. - pp. 97133.

58. Garcia-Luna-Aceves J.J., Murthy S. A Path-Finding Algorithm for Loop-Free Routing // IEEE ACM Trans. Networking. 1997. - N2. - pp.76-82.

59. Gavish В., Hantler S.L. An algorithm for optimal rout selection in SNA networks // IEEE Trans, on Commun. 1983. - N10. - pp.1154-1161.

60. Gelenbe E., Pujolle G. Introduction to queueing networks. N.Y.: John Wiley, 1998. - 396c.

61. Guerin R., Orda A. QoS-based Routing in networks with Inaccurate Information: Theory and Algorithms // Proceedings of INFOCOM'97. Spring-Verlag, 1997. pp. 154-161.

62. Guido P. Maintaining Shortest Paths in Digraphs with Arbitrary Arc Weights: An Experimental Study // Proceedings of 4th International Workshop on Algorithm Engineering. Saarbruecken, Germany: Spring-Verlag, 1982. -pp.228-235.

63. Hedrick C., "RFC 1258 Routing Information Protocol," IEEE, 1988.

64. Henig M.I. The shortest path problem with two objective functions // European J. of Operational Research. 1985. - V.25. - pp.281-291.

65. Huitema C. Routing in the internet, 2nd ed. ed. Upper Saddle River, N.J.: Prentice Hall, 2000. - 384p.

66. Jacquet P., Muhlethaler P., Qayyum A. Optimized Link State Routing Protocol//-2001.

67. Johnson D. The Evolution of a Reliable Transport Network // IEEE Commun. Mag. 1999. - V.8. - pp.52-57.

68. Jungnickel D. Graphs, networks and algorithms. Berlin, Germany: Springer, 1999. - 589p.

69. Kelly F.P. Routing and capacity Allocation in Networks with Trunk Reservation // Mathematics of Operations Research. 1990. - V.15. -pp.771-793.

70. Kelly F.P. Routing in Circuit-Switched Networks: Optimization, Shadow Prices and Decentralization // Advances in Applied Probability. 1998. -V.20.-pp.112-144.

71. Kelly F.P., Williams R.J. Stochastic networks. New York: Springer-Verlag, 1995. - 427p.

72. Korilis Y.A., Orda A. Incentive compatible pricing strategies for QoS routing. Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 2002. - 21 p.

73. Lee W.C.e.a. Rule-Based Call-by-Call Source Routing for Integrated Communication Networks // Proc. IEEE INFOCOM'93. 1993. - pp.987993.

74. Lorenz D.H. Efficient QoS partition and routing of unicast and multicast.- Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1999. 24 p.

75. Lorenz D.H., Orda A. QoS routing in networks with uncertain parameters.- Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1997. 51 p.

76. Loshin P. Big book of border gateway protocol (BGP) RFCs. San Diego, Calif.; London: Morgan Kaufmann, 2000. - 570p.

77. Loshin P. Big book of World Wide Web RFCs. San Francisco, Calif.; London: Morgan Kaufmann, 2000. - 655p.

78. Malkin G., "RFC 2453," IEEE, 1998.

79. Malkin G.S. RIP: an intra-domain routing protocol. Reading, MA: Addison-Wesley, 2000. - 253p.81 . McDysan D.E. QoS and traffic management in IP and ATM networks. -New York: McGraw Hill, 2000. 456p.

80. Minsoo J., Dongseung K. Avoiding Network Congestion with Local Information // Proceedings of International Symposium on High Performance Computing. Kansai Science City, Japan: Springer, 2002. -pp.33-40.

81. Mouftah H.T., Ho P.-H. Optical networks: architecture and survivability. -Boston: Kluwer Academic, 2003. 302p.

82. Moy J. OSPF, RFC 1583. IEEE, 1998.

83. Moy J.T. OSPF: anatomy of an Internet routing protocol. Reading, Mass.; Harlow: Addison-Wesley, 1998. - 339p.

84. Murakami K., Kim H.-S. Comparative study on restoration schemes of survivable ATM networks // IEEE Commun. Mag. 1997. - no.5. -pp.652-680.

85. Nagle J. Congestion Control in TCP/IP Internetworks // Computer Commun. Rev. 1984. - vol.14. - pp.112-116.

86. Nishizeki Т., Chiba N. Planar graphs: theory and algorithms. -Amsterdam: North-Holland, 1988. 232p.

87. Orda A. Routing with end to end QoS guarantees in broadband networks.- Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1997. 26p.

88. Orda A., Rom R. Optimal routing with packet fragmentation in computer networks. Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 1992. - 30p.

89. Orda A., Sprintson A. Precomputation schemes for QoS routing. Haifa: Department of Electrical Engineering, Technion-Israel Institute of Technology, 2003. - 31 p.

90. Parkhurst W.R. Cisco router OSPF: design and implementation guide. -New York; London: McGraw-Hill, 1998. 340p.

91. Parkhurst W.R. Routing first-step. Indianapolis, IN: Cisco, 2005. - 414p.

92. Pepelnjak I. EIGRP network design solutions. Indianapolis, IN, USA: Cisco Press, 2000. - 366p.

93. Peterson L.L., Davie B.S. Computer networks: a systems approach, 3rd ed. Amsterdam; Boston: Morgan Kaufmann Publishers, 2003. - 813p.

94. Piro M., Medhi D. Routing, flow, and capacity design in communication and computer networks. San Francisco, Calif.: Morgan Kaufmann; Oxford: Elsevier Science, 2004. - 400p.

95. Postel J.B., United States. Defense Advanced Research Projects Agency A Graph model analysis of computer communications protocols. Los Angeles: University of California. School of Engineering and Applied Science, 1974. - 183p.

96. Reichert C., Glickman Y., Magedanz T. Two Routing Algortihms for Failure Protection in IP Networks // Proceedings of 10th IEEE Symposium on Computers and Communications. IEEE Press, 2005. pp. 97-102.

97. Retana A., White R., Slice D. EIGRP for IP: basic operation and configuration. Boston: Addison-Wesley, 2000. - 123p.

98. Roberts J. Traffic theory and the Internet // IEEE Communications Mag. -2001.-vol.39.-pp.94-99.

99. Salama H., Reeves D., Viniotis Y. Distributed Algorithm for Delay-Constrained Routing // Proceedings of INFOCOM'97. 1997. pp. 146-152.

100. Schollmeier G., Charzinski J., Kirstadter A., Reichert C., Schrodi K.J., Glickman Y., Winkler C. Improving the Resilience in IP Networks // Proceedings of IEEE Workshop on High Performance Switching and Routing 2003. 2003. pp.91-96.

101. Schulzrinne H. A comprehensive multimedia control architecture for the Internet // Proceedings of International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV). -St. Louis, Missouri: 1997. pp. 322-327.

102. Schulzrinne H. Internet problems and potential // Proceedings of Global Information Infrastructure Workshop at IEEE International Conference on Communications (ICC). Montreal, Canada: 1997. - pp. 154-159.

103. Schulzrinne H., Rosenberg J. Signaling for internet telephony // Proceedings of ICNP. Austine, Texas: 1998. - pp.231-237.

104. Shands D. The performance of probabilistic routing. Miami: University of Florida, 1998. - 91p.

105. Stallings W. High-speed networks and internets: performance and quality of service, 2nd ed. Upper Saddle River, N.J.: Prentice Hall, 2002. -715p.

106. Stamatelakis D., Grover W. IP Layer Restoration and Network Planning Based on Virtual Protection Cycles // IEEE J. Select. Areas Commun. -2000. vol.18. - pp. 1938-1949.

107. Stewart J.W. BGP4: inter-domain routing in the Internet. Reading, Mass.; Harlow: Addison-Wesley, 1999. - 137p.

108. Suurballe J.W. Disjoint Paths in a Network // Networks. 1974. - no.4. -pp. 125-145.

109. Suurballe J.W., Taijan, R.E. A quick method for finding shortest pairs of disjoint paths //Networks. 1984. - vol.14. - pp.325-336.

110. Thomas S.A. IP switching and routing essentials: understanding RIP, OSPF, BGP, MPLS, CR-LDP, and RSVP-TE. New York: Wiley, 2001. - 358p.

111. Thomas T.M. OSPF network design solutions, 2nd ed. Indianapolis, IN: Cisco Press, 2003. - 747p.

112. To M., Neusy P. Unavailability Analysis of Long-Haul Networks // IEEE J. Select. Areas Commun. 1994. - vol.12, no.l. - pp. 100-109.

113. Toy M. Optical networking. Piscataway, NJ: Institute of Electrical and Electronics Engineers, Inc., 2001. - 397p.

114. Tran D.T., Do T.V. Generalised invariant Subspace based Method for Steady State Analysis of QBD-M Proceses // Periodica Polytechnica. -2000. Vol.44. - pp. 159-178.

115. Vegesna S. IP quality of service. Indianapolis, Ind.: Cisco, 2001. - 343p.

116. Vishnevskiy V.M. Algorithms optimisation queueing networks and application for computer networks // Proceedings of International symposium Teletraffic theory and computer simulation. Sofia: 1988. -pp.345-358.

117. Vogel R.e.a. QoS Based Routing of Multimedia Streams in Computer Networks // IEEE Journal on Selected Areas in Communications. 1996. -V.14, no.7. - pp. 1235-1244.

118. White R., McPherson D., Srihari S. Practical BGP. Boston: Addison-Wesley, 2005. - 434p.

119. Wisniewski J.A., Sameh A. Parallel algorithms for network routing problems and recurrences. Urbana, 111.: Dept. of Computer Science, University of Illinois at Urbana-Champaign, 1979. - 34 p.

120. Wu T.-H. Fiber network service survivability. Boston: Artech House, 1992. - 459p.

121. Xu J. Topological structure and analysis of interconnection networks. -Dordrecht: Kluwer Academic Publishers, 2001. 342p.

122. Zhang R., Bartell M. BGP design and implementation. Indianapolis, Ind.: Cisco Press, 2004. - 638p.

123. Главный конструктор СЦПС «Спектр»1. А. Молдовян1. ЧЛЕНЫ КОМИССИИ:

124. Начальник НИО СЦПС «Спектр»

125. Настоящий акт составлен в том, что следующие результаты диссертационной работы Ю.К. Гликмана приняты к внедрению в ОАО «Телекомпания Санкт-Петербургское кабельное телевидение»:

126. Программная реализация разработанных в диссертационной работе алгоритмов многопутевой маршрутизации;

127. Программная реализация алгоритма построения топологий компьютерных сетей, совместимых с многопутевой маршрутизацией.

128. Программное обеспечение для анализа топологий компьютерных сетей;

129. Указанные результаты диссертационной работы Гликмана Ю.К. с успехом используются в ОАО «Телекомпания Санкт-Петербургское кабельное телевидение» при проведении работ по проектированию новых и по анализу существующих каналов связи.

130. Директор по эксплуатации ОАО <1. К.Н.Рахимов

131. Fraunhofer|nstjtutfQr0ffene1. Kommunikationssysteme

132. Fraunhofer FOKUS Kaiserin-Augusta-Allee 31 10589 Berlin2308.2004, Berlin1. STATEMENT

133. After using Yuri Glickman's thesis:

134. Elaboration of method and algorithms of multipath routing for improving the resilience in IP networks"

135. The FOKUS-TIP KING committee, formed by Dr. Peter Deussen, Eng. Ranganai Chaparadza and Eng. Justyna Zander-Nowicka considered the presented materials and decided, that:

136. The main features of the thesis were used during the scientific project "KING -Key Components for the Mobile Internet of Next Generation" in 2002-2004 years.

137. The presented in the theses pattern based algorithms achieve full node protection in topologies where this is theoretically feasible and they are well suited for link weight optimization.

138. The created software is well suited for computation and analysis of routing graphs.

139. The proposed method, algorithms and software allow to significantly improve the resilience in IP networks.1. Committee chairman,1. Dr. Peter Deussen1. Committee members:1. Ranganai Chaparadza1. Justyna Zander-Nowicka

140. Fraunhofer-Gesellschaft zur FSrderung der angewandten Forschung e.V. HansastraBe 27c 80686 Munchen

141. Bankverbindung: Deutsche Bank, MOnchen Konto 75 21 933 BLZ 700 700 10

142. Vorstand der Fraunhofer-Gesellschaft Prof. Dr. Hans-JOrg Bullinger, President

143. Dr. rer. pol. Alfred Gossner Dr. jur. Dirk-Meints Polter Prof. Dr. Dennis Tsichritzis

144. Fraunhofer Institut fur Offer>« Kommunikationssysteme FOKUS

145. Kaiserin-Augusta-Allee 31 10589 Berlin

146. Tel +49 (0) 30/34 63-70 00 Fax +49(0)30/3463-80001. FOKUS Institutsleitung1.stitute leiter

147. Univ.-Prof. Dr.-lng.habil. Prof.e.h. Dr.h.c. Radu Popescu-Zeletin Stellvertretender Institutsleiter Dipl.-lng. Berthold Butscher