Маршрутизация пакетов: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Маршрутизация с промежуточным хранением; | Маршрутизация с промежуточным хранением; планирование набора заданий | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 30: | Строка 30: | ||
Вернемся ненадолго к первой задаче, а именно к предварительному построению набора путей. Очевидно, наша цель заключается в нахождении для конкретного множества пакетов, с заранее заданными источниками и пунктами назначения, множества путей, которое минимизирует сумму с + d. Шринивасан и Тео [ ] разработали оффлайновый алгоритм, выдающий множество путей, для которого сумма 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) шагов. | |||
'''Планирование набора заданий''' | |||
Рассмотрим задачу планирования для заданий j1, ..., jr и машин m1, ..., ms, в которой каждое задание должно выполняться на заданной последовательности машин (в заданном порядке). Предположим, что каждое задание тратит единицу времени на каждой машине и что ни одна машина не должна выполнять какое-либо задание более одного раза (на языке составления расписаний имеет место не упреждающая ациклическая задача планирования с единичными заданиями). Существует отображение последовательностей машин на пути и заданий на пакеты, представляющее собой иную формулировку основной задачи маршрутизации пакетов, в которой c теперь обозначает максимальное количество заданий, которые должны выполняться на любой отдельной машине, а d – максимальное количество различных машин, выполняющих любое отдельное задание; для соответствующего экземпляра задачи маршрутизации пакетов O(c) теперь обозначает нагруженность, а O(d) – протяженность. Оффлайновый результат LMR показывает, что существует план, при котором все задания выполняются за O(c + d) шагов и, кроме того, время ожидания между последовательными машинами для каждого задания составляет не более константного количества шагов (к тому же размер очереди заданий, ожидающих некоторую конкретную машину, всегда будет ограничен константой). Техники, аналогичные использованным в статье о LMR, были впоследствии применены к более общим задачам планирования набора заданий; см. работы [4, 11]. | |||
== Открытые вопросы == | |||
Основная нерешенная проблема заключается в том, существует ли рандомизированное онлайновое планирование пакетов, соответствующее границам оффлайнового алгоритма LMR,составляющим O(c + d). Приведенная в работе [ ] граница близка к нему, но все же логарифмически возрастает вместе с ростом числа пакетов. | |||
В контексте задачи планирования набора заданий неизвестно, можно ли улучшить алгоритм аппроксимации с константным коэффициентом для не упреждающей ациклической задачи планирования набора заданий с единичной длиной, подразумеваемой 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) | |||