4551
правка
Маршрутизация: различия между версиями
Материал из WEGA
м
нет описания правки
Irina (обсуждение | вклад) Нет описания правки |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 65: | Строка 65: | ||
С точки зрения применения этих результатов самое важное заключается в том, что с их помощью можно рассчитать наилучшую стратегию маршрутизации для топологии сети с ограничениями на пропускную способность. Это исключительно полезный инструмент для планирования сетей. Используя данные механизмы анализа, эффективность имеющейся топологии можно проверить, не имея информации о трафике в сети. | С точки зрения применения этих результатов самое важное заключается в том, что с их помощью можно рассчитать наилучшую стратегию маршрутизации для топологии сети с ограничениями на пропускную способность. Это исключительно полезный инструмент для планирования сетей. Используя данные механизмы анализа, эффективность имеющейся топологии можно проверить, не имея информации о трафике в сети. | ||
Многие исследователи изучали различные варианты задач маршрутизации. Обзоры самых значимых моделей и результатов можно найти в работах [ | Многие исследователи изучали различные варианты задач маршрутизации. Обзоры самых значимых моделей и результатов можно найти в работах [10] и [11]. Алгоритмы маршрутизации в отсутствие информации первыми проанализировали Валиант и Бребнер [15]. Они рассматривали модель параллельного компьютера и исследовали конкретные архитектуры, такие как гиперкуб, квадратные решетки и т. п. Бородин и Хопкрофт изучали сети общего вида [6]. Они показали, что такие простые детерминированные стратегии, как маршрутизация в отсутствие информации, не могут быть по-настоящему эффективными для онлайновой машрутизации, и доказали нижнюю границу коэффициента конкурентоспособности алгоритмов маршрутизации в отсутствие информации. Эта нижняя граница впоследствии была улучшена Какламанисом и др. [9], они также предложили оптимальный детерминированный алгоритм маршрутизации в отсутствие информации для гиперкуба. | ||
В 2002 году Ракке построил полилогарифмический конкурентный рандомизированный алгоритм для неориентированных сетей общего вида. Точнее говоря, он доказал, что для любого значения спроса существует маршрутизация, такая, что максимальная нагруженность ребра не более чем в polylog(n) раз превышает оптимальную для этого спроса [12]. Азар и др. в своей работе дополнили этот результат, предложив полиномиальный метод для расчета оптимальной маршрутизации в отсутствие информации для сети. Они также доказали, что для ориентированных сетей не существует логарифмического коэффициента эффективности маршрутизации в отсутствие информации. Недавно Хаджиагаи и др. предложили алгоритм маршрутизации в отсутствие информации, являющийся O (log n)-конкурентным с высокой вероятностью в ориентированных сетях [8]. | В 2002 году Ракке построил полилогарифмический конкурентный рандомизированный алгоритм для неориентированных сетей общего вида. Точнее говоря, он доказал, что для любого значения спроса существует маршрутизация, такая, что максимальная нагруженность ребра не более чем в polylog(n) раз превышает оптимальную для этого спроса [12]. Азар и др. в своей работе дополнили этот результат, предложив полиномиальный метод для расчета оптимальной маршрутизации в отсутствие информации для сети. Они также доказали, что для ориентированных сетей не существует логарифмического коэффициента эффективности маршрутизации в отсутствие информации. Недавно Хаджиагаи и др. предложили алгоритм маршрутизации в отсутствие информации, являющийся <math>O(log^2 n)</math>-конкурентным с высокой вероятностью в ориентированных сетях [8]. | ||
Специальная онлайновая модель исследовалась в работе [5], авторы которой определили так называемую формулировку «повторяющейся игры», в которой алгоритм может ежедневно выбирать новый маршрут. Это означает, что алгоритм не имеет информации о спросе, который возникнет на следующий день. Авторы представили 1 + | Специальная онлайновая модель исследовалась в работе [5], авторы которой определили так называемую формулировку «повторяющейся игры», в которой алгоритм может ежедневно выбирать новый маршрут. Это означает, что алгоритм не имеет информации о спросе, который возникнет на следующий день. Авторы представили <math>1 + \varepsilon</math>-конкурентный алгоритм для этой модели. | ||
Для адаптивного случая существуют более эффективные алгоритмы, например, представленные в [2]. Рагхаван и Томпсон предложили эффективный алгоритм для оффлайнового случая [13]. | Для адаптивного случая существуют более эффективные алгоритмы, например, представленные в [2]. Рагхаван и Томпсон предложили эффективный алгоритм для оффлайнового случая [13]. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
В данной статье рассматривалась нагруженность ребер, однако в практическом плане нагруженность вершин может быть не менее интересна. Под нагруженностью вершины понимается отношение общего объема трафика через эту вершину к ее пропускной способности. Некоторые результаты для этой задачи можно найти в работах [ ] и [ ]. Остается открытым вопрос, можно ли применить для этой модели метод, разработанный для анализа нагруженности ребер. Еще один любопытный нерешенный вопрос заключается в том, существует ли более эффективный алгоритм для вычисления оптимального коэффициента эффективности маршрутизации в отсутствие информации для сети [1, 14]. | В данной статье рассматривалась нагруженность ребер, однако в практическом плане нагруженность вершин может быть не менее интересна. Под нагруженностью вершины понимается отношение общего объема трафика через эту вершину к ее пропускной способности. Некоторые результаты для этой задачи можно найти в работах [7] и [3]. Остается открытым вопрос, можно ли применить для этой модели метод, разработанный для анализа нагруженности ребер. Еще один любопытный нерешенный вопрос заключается в том, существует ли более эффективный алгоритм для вычисления оптимального коэффициента эффективности маршрутизации в отсутствие информации для сети [1, 14]. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||
