Телекоммуникационные технологии. Том 1



Базовые характеристики маршрутизации на основе ограничений


Маршрутизация на основе ограничений должна, по крайней мере, иметь возможность автоматически получать базовые, приемлемые решения задачи размещения пути для канала передачи данных.

Вообще, известно, что проблема маршрутизации на основе ограничений трудно разрешима для большинства реалистичных ограничений. Однако, на практике для нахождения приемлемого пути, если он существует, может использоваться очень простая хорошо известная эвристика (смотри, например, [9]):

  1. Сначала отбрасываются ресурсы, которые не удовлетворяют требованиям атрибутов канала передачи данных.
  2. Затем, для оставшегося графа связей запускается алгоритм поиска кратчайшего пути.

Ясно, что если приемлемый путь для заданного канала передачи данных существует, тогда выше предложенная простая процедура его найдет. Могут быть специфицированы дополнительные правила для разрубания узлов и выполнения дальнейшей оптимизации. Вообще, оптимизация обычно сводится к минимизации перегрузки. Однако когда нужно маршрутизировать несколько каналов передачи данных, можно показать, что выше предложенный алгоритм не всегда находит решение, даже когда такое решение существует.




Содержание  Назад  Вперед