Маршрутизация в мультисервисных сетях телекоммуникаций на основе модифицированного алгоритма Дейкстры

Abstract

Рассматривается проблема поиска оптимальных маршрутов на графе мультисервисной телекоммуникационной сети. Для данных сетей, кроме полосы пропускания, должны приниматься во внимание такие параметры качества обслуживания (QoS ), как потери пакетов, задержка пакетов, вариация времени задержки (джиттер). Задачу маршрутизации в мультисервисных сетях предлагается решать на основе критериев, учитывающих перечисленные параметры, согласно требованиям конкретных приложений. Эта задача сформулирована как многокритериальная задача поиска маршрута с минимальной стоимостью, причем поиск выполняется только на подмножестве осуществимых путей, удовлетворяющих ограничениям на параметры качества сервиса. Предложена модификация алгоритма Дейкстры, которая позволяет осуществлять многокритериальный поиск оптимального маршрута с учетом ограничений на каждый критерий в отдельности, а также в случае, когда стоимость маршрута неаддитивна. Приведены примеры расчетов, показывающие эффективность предложенного подхода в рамках сервис-ориентированной архитектуры. = The problem of optimal routes search for a multiservice telecommunication network graph is considered. For those networks, unless bandwidth, quality of service (QoS ) parameters such as error rates, transmission delay, jitter should be taken into account. It is proposed to solve the problem of routing in multiservice networks, using criteria that take into account the QoS parameters, as well as the requirements of specific applications. This problem is formulated as a multi-objective problem of searching for the route with the lowest cost (the shortests path), while the search is performed only on a feasible paths subset satisfying the constraints on the QoS parameters. In this case, the path cost is defined as the four criteria convolution to ensure the minimization of error rates, transmission delay and jitter as well as maximize bandwidth. A modification of Dijkstra’s algorithm, which enables multi-criteria search for an optimal route taking into account the constraints on each criterion separately, when the cost of the route is not additive, is proposed. Examples of calculations showing the effectiveness of the proposed approach within a service-oriented architecture.