4551
правка
Алгоритмы прямой маршрутизации: различия между версиями
Материал из WEGA
Алгоритмы прямой маршрутизации (посмотреть исходный код)
Версия от 23:43, 28 ноября 2013
, 28 ноября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
== Основные результаты == | == Основные результаты == | ||
Буш, Магдон-Исмаил, Маврониколас и Спиракис представили в своей книге [6] исчерпывающее исследование прямых алгоритмов. Они изучали различные аспекты прямой маршрутизации – такие как вычислительная сложность задач прямых вычислений и построение эффективных прямых алгоритмов. | Буш, Магдон-Исмаил, Маврониколас и Спиракис представили в своей книге [6] исчерпывающее исследование прямых алгоритмов. Они изучали различные аспекты прямой маршрутизации – такие как вычислительная сложность задач прямых вычислений и построение эффективных прямых алгоритмов. | ||
Трудности прямой маршрутизации | Трудности прямой маршрутизации | ||
В главе 4 [6] показано, что оптимальная задача прямого планирования, в которой пути заранее заданы и требуется вычислить оптимальный план вброса пакетов, обеспечивающий достижение минимального времени маршрутизации, является NP-полной. Этот результат был получен при помощи редукции алгоритма раскраски вершин; задача раскраски вершин преобразуется в соответствующую задачу прямого планирования на двумерной решетке. Кроме того, было показано, что найти приближенные решения задачи прямого планирования так же сложно, как приближенные решения задачи раскраски вершин. Вопрос о том, какие виды аппроксимаций можно получить за полиномиальное время, изучается в той же работе для графов общего вида и некоторых отдельных разновидностей. | В главе 4 [6] показано, что оптимальная задача прямого планирования, в которой пути заранее заданы и требуется вычислить оптимальный план вброса пакетов, обеспечивающий достижение минимального времени маршрутизации, является NP-полной. Этот результат был получен при помощи редукции алгоритма раскраски вершин; задача раскраски вершин преобразуется в соответствующую задачу прямого планирования на двумерной решетке. Кроме того, было показано, что найти приближенные решения задачи прямого планирования так же сложно, как приближенные решения задачи раскраски вершин. Вопрос о том, какие виды аппроксимаций можно получить за полиномиальное время, изучается в той же работе для графов общего вида и некоторых отдельных разновидностей. | ||
Прямая маршрутизация в графах общего вида | Прямая маршрутизация в графах общего вида | ||
В главе 3 [6] приводится прямой алгоритм, решающий в приближенном виде задачу оптимального прямого планирования в сетях с топологиями общего вида. Пусть имеются набор пакетов и соответствующие пути. Вычисление плана вброса занимает полиномиальное время относительно размера графа и числа пакетов. Время маршрутизации характеризуется такими параметрами, как C – нагруженность путей передачи пакетов (максимальное число пакетов, использующих ребро графа), и D – протяженность (максимальная длина любого пути). | В главе 3 [6] приводится прямой алгоритм, решающий в приближенном виде задачу оптимального прямого планирования в сетях с топологиями общего вида. Пусть имеются набор пакетов и соответствующие пути. Вычисление плана вброса занимает полиномиальное время относительно размера графа и числа пакетов. Время маршрутизации характеризуется такими параметрами, как C – нагруженность путей передачи пакетов (максимальное число пакетов, использующих ребро графа), и D – протяженность (максимальная длина любого пути). | ||
В [6] установлено существование простого жадного алгоритма прямого планирования с временем маршрутизации rt = O(C | В [6] установлено существование простого жадного алгоритма прямого планирования с временем маршрутизации <math>rt = O(C \cdot D)</math>. В этом алгоритме пакеты обрабатываются в произвольном порядке; каждому пакету назначается наименьшее возможное время вброса. Полученное время маршрутизации является оптимальным в наихудшем случае, поскольку существуют примеры задач прямого планирования, для которых ни один алгоритм прямого планирования не может обеспечить лучшего времени маршрутизации. Тривиальная нижняя граница времени маршрутизации любой задачи прямого планирования составляет <math>\Omega (C + D) \; </math>, поскольку ни один алгоритм не может доставить пакеты быстрее, чем позволяют значения нагруженности и протяженности путей. Таким образом, в общем случае время маршрутизации для алгоритма в [6] составляет <math>rt = O((rt^*)^2) \; </math>, где rt* - оптимальное время маршрутизации. | ||
Прямая маршрутизация в графах некоторых отдельных разновидностей | Прямая маршрутизация в графах некоторых отдельных разновидностей | ||
Для сетей определенной топологии представлены специальные прямые алгоритмы. Эти алгоритмы решают задачу прямой маршрутизации, в которой вначале строятся хорошие пути, а затем вычисляется эффективный план вброса пакетов. Пусть для некоторого набора пакетов C* и D* обозначают оптимальные значения нагруженности и протяженности, соответственно, для всех возможных наборов путей прохождения пакетов. Очевидно, что оптимальное время маршрутизации составляет rt* = Q(C* + D*). Верхняя граница прямого алгоритма из [6] выражается в терминах этой нижней границы. Все алгоритм исполняются за время, полиномиальное относительно размера входного графа. | Для сетей определенной топологии представлены специальные прямые алгоритмы. Эти алгоритмы решают задачу прямой маршрутизации, в которой вначале строятся хорошие пути, а затем вычисляется эффективный план вброса пакетов. Пусть для некоторого набора пакетов C* и D* обозначают оптимальные значения нагруженности и протяженности, соответственно, для всех возможных наборов путей прохождения пакетов. Очевидно, что оптимальное время маршрутизации составляет rt* = Q(C* + D*). Верхняя граница прямого алгоритма из [6] выражается в терминах этой нижней границы. Все алгоритм исполняются за время, полиномиальное относительно размера входного графа. | ||
Дерево. Пусть граф G представляет собой произвольное дерево. Алгоритм прямой маршрутизации (глава 3.1, [6]) обеспечивает движение каждого пакета по кратчайшему пути из точки вброса до места назначения. План вброса вычисляется при помощи жадного алгоритма с учетом порядка пакетов. Время маршрутизации этого алгоритма является асимптотически оптимальным: rt <2C* + D* -2< 3-rt*. | Дерево. Пусть граф G представляет собой произвольное дерево. Алгоритм прямой маршрутизации (глава 3.1, [6]) обеспечивает движение каждого пакета по кратчайшему пути из точки вброса до места назначения. План вброса вычисляется при помощи жадного алгоритма с учетом порядка пакетов. Время маршрутизации этого алгоритма является асимптотически оптимальным: rt <2C* + D* -2< 3-rt*. | ||
Сотовая сеть. Граф G представляет собой d-мерную сотовую сеть (решетку) с n узлами [10]. Алгоритм прямой маршрутизации (глава 3.2, [6]) вначале строит эффективные пути для пакетов с нагруженностью C = O(dlog n ■ C*) и протяженностью D = O(d2 ■ D*) (нагруженность с высокой вероятностью гарантирована). Затем, используя эти пути, вычисляется план вброса; при этом используется прямой алгоритм с временем маршрутизации | Сотовая сеть. Граф G представляет собой d-мерную сотовую сеть (решетку) с n узлами [10]. Алгоритм прямой маршрутизации (глава 3.2, [6]) вначале строит эффективные пути для пакетов с нагруженностью C = O(dlog n ■ C*) и протяженностью D = O(d2 ■ D*) (нагруженность с высокой вероятностью гарантирована). Затем, используя эти пути, вычисляется план вброса; при этом используется прямой алгоритм с временем маршрутизации | ||
rt = O(d2 log2 n ■ C* + d2 ■ D*) = O(d2 log2 n • rt*): | rt = O(d2 log2 n ■ C* + d2 ■ D*) = O(d2 log2 n • rt*): | ||
| Строка 34: | Строка 41: | ||
Бабочка. Граф 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). | ||
Нижняя граница для буферизации | Нижняя граница для буферизации | ||
В главе 5 в [6] рассматривалась также дополнительная задача, касающаяся объема буферизации, необходимого для обеспечения малого времени маршрутизации. Было показано, что существует задача прямого планирования, для которой каждому прямому алгоритму требуется время маршрутизации Q{C ■ D); в то же время C + D = &{JC-D) = o(C ■ D). Если буферизация пакетов допускается, то существуют известные алгоритмы планирования пакетов ([11, 12]) с временем маршрутизации, очень близким к оптимальному (O(C + D)). В [6] было показано, что в случае конкретной задачи планирования пакетов для того, чтобы превратить прямой план вброса с временем маршрутизации O(C ■ D) в план пакетов с временем маршрутизации O(C + D), необходимо выполнять буферизацию пакетов в узлах сети в сумме Q(N413) раз. Здесь буферизация пакета заключается в хранении пакета в промежуточном буферном узле на протяжении одного временного такта; N – количество пакетов. | В главе 5 в [6] рассматривалась также дополнительная задача, касающаяся объема буферизации, необходимого для обеспечения малого времени маршрутизации. Было показано, что существует задача прямого планирования, для которой каждому прямому алгоритму требуется время маршрутизации Q{C ■ D); в то же время C + D = &{JC-D) = o(C ■ D). Если буферизация пакетов допускается, то существуют известные алгоритмы планирования пакетов ([11, 12]) с временем маршрутизации, очень близким к оптимальному (O(C + D)). В [6] было показано, что в случае конкретной задачи планирования пакетов для того, чтобы превратить прямой план вброса с временем маршрутизации O(C ■ D) в план пакетов с временем маршрутизации O(C + D), необходимо выполнять буферизацию пакетов в узлах сети в сумме Q(N413) раз. Здесь буферизация пакета заключается в хранении пакета в промежуточном буферном узле на протяжении одного временного такта; N – количество пакетов. | ||
