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

''Маршрутизация'' является одной из самых широко используемых техник в современных компьютерных сетях. Под маршрутизацией понимается выбор путей в сети, по которым следует отправлять данные. Спрос обычно возникает случайным образом в некоторых узлах сети, и алгоритмы маршрутизации должны быть способны отправить данные по месту их назначения. Данные пересылаются через промежуточные узлы при помощи соединительных звеньев (линий связи) с учетом топологии сети. Пользователь ждет от сети гарантии наличия необходимой пропускной способности в процессе передачи данных, что означает, что сеть ведет себя так, словно ее узлы напрямую соединены физическим каналом связи. Подобный сервис носит название ''постоянного виртуального соединения'' (permanent virtual circuit, PVC). Для моделирования реальных ситуаций будем предполагать, что спрос возникает ''в режиме онлайн'', задается точкой-источником и точкой-получателем и включает требования к пропускной способности.

Аналогичные задачи маршрутизации возникают в других областях – например, в параллельных вычислениях. В таком случае имеются несколько процессоров, соединенных кабелями. В ходе работы у определенных процессоров появляются некоторые данные, которые должны быть переданы в конкретные точки назначения. В данном случае также требуется решать задачу маршрутизации. Далее будет рассматриваться главным образом сетевая модель, а не модель с параллельными компьютерами.

В любой конкретной ситуации имеется несколько возможных вариантов маршрутизации. Естественным образом возникает вопрос, какой алгоритм работает лучше всего. Для нахождения лучшего алгоритма следует определить целевую функцию, выражающую эффективность алгоритма. Например, целью может являться минимизация сетевой нагрузки. Нагрузку можно измерять разными способами, самым естественным из которых представляется измерение процента использования вершин или каналов сети. В онлайновой формулировке любопытно сравнить поведение алгоритма маршрутизации, разработанного для конкретного экземпляра задачи, с наилучшим возможным алгоритмом.

Существуют два фундаментальных подхода к разработке алгоритмов маршрутизации. Первый подход заключается в ''адаптивной маршрутизации'' (adaptive routing), учитывающей фактическую нагрузку узлов или каналов связи. Второй подход представляет собой ''[[маршрутизация в отсутствие информации|маршрутизацию в отсутствие информации]]'' (oblivious routing), без использования каких-либо данных о текущем состоянии сети. Далее будет рассматриваться только второй подход.

Пусть дана сеть с информацией о пропускной способности G = (V, E, c), где V – множество вершин, а E – множество дуг с функцией пропускной способности <math>c: E \to R^+.</math> Пусть |V| = n, |E| = m. Можно предположить, что сеть G является ориентированной, поскольку в противном случае для каждого неориентированного ребра e = (u, v) можно добавить к графу две новых вершины x, y и четыре новых ориентированных ребра <math>e_1 = (u, x), e_2 = (v, x), e_3 = (x, u), e_4 = (y, u)</math> с бесконечной пропускной способностью. Если e рассматривается как неориентированное ребро с той же пропускной способностью, то получается ориентированная сеть, эквивалентная исходной.

''Нагруженность'' спроса D по маршруту r составляет <math>con(r, D) = max_{e \in E} \; con(e, r, D)</math>.

'''Дано''': Сеть с информацией о пропускной способности G = (V, E, c).

Многие исследователи изучали различные варианты задач маршрутизации. Обзоры самых значимых моделей и результатов можно найти в работах [10] и [11]. Алгоритмы маршрутизации в отсутствие информации первыми проанализировали Валиант и Бребнер [15]. Они рассматривали модель с параллельными компьютерами и исследовали конкретные архитектуры, такие как гиперкуб, квадратные решетки и т. п. Бородин и Хопкрофт изучали сети общего вида [6]. Они показали, что такие простые детерминированные стратегии, как маршрутизация в отсутствие информации, не могут быть по-настоящему эффективными для онлайновой машрутизации, и доказали нижнюю границу коэффициента конкурентоспособности алгоритмов маршрутизации в отсутствие информации. Эта нижняя граница впоследствии была улучшена Какламанисом и др. [9], которые также предложили оптимальный детерминированный алгоритм маршрутизации в отсутствие информации для гиперкуба.

В 2002 году Рэкке построил полилогарифмически-конкурентный рандомизированный алгоритм для неориентированных сетей общего вида. Точнее говоря, он доказал, что для любого значения спроса существует маршрутизация, такая, что максимальная нагруженность ребра не более чем в polylog(n) раз превышает оптимальную для этого спроса [12]. Азар и др. в своей работе дополнили этот результат, предложив полиномиальный метод для расчета оптимальной маршрутизации в отсутствие информации для сети. Они также доказали, что для ориентированных сетей не существует логарифмического коэффициента эффективности маршрутизации в отсутствие информации. Недавно Хаджиагаи и др. предложили алгоритм маршрутизации в отсутствие информации, являющийся <math>O(log^2 n)</math>-конкурентным с высокой вероятностью в ориентированных сетях [8].

Специальная онлайновая модель исследовалась в работе [5], авторы которой определили так называемую формулировку «повторяющейся игры», в которой алгоритм может ежедневно выбирать новый маршрут. Это означает, что алгоритм не имеет информации о спросе, который возникнет на следующий день. Авторы предложили <math>1 + \varepsilon</math>-конкурентный алгоритм для этой модели.

В данной статье рассматривалась нагруженность ребер, однако в практическом плане нагруженность вершин может быть не менее интересна. Под нагруженностью вершины понимается отношение общего объема трафика через эту вершину к ее пропускной способности. Некоторые результаты для этой задачи можно найти в работах [7] и [3]. Остается открытым вопрос, можно ли применить для этой модели метод, разработанный для анализа нагруженности ребер. Еще один любопытный нерешенный вопрос заключается в том, существует ли более эффективный алгоритм для вычисления оптимального коэффициента эффективности маршрутизации в отсутствие информации для сети [1, 14].

12. Räcke, H.: Minimizing Congestions in General Networks. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002, pp. 43-52