Interval Characteristics of Group Poisson Models of Telecommunication Systems Trafic

Full Text

Появление сетей передачи данных с коммутацией пакетов показало, что пуассоновские модели потоков не являются адекватными, и потребовало разработки новых моделей, основанных на непуассоновских распределениях. Исследуются потоки с распределениями Вейбулла, Эрланга, Парето, гамма-распределениями и др. Все интервалы времени, представляемые данными распределениями вероятностей, по-прежнему считались взаимно независимыми. Это позволяло применить хорошо разработанный аппарат теории очередей для анализа сетей с пакетной коммутацией. Описание сложных коррелированных потоков в современных телекоммуникационных сетях часто производилось с использованием «фрактальных» процессов. Сотни работ посвящены анализу «самоподобного» трафика. Однако ощутимых практических результатов указанные исследования не дали. Недостаточная эффективность представления трафика моделями «самоподобных» процессов привела к созданию целого класса моделей потоков, управляемых цепью Маркова. Этапы развития указанных моделей представлены в обзоре [1]. В нашей стране они были названы МС-потоками, а в США эволюционировали от «разносторонних (versatile) потоков», через «N-потоки (потоки Ньютса) [2] до марковских входных потоков (MАP - Markovian Arival Process) и их обобщения - групповых марковских входных потоков (BMАP - Batch Markovian Arival Process) [6-13]. Стимулом к развитию BMАP-моделей явились их матричные представления, предложенные в работах М. Ньютса. Переход к матричным представлениям вероятностных характеристик BMАP-потоков позволил осуществлять описание их работы и открыл широкий простор для аналитических исследований. Однако определение характеристик входного потока заявок часто осуществлялось отдельно от характеристик обрабатывающей его системы. Вместе с тем такая характеристика, как время обработки пакета в телекоммуникационных системах, зависит не только от пропускной способности системы, но и тесно связана с размером пакета, который является одной из характеристик входного потока. Наиболее значительной работой в области анализа систем массового обслуживания (СМО) с подобными потоками, по-видимому, можно считать [3]. Одним из перспективных, на наш взгляд, направлений изучения пакетного трафика является разрабатываемый нами интервальный метод [4], позволяющий заменить анализ интервалов времени между соседними заявками и интервалов времени обработки заявок, анализом одной случайной величины - числом заявок, поступающих в течение последовательных интервалов времени обработки каждой из заявок. Показано, что дисперсия и корреляционные свойства указанной случайной величины при заданной загрузке полностью характеризуют средний размер очереди в СМО [4]. Для одноканальных СМО было получено соотношение (1), обобщающее известную формулу Хинчина - Поллачека для среднего значения очереди () q r и справедливое для любых стационарных потоков заявок при заданном коэффициенте загрузки : r 1 2 21 2 21 2 () [ (); ()] () () () . () m ii D Cov q m q mE - r+ r r r r= - = -r rr = - -r (1) Анализ числителя () mE r формулы (1) показывает, что среднее значение очереди для потоков любого вида зависит от двух составляющих: первая составляющая - это дисперсия () m D r числа заявок (пакетов) ( ), i m r поступающих в течение интервала времени обработки одной заявки, а вторая - это составляющая, обусловленная наличием корреляционных связей в указанном потоке. Корреляционные связи учитываются ковариацией 1 [ ( ); ( )] Cov q m ii rr - между значениями () i m r и значениями очереди 1 () i q - r на предыдущем интервале анализа. В частном случае для пуассоновского потока указанная составляющая равна нулю, а дисперсия () . m D r=r Тогда при постоянном времени обслуживания обобщенная формула (1) приобретает обычный вид: 2 21 () . () q r r= -r (2) Групповой неординарный пуассоновский поток Одной из разновидностей ВМАР-потоков является неординарный пуассоновский поток событий. В таком потоке выполняются свойства стационарности и отсутствия последействия, но не выполняется свойство ординарности. Рассмотрим пуассоновский поток независимых событий с параметром l. Каждое событие заключается в одновременном появлении в момент k t «пачки» из k m независимых случайно распределенных чисел заявок с распределением . kk P kf m= = Такой поток называют пуассоновским неординарным (групповым) потоком независимых событий, и он рассмотрен в [5]. Примем, что t - это интервал времени обработки одной заявки. Разделим достаточно большой промежуток времени Т, в течение которого действует поток указанных событий, на Nt таких последовательных интервалов. Пусть () i m t - число событий, произошедших в течение i-го интервала времени . t Тогда вероятности наступления на интервале t ровно n событий подчиняются закону Пуассона: () () ( ) . ! n in Pm n P e n -lt lt t= = lt= Каждому из событий сопутствует появление «пачки» с распределением вероятностей чисел заявок . k f Введем производящую функцию 0 () . k k k f z fz ∞ = = ∑ Поскольку все k m взаимно независимы и одинаково распределены, появлению на интервале t ровно () i m t заявок при условии, что на указанном интервале произошло n событий, соответствуют вероятность () n k f и производящая функция [ ( )] . n fz Производящая функция () () m Gz t числа заявок на интервале t есть 0 0 11 0 () () [ () ] [ () ] ( ) ( )[ ( )] () [ ( )] ! ( ( )) [ ]. ! n mn n n n n n fz fz fz n G z P fz e fz n fz ee e n ∞ t = ∞ -lt = ∞ -lt lt - lt - = = lt = lt = = lt = = ∑ ∑ ∑ Определим среднее число заявок на : t 1 0 1 1 11 1 1 () [ () ] () () () [ ()] ( ) ( ). m ii i z fz z Gz m m Pm z f ze f ∞ t = = lt - = ∂ t= t t = = ∂ = lt = lt ∑ Учитывая, что 1 00 1 1 () , k kk kk z d f f z kf k dz ∞∞ = = = = = = ∑∑ получим () , mk t = lt где k - среднее число заявок в «пачке». Определим второй начальный момент: 2 22 2 2 0 1 () () () () [ ()] m ii i z Gz m m Pm z ∞ t = = ∂ t = t t= = ∂ ∑ 11 1 11 1 2 1 1 2 2 22 [ () ] [ () ] () [ () ( ())] ( ) (). fz z fz z f ze f z fz e k k km lt - = lt - = = lt = = lt + lt = = lt + lt = lt + t Определим дисперсию () m D t числа заявок на интервалах : t 2 22 2 2 1 () () () ( ) ( ), m kk Dmm k Dk k t = t - t = lt = = lt + = r + ν (3) где () km r = lt = t - общий коэффициент загрузки; 2 2 () k k D k ν= - квадрат коэффициента вариации чисел заявок в пачках. Дисперсия () m D r линейно зависит от коэффициента загрузки . r Преобразуем формулу (1): 21 2 () () () , () m DJ q rr r r= - -r (4) где 1 12 () () ii qm Jr - r= + r называют ковариационным индексом дисперсии, а 1 1 [ ( ); ( )] () () ii ii qm m Cov q m r D - - rr r= r - нормированная ковариационная функция. В дальнейшем с помощью имитационного моделирования мы покажем, что при малых коэффициентах загрузки значение индекса дисперсии для потоков с пуассоновским распределением чисел заявок в пачках мало отличается от единицы и корреляционная составляющая практически отсутствует. При этом формула (1) упрощается () mE r= () m DE r=r и 21 2 21 2 () () , () () m D E q r rr r r= - = - -r -r (5) где 2 1 ( ). k Ek = +ν Дисперсия () m D r в (5) линейно зависит от коэффициента загрузки , r а ее значе ние пропорционально среднему числу заявок в пачке. Рассмотрим частные случаи. 1. Ординарный пуассоновский поток: 1, i k = 1, k = 2 0, k ν= 1 E = - при этом справедлива формула (2). 2. Все пачки имеют одинаковое число заявок: , kk = 2 0, k ν= . Ek = 3. Числа заявок в пачках распределены по закону Пуассона: , kk = 2 1 , k k ν= 1. Ek = + 4. Числа заявок в пачках целые и распределены по экспоненциальному закону: , kk = 2 1, k ν= 2 . Ek = Групповые неординарные пуассоновские потоки с зависимым числом заявок в пакете Мы рассмотрели групповые пуассоновские потоки, в которых случайные, взаимно независимые числа заявок k m в пачках не зависят также и от интервалов времени между соседними событиями (соседними пачками). Рассмотрим теперь поток, в котором указанные числа заявок в пачках пропорциональны длительностям интервалов времени 1 kk k tt + ϑ= - между соседними пачками . kk k m = lϑ Очевидно, что .k k m= Поскольку ин-тервалы k ϑ между соседними пачками взаимно независимы и имеют экспоненциальное распределение, числа заявок k m в пачках также взаимно независимы и имеют экспоненциальное распределение со средним значением , k параметрами 2 1 k ν= и 2 . Ek = Однако, в отличие от рассмотренного выше примера, числа заявок в каждой из пачек пропорциональны длительностям соответствующих интервалов , k ϑ и очередь, возникающая с появлением каждой пачки, успевает завершиться до появления следующей пачки заявок, причем даже при коэффициенте загрузки, равном единице. Покажем это, принимая во внимание, что k m t= kk kltϑ = rϑ - длительность времени обработки всех заявок на интервале . k ϑ Обозначим через kk k ∆ = ϑ - rϑ = 1 () k ϑ -r запас по времени обработки всех заявок на указанном интервале. Относительный запас по времени 1 k k ∆ = -r ϑ остается постоянным на всех интервалах и зависит только от коэффициента загрузки. При максимальной загрузке 1 r= запас равен нулю, но обработка всех заявок в очереди успевает завершиться до появления очередной пачки заявок (это хорошо иллюстрируют рисунки 7, 8 в разделе с результатами имитационного моделирования). Даже в случае максимальной загрузки, когда на интервале, предшествующем интервалу появления пачки, происходит обработка последней заявки, очередь заявок 1 0 () , i q - r= и, следовательно, 1 0 () () . ii qm - r r= Учитывая, что 1 [ ( ); ( )] ii Cov q m - r r= 1 ()[ () ], ii qm - r r -r преобразуем формулу (1): 1 1 1 2 1 2 1 22 () ( )( ) () [ ( ); ( )] () () () () () , m ii m ii D q Cov q m D qm q - - r r -r = + r -r + r r- = r r -r = + r r - rr- (6) 11 22 2 1 2 () () () () , () () . m D E q qk r r -r r-r -r r= - = r -r r = r- Максимальное значение дроби в полученном выражении не превышает 0.125, поэтому даже при небольших значениях чисел заявок в пачках характеристика () q r практически линейна, как это будет видно из рисунка 9 в разделе имитаци- онного моделирования. Равенство нулю математического ожидания 1 0 () () ii qm - r r= свидетельствует, что для данного потока взаимная ковариация 1 [ ( ); i Cov q - r ( )] i m r не равна нулю и отрицательна: 1 1 [ ( ); ( )] () () () (). ii ii Cov q m qm q q - - r r= = r r- rr=- rr Подставляя значения () q r из (6), получим: 1 2 22 11 1 2 2 [ ( ); ( )] () ( ). ii Cov q m kk k - r r= r -r -r =-r + =-r - (7) При достаточно больших значениях чисел заявок в пачках ковариация имеет практически квадратичную зависимость от коэффициента загрузки. Соотношение (7) позволяет определить значения числителя в первой дроби (1), обозначенного нами в разделе моделирования на рисунке 9 через r ( ): mE 21 1 2 ( ) ( )( ). mE k k r r = r -r + (8) Указанная зависимость имеет максимум при значениях 05 , r≈ - см. рисунок 9. Именно наличие члена 1 ( ), -r сокращающегося при подстановке в формулу (1), приводит для данного потока к практически линейной зависимости среднего размера очереди от коэффициента загрузки, показанной в (6). Групповые гиперпуассоновские потоки Сумму независимых одновременно параллельно протекающих рассмотренных выше потоков назовем групповым гиперпуассоновским потоком. В отличие от большинства потоков, управляемых цепью Маркова, протекание всех суммируемых потоков происходит не последовательно, а непрерывно, параллельно во времени. При получении гиперпуассоновского потока происходит суммирование нескольких пуассоновских потоков событий, каждое из которых представляет пачку одновременно поступающих заявок. Однако суммарный поток событий (появлений пачек) является пуассоновским. Следовательно, суммарный поток заявок также является групповым пуассоновским потоком. Линейная зависимость числителя в формуле (5) от коэффициента загрузки при малых загрузках существенно упрощает определение средних размеров очередей суммарного гиперпуассоновского потока при мультиплексировании взаимно независимых групповых пуассоновских потоков: 11 ;. MM j jj jj EE ΣΣ = = Σ r r= r = r ∑∑ С точки зрения средних значений образуемых очередей полученный суммарный гиперпуассоновский поток эквивалентен соответствующему групповому пуассоновскому потоку, однако характеристики их мгновенных значений могут существенно отличаться. В дальнейшем мы покажем, что соответствующим выбором характеристик суммируемых потоков можно получить суммарный гиперпуассоновский поток с характеристиками, весьма близкими к реальному моде- лируемому потоку. Имитационное моделирование В этом разделе подтвердим полученные выводы результатами имитационного моделирования c помощью разработанной нами программной системы АМС [4]. Система позволяет получить и исследовать основные интервальные характеристики потоков, представленных в формате .txt в виде последовательности моментов поступления заявок. Групповой поток с пуассоновским распре-делением вероятностей независимых чисел заявок в пачке. Былисгенерированы два групповых пуассоновских потока с одинаковыми значениями интенсивностей 1 l= заявка в секунду. Первый поток содержал пачки заявок, имеющих пуассоновское распределение чисел заявок в пачке, со средним значением 1 10 k = заявок в пачке и интенсивностью поступления пачек 1 01 , l= пачка в секунду. 1 1 1. k l= l = Второй поток имел следующие характеристики: 2 22 11 ;, kk l=l = = = то есть каждая пачка состояла точно из одной заявки и, следовательно, второй поток был обычным пуассоновским потоком с интенсивностью, равной . l На рисунке 1 совмещены графики чисел заявок на интервалах обслуживания для первого и второго потоков при коэффициенте загрузки 01 ,. r= Пуассоновский поток весьма равномерен и в основном имеет не более одной заявки, в то время как групповой пачечный поток на аналогичном интервале имеет свыше 10 заявок, числа которых распределены по закону Пуассона. Пачечный характер группового потока приводит к возникновению больших очередей при его обслуживании. На рисунке 2 показан график изменения очереди при обслуживании группового пуассоновского потока в однолинейной СМО при коэффициенте загрузки 05 ,. r= Максимальные значения чисел заявок в очередях превышают 60, что является результатом высокой пачечности потока. Наиболее значительной интервальной характеристикой рассматриваемых потоков является зависимость дисперсии () m D r чисел заявок на интервалах обслуживания от коэффициента загрузки. Нами было показано, что указанная за- висимость носит линейный характер и для пуассоновского распределения вероятностей чисел заявок в пачках определяется соотношением (3) При заданных параметрах группового потока: 22 2 1 0 1 1 11 ,; ( ) , () k kk D Ek kk ν = = = = +ν = в то время как для обычного пуассоновского потока 1. E = Зависимости дисперсии () m D r чисел заявок на интервалах обслуживания от коэффициента загрузки, полученные в результате имитационного моделирования обоих потоков, отражены на рисунке 3. Верхний график соответствует групповому пуассоновскому потоку с углом наклона 11. E = Нижний график соответствует обычному пуассоновскому потоку с углом наклона 1. E = Средний график соответствует потоку, полученному в результате суммирования указанных потоков. Видно, что все зависимости строго линейны. На рисунке 4 показаны зависимости средних размеров очередей () q r от коэффициента за- грузки, полученные в результате имитационного моделирования обоих потоков. Верхний график - групповой поток, нижний график - пуассоновский поток. В верхнем углу показано значение размера очереди для группового потока при коэффициенте загрузки 05 ,, r= полученное непосредственно с графика, 5 186 () , . q r= Теоретическое значение, определенное по формуле (4), 5 25 () , . q r= Незначительная разница объясняется погрешностью процесса имитационного моделирования и влиянием корреляционных связей. Очереди при малых загрузках. Был сгенерирован групповой пуассоновский поток со значением интенсивности 100 l= заявок в секунду. Поток содержал пачки заявок, имеющих пуассоновское распределение чисел заявок в пачке, со средним значением 1 100 k = заявок в пачке и интенсивностью поступления пачек 1 1 l= пачка в с, 1 1 100. k l= l = На рисунке 5 показаны изменение значений числителя () () m DJ rr в формуле (4) (сплошная линия) и изменение дисперсии () m D r (точечная линия) для коэффициентов загрузки , r не превышающих 0,5. На участках, где линии совпадают, индекс дисперсии равен единице, что означает малое влияние корреляционной составляющей. Среднее значение очереди определяется в основном дисперсией. На рисунке 6 показаны изменение средних значений размера очереди и изменение дисперсии () m D r (прямая линия) для коэффициентов загрузки , r не превышающих 0,5. На указанном участке разница составляет примерно 30 %. Ис- следуем этот параметр более подробно: 21 2 () () () . () m E DqE rr ∆r= r- r=r - - -r Точка пересечения линий соответствует за- грузке 0 1 05 2 + r= ≈ ,. E E Максимальное значение разности соответствует загрузке 1 0 25 22 1 ,. () m E E + r= ≈ - Максимальная разность 83 () , m ∆r ≈ превышает значение очереди () m q r также примерно на 30 %. Групповой поток с экспоненциальным распределением вероятностей чисел заявок в пачках, зависимых от интервалов времени между пачками Моделирование проводилось в сравнении с групповым потоком, имеющим пуассоновское распределение вероятностей независимых заявок в пачках. Были сгенерированы два потока пачек с одинаковыми интенсивностями 1 l= и экспоненциальным распределением вероятностей интервалов между соседними пачками. Числа заявок в пачках первого потока имеют экспоненциальное распределение вероятностей со средним значением 1 100 = k и пропорциональны длительностям интервалов между пачками. Числа заявок в пачках второго потока распределены по закону Пуассона со средним числом заявок в пачке 2 200. k = Это позволило для обоих потоков сделать одинаковыми дисперсии чисел заявок на интервалах обслуживания. Для каждого из потоков было сгенерировано по 105 заявок. На рисунках 7, 8 показаны графики изменения очередей при коэффициенте загрузки 09 , r= для первого и второго потоков соответственно. Из рисунка 7 видно, что очереди, возникающие при появлении пачек заявок, не пересекаются во времени и перед появлением каждой очередной пачки очередь отсутствует. Для второго потока, показанного на рисунке 8, наоборот, очереди пересекаются и максимальные значения очередей намного превышают максимальные значения первого потока. На рисунке 9 для сравнения совмещены некоторые характеристики рассматриваемых потоков. Зависимости дисперсий () m D r для обоих потоков совмещены и представлены верхней (сплошной) прямой линией. Зависимость очереди () q r для первого потока также линейна, представлена нижней (точечной) прямой линией, имеющей угол наклона, вдвое меньший линии дисперсии, что полностью соответствует (6). Для обоих потоков совмещены (верхняя сплошная прямая). Зависимость очереди для пер вого потока (точечная прямая); зависимость очереди () q r для второго потока (точечная кривая); зависимость () mE r числителя в формуле (1) для первого потока (дуга, сплошная линия). Аппроксимация средних значений очередей реального трафика Анализ двух рассмотренных выше потоков показал, что они имеют принципиально различные характеристики зависимостей очередей от коэффициента загрузки. Если характеристика потока с зависимыми заявками строго линейна, то характеристика потока с независимыми числами заявок в пачках нелинейно возрастает при больших загрузках. Эти различия можно использовать, создав групповой гиперпуассоновский поток из двух таких потоков. Соответствующим выбором параметров этого потока можно получить зависимости средних размеров очередей () q r от коэффициента загрузки, весьма близкие к соответствующим характеристикам реального трафика. На рисунке 10 показаны зависимости средних размеров очередей () q r от коэффициента загрузки для реального видеотрафика и для группового потока, имеющего пуассоновское распределение чисел заявок в пачках со значением 420. k = Наблюдаем удовлетворительное совпадение. Однако причины возникновения очередей в обоих случаях существенно различны. В случае видео-трафика основной вклад в образование очередей вносят корреляционные связи. Во втором случае, наоборот, основной вклад вносит дисперсия при незначительном влиянии корреляционных связей. Сказанное хорошо иллюстрируется представленными на рисунке 11 зависимостями дисперсий обоих потоков от коэффициента загрузки. Размеры дисперсии чисел заявок группового пуассоновского потока при одинаковых загрузках значительно превышают соответствуюшие значения дисперсии потока реального видеотрафика. Рисунок 1. Числа заявок на интервалах обслуживания для первого и второго потоков при коэффициенте загрузки 01 Рисунок 2. Очереди, возникающие при обслуживании группового пуассоновского потока в однолинейной СМО при коэффициенте загрузки 05 Рисунок 3. Зависимости дисперсии ()mDrчисел заявок на интервалах обслуживания от коэффициента загрузки Рисунок 4. Зависимости средних размеров очередей ()qr от коэффициента загрузки Рисунок 5. Изменение значений числителя () ()mDJrr и изменение значений дисперсии ()mD Рисунок 6. Изменение средних значений размера очереди и дисперсии для коэффициентов загрузки ,r не превышающих 0,5 Рисунок 7. Изменение размеров очередей во времени для первого потока Рисунок 8. Изменение размеров очередей во времени для второго потока Рисунок 9. Зависимости дисперсий ()mD Рисунок 10. Зависимости средних размеров очередей ()qr для реального видеотрафика (точечная линия) и для группового потока (сплошная линия) Рисунок 11. Зависимости дисперсий для реального видеотрафика (точечная линия) и для группового потока (сплошная линия) Выводы 1. Незначительное влияние корреляционных связей в групповом пуассоновском потоке делает его привлекательным в качестве модели телекоммуникационного трафика. 2. При суммировании нескольких групповых пуассоновских потоков результирующий поток также является групповым пуассоновским потоком. 3. Предложенный в работе групповой пуассоновский поток с зависимым числом заявок в пачках имеет линейную характеристику среднего размера очереди ( ).qr 4. В групповом потоке с независимым числом заявок в пачках, распредленным по закону Пуассона, ковариационная составляющая числителя в обобщенной формуле Хинчина - Поллачека практически отсутствует и средний размер очереди определяется значениями дисперсии ( ),mDr линейно зависящими от коэффициента загрузки. 5. Принципиальное различие характеристик указанных выше потоков позволяет при их мультиплексировании получить суммарную зависимость, хорошо аппроксимирующую характеристику реального телекоммуникационного трафика.

About the authors

B. Ya Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psuti.ru
Samara, Russian Federation

References

Supplementary files