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

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

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

на шаге l  0,X, Y  X . В этом случае уравнения (6.9) примут следующий вид: l 1  Y     X  X, Y  ,ll ,l 1YX , l  0 .(6.17)XXДлявычисленияматрицыпереходныхвероятностей l ,l1введемвспомогательную матрицу A  Xl 1  SXl , каждый элемент которой показывает,- 194 -какие изменения произошли с m -й позицией буфера n -го пользователя на l -мтакте: A(n, m)  0 , если не было изменений; A(n, m)  1, если n -й пользовательуспешно загрузил порцию данных в m -ю позицию своего буфера; A(n, m)  1 ,если имеющаяся на предыдущем такте в m  1 -йпозиции порция данныхпосле операции сдвига отсутствует в буфере пользователя.Заметим, что A(n, 0) равно 1, если n -й пользователь на l -м такте получилNпорцию данных непосредственно от сервера.

Таким образом, A(n, 0)  1 .n 1MЕсли  A  n, m   1 , то n -й пользователь успешно загрузил порцию данныхm0Mна l -м такте. Если A  n, m   0 , то на l -м такте n -й пользователь не загрузилm0порций данных ни от сервера, ни от других пользователей. Это моглопроизойти, если пользователь не был выбран сервером для загрузки, а также попричине отсутствия пустых позиций в буфере n -го пользователя, или в случае,если n -й пользователь неудачно выбрал целевого пользователя, т.е. выбрал вкачестве целевого пользователя, у которого не было доступных для загрузкипорций данных.Определим два множества X 1 и X 1 пар состояний X, Y   X  X ,длякоторых, согласно предположениям модели, переходы между состояниямивнутри пары невозможны:X1   X, Y  : n  N , m  M, Y  n, m   SX  n, m   1 ;X1  X, Y  : n  N ,   Y  n, m  SX  n, m  2 .mMМножество X 1 соответствует переходам из состояния X в состояние Y ,при которых хотя бы одна порция данных «исчезла» из буфера хотя бы одногопользователя.

Множество X 1 соответствует переходам, при которых хотя быодин пользователь скачал больше одной порции данных.sДалее определим вероятности следующих событий: PXY  n  – вероятностьтого, что при переходе системы из состояния X в состояние Yn -йпользователь получил порцию данных от сервера; PXY  n  – n -й пользователь- 195 не получил данных ни от сервера, ни от других пользователей; PXY  n  – n -йпользователь успешно скачал порцию данных от другого пользователя. Длястратегии LF эти вероятности вычисляются по формулам (6.18)-(6.20).sPXY n 1N(6.18)1 n PI   1 SX n,m  SX h,m 0 XYN-1 hN \n  mMPXY n (6.19)1   Y  n, m  N -1 mM \0 (6.20) m1 SX  n, m    SX  h, m   I   1  SX  n, i    SX  h, i   0   .hN \n i 1Таким образом, переходные вероятности ц.м.

рассчитываются согласноследующей теореме.Теорема 6.5. Пусть Xl  X и Xl1  Y , тогдаl ,l1  X, Y   0 , если X = Y ;(6.21)l ,l1  X, Y   0 , если (X, Y)  X1  X1(6.22)s l ,l 1  X, Y    I  A  n,0   1  PXY n nN  I   A  n, m   0   PXY n  mM(6.23)  I   A  n, m   1  PXYn   , если (X, Y)  X \ X1  X1 . ■ mM \0Предположим, что существует финальное распределение ц.м. Xl , l  0 иобозначим   X   lim  l  X  финальную вероятность состояния X .

Тогда вl (6.17)матрицапереходныхвероятностейнезависитотl,т.е. l ,l1  X, Y     X, Y  l  0,  X, Y   X  X . Следовательно, формулы (6.18)(6.20) и теорема 6.5 позволяют рассчитать матрицу  и стационарныевероятности   X  , X  X , ц.м. Xl , l  0 .Для иллюстрации предложенного метода вычисления матрицы переходныхвероятностей рассмотрим численные примеры.- 196 -Пример 1.Для изображенного на рисунке перехода X, Y   X 1 , т.к. A 1,3  1 . т.к.первый пользователь ( n  1 ) «потерял» порцию данных из второй позициисвоего буфера ( m  2 ). Таким образом, в этом примере   X, Y   0 .A = Y - SXXl = XSX0 0 -1 1Xl+1 = Y1 1 0 10 1 1 01 0 0 00 1 0 10 1 1 00 0 1 10 0 1 01 0 1 10 0 0 10 0 0 00 0 0 00 0 1 00 0 1 10 0 0 10 0 0 1tl+1tlПример 2.A = Y - SXXl = XSX0 0 0 1Xl+1 = Y1 1 0 10 1 1 01 0 0 00 1 1 10 1 1 00 0 1 10 1 1 0+1 0 1 10 0 0 10 0 0 00 0 0 00 1 1 00 0 1 10 0 0 10 0 0 1tl+1tlВ этом случае  X, Y   X 1 , т.к. A  3, m   2  1 .

т.к. третий пользователь (mMn  3 ) загрузил две порции данных в первую и вторую позицию своего буфера (m  1, 2 ). Таким образом, в этом примере   X, Y   0 .Пример 3.A = Y - SXlX =XSX0 0 0 1Xl+1 = Y1 1 0 10 1 1 01 0 0 00 1 1 10 1 1 00 0 1 10 0 1 01 0 1 10 0 0 10 0 0 00 0 0 00 0 1 00 0 1 10 0 0 1tl0 0 0 1tl+1Здесь  X, Y   X \  X 1  X 1 : 1-й пользователь ( n  1 ) загрузил порцию в 3-юпозицию буфера ( m  3 ); 2-й пользователь ( n  2 ) получил порцию данных- 197 -непосредственно от сервера; 3-й пользователь ( n  3 ) загрузил порцию в 2-юпозицию буфера ( m  2 ); 4-й пользователь ( n  4 ) не загрузил ничего. Значениясоответствующих индикаторных функций в формуле (6.23) показаны втаблице 6.1. Из формулы (6.23) и таблицы 6.1 следует, что2 1 1 1 1s  X, Y   PXY1  PXY 2  PXY 3  PXY 4      .3 4 3 3 18Таблица 6.1. Значения индикаторных функций в формуле (6.23)n 1n2n3n4I  A  n,0   10100I   A  n, m   0  mM0001I   A  n, m   1 mM \01010Разработанныйметодпозволяетвычислитьматрицупереходныхвероятностей ц.м.

для расчета вероятности непрерывного просмотра видеопользователем в потоковой одноранговой сети. Необходимо отметить, чтовычисление матрицы переходных вероятностей ц.м. возможно только для сетейнебольшой размерности. Расчет переходных вероятностей в случае большойразмерности сети представляет собою отдельную задачу, которая не решалась вдиссертационной работе. Для сетей большой размерности предлагаетсяиспользовать приближенный метод, разработанный автором [8, 40] на основеподхода [155].

Вероятности p1  n, m  предлагается вычислять по (6.15), где p1  n, m   1  p1  n, m   , = LF;Q(n, m,  )   p1  n, m   1  p1  n,1  p1  n, M   p1  n, m  1  , =Gr.(6.24)В статьях [155, 257] предложена эвристическая формула для оценкисреднего времени  ожидания начала просмотра:M  n    p1  n, m  .m0(6.25)- 198 -Графики на рис.

6.6 и рис. 6.7 иллюстрируют оценку точности приближениядля сети с N  1000 пользователей, M  40 позиций для случая, когдапользователи постоянно присутствуют в сети, то есть     0 , на примерестратегии загрузки данных LF. Здесь сплошной линией показаны графики,полученные при имитационном моделировании, а пунктирной линией - графикидля Q *(n, m,  ) , вычисленной по приближенной формуле (6.24), и p *(n, m) ,вычисленной по (6.15) с учетом (6.24).Рис.

6.6. Вероятность p  n, m  наличия порции данных в буфере,оценка точности формулы (6.15) для N  1000 , M  40- 199 -Рис. 6.7. Вероятность Q  n, m,   загрузки порции данных в буфер,Итак,оценка точности формулы (6.24) для N  1000 , M  40для расчета вероятности V непрерывного воспроизведениявидеопотока рекомендуется пользоваться приближенной формулой (6.24) илирешать задачу средствами имитационного моделирования, а среднее время ожиданияначалапросмотраоцениватьспомощьюимитационногомоделирования.Эти рекомендации использованы далее при численном решении задачипоискаоптимальнойстратегиивыборапорцииданныхдлязагрузки,позволяющей максимизировать вероятность V и минимизировать время  .Решение было получено с помощью разработанного программного средства,моделирующего обмен данными между пользователями потоковой сети сучетом стратегии загрузки данных.

Известные из [29-31, 155, 169, 170, 257]результаты анализа основных используемых в потоковых сетях стратегий LF иGr для случая, когда пользователи постоянно присутствуют в сети, то есть    0 , показали, что для непрерывного воспроизведения видеопотокастратегия LF работает лучше стратегии Gr. Однако результаты анализа сети сподключением и отключением пользователей (   0 и   0 ) свидетельствуюто том, что стратегия LF является лучшей не всегда.

Например, когда во времярекламы,пользователивбольшомколичествепокидаютсетьилипереключаются на другой канал, т.е. при высоких  , с точки зрения- 200 -непрерывного воспроизведения видеопотока стратегия Gr работает лучшестратегии LF. Обратный эффект наблюдается при небольших же значениях  ,когда стратегия LF работает лучше стратегии Gr. Кроме того, проведенныйанализ для случая, когда пользователи постоянно присутствуют в сети, показал,что при стратегии LF пользователям приходится дольше ждать началапросмотра, чем при стратегии Gr, когда время ожидание начала просмотраневелико. Это объясняется тем, что при стратегии LF преимущество призагрузке отдается начальным, а при стратегии Gr - последним позициям буфера.Следовательно, нужно искать оптимальную стратегию заполнения буфера,которая будет сочетать преимущества обеих основных стратегий, т.е.

стратегиювыбора порции данных для загрузки, которая будет обеспечивать высокуювероятностьювероятности непрерывноговоспроизведенияприлюбыхзначенияхи небольшое время ожидания начала просмотра. Такаястратегия была построена в виде так называемой «смешанной стратегии»,основная идея которой заключается в разбиении буфера на две области точкойm0, , M и применении в каждой из областей буфера одной из основныхстратегий LF и Gr. Численный анализ для сети с N  1000 пользователей,M  40 позиций буфера, с учетом подключения и отключения пользователей (  0 и   0 ) был выполнен с помощью разработанного программногосредства, моделирующего обмен данными между пользователями потоковойсети с учетом стратегии загрузки данных. Для четырех возможных комбинацийосновных стратегий LF и Gr с учетом последовательности их применения былпроведен расчет основных показателей эффективности функционирования сети,при этом вероятность Vнепрерывного воспроизведения вычислялась поформуле (6.15), а среднее время  ожидания начала просмотра оценивалось спомощью имитационного моделирования.

Анализ показал преимуществосмешанной стратегии выбора порции данных для загрузки LF|Gr (рис. 6.8) с0 m Mдемаркационной точкой m  10 .- 201 -GrLF. . . m 1 m m 1 . . .0MДемаркационная точкаРис. 6.8. Смешанная стратегия LF|Gr0 m MПри такой комбинации основных стратегий сначала для позицийm0, ,10 буфера применяется стратегия LF, что позволяет быстрораспространить по сети редко встречающиеся порции данных, а затем дляостальныхпозицийбуфераm11,, 40применяетсястратегияGr,повышающая вероятность непрерывного просмотра. Для смешанной стратегииLF|Grполученоследующееутверждение, являющеесяследствиемиз0 m Mтеоремы 6.1.Следствие 6.1. Номер m  Z, x  n  , x  h   позиции буфера для загрузки порцииопределяется в соответствии со смешанной стратегией загрузкиLF|Gr0 m Mследующим образом.ЕслиM0  x  n   M1  x  h    иM   x  n1M0  x  h   0,то m  x  n  , x  h    min m : m ЕслииM   x  n0M   x  n0, m   ,M   x  n0M1  x  h   0,M1  x  h   m  1,M1  x  h   0,, m ., m  , M   ,тоm  x  n  , x  h    max m : m M   x  n0M1  x  h   m  1,, M .На рис.

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

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