Моделирование алгоритма маршрутизации

IНО2α2рНОНЗ(1 - рНОНО)  = IНО3α´3; I´´НО3α´´3 = IНО4α4;

λ(1 - π) (1 – а1) (1 – а2) = ΙΠ1α1;

[(J1 - J´1)µ1 + (JНЗ2 - J´НЗ2) µ2]( 1 – а1) (1 – а2) = ΙΠВ1α1;

[(JНЗ1 - J´НЗ1)µ1 + (JНЗ2 - J´НЗ2) µ2]( 1 – а1) (1 – а2) = ΙНЗ1α1;

[(JНО1 - J´НО1)µ1 + (JНО2 - J´НО2) µ2(JЗ - J´З)µ3]( 1 – а1) (1 – а2) = ΙНО1α1.

 

3.2 Приближенный алгоритм расчета модели, основанный на использовании формулы Эрланга

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

Введем обозначения:

x1=J1µ1+J2µ2; x2=JНЗ1µ1+JНЗ2µ2; x3=JНО1µ1+JНО2µ2+J3µ3.

Тогда интенсивность потока повторных вызовов х определяют из решения неявного уравнения

х = х1 + х2 + х3,                                                                                              (3.2)

где х1, х2, х3 находят из формул

x1 = [λ(а1с1 + (1 – а1)(а2 + (1 – а2)(1 – р1(1 - π(х))H1)]/[1 – a1c1 – (1 – a1)(a2 + (1 – a2)(1 – p1(1 – π(x))) H2],

x2 = x´2/ x´´2,

x´2 = (1 – a1)(1 – a2)(1 – π(x))p1(λH1(1 – p2) + x1(H2(1 – p2) – HНОБ)1 - pНОНЗ)) + x HНОБ(1 - pНОНЗ)),

x3 = x´3/ x´´3,

x´3 = (1 - π(х)(1 – а1)(а2 + (1 – а2)р1((λHНО1 + x1HНО1)р2(1 – p3) + x2 HБНОрНЗНЗ(1 - pНЗНО)),

x´´3 = 1 – a1c1 – (1 – a1)(a2HНОБ + (1 – a2)(π(х)HНОБ + (1 – а2)(π(х)HНОБ + (1 - π(х))((1 – p1)HНОБ + p1 pНОНЗ(1 - pНОНО) HНОНО))).

В записи х 1, х2, х3 использованы следующие обозначения:

 

 

причем константы P*, N*z, N*0 зависят только от входных параметров модели и определяются из выражений:

P* = 1 + α1p1/α2 + α1p1p2p3/α´´3 + α1p1p2(1 - p3)/α´3 + α1p1p2p3/α4;

N*z = 1 + α1p1/α2 + α1p1pНЗНЗpНЗНО/α´´3 + α1p1pНЗНЗ(1 - pНЗНО)/α´3 + α1p1pНЗНЗpНЗНО/α4;

N*0 = 1 + α1p1/α2 + α1p1pНОНЗpНОНО/α´´3 + α1p1pНОНЗ(1 - pНОНО)/α´3 + α1p1pНОНЗpНОНО/α4.

Неявные уравнения (3.2) можно решать методом последовательных приближений, используя на каждом шаге приближения формулу Эрланга. После определения х находятся оценки всех вероятностных характеристик исходной модели таким же образом, как это было сделано для базовой модели. Они имеют следующий вид:

                                                                           (3.3)

 

 

 

 

3.3 Преобразование модели полнодоступного пучка простейшего типа

При нахождении оценок вероятностных характеристик исследуемой модели МТС прямого пучка МТС существенно предположение о том, что поток повторных вызовов является пуассоновским. В области малой и большой нагрузки, а также для больших пучков это допущение оказывается вполне приемлемым. Дальнейшее уточнение оценок, естественно, должно идти по пути устранения тех причин, которые эту «пуассоновость» нарушают. Рассмотрим абонентов, которые в последней попытке соединения получили отаз из-за занятости всех линий пучка. Очевидно, что следующая попытка соединения от таких абонентов с большей вероятностью попадет в состояние занятости всех линий пучка, чем первичная попытка. Это свойство модели нарушает нашу гипотезу о пуассоновости суммарного потока повторных вызовов, поскольку при ее выполнении все состояния системы для потсупающих повторных вызовов равновероятны.

Теперь понятно, как можно уточнить приближенный метод, используемый в предыдущем разделе. Сохраним в упрощенной модели абонентов, повторяющих вызов из-за занятости всех доступных линий, а на пуассоновский заменим все оставшиеся потоки повторных вызовов. Для того чтобы это сделать, необходимо провести уточнение процесса взаимодействия абонента и обслуживающей системы, позволяющее выделить в общей массе повторяющих вызов абонентов тех, что получили в последней попытке отказ из-за занятости доступных линий. Сделаем некоторые изменения в символах,  для обозначения причины отказа в обслуживании. Теперь символ ЛЗ будет означать отказ по причине занятости линий пучка, а Б´ - все прочие отказы из-за блокировки (кроме НЗ). Чтобы несколько упростить дальнейшее изложение, предположим, что а1 = а2 = 0. смысл оставшихся символов тот же, что и в утонченной модели, рассмотренной в предыдущем разделе.

Перейдем к определению компонент марковского процесса, описывающего функционирование модели. По аналогии с разделом 4 посмотрим, какие изменения произойдут в определении компонент по сравнению с утонченным вариантом модели. Поскольку мы предположили, что а1 = 0, то ИПВ 1-го типа не будет. Зато ИПВ, образующиеся из-за блокировки, разделяются уже на шесть групп. Любую конечную комбинацию символов Б´, ЛЗ обозначим { Б´, ЛЗ }. Тогда определение компонент марковского процесса, описывающего функционирование модели, имеет вид: : j2(t) – число абонентов, имеющих в момент времени t предысторию взаимодействия с обслуживающей системой вид ({Б´, ЛЗ}, Б´); jЛЗ2(t) - … - ({Б´, ЛЗ}, ЛЗ); jНЗ2(t) - … (..., НЗ, {Б´, ЛЗ}; (..., НЗ, {Б´, ЛЗ}, НЗ), ({Б´, ЛЗ}, НЗ), (..., НО, {Б´, ЛЗ}, НЗ); jНЗЛЗ2(t) - ,…, (..., НЗ,{Б´, ЛЗ}, ЛЗ); jНО2(t) - …, (..., НО,{Б´, ЛЗ}, Б´);  jНОЛЗ2(t) - …, (..., НО,{Б´, ЛЗ}, ЛЗ).

Построение приближенного метода начнем в записи законов сохранения. В принятых обозначениях они имеют вид:

J2µ2 = (1 - р1)(IΠ1α1H1 + IΠ1α1H2);                                                                 (3.4)

JЛЗ2µ2 = (J´ЛЗ2µ2 + J´2µ2)H2 + λπH1;

JНЗ2µ2 = (IНЗ1α1(1 - р1)Н2+ J´2µ2)H2 + IΠ2α2(1 – р2)H1 + IΠВ2α2(1 – р2)H2+ IНЗ2α2(1 – рНЗНЗ)H2 + IНО2α2(1 – рНОНЗ)HНОБ;

JНЗЛЗ2µ2 = (J´НЗ2µ2 + J´НЗЛЗµ2)H2;

JНО2µ2 = (IНО1α1 (1 - р1)HНОБ;

JНОЛЗ2µ2 = (J´НО2µ2 + J´НОЛЗµ2 + J´Зµ3)HНОБ;

JЗµ3 = I´П3α´3HНО1 + I´ПВ3α´3HБНО + I´НЗ3α´3HБНО + I´НО3α´3HНОНО;

IΠ1α1р1 = IΠ2α2; IΠ2α2р2р3 = I´´Π3α´´3;

IΠ2α2р2(1 – р3) = I´Π3α´3; I´´Π3α´´3 = IΠ4α4;

IΠВ1α1р1 = IΠВ2α2; IΠВ2α2р2р3 = I´´ΠВ3α´´3;

IΠВ2α2р2 (1 - р3) = I´ΠВ3α´3; I´´ΠВ3α´´3 = IΠВ4α4;

IНЗ1α1р1 = IНЗ2α2; IНЗ2α2рНЗНЗрНЗНО = I´´НЗ3α´´3;

IНЗ2α2рНЗНЗ(1 - рНЗНО) = I´НЗ3α´3; I´НЗ3α´3 = IНЗ4α4

IНО1α1р1 = IНО2α2; IНО2α2рНОНЗрНОНО = I´´НО2α´´3;

IНО2α2рНОНЗ(1 - рНОНО)  = IНО3α´3; I´´НО3α´´3 = IНО4α4;

λ(1 - π) = ΙΠ1α1; ((J2 - JЛЗ2) - (J´2 - J´ЛЗ2))µ2 = ΙΠВ1α1;

((JНЗ2 + JНЗЛЗ2) - (J´НЗ2- J´НЗЛЗ2))µ2 = ΙНЗ1α1;

((JНО2µ2 + JНОЛЗ2µ2 + J3µ3) - (J´НО2µ2 + J´НОЛЗ2µ2 + J´3µ3) = ΙНО1α1.

Упрощенная модель, которая будет использоваться при построении оценок вероятностных характеристик исходной модели, имеет вид М/М/v с (Н1*, Н2*; µ2) – настойчивым абонентом. Чтобы свести исходную модель к моедли такого типа, мы, как условились ранее, заменим пуассоновский только поток повторных вызовов, образованный не по причине занятости всех линий пучка, и многоэтапное обслуживание заменим на одноэтапное. Обозначим х интенсивность пуассоновского потока повторных вызовов, а γ(х) – параметр одноэтапного обслуживания. Тогда система уравнений статистического равновесия марковского имеет вид:

(λ + x + jµ2 + iγ(x))P(i,j) = (λ+х) P(j,i + 1)(i + 1) γ(x), i = 0, 1, …,N – 1, i = 0, 1, …,υ – 1;                                                                                                     (3.5)

(λ + x + jµ2 + iγ(x))P(i,j) = (λ+х) P(j,i - 1)(i + 1) (i +1)γ(x), j = N, i = 0, 1, …,υ – 1;

((λ + x)H*1 + jµ2(1 - H*2) + iγ(x))P(i,j) = (λ+х)P(j,i - 1) + P(j + 1, i - 1)(j + 1)µ2 + (λ+х) H*1P(j – 1,i) + P(j + 1, i)(j + 1) µ2 (1 - H*2), j = 0, 1, …,N – 1, i = υ;

(jµ2(1 - H*2) + iγ(x))P(i,j) = (λ+х)P(j,i - 1) + (λ+х) H*1P(j – 1,i), j = N, i = υ.

Здесь Р(j,i) – стационарные вероятности модели (j – число абонентов, повторяющих вызов; i – число занятых линий в пучке); Н1* и Н2* - обощенные значения функции настойчивости (их определение будет дано несколько позднее); N – максимально допустимое число ИПВ. Для Р(j,i) выполнено условие нормировки:

Введем основные вероятностные характеристики модели: вероятность потерь по времени; среднее число занятых линий; среднее число повторяющих вызовы абонентов;

Среднее число повторяющих вызовы абонентов, находящихся в системе в момент занятости всех линий. Вероятностные характеристики упрощенной модели π*, I*, J*, J*´ будут оценками соотвестсвующих характеристик исходной модели. Вероятности Р(j,i), а следовательно, и π*, I*, J*, J*´, являются функциями неизвестного параметра х. Для определения х вновь воспользуемся законами сохранения, превратив их в неявные уравнения относительно х. Для определения вероятностных характеристик π*, I*, J*, J*´ необходимо найти x, γ(x), Н1*, Н2*. Введем обозначения:

x1 = [(1 – p1)(λH1(1 - π*(x)) + (JЛЗµ2 - J´ЛЗµ2) H2)]/[1 – (1 – р1)H2(1 - π*(x))];

x´2 = р1(1 – p2)(λ(1 - π*(x)) H1 + x1(1 - π*(x)Н2 + (JЛЗ - J´ЛЗ)µ2H2) + р1(1 – π*(x)) + (JНОЛЗµ2 - J´НОЛЗ)µ2)HНОБ + (1 – p1pНЗНЗ)*(JНОЛЗµ2 - J´НОЛЗ) µ2Н2;

x´´2 = 1 – (1 - π*(x))(1 – p1pНЗНЗ)Н2 - p1pНЗНЗ HНОБ);

x3 = x´3/x´´3,

x´3 = p1p2(1 – pЗ)((λHНО1 + х2HБНО)(1 - π*(x)) + (JЛЗ - J´ЛЗ)µ2HБНО + p1pНЗНЗ(1 – p1pНЗНО)(х2HБНО)(1 - π*(x)) + (JНЗЛЗ - J´НЗЛЗ) µ2Н2) + (JНОЛЗ - J´НОЛЗ) µ2(p1pНОНЗ(1 - pНОНО)HНОНО + (1 - p1)HНОБ),

x´´3 =  1 – (1 - π*(x))((1 - p1)HНОБ + p1pНОНЗ(1 – p1pНОНО)(HНОНО).

Тогда неизвестная интенсивность х находится из решения неявного уравнения:

х = х1 + х2 + х3.                                                                                              (3.6)

Дадим определение отдельных величин, входящих в выражение (3.6).

1. значения JЛЗ, JНЗЛЗ, JНОЛЗ, J´ЛЗ …определяются соотношениями:

JЛЗ =

JНЗНЗ =

JНОЛЗ =

J´ЛЗ = JЛЗ

J´НЗЛЗ = JНЗЛЗ

J´НОЛЗ = JНОЛЗ

2. обощенные значения настойчивости абонента определяются формулами:

где

3. параметр одноэтапного обслуживания имеет вид:

неявное уравнение (3.6) решается методом последовательных приближений. В качестве начальных значений можно выбирать  . для опеделения каждого промежуточного шага необходимо решить систему (3.5) методом декомпозиции (3.4) с последующим пересчетом параметров по приведенным выше формулам. После нахождения х определяются оценки вероятностных характеритсик исходной модели :

. и  так далее.

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

 

 

 

 

 

 

 

4 МОДЕЛИРОВАНИЕ АЛГОРИТМА МАРШРУТИЗАЦИИ

4.1 Модель сети связи

Рассмотрим модель сети связи с коммутацией сообщений, имеющей M каналов и N узлов. В этой модели предполагается, что M каналов являются абсолютно надежными, а пропускная способность i-го канала равна Ci (бит в секунду). Все N узлов, соответствующих центрам коммутации сообщений (пакетов), предполагаются абсолютно надежными и выполняющими операции по коммутации сообщений, включая, например, декомпоновку сообщений, выбор маршрутов, хранение в буфере, уведомление и тому подобное. Считается, что времена обработки в узлах равны K и являются постоянными (обычно величина K предполагается пренебрежимо малой при реализации алгоритма отыскания потока К считалось равным нулю). Кроме того, в модели имеются очереди к каналам и задержки при передаче. Трафик, поступающий в сеть из внешних источников (например, из хостов) образует пуассоновский процесс со средним значением jk (сообщений в секунду) для тех сообщений, которые возникают в узле j и предназначаются для узла k. Полный внешний трафик, поступающий в сеть (и следовательно, покидающий ее), определим как

(4.1)

Заметим, что величина i имеет вид

(4.2)

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

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

(4.3)

Выше была определена задержка сообщения как полное время, которое сообщение проводит в сети. Наибольший интерес представляет средняя задержка сообщения

T = M [задержка сообщения],которая  будет принята за главную характеристику  сети. Определим среднюю величину Zjk.

Zjk = M [задержка сообщения, которое возникло в j и имеет место назначения k].Эти две средние величины связаны равенством

(4.4)

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