4551
правка
Маршрутизация в отсутствие информации: различия между версиями
Материал из WEGA
Маршрутизация в отсутствие информации (посмотреть исходный код)
Версия от 20:26, 16 июля 2019
, 16 июля 2019→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
== Нотация == | == Нотация == | ||
Пусть G = (V, E) – некориентированный граф, каждое ребро которого имеет неотрицательную пропускную способность c(e) | Пусть G = (V, E) – некориентированный граф, каждое ребро которого <math>e \in E</math> имеет неотрицательную пропускную способность c(e). Предположим, что имеется k пар «отправитель-получатель» <math>(s_i, t_i)</math> для i = 1, ..., k, и обозначим за <math>d_i</math> объем потока (или спрос), который пара i желает переслать из точки <math>s_i</math> в точку <math>t_i</math>. Пусть имеется маршрутизация этих потоков в графе G. ''Нагруженность'' ребра e определяется как u(e)/c(e) – отношение совокупного потока, проходящего через ребро e, к его пропускной способности. Нагруженность всей маршрутизации определяется как максимальная нагруженность по всем ребрам. Задача минимизации нагруженности заключается в поиске маршрутизации, при которой максимальная нагруженность оказывается минимальной. Заметим, что задание потока из <math>s_i</math> в <math>t_i</math> эквивалентно нахождению распределения вероятностей (не обязательно уникального) на наборе путей из <math>s_i</math> в <math>t_i</math>. | ||
| Строка 12: | Строка 12: | ||
Далее будет рассматриваться маршрутизация в отсутствие информации. В этом случае схема маршрутизации определяется для каждой пары вершин заранее, без знания о том, каким фактически будет спрос. Заметим, что возможности алгоритма в этой формулировке значительно ограничены. В частности, если для пары ( | Далее будет рассматриваться маршрутизация в отсутствие информации. В этом случае схема маршрутизации определяется для каждой пары вершин заранее, без знания о том, каким фактически будет спрос. Заметим, что возможности алгоритма в этой формулировке значительно ограничены. В частности, если для пары <math>(s_i, t_i)</math> поступает спрос в <math>d_i</math> единиц, алгоритм должен обязательно направить этот спрос по заранее определенным путям, независимо от спроса в других узлах и от любой другой информации, такой как нагруженность других ребер. Таким образом, для исходного графа сети G потоки необходимо вычислить только один раз. После окончания вычисления задача алгоритма маршрутизации становится тривиальной: при получении нового спроса он просто направляет его по заранее рассчитанному пути. Схема маршрутизации в отсутствие информации называется ''c''-конкурентной, если для каждого набора значений спроса D максимальная нагруженность решения не более чем в ''c'' раз превышает нагруженность оптимального оффлайнового решения для D. Учитывая строгие требования к качеству маршрутизации в отсутствие информации, не всегда априори бывает очевидно, существует ли рациональная схема маршрутизации в принципе. | ||
== Основные результаты == | == Основные результаты == | ||
