4551
правка
Маршрутизация в отсутствие информации: различия между версиями
Перейти к навигации
Перейти к поиску
Маршрутизация в отсутствие информации (посмотреть исходный код)
Версия от 18:49, 9 июля 2019
, 9 июля 2019→Техника
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
== Техника == | == Техника == | ||
Далее будет на высоком уровне описана основная идея Рэкке. Для подмножества S С V обозначим за cap(S) совокупную пропускную способность ребер, пересекающих разрез (S, V n S), а за dem(S) – совокупный спрос, который должен быть направлен через разрез (S, V n S). Заметим, что q = maxSCy dem(S)/cap(S) – нижняя граница нагруженности любого решения. С другой стороны, из основных выводов работ [3, 13], относящихся к многопродуктовым потокам и разрезам, следует, что существует маршрутизация, такая, что максимальная нагруженность не превышает O(qlog k), где k – число отдельных пар «источник-сток». Заметим, однако, что одного этого недостаточно для качественной маршрутизации в отсутствие информации, поскольку паре (si, ti) могут требоваться разные маршруты для разных множеств значений спроса. Основная идея Рэкке заключалась в наложении древовидной структуры для маршрутизации на графе, позволяющей действовать в отсутствие информации. Этот подход формализован при помощи описанной далее иерархической декомпозиции. | |||
Рассмотрим следующую иерархическую декомпозицию графа G = (V, E). Начинаем с множества S = V и последовательно разбиваем множества до тех пор, пока каждое из них не будет состоять из одиночной вершины. Иерархическую декомпозицию можно естественным образом рассматривать как дерево T, корень которого соответствует множеству V, а листья – одноэлементным множествам {v}. Обозначим за Si подмножество V, соответствующее вершине i в T. Назначим ребру дерева (i, j), где i является потомком j, пропускную способность cap(Si) (заметим, что это пропускная способность пути из Si в оставшуюся часть G, а не пути между Si и Sj в графе G). Дерево T используется для моделирования маршрутов в G и наоборот. Пусть задан спрос на участке между вершинами u и v в графе G. Рассмотрим соответствующий (уникальный) маршрут между листьями, соответствующими {u} и {v}, в дереве T. Для любого множества значений спроса легко увидеть, что нагруженность в T не превышает нагруженность в G. И наоборот, Рэкке показал, что существует также дерево T, маршруты в котором могут быть отображены на потоки в G таким образом, что для любого множества значений спроса нагруженность в G не более чем в O(log n) раз превышает нагруженность в T. В этом отображении поток вдоль пути (i, j) в дереве T соответствует подходящим образом построенному потоку между множествами Si и Sj в графе G. Поскольку маршрут между любыми двумя вершинами в T уникален, получаем маршрутизацию (в отсутствие информации) для G. | |||
Рэкке использует изобретательный подход для доказательства существования такой иерархической декомпозиции. Полное описание построения не будет здесь приведено, однако полезно понимать, каким требованиям должна удовлетворять подобная декомпозиция. Во-первых, дерево T должно отражать все узкие места графа G, т.е. если существует множество значений спроса, вызывающее высокую нагруженность G, то оно должно также вызывать высокую нагруженность T. Естественный способ построения T выглядит следующим образом: начать с V, разбить V вдоль узкого места (формально – вдоль разреза с низким уровнем разреженности), рекурсивно повторить. Однако реализации этого слишком простого подхода недостаточно для успешной работы. Как будет показано ниже, дерево T также должно удовлетворять двум другим естественным условиям, называемым свойствами пропускной способности и веса и мотивированным следующим образом. Рассмотрим вершину i, соединенную с ее предком j в T. Это значит, что i должна направить поток dem(Si) из Si, что вызывает нагруженность dem(Si)/cap(Si) в T. Однако, когда T отображается обратно на G, весь поток, выходящий из Si, должен пройти через Sj. Чтобы гарантировать, что ребра между Si и Sj не будут перегружены, необходимо, чтобы пропускная способность пути из Si в Sj была неслишком малой по сравнению с пропускной способностью путей из Si в оставшуюся часть графа V n Si. Это условие называется свойством пропускной способности. Рэкке гарантирует, что это отношение всегда составляет J2(l/log n) для всех Si и Sj, соответствующих ребрам (i, j) дерева. Свойство веса объясняется следующим образом. Рассмотрим вершину j дерева T с потомками i1..; ip. Свойство веса, в сущности, требует, чтобы множества Si 1...Sip были тесно связанными друг с другом, даже если они ограничены подграфом Sj. Чтобы понять, зачем это нужно, рассмотрим любую коммуникацию между вершинами, например, i1 и i2 в дереве T. Для этого необходим маршрут из i1 в j и далее в i2, и, следовательно, в графе G Si1 не может использовать ребра, не входящие в Sj, для коммуникации с Si2. Рэкке показывает, что эти условия являются достаточными и что можно получить удовлетворяющую им декомпозицию. | |||
Коэффициент O(log n) в приводимой Рэкке гарантии появляется из трех источников. Первый логарифмический множитель связан с разрывом целостности [3, 13]. Второй определяется логарифмической высотой дерева, а третий связан с отбрасыванием логарифмического множителя в свойствах пропускной способности и веса. | |||
== Применение == | |||
Данная задача часто встречается при маршрутизации в сетях. На практике нередко требуется, чтобы все маршруты представляли собой одиночные пути, а не потоки. Этой цели нередко можно достичь при помощи техник рандомизированного округления (иногда в предположении, что отношение спроса к пропускной способности не слишком велико). Формулировка на основе потоков представляет собой намного более четкую структуру для изучения вышеперечисленных задач. | |||
Любопытно, что иерархическая декомпозиция также широко применяется в таких на первый взгляд не связанных с этой задачей областях, как получение хороших начальных условий для решения систем линейных уравнений [14, 16], задача управления несколькими товарными потоками типа «все или ничего» [ ], оптимизация сетей в режиме онлайн [1] и многие другие. | |||
== Открытые вопросы == | |||
Существует возможность того, что любой граф имеет O(log n)-конкурентную схему маршрутизации в отсутствие информации. Так ли это, пока не установлено. | |||
== См. также == | |||
* [[Маршрутизация]] | |||
* [[Сепараторы в графах]] | |||
* [[Самое неплотное сечение]] | |||
== Литература == | |||
1. Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: A general approach to online network optimization problems. In: Symposium on Discrete Algorithms, pp. 570-579 (2004) | |||
2. Applegate, D., Cohen, E.: Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs. In: SIGCOMM, pp. 313-324 | |||
(2003) | |||
3. Aumann, Y., Rabani, Y.: An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput. 27(1),291-301 (1998) | |||
4. Azar, Y., Cohen, E., Fiat, A., Kaplan, H., Racke, H.: Optimal oblivious routing in polynomial time. In: Proceedings of the 35th ACM Symposium on the Theory of Computing, pp. 383-388 (2003) | |||
5. Bansal, N., Blum, A., Chawla, S., Meyerson, A.: Online oblivious routing. In Symposium on Parallelism in Algorithms and Architectures, pp. 44-49 (2003) | |||
6. Borodin, A., Hopcroft, J.: Routing, merging and sorting on parallel models of computation. J. Comput. Syst. Sci. 10(1), 130-MS (1985) | |||
7. Chekuri, C., Khanna, S., Shepherd, F.B.: The All-or-Nothing Multicommodity Flow Problem. In: Proceedings of 36th ACM Symposium on Theory of Computing, pp. 156-165 (2004) | |||
8. Hajiaghayi, M., Kim, J.H., Leighton, T., Racke, H.: Oblivious routing in directed graphs with random demands. In: Symposium on Theory of Computing, pp. 193-201 (2005) | |||
9. Hajiaghayi, M., Kleinberg, R., Leighton, T.: Semi-oblivious routing: lower bounds. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 929-938 (2007) | |||
10. Hajiaghayi, M., Kleinberg, R., Leighton, T., Racke, H.: Oblivious routing in node-capacitated and directed graphs. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 782-790 (2005) | |||
11. Harrelson, C., Hildrum, K., Rao, S.: A polynomial-time tree decomposition to minimize congestion. In: Proceedings of the 15th annual ACM Symposium on Parallel Algorithms and Ar | |||
chitectures, pp. 34^3 (2003) | |||
12. Kaklamanis, C., Krizanc, D., Tsantilas, T.: Tight bounds for oblivious routing in the hypercube. In: Proceedings of the 3rd annual ACM Symposium on Parallel Algorithms and Architectures, pp. 31-36 (1991) | |||
13. Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. In: IEEE Symposium on Foundations of Computer Science, pp. 577-591 (1994) | |||
14. Maggs, B.M., Miller, G.L., Parekh, O., Ravi, R., Woo, S.L.M.: Finding effective support-tree preconditioners. In: Symposium on Parallel Algorithms and Architectures, pp. 176-185 (2005) | |||
15. Racke, H.: Minimizing congestion in general networks. In: Proceedings of the 43rd Annual Symposium on the Foundations of Computer Science, pp. 43-52 (2002) | |||
16. Vaidya, P.: Solving linear equations with symmetric diagonally dominant matrices by constructing good preconditioners. Unpublished manuscript (1991) | |||
17. Valiant, L., Brebner, G.J.: Universal schemes for parallel communication. In: Proceedings of the 13th ACM Symposium on Theory of Computing, pp. 263-277 (1981) | |||