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

Пусть G = (V, E) – некориентированный граф, каждое ребро которого имеет неотрицательную пропускную способность c(e) для e 2 E. Предположим, что имеется k пар «отправитель-получатель» (SI ; ti) для i = 1…, … k, и обозначим за di объем потока (или спрос) который пара i желает переслать из точки si в точку ti. Пусть имеется маршрутизация этих потоков в графе G. Нагруженность ребра e определяется как u(e)/c(e) – отношение совокупного потока, проходящего через ребро e, к его пропускной способности. Нагруженность всей маршрутизации определяется как максимальная нагруженность по всему ребрам. Задача минимизации нагруженности заключается в поиске маршрутизации, при которой максимальная нагруженность оказывается минимальной. Заметим, что задание потока из si в ti эквивалентно нахождению распределения вероятностей (не обязательно уникального) на наборе путей из si в ti.

Далее будет рассматриваться маршрутизация в отсутствие информации. В этом случае схема маршрутизации определяется для каждой пары вершин заранее, без знания о том, каким фактически будет спрос. Заметим, что возможности алгоритма в этой формулировке значительно ограничены. В частности, если для пары (si ; ti■) поступает спрос в di единиц, алгоритм должен обязательно направить этот спрос по заранее определенным путям, независимо от спроса в других узлах и от любой другой информации, такой как нагруженность других ребер. Таким образом, для исходного графа сети G потоки необходимо вычислить только один раз. После окончания вычисления задача алгоритма маршрутизации становится тривиальной: при получении нового спроса он направляет его по заранее рассчитанному пути. Схема маршрутизации в отсутствие информации называется c-конкурентной, если для каждого набора значений спроса D максимальная нагруженность решения не более чем в c раз превышает нагруженность оптимального оффлайнового решения для D. Учитывая строгие требования к качеству маршрутизации в отсутствие информации, не всегда априори бывает очевидно, существует ли вообще рациональная схема маршрутизации.

К счастью, ситуация оказывается намного лучше, если требование единственного пути смягчается и допускается распределение вероятностей (эквивалентное потоку) для путей между каждой парой вершин. В своей основополагающей статье [17] Валиант и Бребнер предложили первую схему маршрутизации перестановок в отсутствие информации с малой нагруженностью на гиперкубе. Эта схема заслуживает отдельного изучения. Рассмотрим гиперкуб с <math>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). Относительно простоя анализ позволяет установить, что

Ключом к теореме Рэкке является процедура иерархической декомпозиции графа, лежащего в основе сети (она будет подробно описана ниже). Такая иерархическая декомпозиция представляет собой фундаментальный комбинаторный результат на структуре разрезов графа и находит применение в различных областях, часть которых приведена в соответствующем разделе. Предложенное Рэкке доказательство теоремы 3 только доказывает существование хорошей иерархической декомпозиции, но не приводит эффективного алгоритма для ее нахождения за полиномиальное время. В последующей работе Харрелсон, Хилдрум и Рао [11] предложили процедуру с полиномиальным временем выполнения для поиска декомпозиции и улучшили коэффициент конкурентоспособности маршрутизации в отсутствие информации до <math>O(log^2 n \; log \; log \; n)</math>.

Любопытно, что Азар и др. [4] показали, что задача нахождения оптимальной маршрутизации в отсутствие информации для графа может быть сформулирована в виде линейной программы. Они рассмотрели формулировку с экспоненциальным числом ограничений, по одному для каждой возможной матрицы спроса, имеющей единичную оптимальную нагруженность, в силу чего маршрутизация согласно этой матрице должна иметь невысокую нагруженность. Азар и др. [4] представили оракула разделения для этой задачи; следовательно, она может быть решена методом эллипсоидов. Более практичную линейную программу полиномиального размера впоследствии предложили Эпплгейт и Коэн [2]. Бансал и др. [5] рассматривали более общий вариант, названный ими онлайновой маршрутизацией в отсутствие информации, который также может использоваться для поиска оптимальной маршрутизации. Однако стоит заметить, что без находки Рэкке было бы неясно, насколько хороша была бы эта оптимальная маршрутизация. Кроме того, эти техники не позволяют получить иерархическую декомпозицию и в силу этого могут быть менее эффективны в некоторых контекстах. С другой стороны, порой они могут быть более полезны из-за того, что обеспечивают оптимальную маршрутизацию (в то время как подход из работы [11] дает <math>O(log^2 n \; log \; log \; n)</math>-конкурентную маршрутизацию для любого графа, лучший алгоритм маршрутизации в отсутствие информации может обеспечить гораздо лучшую гарантию для конкретного графа).

Рэкке использует изобретательный подход для доказательства существования такой иерархической декомпозиции. Полное описание построения не будет здесь приведено, однако полезно понимать, каким требованиям должна удовлетворять подобная декомпозиция. Во-первых, дерево T должно отражать все узкие места графа G, т.е. если существует множество значений спроса, вызывающее высокую нагруженность G, то оно должно также вызывать высокую нагруженность T. Естественный способ построения T выглядит следующим образом: начать с V, разбить V вдоль узкого места (формально – вдоль разреза с низким уровнем разреженности), рекурсивно повторить. Однако реализации этого слишком простого подхода недостаточно для успешной работы. Как будет показано ниже, дерево T также должно удовлетворять двум другим естественным условиям, называемым свойствами пропускной способности и веса и мотивированным следующим образом. Рассмотрим вершину i, соединенную с ее предком j в T. Это значит, что i должна направить поток <math>dem(S_i)</math> из <math>S_i</math>, что вызывает нагруженность <math>dem(S_i)/cap(S_i)</math> в T. Однако, когда T отображается обратно на G, весь поток, выходящий из <math>S_i</math>, должен пройти через <math>S_j</math>. Чтобы гарантировать, что ребра между <math>S_i</math> и <math>S_j</math> не будут перегружены, необходимо, чтобы пропускная способность пути из <math>S_i</math> в <math>S_j</math> была не слишком мала по сравнению с пропускной способностью путей из <math>S_i</math> в оставшуюся часть графа <math>V \backslash S_i</math>. Это условие называется ''свойством пропускной способности''. Рэкке гарантирует, что это отношение всегда составляет <math>\Omega(1 / log \; n)</math> для всех <math>S_i</math> и <math>S_j</math>, соответствующих ребрам (i, j) дерева. ''Свойство веса'' объясняется следующим образом. Рассмотрим вершину j дерева T с потомками <math>i_1, ..., i_p</math>. Свойство веса, в сущности, требует, чтобы множества <math>S_{i_1}, ..., S_{i_p}</math> были тесно связанными друг с другом, даже если они ограничены подграфом Sj. Чтобы понять, зачем это нужно, рассмотрим любую коммуникацию между вершинами, например, i1 и i2 в дереве T. Для этого необходим маршрут из i1 в j и далее в i2, и, следовательно, в графе G <math>S_{i_1}</math> не может использовать ребра, не входящие в <math>S_j</math>, для коммуникации с <math>S_{i_2}</math>. Рэкке показывает, что эти условия являются достаточными и что можно получить удовлетворяющую им декомпозицию.

Коэффициент <math>O(log^3 n</math>) в приводимой Рэкке гарантии появляется из трех источников. Первый логарифмический множитель связан с разрывом целостности [3, 13]. Второй определяется логарифмической высотой дерева, а третий связан с отбрасыванием логарифмического множителя в свойствах пропускной способности и веса.

* [[Самое неплотное сечение]]