7.2 Постановка задачи

Рассмотрим следующую модель сети передачи данных (СПД). СПД состоит из N узлов коммутации и М линий связи. Предполагается, что:

1) все линии связи абсолютно надежны;

2) все линии связи помехоустойчивы;

3) узлы коммутации имеют бесконечную память;

4) время обработки в узлах коммутации отсутствует;

5) длины всех сообщений независимы и распределены по показательному закону со средним значением [байт];

6) трафик, поступающий в сеть, состоит из сообщений, имеющих одинаковый приоритет, и образует пуассоновский поток со средним значением [сообщений/сек] для сообщений, возникающих в узле и предназначенных узлу j; обозначим:

— полный внешний трафик;

7) каждая линия связи состоит из единственного дуплексного канала связи с пропускной способностью, равной [байт/сек] - линия связи между узлами k и l); если линия связи между узлами к и I отсутствует, то

Обозначим через - долю потока проходящую по линии

Тогда:

где - величина потока в линии [сообщений/сек], обусловленная потоком

Для переменных должно выполняться условие сохранения потока в сети, которое записывается следующим образом:

Определим через - среднее время, затрачиваемое на передачу сообщения, которое возникло в узле i и предназначается узлу j (межконцевая задержка сообщения). Важной характеристикой качества функционирования сети передачи данных является средняя задержка сообщения в сети - Т, которая определяется как взвешенная сумма межконцевых задержек :

Применение формулы Литтла к сети очередей приводит к общему, и в то же время чрезвычайно простому результату, впервые полученному Л. Клейнроком:

где - среднее время пребывания сообщений в линии

Для получения аналитического вида величины средней задержки сообщения Т либо можно воспользоваться результатами главы 6 (формула 6.1), либо использовать следующие простые соображения. Среднее время пребывания сообщений в линии , состоящее из времени передачи сообщения - и времени ожидания в очереди определяется по формуле:

где

или

Обозначим: - величина потока в линии , выраженная в байтах/сек. Тогда:

При подстановке в выражение (2.6) получается выражение для средней задержки сообщений по сети:

Сделанные предположения и обозначения позволяют сформулировать задачу поиска таких значений переменных которые обеспечат оптимальное (наименьшее) значение величине Т. Известны:

1) топологическая структура СПД;

2) матрица входных потоков - ;

3) пропускные способности линий связи - ;

4) средняя длина сообщения - .

Требуется найти:

1) переменные (см. замечание) и, следовательно, потоки в линиях связи такие, что:

при выполнении ограничений:

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

Ограничение (7.15) предполагает, что для передачи сообщений из узла i в узел j может быть использовано более одного маршрута, то есть задача (7.11-7.15) описывает альтернативную процедуру выбора маршрутов.

Если условие (7.15) заменить на условие

(7.15 а)

то задача (7.11-7.14) совместно с условием (7.15 а) будет определять фиксированную маршрутизацию.

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

Введем переменную:

Иными словами, переменная , если линия связи используется для передачи потока в узел-адресат j хотя бы от одного узла-источника и равна 0, в противном случае.

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

Таким образом, задача (7.11-7.17) описывает К-путевую маршрутизацию. Заметим, что если положить величину К, равной 1, то ограничения (7.16) и (7.17) превратятся в ограничение (7.15 а), то есть мы вновь получим постановку задачи для фиксированной маршрутизации, что совершенно естественно.

Замечание. Формальным результатом решения задачи выбора оптимальных потоков в сети является множество переменных Зная эти переменные, легко определить величины потоков в линиях связи множество оптимальных маршрутов для всех пар узлов «источник - адресат» и доли от входящих потоков которые нужно передавать по оптимальным маршрутам. Сами переменные практического смысла не имеют и многие существующие алгоритмы решения задачи выбора оптимальных потоков, как правило, определяют лишь потоки в линиях связи Зная значения по формуле (7.10) можно определить значение минимальной задержки Т. Однако, в ряде случаев, необходимо знать, какие именно маршруты приводят к оптимальному распределению потоков.

Более строго, ставится следующая задача: для каждой пары узлов «источник - адресат необходимо определить множество оптимальных маршрутов - количество оптимальных маршрутов из узла в узел j) и доли потоков а - от входного потока , в соответствии с которыми используются маршруты Очевидно, что для фиксированной маршрутизации , то есть определяется единственный оптимальный маршрут. Решение данной задачи осуществляется в рамках соответствующих алгоритмов.