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