Маршрутизация в отсутствие информации
Ключевые слова и синонимы
Маршрутизация с фиксированной траекторией
Постановка задачи
Рассмотрим коммуникационную сеть – например, сеть городов в стране, соединенных линиями связи. В сети есть несколько пар «отправитель-получатель», желающих связываться друг с другом посредством отправки трафика по сети. Задача заключается в маршрутизации всего трафика в сети таким образом, что ни одно ее звено не оказывается чрезмерно перегруженным. Иначе говоря, ни одна линия связи в сети не должна нести слишком много трафика по сравнению со своей пропускной способностью. Отсутствие информации в данном случае заключается в требовании построения маршрутов в сети без знания возникающих в сети актуальных запросов на трафик – иначе говоря, маршрут для каждой пары «отправитель-получатель» остается фиксированным независимо от того, какой объем трафика собирается переслать каждая пара. Разработка эффективной стратегии маршрутизации в отсутствие информации имеет практический смысл, поскольку она гарантирует надежную работу сети в ситуации любых изменений шаблонов распределения трафика.
Нотация
Пусть 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. Учитывая строгие требования к качеству маршрутизации в отсутствие информации, не всегда априори бывает очевидно, существует ли вообще рациональная схема маршрутизации.