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

''Маршрутизация'' является одной из самых широко используемых техник в современных компьютерных сетях. Под маршрутизацией понимается выбор путей в сети, по которым следует отправлять данные. Спрос обычно возникает случайным образом в некоторых узлах сети, и алгоритмы маршрутизации должны быть способны отправить данные по месту их назначения. Данные пересылаются через промежуточные узлы при помощи соединительных звеньев (линий связи) с учетом топологии сети. Пользователь ждет от сети гарантии наличия необходимой пропускной способности в процессе передачи данных, что означает, что сеть ведет себя так, словно ее узлы напрямую соединены физическим каналом связи. Подобный сервис носит название ''постоянного виртуального соединения'' (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>.

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

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