Маршрутизация в отсутствие информации

Ключевые слова и синонимы

Маршрутизация с фиксированной траекторией

Постановка задачи

Рассмотрим коммуникационную сеть – например, сеть городов в стране, соединенных линиями связи. В сети есть несколько пар «отправитель-получатель», желающих связываться друг с другом посредством отправки трафика по сети. Задача заключается в маршрутизации всего трафика в сети таким образом, что ни одно ее звено не оказывается чрезмерно перегруженным. Иначе говоря, ни одна линия связи в сети не должна нести слишком много трафика по сравнению со своей пропускной способностью. Отсутствие информации в данном случае заключается в требовании построения маршрутов в сети без знания возникающих в сети актуальных запросов на трафик – иначе говоря, маршрут для каждой пары «отправитель-получатель» остается фиксированным независимо от того, какой объем трафика собирается переслать каждая пара. Разработка эффективной стратегии маршрутизации в отсутствие информации имеет практический смысл, поскольку она гарантирует надежную работу сети в ситуации любых изменений шаблонов распределения трафика.

Нотация

Пусть 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. Учитывая строгие требования к качеству маршрутизации в отсутствие информации, не всегда априори бывает очевидно, существует ли вообще рациональная схема маршрутизации.

Основные результаты

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

Теорема 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].