3.4. МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ КВАЗИСЛУЧАИНЫХ ПРОЦЕДУР ВЫБОРА МАРШРУТОВ

Общие сведения

Математическое обеспечение квазисл у чайных процедур состоит в определении вероятности передачи для каждой линии связи узла. Иначе определяется часть общего потока сообщений, направляемая в каждую исходящую лилию. При чисто случайной процедуре соответствующие вероятности «полагаются равными. Квазислучайная процедура учитывает статистическую информацию о параметрах линий связи, что позволяет оптимизировать используемое распределение вероятностей передач.

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

Квазислучайная процедура с локальной информацией

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

При априорно известных по результатам статистического анализа пропускной способности и надежности каждой из исходящих линий связи найти такое распределение «входящего в узел потока сообщений, при котором будет обеспечено минимальное среднее время задержки сообщений в узле.

Среднее время задержки в узле определяется соотношением

где — среднее время задержки при передаче по линии

связи, число исходящих линий связи; вероятность передачи по линии связи; интенсивности исходящих потоков по линии связи и, суммарного соответственно.

Величину определим на основе модели одноканальной системы обслуживания с ненадежным прибором:

где — соответственно пропускная способность, а-грузка, коэффициент простоя и среднее время восстановления линии связи.

Задача выбора оптимальных значений или, что то же, -формулируется следующим образом.

Найти значения при которых обеспечивается

по множеству наборов ограниченному условием

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

где — неопределенный множитель.

В качестве выражения для используем (3.8), заменив на Тогда из первых уравнений получим

Подставляя (3.11) в последнее уравнение системы, найдем неопределенный множитель, после чего окончательное решение примет следующий вид:

При расчетах по соотношению (3.12) может оказаться, что некоторые значения А имеют отрицательную величину. В этом случае необходимо исключить соответствующие линии связи из разрешенных для передачи и осуществить перерасчет для нового набора.

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

Множество разрешенных линий связи в первоначальном решении для конкретного сообщения не должно содержать тех линий связи, по которым это сообщение ранее передавалось в процессе случайного блуждания по сети. Расчеты, произведенные для случая пяти линий связи с одинаковыми но различными в диапазоне от 0,99 до 0,7, показывают, что применение оптимального квазислучайного распределения обеспечивает почти двухкратное сокращение среднего времени задержки по отношению к чисто случайной.

Квазислучайная процедура при наличии сетевой информации

В данном случае отличие состоит в том, что оптимизируется распределение потока не на узле, а всего внешнего потока, поступающего в сеть. Критерием оптимальности при этом является усредненное по всем линиям связи сети время задержки . Для решения данной задачи может быть использован метод отклонения потоков [12], сущность которого состоит в следующем.

Каждой линии связи назначается вес, который определяется производной среднего времени задержки, являющейся линейной скоростью возрастания при бесконечно малых приращениях потоков в линии связи: Далее эти веса используются для вычисления кратчайших маршрутов на основе метода Флойда или Дийкстры. Полученные при этом маршруты будут наилучшими в смысле снижения а следовательно, к ним может быть отклонена некоторая часть потока.

Определение отклоняемой части потока является внутренней задачей. После того как она будет решена, вычисляются новые кратчайшие маршруты и очередные отклоняемые части потоков.

Эта итеративная процедура продолжается до тех пор, пока имеет место уменьшение весового показателя сети. Алгоритм, реализующий вычисление оптимальных потоков в линиях связи, включает следующую последовательность шагов.

Шаг вычислить начальное реализуемое распределение потоком

Шаг 1. Вычислить веса линий связи

Шаг 2. Вычислить весовой показатель сети

Шаг 3. Решить задачу отыскания потоков по кратчайшим маршрутам. Для этого найти кратчайшие маршруты между всеми парами узлов сети для

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

где — номера абонентов сети; — поток между абонентами;

Шаг 4. Найти весовой показатель сети

Шаг 5 (правило остановки). Если где — выбранный допуск, то стоп, в противном случае перейти к шагу 6.

Шаг 6. Найти такое значение для которого потоки минимизируют I в сети (например, с помощью метода Фибоначи).

Шаг 7. Произвести отклонение потока, положив

Шаг перейти к шагу 1.

Для определения начальных реализуемых потоков сообщений на шаге 0 предложен следующий алгоритм [12, 47].

Шаг 0. Вычисляются веса линий связи при нулевых параметрах потоков: Весь внешний поток направляется в сеть по кратчайшим маршрутам и вычисляется Часть внешнего потока, направляемого в сеть, будем обозначать На данном шаге

Шаг Если то и конец (найден начальный реализуемый поток). Если то где — параметр, определяемый требуемой точностью.

Шаг 2. Вычислить потоки в линиях связи при внешних потоках по всем и I:

Шаг 3. Произвести операцию отклонения для потока Для этого необходимо выполнить шаги 1, 3, 6, 7 основного алгоритма отклонения потоков. Тогда Если то перейти к шагу 5, иначе к шагу 4.

Шаг 4. Проверить наличие реализуемых начальных решений. Если

где — положительные допуски, то реализуемых решений нет.

В противном случае переход к шагу 5.

Шаг и переход к шагу 1.

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

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

В чистом виде изложенный метод имеет преимущественно теоретическое значение, так не гарантирует отсутствия циклов и

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