4501
правка
Маршрутизация: различия между версиями
Материал из WEGA
м
→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показано 14 промежуточных версий этого же участника) | |||
| Строка 11: | Строка 11: | ||
== Постановка задачи == | == Постановка задачи == | ||
''Маршрутизация'' является одной из самых широко используемых техник в современных компьютерных сетях. Под маршрутизацией понимается выбор путей в сети, по которым следует отправлять данные. Спрос обычно возникает случайным образом в некоторых узлах сети, и алгоритмы маршрутизации должны быть способны отправить данные по месту их назначения. Данные пересылаются через промежуточные узлы при помощи соединительных звеньев | ''Маршрутизация'' является одной из самых широко используемых техник в современных компьютерных сетях. Под маршрутизацией понимается выбор путей в сети, по которым следует отправлять данные. Спрос обычно возникает случайным образом в некоторых узлах сети, и алгоритмы маршрутизации должны быть способны отправить данные по месту их назначения. Данные пересылаются через промежуточные узлы при помощи соединительных звеньев (линий связи) с учетом топологии сети. Пользователь ждет от сети гарантии наличия необходимой пропускной способности в процессе передачи данных, что означает, что сеть ведет себя так, словно ее узлы напрямую соединены физическим каналом связи. Подобный сервис носит название ''постоянного виртуального соединения'' (permanent virtual circuit, PVC). Для моделирования реальных ситуаций будем предполагать, что спрос возникает ''в режиме онлайн'', задается точкой-источником и точкой-получателем и включает требования к пропускной способности. | ||
Аналогичные задачи маршрутизации возникают в других областях | Аналогичные задачи маршрутизации возникают в других областях – например, в параллельных вычислениях. В таком случае имеются несколько процессоров, соединенных кабелями. В ходе работы у определенных процессоров появляются некоторые данные, которые должны быть переданы в конкретные точки назначения. В данном случае также требуется решать задачу маршрутизации. Далее будет рассматриваться главным образом сетевая модель, а не модель с параллельными компьютерами. | ||
В любой конкретной ситуации имеется несколько возможных вариантов маршрутизации. Естественным образом возникает вопрос, какой алгоритм работает лучше всего. Для нахождения лучшего алгоритма следует определить целевую функцию, выражающую эффективность алгоритма. Например, целью может являться минимизация сетевой нагрузки. Нагрузку можно измерять разными способами, самым естественным из которых представляется измерение процента | В любой конкретной ситуации имеется несколько возможных вариантов маршрутизации. Естественным образом возникает вопрос, какой алгоритм работает лучше всего. Для нахождения лучшего алгоритма следует определить целевую функцию, выражающую эффективность алгоритма. Например, целью может являться минимизация сетевой нагрузки. Нагрузку можно измерять разными способами, самым естественным из которых представляется измерение процента использования вершин или каналов сети. В онлайновой формулировке любопытно сравнить поведение алгоритма маршрутизации, разработанного для конкретного экземпляра задачи, с наилучшим возможным алгоритмом. | ||
Существуют два фундаментальных подхода к разработке алгоритмов маршрутизации. Первый подход заключается в ''адаптивной маршрутизации'' (adaptive routing), учитывающей фактическую | Существуют два фундаментальных подхода к разработке алгоритмов маршрутизации. Первый подход заключается в ''адаптивной маршрутизации'' (adaptive routing), учитывающей фактическую нагрузку узлов или каналов связи. Второй подход представляет собой ''[[маршрутизация в отсутствие информации|маршрутизацию в отсутствие информации]]'' (oblivious routing), без использования каких-либо данных о текущем состоянии сети. Далее будет рассматриваться только второй подход. | ||
== Нотация и определения == | == Нотация и определения == | ||
| Строка 26: | Строка 26: | ||
Пусть дана сеть с | Пусть дана сеть с информацией о пропускной способности 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 рассматривается как неориентированное ребро с той же пропускной способностью, то получается ориентированная сеть, эквивалентная исходной. | ||
| Строка 38: | Строка 38: | ||
''Нагруженность'' спроса D по маршруту r составляет <math>con(r, D) = max_{e \in E} con(e, r, D)</math>. | ''Нагруженность'' спроса D по маршруту r составляет <math>con(r, D) = max_{e \in E} \; con(e, r, D)</math>. | ||
| Строка 52: | Строка 52: | ||
'''Задача''' | '''Задача''' | ||
'''Дано''': Сеть с | '''Дано''': Сеть с информацией о пропускной способности G = (V, E, c). | ||
'''Требуется''': Найти маршрут r в отсутствие информации с минимальным <math>P_r</math>. | '''Требуется''': Найти маршрут r в отсутствие информации с минимальным <math>P_r</math>. | ||
| Строка 63: | Строка 63: | ||
== Применение == | == Применение == | ||
С точки зрения применения этих результатов самое важное заключается в том, что с их помощью можно рассчитать наилучшую стратегию маршрутизации для топологии сети с ограничениями на пропускную способность. Это исключительно полезный инструмент для планирования сетей. Используя данные механизмы анализа, эффективность имеющейся топологии можно проверить, не имея информации о трафике в сети. | |||
Многие исследователи изучали различные варианты задач маршрутизации. Обзоры самых значимых моделей и результатов можно найти в работах [10] и [11]. Алгоритмы маршрутизации в отсутствие информации первыми проанализировали Валиант и Бребнер [15]. Они рассматривали модель с параллельными компьютерами и исследовали конкретные архитектуры, такие как гиперкуб, квадратные решетки и т. п. Бородин и Хопкрофт изучали сети общего вида [6]. Они показали, что такие простые детерминированные стратегии, как маршрутизация в отсутствие информации, не могут быть по-настоящему эффективными для онлайновой машрутизации, и доказали нижнюю границу коэффициента конкурентоспособности алгоритмов маршрутизации в отсутствие информации. Эта нижняя граница впоследствии была улучшена Какламанисом и др. [9], которые также предложили оптимальный детерминированный алгоритм маршрутизации в отсутствие информации для гиперкуба. | |||
В 2002 году Рэкке построил полилогарифмически-конкурентный рандомизированный алгоритм для неориентированных сетей общего вида. Точнее говоря, он доказал, что для любого значения спроса существует маршрутизация, такая, что максимальная нагруженность ребра не более чем в polylog(n) раз превышает оптимальную для этого спроса [12]. Азар и др. в своей работе дополнили этот результат, предложив полиномиальный метод для расчета оптимальной маршрутизации в отсутствие информации для сети. Они также доказали, что для ориентированных сетей не существует логарифмического коэффициента эффективности маршрутизации в отсутствие информации. Недавно Хаджиагаи и др. предложили алгоритм маршрутизации в отсутствие информации, являющийся <math>O(log^2 n)</math>-конкурентным с высокой вероятностью в ориентированных сетях [8]. | |||
Специальная онлайновая модель исследовалась в работе [5], авторы которой определили так называемую формулировку «повторяющейся игры», в которой алгоритм может ежедневно выбирать новый маршрут. Это означает, что алгоритм не имеет информации о спросе, который возникнет на следующий день. Авторы предложили <math>1 + \varepsilon</math>-конкурентный алгоритм для этой модели. | |||
Для адаптивного случая существуют более эффективные алгоритмы, например, представленные в [2]. Рагхаван и Томпсон предложили эффективный алгоритм для оффлайнового случая [13]. | |||
== Открытые вопросы == | |||
В данной статье рассматривалась нагруженность ребер, однако в практическом плане нагруженность вершин может быть не менее интересна. Под нагруженностью вершины понимается отношение общего объема трафика через эту вершину к ее пропускной способности. Некоторые результаты для этой задачи можно найти в работах [7] и [3]. Остается открытым вопрос, можно ли применить для этой модели метод, разработанный для анализа нагруженности ребер. Еще один любопытный нерешенный вопрос заключается в том, существует ли более эффективный алгоритм для вычисления оптимального коэффициента эффективности маршрутизации в отсутствие информации для сети [1, 14]. | |||
== Экспериментальные результаты == | |||
Авторы [4] применили свой метод к топологиям сетей поставщиков услуг Интернета и обнаружили, что полученные оптимальные коэффициенты эффективности для маршрутизации в отсутствие информации на удивление малы – от 1,4 до 2. Другие исследования этого вопроса привели к похожим результатам [1, 14]. | |||
== См. также == | |||
* [[Приближенное решение задачи о максимальном потоке]] | |||
* [[Алгоритмы прямой маршрутизации]] | |||
* [[Балансировка нагрузки]] | |||
* [[Мобильные агенты и исследования]] | |||
* [[Маршрутизация в отсутствие информации]] | |||
* [[Вероятностная пересылка данных в беспроводных сетях датчиков]] | |||
==Литература== | ==Литература== | ||
| Строка 90: | Строка 112: | ||
11. Leonardi, S.: On-line network routing. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms - The State of the Art. Chap. 11, pp. 242-267. Springer, Heidelberg (1998) | 11. Leonardi, S.: On-line network routing. In: Fiat, A., Woeginger, G. (eds.) Online Algorithms - The State of the Art. Chap. 11, pp. 242-267. Springer, Heidelberg (1998) | ||
12. | 12. Räcke, H.: Minimizing Congestions in General Networks. In: Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002, pp. 43-52 | ||
13. Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365-374 (1987) | 13. Raghavan, P., Thompson, C.D.: Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica 7, 365-374 (1987) | ||
