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

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

Для адаптивного случая существуют более эффективные алгоритмы, например, представленные в [2]. Рагхаван и Томпсон предложили эффективный алгоритм для оффлайнового случая [13].