Диссертация (1154395), страница 33

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 33)

проведем для сети без учета задержекпередачи информации от сервера-источника данных, т.е. для случая lag  0 . Длясети с учетом задержек передачи информации от сервера-источника данных ц.м.строится аналогично, отличие состоит в том, что вместо множестваM  Z, x  n  , x  h  ,определенного формулой (6.4), используется множествоM  Z, x  n  , x  h  , lag  n  , lag  h  , определенное формулой (6.7).Обозначим Sx  n  операцию сдвига вектора x  n  :если x  n    x  n,0  , x  n,1 , ... , x  n, M 1 , x  n, M   ,то Sx  n    0, x  n,0  , x  n,1 , ...

, x  n, M  1  .Обозначим tl момент сдвига содержимого буфера. Пусть в момент tl  0буфер находился в состоянии x  n  , тогда в момент tl  0 он будет находиться всостоянии Sx  n  . Соседние точки tl на оси времени определяют такт припостроении модели в дискретном времени: интервал tl , tl 1  соответствует l -мутакту при обмене данными в одноранговой сети.Предположим, что подключение пользователей к сети и его отключениеможет происходить только в моментn -пользователя в моментtl . Обозначимtl  0 . Величинаa l ( n)a l ( n)состояниеявляется индикаторомприсутствия n -пользователя в сети: al (n)  1 в момент tl  0 , если он находитсяв сети, в противном случае al (n)  0 .

В модели подключения пользователей ксети и их отключение описывают следующие условные вероятности:P al  n   1| al 1  n   0    n  ,P al  n   0 | al 1  n   0  1    n  ,- 189 -P al  n   0 | al 1  n   1    n  ,P al  n   1| al 1  n   1  1    n  ,где   n  вероятность появления и   n  вероятность ухода n -пользователя изсети. Далее при построении модели предполагаем, что пользователи имеютодинаковые вероятности прихода в сеть и ухода из нее:   n    ,   n    ,n  1,..., N . При отключении n -го пользователя от сети (переключениепользователя на другой канал также может быть интерпретировано какотключение) строка матрицы X , которая представляет собою вектор x  n  ,соответствующий состоянию буфера этого пользователя, обнуляется, т.е.x  n  0 .Алгоритм обмена порциями, соответствующий протоколу распределенияданных в одноранговой сети, описан в разделе 1.5.

На l -м такте сервером ипользователями совершаются следующие действия.1. В момент tl для каждого пользователя системы с вероятностями  и разыгрывается его появление либо уход из сети.2. В момент tl происходит сдвиг буфера каждого пользователя: порция данных, находившаяся в буфере пользователя в M - позиции,отправляется на воспроизведение; все остальные порции данных в буфере сдвигаются на одну позициювправо к концу буфера; 0-позиция в буфере пользователя освобождается.3.

В момент tl  0 сервер равновероятно выбирает любого из присутствующихl( a  n   1 ) в сети пользователей и начинает загружать ему порцию данных в0-позицию его буфера. Если выбран i -й пользователь, то x  i,0   1 в моментtl 1  0 .4. Каждый из присутствующих в сети пользователей, которого сервер невыбрал для загрузки  al  n   1, n  i  , выполняет следующие действия: Есливбуфереn -гопользователяестьпустыепозиции,т.е.M0  Z, x  n     , то n -й пользователь выбирает случайным образом из- 190 lприсутствующих в сети h -го пользователя, h  n , a  h   1 , при этомM1  Z, x  h  - множество заполненных данными позиций в буфере h -го пользователя. ЕслиM  Z, x  n  , x  h    ,топользовательn -йвыбираетвсоответствии со стратегией загрузки  позицию m  Z, x  n  , x  h   всвоем буфере, в которую он будет загружать порцию данных от h -гопользователя. ЕслиM  Z, x  n  , x  h    или в буферепозиций ( M0n -го пользователя нет пустых Z, x  n    ), то никаких действий не выполняется.Необходимые для дальнейшего изложения обозначения показаны нарис.

6.5. Здесь Zl  (al , Xl ) состояние сети в момент tl  0 .Zl 1Zlxl  n  Sxl  n xl 1  n al 1alal 1tt l 1tll -такт Рис. 6.5. Иллюстрация изменения состояний ц.м. Zl на l -м шагеНетрудно убедиться, что последовательностьц.м. над пространством состоянийlВведем   Z   P Zl  ZZ  : Z ,ll 0lобразуетZ  0,1N 0,1N (M 1) .вероятность цепи МарковаZ lна l -м шагенаходиться в состоянии Z и l ,l1  Z, Y  переходную вероятность ц.м. изl ,l1состояния Z в состояние Y на l -м шаге. Переходные вероятности   Z, Y зависят от номера m  Z, x  n  , x  h   и от вероятностей  появления и ухода пользователя из сети. Таким образом, стратегия выбора порцииданных для загрузки от другого пользователя сети определяет переходные- 191 l ,l1вероятности   Z, Y  , а уравнения Колмогорова-Чепмена - вероятности l Z : l 1  Y     l  Z  l ,l 1  Z, Y  , Y  Z , l  0 .(6.9)ZZМодель процесса обмена данными без лагов была построена в [31, 132], амодель с лагами в [53, 171].lРешением системы (6.9) являются вероятности   Z  состояний ц.м.Z , l  0 .lЗная это распределение, можно получить формулы для расчетавероятности V  n  непрерывного воспроизведения видео потока, котораясоответствует вероятности того, что в конце такта в M -й позиции буфера n -йпользователь имеет порцию данных для воспроизведения видео.

В модели этухарактеристику определяет состояние последнего M -го столбца матрицы X ,которая отражает состояние буферов всех пользователей сети.llОбозначим p0  n, m  ( p1  n, m  ) вероятность того, что m -я позиция буфераn -гопользователя пуста (заполнена) наl -м шаге. Этивероятностиопределяются по следующим формулам:P  xl  n, m   0 P  xl  n, m   1 YZ : y ( n )  x ( n ), x n , m  0, a ( n ) 1 l (Y) : p0l  n, m  ,lYZ : y ( n )  x ( n ), x n , m  1, al ( n ) 1 l (Y) : p1l  n, m  ,p0l  n, m   p1l  n, m   1 .(6.10)Для нахождения вероятности непрерывного воспроизведения введемвеличину q  n, m, Z,   , которая для каждого состоянияZ  Z определяетчисло пользователей, у которых в m -й позиции есть порция данных длязагрузки n -му пользователю согласно стратегии выбора  :Nq  n, m, Z,     I m  Z, x(n), x(h)   m, Z  Z ,h 1hn - индикаторная функция.где I (6.11)- 192 -NТакжеобозначимN(Z)   a(n)числоприсутствующихвсетиn 1пользователей, когда сеть находится в состоянии Z  (a, X) .

Определимфункцию Ql (n, m,  ) , которая представляет собою вероятность того, что в сетина l -м шаге у присутствующих пользователей имеется порция данных длязагрузки n -пользователю в m -ю позицию буфера.Теорема 6.3. Для Z  Z таких, что N(Z)  2 , вероятность Ql (n, m,  ) можетбыть рассчитана по формуламQl (n,0,  )  0 ,Ql (n, m,  )  ZZq  n, m, Z,   l  (Z) , m  1,..., M .N(Z)  1Соотношение,связывающеевероятности(6.12)состоянийбуфераn -гопользователя на  l  1 -м и l -м шагах, следует из формулыP  xl 1  n, m  1  1  P  x l  n, m   1, a l (n)  1  (1   )  P  xl  n, m   0, a l (n)  1  (1   )  Q l (n, m,  )  P  xl  n, m   1, a l (n)  0   (6.13) P  xl  n, m   0, a l (n)  0    Q l (n, m,  ), m  1,..., M.Из (6.13) c учетом P xl  n, m   1, al (n)  0  0 и P xl  n, m   0, al (n)  0  1следует теорема 6.4.Теорема 6.4.

Вероятности состояний буфера n -го пользователя на l -м шагеопределяются следующими соотношениями:p1l  n,0  1,Np1l 1  n, m  1  p1l  n, m   (1   )  p0l  n, m   (1   )  Ql (n, m,  )   Ql (n, m,  ) , m  1,..., M  1 .(6.14)Предельным переходом из теоремы 6.4 получаем соотношение для расчетастационарных вероятностей:p1  n,0  1,Np1  n, m  1  p1  n, m   (1   )  p0  n, m   (1   )  Q(n, m,  ) - 193 -  Q(n, m,  ) , m  1,..., M  1 .(6.15)Рекурсивное соотношение (6.15) определяет метод расчета вероятностиp1  n, M  того, что M -я позиция буфера n -го пользователя заполнена, т.е.искомой вероятности V  n  непрерывного воспроизведения видео потока:V  n   p1  n, M  .(6.16)Таким образом, для дальнейшего анализа необходимо вычислять матрицуl ,l1переходных вероятностей   Z, Y  .

Этому посвящен следующий разделдиссертационной работы.6.3.Аналитический метод расчета матрицы переходных вероятностейДля расчетов по формуле (6.14) необходимо уметь вычислять вероятностиQl (n, m,  ) , которые в свою очередь зависят от распределения  l  Z  , Z  Z  .Для вычисления этого распределения необходимо решить систему уравнений(6.9), для которой далее получен аналитический метод расчета матрицыпереходных вероятностей.Без потери общности изложения метод расчета матрицы переходныхвероятностей получен [169] для случая, когда пользователи постоянноприсутствуют в сети, для стратегии загрузки данных LF. В этом случае al  1 ,l  0 , а состояние Zl  (al , Xl ) ц.м.

Zl  в момент t1  0 определяет только Xl ,где X =  x  n  n1,..., N - матрица, описывающая состояния буферов всех Nпользователейсети.Последовательностьпространством состояний X = 0,1N ( M 1)X , l  0lобразуетц.м.надl. Пусть   X  – вероятность того, чтоц.м. Xl , l  0 на такте l находится в состоянии X , т.е.  l  X   P Xl  X , иl ,l 1  X, Y   P Xl 1  Y | Xl  X – переходная вероятность ц.м.

Характеристики

Список файлов диссертации