Введение. 
Исследование алгоритма Дейкстры для маршрутизации пакетов в компьютерной сети

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

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

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