Alfraganus
xalqaro ilmiy jurnal
40
УДК 519.21.
ЗВЕЗДООБРАЗНЫЕ СЕТИ С ОЧЕРЕДЯМИ
С ПРОТОКОЛОМ КОММУТАЦИИ КАНАЛОВ
Шамсиев Рахим Нажмиддинович,
доцент кафедры “Математики и физики”
ALFRAGANUS UNIVERSITY
ORCID: 0009-0004-5697-4063
Аннотация:
Данное исследование посвящено анализу звездообразных сетей
с протоколом коммутации каналов
,
состоящей из пяти периферийных и одного
центральных узлов. Приведено наглядное описание работы сети по временам
ожиданий в узлах и каналах. Формальное описание правила передачи приведено
с помощью уравнений
FCFS
для времен ожиданий в узлах и каналах. Основным
результатом работы является теорема, в котором найдено условия существования,
единственности стационарного режима работы сети и убывания корреляций по
времени как маркированный случайный процесс.
Ключевые слова:
Сети с очередями, коммутация каналов, узлы, каналы,
правила передачи, времена ожиданий, случайный процесс, стационарный режим,
уравнение, мажорирующий процесс.
Abstract:
The work is devoted to the analysis of star-shaped networks with a circuit
switching protocol, consisting of five peripheral and one central nodes. A visual description
of the network operation is given in terms of waiting times in nodes and channels. A formal
description of the transmission rule is given using the FCFS equations for waiting times
in nodes and channels. The main result of the work is a theorem in which conditions were
found for the existence, uniqueness of a stationary mode of operation of the network and
a decrease in correlations over time as a marked random process
.
Networks with queues, circuit switching, nodes, channels, transmission
rules, waiting times, random process, stationary mode, equation, majorizing process.
Annotatsiya:
Mazkur maqola beshta chetki va bitta markaziy tugundan va protokol-
li kanallar kommutatsiyasidan iborat yulduzsimon navbatli tarmoqlar ishini tahlil qilish-
ga bag‘ishlangan. Tugunlar va kanallardagi kutish vaqtlari bo‘yicha tarmoq ishining
ko‘rsatmali bayoni keltirilgan. Axborotlarni uzatish qoidasining tavsifi esa tugunlar va
kanallardagi kutish vaqtlari uchun FCFS tenglamalari orqali berilgan. Maqolaning aso
-
siy natijasi tarmoq ishining statsionar holati mavjudligi, yagonaligi va vaqt bo‘yicha
korrelyatsiyaning kamayishi uchun shart topilgan teoremadan iborat.
Kalit so‘zlar:
navbatli tarmoqlar, kanallar kommutatsiyasi, tugunlar, kanallar, uzatish
qoidasi, kutish vaqti, tasodifiy jarayon, statsionar holat, tenglama, majorlovchi jaroyon.
Key words:
Alfraganus
xalqaro ilmiy jurnal
41
ВВЕДЕНИЕ
Теория сетей с очередями имеет большой практический интерес. Они
используются в качестве моделей во многих приложениях-от транспортных сетей
до глобальных информационных сетей (например,
Internet
).
Периферийные узлы сети обозначим через
1, 2, 3, 4, и 5, а центрального через С (см. рис
1). В каждый периферийный узел поступает
Пуассоновский поток сообщений с
соответственно. Длины сообщений
возникших в этих узлах экспоненциально
распределенные случайные величины с
параметрами
.
Каждое сообщение, возникшее в узле
имеет маршрут
с вероятностью
и
с вероятностью
.
Сообщение получает доступ к следующему этапу в соответствии дисциплины
FCFS
(
First
came-first is serviced (первый пришел-первым обслуживается)). Че-
рез
обозначим сообщение возникший в узле
в момент имеющий маршрут и с длиной , где принимает
как значение один из маршрутов
или
. С математической точки зрения это означает, что задано
семейство независимых маркированных пуассоновских процессов
интенсивностями
с независимыми одинаково распределенными
марками
.
Теперь приведем наглядное описание правила передачи. Сообщение
ожидает, пока этот узел не покинут сообщения,
возникшие здесь, т.е. в узле , до него. Данный этап «жизни» сообщения удоб-
но назвать нулевой фазой ожидания; его длительность обозначается через
. С наглядной точки зрения,
–это время ожидания
сообщением
доступа к сети. Если
, то после заверше-
ния нулевой фазы ожидания т.е., в момент
(момент
получения доступа к сети) сообщение
передается по линии
в течение
Alfraganus
xalqaro ilmiy jurnal
42
времени, равного длине сообщения
. Если же
, то в момент
сообщение
«закрепляет» за собой линию
и начинает «претендовать» на вторую
линию маршрута, т.е. на линию
. Для сообщения
начинается
первая фаза ожидания, в ходе которой оно пропускает перед собой сообщения
с маршрутами
и начавшие претендовать на эту линию раньше, чем это сделало сообщение
. По завершении этой фазы ожидания, длительность которой обозначает-
ся
сообщение
передается по каналу
в течение времени
и после чего выбывает из
дальнейшего рассмотрения.
Теперь приведем формальное описание правила передачи. Для любых по-
следовательно возникших в узле сообщений
(это означает, что
(а) в случае если
выполнены соотношения
(1)
(2)
(б) если
, то
(3)
(в) если
и
, то
(4)
Alfraganus
xalqaro ilmiy jurnal
43
(г) для любых последовательно претендовавших на линию
возникших в узлах
сообщений
(это
означает,
что
)
t
(
D
y
′
)+
W
0
(
D
y
′
)+
W
1
(
D
y
′
)+
l
(
D
y
′
)≤
t
(
A
y
′′
)+
W
0
(
A
y
′′
)+
W
1
(
A
y
′′
) (5)
(6)
Математическая задача состоит в том, чтобы построить семейство
маркированных случайных процессов
, с марками
, которые дают решение уравнений (2), (3), (6). Можно
говорить, что искомое семейство маркированных случайных процессов
должны задавать «оснащение» пуассоновских процессов
, согласованное с описанным выше правилом передачи.
ТЕОРЕМА
Пусть
и
. Тогда существует семейство
маркированных случайных процессов
, дающее решение
уравнений (2), (3), (6). Это семейство единственно и обладает свойством убывания
корреляций по времени.
На первом этапе построения семейство маркированных случайных про-
цессов
рассматривается сеть, которая начинает работу
в момент времени
, исходя из «нулевого» начального состояния. Формально
говоря, рассматривается «урезанное» семейство внешних потоков
, где
сужение потока
на
, а также
прежнее правило передачи.
Лемма 1. Пусть семейство внешних потоков
и
правило передачи удовлетворяют условиям, сформулированным выше. Тогда для
любого
существует единственное семейство потоков
Alfraganus
xalqaro ilmiy jurnal
44
с марками
, удовлетворяющее системе
уравнений (2), (3), (6). Это семейство является оснащением семейства потоков
.
Доказательство леммы проводится с помощью «непосредственного» постро-
ения. Мы «запускаем» сеть в момент времени
, последовательно «присваивая»
сообщениям соответствующие значения компонент марки
.
На втором этапе доказывается, что семейство маркированных случай-
ных процессов
сходиться при
к предельному семейству
. Предельные
будут
представлять собой оснащение пуассоновских
и дают
решение системы уравнений (2), (3), (6).
Важную роль в ходе доказательства теоремы играет семейство независи-
мых одинаково распределенных маркированных случайных процессов
, которые будет в естественном смысле мажорировать допредель-
ные семейства
, равно как и предельное семейство
. Возможность построения такой мажоранты, не зависящей
от
, означает, что аппроксимирующие семейство маркированных случайных
процессов
, а следовательно и предельные семей-
ство маркированных случайных процессов
не могут «уйти
в бесконечность». Более того, через мажорирующие семейство маркированных
случайных процессов можно оценить «степень распространения влияния» в
семействах маркированных случайных процессов
.
В силу независимости для задания совместного распределения семейства
нам достаточно построить распределение отдельного
мажорирующего маркированного случайного процесса, который мы условимся
обозначать через . Это процесс с марками из
, представляющий собой
суперпозицию двух независимых маркированных случайных процессов
(7)
Здесь
пуассоновские процессы интенсивности
и
соответственно, c независимыми экспоненциально
Alfraganus
xalqaro ilmiy jurnal
45
распределенными марками из
с параметром
.
Лемма 2. (а) При достаточно малом значении маркированный случайный
процесс
допускает единственное оснащение, согласованное с уравнением
очереди
FCFS
. При этом для любого набора непересекающихся интервалов
и любого набора точек
условная вероятность
Здесь
– событие, состоящее в том, что в потоке
интервал содержится в одном из периодов занятости, роль условия играет
событие, что в моменты
, в потоке
«появились»
сообщения, а
– фиксированные константы.
(б) При любом
маркированные случайные процессы
и
можно определить на одном вероятностном пространстве
так, что с
вероятностью 1 при всех
будет
выполнено неравенство
Здесь
– процесс виртуального времени ожидания.
Сети на бесконечных графах имеет большой теоретический интерес, но в силу
бесконечности графа построение
представлять затруднительным. Только для
некоторых классов (например, для гибридных) сетей эта задача частично решено
[1], [2].
ЗАКЛЮЧЕНИЕ
При выполнении условий (7) рассмотренный
звездообразны
сеть с протоколом
коммутации каналов, согласованный с соотношениями и уравнениями (1) – (6),
имеет единственный стационарный режим работы, не зависящее от начального
состояния. Этот стационарный режим обладает свойством убывания корреляций
по времени как маркированный случайный процесс.
Alfraganus
xalqaro ilmiy jurnal
46
ЛИТЕРАТУРА:
1.
Шамсиев Р.Н., Еркишева Ж.С. Сети с очередями на бесконечной одномерной решетке с
протоколами гибридной коммутации. Материалы
VIII
международной научно-практической
конференции «Новината за напреднали наука».
–
София, 2012. – С. 22–25.
2.
Р.Н.
Шамсиев, Б.А.
Куралов.
Сети с очередями на бесконечных графах с пртоколами гибридной
коммутации.
Вестник ТашГТУ №3, 2014.
–
С. 8
–
12.
