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

Далее будет на высоком уровне описана основная идея Рэкке. Для подмножества S С V обозначим за cap(S) совокупную пропускную способность ребер, пересекающих разрез (S, V n S), а за dem(S) – совокупный спрос, который должен быть направлен через разрез (S, V n S). Заметим, что q = maxSCy dem(S)/cap(S) – нижняя граница нагруженности любого решения. С другой стороны, из основных выводов работ [3, 13], относящихся к многопродуктовым потокам и разрезам, следует, что существует маршрутизация, такая, что максимальная нагруженность не превышает O(qlog k), где k – число отдельных пар «источник-сток». Заметим, однако, что одного этого недостаточно для качественной маршрутизации в отсутствие информации, поскольку паре (si, ti) могут требоваться разные маршруты для разных множеств значений спроса. Основная идея Рэкке заключалась в наложении древовидной структуры для маршрутизации на графе, позволяющей действовать в отсутствие информации. Этот подход формализован при помощи описанной далее иерархической декомпозиции.

Рассмотрим следующую иерархическую декомпозицию графа G = (V, E). Начинаем с множества S = V и последовательно разбиваем множества до тех пор, пока каждое из них не будет состоять из одиночной вершины. Иерархическую декомпозицию можно естественным образом рассматривать как дерево T, корень которого соответствует множеству V, а листья – одноэлементным множествам {v}. Обозначим за Si подмножество V, соответствующее вершине i в T. Назначим ребру дерева (i, j), где i является потомком j, пропускную способность cap(Si) (заметим, что это пропускная способность пути из Si в оставшуюся часть G, а не пути между Si и Sj в графе G). Дерево T используется для моделирования маршрутов в G и наоборот. Пусть задан спрос на участке между вершинами u и v в графе G. Рассмотрим соответствующий (уникальный) маршрут между листьями, соответствующими {u} и {v}, в дереве T. Для любого множества значений спроса легко увидеть, что нагруженность в T не превышает нагруженность в G. И наоборот, Рэкке показал, что существует также дерево T, маршруты в котором могут быть отображены на потоки в G таким образом, что для любого множества значений спроса нагруженность в G не более чем в O(log n) раз превышает нагруженность в T. В этом отображении поток вдоль пути (i, j) в дереве T соответствует подходящим образом построенному потоку между множествами Si и Sj в графе G. Поскольку маршрут между любыми двумя вершинами в T уникален, получаем маршрутизацию (в отсутствие информации) для G.

Рэкке использует изобретательный подход для доказательства существования такой иерархической декомпозиции. Полное описание построения не будет здесь приведено, однако полезно понимать, каким требованиям должна удовлетворять подобная декомпозиция. Во-первых, дерево T должно отражать все узкие места графа G, т.е. если существует множество значений спроса, вызывающее высокую нагруженность G, то оно должно также вызывать высокую нагруженность T. Естественный способ построения T выглядит следующим образом: начать с V, разбить V вдоль узкого места (формально – вдоль разреза с низким уровнем разреженности), рекурсивно повторить. Однако реализации этого слишком простого подхода недостаточно для успешной работы. Как будет показано ниже, дерево T также должно удовлетворять двум другим естественным условиям, называемым свойствами пропускной способности и веса и мотивированным следующим образом. Рассмотрим вершину i, соединенную с ее предком j в T. Это значит, что i должна направить поток dem(Si) из Si, что вызывает нагруженность dem(Si)/cap(Si) в T. Однако, когда T отображается обратно на G, весь поток, выходящий из Si, должен пройти через Sj. Чтобы гарантировать, что ребра между Si и Sj не будут перегружены, необходимо, чтобы пропускная способность пути из Si в Sj была неслишком малой по сравнению с пропускной способностью путей из Si в оставшуюся часть графа V n Si. Это условие называется свойством пропускной способности. Рэкке гарантирует, что это отношение всегда составляет J2(l/log n) для всех Si и Sj, соответствующих ребрам (i, j) дерева. Свойство веса объясняется следующим образом. Рассмотрим вершину j дерева T с потомками i1..; ip. Свойство веса, в сущности, требует, чтобы множества Si 1...Sip были тесно связанными друг с другом, даже если они ограничены подграфом Sj. Чтобы понять, зачем это нужно, рассмотрим любую коммуникацию между вершинами, например, i1 и i2 в дереве T. Для этого необходим маршрут из i1 в j и далее в i2, и, следовательно, в графе G Si1 не может использовать ребра, не входящие в Sj, для коммуникации с Si2. Рэкке показывает, что эти условия являются достаточными и что можно получить удовлетворяющую им декомпозицию.