Аноним

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

Материал из WEGA

Маршрутизация в отсутствие информации (посмотреть исходный код)

Версия от 18:49, 9 июля 2019

13 794 байта добавлено ,  9 июля 2019
→‎Техника
Строка 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)
Irina
4430

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/13999