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