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

Рассмотренные нами дистанционно-векторный алгоритм и алгоритм, основанный на состоянии линий, представляют собой не просто популярные алгоритмы маршрутизации. По сути, только эти два алгоритма и применяются на практике. Тем не менее за последние 30 лет исследователями было предложено множество других алгоритмов маршрутизации, варьирующихся от крайне простых до очень сложных. Один из простейших предложенных алгоритмов назывался маршрутизацией «горячей картофелины». Своим названием алгоритм обязан поведению маршрутизаторов — каждый маршрутизатор пытается как можно быстрее избавиться (переслать дальше) от пакета данных, передавая его по любой неперегруженной выходной линии, не обращая внимания на то, куда направляется эта линия. В основе другого широкого класса алгоритмов маршрутизации лежит точка зрения на пакетный трафик, как на потоки данных между отправителями и получателями. При таком подходе проблема выбора маршрута может быть сформулирована математически как задача оптимизации при ограничениях, известная как задача сетевых потоков. Еще одно множество алгоритмов маршрутизации, о которых следует сказать здесь несколько слов, обязаны своим происхождением телефонным сетям. Эти алгоритмы маршрутизации коммутируемых каналов представляют интерес для сетей с коммутацией пакетов в ситуациях резервирования ресурсов линии для каждого соединения, таких как пропускная способность части линии связи или объем буферов. И хотя формулировка задачи маршрутизации значительно отличается от ее формулировки для случая определения маршрутов наименьшей стоимости, у подобных алгоритмов маршрутизации есть довольно много общего, по крайне мере в том, что касается алгоритмов определения маршрутов.