Реферат: Несимметричная многомаркерная кольцевая локальная сеть с буферами 2

--PAGE_BREAK--Время перехода свободного маркера между соседними АС будем считать одинаковым для всех станций и равно d. Скорость движения сообщения по кольцу такая же, как и скорость движения свободного маркера. Время, необходимое для передачи и приема сообщения в кольце, обозначим через a.
Интервал времени между последовательными приходами маркеров на станции равен либо D=d+aпри наличии хотя бы одного сообщения для передачи на АС кольца, либо d, если ни на одной АС нет ни одного сообщения для передачи.
После того, как АС-адресат приняла сообщение, квитанция о приеме передается по кольцу на АС-отправитель этого сообщения. При получении квитанции о приеме АС-отправитель освобождается от переданного сообщения, отправляет маркер на очередную АС.
1.2           Математическая модель функционирования многомаркерной, несимметричной КЛВС с буферами <shape id="_x0000_i1034" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image003.wmz» o:><img width=«140» height=«24» src=«dopb330949.zip» v:shapes="_x0000_i1034">, с 3 АС и 2-мя маркерами, с ординарной дисциплиной обслуживания
Рассмотрим несимметричную КЛВС с протоколом маркерного доступа, которая состоит из 3 абонентских станций, на i-тую АС поступает простейший поток сообщений интенсивности <shape id="_x0000_i1035" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image033.wmz» o:><img width=«80» height=«24» src=«dopb330974.zip» v:shapes="_x0000_i1035">
На первой АС имеется буфер емкостью <shape id="_x0000_i1036" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image035.wmz» o:><img width=«52» height=«23» src=«dopb330975.zip» v:shapes="_x0000_i1036">на второй АС буфер емкостью <shape id="_x0000_i1037" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image037.wmz» o:><img width=«45» height=«23» src=«dopb330976.zip» v:shapes="_x0000_i1037">, на третьей АС буфер <shape id="_x0000_i1038" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image039.wmz» o:><img width=«48» height=«24» src=«dopb330977.zip» v:shapes="_x0000_i1038">, которые служат для отправки сообщений по кольцу, а также есть приемные буфера, которые позволяют принимать любое количество сообщений. АС пронумерованы таким образом, что номер АС увеличивается по направлению движения свободных маркеров, причем после прохождения третьей АС свободный маркер поступает на первую АС. Для передачи сообщений используются 2 маркера.
Буфер на i-той станции назовем полностью свободным, если на АС нет сообщений для передачи и полностью занятым, если на АС имеется <shape id="_x0000_i1039" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image031.wmz» o:><img width=«20» height=«24» src=«dopb330973.zip» v:shapes="_x0000_i1039">сообщений, подлежащих передаче.
Если свободный маркер поступает на свободную АС (не содержащую ни одного сообщения), то он немедленно отправляется на очередную АС. Если маркер поступает на АС, где имеется хотя бы одно сообщение, то немедленно начинается передача имеющихся сообщений в соответствии с дисциплиной обслуживания.
Дисциплина обслуживания – ординарная, т.е. при поступлении маркера на АС обслуживается не более одного сообщения, стоящего в очереди в момент прихода маркера.
Будем считать, что во время передачи сообщения все поступающие на эту АС сообщения, подлежащие передаче, теряются. Т.е. в этом случае на АС, с которой передаются сообщения, происходит блокировка буфера, в котором находились сообщения в момент прихода маркера. Время блокировки равно времени передачи сообщения, находившихся на АС-отправителе в момент прихода маркера.
Время перехода свободного маркера между соседними АС будем считать одинаковым для всех станций и равно d. Скорость движения сообщения по кольцу такая же, как и скорость движения свободного маркера. Время, необходимое для передачи и приема сообщения в кольце, обозначим через a.
Интервал времени между последовательными приходами маркеров на станции равен либо D=d+aпри наличии хотя бы одного сообщения для передачи на АС кольца, либо d, если ни на одной АС нет ни одного сообщения для передачи.
После того, как АС-адресат приняла сообщение, квитанция о приеме передается по кольцу на АС-отправитель этого сообщения. При получении квитанции о приеме АС-отправитель освобождается от переданного сообщения, отправляет маркер на очередную АС.
1.3           Математическая модель функционирования многомаркерной, несимметричной КЛВС с NАС, с kмаркерами (k=N) и буферами различной емкости <shape id="_x0000_i1040" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image001.wmz» o:><img width=«119» height=«24» src=«dopb330948.zip» v:shapes="_x0000_i1040">
Рассмотрим несимметричную КЛВС с протоколом маркерного доступа, которая состоит из N абонентских станций, на i-тую АС поступает простейший поток сообщений интенсивности <shape id="_x0000_i1041" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image027.wmz» o:><img width=«85» height=«24» src=«dopb330971.zip» v:shapes="_x0000_i1041">
На каждой АС имеется буфер с емкостью <shape id="_x0000_i1042" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image029.wmz» o:><img width=«113» height=«24» src=«dopb330972.zip» v:shapes="_x0000_i1042">, который служит для отправки сообщений по кольцу, а также есть приемный буфер, который позволяет принимать любое количество сообщений. АС пронумерованы таким образом, что номер АС увеличивается по направлению движения свободных маркеров, причем после прохождения N-ой АС свободный маркер поступает на первую АС. Для передачи сообщений используются k маркеров, k=N.
Буфер на i-той станции назовем полностью свободным, если на АС нет сообщений для передачи и полностью занятым, если на АС имеется <shape id="_x0000_i1043" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image031.wmz» o:><img width=«20» height=«24» src=«dopb330973.zip» v:shapes="_x0000_i1043">сообщений, подлежащих передаче.
Если свободный маркер поступает на свободную АС (не содержащую ни одного сообщения), то он немедленно отправляется на очередную АС. Если маркер поступает на АС, где имеется хотя бы одно сообщение, то немедленно начинается передача имеющихся сообщений в соответствии с дисциплиной обслуживания.
Дисциплина обслуживания – ординарная, т.е. при поступлении маркера на АС обслуживается не более одного сообщения, стоящего в очереди в момент прихода маркера.
Будем считать, что во время передачи сообщения все поступающие на эту АС сообщения, подлежащие передаче, теряются. Т.е. в этом случае на АС, с которой передаются сообщения, происходит блокировка буфера, в котором находились сообщения в момент прихода маркера. Время блокировки равно времени передачи сообщения, находившихся на АС-отправителе в момент прихода маркера.
Время перехода свободного маркера между соседними АС будем считать одинаковым для всех станций и равно d. Скорость движения сообщения по кольцу такая же, как и скорость движения свободного маркера. Время, необходимое для передачи и приема сообщения в кольце, обозначим через a.
Интервал времени между последовательными приходами маркеров на станции равен либо D=d+aпри наличии хотя бы одного сообщения для передачи на АС кольца, либо d, если ни на одной АС нет ни одного сообщения для передачи.
После того, как АС-адресат приняла сообщение, квитанция о приеме передается по кольцу на АС-отправитель этого сообщения. При получении квитанции о приеме АС-отправитель освобождается от переданного сообщения, отправляет маркер на очередную АС.
Данная модель интересна тем, что любая станция может передавать сообщение (если оно имеется). Это объясняется тем, что количество маркеров совпадает с количеством станций. Это модель имеет также особенности и в виде матрицы переходов из одного периодического класса в другой.

2. Определение стационарных вероятностей состояний несимметричных, многомаркерных КЛВС
2.1 Определение стационарных вероятностей состояний многомаркерной, несимметричной КЛВС с буферами различной емкости, с NАС и kмаркерами, с ординарной дисциплиной обслуживания
Будем рассматривать поведение КЛВС в моменты поступления маркеров на АС. В этом случае изменение состояний КЛВС образуют конечную цепь Маркова.
Под состоянием КЛВС будем понимать состояние всех АС кольца в момент поступления на них маркеров. Каждая АС может находиться всегда в одном из <shape id="_x0000_i1044" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image041.wmz» o:><img width=«43» height=«24» src=«dopb330978.zip» v:shapes="_x0000_i1044"><shape id="_x0000_i1045" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image043.wmz» o:><img width=«12» height=«23» src=«dopb330979.zip» v:shapes="_x0000_i1045">состоянии.
Все состояния КЛВС делятся на N периодических классов, каждый из которых содержит в рассматриваемом случае <shape id="_x0000_i1046" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image045.wmz» o:><img width=«75» height=«45» src=«dopb330980.zip» v:shapes="_x0000_i1046">состояние.         
Особенности протокола приводят к тому, что указанная цепь Маркова является неприводимой, периодической с периодом, равным N.
Некоторый j-тый класс (j<shape id="_x0000_i1047" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image047.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1047">{1,2,…, N}) соответствует поступлению некоторого фиксированного маркера на j-тую АС. Вероятности переходов из j-того периодического класса в (j+1) – ый образуют (<shape id="_x0000_i1048" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image045.wmz» o:><img width=«75» height=«45» src=«dopb330980.zip» v:shapes="_x0000_i1048"><shape id="_x0000_i1049" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image049.wmz» o:><img width=«15» height=«13» src=«dopb330982.zip» v:shapes="_x0000_i1049"><shape id="_x0000_i1050" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image045.wmz» o:><img width=«75» height=«45» src=«dopb330980.zip» v:shapes="_x0000_i1050">) матрицу.
Закодируем состояния КЛВС парами чисел (i, r), i=(<shape id="_x0000_i1051" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image051.wmz» o:><img width=«57» height=«25» src=«dopb330983.zip» v:shapes="_x0000_i1051">), 0<shape id="_x0000_i1052" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image053.wmz» o:><img width=«37» height=«16» src=«dopb330984.zip» v:shapes="_x0000_i1052"><shape id="_x0000_i1053" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image055.wmz» o:><img width=«108» height=«48» src=«dopb330985.zip» v:shapes="_x0000_i1053">.Здесь i определяет класс состояний, т.е. равно номерам тех станций, на которых находятся маркеры, r определяет номер состояния.
Введем обозначение M=(<shape id="_x0000_i1054" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image057.wmz» o:><img width=«57» height=«25» src=«dopb330983.zip» v:shapes="_x0000_i1054">) – множество номеров тех станций, на которых находятся маркера, R=(<shape id="_x0000_i1055" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image058.wmz» o:><img width=«49» height=«24» src=«dopb330986.zip» v:shapes="_x0000_i1055">), <shape id="_x0000_i1056" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image060.wmz» o:><img width=«89» height=«24» src=«dopb330987.zip» v:shapes="_x0000_i1056">, l<shape id="_x0000_i1057" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image062.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1057">{1,…, N}, <shape id="_x0000_i1058" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image063.wmz» o:><img width=«12» height=«24» src=«dopb330988.zip» v:shapes="_x0000_i1058"> — обозначает количество сообщений на l-той АС. Также обозначим через P(<shape id="_x0000_i1059" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image057.wmz» o:><img width=«57» height=«25» src=«dopb330983.zip» v:shapes="_x0000_i1059">) – вектор-строку вероятностей состояний КЛВС.
Обозначим через <shape id="_x0000_i1060" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image065.wmz» o:><img width=«43» height=«25» src=«dopb330989.zip» v:shapes="_x0000_i1060"> — вероятность того, что за время <shape id="_x0000_i1061" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image067.wmz» o:><img width=«13» height=«24» src=«dopb330990.zip» v:shapes="_x0000_i1061"> на i-тую АС не поступит ни одного сообщения; <shape id="_x0000_i1062" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image069.wmz» o:><img width=«44» height=«25» src=«dopb330991.zip» v:shapes="_x0000_i1062"> — вероятность того, что за время <shape id="_x0000_i1063" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image067.wmz» o:><img width=«13» height=«24» src=«dopb330990.zip» v:shapes="_x0000_i1063">на i-тую АС поступит m сообщений; <shape id="_x0000_i1064" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image071.wmz» o:><img width=«44» height=«28» src=«dopb330992.zip» v:shapes="_x0000_i1064"> — вероятность того, что за время <shape id="_x0000_i1065" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image067.wmz» o:><img width=«13» height=«24» src=«dopb330990.zip» v:shapes="_x0000_i1065"> на i-тую АС поступит m и более сообщений.
Так как поток сообщений пуассоновский, то имеем:
<shape id="_x0000_i1066" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image065.wmz» o:><img width=«43» height=«25» src=«dopb330989.zip» v:shapes="_x0000_i1066">=<shape id="_x0000_i1067" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image073.wmz» o:><img width=«32» height=«21» src=«dopb330993.zip» v:shapes="_x0000_i1067">
<shape id="_x0000_i1068" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image069.wmz» o:><img width=«44» height=«25» src=«dopb330991.zip» v:shapes="_x0000_i1068">=<shape id="_x0000_i1069" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image075.wmz» o:><img width=«77» height=«45» src=«dopb330994.zip» v:shapes="_x0000_i1069">
<shape id="_x0000_i1070" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image077.wmz» o:><img width=«144» height=«49» src=«dopb330995.zip» v:shapes="_x0000_i1070">, i<shape id="_x0000_i1071" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image079.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1071">{1,2,…, N}
Изучая поведение КЛВС во вложенные Марковские моменты, получим следующую процедуру определения стационарных вероятностей сети.
Теорема. Стационарные вероятности рассматриваемой КЛВС вычисляются из соотношений:
P(<shape id="_x0000_i1072" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image080.wmz» o:><img width=«80» height=«25» src=«dopb330996.zip» v:shapes="_x0000_i1072">)=P(<shape id="_x0000_i1073" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image082.wmz» o:><img width=«145» height=«25» src=«dopb330997.zip» v:shapes="_x0000_i1073">) A(<shape id="_x0000_i1074" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image084.wmz» o:><img width=«145» height=«25» src=«dopb330997.zip» v:shapes="_x0000_i1074">;<shape id="_x0000_i1075" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image080.wmz» o:><img width=«80» height=«25» src=«dopb330996.zip» v:shapes="_x0000_i1075">)   
<shape id="_x0000_i1076" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image085.wmz» o:><img width=«200» height=«45» src=«dopb330998.zip» v:shapes="_x0000_i1076">        (1)
где А -<shape id="_x0000_i1077" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image087.wmz» o:><img width=«171» height=«48» src=«dopb330999.zip» v:shapes="_x0000_i1077"> матрица вероятностей переходов из i-того периодического класса в состояние (i+1) – го класса, элементы которой вычисляются по формуле:

a(<shape id="_x0000_i1078" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image080.wmz» o:><img width=«80» height=«25» src=«dopb330996.zip» v:shapes="_x0000_i1078">)=<shape id="_x0000_i1079" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image089.wmz» o:><img width=«244» height=«48» src=«dopb331000.zip» v:shapes="_x0000_i1079"><shape id="_x0000_i1080" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image091.wmz» o:><img width=«397» height=«28» src=«dopb331001.zip» v:shapes="_x0000_i1080">+<shape id="_x0000_i1081" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image093.wmz» o:><img width=«47» height=«29» src=«dopb331002.zip» v:shapes="_x0000_i1081"><shape id="_x0000_i1082" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image095.wmz» o:><img width=«161» height=«31» src=«dopb331003.zip» v:shapes="_x0000_i1082"><shape id="_x0000_i1083" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image097.wmz» o:><img width=«113» height=«25» src=«dopb331004.zip» v:shapes="_x0000_i1083">+<shape id="_x0000_i1084" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image099.wmz» o:><img width=«189» height=«25» src=«dopb331005.zip» v:shapes="_x0000_i1084">, времена вычисляются по следующим формулам:
<shape id="_x0000_i1085" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image101.wmz» o:><img width=«236» height=«25» src=«dopb331006.zip» v:shapes="_x0000_i1085"> <shape id="_x0000_i1086" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image103.wmz» o:><img width=«53» height=«21» src=«dopb331007.zip» v:shapes="_x0000_i1086">
<shape id="_x0000_i1087" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image105.wmz» o:><img width=«167» height=«25» src=«dopb331008.zip» v:shapes="_x0000_i1087"> <shape id="_x0000_i1088" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image107.wmz» o:><img width=«63» height=«21» src=«dopb331009.zip» v:shapes="_x0000_i1088"><shape id="_x0000_i1089" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image109.wmz» o:><img width=«76» height=«21» src=«dopb331010.zip» v:shapes="_x0000_i1089">
а также вероятность перехода равна нулю, если:
1) <shape id="_x0000_i1090" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image111.wmz» o:><img width=«39» height=«24» src=«dopb331011.zip» v:shapes="_x0000_i1090">>0 <shape id="_x0000_i1091" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image113.wmz» o:><img width=«76» height=«21» src=«dopb331012.zip» v:shapes="_x0000_i1091">, Q={1,2,3,…, N}
2) <shape id="_x0000_i1092" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image115.wmz» o:><img width=«64» height=«24» src=«dopb331013.zip» v:shapes="_x0000_i1092"> <shape id="_x0000_i1093" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image117.wmz» o:><img width=«53» height=«19» src=«dopb331014.zip» v:shapes="_x0000_i1093">
Доказательство:
P(<shape id="_x0000_i1094" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image119.wmz» o:><img width=«56» height=«25» src=«dopb331015.zip» v:shapes="_x0000_i1094">) – вектор-строка вероятностей состояний i-того периодического класса; матрица А размерности <shape id="_x0000_i1095" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image087.wmz» o:><img width=«171» height=«48» src=«dopb330999.zip» v:shapes="_x0000_i1095">, элементами которой являются вероятности переходов из i-того периодического класса в (i+1) – ый.
Вследствие периодичности цепи Маркова <shape id="_x0000_i1096" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image121.wmz» o:><img width=«52» height=«25» src=«dopb331016.zip» v:shapes="_x0000_i1096"> если <shape id="_x0000_i1097" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image123.wmz» o:><img width=«55» height=«21» src=«dopb331017.zip» v:shapes="_x0000_i1097"> либо (i, j)<shape id="_x0000_i1098" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image125.wmz» o:><img width=«15» height=«15» src=«dopb331018.zip» v:shapes="_x0000_i1098">(N, 1). Из этих рассуждений имеем Р(1)=Р(N)<shape id="_x0000_i1099" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image127.wmz» o:><img width=«36» height=«25» src=«dopb331019.zip» v:shapes="_x0000_i1099">
Р(J)=P (J-1)<shape id="_x0000_i1100" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image129.wmz» o:><img width=«51» height=«25» src=«dopb331020.zip» v:shapes="_x0000_i1100"> J<shape id="_x0000_i1101" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image131.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1101">{2,3,…, N}, J определяет периодический класс.
J определяет те, станции на которых находятся маркеры в данном периодическом классе, с учетом постановки математической модели любой маркер может переходить только на соседнюю станцию. Это и обуславливает то, что маркер с N-ной станции переходит на первую АС.
Таким образом, учитывая условие нормировки, имеем процедуру (1) определения векторов стационарных вероятностей КЛВС.
Доказано.
Для обоснования правильности формул времени необходимо учитывать следующие положения:
1)                если поступает сообщение, а соответствующий буфер занят полностью, то сообщение теряется, и при подсчете поступивших сообщений оно не учитывается;
2)                если сообщение не передается, то из данного буфера оно никуда не может исчезнуть, поэтому если при переходе из некоторого состояния в соседнее какое-то сообщение теряется, то вероятность данного перехода равна 0;
3)                при передаче сообщения из АС, на которой есть маркер, буфер данной станции блокируется;
4)                со станции с маркером может передаваться не более одного сообщения.
5)                на тех станциях, на которых нет маркеров, может быть вероятность равна единице в том случае, если в i-том периодическом классе и в (i+1) – вом буфер станции был полностью занят.
2.2<shape id="_x0000_i1102" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image043.wmz» o:><img width=«12» height=«23» src=«dopb330979.zip» v:shapes="_x0000_i1102"> Определение стационарных вероятностей состояний многомаркерной, несимметричной КЛВС с буферами <shape id="_x0000_i1103" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image003.wmz» o:><img width=«140» height=«24» src=«dopb330949.zip» v:shapes="_x0000_i1103">, с 3 АС и 2-мя маркерами, с ординарной дисциплиной обслуживания
Будем рассматривать поведение КЛВС в моменты поступления маркеров на АС. В этом случае изменение состояний КЛВС образуют конечную цепь Маркова.
Под состоянием КЛВС будем понимать состояние всех АС кольца в момент поступления на них маркеров. Каждая АС может находиться всегда в одном из <shape id="_x0000_i1104" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image132.wmz» o:><img width=«43» height=«24» src=«dopb330978.zip» v:shapes="_x0000_i1104">состоянии.
Все состояния КЛВС делятся на 3 периодических классов, каждый из которых содержит в рассматриваемом случае 12 состояний.
Особенности протокола приводят к тому, что указанная цепь Маркова является неприводимой, периодической с периодом, равным 3.
Некоторый j-тый класс (j<shape id="_x0000_i1105" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image047.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1105">{1,2,3}) соответствует поступлению некоторого фиксированного маркера на j-тую АС. Вероятности переходов из j-того периодического класса в (j+1) – ый образуют <shape id="_x0000_i1106" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image133.wmz» o:><img width=«56» height=«23» src=«dopb331021.zip» v:shapes="_x0000_i1106"> матрицу.
Закодируем состояния КЛВС парами чисел (i, r), i=(<shape id="_x0000_i1107" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image135.wmz» o:><img width=«40» height=«24» src=«dopb331022.zip» v:shapes="_x0000_i1107">), 0<shape id="_x0000_i1108" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image053.wmz» o:><img width=«37» height=«16» src=«dopb330984.zip» v:shapes="_x0000_i1108">11. Здесь i определяет класс состояний, т.е. равно номерам тех станций, на которых находятся маркера, r определяет номер состояния.
Введем обозначение M=(<shape id="_x0000_i1109" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image135.wmz» o:><img width=«40» height=«24» src=«dopb331022.zip» v:shapes="_x0000_i1109">) – множество номеров тех станций, на которых находятся маркера, R=(<shape id="_x0000_i1110" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image137.wmz» o:><img width=«45» height=«24» src=«dopb331023.zip» v:shapes="_x0000_i1110">), <shape id="_x0000_i1111" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image060.wmz» o:><img width=«89» height=«24» src=«dopb330987.zip» v:shapes="_x0000_i1111">, l<shape id="_x0000_i1112" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image062.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1112">{1,2,3}, <shape id="_x0000_i1113" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image063.wmz» o:><img width=«12» height=«24» src=«dopb330988.zip» v:shapes="_x0000_i1113"> — обозначает количество сообщений на l-той АС. Также обозначим через P(<shape id="_x0000_i1114" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image135.wmz» o:><img width=«40» height=«24» src=«dopb331022.zip» v:shapes="_x0000_i1114">) – вектор-строку вероятностей состояний КЛВС.
Обозначим через <shape id="_x0000_i1115" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image065.wmz» o:><img width=«43» height=«25» src=«dopb330989.zip» v:shapes="_x0000_i1115"> — вероятность того, что за время <shape id="_x0000_i1116" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image067.wmz» o:><img width=«13» height=«24» src=«dopb330990.zip» v:shapes="_x0000_i1116"> на i-тую АС не поступит ни одного сообщения; <shape id="_x0000_i1117" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image069.wmz» o:><img width=«44» height=«25» src=«dopb330991.zip» v:shapes="_x0000_i1117"> — вероятность того, что за время <shape id="_x0000_i1118" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image067.wmz» o:><img width=«13» height=«24» src=«dopb330990.zip» v:shapes="_x0000_i1118">на i-тую АС поступит m сообщений; <shape id="_x0000_i1119" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image071.wmz» o:><img width=«44» height=«28» src=«dopb330992.zip» v:shapes="_x0000_i1119"> — вероятность того, что за время <shape id="_x0000_i1120" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image067.wmz» o:><img width=«13» height=«24» src=«dopb330990.zip» v:shapes="_x0000_i1120"> на i-тую АС поступит m и более сообщений.
Так как поток сообщений пуассоновский, то имеем:
<shape id="_x0000_i1121" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image065.wmz» o:><img width=«43» height=«25» src=«dopb330989.zip» v:shapes="_x0000_i1121">=<shape id="_x0000_i1122" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image073.wmz» o:><img width=«32» height=«21» src=«dopb330993.zip» v:shapes="_x0000_i1122">
<shape id="_x0000_i1123" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image069.wmz» o:><img width=«44» height=«25» src=«dopb330991.zip» v:shapes="_x0000_i1123">=<shape id="_x0000_i1124" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image075.wmz» o:><img width=«77» height=«45» src=«dopb330994.zip» v:shapes="_x0000_i1124">
<shape id="_x0000_i1125" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image077.wmz» o:><img width=«144» height=«49» src=«dopb330995.zip» v:shapes="_x0000_i1125">, i<shape id="_x0000_i1126" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image079.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1126">{1,2,3}
Изучая поведение КЛВС во вложенные Марковские моменты, получим следующую процедуру определения стационарных вероятностей сети, которая является частным случаем теоремы из пункта 2.1: стационарные вероятности рассматриваемой КЛВС вычисляются из соотношений:

P (2,3)=P (1,2) A (1,2);
P (3,1)=P (2,3) A (2,3);
P (1,2)=P (3,1) A (3,1);
<shape id="_x0000_i1127" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image139.wmz» o:><img width=«103» height=«45» src=«dopb331024.zip» v:shapes="_x0000_i1127">
А –<shape id="_x0000_i1128" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image141.wmz» o:><img width=«56» height=«23» src=«dopb331021.zip» v:shapes="_x0000_i1128"> матрица вероятностей переходов из i-того периодического класса в состояние (i+1) – го класса, элементы которой вычисляются по формуле:
a(<shape id="_x0000_i1129" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image135.wmz» o:><img width=«40» height=«24» src=«dopb331022.zip» v:shapes="_x0000_i1129">)=<shape id="_x0000_i1130" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image142.wmz» o:><img width=«603» height=«48» src=«dopb331025.zip» v:shapes="_x0000_i1130">
<shape id="_x0000_i1131" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image144.wmz» o:><img width=«672» height=«27» src=«dopb331026.zip» v:shapes="_x0000_i1131"><shape id="_x0000_i1132" type="#_x0000_t75" o:ole=""><imagedata src=«101780.files/image146.wmz» o:><img width=«345» height=«27» src=«dopb331027.zip» v:shapes="_x0000_i1132">
времена вычисляются по следующим формулам:
<shape id="_x0000_i1133" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image101.wmz» o:><img width=«236» height=«25» src=«dopb331006.zip» v:shapes="_x0000_i1133"><shape id="_x0000_i1134" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image103.wmz» o:><img width=«53» height=«21» src=«dopb331007.zip» v:shapes="_x0000_i1134">
<shape id="_x0000_i1135" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image105.wmz» o:><img width=«167» height=«25» src=«dopb331008.zip» v:shapes="_x0000_i1135"><shape id="_x0000_i1136" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image107.wmz» o:><img width=«63» height=«21» src=«dopb331009.zip» v:shapes="_x0000_i1136"><shape id="_x0000_i1137" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image109.wmz» o:><img width=«76» height=«21» src=«dopb331010.zip» v:shapes="_x0000_i1137">
а также вероятность перехода равна нулю, если:
1) <shape id="_x0000_i1138" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image111.wmz» o:><img width=«39» height=«24» src=«dopb331011.zip» v:shapes="_x0000_i1138">>0 <shape id="_x0000_i1139" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image113.wmz» o:><img width=«76» height=«21» src=«dopb331012.zip» v:shapes="_x0000_i1139">, Q={1,2,3}
2) <shape id="_x0000_i1140" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image148.wmz» o:><img width=«67» height=«24» src=«dopb331028.zip» v:shapes="_x0000_i1140">
Для обоснования правильности формул времени необходимо учитывать следующие положения:
1)                если поступает сообщение, а соответствующий буфер занят полностью, то сообщение теряется, и при подсчете поступивших сообщений оно не учитывается;
2)                если сообщение не передается, то из данного буфера оно никуда не может исчезнуть, поэтому если при переходе из некоторого состояния в соседнее какое-то сообщение теряется, то вероятность данного перехода равна 0;
3)                при передаче сообщения из АС, на которой есть маркер, буфер данной станции блокируется;
4)                со станции с маркером может передаваться не более одного сообщения;
5)                на тех станциях, на которых нет маркеров, может быть вероятность равна единице в том случае, если в i-том периодическом классе и в (i+1) – вом буфер станции был полностью занят.
В приложении будет предоставлены матрицы переходов для рассматриваемой КЛВС. Обозначение <shape id="_x0000_i1141" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image150.wmz» o:><img width=«44» height=«21» src=«dopb331029.zip» v:shapes="_x0000_i1141"> означает, что маркеры находились на первой и второй станциях.
2.3 Определение стационарных вероятностей состояний многомаркерной, несимметричной КЛВС с буферами различной емкости, с NАС и k=Nмаркерами, с ординарной дисциплиной обслуживания
Будем рассматривать поведение КЛВС в моменты поступления маркеров на АС. В этом случае изменение состояний КЛВС образуют конечную цепь Маркова.
Под состоянием КЛВС будем понимать состояние всех АС кольца в момент поступления на них маркеров. Каждая АС может находиться всегда в одном из <shape id="_x0000_i1142" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image041.wmz» o:><img width=«43» height=«24» src=«dopb330978.zip» v:shapes="_x0000_i1142"><shape id="_x0000_i1143" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image043.wmz» o:><img width=«12» height=«23» src=«dopb330979.zip» v:shapes="_x0000_i1143">состоянии.
Все состояния КЛВС делятся на N периодических классов, каждый из которых содержит в рассматриваемом случае <shape id="_x0000_i1144" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image045.wmz» o:><img width=«75» height=«45» src=«dopb330980.zip» v:shapes="_x0000_i1144">состояние.         
Особенности протокола приводят к тому, что указанная цепь Маркова является неприводимой, периодической с периодом, равным N.
Некоторый j-тый класс (j<shape id="_x0000_i1145" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image047.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1145">{1,2,…, N}) соответствует поступлению некоторого фиксированного маркера на j-тую АС. Вероятности переходов из j-того периодического класса в (j+1) – ый образуют (<shape id="_x0000_i1146" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image045.wmz» o:><img width=«75» height=«45» src=«dopb330980.zip» v:shapes="_x0000_i1146"><shape id="_x0000_i1147" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image049.wmz» o:><img width=«15» height=«13» src=«dopb330982.zip» v:shapes="_x0000_i1147"><shape id="_x0000_i1148" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image045.wmz» o:><img width=«75» height=«45» src=«dopb330980.zip» v:shapes="_x0000_i1148">) матрицу. Зафиксируем некоторый маркер и будем рассматривать поведение сети в моменты поступления этого маркера АС.
Закодируем состояния КЛВС парами чисел (i, r), i=(<shape id="_x0000_i1149" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image051.wmz» o:><img width=«57» height=«25» src=«dopb330983.zip» v:shapes="_x0000_i1149">), 0<shape id="_x0000_i1150" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image053.wmz» o:><img width=«37» height=«16» src=«dopb330984.zip» v:shapes="_x0000_i1150"><shape id="_x0000_i1151" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image055.wmz» o:><img width=«108» height=«48» src=«dopb330985.zip» v:shapes="_x0000_i1151">.Здесь i определяет класс состояний, т.е. равно номеру станции, на которой находятся маркеры, r определяет номер состояния.
Введем обозначение M=(<shape id="_x0000_i1152" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image057.wmz» o:><img width=«57» height=«25» src=«dopb330983.zip» v:shapes="_x0000_i1152">) – множество номеров тех станций, на которых находятся маркера, R=(<shape id="_x0000_i1153" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image058.wmz» o:><img width=«49» height=«24» src=«dopb330986.zip» v:shapes="_x0000_i1153">), <shape id="_x0000_i1154" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image060.wmz» o:><img width=«89» height=«24» src=«dopb330987.zip» v:shapes="_x0000_i1154">, l<shape id="_x0000_i1155" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image062.wmz» o:><img width=«13» height=«13» src=«dopb330981.zip» v:shapes="_x0000_i1155">{1,…, N}, <shape id="_x0000_i1156" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image063.wmz» o:><img width=«12» height=«24» src=«dopb330988.zip» v:shapes="_x0000_i1156"> — обозначает количество сообщений на l-той АС. Также обозначим через P(<shape id="_x0000_i1157" type="#_x0000_t75" o:ole="" fillcolor=«window»><imagedata src=«101780.files/image152.wmz» o:><img width=«59» height=«24» src=«dopb331030.zip» v:shapes="_x0000_i1157">) – вектор-строку вероятностей состояний КЛВС.
    продолжение
--PAGE_BREAK--