Использование стохастической игры в формировании поведения трафика в распределительных устройствах связи (маршрутизаторах)
Автор: Сула Б.А., Лебедев И.Э., Мурая Е.Н.
Журнал: Международный журнал гуманитарных и естественных наук @intjournal
Рубрика: Технические науки
Статья в выпуске: 5-4 (92), 2024 года.
Бесплатный доступ
В данной научной статье рассматривается использование стохастической игры для формирования поведения трафика в распределенных устройствах связи. А также рассматривается применение методов оптимизации для улучшения качества обслуживания и уменьшения задержек в передаче данных, применяя последовательное исследование всех стратегий передачи, что качественно увеличивает пропускную способность канала связи.
Стохастические игры, передача трафика, оптимизация сети, маршрутизация
Короткий адрес: https://sciup.org/170205280
IDR: 170205280 | DOI: 10.24412/2500-1000-2024-5-4-75-79
Текст научной статьи Использование стохастической игры в формировании поведения трафика в распределительных устройствах связи (маршрутизаторах)
Стохастическая игра в формировании поведения трафика в распределительных устройствах связанна с решением проблемы пересылки.
Устройства передачи данных (маршрутизаторы) на рисунке 1 обозначены цифрами 1 и 2. При построении игры предполагается, что в точках 1 и 2 находятся игроки 1 и 2. В этих точках в появляются па- кеты данных однообразной длины с вероятностью: ai е (0, 1) и a2 £ (0, 1).
Цель игрока 1 – переслать пакет в точку dl, а цель игрока 2, по аналогии, - переслать пакет в вершину d2. При передачи у игроков пересекаются пути. Чтобы передача считалась успешной, она должна проходить через противоположного игрока.

Рис. 1. Схема передачи данных
Опишем систему вознаграждений за доставку пакета и систему наказаний за задержку, применимую к игрокам:
-
- с е (0, 1) - издержки игрока при доставке одного пакета данных;
-
- с е 1 - вознаграждение игрокам за успешную доставку пакета.
При доставке «чужого» пакета игрок, несет издержки в размере с. вознаграждение за успешную пересылку пакета в размере 1 получает игрок, у которого этот пакет изначально появился. В случае отказа игроком переслать пакет другого игрока этот пакет остается у игрока, у которого этот пакет изначально появился, и на следующем шаге новый пакет данных у него не появляется. Состояние стохастической игры определяет наличие или отсутствие пакета данных у игроков 1 и 2. Множество состояний игры есть {(0, 0),(0, 1),(1, 0),(1, 1)}, где первый элемент вектора обозначает число пакетов у игрока 1, а второй элемент – число пакетов у игрока 2.
При доставке пакета другого игрока, иной игрок несет расходы в размере с. Награда за успешную передачу пакета будет в размере 1 и вручается игроку, изначально получившему этот пакет. Если игрок отказывается пересылать пакет другому игроку, этот пакет остается у игрока, у которого этот пакет изначально был, и на следующем этапе новый пакет данных не появляется. Состояние стохастической игры определяет наличие или отсутствие пакета данных от игроков 1 и 2. Существует множество состояний игры {(0, 0), (0, 1), (1, 0), (1, 1) }, где первый элемент вектора обозначает количество пакетов у игрока -1, а второй элемент - количество пакетов у игрока - 2.
-
- Пусть состояние (0, 0), тогда стратегия игрока 1 и 2 - W «ожидать». Выигрыш игроков - (0, 0). Вероятность перехода из состояния (0, 0) в состояние (0, 0), (0, 1), (1, 0), (1, 1) будем обозначать через p ii , p i2 , p i3 и p i4. Эти вероятности составляют общий вектор p i = (p ii , p i2 , p i3 , p i4 ), который равен ((1 - a i )(1 - а 2 ), (1 - a i )a2, ai(i - а2), aia2).
-
- Пусть состояние (0, 1): тогда стратегия игрока 2 - Т «отправлять». В свою очередь, игрок 1 может пойти по двум стратегиям: F «отправлять» и D «не отправлять». Выигрыши игроков представлены в матрице:
Т
F
D
(
-с i
о
-с
)
(i)
Вероятность перехода из состояния (0, 1) в состояния (0, 0), (0, 1), (1, 0), (1, 1) при условии, что в игре использовалась ситуация (F, Т), обозначенная через p2,i(F, Т), p2,2(F, Т), p2,3(F, Т) и p2,4(F, Т). Эти вероятности будут задавать вектор переходных вероятностей p2(F, Т) = (p 2i (F, Т), p 22 (F, Т), p 23 (F, Т), p 24 (F, Т)), который будет равен ((1 - a i )(1 -a 2 ), (1 - a i )a 2 , a i (1 - a 2 ), a i a 2 ).
Вероятность перехода из состояния (0, 1) в состояния (0, 0), (0, 1), (1, 0), (1, 1) при условии, что в игре использовалась ситуация (D, Т), обозначенная через p 2i (D, Т), p 22 (D, Т), p 23 (D, Т) и p 24 (D, Т). Эти вероятности будут задавать вектор переходных вероятностей p 2 (D, Т) = (p 2i (D, Т), p 22 (D, Т), p 23 (DJ), p 24 (D, Т)), который будет равен (0, 1 - a i , 0, a i ).
-
- Пусть состояние (1, 0), тогда стратегия игрока 1 - Т «отправлять». Игрок 2 будет иметь две стратегии: F «отправлять» и D «не отправлять». Выигрыши игроков представлены в матрице:
Т
F
D
i
(
- с
- с
)
Вектор вероятности перехода из состояния (1, 0) в состояния (0, 0), (0, 1), (1, 0), (1, 1) при условии, что в игре использовалась ситуация (Т,F), обозначим через p3(F,F) = (pз1(Т,F), pз2(Т,F), pзз(Т,F), pз4(Т,F)), который равен ((1 - ai)(1- a2), (i - ai)a2, ai(1 - a2), aia2). Вектор вероятности перехода из состояния (1, 0) в состояние (0, 0), (0, 1), (1, 0), (1, 1) при условии, что в игре использовалась ситуация (Т,D), обозначим через pз(Т,D) = (p3i(F,D), pз2(Т, D), pзз(Т,D), pз4(Т,D)), который будет равен (0,0,1 - a2, ai).
-
- Пусть состояние (1, 1), тогда у каждого игрока в начале периода есть свой пакет трафика для отправки. Стратегией любого игрока 1 или 2 будет: F («отправлять») и D («не отправлять»). Следовательно, если каждый игрок отправляет пакет трафика другого игрока, то пакеты трафика будут
считать доставленными, и каждый игрок сможет получить выигрыш, который будет равен единице с учетом издержек по от- правке пакета трафика иного игрока. Следовательно, выигрыши игроков будут такими, как в матрице:
Т
F
D
(1 — с, 1 — с) (— с, 1)
( (1, — с) (0, 0) )
В этом состоянии существует всего четыре возможных ситуации в чистых стратегиях.
Вероятность перехода из (1, 1) в (0, 0), (0, 1), (1, 0), (1,1) приведена в таблице 1.
Таблица 1. Вероятности перехода из состояния (1, 1).
Ситуация |
Р4О = (Р 41О , Р 42О , Р 43О , Р 44О ) |
(F, F) |
((1 — a i )(1 — a 2 ),(1 — a i )a 2 , a i (1 — a 2 ), a i a 2 ) |
(F, D) |
(0, 0, 1 — a 2 , a 2 ) |
(D, F) |
(0, 1 — a i , 0, a i ) |
(D, D) |
(0, 0, 0, 1) |
Игроки используют стратегии, которые имеют зависимость только от нынешнего состояния и не имееют зависимости от периода времени. Следует принять Пф Е Hi , которая является стратегией игрока «i = 1,2» в игре Г. Стратегия ni — это функция от состояния, которая показывает его в множестве вероятностных распределений, на множестве чистых стратегий игрока i в этом состоянии. Пара стратегий (η1,η2) формирует одну ситуацию в игре Γ, которая будет обозначена через Ei. В качестве выигрыша i в стохастической игре следует рассмотреть дисконтироваванную сумму выигрышей игроков:
Ein) =
п о (1 - о n(n))' 1 Ki (п),
где π 0 – вектор начального распределения по состояниям; I – единичная матрица, размерность которой равна количеству состояний в игре; 8 - дисконтирующий фактор; Π(η) – матрица переходных вероятностей, строками которой являются строки p i , р 4 , определенные выше; Ki(n) - вектор выигрышей в каждом состоянии игры при условии, что игроки реализуют ситуацию η .
На основании описания состояний можно принять решение по стохастической игре, которая основана на выборе путей передачи данных, и разработать модель вероятностей состояний с определенными условиями. Это поможет в профессиональной деятельности выбирать наиболее подходящие маршруты для распределения трафика.
Режим общей пересылки пакетов предполагает передачу данных внутри одной сети последовательно. На рисунке 2
устройства передачи данных обозначены как вершины 1 и 2. В начале каждого временного периода пакет данных единичной длины появляется в вершине s с вероятностью a1 (0, 1). Общая цель обоих игроков заключается в передаче пакета в вершину d. Из схемы передачи данных видно, что пакет достигнет вершины d только в том случае, если оба игрока передадут его.
Режим общей пересылки пакетов предполагает передачу данных внутри одной сети последовательно. На рисунке 2 устройства передачи данных обозначены как точки 1 и 2. В начале каждого временного периода пакет данных единичной длины появляется в вершине s с вероятностью a i (0, 1). Общая цель обоих игроков заключается в передаче пакета в вершину d. Из схемы передачи данных видно, что пакет достигнет вершины d только в том случае, если оба игрока передадут его.

Рис. 2. Схема передачи данных
С точки зрения стохастической игры, состояние вершины определяет наличие или отсутствие пакета данных в начале каждого периода. Существует большое количество состояний игры, которые имеют значение {0, 1}. Это количество равно количеству пакетов в вершине s. Рассмотрим каждое из этих состояний игры, определим стратегии и выигрыши игроков в каждом из них, а также вероятность перехода к другим игровым ситуациям.
-
- Пусть остояние 0, тогда стратегия игрока 1 и 2 - W («ожидать»). Выигрыши игроков будут составлять - (0, 0). Вероятности перехода из состояния 0 в состояния 0, 1 обозначим через р ‘11 , р ‘1,2 соответ-
- F D
ственно. Эти вероятности формируют вектор p i = (р 11 , р ‘12 ), который равен (1 - a i , Я 1 ).
-
- Предположим, что на начальном этапе периода пакет данных для передачи появляется в вершине s. Игроки могут выбирать между двумя стратегиями: F («отправлять») и D («не отправлять»). Если оба игрока решат отправить пакет, то считается, что передача прошла успешно, и каждый из игроков получит выигрыш в размере единицы за вычетом издержек на передачу. Таким образом, выигрыши игроков будут следующими:
F (1 — с, 1 — с) (— с, 0)
D ( (0, 0) (0, 0)
В данном контексте имеется четыре ситуации, описанные с использованием чистых стратегий. Вероятности перехода из состояния 1 в состояния 0 и 1 приведены в таблице 2.
Таблица 2. Вероятности перехода из состояния 1
Ситуация |
Р‘ 2 (•) = (Р‘ 21 (•), Р‘ 22 (•)) |
(F, F) |
(1 — Я 1 , Я 1 ) |
(F, D) |
(0, 1) |
(D, F) |
(0, 1) |
(D, D) |
(0, 1) |
У всех игроков в этой стохастической игре есть две стратегии. Пусть пчц — j-я стратегия игрока i = 1, 2, при этом j = 1, 2. Следовательно стратегия пij будет такой, при которой пи (1) = ^ и пi1(2) = F для любой i. Стратегия пi2 такова, что цi2(1) = W и пi2(2) = D для любой i.
Возьмем п о = ( n oi ; 1 - n oi ). Рассчитаем выигрышь игроков используя формулу (4):
£ 1 (пи, п 12 ) = &( п 12 , п 21 ) = £ 3 ( п 12 , п 22 ) = 0, i = 1,2
Исходя из описания состояний можно прийти к решению стохастической игры, основанной на наличии пакетов данных, а также составить модель вероятностей состояний с заданными условиями, что поз- волит в профессиональной производственной деятельности выбирать наиболее релевантные условия распределения трафика.
Список литературы Использование стохастической игры в формировании поведения трафика в распределительных устройствах связи (маршрутизаторах)
- Ивченко А.И. Применение методов теории игр при анализе телекоммуникационных систем: монография. - Новосибирск: Изд-во НГТУ, 2019. - 287 c.
- Крейнин Е.И., Васильева О.С. Маршрутизация в современных сетях передачи данных: учебное пособие. - М.: Издательский дом ВШЭ, 2018. - 320 c.
- Коваленко И.И., Воробьев А. И. Основы теории игр и приложения: учебное пособие. - М.: Издательство "Финансы и статистика", 2019. - 288 c.