СЕТИ С ОЧЕРЕДЯМИ НА БЕСКОНЕЧНОЙ ОДНОМЕРНОЙ РЕШЕТКЕ С ПРОТОКОЛАМИ ГИБРИДНОЙ КОММУТАЦИИ

Р.Н.Шамсиев (Ташкентский Государственный Технический Университет имени Беруний,Ташкент,Узбекистан)

Ж.С.Еркишева (Международный казахско-турецкий университет имени А.Ясави, Туркестан, Казахстан)

1. В работе исследуются один класс гибридных сетей на одномерной решетке Z1 со связями ближайшими соседями.

Предположим, что задано семейство независимых одинаково распределенных (н.о.р.) маркированных пуассоновских процессов {xj , jÎZ1} интенсивности а с н.о.р. марками .Скачок процесса xj отвечает «возникновению» внешнего сообщения (в.с.) y=[t;(d,l,z)] в узле j, где t есть момент возникновения сообщения, d=0,1 – индекс сообщения, l – его длина, а z задает допустимое время блокировки (см. ниже): z=0 если d=0. Пусть F – распределение длины l, К распределение величины z (при условии, что d=1). Пусть q=Pr(d=1). Мы предполагаем, что F(b0, b1)=1 при некоторых 0 < b0 £ b1 < ¥ и Ekeaz < ¥ при некотором a > 0.

Каждое в.с. y=[t;(d,l,z)], возникшее в узле jÎZ1, должно быть передано либо в узел j+1 (если d=0), либо в j+2 (если d=1), после чего покидает сеть. В момент t оно начинает «претендовать» на линию ( j®j+1 ). Если d=0, то сообщение в узле j до тех пор, пока все в.с., возникшее в узлах j и j-1, которые начали «претендовать» на линию ( j®j+1 ) раньше него, не завершат передачу по этой линии. После этого оно передается по линии ( j®j+1 ) в течении времени l. Если d=1, то после первой стадии ожидания сообщение у начинает «претендовать» на линию ( j+1®j+2 ), блокируя при этом линию ( j®j+1 ). Если по истечении времени z сообщение у не получило в свое распоряжение линию ( j+1®j+2 ), оно начинает передаваться в узел j+1, где и ожидает остаток времени до освобождения линии ( j+1®j+2). Тем самым проводиться «деблокировка» линии ( j®j+1 ).

2. При математической формулировке задачи вводятся времена ожидания W1(y) и W2(y) на первой и второй стадиях, которые связаны системой рекуррентных уравнений (аналогичных хорошо известному уравнению очереди FCGS) для разных сообщений. Задача состоит в том, что чтобы построить семейство маркированных точечных случайных процессов (м.т.с.п.) hj, jÎZ1, с марками (d, l, z, W1, W2), которые дают решение этой системы уравнений. Можно говорить, что искомые м.т.с.п. hj должны задавать «оснащение» пуассоновских процессов xj, согласованное с описанным выше правилом передачи. При этом, как обычно, вводятся понятия сильного и слабого решения (оснащения).

Основным результатом работы является следующая:

Теорема. Пусть a(2EFl + EKz) < 1 и q достаточно мало: qÎ(0, q0), где q0Î(0,1). Тогда существует семейство м.т.с.п. {hj, jÎZ1}, дающее сильное решение системы уравнений. Это семейство единственно (в некотором классе) и обладает свойством пространственно-временного перемешивания (убывания корреляций).

На первом этапе построения семейства м.т.с.п. {hj, jÎZ1} рассматривается конечная сеть с узлами  «отделенная» от узлов   которая начинает работу в момент времени t0, исходя из «нулевого» начального состояния. Формально говоря, рассматривается «урезанное» семейство внешних потоков  где - сужение потока xj на [t0, ¥) при  и  при  а также прежнее правило передачи.

Лемма 1. Пусть семейство внешних потоков {xj , jÎZ1} и правило передачи удовлетворяют условиям, сформулированным выше, без ограничений на малость q. Тогда при всех N³1 и t0 ÎR1

(а) существует единственное семейство потоков  с марками изудовлетворяющее системы уравнений.

(б) Это семейство является сильным оснащением семейства потоков .

Доказательство леммы 1 проводится с помощью «непосредственного» построения. Мы «запускаем» сеть в момент t0, последовательно «присваивая» сообщениям соответствующие значения компонент марки W1(y), W2(y). На втором этапе доказывается, что для достаточно малого q семейство м.т.с.п.  сходится при t0®-¥, N®¥ к предельному семейству {hj, jÎZ1}. Предельное м.т.с.п. hj, jÎZ1 будут представлять собой сильное оснащение пуассоновских м.т.с.п. xj , jÎZ1 и дают решение системы уравнений. Подчеркнем, что оценка для q не будет зависеть от t0 и N.

 

 

3. Важную роль в ходе доказательстве теоремы играет семейство н.о.р. м.т.с.п. {xj , jÎZ1}, которое будет в естественном смысле мажорировать допредельные семейства  N³1, t0ÎR1, равно как и предельное семейство {hj, jÎZ1}. Возможность построения такой мажоранты, независящей от N и t0, означает, что аппроксимирующие м.т.с.п. , а следовательно, и предельные м.т.с.п.hj, jÎZ1, не могут «уйти в бесконечность». Более того, через мажорирующие м.т.с.п. можно оценить «степень распространения влияния» в семействах м.т.с.п..

В силу независимости для задания совместного распределения семейства {xj , jÎZ1} нам достаточно построить распределение отдельного мажорирующего м.т.с.п., который мы условимся обозначать через z. Это процесс с марками из , представляет собой суперпозицию двух независимых м.т.с.п.

                                                                            (1)

Здесь g - бернуллиевский м.т.с.п. с параметрами   пуассоновский процесс интенсивности а с н.о.р. марками из  и индивидуальным распределением марки G = F(2) * K, где F(2) –распределение удвоенной длины сообщения.

         Лемма 2. (а) При достаточно малом значении q м.т.с.п. z допускает единственное оснащение, согласованное с уравнением очереди FCGS. При этом для любого набора непересекающихся интервалов I1, I2, …,Im интервалов и любого набора точек   условная вероятность

    (2)

Здесь – событие, состоящее в том, что в потоке z интервал Is содержится в одном из периодов занятости, роль условия играет событие, что в моменты уs , s=1,…,n, в потоке g «появились» сообщения (длины в0 + в1 ), а С0, С1 > 0 – фиксированные константы.

         (б) При любых  и  м.т.с.п.   и  можно определить на одном вероятностном пространстве (W,D,P) так, что с Р вероятностью 1 при всех и  будет выполнено неравенство

Здесь -м.т.с.п., порождающий очередь на линии ( j®j+1) в конечной сети с узлами , {Wt(∙)}- процесс виртуального ожидания.

         4. С помощью несущественных изменений метода можно изучить еще ряд моделей коммутационных сетей [1]. Для краткости мы упомянем здесь одну из них: модель коммутации каналов с приоритетом транзитных сообщений. В этой модели сообщение у с d(y)=1, возникшее в узле j, по закреплении первой линии своего маршрута, т.е. в момент t'(y)=t(y)+W1(y), когда оно начинает претендовать на линию  (j+1®j+2), получает приоритет перед сообщениями, возникшими в узле j+1 (независимо от значений их индексов).Для этой модели справедливо утверждение теоремы 1.

         В качестве мажорирующих потоков в данной модели выступают н.о.р. м.т.с.п.

 ,

где  -бернуллиевский м.т.с.п. с параметрами  ,- пуассоновский процесс интенсивности а с н.о.р. марками из  и индивидуальным распределением марки G=F*F.

 

Литература

1. Сети с очередями на бесконечных графах с приоритетной коммутацией. Материалы международной научно-практической конференции, посвященной 50-летию самолетостроительного факультета ТГАИ. Ташкент. 2006, С.126-128.