Маршрутизация пакетов
Ключевые слова и синонимы
Маршрутизация с промежуточным хранением; оптимально минимизированное производственное планирование
Постановка задачи
Набор пакетов необходимо переправить из множества указанных источников в множество указанных пунктов назначения в произвольной сети. Лейтон, Мэггз и Рао [ ] рассмотрели модель, в которой эта задача разбивается на две отдельных подзадачи: первая представляет собой задачу выбора пути, в которой для каждого указанного пакета 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 выглядит следующим образом.
Теорема [5]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d), в котором размер очередей при каждом ребре всегда ограничен константой.
Изначальное доказательство теоремы в статье о LMR не является конструктивным. Оно использует лемму о локальности [ ] для доказательства существования такого плана, но не дает способов его нахождения. В своей книге [10] Шайделер показал, что фактически существует план длины O(c + d), размер очередей при ребрах в котором ограничен 2, и дал более простое доказательство изначального результата LMR. В последующей статье Лейтон, Мэггз и Рича [6] в 1999 году предложили конструктивную версию LMR, которая выглядит следующим образом.
Теорема [6]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d). Более того, этот план может быть найден за время 0(p\og1+€ p\og*(c+ d)) для любого e>0, где p – сумма длин путей, взятых по пакетам, а " включено в константу, спрятанную в скобках O большого в выражении для длины плана.
Алгоритм в этой статье является рандомизированным, хотя авторы утверждают, что его можно дерандомизировать с помощью метода условных вероятностей. Тем не менее, хотя алгоритм Лейтона, Мэггза и Ричи является конструктивным, он остается оффлайновым; иначе говоря, для построения расписания требуется полное знание всех пакетов в сети и точных путей, по которым будет проходить каждый из них. В исходной работе LMR также был приведен простой рандомизированный онлайновый алгоритм, который, за счет назначения задержек пакетам независимым и равномерно случайным образом в зависимости от соответствующего интервала, позволяет составить намного более эффективный график по сравнению с результатами работы жадных алгоритмов, хотя и не настолько эффективный, как оффлайновые построения.
Теорема [5]. Существует простой рандомизированный оффлайновый алгоритм для получения с высокой вероятностью плана длины O(c + dlog(Nd)), использующего очереди размера O(log(Nd)), где c обозначает нагруженность, d - протяженность, а N - число пакетов.
В специальном случае, когда предполагается, что все пакеты следуют по кратчайшим путям в сети, Мейер ауф дер Хайде и Воккинг создали простой рандомизированный онлайновый алгоритм, который с высокой вероятностью вычисляет план из O(c + d + log Nd) шагов, однако очереди могут быть иметь размер O(c) [7]. Для произвольных путей онлайновый результат LMR был в конечном итоге улучшен до O(c + d + log +€ N) шагов для любого e>0 с высокой вероятностью, с чем можно подробнее ознакомиться в серии из двух работ Рабани и Тардош [ ], а также Рабани и Островского [8]. Онлайновые протоколы также изучались в условиях, когда дополнительные пакеты динамически впрыскиваются в сеть в состязательной ситуации; обзор см. в работе [ ].
Затем обсуждение ненадолго вернулось к первой задаче, а именно к предварительному построению набора путей. Очевидно, задача заключается в нахождении для конкретного множества пакетов с заранее заданными источниками и пунктами назначения множество путей, которое минимизирует сумму с + d. Шринивасан и Тео [ ] разработали оффлайновый алгоритм, выдающий набор путей, для которого сумма c + d доказуемо отличается от оптимальной не более чем на константный коэффициент. Вместе с оффлайновым результатом LMR получаем задачу аппроксимации с постоянным коэффициентом для оффлайновой задачи маршрутизации пакетов с промежуточным хранением. Стоит отметить важность подхода, стремящегося минимизировать c + d, а не только c; получить планы, отличающиеся на константный коэффициент от оптимальных для нагруженности c, очень непросто, и было показано, что это связано с разрывом целостности при управлении несколькими товарными потоками [1,2].
Применение
Эмуляция сети