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

Концепция принудительной маршрутизации 255

Пусть d (с, j) является метрикой канала (с, j) .■ Для любого маршрута Р = (с, j, к,…, I, т) метрика d (Р) является:

• аддитивной, если d (Р) =d (с, j) +d (j, k) +…+d (1, m);

• мультипликативной, если d (P) =-d (c, j ) d (j , k) …d (l,m);

• вогнутой, если d (P) =min{d (c, j ) +d (j , k) +…+d (1, m) }.

Такие метрики как задержка, джиттер задержки и количество шагов являются аддитивными, вероятностные метрики (в том числе и вероятность потери пакета) - мультипликативными, а метрика полосы пропускания - вогнутой.

Как уже было сказано выше, нахождение выполнимого маршрута с двумя и более независимыми требованиями по качеству обслуживания является задачей NP-сложности, т.е. и алгоритм минимизации значения целевой функции является также задачей NP-сложности. Отметим, что, учитывая классификацию метрик, представленное утверждение справедливо как для аддитивных, так и мультипликативных метрик. Только в случае поиска выполнимого пути по вогнутой (т.е. по полосе пропускания) и еше одной какой-либо метрике вычисления осуществимы.

⇐Методы и метрики обеспечения качества обслуживания | Управление трафиком и качество обслужевания в сети | Теоретическая модель сети на основе графа⇒