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

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