Эндрю Уэзеролл - Компьютерные сети. 5-е издание

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

Такие цели, как справедливость и эффективность, могут показаться очевидными — вряд ли кто-нибудь станет возражать против них, — однако они зачастую оказываются взаимоисключающими. Для примера рассмотрим ситуацию, показанную на рис. 5.4.

Предположим, что трафик между станциями A и A ', B и B', а также C и С' настолько интенсивный, что горизонтальные линии связи оказываются полностью насыщенными. Чтобы максимизировать общий поток данных, трафик между станциями X и X' следовало бы совсем отключить. Однако станции X и X', скорее всего, имеют другую точку зрения по данному вопросу. Очевидно, необходим компромисс между справедливым выделением трафика всем станциям и оптимальным использованием канала в глобальном смысле.

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

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

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

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

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

5.2.1. Принцип оптимальности маршрута

Прежде чем перейти к рассмотрению отдельных алгоритмов, возможно, следует привести некие общие положения, описывающие оптимальные маршруты, вне зависимости от топологии или трафика. Такой основополагающей идеей является принцип оптимальности (Беллман, 1957). В соответствии с этим принципом, если маршрутизатор J располагается на оптимальном маршруте от маршрутизатора I к маршрутизатору K, то оптимальный маршрут от маршрутизатора J к маршрутизатору K совпадет с частью первого маршрута. Чтобы убедиться в этом, обозначим часть маршрута от маршрутизатора I к маршрутизатору J как г 1, а остальную часть маршрута — r 2. Если бы существовал более оптимальный маршрут от маршрутизатора J к маршрутизатору K , чем r 2, то его можно было объединить с r 1, чтобы улучшить маршрут от маршрутизатора I к маршрутизатору K, что противоречит первоначальному утверждению о том, что маршрут г 1г 2является оптимальным.