Факультет вычислительной техники и информатики
Специальность: Компьютерные системы и сети
В компьютерных сетях применяется большое количество алгоритмов маршрутизации. Именно сетевой уровень модели OSI занимается разработкой маршрутов доставки пакетов от отправителя к получателю. Чтобы добраться до пункта назначения, пакету может потребоваться преодолеть несколько транзитных участков между маршрутизаторами. Сетевой уровень является самым низким уровнем, который имеет дело с передачей данных по всему пути от одного конца до другого.
Обычно в сложных составных сетях практически всегда существует несколько альтернативных маршрутов, по которым возможна передача данных между двумя узлами. Кроме того, крупные составные сети могут включать в себя сети различных масштабов – от локальных до территориально-распределенных глобальных сетей.
Маршрутом пересылки пакета с одного узла составной сети на другой является порядок прохождения этим пакетом транзитных сетей, соединяющих сети, в которых расположены источник и адресат данного пакета.
Составные сети, в которых требуется маршрутизация пакета на сетевом уровне, должны быть объединены между собой посредством маршрутизаторов. Поэтому маршрутом пересылки пакета по сети можно назвать последовательность маршрутизаторов, через которые этот пакет будет перенаправлен в процессе следования к своему адресату.
Маршрутизация пакетов включает в себя две основные задачи: определение оптимального маршрута пересылки пакета по составной сети; собственно пересылка пакета по сети [1].
Для реализации задачи передачи данных сетевой уровень должен обладать информацией о топологии подсети связи (то есть о множестве всех маршрутизаторов) и выбирать нужный путь по этой подсети. Достаточно важно следить за тем, чтобы нагрузка на маршрутизаторы и линии связи была, по возможности, более равномерной.
Алгоритм маршрутизации реализуется той частью программного обеспечения сетевого уровня, которая отвечает за выбор выходной линии для отправки пришедшего пакета. При современном уровне развития сетевых технологий особые требования предъявляются к тому, чтобы алгоритм выбора маршрута обладал определенными свойствами – корректностью, простотой, надежностью, устойчивостью, справедливостью и оптимальностью. Во время работы большой сети постоянно происходят какие-то отказы аппаратуры и изменений топологии [2].
Магистерская работа выполняется в течении 2008-2009 гг. в соответствии с научным направлением кафедры «Электронные вычислительные машины» Донецкого национального технического университета.
Цель работы. Исследование и анализ работы алгоритма маршрутизации в сетевой топологии.
Идея работы. Рассмотрение частичного использования метода применения централизованной маршрутизации в компьютерной сети, при котором некий главный роутер является центром, а все соседние, непосредственно присоединенные к нему – второстепенными узлами. В таком случае для анализа работы сети удобно расположить маршрутизаторы в порядке последовательного чередования.
Основные задачи разработки и исследования. Для достижения поставленной цели в процессе исследования необходимо:
Предмет разработки и исследования. Компьютерная сеть.
Объект разработки и исследования. Устройства сетевого уровня – роутеры (маршрутизаторы).
Методология и методы исследования. В процессе исследования применяется формальный аппарат теории графов и алгоритмов маршрутизации.
Новизна полученных результатов заключается в использовании в качестве модели исследования конкретной разработанной топологии сети и механизма работы алгоритма маршрутизации для предоставления услуг обмена данными между узлами.
Состоит в применении выбора алгоритма работы роутера в конкретной топологии.
Основные результаты докладывались и обосновывались на четвертой международной научно-технической конференции студентов, аспирантов и молодых ученых по «Информатике и компьютерным технологиям».
При разработке алгоритмов маршрутизации часто преследуют одну или несколько из перечисленных ниже целей: оптимальность, простота и низкие непроизводительные затраты, живучесть и стабильность, быстрая сходимость, гибкость [3].
Альтернативная маршрутизация. Задача выбора оптимальных маршрутов относится к классу многопродуктовых задач с выпуклой целевой функцией и выпуклым множеством ограничений. Следовательно, существует единственный локальный минимум данной задачи, являющийся глобальным минимумом, для нахождения которого разработано достаточно большое число вычислительных методов [4].
Необходимо помнить, что абсолютно надежных протоколов маршрутизации не существует. При чрезмерной нагрузке отказать может любой протокол. Каких-то общепринятых стандартов настройки протоколов состояния канала нет [5].
IP-маршрутизация — простой процесс, который одинаков в сетях любого размера. Например, на рис. 1 показан процесс пошагового взаимодействия хоста А с хостом В в другой сети [6].
Рис. 1. Пример IP-маршрутизации для двух хостов и одного маршрутизатора.
Адаптивная маршрутизация – это основной вид алгоритмов маршрутизации, применяющихся маршрутизаторами в современных сетях со сложной топологией. Основывается на том, что маршрутизаторы периодически обмениваются специальной топологической информацией об имеющихся в интерсети сетях, а также о связях между маршрутизаторами. Обычно учитывается не только топология связей, но и их пропускная способность и состояние [7].
Устройство маршрутизатора: входные порты; коммутационный блок; выходные порты; маршрутный процессор [8].
Ведущие лидеры в разработке роутер-технологий [9]: Cisco; Juniper; Huawei; Fujitsu; Foundry; NEC.
Моделирование представляет собой мощный метод научного познания, при использовании которого исследуемый объект заменяется более простым объектом, называемым моделью. Основными разновидностями процесса моделирования можно считать два его вида - математическое и физическое моделирование. При физическом (натурном) моделировании исследуемая система заменяется соответствующей ей другой материальной системой, которая воспроизводит свойства изучаемой системы с сохранением их физической природы.
Возможности физического моделирования довольно ограничены. Оно позволяет решать отдельные задачи при задании небольшого количества сочетаний исследуемых параметров системы. Действительно, при натурном моделировании вычислительной сети практически невозможно проверить ее работу для вариантов с использованием различных типов коммуникационных устройств - маршрутизаторов, коммутаторов и т.п. Проверка на практике около десятка разных типов маршрутизатров связана не только с большими усилиями и временными затратами, но и с немалыми материальными затратами [10].
Рассматривается метод исследования алгоритма маршрутизации. Производится дифференцирование алгоритмов маршрутизации, основываясь на нескольких ключевых характеристиках. Во-первых, на работу результирующего протокола маршрутизации влияют конкретные задачи. Во-вторых, влияние различных типов алгоритмов маршрутизации на сеть и ресурсы. И наконец, алгоритмы маршрутизации используют разнообразные показатели, которые влияют на расчет оптимальных маршрутов.
В общем случае принцип работы маршрутизатора можно представить следующей последовательностью действий (рис. 2):
Рис. 2 – Алгоритм работы роутера (анимация: 6 кадров, 6 циклов, 31 Кб).
В некоторый начальный момент времени работы сети принято, что второстепенные маршрутизаторы (на рис. 3 обозначены номерами, начиная с №14) имеют информацию только о непосредственно подключенных к ним роутерам. Центральные роутеры с номерами от 1 до 13 содержат в своих таблицах информацию не только о непосредственных соседних маршрутизаторах, но и маршрутизаторах, расположенных через один (то есть на расстоянии с метрикой прохождения пути равной двум). В дальнейшем при функционировании сети и при поиске новых требуемых путей работают по алгоритмам маршрутизации только главные, более сложные в реализации, маршрутизаторы. Информацию о найденных путях они могут указывать второстепенным роутерам для возможности работы сети и корректной отправки пакетов. Сами же роутеры с простой реализацией поиском маршрутных путей не занимаются, а - только отправкой пакетов по данным о топологии сети в собственных таблицах маршрутизации.
Рис. 3 – Топология экспериментальной сети.
Алгоритм начинает заниматься поиском маршрутов только тогда, когда они реально требуются. Пусть необходимо найти путь между маршрутизаторами №1 и №8. Узел №1 генерирует специальный запрос маршрута Route Request и распространяет его по сети широковещательным способом. В больших сетях алгоритмом генерируется много широковещательных пакетов, поэтому для избежания излишней загрузки и для обнаружения адресата отправитель рассылает пакет запроса маршрута с шагом, равным 1. То есть запрос формируется для роутеров №14 и №16 (в примере). Если ответ не приходит и путь по-прежнему неопределен, то посылается еще один запрос, но с шагом, равным 2, и т.д. Таким образом, поиск, начавшийся в какой-то локальной области, все больше расширяет свой охват.
Когда после конкретного числа шагов запроса маршрута, находится необходимая информация, то формируется ответ о наличии пути Route Reply. Последний отправляется в обратном пути в источнику запроса. При этом узлы, стоящие на указанном пути, совершенно «бесплатно» получают информацию о маршруте к роутеру №8.
Рассматриваются проблемы перегрузки линий передачи данных. С каждой линией может быть связана вещественная переменная u, значение которой в пределах от 0.0 до 1.0 отражало было бы использование линии за последнее время. Такую усредненную оценку загруженности линии можно получить с помощью несложных вычислений, периодически замеряя мгновенную загруженность линии f (0 либо 1) и рассчитывая новое значение переменной u по формуле:
uнов=auст+(1-a)f,
где константа а определяет, насколько часто во времени маршрутизатор анализирует загруженность линии.
Когда значение переменной u начинает превышать некий пороговый уровень, это означает, что линия переходит в опасное состояние. Каждый приходящий пакет проходит проверку: если ему предстоит следовать по линии, находящейся в близком к перегрузке состоянии, то необходимо выбрать альтернативный путь.
Когда число пакетов, посылаемых хостами в сеть, не превышает ее пропускной способности, все они доставляются адресатам. При этом количество доставленных пакетов пропорционально количеству посланных. Однако по мере роста трафика маршрутизаторы перестают успевать обрабатывать все пакеты и начинают их терять. Когда пакетов достигает максимального уровня, производительность сети падает до низкого уровня.
В магистерской работе для достижения поставленной цели в процессе исследования решены следующие задачи:
При написании данного автореферата магистерская работа еще не завершена. Окончательное завершение: декабрь 2009 г. Полный текст работы и материалы по теме могут быть получены у автора или его руководителя после указанной даты.