Маршрутизация пакетов

Ключевые слова и синонимы

Маршрутизация с промежуточным хранением; оптимально минимизированное производственное планирование

Постановка задачи

Набор пакетов необходимо переправить из множества указанных источников в множество указанных пунктов назначения в произвольной сети. Лейтон, Мэггз и Рао [ ] рассмотрели модель, в которой эта задача разбивается на две отдельных подзадачи: первая представляет собой задачу выбора пути, в которой для каждого указанного пакета i с источником [math]\displaystyle{ s_i }[/math] и пунктом назначения [math]\displaystyle{ t_i }[/math] предварительно выбирается простой (то есть с неповторяющимися ребрами) путь [math]\displaystyle{ P_i }[/math] по сети из [math]\displaystyle{ s_i }[/math] в [math]\displaystyle{ t_i }[/math]. Пакеты перемещаются по сети в режиме, допускающем промежуточное хранение: каждый раз, когда пакет пересылается дальше, он движется вдоль выбранного звена предварительно выбранного пути. Предполагается, что по каждому отдельному звену в один заданный глобальный (синхронный) такт времени может перемещаться только один пакет. Таким образом, в случае конкуренции за проход по звену пакеты, ожидающие пересылки, сохраняются в локальной очереди звена (также определяются специальные очереди вершин-источников и пунктов назначения неограниченного размера, хранящие пакеты в начальных и конечных точках маршрутов). Вторая задача и основной результат исследования Лейтона, Мэггза и Рао (получивший название результата LMR) представляют собой задачу планирования: в ней необходимо определить, в случае наличия у звена непустой очереди, какой пакет должен пройти по звену на следующем такте (после чего он, как предполагается, немедленно встанет в очередь звена для следующего прыжка). Задача заключается в планировании пересылки пакетов таким образом, чтобы минимизировать максимальное время, необходимое пакету для достижения точки назначения.

Два параметра сети, наряду с предварительно выбранными путями, имеют важное значение. Одним из них является нагруженность (c), определяемая как максимальное количество путей, использующих одно и то же звено сети. Другим оказывается протяженность (d), равная длине самого длинного пути, проходимого любым из пакетов по сети. Очевино, что оба значения c и d представляют собой нижнюю границу любого плана, направляющего все пакеты к пунктам назначения. Легко заметить, что всегда существует план с длиной не более cd. На самом деле любой план, в котором ни одно звено не простаивает, если имеется пакет, который может использовать его на данном такте, гарантированно завершит работу за cd шагов, поскольку каждый пакет проходит не более d звеньев и в каждом звене может быть задержан из-за других пакетов не более c - 1 раз.

Основные результаты

Удивительный и замечательный результат LMR выглядит следующим образом.