Маршрутизация пакетов: различия между версиями

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

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