Раздел 7 Принципы маршрутизации
7.1 Алгоритмы выбора маршрутов
7.1.1 Алгоритмы выбора маршрута являются частью программного обеспечения сетевого уровня, ответственный за выбор выходной линии, по которой следует отправить пришедший пакет. Если подсеть использует дейтограммную службу, выбор маршрута для каждого пакета должен производиться заново, т.к. оптимальный маршрут мог измениться. Если подсеть использует виртуальные каналы, маршрут выбирается только при создании нового виртуального канала. После этого все информационные пакеты следуют по выбранному маршруту. Последний случай иногда называют сеансовой маршрутизацией, т.к. маршрут остается в силе на протяжении всего сеанса пользователя.
Однако, в обоих случаях алгоритм выбора маршрута должен обладать определенными свойствами: правильностью, простотой, надежностью, устойчивостью, справедливостью и оптимальностью. За период работы большой сети постоянно происходят различные отказы аппаратуры и изменения топологии. Алгоритм маршрутизации должен уметь справляться с изменениями топологии и трафика без необходимости прекращения всех задач на всех хостах и перегрузки сети каждой поломке маршрутизатора.
Алгоритм выбора маршрута должен также обладать устойчивостью. Существуют алгоритмы выбора маршрута, никогда не приходящие в состоянии равновесия, независимо от того, как долго они работают. Такие цели, как справедливость и оптимальность, могут показаться очевидными. Однако, эти цели часто оказываются взаимоисключающими. Для примера рассмотрим ситуацию, изображенную на рисунке 63. Конфликт справедливости и оптимальности.
Рисунок 66 - Конфликт справедливости и оптимальности
7.1.2. Предположим, трафик между станциями А и А’, В и В’, С и С’ настолько интенсивный, что горизонтальные линии связи оказываются полностью насыщенными. Чтобы максимизировать общий поток данных, трафик между станциями Х и Х’ следовало бы совсем отключить. Однако, станции Х и Х’, скорее всего, имеют другую точку зрения в данном вопросе. Очевидно, необходим компромисс между справедливым выделением трафика всем станциям и оптимальным использованием канала.
Прежде чем попытаться найти приемлемое соотношение справедливости и оптимальности, следует решить, что именно мы будем пытаться оптимизировать. Можно попытаться минимизировать среднее время задержки или увеличить общую пропускную способность сети. Однако обе эти цели также противоречат друг другу, поскольку работа любой системы с очередями вблизи максимума производительности предполагает долгое состояние в очередях. В качестве компромисса многие сети стараются минимизировать количество пересылок для каждого пакета, поскольку при этом снижается время прохождения пакета по сети, а также снижается нагрузка на сеть, в результате чего улучшается пропускная способность.
7.1.3. Алгоритмы выбора маршрута разбить на два основных класса: адаптивные и неадаптивные.
Неадаптивные алгоритмы не учитывают при выборе маршрута топологии и текущего состояния сети, не изменяют трафик в линиях. Вместо этого выбор маршрута для каждой пары станции производится заранее, в автономном режиме, и список маршрутов загружается в маршрутизаторы во время загрузки сети. Такая процедура иногда называется статической маршрутизацией.
Адаптивные алгоритмы, напротив, изменяют решение о выборе маршрутов при изменении топологии и также часто в зависимости от загруженности линий. Адаптивные алгоритмы различаются по тому, где они получают информацию (например, локально, от соседних маршрутизаторов или от всех маршрутизаторов), когда изменяют маршруты (через определенные равные интервалы времени, при изменении нагрузки или при изменении топологии) и какие данные используются для оптимизации (расстояние, количество транзитных участков или ожидаемое время пересылки).