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

Для принятия решения о выборе направления маршрутизатор должен иметь информацию о текущем состоянии сети. Эта информация получается и обрабатывается с помощью алгоритмов маршрутизации и фиксируется в памяти маршрутизатора в виде таблицы маршрутизации.

Алгоритмы маршрутизации включают процедуры:

Различают несколько типов алгоритмов маршрутизации. В фиксированных алгоритмах информация о маршрутах составляется и заносится в память маршрутизатора администратором сети. В случайных алгоритмах выбор направления передачи пакета (выбор выходного порта) в маршрутизаторах случаен. В алгоритмах лавинной маршрутизации пакет передается во всех возможных направлениях, что ускоряет доставку данного пакета, но лишь в условиях малой нагрузки. Наиболее популярны алгоритмы адаптивной маршрутизации, на основе которых разработаны адаптивные протоколы маршрутизации — RIP (Routing Information Protocol) и OSPF (Open Shortest Path First), называемые также методами маршрутизации.

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

Протокол RIP основан на алгоритме Беллмана-Форда и используется преимущественно на нижних уровнях иерархии сети. Информация о любом изменении в сети рассылается в алгоритме RIP волнообразно, а в сетях, работающих в соответствии с методом OSPF, лавинообразно.

Каждый маршрутизатор, работающий по алгоритму RIP, периодически широковещательно рассылает по сети сведения о доступности для него всех известных ему маршрутизаторов. Например, доступность некоторого маршрутизатора А может характеризоваться расстоянием до маршрутизатора А и длиной очереди к нему (или объемом доступной в А буферной памяти). Несмотря на медленную сходимость, для сетей сравнительно небольших масштабов алгоритм Беллмана-Форда вполне приемлем.

Алгоритм Беллмана-Форда относится к алгоритмам DVA (Distance Vector Algorithms). В DVA рельеф () — это оценка кратчайшего пути от узла к узлу . Оценка (условно назовем ее расстоянием) может выражаться временем доставки, надежностью доставки или числом узлов коммутации (измерение в хопах) на данном маршруте. В таблице маршрутизации узла каждому из остальных узлов отводится одна строка со следующей информацией:

Например, для рис. 1 в узле строка для выглядит как ()= ()

Пусть изменилась задержка () на маршруте от к через узел причем так, что () стала меньше, чем (). Тогда в строке таблицы маршрутизации узла корректируется (), () изменяется на и, кроме того, всем соседям узла посылается сообщение об измененном (). Например, в некотором соседнем узле при этом будет изменено значение () = () + (). Мы видим, что возникает итерационный процесс корректировки маршрутной информации в узлах маршрутизации.

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

Обозначим кратчайшее расстояние от к некоторому узлу через . Разделим узлы на три группы: 1) перманентные, для которых уже рассчитано; 2) активные, для которых получена некоторая промежуточная оценка , возможно не окончательная; 3) пассивные, еще не вовлеченные в итерационный процесс. В табл. 1 представлены значения на последовательных итерациях.

Итерационный процесс начинается с отнесения узла к группе перманентных. Далее определяются узлы, смежные с узлом . Это узлы и , которые включаются в группу активных узлов. Включение в группу активных отмечается указанием в клетке таблицы рядом с оценкой расстояния активного узла также имени узла, включаемого на этом шаге в число перманентных. Так, для узлов и определяются расстояния = 3, = 1 и для них в таблице отмечается узел . На следующем шаге узел с минимальной оценкой (в нашем примере это узел ) включается в группу перманентных, а узлы, смежные с узлом , — в группу активных, для них оцениваются расстояния = 8 и = 13 и они помечаются символом . Теперь среди пробных узлов минимальную оценку имеет узел , он включается в группу перманентных узлов, узел — в группу пробных и для всех пробных узлов, смежных с , рассчитываются оценки. Это, в частности, приводит к уменьшению оценки узла с 8 на 5. Акт уменьшения фиксируется (в табл. 1 это отражено, во-первых, скобками, а во-вторых, заменой у узла метки на ). Если же новая оценка оказывается больше прежней, то она игнорируется. Этот процесс продолжается, пока все узлы не окажутся в группе перманентных. Теперь виден кратчайший путь от узла к любому другому узлу или, что то же самое, от к . Это последовательность конечных отметок в строках таблицы, начиная с последнего узла . Так, для узла = имеем в строке отметку , в строке — отметку , в строке — отметку и т.д. и окончательно кратчайший путь есть -----.

Находит применение еще один протокол маршрутизации — протокол IGRP (Interior Gateway Routing Protocol), разработанный фирмой Cisco. Он аналогичен алгоритму RIP, но развивает его в направлениях:

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