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