Маршрутизация в отсутствие информации
Ключевые слова и синонимы
Маршрутизация с фиксированной траекторией
Постановка задачи
Рассмотрим коммуникационную сеть – например, сеть городов в стране, соединенных линиями связи. В сети есть несколько пар «отправитель-получатель», желающих связываться друг с другом посредством отправки трафика по сети. Задача заключается в маршрутизации всего трафика в сети таким образом, что ни одно ее звено не оказывается чрезмерно перегруженным. Иначе говоря, ни одна линия связи в сети не должна нести слишком много трафика по сравнению со своей пропускной способностью. Под маршрутизацией в отсутствие информации понимается требование построения маршрутов в сети без знания возникающих в сети актуальных запросов на трафик – иначе говоря, маршрут для каждой пары «отправитель-получатель» остается фиксированным независимо от того, какой объем трафика собирается переслать каждая пара. Разработка эффективной стратегии маршрутизации в отсутствие информации имеет практический смысл, поскольку она гарантирует надежную работу сети в ситуации любых изменений шаблонов распределения трафика.
Нотация
Пусть G = (V, E) – некориентированный граф, каждое ребро которого [math]\displaystyle{ e \in E }[/math] имеет неотрицательную пропускную способность c(e). Предположим, что имеется k пар «отправитель-получатель» [math]\displaystyle{ (s_i, t_i) }[/math] для i = 1, ..., k, и обозначим за [math]\displaystyle{ d_i }[/math] объем потока (или спрос), который пара i желает переслать из точки [math]\displaystyle{ s_i }[/math] в точку [math]\displaystyle{ t_i }[/math]. Пусть имеется маршрутизация этих потоков в графе G. Нагруженность ребра e определяется как u(e)/c(e) – отношение совокупного потока, проходящего через ребро e, к его пропускной способности. Нагруженность всей маршрутизации определяется как максимальная нагруженность по всем ребрам. Задача минимизации нагруженности заключается в поиске маршрутизации, при которой максимальная нагруженность оказывается минимальной. Заметим, что задание потока из [math]\displaystyle{ s_i }[/math] в [math]\displaystyle{ t_i }[/math] эквивалентно нахождению распределения вероятностей (не обязательно уникального) на наборе путей из [math]\displaystyle{ s_i }[/math] в [math]\displaystyle{ t_i }[/math].
Задачу минимизации нагруженности можно рассматривать в разных формулировках. В оффлайновой формулировке экземпляр задачи о потоке предоставляется заранее, а целью является нахождение оптимальной маршрутизации. В онлайновой формулировке информация о спросе появляется в произвольном состязательном порядке, и поток для спроса должен определяться немедленно после получения информации о нем; этот поток навсегда остается фиксированным, и его маршрут не может быть изменен позднее при поступлении новой информации о потоке. Исследовались также несколько распределенных подходов, в рамках которых каждая пара направляет свой поток распределенным образом, основываясь на некоторой глобальной информации – такой как текущая нагруженность ребер.
Далее будет рассматриваться маршрутизация в отсутствие информации. В этом случае схема маршрутизации определяется для каждой пары вершин заранее, без знания о том, каким фактически будет спрос. Заметим, что возможности алгоритма в этой формулировке значительно ограничены. В частности, если для пары [math]\displaystyle{ (s_i, t_i) }[/math] поступает спрос в [math]\displaystyle{ d_i }[/math] единиц, алгоритм должен обязательно направить этот спрос по заранее определенным путям, независимо от спроса в других узлах и от любой другой информации, такой как нагруженность других ребер. Таким образом, для исходного графа сети G потоки необходимо вычислить только один раз. После окончания вычисления задача алгоритма маршрутизации становится тривиальной: при получении нового спроса он просто направляет его по заранее рассчитанному пути. Схема маршрутизации в отсутствие информации называется c-конкурентной, если для каждого набора значений спроса D максимальная нагруженность решения не более чем в c раз превышает нагруженность оптимального оффлайнового решения для D. Учитывая строгие требования к качеству маршрутизации в отсутствие информации, не всегда априори бывает очевидно, существует ли рациональная схема маршрутизации в принципе.
Основные результаты
Маршрутизация в отсутствие информации изначально исследовалась в контексте маршрутизации перестановок, в которой пары вершин со спросом формируют перестановку, и каждой из них присвоено единичное значение. Было показано, что любой алгоритм маршрутизации в отсутствие информации, определяющий единственный путь (а не поток) между каждыми двумя вершинами, неизбежно имеет низкую эффективность. Впервые это доказали Бородин и Хопкрофт [6] для гиперкубов, впоследствии на графы общего вида это рассуждение распространили Какламанис, Кризанс и Тсантилас [12], доказавшие следующую теорему.
Теорема 1 [6, 12]. Для любого графа G размера n с максимальной степенью d и любой стратегии маршрутизации в отсутствие информации, применяющей только один путь для каждой пары «источник-адресат», существует перестановка, приводящая к перекрытию по меньшей мере [math]\displaystyle{ (n/d)^{1/2} }[/math] путей в некоторой вершине. Таким образом, если каждое ребро G имеет единичную пропускную способность, нагруженность ребер составит не менее [math]\displaystyle{ (n/d)^{1/2}/d }[/math].
Поскольку существуют графы с константной степенью, такие как графы типа «бабочка», способные выполнить маршрутизацию любой перестановки с логарифмической нагруженностью, из этого следует, что подобные схемы маршрутизации в отсутствие информации неизбежно должны демонстрировать низкую эффективность на некоторых типах графов.
К счастью, ситуация оказывается намного лучше, если требование единственного пути смягчается и допускается распределение вероятностей (эквивалентное потоку) для путей между каждой парой вершин. В своей основополагающей статье [17] Валиант и Бребнер предложили первую схему маршрутизации перестановок в отсутствие информации с малой нагруженностью на гиперкубе. Эта схема заслуживает отдельного изучения. Рассмотрим гиперкуб с [math]\displaystyle{ N = 2^n }[/math] вершинами. Представим вершину i в виде двоичного разложения i. Для любых двух вершин s и t существует каноническая траектория (длиной не более n = log N) из s в t, для получения которой следует начать с s и инвертировать биты s слева направо, добиваясь совпадения с битами t. Рассмотрим схему маршрутизации, которая для пары s и t вначале выбирает некоторую вершину p равномерным случайным образом, направляет поток из s в p по канонической траектории, а затем вновь направляет его из p в t по канонической траектории (или, что эквивалентно, отправляет 1/N единиц потока из s в каждую промежуточную вершину p, а затем направляет его в t). Относительно простой анализ позволяет установить, что
Теорема 2 [17]. Вышеприведенная схема маршрутизации в отсутствие информации обеспечивает нагруженность O(1) для гиперкубов.
Впоследствии схемы маршрутизации в отсутствие информации были предложены для некоторых других специальных классов сетей. Однако задача разработки таких схем для графов общего вида оставалась нерешенной до недавнего времени, а именно – до революционного открытия Рэкке.
Теорема 3 [15]. Для любого неориентированного графа с ограничениями на пропускную способность G = (V, E) существует схема маршрутизации в отсутствие информации с нагруженностью [math]\displaystyle{ O(log^3 n) }[/math], где n – количество вершин в графе G.
Ключом к теореме Рэкке является процедура иерархической декомпозиции графа, лежащего в основе сети (она будет подробно описана ниже). Такая иерархическая декомпозиция представляет собой фундаментальный комбинаторный результат, относящийся к структуре разрезов графа, и находит применение в различных областях, часть которых перечислена в соответствующем разделе. Предложенное Рэкке доказательство теоремы 3 только доказывает существование хорошей иерархической декомпозиции, но не приводит эффективного алгоритма для ее нахождения за полиномиальное время. В последующей работе Харрелсон, Хилдрум и Рао [11] предложили процедуру с полиномиальным временем выполнения для поиска декомпозиции и улучшили коэффициент конкурентоспособности маршрутизации в отсутствие информации до [math]\displaystyle{ O(log^2 n \; log \; log \; n) }[/math].
Теорема 4 [11]. Существует [math]\displaystyle{ O(log^2 n \; log \; log \; n) }[/math]-конкурентная схема маршрутизации в отсутствие информации для графов общего вида; более того, она может быть найдена за полиномиальное время.
Любопытно, что Азар и др. [4] показали, что задача нахождения оптимальной маршрутизации в отсутствие информации для графа может быть сформулирована в виде линейной программы. Они рассмотрели формулировку с экспоненциальным числом ограничений, по одному для каждой возможной матрицы спроса, имеющей единичную оптимальную нагруженность, в силу чего маршрутизация согласно этой матрице должна иметь невысокую нагруженность. Азар и др. [4] представили оракула разделения для этой задачи; из чего следует, что она может быть решена методом эллипсоидов. Более практичную линейную программу полиномиального размера впоследствии предложили Эпплгейт и Коэн [2]. Бансал и др. [5] рассматривали более общий вариант, названный ими онлайновой маршрутизацией в отсутствие информации, который также может использоваться для поиска оптимальной маршрутизации. Однако стоит заметить, что без находки Рэкке было бы неясно, насколько хороша была бы эта оптимальная маршрутизация. Кроме того, эти техники не позволяют получить иерархическую декомпозицию и в силу этого могут быть менее эффективны в некоторых контекстах. С другой стороны, порой они могут быть более полезны из-за того, что обеспечивают оптимальную маршрутизацию (в то время как подход из работы [11] дает [math]\displaystyle{ O(log^2 n \; log \; log \; n) }[/math]-конкурентную маршрутизацию для любого графа, лучший алгоритм маршрутизации в отсутствие информации может обеспечить гораздо более удачную гарантию для конкретного графа).
Подобная маршрутизация изучалась и для ориентированных графов, однако в этом случае ситуация значительно сложнее. Азар и др. [4] показали, что существуют ориентированные графы, на которых любая маршрутизация в отсутствие информации является [math]\displaystyle{ \Omega(\sqrt{n}) }[/math]-конкурентной. Известны и некоторые положительные результаты [10]. Хаджиагаи и др. [8] продемонстрировали значительно улучшенную гарантию [math]\displaystyle{ O(log^2 n) }[/math] для ориентированных графов в модели со случайным спросом. Здесь для каждой пары «источник-сток» имеется распределение (известное алгоритму), на основе которого она независимо выбирает значение спроса. Также исследовалась релаксация маршрутизации в отсутствие информации, известная как маршрутизация с неполной информацией [9].
Техника
Далее будет на высоком уровне описана основная идея Рэкке. Для подмножества [math]\displaystyle{ S \subset V }[/math] обозначим за cap(S) совокупную пропускную способность ребер, пересекающих разрез (S, V \ S), а за dem(S) – совокупный спрос, который должен быть направлен через разрез (S, V \ S). Заметим, что [math]\displaystyle{ q = max_{S \subset V} dem(S)/cap(S) }[/math] – нижняя граница нагруженности любого решения. С другой стороны, из основных выводов работ [3, 13], относящихся к многопродуктовым потокам и разрезам, следует, что существует маршрутизация, такая, что максимальная нагруженность не превышает O(q log k), где k – число отдельных пар «источник-сток». Заметим, однако, что одного этого недостаточно для качественной маршрутизации в отсутствие информации, поскольку паре [math]\displaystyle{ (s_i, t_i) }[/math] могут требоваться разные маршруты для разных множеств значений спроса. Основная идея Рэкке заключалась в наложении древовидной структуры для маршрутизации на графе, позволяющей действовать в отсутствие информации. Этот подход формализован при помощи описанной далее иерархической декомпозиции.
Рассмотрим следующую иерархическую декомпозицию графа G = (V, E). Начинаем с множества S = V и последовательно разбиваем множества до тех пор, пока каждое из них не будет состоять из одиночной вершины. Иерархическую декомпозицию можно естественным образом рассматривать как дерево T, корень которого соответствует множеству V, а листья – одноэлементным множествам {v}. Обозначим за [math]\displaystyle{ S_i }[/math] подмножество V, соответствующее вершине i в T. Назначим ребру дерева (i, j), где i является потомком j, пропускную способность [math]\displaystyle{ cap(S_i) }[/math] (заметим, что это пропускная способность пути из [math]\displaystyle{ S_i }[/math] в оставшуюся часть G, а не пути между [math]\displaystyle{ S_i }[/math] и [math]\displaystyle{ S_j }[/math] в графе G). Дерево T используется для моделирования маршрутов в G и наоборот. Пусть задан спрос на участке между вершинами u и v в графе G. Рассмотрим соответствующий (уникальный) маршрут между листьями, соответствующими {u} и {v}, в дереве T. Для любого множества значений спроса легко увидеть, что нагруженность в T не превышает нагруженность в G. И наоборот, Рэкке показал, что существует также дерево T, маршруты в котором могут быть отображены на потоки в G таким образом, что для любого множества значений спроса нагруженность в G не более чем в [math]\displaystyle{ O(log^3 n) }[/math] раз превышает нагруженность в T. В этом отображении поток вдоль пути (i, j) в дереве T соответствует подходящим образом построенному потоку между множествами [math]\displaystyle{ S_i }[/math] и [math]\displaystyle{ S_j }[/math] в графе G. Поскольку маршрут между любыми двумя вершинами в T уникален, получаем маршрутизацию (в отсутствие информации) для G.
Рэкке использует изобретательный подход для доказательства существования такой иерархической декомпозиции. Полное описание построения не будет здесь приведено, однако полезно понимать, каким требованиям должна удовлетворять подобная декомпозиция. Во-первых, дерево T должно отражать все узкие места графа G, т.е. если существует множество значений спроса, вызывающее высокую нагруженность G, то оно должно также вызывать высокую нагруженность T. Естественный способ построения T выглядит следующим образом: начать с V, разбить V вдоль узкого места (формально – вдоль разреза с низким уровнем разреженности), рекурсивно повторить. Однако реализации этого слишком простого подхода недостаточно для успешной работы. Как будет показано ниже, дерево T также должно удовлетворять двум другим естественным условиям, называемым свойствами пропускной способности и веса и обоснованным следующими причинами. Рассмотрим вершину i, соединенную с ее предком j в T. Это значит, что i должна направить поток [math]\displaystyle{ dem(S_i) }[/math] из [math]\displaystyle{ S_i }[/math], что вызывает нагруженность [math]\displaystyle{ dem(S_i)/cap(S_i) }[/math] в T. Однако, когда T отображается обратно на G, весь поток, выходящий из [math]\displaystyle{ S_i }[/math], должен пройти через [math]\displaystyle{ S_j }[/math]. Чтобы гарантировать, что ребра между [math]\displaystyle{ S_i }[/math] и [math]\displaystyle{ S_j }[/math] не будут перегружены, необходимо, чтобы пропускная способность пути из [math]\displaystyle{ S_i }[/math] в [math]\displaystyle{ S_j }[/math] была не слишком мала по сравнению с пропускной способностью путей из [math]\displaystyle{ S_i }[/math] в оставшуюся часть графа [math]\displaystyle{ V \backslash S_i }[/math]. Это условие называется свойством пропускной способности. Рэкке гарантирует, что это отношение всегда составляет [math]\displaystyle{ \Omega(1 / log \; n) }[/math] для всех [math]\displaystyle{ S_i }[/math] и [math]\displaystyle{ S_j }[/math], соответствующих ребрам (i, j) дерева. Свойство веса объясняется следующим образом. Рассмотрим вершину j дерева T с потомками [math]\displaystyle{ i_1, ..., i_p }[/math]. Свойство веса, в сущности, требует, чтобы множества [math]\displaystyle{ S_{i_1}, ..., S_{i_p} }[/math] были тесно связанными друг с другом, даже если они ограничены подграфом [math]\displaystyle{ S_j }[/math]. Чтобы понять, зачем это нужно, рассмотрим любую коммуникацию между вершинами, например, [math]\displaystyle{ i_1 }[/math] и [math]\displaystyle{ i_2 }[/math]? в дереве T. Для этого необходим маршрут из [math]\displaystyle{ i_1 }[/math] в j и далее в [math]\displaystyle{ i_2 }[/math], и, следовательно, в графе G вершина [math]\displaystyle{ S_{i_1} }[/math] не может использовать ребра, не входящие в [math]\displaystyle{ S_j }[/math], для коммуникации с [math]\displaystyle{ S_{i_2} }[/math]. Рэкке показывает, что эти условия являются достаточными и что можно получить удовлетворяющую им декомпозицию.
Коэффициент [math]\displaystyle{ O(log^3 n }[/math]) в приводимой Рэкке гарантии возникает из трех источников. Первый логарифмический множитель связан с разрывом целостности [3, 13]. Второй определяется логарифмической высотой дерева, а третий связан с потерей логарифмического множителя в свойствах пропускной способности и веса.
Применение
Данная задача часто встречается при маршрутизации в сетях. На практике нередко требуется, чтобы все маршруты представляли собой одиночные пути, а не потоки. Этой цели нередко можно достичь при помощи техник рандомизированного округления (иногда в предположении, что отношение спроса к пропускной способности не слишком велико). Формулировка на основе потоков представляет собой намного более четкую структуру для изучения вышеперечисленных задач.
Любопытно, что иерархическая декомпозиция также широко применяется в таких на первый взгляд не связанных с этой задачей областях, как получение хороших начальных условий для решения систем линейных уравнений [14, 16], задача управления несколькими товарными потоками типа «все или ничего» [7], оптимизация сетей в режиме онлайн [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)