4551
правка
Алгоритмы прямой маршрутизации: различия между версиями
Перейти к навигации
Перейти к поиску
Алгоритмы прямой маршрутизации (посмотреть исходный код)
Версия от 01:58, 29 ноября 2013
, 29 ноября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 35: | Строка 35: | ||
'''Дерево.''' Пусть граф G представляет собой произвольное дерево. Алгоритм прямой маршрутизации (глава 3.1, [6]) обеспечивает движение каждого пакета по кратчайшему пути из точки вброса до места назначения. План вброса вычисляется при помощи жадного алгоритма с учетом порядка пакетов. Время маршрутизации этого алгоритма является асимптотически оптимальным: <math>rt \le 2C^* + D^* -2 < 3 \cdot rt^* \; </math>. | '''Дерево.''' Пусть граф G представляет собой произвольное дерево. Алгоритм прямой маршрутизации (глава 3.1, [6]) обеспечивает движение каждого пакета по кратчайшему пути из точки вброса до места назначения. План вброса вычисляется при помощи жадного алгоритма с учетом порядка пакетов. Время маршрутизации этого алгоритма является асимптотически оптимальным: <math>rt \le 2C^* + D^* -2 < 3 \cdot rt^* \; </math>. | ||
Сотовая сеть. Граф G представляет собой d-мерную сотовую сеть (решетку) с n узлами [10]. Алгоритм прямой маршрутизации (глава 3.2, [6]) вначале строит эффективные пути для пакетов с нагруженностью C = O( | '''Сотовая сеть.''' Граф G представляет собой d-мерную сотовую сеть (решетку) с n узлами [10]. Алгоритм прямой маршрутизации (глава 3.2, [6]) вначале строит эффективные пути для пакетов с нагруженностью <math>C = O(d \; log n \cdot C^*)</math> и протяженностью <math>D = O(d^2 \cdot D^*)</math> (нагруженность с высокой вероятностью гарантирована). Затем, используя эти пути, вычисляется план вброса; при этом используется прямой алгоритм с временем маршрутизации | ||
rt = O( | <math>rt = O(d^2 log^2 n \cdot C^* + d^2 \cdot D^*) = O(d^2 log^2 n \cdot rt^*)</math>. | ||
Этот результат следует из более общего, приведенного там же, который утверждает, что если пути содержат не более b «поворотов», т.е. изменений размерности, то существует алгоритм прямого планирования с временем маршрутизации O(b | Этот результат следует из более общего, приведенного там же, который утверждает, что если пути содержат не более b «поворотов», т.е. изменений размерности, то существует алгоритм прямого планирования с временем маршрутизации <math>O(b \cdot C + D) \; </math>. Это следует из того, что сконструированные пути имеют <math>b = O(d \; log n)</math> поворотов. | ||
Бабочка. Граф G представляет собой сеть в форме бабочки с n входными и n выходными узлами [10]. В главе 3.3 [6] авторы исследовали задачу маршрутизации перестановок в бабочке, где каждый входной (выходной) узел является источником (адресатом) ровно одного пакета. Эффективный алгоритм прямой маршрутизации [6] вначале вычисляет хорошие пути для пакетов, используя метод Валианта [14, 15]: две бабочки соединяются «спина к спине», и каждый путь строится путем выбора случайного промежуточного узла в выходной части первой бабочки. Выбранные пути имеют нагруженность C = O(lg n) (с высокой вероятностью) и протяженность D = 2lg n = O(D*). Затем, используя эти пути, вычисляется план вброса с временем маршрутизации, очень близким к оптимальному – rt <5lgn = O(rt*). | '''Бабочка.''' Граф G представляет собой сеть в форме бабочки с n входными и n выходными узлами [10]. В главе 3.3 [6] авторы исследовали задачу маршрутизации перестановок в бабочке, где каждый входной (выходной) узел является источником (адресатом) ровно одного пакета. Эффективный алгоритм прямой маршрутизации [6] вначале вычисляет хорошие пути для пакетов, используя метод Валианта [14, 15]: две бабочки соединяются «спина к спине», и каждый путь строится путем выбора случайного промежуточного узла в выходной части первой бабочки. Выбранные пути имеют нагруженность C = O(lg n) (с высокой вероятностью) и протяженность D = 2lg n = O(D*). Затем, используя эти пути, вычисляется план вброса с временем маршрутизации, очень близким к оптимальному – rt <5lgn = O(rt*). | ||
Гиперкуб. Граф G представляет собой гиперкуб с n узлами [10]. Прямой алгоритм маршрутизации в главе 3.4 [6] решает задачу маршрутизации перестановок: вначале он вычисляет хорошие пути для пакетов путем выбора единственного случайного промежуточного узла для каждого пакета; затем строится подходящий план вброса с временем маршрутизации rt < 14lg n, являющимся оптимальным в наихудшем случае, поскольку существуют перестановки, для которых D* = £?(lg n). | Гиперкуб. Граф G представляет собой гиперкуб с n узлами [10]. Прямой алгоритм маршрутизации в главе 3.4 [6] решает задачу маршрутизации перестановок: вначале он вычисляет хорошие пути для пакетов путем выбора единственного случайного промежуточного узла для каждого пакета; затем строится подходящий план вброса с временем маршрутизации rt < 14lg n, являющимся оптимальным в наихудшем случае, поскольку существуют перестановки, для которых D* = £?(lg n). | ||