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

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