Investigation of random access computer networks operating in a diffusion environment with an increasing number of subscriber stations

Vavilov Viacheslav PhD in Physics and Mathematics Associate Professor, Department of Software Engineering, National Research Tomsk State University 634050, Russia, Tomskaya oblast', g. Tomsk, ul. Lenina, 36 vavilovv@yandex.ru Other publications by this author

Введение

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

Увеличивающийся объём информационных потоков ставит новые задачи развития и интеграции вычислительных сетей и сетевых технологий. Появление телекоммуникационного стандарта нового поколения 5G на определённое время решает ряд проблем, поскольку обеспечивают надёжные коммуникации, а также достаточно высокую пропускную способность и скорость передачи. Тем не менее, развитие интернета вещей в перспективе потребует дальнейшего увеличения пропускной способности компьютерных сетей, а, следовательно, исследования различного рода в данном направлении остаются актуальными.

Наиболее распространены как в России, так и в целом мире, сети случайного множественного доступа ^[1]. Основной принцип функционирования – случайный доступ множества абонентских станций к единому ресурсу – разделяемой среде (каналу) передачи данных. Любая абонентская станция в любой момент времени может обратиться к общей среде передачи данных (коаксиальный кабель, оптоволокно, спутниковый канал связи и т. д.) с попыткой осуществления передачи информации. В этом случае не исключён конфликт (коллизия) – когда из-за принципа случайности одна станция может отправить в сеть пакет данных во время передачи сообщения от другой станции. В такой ситуации сигнал искажается и абонентские станции должны передать свои пакеты заново после завершения этапа оповещения о конфликте. Попытки передачи пакетов абонентскими станциями на этапе оповещения о конфликте безрезультатны, так как единая передающая среда в этом случае занята. Чем больше абонентских станций в сети, тем больше конфликтов, а чем больше конфликтов, тем меньше работоспособность сети. Растущее число абонентских станций – не единственный фактор, влияющий на эффективность функционирования компьютерных сетей. Множество внешних факторов, изменяющих процесс передачи данных в сети, называют случайной средой.

Данная работа посвящена математическому моделированию сетей с множественным доступом в случайной среде. Основные методы анализа – методы теории конечно-разностных и дифференциальных уравнений ^[2], случайных процессов ^[3-5] и теории массового обслуживания ^[6-12]. База моделирования – системы массового обслуживания с повторными вызовами ^[6-7]. Такой подход моделирования компьютерных сетей даёт возможность анализа механизмов передачи данных с получением вероятностных характеристик функционирования ^[13-15].

Особенность предложенной в работе модели – учёт влияния внешних воздействий на процесс функционирования сети. В ряде работ случайная среда представлена цепью Маркова [17-18, 24-32], полумарковским процессом [19-21, 33-36]. В данной работе, как и в работах ^[22-23], случайная среда – есть диффузионный процесс.

Исследование выполнено в предельных условиях возрастающего количества абонентских станций с применением асимптотических методов ^[11-12]. В результате найдены коэффициенты переноса и диффузии аппроксимирующих диффузионных процессов. Такой подход использован в ряде работ, например ^[16-23]. Получение коэффициентов переноса и диффузии даёт возможность анализа плотности распределения вероятностей значений процесса изменения состояний математической модели компьютерной сети.

1. Математическая модель

Представим случайную внешнюю среду, влияющую на работоспособность сетей множественного доступа как диффузионный процесс, описываемый уравнением ds(t)=α(s)dt+β(s)dw(t), где w(t) – есть процесс Винера. Воздействие среды приводит к изменению длительности передачи пакетов по каналу, интенсивности обращения заявок из орбиты, а также характеристик входящего потока сообщений.

Модель сети с оповещением о конфликте рассмотрим в виде однолинейной системы массового обслуживания, куда поступают заявки от ограниченного числа N абонентских станций. Время генерации заявки от одной станции имеет экспоненциальное распределение с параметром λ(s)/N. Входной поток управляется описанным выше диффузионным процессом. Вероятность обращения новой заявки за бесконечно малый промежуток времени Δt равна (λ(s)/N)Δt+o(Δt).

Заявка, поступившая в свободную систему, начинает обслуживаться. Время обслуживания заявки на приборе при условии пребывания среды в состоянии s, имеет экспоненциальное распределение с параметром μ(s). Вероятность завершения успешного обслуживания заявки за бесконечно малый промежуток времени Δt равна μ(s)Δt+o(Δt). Если во время обслуживания заявки поступает ещё одна заявка, то начинается этап конфликта.

Таким образом, состояния системы, определяемые прибором: k=0, если прибор свободен; k=1, если он занят обслуживанием; k=2, если идёт этап конфликта.

Конфликтные заявки и заявки, поступившие во время конфликта переходят на орбиту. Интенсивность обращения заявок из орбиты зависит от состояний s случайной среды, то есть γ(s)/N. Вероятность обращения заявок на прибор из орбиты за бесконечно малый промежуток времени Δt равна (γ(s)/N)Δt+o(Δt). Будем полагать, что на орбите i заявок.

Величины интервалов оповещения о конфликте имеют экспоненциальное распределение с параметром 1/a.

Таким образом, в силу выше изложенного описания, процесс {k(t),i(t),s(t)} изменения во времени состояний {k(t),i(t)} математической модели сети связи и состояний {s(t)} математической модели среды является марковским процессом.

Обозначим P(k(t)=k,i(t)=i,s≤s(t)<s+ds)/ds=P_k(i,s,t).

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

Используя подход, аналогичный предложенному нами в работах ^[22-23], для распределения вероятностей P_k(i,s,t) можно получить прямую систему дифференциальных уравнений Колмогорова:

Будем искать решение P_k(i,s,t) системы (1) методом асимптотического анализа ^[12] в условиях растущего числа абонентских станций N→∞.

Обозначим

и рассмотрим предельный процесс

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

Рассмотрим также процесс

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

Для достаточно малых ε, рассмотрим процесс z(τ)=x(τ)+y(τ), аппроксимирующий число заявок на орбите ε²i(τ/ε²), покажем, что это однородный диффузионный процесс.

Учитывая обозначения (2), выполним замены в системе (1):

Полагая, что функции H_k(y,s,τ,ε) дифференцируемы по y, получим систему:

Для дальнейшего анализа будем использовать данную систему.

2. Исследование асимптотических средних характеристик

Асимптотические средние характеристики сети – это распределение вероятностей R_k(x) состояний k канала и функция x=x(τ).

Теорема 1. Асимптотически при N→∞ распределение вероятностей R_k(x) состояний k канала имеет вид

где

здесь a задано, x=x(τ) – детерминированная функция, определяемая обыкновенным дифференциальным уравнением вида:

в котором ψ_k(x), Λ_k(x), k=0,1 есть величины вида:

здесь Q_k(x,s) определяется решением системы (10) и условием нормировки (11).

Доказательство. В (4) перейдем к пределу при ε→0, положим, что существуют конечные пределы

получим:

Решение H_k(y,s,τ) системы (8) будем искать в виде:

где H(y,s) – есть плотность распределения вероятностей значений процесса y(τ), а Q_k(x,s) – есть условное совместное распределение вероятностей состояний k канала и s среды и, как следует из (8), определяется системой:

и условием нормировки:

Обозначим:

здесь R_k(x) и r(s) – маргинальные распределения вероятностей состояний k канала и s среды соответственно. Для данных распределений должны выполняться условия:

Сложим по k уравнения системы (10) и с учётом обозначения (12) получим:

которое совместно с условием нормировки (13) определяет стационарное распределение вероятностей r(s) состояний диффузионной среды.

Уравнение (14) – линейное однородное дифференциальное уравнение второго порядка. Обозначим:

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

Решение имеет вид:

С учётом замены получим:

Константу C найдём из условия нормировки (13), тогда стационарное распределение вероятностей r(s) состояний s среды примет вид:

Проинтегрируем каждое из уравнений системы (10) по s, учтём (13), обозначим:

положим, что

тогда (10) примет вид:

Система (17) совместно с условием нормировки (13) даёт решение вида (5).

Далее в системе (4) функции H_k(y±ε,s,τ,ε) разложим в ряд по приращениям y с точностью до o(ε), получим:

Уравнения системы (18) просуммируем по k, проинтегрируем по s и, полагая что

запишем:

Поделим на ε обе части полученного уравнения, выполним переход (7), учтём (10):

По условию нормировки (11), обозначению (12), можно записать:

Так как производная плотности распределения H(y,τ) не может тождественно равняться нулю, значит, функция x=x(τ) – есть решение обыкновенного дифференциального уравнения вида (6). Теорема доказана.

3. Исследование величин отклонения

Правую часть дифференциального уравнения (7) обозначим как A(x), тогда

Теорема 2. Асимптотически при N→∞ случайный процесс y(τ) определяется стохастическим дифференциальным уравнением вида:

где w(τ) есть стандартный процесс Винера, A'(x) определяется обозначением (20), а функция B(x) определяется равенством:

здесь a задано, R_k(x) есть распределения (5), величины ψ_k(x), Λ_k(x), k=0,1 определяются равенствами (16), функции h_k⁽¹⁾(x), k=0,1,2, η_k(x), k=0,1 – определяются обозначением (33) и решением системы (32).

Доказательство. Будем искать решение H_k(y,s,τ,ε) системы (4) в виде разложения:

Сначала найдём вид функций h_k(y,s,τ). Перепишем (18) в виде:

Подставим в эту систему разложение (23), учтём (10) и запишем полученную систему, сократив на ε все уравнения, в виде:

Будем искать решение системы (24) в следующем виде:

Подставим (25) в (24) и представим систему в виде двух систем:

и

Продифференцируем (10) по x, получим:

Из (27) и (28) следует, что решение h_k⁽²⁾(x,s) системы (27) имеет вид:

С учётом (29) и (25) разложение (23) примет вид:

Теперь найдём вид функции H(y,τ). Функции в правой части (4) разложим в ряд по приращениям y с точностью до o(ε²), получим:

Сложим уравнения системы (31) по k, получим:

Подставим в полученное равенство разложение H_k(y,s,τ,ε) в виде (30), учтём (12):

Проинтегрируем (32) по s, учтём условие нормировки (13), обозначение (12), обозначим:

учтём (19), получим:

В силу дифференциального уравнения (6) уничтожим слагаемые порядка o(ε), поделим обе части полученного уравнения на ε², выполним преобразования, будем иметь:

Получили уравнение Фоккера-Планка для плотности H(y,τ). При этом, коэффициент переноса (35) – это A'(x). В силу обозначения (20) можно записать:

Обозначим коэффициент диффузии:

Получили, что (37) совпадает с (22).

Из (35) следует, что H(y,τ) – есть плотность распределения вероятностей некоторого процесса y(τ), который удовлетворяет стохастическому дифференциальному уравнению (21). Теорема доказана.

Следствие 2.1. Решение y(τ) стохастического дифференциального уравнения (21) имеет вид:

где w(τ) – стандартный процесс Винера.

Доказательство. Представим процесс y(τ) в виде:

тогда

здесь A'(x) определяется равенством (20).

Продифференцируем f(x), используя формулы Ито:

Учитывая (21), получим:

Выполним преобразования, будем иметь:

Проинтегрируем (40), положим f(0)=0, получим, что исходное представление y(τ) в виде (39) примет вид (38). Следствие доказано.

4. Аппроксимация процесса изменения состояний сети

Третьим этапом необходимо показать, что для малых значений ε случайный процесс z(τ)=x(τ)+εy, аппроксимирующий процесс ε²i(τ/ε²) является однородным диффузионным процессом. Докажем теорему.

Теорема 3. С точностью до o(ε) случайный процесс z(τ) является решением стохастического дифференциального уравнения:

где w(τ) есть стандартный процесс Винера.

Доказательство. Поскольку z(τ)=x(τ)+εy, то дифференцируя z(τ) по τ получаем:

В силу (6) и (21) имеем:

Так как правая часть содержит разложение в ряд по приращениям εy аргумента x, то:

Заметим, что z(τ)=x(τ)+εy, тогда с точностью до o(ε), имеем:

С учётом (20) уравнение (42) примет вид:

Таким образом, z(τ) – однородный диффузионный процесс с коэффициентом переноса A(z) и коэффициентом диффузии ε²B²(z), определяемый с точностью до o(ε) стохастическим дифференциальным уравнением вида (41). Теорема доказана.

Следствие 3.1. Плотность распределения вероятностей значений процесса z(τ) имеет вид:

.

Доказательство. Обозначим F(z,τ) плотность распределения вероятностей значений процесса z(τ), тогда можно записать уравнение Фоккера – Планка для плотности:

.

Положим, что F(z,τ)=F(z), тогда стабильное распределение можно отыскать из уравнения Фоккера – Планка:

Обозначим:

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

Проинтегрируем:

выполним преобразования:

Учтём замену (45) и перепишем последнее уравнение в виде:

Константу C найдём из условия нормировки:

тогда

Подставим (47) в (46), получим плотность распределения вероятностей для процесса z(τ) в виде (43). Следствие доказано

Выводы

Итак, в работе предложена математическая модель функционирующих в диффузионной среде сетей случайного множественного доступа. Асимптотическим методом ^[12] получено обыкновенное дифференциальное уравнение (6), определяющее среднее x=x(τ) нормированного числа заявок на орбите. Распределение R_k(x), k=0,1,2, вероятностей состояний канала сети представлено в виде (5), где функции Q_k(x,s), k=0,1,2, – есть совместное распределение вероятностей состояний k канала и s среды. Эти функции определяются системой (10) и условием нормировки (11). Показано, что процесс y(τ), характеризующий изменение величин отклонения нормированного числа требований на орбите, является диффузионным процессом авторегрессии и определяется стохастическим дифференциальным уравнением (21). Доказано, что для малых значений ε процесс z(τ)=x(τ)+εy – есть однородный диффузионный процесс. Найдена плотность распределения вероятностей значений этого процесса в виде (47). Полученные результаты могут использоваться для оценки характеристик функционирования компьютерных сетей множественного доступа, при проектировании и разработке сетевых протоколов.