4446
правок
Алгоритмы прямой маршрутизации: различия между версиями
Материал из WEGA
Алгоритмы прямой маршрутизации (посмотреть исходный код)
Версия от 14:10, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 52: | Строка 52: | ||
Единственное более раннее исследование алгоритмов прямой маршрутизации относилось к задаче перестановок на деревьях [3, 13]. В этих статьях было получено время маршрутизации O(n) для любого дерева с n вершинами. Это время является оптимальным в наихудшем случае, тогда как результат в [6] является асимптотически оптимальным для всех задач маршрутизации на деревьях. | Единственное более раннее исследование алгоритмов прямой маршрутизации относилось к задаче перестановок на деревьях [3, 13]. В этих статьях было получено время маршрутизации O(n) для любого дерева с n вершинами. Это время является оптимальным в наихудшем случае, тогда как результат в [6] является асимптотически оптимальным для всех задач маршрутизации на деревьях. | ||
Сайфер и коллеги [7] изучали онлайн-версию задачи прямой маршрутизации, в которой червь (пакет длины L) может быть повторно передан в случае, если он был брошен (они также допускали пропускную способность каналов равной <math>B \ge 1 \; </math>). Адлер и коллеги [1] изучали задачу прямой маршрутизации с ограничением по времени, в которой требуется спланировать в рамках заданного интервала времени максимальное количество пакетов. Они показали, что версия этой задачи с ограничением по времени является NP-полной, а также рассмотрели алгоритмы | Сайфер и коллеги [7] изучали онлайн-версию задачи прямой маршрутизации, в которой червь (пакет длины L) может быть повторно передан в случае, если он был брошен (они также допускали пропускную способность каналов равной <math>B \ge 1 \; </math>). Адлер и коллеги [1] изучали задачу прямой маршрутизации с ограничением по времени, в которой требуется спланировать в рамках заданного интервала времени максимальное количество пакетов. Они показали, что версия этой задачи с ограничением по времени является NP-полной, а также рассмотрели аппроксимационные алгоритмы на деревьях и сотовых сетях. Кроме того, был рассмотрен вопрос, насколько буферизация эффективна в решении этой задачи. | ||
В число других моделей безбуферной маршрутизации входят [[маршрутизация с сопоставлением]] [2], при которой пакеты движутся к местам назначения за счет обмена пакетами в смежных узлах, и [[срочная маршрутизация]] [4, 5, 8, 9], при которой пакеты следуют по каналам, ведущим их ближе к месту назначения, а если они не могут переместиться ближе из-за конфликтов, они перебрасываются на альтернативные направления. | В число других моделей безбуферной маршрутизации входят [[маршрутизация с сопоставлением]] [2], при которой пакеты движутся к местам назначения за счет обмена пакетами в смежных узлах, и [[срочная маршрутизация]] [4, 5, 8, 9], при которой пакеты следуют по каналам, ведущим их ближе к месту назначения, а если они не могут переместиться ближе из-за конфликтов, они перебрасываются на альтернативные направления. | ||
