Маршрутизация пакетов
Ключевые слова и синонимы
Маршрутизация с промежуточным хранением; планирование набора заданий
Постановка задачи
Набор пакетов необходимо переправить из множества указанных источников в множество указанных пунктов назначения в произвольной сети. Лейтон, Мэггз и Рао [5] рассмотрели модель, в которой эта задача разбивается на две отдельных подзадачи: первая представляет собой задачу выбора пути, в которой для каждого указанного пакета 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 выглядит следующим образом.
Теорема 1 [5]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d), в котором размеры очередей при каждом ребре всегда ограничены константой.
Доказательство теоремы в статье о LMR не является конструктивным. Оно использует лемму о локальности [3] для доказательства существования такого плана, но не дает способов его нахождения. В своей книге [10] Шайделер показал, что фактически существует план длины O(c + d), размер очередей при ребрах в котором ограничен 2, и дал более простое доказательство изначального результата LMR. В последующей статье Лейтон, Мэггз и Рича [6] в 1999 году предложили конструктивную версию LMR, которая выглядит следующим образом.
Теорема 2 [6]. Для любой сети G с заранее определенным множеством путей P с нагруженностью c и протяженностью d существует план длины O(c + d). Более того, этот план может быть найден за время [math]\displaystyle{ O(p \; log^{1 + \epsilon} p \; log^* (c+d)) }[/math] для любого [math]\displaystyle{ \epsilon \gt 0 }[/math], где p – сумма длин путей, взятая по пакетам, а [math]\displaystyle{ \epsilon }[/math] включено в константу, спрятанную в скобках O большого в выражении для длины плана.
Алгоритм в этой статье является рандомизированным, хотя авторы утверждают, что его можно дерандомизировать с помощью метода условных вероятностей. Тем не менее, хотя алгоритм Лейтона, Мэггза и Ричи является конструктивным, он остается оффлайновым; иначе говоря, для построения плана требуется полное знание всех пакетов в сети и точных путей, по которым будет проходить каждый из них. В исходной работе LMR также был приведен простой рандомизированный онлайновый алгоритм, который, за счет назначения задержек пакетам независимым и равномерно случайным образом из соответствующего интервала, позволяет составить намного более эффективный план по сравнению с результатами работы жадных алгоритмов, хотя и не настолько эффективный, как оффлайновые построения.
Теорема 3 [5]. Существует простой рандомизированный оффлайновый алгоритм для получения с высокой вероятностью плана длины O(c + d log(Nd)), использующего очереди размера O(log(Nd)), где c обозначает нагруженность, d - протяженность, а N - число пакетов.
Для специального случая, в котором предполагается, что все пакеты следуют по кратчайшим путям в сети, Мейер ауф дер Хайде и Вёккинг создали простой рандомизированный онлайновый алгоритм, который с высокой вероятностью вычисляет план длиной O(c + d + log Nd) шагов, однако очереди могут иметь размер O(c) [7]. Для произвольных путей онлайновый результат LMR был в конечном итоге улучшен до [math]\displaystyle{ O(c + d + log^{1 + \epsilon} N) }[/math] шагов для любого [math]\displaystyle{ \epsilon \gt 0 }[/math] с высокой вероятностью, с чем можно подробнее ознакомиться в серии из двух работ Рабани и Тардош [9], а также Рабани и Островского [8]. Онлайновые протоколы также изучались для формулировки задачи, в которой дополнительные пакеты динамически впрыскиваются в сеть в состязательной ситуации; обзор исследований см. в работе [10].
Вернемся ненадолго к первой задаче, а именно – к предварительному построению набора путей. Очевидно, наша цель заключается в нахождении для конкретного множества пакетов, с заранее заданными источниками и пунктами назначения, множества путей, которое минимизирует сумму с + d. Шринивасан и Тео [12] разработали оффлайновый алгоритм, выдающий множество путей, для которого сумма c + d доказуемо отличается от оптимальной не более чем на константный коэффициент. Вместе с оффлайновым результатом LMR получаем аппроксимационную задачу с постоянным коэффициентом для оффлайновой задачи маршрутизации пакетов с промежуточным хранением. Стоит отметить важность подхода, стремящегося минимизировать c + d, а не только c; получить планы, отличающиеся на константный коэффициент от оптимальных для нагруженности c, очень непросто, и было показано, что это связано с разрывом целостности при управлении несколькими товарными потоками [1, 2].
Применение
Эмуляция сети
Как правило, гостевая сеть G эмулируется хостовой сетью H посредством вложения G в H. Узлы сети G отображаются на узлы сети H, а ребра G – на пути в H. Если P – множество из e путей (каждый из которых соответствует ребру в гостевой сети G), то нагруженность и протяженность определяются аналогично задаче с множеством путей P, то есть c обозначает максимальное количество путей, использующих любое ребро H, а d – длину самого длинного пути в P. Кроме этого, нагрузка l определяется как максимальное число вершин в G, отображенных на одну вершину H. После вложения G в H сеть H может эмулировать сеть G следующим образом. Каждая вершина H эмулирует локальные вычисления, выполняемые l (или меньшим числом) вершин, отображаемых на нее, за время O(l). Тогда для каждого пакета, пересылаемого вдоль ребра сети G, сеть H пересылает пакет по соответствующему пути во вложении; согласно оффлайновому результату LMR, на это требуется O(c + d) шагов. Таким образом, H может эмулировать каждый шаг в G за O(c + d + l) шагов.
Планирование набора заданий
Рассмотрим задачу планирования для заданий [math]\displaystyle{ j_1, ..., j_r }[/math] и машин [math]\displaystyle{ m_1, ..., m_s }[/math], в которой каждое задание должно выполняться на заданной последовательности машин (в заданном порядке). Предположим, что каждое задание тратит единицу времени на каждой машине и что ни одна машина не должна выполнять какое-либо задание более одного раза (на языке составления расписаний имеет место ациклическая задача планирования с единичными заданиями без вытеснения). Существует отображение последовательностей машин на пути и заданий на пакеты, представляющее собой иную формулировку основной задачи маршрутизации пакетов, в которой c теперь обозначает максимальное количество заданий, которые должны выполняться на любой отдельной машине, а d – максимальное количество различных машин, выполняющих любое отдельное задание; для соответствующего экземпляра задачи маршрутизации пакетов O(c) теперь обозначает нагруженность, а O(d) – протяженность. Оффлайновый результат LMR показывает, что существует план, при котором все задания выполняются за O(c + d) шагов и, кроме того, время ожидания между последовательными машинами для каждого задания составляет не более константного количества шагов (а размер очередей заданий, ожидающих некоторую конкретную машину, всегда будет ограничен константой). Техники, аналогичные использованным в статье о LMR, были впоследствии применены к более общим задачам планирования набора заданий; см. работы [4, 11].
Открытые вопросы
Основная нерешенная проблема заключается в том, возможно ли рандомизированное онлайновое планирование пакетов, соответствующее границам оффлайнового алгоритма LMR, составляющим O(c + d). Приведенная в работе [8] граница близка к нему, но все же логарифмически возрастает вместе с ростом числа пакетов.
В контексте задачи планирования набора заданий неизвестно, можно ли улучшить аппроксимационный алгоритм с константным коэффициентом для ациклической задачи планирования набора заданий с единичной длиной без вытеснения, подразумеваемой LMR, до PTAS. Неизвестно также, существует ли аппроксимационный алгоритм с константным коэффициентом для заданий произвольной длины.
Литература
1. Andrews, M., Zhang, L.: Hardness of the Undirected Congestion Minimization Problem. Proceedings of the 37th Annual CM Symposium on Theory of Computing, pp. 284-293 (2005)
2. Chuzhoy, J., Naor, J.: New Hardness Results for Congestion Minimization and Machine Scheduling. Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 28-34. ACM, New York (2004)
3. Erdos, P., Lovasz, L.: Problems and results on 3-chromatic hypergraphs and some related questions. Colloq. Math. Soc. Janos Bolyai 10,609-627 (1975)
4. Goldberg, L.A., Patterson, M., Srinivasan, A., Sweedick, E.: Bet ter Approximation Guarantees for Job-Shop Scheduling. SIAM J. Discret. Math. 14(1), 67-92 (2001)
5. Leighton, F.T., Maggs, B.M., Rao, S.B.: Packet routing and job-shop scheduling in O(congestion+dilation) steps. Combinatorica 14(2), 167-180(1994)
6. Leighton, F.T., Maggs, B.M., Richa, A.W.: Fast algorithms for finding O(congestion+dilation) packet routing schedules. Combinatorica 19(3), 375-401 (1999)
7. Meyer auf der Heide, F., Vocking, B.: Shortest-Path Routing in Arbitrary Networks. J. Algorithms 31 (1), 105-131 (1999)
8. Ostrovsky, R., Rabani, Y.: Universal O(congestion + dilation+log1 + "N) Local Control Packet Switching Algorithm. In: Proceedings of The Twenty-Ninth ACM Symposium on Theory of Computing, pp. 644-653 (1997)
9. Rabani, Y., Tardos, E.: Distributed Packet Switching in Arbitrary Networks. In: the 28th ACM Symposium on Theory of Computing, pp. 366-376 (1996)
10. Scheideler, C.: Universal Routing Strategies for Interconnection Networks. In: Lecture Notes in Computer Science, vol. 1390. Springer (1998)
11. Shmoys, D.B., Stein, C., Wein, J.: Improved Approximation Algorithms for Shop Scheduling Problems. SIAM J. Comput. 23(3), 617-632(1994)
12. Srinivasan, A., Teo, C.P.: A Constant-Factor Approximation Algorithm for Packet Routing and Balancing Local vs. Global Criteria. SIAM J. Comput. 30(6), 2051-2068 (2000)
