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

Теорема 1 [6, 12]. Для любого графа G размера n с максимальной степенью d и любой стратегии маршрутизации в отсутствие информации, применяющей только один путь для каждой пары «источник-адресат», существует перестановка, приводящая к перекрытию по меньшей мере (n/d)1/2 путей в некоторой вершине. Таким образом, если каждое ребро G имеет единичную пропускную способность, нагруженность ребер составит не менее (n/d)1/2/d.

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

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

Теорема 4 [11]. Существует O(log nloglogn)-конкурентная схема маршрутизации в отсутствие информации для графов общего вида; более того, она может быть найдена за полиномиальное время.

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

Подобная маршрутизация изучалась и для ориентированных графов, однако в этом случае ситуация значительно сложнее. Азар и др. [4] показали, что существуют ориентированные графы, на которых любая маршрутизация в отсутствие информации является Q(pn)-конкурентной. Известны и некоторые положительные результаты [ ]. Хаджиагаи и др. [ ] продемонстрировали значительно улучшенную гарантию O(log n) для ориентированных графов в модели со случайным спросом. Здесь для каждой пары «источник-сток» имеется распределение (известное алгоритму), на основе которого она независимо выбирает значение спроса. Также исследовалась релаксация маршрутизации в отсутствие информации, известная как маршрутизация с неполной информацией [9].