Классификации задач маршрутизации multicast и unicast идентичны. Разница заключается в том, что в случае multicast процедуры оптимизации и задания значений метрик должны применяться к дереву маршрутов. Существует несколько хорошо известных задач маршрутизации multicast. Среди них можно выделить следующие наиболее часто используемые:

• «дерево Штейнера» (Steiner tree), используемая для нахождения дерева маршрутов с наименьшей стоимостью, является задачей NP-сложности [Salama97-1];

• «дерево Штейнера с удовлетворением требований» (constrained Steiner tree), используемая для нахождения дерева маршрутов с удовлетворением требований по значению задержки, является задачей NP-сложности [Salama97-1];

• «дерево с удовлетворением множественных требований» (multitree-constrained), является также задачей NP-сложности в случае введения предположения, что метрики, задающие требования, являются независимыми и определяются нецелочисленными или неограниченными целочисленными значениями [Rous97], Также эта задача может быть решена в полиномиальном времени, если все метрики задаются ограниченными целочисленными значениями или если все метрики зависимы от одной.

Примеры нахождения маршрутов и деревьев для различных условий представлены на рис. 3.6.

В [Kui02] заинтересованный читатель сможет найти исчерпывающую информацию о концепции и философии построения маршрутизации multicast, а в [Salama97-1,WangOO] - ряд алгоритмов, используемых для ее реализации.

⇐Управление информацией состояния | Управление трафиком и качество обслужевания в сети | Интеграция qos-маршрутизации - qos-маршрутизация и маршрутизация для best effort⇒