Источник: Таненбаум Э. Компьютерные сети. 4-е изд. – СПб.: Питер, 2007. – c. 406-408.
Основная функция сетевого уровня заключается в выборе маршрута для пакетов от начальной до конечной точки. В большинстве сетей пакетам приходится про- ходить через несколько маршрутизаторов. Единственным исключением являют- ся широковещательные сети, но даже в них маршрутизация является важным во- просом, если отправитель и получатель находятся в разных сетях. Алгоритмы выбора маршрутов и используемые ими структуры данных являются главной це- лью при проектировании сетевого уровня.
Алгоритм маршрутизации реализуется той частью программного обеспече- ния сетевого уровня, которая отвечает за выбор выходной линии для отправки пришедшего пакета. Если подсеть использует дейтаграммную службу, выбор марш- рута для каждого пакета должен производиться заново, так как оптимальный маршрут мог измениться. Если подсеть использует виртуальные каналы, мар- шрут выбирается только при создании нового виртуального канала. После этого все информационные пакеты следуют по выбранному маршруту. Последний случай иногда называют сеансовой маршрутизацией, так как маршрут остается в силе на протяжении всего сеанса связи с пользователем (например, сеанса ре- гистрации на терминале или передачи файла).
Полезно понимать разницу между маршрутизацией, при которой системе приходится делать выбор определенного маршрута следования, и пересылкой — действием, происходящим при получении пакета. Можно представить себе мар- шрутизатор как устройство, в котором функционируют два процесса. Один из них обрабатывает приходящие пакеты и выбирает для них по таблице маршру- тизации исходящую линию. Такой процесс называется пересылкой. Второй про- цесс отвечает за заполнение и обновление таблиц маршрутизации. Именно здесь в игру вступает алгоритм маршрутизации.
Вне зависимости от того, отдельно ли выбираются маршруты для каждого па- кета или же только один раз для соединения, желательно, чтобы алгоритм выбо- ра маршрута обладал определенными свойствами — корректностью, простотой, надежностью, устойчивостью, справедливостью и оптимальностью. Правильность и простота вряд ли требуют комментариев, а вот потребность в надежности не столь очевидна с первого взгляда. Во время работы большой сети постоянно про- исходят какие-то отказы аппаратуры и изменения топологии. Алгоритм маршру- тизации должен уметь справляться с изменениями топологии и трафика без необ- ходимости прекращения всех задач на всех хостах и перезагрузки сети при каждой поломке маршрутизатора.
Алгоритм маршрутизации должен также обладать устойчивостью. Существу- ют алгоритмы выбора маршрута, никогда не приходящие в состояние равнове- сия, независимо от того, как долго они работают. Такие цели, как справедливость и оптимальность, могут показаться очевидными — вряд ли кто-нибудь станет воз- ражать против них, — однако они зачастую оказываются взаимоисключающими. Прежде чем пытаться искать приемлемое соотношение справедливости и оп- тимальности, следует решить, что именно мы будем стремиться оптимизировать. Можно попробовать минимизировать среднее время задержки или увеличить об- щую пропускную способность сети. Однако эти цели также противоречат друг другу, поскольку работа любой системы с очередями вблизи максимума произ- водительности предполагает долгое стояние в очередях. В качестве компромисса многие сети стараются минимизировать количество пересылок для каждого па- кета, поскольку при этом снижается время прохождения пакета по сети, а также снижается нагрузка на сеть, в результате чего улучшается пропускная способ- ность.
Алгоритмы выбора маршрута можно разбить на два основных класса: адап- тивные и неадаптивные. Неадаптивные алгоритмы не учитывают при выборе маршрута топологию и текущее состояние сети и не измеряют трафик на лини- ях. Вместо этого выбор маршрута для каждой пары станций производится зара- нее, в автономном режиме, и список маршрутов загружается в маршрутизаторы во время загрузки сети. Такая процедура иногда называется статической марш- рутизацией.
Адаптивные алгоритмы, напротив, изменяют решение о выборе маршрутов при изменении топологии и также часто в зависимости от загруженности линий. Адаптивные алгоритмы отличаются источниками получения информации (такие источники могут быть, например, локальными, если это соседние маршрутизато- ры, либо глобальными, если это вообще все маршрутизаторы сети), моментами изменения маршрутов (например, через определенные равные интервалы време- ни, при изменении нагрузки или при изменении топологии) и данными, исполь- зующимися для оптимизации (расстояние, количество транзитных участков или ожидаемое время пересылки). В следующих разделах мы обсудим различные ал- горитмы маршрутизации, как статические, так и динамические.