Источник: Інформатика та комп'ютерні технології — 2008 / Матеріали IV науково-технічної конференції молодих учених та студентів. — Донецьк, ДонНТУ — 2008, с. 89-91.
В компьютерных сетях применяется большое количество алгоритмов маршрутизации. Именно сетевой уровень модели OSI занимается разработкой маршрутов доставки пакетов от отправителя к получателю. Чтобы добраться до пункта назначения, пакету может потребоваться преодолеть несколько транзитных участков между маршрутизаторами. Сетевой уровень является самым низким уровнем, который имеет дело с передачей данных по всему пути от одного конца до другого.
Для достижения данной цели сетевой уровень должен обладать информацией о топологии подсети связи (то есть о множестве всех маршрутизаторов) и выбирать нужный путь по этой подсети. Он должен также заботиться о том, чтобы нагрузка на маршрутизаторы и линии связи была, по возможности, более равномерной.
Алгоритм маршрутизации реализуется той частью программного обеспечения сетевого уровня, которая отвечает за выбор выходной линии для отправки пришедшего пакета. Желательно, чтобы алгоритм выбора маршрута обладал определенными свойствами – корректностью, простотой, надежностью, устойчивостью, справедливостью и оптимальностью. Во время работы большой сети постоянно происходят какие-то отказы аппаратуры и изменений топологии.
Адаптивные алгоритмы изменяют решение о выборе маршрутов при изменении топологии и также часто в зависимости от загруженности линий. В общем случае данные алгоритмы маршрутизации отличаются источниками получения информации (такие источники могут быть, например, локальными, если это соседние маршрутизаторы, либо глобальными, если это вообще все маршрутизаторы сети), моментами изменения маршрутов (например, через определенные равные интервалы времени, при изменении нагрузки или при изменении топологии) и данными, использующимися для оптимизации (расстояние, количество транзитных участков или ожидаемое время пересылки). Централизованная адаптивная маршрутизация основана на использовании информации, получаемой от центра маршрутизации.
В данной работе рассматривается частичное использование метода применения централизованной маршрутизации, при котором некий главный роутер является центром, а все соседние, непосредственно присоединенные к нему – второстепенными. В таком случае для анализа работы сети удобно расположить маршрутизаторы с простым и сложным алгоритмами в «шахматном» виде.
В некоторый начальный момент времени работы сети принято, что второстепенные маршрутизаторы имеют информацию только о непосредственно подключенных к ним роутерам. Центральные роутеры содержат в своих таблицах информацию не только о непосредственных соседних маршрутизаторах, но и маршрутизаторах, расположенных через один (то есть на расстоянии с метрикой прохождения пути равной двум). В дальнейшем при функционировании сети и при поиске новых требуемых путей работают по алгоритмам маршрутизации только главные, более сложные в реализации, маршрутизаторы. Информацию о найденных путях они могут указывать второстепенным роутерам для возможности работы сети и корректной отправки пакетов. Сами же роутеры с простой реализацией поиском маршрутных путей не занимаются, а - только отправкой пакетов по данным о топологии сети в собственных таблицах маршрутизации.
Алгоритм начинает заниматься поиском маршрутов только тогда, когда они реально требуются. Пусть необходимо найти путь между маршрутизаторами №1 и №8. Узел №1 генерирует специальный запрос маршрута Route Request и распространяет его по сети широковещательным способом. В больших сетях алгоритмом генерируется много широковещательных пакетов, поэтому для избежания излишней загрузки и для обнаружения адресата отправитель рассылает пакет запроса маршрута с шагом, равным 1. Если ответ не приходит и путь по-прежнему неопределен, то посылается еще один запрос, но с шагом, равным 2, и т.д. Таким образом, поиск, начавшийся в какой-то локальной области, все больше расширяет свой охват.
Когда после конкретного числа шагов запроса маршрута, находится необходимая информация, то формируется ответ о наличии пути Route Reply. Последний отправляется в обратном пути в источнику запроса. При этом узлы, стоящие на указанном пути, совершенно «бесплатно» получают информацию о маршруте к роутеру №8.
Если в сети происходит обрыв связи между какими-либо маршрутизаторами, то происходит немедленное распространение сообщения о недействительности путей, лежащих через данный участок. Если маршрут является задействованным в передаче пакетов, происходит поиск и переключение на другой путь.
Статистика использования линий сети и борьба с перегрузкой. Каждый маршрутизатор может очень просто следить за использованием своих выходных линий и других ресурсов. Например, с каждой линией может быть связана вещественная переменная u, значение которой в пределах от 0.0 до 1.0 отражало было бы использование линии за последнее время.
Когда значение переменной u начинает превышать некий пороговый уровень, это означает, что линия переходит в опасное состояние. Каждый приходящий пакет проходит проверку: если ему предстоит следовать по линии, находящейся в близком к перегрузке состоянии, то необходимо выбрать альтернативный путь.
Когда число пакетов, посылаемых хостами в сеть, не превышает ее пропускной способности, все они доставляются адресатам. При этом количество доставленных пакетов пропорционально количеству посланных. Однако по мере роста трафика маршрутизаторы перестают успевать обрабатывать все пакеты и начинают их терять. Когда пакетов достигает максимального уровня, производительность сети падает до низкого уровня.