На момент написания книги было предложено чрезвычайно большое количество алгоритмов обеспечения QoS-маршрутизации, в финальном отчете европейского проекта COST 263 «Quality of Future Internet Services» [COST263-03] заинтересованный читатель найдет исчерпывающий анализ данной проблемы.

Ниже перечислены наиболее известные алгоритмы QoS-маршрутизации для решения задачи MPC (см. п. 3.3.1.4 данной главы):

• Д. Джаффе в [Jaffe84] еще в 1984 году были предложены теоретические алгоритмы. Олин из алгоритмов предполагает использование метрики, построенной на линейной комбинации двух метрик (в оригинале - двух весов канала, отражающие различные его параметры), для поиска наикратчайшего пути. Существенно позднее, в 1998 году, в [Andrew98] алгоритм Джаффе был расширен для случая использования в задаче MPC т метрик.

Основным недостатком предложенного алгоритма и его модификации яачяется использование линейной функции, что в соответствии с доказательством, приведенным в [MieghemOl], ведет к некорректному результату функционирования, заключающемуся в том, что выполнимый путь может существовать и не быть найденным. Это объясняется тем, что только при использовании алгоритмом поиска оптимального пути по нелинейной функции выполнимый путь будет найден, если он существует. Кроме того, высокая вычислительная сложность также является серьезным недостатком.

• А. Ивата и др. в [Iwata96] был предложен элегантный алгоритм, заключающийся в организации последовательного вычисления выполнимого пути. Сначала находится оптимальный путь (пути) по одной из метрик и далее алгоритм проверяет его на оптимальность для остальных метрик. В случае невыполнения поставленных условий оптимизация проводится'по другой метрике до тех пор, пока не будет найден выполнимый путь.

⇐Факторы, влияющие на «накладные расходы» | Управление трафиком и качество обслужевания в сети | Перспективные задачи для оов-маршрутизации⇒