4501
правка
Маршрутизация: различия между версиями
Перейти к навигации
Перейти к поиску
→Применение
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
== Применение == | == Применение == | ||
С точки зрения применения этих результатов самое важное заключается в том, что с их помощью можно рассчитать наилучшую стратегию маршрутизации для топологии сети с ограничениями на пропускную способность. Это исключительно полезный инструмент для планирования сетей. Используя данные механизмы анализа, эффективность имеющейся топологии можно проверить, не имея информации о трафике в сети. | |||
Многие исследователи изучали различные варианты задач маршрутизации. Обзоры самых значимых моделей и результатов можно найти в работах [ ] и [ ]. Алгоритмы маршрутизации в отсутствие информации первыми проанализировали Валиант и Бребнер [15]. Они рассматривали модель параллельного компьютера и исследовали конкретные архитектуры, такие как гиперкуб, квадратные решетки и т. п. Бородин и Хопкрофт изучали сети общего вида [ ]. Они показали, что такие простые детерминированные стратегии, как маршрутизация в отсутствие информации, не могут быть по-настоящему эффективными для онлайновой машрутизации, и доказали нижнюю границу коэффициента конкурентоспособности алгоритмов маршрутизации в отсутствие информации. Эта нижняя граница впоследствии была улучшена Какламанисом и др. ([9]), они также предложили оптимальный детерминированный алгоритм маршрутизации в отсутствие информации для гиперкуба. | |||
В 2002 году Ракке построил полилогарифмический конкурентный рандомизированный алгоритм для неориентированных сетей общего вида. Точнее говоря, он доказал, что для любого значения спроса существует маршрутизация, такая, что максимальная нагруженность ребра не более чем в polylog(n) раз превышает оптимальную для этого спроса [12]. Азар и др. в своей работе дополнили этот результат, предложив полиномиальный метод для расчета оптимальной маршрутизации в отсутствие информации для сети. Они также доказали, что для ориентированных сетей не существует логарифмического коэффициента эффективности маршрутизации в отсутствие информации. Недавно Хаджиагаи и др. предложили алгоритм маршрутизации в отсутствие информации, являющийся O (log n)-конкурентным с высокой вероятностью в ориентированных сетях [8]. | |||
Специальная онлайновая модель исследовалась в работе [5], авторы которой определили так называемую формулировку «повторяющейся игры», в которой алгоритм может ежедневно выбирать новый маршрут. Это означает, что алгоритм не имеет информации о спросе, который возникнет на следующий день. Авторы представили 1 + "-конкурентный алгоритм для этой модели. | |||
Для адаптивного случая существуют более эффективные алгоритмы, например, представленные в [2]. Рагхаван и Томпсон предложили эффективный алгоритм для оффлайнового случая [13]. | |||
== Открытые вопросы == | == Открытые вопросы == | ||