Алгоритмы прямой маршрутизации: различия между версиями

Для сетей определенной топологии представлены специальные прямые алгоритмы. Эти алгоритмы решают задачу прямой маршрутизации, в которой вначале строятся хорошие пути, а затем вычисляется эффективный план вброса пакетов. Пусть для некоторого набора пакетов C* и D* обозначают оптимальные значения нагруженности и протяженности, соответственно, для всех возможных наборов путей прохождения пакетов. Очевидно, что оптимальное время маршрутизации составляет <math>rt* = \Omega(C^* + D^*) \; </math>. Верхняя граница прямого алгоритма из [6] выражается в терминах этой нижней границы. Все алгоритм исполняются за время, полиномиальное относительно размера входного графа.

'''Дерево.''' Пусть граф G представляет собой произвольное дерево. Алгоритм прямой маршрутизации (глава 3.1, [6]) обеспечивает движение каждого пакета по кратчайшему пути из точки вброса до места назначения. План вброса вычисляется при помощи жадного алгоритма с учетом порядка пакетов. Время маршрутизации этого алгоритма является асимптотически оптимальным: <math>rt \le 2C^* + D^* -2 < 3 \cdot rt^* \; </math>.