Использование стохастической игры в формировании поведения трафика в распределительных устройствах связи (маршрутизаторах)

Стохастическая игра в формировании поведения трафика в распределительных устройствах связанна с решением проблемы пересылки.

Устройства передачи данных (маршрутизаторы) на рисунке 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

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