CONDITIONAL AVERAGE VALUE OF QUEUES IN QUEUE SYSTEMS WITH PACKET FLOWS OF DEMANDS

Full Text

Введение Любой пакетный трафик мультисервисных сетей связи является продуктом компьютерной обработки, выполняемой процессором при решении задач приложений. Решение каждой такой задачи состоит из трех последовательных этапов: получение исходных данных, процесс обработки и процесс выдачи результатов, причем, трафик образуется именно на третьем этапе. Это и обуславливает его пачечный характер. Пакеты группируются в «пачки» в одних промежутках времени и практически отсутствуют - в других промежутках [1]. Случайный процесс поступления заявок (пакетов) в систему характеризуется законом распределения, устанавливающим связь между значениями случайной величины и вероятностями появления указанных значений. В большинстве случаев, такой поток характеризуется функцией распределения временных интервалов между соседними заявками. Имеется также множество работ, в которых потоки заявок характеризуются функцией распределения числа заявок за условную единицу времени. В предыдущих работах [3-6] в качестве указанной единицы времени, рассматривался постоянный интервал времени обработки одной заявки. Было показано, что дисперсия и корреляционные свойства числа заявок, поступающих за интервал обработки, оказывают определяющее влияние на средний размер очереди. Для одноприборной системы массового обслуживания (СМО) на основании рекуррентного соотношения (1), где и - числа заявок, поступивших в течение i-го интервала и размер очереди, образовавшейся на указанном интервале, соответственно, (1) Была установлена связь между средними размерами очередей и параметром загрузки вида , (2) где ; - дисперсия чисел заявок на интервалах обслуживания , а также - второй взаимный центральный момент указанных последовательностей, называемый корреляционным моментом или ковариацией. Он определяется как математическое ожидание произведений центрированных значений элементов и . Соотношение (2) обобщает формулу Хинчина-Поллячека [2; 7-10] и справедливо для любых стационарных и ординарных потоков заявок при постоянном времени обслуживания . Для пуассоновского потока и формула (2) приобретает обычный вид: Применение указанной формулы для расчета очередей пачечных потоков приводит к погрешностям, превышающим сотни процентов. На рис. 1 представлены числа пакетов поступающих в течение интервала (черные линии) и пуассоновского потока (серые линии), при одинаковой загрузке . Рис. 1. Числа пакетов видеотрафика, поступающих в течение интервала (черные линии) и пуассоновского потока (серые линии) Видеотрафик, по сравнению с пуассоновским, обладает существенной неравномерностью и носит пачечный характер, что приводит к возникновению больших очередей. Рис. 2. График изменения мгновенных значений размеров очередей для видеотрафика На рис. 2 показан график изменения размеров очередей для рассмотренного выше видеотрафика. Пиковые значения размеров очередей достигают 800 заявок (пакетов), в то время, как для пуассоновского потока они не превышают пяти заявок. На рис. 3 показаны зависимости средних значений размеров очередей от изменения коэффициента загрузки , для рассматриваемого видеотрафика и пуассоновского потока. Размеры очередей для пуассоновского потока несравнимо меньше, чем для потока видеотрафика. Поэтому для анализа видеотрафика следует применять обобщенную формулу (2). Рис. 3. Зависимости средних значений размеров очередей от изменения коэффициента загрузки Очереди при малых загрузках Размеры очередей в коммутаторах мультисервисных сетей определяют объемы буферной памяти, требуемой для их хранения, и размеры задержек пакетов в процессе их обработки. Для обеспечения допустимых значений указанных параметров, необходимо соответствующим образом уменьшать загрузку. Поэтому, особый интерес представляет анализ характеристик трафика при малых значениях коэффициента загрузки . На рис. 4 для рассмотренного выше потока видеотрафика, показан график изменения функции при значениях коэффициента загрузки, не превышающих Из графика видно, что при малых загрузках, можно выделить три интервала изменения характеристики. На начальном участке, до некоторого значения , значения равны нулю. На промежуточном участке происходит нелинейное возрастание характеристики. Рис. 4. График изменения для потока видеотрафика при Далее характеристика изменяется почти линейно. Появление начального участка характеристики объясняется тем, что на этом интервале изменения коэффициента загрузки, интервал времени обработки всегда остается меньше, чем минимальный промежуток времени между двумя соседними заявками, и в интервал не может попасть более одной заявки. Дисперсия при этом, определяется как Подставляя это значение в (2), получим , что и следовало ожидать. Введем понятие условного среднего значения размера очереди , которое представляет среднее значение очереди, на каждом из интервалов , при условии активной загрузки процессора, и не учитывает наличия интервалов простоя. Из графика рис. 4 следует, что коэффициент загрузки приблизительно соответствует среднему значению очереди . При этом заявки, что в 33 раза превышает среднее значение очереди . Таким образом, среднее значение не отражает реальное состояние очередей и для характеристики размеров очередей следует ориентироваться на условные средние значения чисел заявок . Аппроксимация Для получения значений коэффициента загрузки , обеспечивающих допустимые размеры очередей, особый интерес представляет функция , обратная представленной на рис. 4. Предлагается аппроксимировать зависимость функцией . (3) где - максимально допустимое значение среднего размера очереди; - максимально допустимое значение коэффициента загрузки; , и - постоянные коэффициенты, определяемые в процессе аппроксимации. Зависимость , показанная на рис. 4, представляет обратную функцию при ; при , с помощью, которой и производится непосредственная аппроксимация. Предлагается следующий алгоритм аппроксимации. 1. Устанавливается предельное значение изменения коэффициента загрузки . 2. Определяется шаг дискретизации по , равный . 3. Путем перебора, находится значение минимального интервала между двумя соседними заявками . 4. Определяется значение , где - округление до ближайшего целого числа, начиная с нуля. 5. По имеющейся характеристике определяется предельное значение размера очереди . 6. Определяется предельное значение коэффициента . 7. Определяется предельное значение коэффициента . 8. Определяется шаг дискретизации по , и по , равные и , соответственно. 9. Начальное состояние: . 10. Производится приращение . 11. Производится приращение . 12. По формуле (2) определяется значение и сравнивается с текущим значением . 13. Если , то приращение вычитается из . 14. Производится приращение . 15. По формуле (2) определяется значение и сравнивается с текущим значением . 16. Если , то приращение вычитается из . 17. Если в обоих пунктах 13 и 16 вычитания не произошло, то пункты 11-16 повторяются, пока, хотя бы в одном из пунктов 13 или 16 произойдет вычитание. 18. Пункты, 10-17 повторяются, пока значение достигнет значения . 19. Окончательные значения коэффициентов и являются искомыми для уравнения аппроксимации (3). Коэффициент может иметь отрицательное значение, в то время как коэффициент всегда положителен. Следует заметить, что коэффициент определяется сразу и не меняется, в процессе аппроксимации . Для рассмотренного выше видеотрафика были получены следующие значения параметров аппроксимации: = 0,025; = 0,0024; = 0,0019. Интенсивность трафика . Задержки в очередях Учитывая, что , где - допустимое среднее время задержки в очереди, получим , где - максимально допустимое значение коэффициента загрузки, обеспечивающее допустимое среднее время задержки в очереди . Полагая допустимое среднее время задержки в очередях коммутаторов , для рассмотренного выше видеотрафика получим максимально допустимое значение коэффициента загрузки . Максимально допустимое значение среднего размера очереди При этом условное среднее значение размера очереди пакета, а средне-пиковое значение, превышающее его в два раза, составляет 39,6 пакетов. Следовательно, при выборе размеров буферной памяти, как мы уже показали, необходимо ориентироваться на условные средние значения размеров очередей . При этом размер памяти, требуемой для буферизации очереди, следует выбирать с двойным запасом, поскольку средне-пиковые значения очередей почти вдвое превышают условные средние значения. Для каждого конкретного кодека типа полоса пропускания определяется соотношением , где - длина полезной части информации для кадра трафика. В результате получим . (4) Полагая длину полезной части информации для кадра трафика , определим полосу пропускания для рассматриваемого видеокодека: . В этом случае пропускная способность порта коммутатора, к которому подключается пользователь услуги, должна быть не менее .

About the authors

Boris Yakovlevich Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psati.ru

References

Supplementary files