Курсовые и лабораторные работы Математика решение задач Электротехника Лабораторные работы по электронике Физика Информатика На главную
Реализация сервиса виртуальные каналы Алгоритмы маршрутизации Метод заливки Маршрутизация Иерархическая маршрутизация Широковещательная маршрутизация Многоадресная рассылка Борьба с флуктуациями

Алгоритмы маршрутизации

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

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

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

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

Алгоритм маршрутизации должен также обладать устойчивостью. Существуют алгоритмы выбора маршрута, никогда не приходящие в состояние равновесия, независимо от того, как долго они работают. Такие цели, как справедливость и оптимальность, могут показаться очевидными — вряд ли кто-нибудь станет возражать против них, — однако они зачастую оказываются взаимоисключающими. Для примера рассмотрим ситуацию, показанную на рис. 5.4. Предположим, что трафик между станциями А и А', В и В', а. также С и С' настолько интенсивный, что горизонтальные линии связи оказываются полностью насыщенными. Чтобы максимизировать общий поток данных, трафик между станциями X и X' следовало бы совсем отключить. Однако станции X и X' скорее всего, имеют другую точку зрения по данному вопросу. Очевидно, необходим компромисс между справедливым выделением трафика всем станциям и оптимальным использованием канала в глобальном смысле.

Рис. 5.4. Конфликт справедливости и оптимальности

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

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

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


Лекции по сопромату http://fihel.ru/
Сетевой уровень Управление доступом У каждого хоста и маршрутизатора в Интернете есть IP-адрес