Моделирование вс на основе систем и сетей массового обслуживания. Понятие о системах массового обслуживания (СМО) Структура обслуживающей системы
Во многих областях экономики, финансов, производства и быта важную роль играют системы массо-вого обслуживания (СМО), т.е. такие системы, в которых, с одной стороны, возникают массовые запросы (требования) на выполнение каких-либо услуг, а с другой стороны, происходит удовлетворение этих запросов.
В качествепримеров СМО в финансово-экономи-ческой сфере можно привести системы, представляющие собой: банки различных типов, страховые организа-ции, налоговые инспекции, ау-диторские службы, различные системы связи (в том числе те-лефонные станции), погрузочно-разгрузочные комплексы (товарные станции), автозаправочные станции, различные предприятия и организации сферы обслуживания (магазины, предприятия массового питания, справочные бюро, парикмахерские, билетные кассы, пункты по обмену валюты, ремонтные мастерские, больницы).
Такие сис-темы как компьютерные сети, системы сбора, хранения и обра-ботки информации, транспортные системы, автоматизирован-ные производственные участки, поточные линии также могут рассматриваться как своеобразные СМО.
В торговле выполняется множество операций в процессе движе-ния товарной массы из сферы производства в сферу потребления. Такими операциями являются: погрузка и выгрузка товаров, пере-возка, упаковка, фасовка, хранение, выкладка, продажа и т. д. Для торговой деятельности характерны массовое поступление товаров, денег, массовое обслу-живание покупателей и т. п., а также выполнение соответствующих операций, которые носят случайный характер. Все это создает не-равномерность в работе торговых организаций и предприятий, порождает недогрузки, простои и перегрузки. Много времени отни-мают очереди, например, у покупателей в магазинах, водителей ав-томашин на товарных базах, ожидающих разгрузки или погрузки.
В связи с этим возникают задачи анализа работы, например тор-гового отдела, торгового предприятия или секции, для оценки их деятельности, выявления недостатков, резервов и принятия в конеч-ном итоге мер, направленных на увеличение ее эффективности. Кроме того, возникают задачи, связанные с созданием и внедре-нием более экономичных способов выполнения операций в пределах секции, отдела, торгового предприятия, овощной базы, управления торговли и т. п. Следовательно, в организа-ции торговли методы теории массового обслуживания позволяют определить оптимальное количество торговых точек данного профиля, численность про-давцов, частоту завоза товаров и другие параметры.
Другим ха-рактерным примером систем массового обслуживания могут служить склады или базы снабженческо-сбытовых организа-ций, и задача теории массового обслуживания сводится к тому, чтобы установить оптимальное соотношение между числом по-ступающих на базу требований на обслуживание и числом об-служивающих устройств, при котором суммарные расходы на обслуживание и убытки от простоя транспорта были бы мини-мальными. Теория массового обслуживания может найти при-менение и при расчете площади складских помещений, при этом складская площадь рассматривается как обслуживающее устройство, а прибытие транспортных средств под выгрузку - как требование.
Основные характеристики СМО
СМО включаетследующие элементы : источник требований, входящий поток требований, очередь, обслуживающее устройство (канал обслуживания), выходящий поток требований (обслуженных заявок).
Каждая СМО предназначена для обслуживания (выполнения) некоторого потока заявок (требований), поступающих на вход системы, в основном, не регулярно, а в случайные моменты времени. Обслуживание заявок также длится не постоянное, заранее известное время, а случайное время, которое зависит от многих случайных причин. После обслуживания заявки канал освобожден и готов к приему следующей заявки.
Случайный характер потока заявок и времени их обслуживания приводит к не-равномерной загруженности СМО: в некоторые промежутки времени на входе СМО могут скапливаться необслуженные заявки, что приводит к перегрузке СМО, в некоторые же дру-гие интервалы времени при свободных каналах на входе CMО заявок не будет, что приводит к недогрузке СМО, т.е. к про-стаиванию ее каналов. Заявки, скапливающиеся на входе СМО, либо "становятся" в очередь, либо по какой-то причине невоз-можности дальнейшего пребывания в очереди покидают СМО необслуженными.
Схема СМО изображена на рисунке 5.1.
Рисунок 5.1 - Схема системы массового обслуживания
Каждая СМО включает в свою структуру некоторое число обслуживающих устройств, которые называют каналами обслуживания . Роль каналов могут играть различные приборы, лица, выполняющие те или иные операции (кассиры, операторы, продавцы), линии связи, автомашины и т.д.
Каждая СМО в зависимости от своих параметров: характера потока заявок, числа каналов обслуживания и их производи-тельности, а также от правил организации работы обладает определенной эффективностью функционирования (пропускной способностью), позволяющей ей более или менее успешно справляться с потоком заявок.
СМО явля-ется предметом изучения теории массового обслуживания .
Цель теории массового обслуживания — выработка рекомен-даций по рациональному построению СМО, рациональной ор-ганизации их работы и регулированию потока заявок для обес-печения высокой эффективности функционирования СМО.
Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффек-тивности функционирования СМО от ее организации (пара-метров).
В качестве характеристик эффективности функционирова-ния СМО можно выбрать три основные группы (обычно средних) показателей:
1. Показатели эффективности использования СМО:
1.1. Абсолютная пропускная способность СМО - среднее число заявок, которое сможет обслужить СМО в единицу времени.
1.2. Относительная пропускная способность СМО - от-ношение среднего числа заявок, обслуживаемых СМО в единицу времени, к среднему числу посту-пивших заявок за это же время.
1.3. Средняя продолжительность периода занятости СМО.
1.4. Коэффициент использования СМО — средняя доля времени, в течение которого СМО занята обслужи-ванием заявок.
2. Показатели качества обслуживания заявок :
2.1. Среднее время ожидания заявки в очереди.
2.2. Среднее время пребывания заявки в СМО.
2.3. Вероятность отказа заявке в обслуживании без ожи-дания.
2.4. Вероятность того, что поступившая заявка немедлен-но будет принята к обслуживанию.
2.5. Закон распределения времени ожидания заявки в очереди.
2.6. Закон распределения времени пребывания заявки в СМО.
2.7. Среднее число заявок, находящихся в очереди.
2.8. Среднее число заявок, находящихся в СМО, и т.п.
3. Показатели эффективности функционирования пары "СМО — потребитель" , где под "потребителем" понимают всю совокупность заявок или некий их источник (например, средний доход, при-носимый СМО в единицу времени, и т.п.).
Случайный характер потока заявок и длительности их об-служивания порождает в СМО случайный процесс . Поскольку моменты времени T i и интервалы времени поступле-ния заявок T , продолжительность операций обслуживания Т обс , про-стоя в очереди T оч , длина очереди l оч — случайные величины, то характеристики состояния систем массового обслуживания носят вероятностный характер. Поэтому для решения задач теории массового обслужива-ния необходимо этот случайный процесс изучить, т.е. постро-ить и проанализировать его математическую модель.
Математическое изучение функционирования СМО значи-тельно упрощается, если протекающий в ней случайный про-цесс является марковским . Чтобы случайный процесс был марковским, необходимо и достаточно, чтобы все потоки событий, под воз-действием которых происходят переходы системы из состояния в состояние, были (простейшими) пуассоновскими .
Простейший поток обладает тремя основными свойствами : ординарности, стационарности и отсутствия последействия.
Ординарность потока означает практическую невозмож-ность одновременного поступления 2-х и более требований. На-пример, достаточно малой является вероятность того, что в магазине самообслуживания одно-временно выйдут из строя несколько кассовых аппаратов.
Стационарным называется поток, для которого математиче-ское ожидание числа требований, поступающих в систему в едини-цу времени (обозначим λ ), не меняется во времени. Таким образом, вероятность поступления в систему определенного количества тре-бований в течение заданного промежутка времени ?T зависит от его величины и не зависит от начала его отсчета на оси времени.
Отсутствие последействия означает, что число требова-ний, поступивших в систему до момента T , не определяет того, сколько требований поступит в систему за время (T + ?T) . Например, если в кассовом аппарате в данный момент произо-шел обрыв кассовой ленты и он устранен кассиром, то это не влияет на воз-можность нового обрыва на данной кассе в следующий момент и тем более на вероятность возникновения обрыва на других кассовых аппаратах.
Для простейшего потока частота поступления требований в систему подчиняется закону Пуассона , т. е. вероятность по-ступления за время T ровно k требований задается формулой
где λ — интенсивность потока заявок , т. е. среднее число заявок, поступающих в СМО в единицу времени,
где τ — среднее значение интервала времени между двумя со-седними заявками.
Для такого потока заявок время между двумя соседними заяв-ками распределено экспоненциально с плотностью вероятности
Случайное время ожидания в очереди начала обслуживания то-же можно считать распределенным экспоненциально:
где ν — интенсивность движения очереди , т. е. среднее число зая-вок, приходящих на обслуживание в единицу времени,
где Т оч - среднее значение времени ожидания в очереди.
Выходной поток заявок связан с потоком обслуживания в кана-ле, где длительность обслуживания Т обс является случайной величи-ной и подчиняется во многих случаях показательному закону рас-пределения с плотностью
где μ — интенсивность потока обслуживания , т. е. среднее число заявок, обслуживаемых в единицу времени,
Важной характеристикой СМО, объединяющей показатели λ и μ , является интенсивность нагрузки, которая показывает степень согласования указанных потоков зая-вок:
Перечисленные показатели k, τ, λ, l оч, Т оч, ν, Т обс, μ, ρ, Р k являются наиболее общими для СМО.
Сеть массового обслуживания (СеМО) - сеть, которая производит обслуживание поступающих в неё требований. Обслуживание требований в СМО производится обслуживающими приборами. Классическая СМО содержит от одного до бесконечного числа приборов. В зависимости от наличия возможности ожидания поступающими требованиями начала обслуживания СМО подразделяются на:истемы с потерями, в которых требования, не нашедшие в момент поступления ни одного свободного прибора, теряются;истемы с ожиданием, в которых имеется накопитель бесконечной ёмкости для буферизации поступивших требований, при этом ожидающие требования образуют очередь;истемы с накопителем конечной ёмкости (ожиданием и ограничениями), в которых длина очереди не может превышать ёмкости накопителя; при этом требование, поступающее в переполненную СМО (отсутствуют свободные места для ожидания), теряется.
Каждая СМО предназначена для обслуживания (выполнения) некоторого потока заявок (или требований), поступающих на вход системы большей частью не регулярно, а в случайные моменты времени. Обслуживание заявок, в общем случае, также длится не постоянное, заранее известное, а случайное время. После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока и времени их обслуживания приводит к неравномерной загруженности СМО: в некоторые промежутки времени на входе СМО могут скапливаться необслуженные заявки (они либо становятся в очередь, либо покидают СМО необслуженными), в другие же периоды при свободных каналах на входе СМО заявок не будет, что приводит к недогрузке СМО, т.е. к простаиванию каналов.
Таким образом, во всякой СМО можно выделить следующие основные элементы:
) входящий поток заявок;
) очередь;
) каналы обслуживания;
) выходящий поток обслуженных заявок.
Каждая СМО в зависимости от своих параметров: характера потока заявок, числа каналов обслуживания и их производительности, а также от правил организации работы, обладает определенной эффективностью функционирования (пропускной способностью), позволяющей ей более или менее успешно справляться с потоком заявок.
Предметом изучения теории массового обслуживания являются СМО.
Цель теории массового обслуживания - выработка рекомендаций по рациональному построению СМО, рациональной организации их работы и регулированию потока заявок для обеспечения высокой эффективности функционирования СМО.
Для достижения этой цели ставятся задачи теории массового обслуживания, состоящие в установлении зависимостей эффективности функционирования СМО от ее организации (параметров): характера потока заявок, числа каналов и их производительности и правил работы СМО.
Случайный характер потока заявок и длительности их обслуживания порождает в СМО случайный процесс.
Определение: Случайным процессом (или случайной функцией) называется соответствие, при котором каждому значению аргумента (в данном случае - моменту из промежутка времени проводимого опыта) ставится в соответствие случайная величина (в данном случае - состояние СМО). массовое обслуживание
1. ИССЛЕДОВАНИЕ ОСОБЕННОСТЕЙ МУЛЬТИМЕДИЙНОГО ВИДЕОТРАФИКА ПРИ ЕГО ПЕРЕДАЧЕ ПО ПАКЕТНЫМ СЕТЯМ
1.1. Основные типы мультимедийного трафика реального времени.
1.2. Общий подход к описанию мультимедийного трафика реального времени.
1.3. Параметры качества обслуживания при передаче мультимедийного трафика в пакетных сетях передачи данных.
1.4. Технологии и стандарты кодирования и передачи видеотрафика.
1.5. Аппроксимация видеотрафика марковскими процессами.
2. АНАЛИЗ И РАЗРАБОТКА МЕТОДОВ МОДЕЛИРОВАНИЯ ТЕЛЕКОММУНИКАЦИОННЫХ СИСТЕМ ПЕРЕДАЧИ МУЛЬТИМЕДИЙНЫХ ВИДЕОТРАФИКОВ.
2.1. Анализ классов математических моделей для исследования процессов передачи мультимедийного видеотрафика в пакетных сетях.
2.2. Сети массового обслуживания как модели телекоммуникационных систем.
2.2.1. Параметры сетей массового обслуживания.
2.2.2. Характеристики стационарного режима функционирования сети массового обслуживания.
2.3. Расчет замкнутых неоднородных сетей массового обслуживания большой размерности.
2.4. Вычисление характеристик сетей массового обслуживания, производных от метода анализа средних.
2.5. Расчет замкнутых неоднородных сетей массового обслуживания с приоритетным обслуживанием.
3. МОДЕЛИРОВАНИЕ ПРОЦЕССОВ ПЕРЕДАЧИ ВИДЕОТРАФИКА В
ПАКЕТНЫХ СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.
3.1. Общие принципы организации мультимедийных сервисов в пакетных телекоммуникационных сетях.
3.2. Концептуальная модель задержек передачи видеотрафика.
3.3. Математическая модель задержек передачи видеопотока.
3.4. Вероятностно- временные характеристики модели оценки задержек передачи видеопотока.
3.5. Результаты моделирования.
4. ОЦЕНКА ДЖИТТЕРА ПЕРЕДАЧИ ВИДЕОПОТОКОВ В ПАКЕТНЫХ
СЕТЯХ ПЕРЕДАЧИ ДАННЫХ.
4.1. Общая постановка задачи.
4.2. Оценка дисперсии задержки передачи видеотрафика в пакетной сети, достоверность результатов.
Рекомендованный список диссертаций
Влияние самоподобности речевого трафика на качество обслуживания в телекоммуникационных сетях 2005 год, кандидат технических наук Осин, Андрей Владимирович
Аппроксимативные методы и модели массового обслуживания для исследования компьютерных сетей 2011 год, доктор технических наук Бахарева, Надежда Федоровна
Разработка модели и анализ характеристик обслуживания видеоинформации в узле сети АТМ 2002 год, кандидат технических наук Молчанов, Дмитрий Александрович
Влияние мультифрактальных свойств GPRS/EDGE трафика на характеристики обслуживания мобильных телекоммуникационных сетей 2009 год, кандидат технических наук Матвеев, Сергей Борисович
Методика исследования информационных процессов в телекоммуникационных системах на железнодорожном транспорте 2006 год, кандидат технических наук Толстошеин, Андрей Викторович
Введение диссертации (часть автореферата) на тему «Применение сетей массового обслуживания для исследования процессов передачи видеопотоков в пакетных сетях»
Одной из тенденций развитая современного общества является стремительный рост потребления различных информационных и телекоммуникационных услуг - . Постоянное снижение стоимости информационных услуг, а также развитие телекоммуникационной инфраструктуры (охват все большей территории и все большей части её населения) являются основными причинами этого роста.
Рассматривая особенности развития телекоммуникаций в Иордании, можно отметить следующую особенность . Исторически недостаточно развитая инфраструктура, ограниченный объем инвестиций для её развития, и бурный спрос на телекоммуникационные услуги, в том числе на мультимедийные, который обусловлен экономическим и географическим положением страны, вызывает острую необходимость более эффективного использования всех имеющихся телекоммуникационных ресурсов.
Современные телекоммуникационные системы постоянно расширяют перечень своих услуг посредством предоставления все большего числа различного вида информационных сервисов, в том числе и мультимедийных. Примерами мультимедийных сервисов являются: видеотелефония, видеоконференция, высокоскоростная передача мультимедийных данных, IP-телефония, цифровое телевизионное вещание, мобильная видеосвязь и видео по запросу - .
Традиционно для предоставления информационных услуг использовались синхронные методы передачи данных, при которых на первичной сети выделялись телекоммуникационные ресурсы в расчете на максимальную нагрузку, которые монопольно занимались потребителями и поставщиками соответствующих информационных услуг. В этом случае телекоммуникационные ресурсы сети ис-® пользовались неэффективно, а общая производительность сети была низкой .
Применение пакетных методов передачи информации позволяет за счет ста-^ тистического мультиплексирования значительно повысить общую пропускную способность телекоммуникационной сети - .
Свидетельством этому служит сравнительный анализ способов коммутации для обеспечения мультимедийных услуг, приведенный в . В этой статье обсуждаются перспективы построения мультимедийных сетей связи с использованием режима коммутации пакетов, имеющего следующие преимущества перед методом коммутации каналов:
Более высокую эффективность использования ресурсов звена передачи данных за счет статистического мультиплексирования трафиков пакетов многих приложений;
Значительно более низкую вероятность потери пакетов передаваемого трафика при повышении нагрузки на сеть, хотя при этом имеют место значительные непредсказуемые транзитные задержки;
Возможность гибкого динамического управления передаваемыми трафиками за счет использования различных механизмов назначения приоритетов элементам трафика, и резервирование телекоммуникационных ресурсов сети.
В связи с ростом производительности систем передачи данных стало # возможным использование пакетных методов передачи трафиков, генерируемых различными информационными сервисами, число которых может быть достаточно большим. Поэтому становится актуальной задача оценки параметров качества предоставляемого сервиса с учетом конкретных архитектуры и топологии используемой телекоммуникационной сети в условиях реальной информационной нагрузки .
Эта задача особенно актуальна в случае предоставления мультимедийного сервиса, который в значительной степени чувствителен к задержкам передачи его ^ трафика .
В статьях и делается вывод о том, что технология ATM является наиболее подходящей технологией для эффективной передачи мультимедийной информации и предоставления услуг ATM-сетей с гарантированным требуемым ц качеством. Однако, обеспечение параметров качества услуг речевого трафика в сетях ATM является сложной задачей, решение которой невозможно без применения специальных методов управления транспортными, сетевыми и канальными ресурсами. В этих статьях подробно рассмотрены понятия качества и целостности услуг, эффективности использования ресурсов; приведена классификация механизмов управления трафиком; проведен сравнительный анализ алгоритмов управления перегрузками в сетях ATM.
Необходимо отметить, что к настоящему времени теория оценки парамет-^ ров качества предоставляемого мультимедийного сервиса в пакетных сетях недостаточно развита.
Разработан ряд математических моделей различных классов, которые позволяют получить адекватную оценку параметров качества обслуживания для конкретных видов информационных сервисов, конкретных архитектур телекоммуникационных систем, а также конкретных их топологий, как правило, регулярных , , .
Наиболее актуальными, в плане решения задач оценки качества предоставляемого мультимедийного сервиса, выделяются три основные задачи:
1. Оценка параметров трафиков, генерируемых информационными серви-ф сами определенного типа.
2. Собственно оценка параметров задержек передачи мультимедийного трафика, передаваемого в пакетной сети с заданной архитектурой и топологией.
3. Оценка дисперсии и джиггера задержки передачи мультимедийного трафика в пакетных сетях.
Для решения выше перечисленных задач применяются различные математические методы моделирования , , среди которых выделяются аналитические, имитационные и гибридные. Так, в статье профессором Мархасиным предложен метод баланса шггенсивностей нагрузок для решения задачи анализа интегрального телетрафика в радиоинтерфейсе, оптимизации и динамического управления качеством обслуживания мобильных сетей 3-ш поколения, например ^ систем GPRS. В работе оценивается вероятность появления скачков интенсивности трафика в сотовых сетях подвижной связи и проводится анализ его рабочих характеристик, для решения данной задачи можно использовать аппарат теории самоподобия. В работах и анализируется видеотрафик, генерируемый различными сервисами в радио и мобильных сетях.
Для решения второй задачи в работе предлагаются различные методы совпадения импульсных потоков для отыскания необходимых параметров суммарного трафика, передаваемого по телекоммуникационной сети с заданными архитектурой и топологией. Применение методов теории совпадения импульсных потоков для расчета трафиков нагрузки в широкополосных интегральных сетях ATM предлагалось в . Цыбаков В. И. в работе утверждает, что традиционные методы проектирования телефонных сетей оказываются неприемлемы для оценки параметров мультимедийных сетей, так как традиционные методы учитывают только лишь одномерный трафик, который к тому же является однородным. Мультимедийная сеть представляет собой интегрированную сеть с представлением широкого спектра услуг (речи, данных, видео), т. е. является сетью, обеспечивающей многомерный и неоднородный трафик.
Для решения задачи оценки джиттера задержки (задача 3) применяются математические модели различных классов. Наиболее распространенными являются аналитические и имитационные модели. Содержание этих методов более подробно рассмотрено в главе 2. Выбор используемого класса моделей определяется многими факторами, среди которых можно выделить следующие: цели моделирования, возможность адекватного описания исследуемых параметров в соответствующих классах математических моделей, трудоемкость разработки этих моделей и др - .
В качестве примеров аналитического моделирования параметров качества предоставления мультимедийных сервисов можно выделить следующие работы.
Рекомендации ITU-T Е.430, Е.800 и концепция соответствия качества услуг представленного информационного сервиса. Эту модель предлагается использовать для проектирования, инсталляции и эксплуатации как существующих, так и вновь разрабатываемых информационных услуг современных телекоммуникационных сетей.
В работе разработана аналитическая модель процессов обслуживания видеографика в узле коммутации ATM. Использование данной модели на этапе планирования пользовательских услуг видеоинформации позволит определять необходимые параметры качества обслуживания, такие как задержка, джиггер и вероятность потери пакетов, необходимых при установлении транспортного соединения.
В литературе часто встречаются аналитические модели различных телекоммуникационных систем, разработанных в классе конечных марковских цепей и непрерывных марковских процессов. Для построения аналитической модели сети радиосвязи с неоднородными потоками информации в работе выбраны методы непрерывных марковских процессов с конечным множеством состояний. Приведена модель, описывающая процесс передачи информации в радиосетях и позволяющая определить вероятности отказа по требованиям и по нагрузке для всей сети и для каждого поступающего в сеть потока.
В статье предложена математическая модель IP сети передачи звука, представленная в виде марковского процесса, в котором стационарное распределение вероятностей состояний имеет непрерывный характер. Марковский процесс описывает возможности предоставления услуг с несколькими уровнями качества.
В статье рассматриваются математические модели, описывающие процессы функционирования и управления трафиком в системах мобильной связи. В качестве математических аппаратов применены модели сетей и систем массового обслуживания с комбинированным обслуживанием, относительными приоритетами, ожиданием, потерями, резервированием ресурсов и ненадежными каналами. Получены основные вероятностно-временные характеристики этих процесссов.
В работе представляется методика оценки качества обслуживания пользователей сети Интернет, а что касается мультимедийных сетей, то такая методика представлена в статье .
В качестве примеров имитационного моделирования параметров качества предоставления мультимедийных сервисов можно выделить работы и , в которых для оценки параметров передачи мультимедийного трафика применялся метод имитационного моделирования. Представленные имитационные модели процессов передачи видеотрафика в телекоммуникационных сетях, работающих в режиме коммутации пакетов, на примере IP-сети, позволяют изучить поведение видеопотока в условиях, когда телекоммуникационная система не гарантирует качества предоставления соответствующих услуг абонентам. В этих моделях различные типы видеокадров, составляющие его последовательности, передаются отдельно (в каждом эксперименте передается один тип видеокадров), а в конце суммируются результаты. В этих моделях не учитывается влияние дополнительных кадров (например, повторно переданных) и не рассчитывается задержка, которая является основным параметром качества видеосервиса.
В работе для исследования мобильной сети, предоставляющей различен ные мультимедийные услуги, представлена имитационная модель, которая позволяет определить параметры задержки и потери пакетов, происходящие в мобильных сетях. В данной имитационной модели исследуется процесс передачи узкоформатного видеоизображения с низкой частотой регенерации (низкокачественное видео).
В работе рассматривается пример А ГМ-сети, которая предоставляет услугу передачи мультимедийного трафика ABR, в соответствии с которой гарантируется минимальная скорость передачи, и не производится синхронизации приемника и передатчика. Передаваемый видеопоток в данной системе имеет низкий приоритет, а число абонентов этой сети является ограниченным.
В работе представляется имитационная модель, предназначенная для исследования вероятностно-временных характеристик транспортного протокола в беспроводной сети. В данной модели приводится анализ задержки при различных вероятностях потери пакетов информации для различных вариантов транспортного протокола TCP. Разработанная модель подтверждается реальными измерениями на реальной сети.
В работе анализируется процесс цифровой передачи видеотрафика, который предъявляет строгие требования к ширине полосы пропускания, задержке и потере. Сети с коммутацией пакетов не могут гарантировать качество обслуживания, особенно при многоадресной (широковещательной) передаче видео. Для обеспечения большей гибкости и эффективности в этих сетях применяются различные механизмы управления потоками, позволяющие, с одной стороны, повысить эффективность, а с другой стороны, обеспечить требуемое качество предоставляемого сервиса. Сравнительный анализ приводится в на примере передачи мультимедийного трафика стандарта MPEG. Сравниваются два механизма управления потоками: IntServ и DiffServ. Отдается предпочтение механизму Diff-Serv с приоритетами и разбиением мультимедийного передаваемого потока на ряд потоков с различными уровнями приоритетов.
Целью диссертационной работы является разработка методов и средств аналитического моделирования процессов передачи мультимедийных видеопотоков в пакетных сетях; применение разработанных методов для оценивания основных параметров качества мультимедийных видеосервисов (транзитной задержки и её джиггера).
Для достижения этих целей решены следующие основные задачи диссертационной работы:
1) Исследование особенностей мультимедийных трафиков, их классификация и параметризация.
2) Анализ особенностей методов кодирования и процессов передачи мультимедийных видеотрафиков в пакетных сетях.
3) Адаптация метода аналитического моделирования телекоммуникационных систем замкнутыми неоднородными сетями массового обслуживания для оценки параметров качества мультимедийных видеосервисов.
4) Разработка аналитических моделей задержек передачи видеотрафика в IP-сети и оценка джиттера и дисперсии этих задержек.
Научная новизна результатов:
1. Разработана модель видеотрафика реального времени, которая учитывает структуру и содержание мультимедийной информации, используемого метода кодирования и сжатия при условии его передачи в пакетных сетях; основана на его аппроксимации пуассоновскими процессами.
2. Разработана методика аналитического моделирования процессов передачи мультимедийного трафика замкнутыми неоднородными сетями массового обслуживания большой размерности, которая учитывает топологию телекоммуникационной сети и применяемые протоколы обмена данными.
3. Разработана модель процесса передачи видеотрафика в TCP/IP сети с типичной звездообразной топологией, обеспечивающая оценивание широкого спектра вероятностно-временных характеристик её процессов функционирования.
4. На базе разработанной модели получены оценки основных параметров качества представляемого мультимедийного видеосервиса (транзитная задержка и её джиггер).
Практическая ценность результатов работы.
Предложенные математические модели и методы позволяют проектировать систему передачи данных произвольной топологии, с учетом ее конкретного оборудования, с целью обеспечения требуемых параметров качества предоставляемых мультимедийных сервисов различных видов.
Разработано программное обеспечение анализа приоритетных замкнутых неоднородных сетей массового обслуживания большой размерности (до 200 систем обслуживания, 3000 классов требований и 10 000 требований);
Предложенные модели использовались ООО "Первая миля" (Компьютерные сети Академгородка) при проектировании и развитии мультисервисной сети Академгородка.
Результаты проведенных исследований внедрены в учебный процесс Сибирского Государственного Университета Телекоммуникаций и Информатики.
Основные положения, выносимые на защиту:
1. Модель аппроксимации трафика мультимедийного видеосервиса марковскими цепями с учетом структуры и содержания его мультимедийной информации, её методов кодирования и сжатия, архитектуры используемых систем передачи данных.
2. Методика аналитического моделирования процессов передачи трафиков мультимедийных видеосервисов замкнутыми неоднородными сетями массового обслуживания большой размерности, основанная на отображении неоднородных информационных потоков соответствующими классами требований, задержки элементов этих потоков в соответствующем телекоммуникационном оборудовании соответствующими системами массового обслуживания.
3. Аналитическая модель процессов передачи видеотрафика в локальной сети с использованием стека протоколов ТСРЯР для оценки параметров качества (транзитная задержка и джиггер) предоставленных мультимедийных сервисов - видео по требованию.
Апробация работы. Основные положения и результаты диссертационной $ работы докладывались и обсуждались на: Международной научно-технической конференции «Информатика и проблемы телекоммуникаций» (г. Новосибирск, 1997г); Российских научно-технических конференциях (г. Новосибирск, 1996, 2004 гг); Международной научно-практической конференции «Связь-2004»; научно-технических семинарах кафедры ТС и ВС Сибирского государственного университета телекоммуникаций и информатики (г. Новосибирск, 1996 - 2004гг).
Публикации: Основные результаты диссертационной работы опубликованы с 1996 по 2004 г. в 6 работах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и приложений. Общий объем работы составляет 145 страниц машинописного текста и включает: 23 рисунка, 18 таблиц, список литературы из 130 наименований и 2 приложения.
Похожие диссертационные работы по специальности «Системы, сети и устройства телекоммуникаций», 05.12.13 шифр ВАК
Исследование фрактальных свойств потоков трафика реального времени и оценка их влияния на характеристики обслуживания телекоммуникационных сетей 2007 год, кандидат технических наук Урьев, Григорий Анатольевич
Разработка метода повышения пропускной способности уровня абонентского доступа 2009 год, кандидат технических наук Булатов, Сергей Валерьевич
Влияние помехоустойчивости широкополосных систем беспроводного доступа IEEE 802.16 на качество передачи потокового трафика 2010 год, кандидат технических наук Арсеньев, Андрей Владимирович
Пути построения и методы анализа гибридных мультисервисных спутниковых систем связи 2002 год, кандидат технических наук Сирухи Джозеф Вере
Сетевая информационная система с виртуальными подсетями повышенной производительности 2009 год, кандидат технических наук Хворов, Алексей Александрович
Заключение диссертации по теме «Системы, сети и устройства телекоммуникаций», Аль-Днебат Саид Али
Предложен метод оценки джиттсра доставки мультимедийного видеотрафика. Он учитывает топологию исследуемой телекоммуникационной системы, структуру передаваемого видеопотока и маршрута его доставки.
Данный метод основан на оценке задержек передачи видеокадров сетями массового обслуживания и аппроксимации дисперсии задержек в компонентах телекоммуникационной системы дисперсиями задержек в СМО М/М/1. Эта СМО эквивалентна соответствующей СМО сети по интенсивности входного потока требований и их среднему времени пребывания в ней.
Корректность предложенных методов подтверждается результатами, представленными в перечисленных на рисунках публикациях.
ЗАКЛЮЧЕНИЕ
Результаты проведенных в диссертационной работе исследований показывают, что основная цель данной работы, заключающаяся в разработке аналитических моделей процессов передачи мультимедийных видеотрафиков в пакетных телекоммуникационных сетях, достигнута. При выполнении данной диссертационной работы получены следующие основные результаты:
1) Проанализированы сервисы, которые предоставляют мультимедийные услуги в современных телекоммуникационных сетях. Проведена параметризация трафиков этих сервисов с учетом конкретной архитектуры используемых телекоммуникационных сетей и их топологии. Предложена модель аппроксимации трафиков мультимедийных сервисов марковскими процессами, которая учитывает особенности кодирования и передачи MPEG видеопотоков.
2) Адаптирована методика моделирования процессов передачи мультимедийных трафиков и оценки параметров качества предоставляемого мультимедийного сервиса в пакетных сетях передачи данных замкнутыми неоднородными сетями массового обслуживания большой размерности.
3) Модифицирован метод "анализ средних" - расчета сетей обслуживания, с учетом большой размерности сети (L = 200 систем обслуживания, и К = 3000 классов требований) и наличия приоритетных потоков требований.
4) В системе Mathcad разработана программа расчета замкнутой неоднородной сети массового обслуживания с числом узлов до 200, числом классов требований до 3000 и суммарным числом требований всех классов до 10 000.
5) Разработана аналитическая модель процесса передачи трафика мультимедийного сервиса «цифровое видео по запросу» по локальной TCP/IP сети конкретной топологии. Данная модель обеспечивает оценку следующих вероятностно-временных характеристик используемой телекоммуникационной системы: коэффициент использования различного телекоммуникационного оборудования, время доставки пакетов мультимедийного трафика до абонентов, дисперсия времени доставки, задержка пакетов в различных компонентах телекоммуникационной сети, дисперсия и джиггер этой задержки.
6) Проведены многочисленные расчеты с помощью данной модели. Получены зависимости вероятностно-временных характеристик такой сети от числа абонентов данного мультимедийного сервиса.
7) Разработанные методики математического моделирования были внедрены в учебный процесс Сибирского Государственного Университета Телекоммуникаций и информатики.
8) Предложенные модели использовались ООО " Первая миля" при проектировании и развитии мультисервисной сети Академгородка города Новосибирска.
9) Достоверность предложенных методов подтверждается результатами моделирования, а также реальными измерениями подобных телекоммуникационных систем. Результаты представлены на рис. 18 в гл.З и рис.23 в гл.4.
Проведенные исследования показали возможность применения марковских процессов и сетей массового обслуживания для исследования процессов передачи мультимедийной информации в телекоммуникационных системах различных архитектур. Приведенные результаты моделирования продемонстрировали хорошую адекватность разработанных моделей, достаточную для практического применения . Разработанные методы и модели могут быть успешно применены для исследования процессов передачи мультимедийной информации в сетях с произвольной архитектурой и топологией.
Список литературы диссертационного исследования кандидат технических наук Аль-Днебат Саид Али, 2004 год
1. Мархасин А.Б. Резервы роста российского рынка услуг мобильной связи: дифференциация и динамическое управление качеством услуг (QoS) и тарифа-ми//Электросвязь № 3 - 2001.
2. Шехтман Л. И. Системы телекоммуникаций: проблемы и перспективы. Опыт системного исследования. М.: Радио и Связь, 1998.
3. Marchese М. Study and performance evaluation of TCP modifications and tuning over satellite links//ICC 2000.
4. Аль-Днебат С., Аль-Касасбех Б. Вопросы развития перспективных широкополосных телекоммуникационных сетей в Иордании//Информатика и проблемы телекоммуникаций. Тезисы докладов Российской научно-технической конференции Новосибирск: СибГУТИ, 1996 - С.73-74.
5. Altmann J., Rupp В., Varaiya P. The Case for Quality of Service on Demand. ISQE"99//Workshop on Internet Service Quality Economics 1999.
6. Guirguis R.M., Mahmoud S. Transmission of real-time multi layered MPEG-4 over ATM/ABR service/ЛСС 2000 - PP.259-263.
7. Dubrovsky A., Gerla M., Lee S. S., Cavendish D., Internet QoS Routing with IP Telephony and TCP Traffic//IEEE, JUNE 18-22, 2000 New Orleans.
8. Ma Q., Steenkiste P. Routing Traffic with Quality-of-Service Guarantees in Integrated Services Networks//Workshop on Network and Operating Systems Support for Digital Audio and Video, Cambridge, England, July 1998.
10. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер: с англ.-М.:Мир. 1989, 544 с.
11. Мизин И.А., Богатырев В.А., Кулешов А.П. Сети с коммутацией пакетов. М.: Радио и связь, 1986, 408 с.
12. Лагутин В.С.Использование сетей с коммутации пакетов для реализации услуг мультимедиа / Системы управления сетями телекоммуникаций. МТУ СИ. М., 2002, С 210. в ЦНТИ "Информсвязь" 2002, №2205-св2002.
13. Попова А.Г., Панов А.Е. Сравнительный анализ способов коммутации для обеспечения услуг мультимедиа. Системы управления сетями телекоммуни-каций//МТУСИ. М., 2002, С.69-75.
14. Крук Б.И., Попантонопуло В.Н., Шувалов В.П. Телекоммуникационные системы и сети, современные технологии. Том 1 М. горячая линия-телеком, 2003г, - С.647.
15. Башарин Г.П., Самуйлов К.Е. Современный этап развития теории телеграфи-ка//Информационные материалы -2110-№1- С. 153-166.
16. Pippas J.B., Venieris I.S. A red variation for delay control/ЛЕЕЕ June 18-22, 2000- New Orleans.
17. S. Kapoor S. Raghavan. Improved multicast routing with delay and delay variation constraints. GLOBECOM 00 IEEE. San Francisc. 27 November -1 December 2000.
18. Chili-Jen C., Nilsson A.A. Queuing networks modeling for a packet router architecture using the DTM technology//IEEE June 18-22, 2000 New Orleans.
19. T.M. Trang, N. Boukhatem, G. Pujolle. COPS-SLS usage for dynamic policy-based QoS management over heterogeneous IP networks/ЯЕЕЕ network. May/June, 2003, PP 44-50.
20. Мархасин А.Б. Анализ интегрального телетрафика и проектирование мобильных сетей ЗС//Электросвязь 2002 - № 12 - С.3-9.
21. Демьянов А.И. Оценка параметров скачков нагрузки в сотовых сетях подвижной связи//Электросвязь 2002 - № 5.
22. Bahl P. Supporting digital video in a managed wireless network//IEEE Communications Magazine vol. 36 - June 1998 - PP.94-102.
23. Davies N., Finney J., Friday A., Scott A. Supporting adaptive video applications in mobile environments//IEEE Communications Magazine vol. 36 - June 1998 -PP. 138-143.
24. Седякин H.M. Элементы теории случайных импульсных потоков. М.: Советское радио, 1965, С.260.
25. Цыбаков В.И., Численные исследования дисперсионных свойств нагруз-ки//Вести связи 2002 - № 12 - С.55-58.
26. Шеннон Р. Имитационное моделирования систем, искусство и наука. Пер: с англ. М.: Мир, 1978, - С.420.
27. Аврамчук Е.Ф., Вавилов А.А., Емельянов С В. и др. Технология системного моделирования. Машиностроение. Берлин: Техник, 1988, - С.520.
28. Максимей И.В. Имитационное моделирование на ЭВМ. М.: Радио и мир. 1988, С. 232.
29. Иванов А.Б., Соколов И.В., От сквозного контроля сети к контролю качества услуг//Элекгросвязь 2001 - № 2.
30. Молчанов Д.А. Разработка модели и анализ характеристик обслуживания видеоинформации в узле сети АТМ//автореферат диссертационной работы на соискание ученой степени кандидата технических наук ГУТ - Санкт-Петербург - 2002 - С. 180.
31. Швецов В.П., Цирик И.А. Модель сети радиодоступа с разнородными потоками информации//Информсвязь 2001 - № 2195 - С. 18-25.
32. Casetti С. De Martin J.C. Meo M. A framework for the analysis of adaptive voice over IP//IEEE June 18-22, 2000 New Orleans.
33. Михалевич И.Ф., Сычёв К.И. Моделирование процессов функционирования и управления трафиком в системах мобильной связи//Элекгросвязь-2002 № 1.
34. Голышко А.В., Ершов В.А., Цыбаков В.И. Оценка качества обслуживания пользователей Интернет, включенных в электромеханические АТС//Вестник связи 2000 - № 12 - С.70.
35. Ершов В.А., Ершова Э.Б., Щека А.Ю., Метод оценки качества обслуживания на мультисервисной сети с учетом числа пользователей услуг//Электросвязь-2001 №8-С.5-8.
36. Cohen R., Radha Н., Streaming fine-grained scalable video over packet-based net-work//IEEE Global Telecommunications Conference San Francisco -27 November-1 December - 2000.
37. Lee M.J., Kim J.K. Video frame rate control for non-guaranteed network services with explicit rate feedback Visual Communications Lab//Dept. of Electrical Engineering Kusongdong Yusonggu Taejon - PP 305-701.
38. Wong W.K., Qian Y., Leung V.C. Scheduling for heterogeneous traffic in next generation wireless network//GLOBECOM IEEE-San Francisco 2000 - PP .283-287.
39. ElAarag H., Bassiouni M. Simulation of transport protocols over wireless communication networks//Proceedings of the 2000 Winter Simulation Conference -PP 235-1241.
40. Dapeng W., Yiwei H. Streaming video over the Internet Approaches and direc-tions/ЛЕЕЕ Trans / Circuits and Syst. Video Technol 2001 - № 3 - PP.282-300.
41. Zhao H., Ansari N., Shi Yun Q. Transmission of real-time video over IP differentiated services//Electron. Lett. 2002 - № 19 - PP.1151-1153.
42. Baskett F., Chandy K.M., Muntz R.R., Polacias F.G. Open, closed and mixednet-works of queues with different classes of customers//Journal of the ACM v.22, №2 - 1975 - PP.248-260.
43. Konstantopoulos Т., Zazanis M., De Veciana G. Conservation laws and reflection mappings with an application to multiclass mean value analysis for stochastic fluid queues//Stochastic Process vol. 65, №. 1 - 1996 - PP. 139-146.
44. Marchese M. Study and performance evaluation of TCP modifications and tuning over satellite links//IEEE ICC JUNE 18-22 2000- NEW ORLEANS.
45. Chen J.C, Agrawal P. Active techniques for real time video transmission and play-Ьаск/ЛЕЕЕ ICC 2000 - New Orleans - PP.239-243.
46. Lixin W. Hamdi M. Analysis of Multimedia Access Protocols for Shared Medium Networks//IEEE 2000 Global Telecommunications Conference - San Francisco.
47. Фоминов О. Мультимедиа и сети. Мультимедиа. Цифровое видео, № 5 1997.
48. Bodamer S., A New Scheduling Mechanism to Provide Relative Differentiation for Real-Time IP Traffic/ЛЕЕЕ 2000 GTC - San Francisco.
49. Bandara J., Shen X., Nurmohamed Z. A Fuzzy Resource Controller for Non-RealTime Traffic in Wireless Networks//IEEE ICC june 18-22, 2000 - New Orleans.
50. Jiang J. Lai Т. H., An Efficient Approach to Support QoS and Bandwidth Efficiency in High-Speed Mobile Networks//IEEE ICC june 18-22, 2000 - New Orleans.
51. Barryl M., Andrew T. Distributed Control Algorithms for Service Differentiation in Wireless Packet Networks//IEEE INFOCOM 2001.
52. Mansour J. Karam F. Tobagi A. On Traffic Types and Service Classes in the Internet//IEEE Global Telecommunications Conference 2000 - San Francisco.
53. Mercado A., Ray K. J. Adaptive QoS for Mobile Multimedia Applications Using Power Control and Smart Antennas//IEEE ICC june 18-22,2000 - New Orleans.
54. Kuzmanovic A. Edward W Measuring Service in Multi-Class Networks//IEEE INFOCOM 2001.
55. Lombardo A., Morabito G., Schembra G., An Accurate and Treatable Markov Model of MPEG-Video Traffic//IEEE Proc. Infocom April 1998 - USA, San Francisco.
56. ITU-T Recommendation 1.363.2: B-ISDN ATM Adaptation Layer 2 Specifications, Sep 1997.
57. ITU-T Recommendation H.323 Version 3, Packet Based Multimedia Communication Systems, 1998.
58. Capurro M., Ravaglia R., Giuli D. Users, Services and Traffic Modeling for Broadband Telecommunications Planning/TVol. 2- № 4 Jul.-Aug. 1991.
59. Bonatti M., Gaivoronski A., Lemonche P., Polese P. Summary of Some Traffic Engineering Studies Carried out Within RACE Project R1044//Vol. 5, № 2 Mar. Apr. 1994.
60. Maniatis S.I., Nikolouzou E.G., Venieris I.S. QoS issues in the converged 3G wireless and wired networks//IEEE Communications Magazine V.40, № 8 -2002 - PP.44-53.
61. Олифер В.Г., Олифер H.A. Компьютерные сети, принципы, технологии, протоколы. СП.: Питер, 2001, С.668.
62. Markopoulou P., Tobagi A., Karam J. Assessment of VoIP Quality over Internet Backbones//IEEE INFOCOM 2002.
63. Voran S. Speech quality of G.723.1 coding with added temporal discontinuity im-pairments//Proc. of ICASSP May 2001.
64. Ramjee R., Kurose J., Schulzrinne H. Adaptive play out mechanisms for pack-etized audio applications in wide-area networks/ЯЕЕЕ INFOCOM June 1994.
65. Rosenberg J., Qiu L., Schttlrinne H., Integrating packet FEC into adaptive voice playout buffer algorithms on the lnternet/ЛЕЕЕ INFOCOM March 2000.
66. Carle G., Biersack E. W., Survey of Error Recoveiy Techniques for IP-Based Audio-Visual Multicast Applications//IEEE Network vol. 11 - November-December 1997 - PP.24-36.
67. Perkins C., Hodson O., Hardman V. A Survey of Packet-Loss Recovery Techniques for Streaming Audio//IEEE Network vol.12, №. 5 - Sept-Oct 1998 -PP.40-48.
68. Erdol N., Castelluccia C., Zilouchian A. Recoveiy of Missing Speech Packets Using the Short-Time Energy and Zero-Crossing Measurements//IEEE Transactions on Speech and Audio Processing vol.1, №.3 - July 1993 - PP.295-303.
69. Chen Y. L., Chen B. S. Model-Based Multirate Representation of Speech Signals and Its Application to Recovery of Missing Speech Packets//IEEE Transactions on Speech and Audio Processing vol. 5, №. 3 - May 1997 - PP.220-231.
70. Hardman V., Sasse M.A., Handley M., Watson A. Reliable Audio for Use over the Intemet//Int. Proceedings of INET"95 1995.
71. Советов Б.Я., Яковлев С.А. Построение сетей интегрального обслуживания. -Л.: Машиностроение, 1990. С.332.
72. ISO/IEC JTC1/SC29/WG11 № 2459 Overview of the MPEG-4 standard. 1998.
73. Srivastava A., Kumar A., Singru A., Design and Analysis of a Video-on-Demand Served/Multimedia Systems Vol.5, No.4 - July 1997 - PP.238-254.
74. Wu D., Hou Y., Zhu W., Zhang Y., Peha M. Streaming video over the Internet Approaches and directions//IEEE Trans. Circuits and Syst. / Video Technol. 2001 -№ 3 - PP.282-300.
75. Conklin G., Greenbaum G., Lillevold K., Lippman A., Reznik Y. Video coding for streaming media delivery on the Internrt/ЯЕЕЕ Trans. Circuits and Syst. Video Technol. - 2001 - № 3 - PP.269-281.
76. Lee J. On a unified architecture for video-on-demand services/ЛЕЕЕ Trans. Multimedia 2002 - № 1 - PP.38-47.
77. Pornavalai C., Chakraborty G., Shiratori N. QoS Based Routing Algorithm in Integrated Services Packet NetwoTks//Intemational Conference on Network Protocols Atlanta, Georgia - PP. 167-175.
78. Rabbat R. Traffic Engineering Algorithms Using MPLS for Service Differentia-tion//IEEE JUNE 18-22, 2000 - NEW ORLEANS.
79. Toukourou M., Orozco-Barbosa L. Performance of MPEG-2 video-on-demand over RSVP//Proc. SPIE 2000 - PP. 13-24.
80. Furey S. The place of modeling tools in network planning//EDP Perform. Revio (USA) 1989 - V.17 - №6 - PP. 1-4.
81. Frost V.S., Melamed В., Traffic modeling for telecommunications net-works//IEEE Communications Magazine Mar. 1994 - PP.70-81.
82. Loeve W. Construction of programs for simulation//Informatie (Netherlands) -1993,- V.35, № 7-8 PP.485-492.
83. Shannon R.E., Introduction to simulation//IEEE Winter Simulations Conference Proceedings New York, USA - 1992 - PP.65-73.
84. Barton R.R., Fishman G.S., Kalos M.H., Kelton W.D., Kleijnen J.P. Experimental design issues for large simulation models//IEEE Winter Simulations Conference Proceedings San Diego, USA - 1989 - PP.411-418.
85. Henriksen J.O. The integrated simulation environment. Simulation software of the 1990s//0peration Res. (USA) 1983 - V.31, .№6 - PP. 1053-1073.
86. Radiya A., Fishwick P.A., Nance R.E., Rothenberg J., Sargent R.G. Discrete event simulation modeling, directions for the 1990s. 1992
87. Розанов Ю.А. Случайные процессы. M.: Наука, 1979г. С. 112.
88. Казаков В.А. Введение в теорию марковских процессов и некоторые радиотехнические задачи. -М.: Советское радио, 1973.
89. Гнеденко Б.В. Курс теории вероятностей. М.: Наука. 1969
90. Феллер В. Ведение в теорию вероятностей и ее приложения. Т.1, 2. М.: Мир, 1984.
91. Кемин Дж., Снелл Дж. Конечные цепи Маркова. М.: Наука. 1970.
92. Карлин С.Осноы теории случайных процессов. М.: Мир, 1971.
93. Krunz, М.М. Makowski A.M., Modeling Video Traffic Using M/G/l Input Processes: A Compromise Between Markovian and LRD Models//IEEE Journalon Selected Areas in Communications 16 (5) PP.733-748.
94. Poon, W. Lo K., A refined version of M/G/ос processes for modeling VBR video traffic//Computer Communications PP. 1105-1114.
95. Кофман А., Крюон P. Массовое обслуживание. Теория и приложения. М.: Мир, 1965.
96. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчёта. М.: Наука, 1989. С. 336.
97. Штойян Д. Качественные свойства и оценки стохастических моделей. М.: Мир, 1979.
98. Кениг Д., Штойян Д. Методы теории массового обслуживания. М.: Радио и связь, 1981.
99. Jackson J.R. Networks of waiting Iines//Operation Research 1957 - №5 -PP.518-521.
100. Gordon W.G., Newell G.F. Closed queueing systems with exponential serv-ers//Operation Research V.15, №2 - 1967 - PP.254-265.
101. Митрофанов Ю.И., Беляков В.Г., Курбангулов B.X. Методы и программные средства аналитического моделирования сетевых систем//Препринт, М.: Научный совет по комплексной проблеме Кибернетика, 1982. с 67.
102. ChandyK.M., Howard J.H., TowsIeyD.F., Product form and local balance in queueing networks//Journal of the ACM v.24, №2 - 1977 - PP.250-263.
103. Беляков В.Г., Митрофанов Ю.И., Ярославцев А. Ф. Пакет прикладных программ для математического моделирования сетевых систем. 1986. С. 145150.
104. Гурьянов А.И., Митрофанов Ю.И. Определение параметров замкнутых линейных сетей систем массового обслуживания. 1970. С.39-49.
105. Chandy К.М. Neuse D., a heuristic algorithm for queueing network models for communications of the ACM. v.25, №2, PP. 126-141.
106. Reiser M., Lavenberg S.S. Mean-value analysis of closed multichain queueing networks//J. ACM vol. 27, № 2 - April 1980 - PP 313-322.
107. Reiser M. Mean-value analysis and convolution method for queue-dependentservers in closed queueing networks//Performance evaluation vol. 1 - 1981 -PP 7-18.
108. Жожикашвили В.А., Вишневский B.M. Сети массового обслуживания. Теория и применение к сетям ЭВМ. М.: Радио и связь, 1988. С. 192.
109. Xu Y., Chang Y., Liu Z. Calculation and analysis of compensation buffer size in multimedia systems//IEEE Commun. Lett. 2001 - № 8 - PP.355-357.
110. Xie J., Jiang S., Jiang Y. A dynamic bandwidth allocation scheme for differentiated services in EPONs//IEEE Communications Magazine august 2004, vol. 42 №. 8, PP.32-39.
111. Derong L., Endre S., Wei S. Nested auto-regressive processes for MPEG-encoded video traffic modeling/ЛЕЕЕ Trans. Circuits and syst / Video Technol -2001 -№2-PP 169-183.
112. Митрофанов Ю.И. Синтез сетей массового обслуживания. Саратов: Изд-во ГуНЦ "Колледж", 1995. С. 168.
113. Uttam K.S., Ramakrishnan S., Dilip S. Segmenting full-length VBR video into shots for modeling with Markov-modulated gamma-based framework//Proc. SPIE-2001 PP. 191-202.
114. Ярославцев А.Ф., Аль-Днебат С.А. Моделирование процессов передачи мультимедийного трафика в 1Р-сети//Информатика и проблемы телекоммуникаций. Тезисы докладов Российской научно-технической конференции. Новосибирск: СибГУТИ, 2003 - С.77-80.
115. Ярославцев А.Ф., Аль-Днебат С. А. Применение структурированных сетей обслуживания для оценки параметров качества сервиса телекоммуникационных сетей. Материалы международной научно-практической конференции «Связь 2004». 22-29 августа 2004 г. С.329-335.
116. CCIE, Cisco Certified internetworking Expert. Учебное руководство, Экзамен 350-001, М, 2002.
117. Schulzrinne Н., Casner S., Frederick R., Jacobson V. A Transport Protocol for Real-Time Applications//Audio-Video Transport Working Group January 1996.
118. Braden R., Clark D., Shenker S. Integrated Services in the Internet Architecture:an Overview / Internet RFC 1633, June 1994.
119. Zhao W. Tripathi S. K. Routing Guaranteed Quality of Service Connections in Integrated Services Packet Networks//International Conference on Network Protocols Atlanta, Georgia - PP. 175-182.
120. Balakrishnan H., Padmanabhan V., Seshan S., Katz R. A Comparison of Mechanisms for Improving TCP Performance over Wireless Links//IEEE ACM Trans, on Networking December 1997.
121. He E., Hughes H.D. Experimental Evaluation of TCP Performance over Wireless Networks//Symposium on Performance Evaluation of Computer and Telecommunication Systems 1999.
122. Schulzrinne H., Casner S., Frederick R., Jacobson V. RTP: A Transport Protocol for Real-Time Applications//RFC 1889 January 1996.
123. Spiridon В., Li V. Maximizing the number of users in an interactive video-on-demand system//IEEE Trans. Broadcast 2002 - № 4 - PP.281-292.
124. Hartanto F., Tiohardi L. Effects of interaction between error control and media synchronization on application-level performances//GLOBECOM"00. IEEE San Francisco - 2000 - PP.283-287.
125. Chatzimisios P., Boucouvalas A.C. Vitsas V. Performance Analysis of IEEE 802.11 DCF in Presence of Transmission Errors//2004 IEEE International Conference on Communications 2004.
126. Ярославцев А.Ф., Аль-Днебат С.А., Аналитическая модель передачи мультимедийного трафика по TCP/IP сети. Материалы международной научно-практической конференции «Связь 2004». 22-29 августа 2004 г. С.323-328.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.
Рассмотренный в предыдущей лекции марковский случайный процесс с дискретными состояниями и непрерывным временем имеет место в системах массового обслуживания (СМО).
Системы массового обслуживания – это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания.
Примерами систем массового обслуживания могут служить:
- расчетно-кассовые узлы в банках, на предприятиях;
- персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;
- станции технического обслуживания автомобилей; АЗС;
- аудиторские фирмы;
- отделы налоговых инспекций, занимающиеся приёмкой и проверкой текущей отчетности предприятий;
- телефонные станции и т. д.
Узлы |
Требования |
|
Больница |
Санитары |
Пациенты |
Производство |
||
Аэропорт |
Выходы на взлетно-посадочные полосы Пункты регистрации |
Пассажиры |
Рассмотрим схему работы СМО (рис. 1). Система состоит из генератора заявок, диспетчера и узла обслуживания, узла учета отказов (терминатора, уничтожителя заявок). Узел обслуживания в общем случае может иметь несколько каналов обслуживания.
Рис. 1
- Генератор заявок – объект, порождающий заявки: улица, цех с установленными агрегатами. На вход поступает поток заявок (поток покупателей в магазин, поток сломавшихся агрегатов (машин, станков) на ремонт, поток посетителей в гардероб, поток машин на АЗС и т. д.).
- Диспетчер – человек или устройство, которое знает, что делать с заявкой. Узел, регулирующий и направляющий заявки к каналам обслуживания. Диспетчер:
- принимает заявки;
- формирует очередь, если все каналы заняты;
- направляет их к каналам обслуживания, если есть свободные;
- дает заявкам отказ (по различным причинам);
- принимает информацию от узла обслуживания о свободных каналах;
- следит за временем работы системы.
- Очередь – накопитель заявок. Очередь может отсутствовать.
- Узел обслуживания состоит из конечного числа каналов обслуживания. Каждый канал имеет 3 состояния: свободен, занят, не работает. Если все каналы заняты, то можно придумать стратегию, кому передавать заявку.
- Отказ от обслуживания наступает, если все каналы заняты (некоторые в том числе могут не работать).
Кроме этих основных элементов в СМО в некоторых источниках выделяются также следующие составляющие:
терминатор – уничтожитель трансактов;
склад – накопитель ресурсов и готовой продукции;
счет бухгалтерского учета – для выполнения операций типа «проводка»;
менеджер – распорядитель ресурсов;
Классификация СМО
Первое деление (по наличию очередей):
- СМО с отказами;
- СМО с очередью.
В СМО с отказами заявка, поступившая в момент, когда все каналы заняты, получает отказ, покидает СМО и в дальнейшем не обслуживается.
В СМО с очередью заявка, пришедшая в момент, когда все каналы заняты, не уходит, а становится в очередь и ожидает возможности быть обслуженной.
СМО с очередями подразделяются на разные виды в зависимости от того, как организована очередь, – ограничена или не ограничена . Ограничения могут касаться как длины очереди, так и времени ожидания, «дисциплины обслуживания».
Итак, например, рассматриваются следующие СМО:
- СМО с нетерпеливыми заявками (длина очереди и время обслуживания ограничено);
- СМО с обслуживанием с приоритетом, т. е. некоторые заявки обслуживаются вне очереди и т. д.
Типы ограничения очереди могут быть комбинированными.
Другая классификация делит СМО по источнику заявок. Порождать заявки (требования) может сама система или некая внешняя среда, существующая независимо от системы.
Естественно, поток заявок, порожденный самой системой, будет зависеть от системы и ее состояния.
Кроме этого СМО делятся на открытые СМО и замкнутые СМО.
В открытой СМО характеристики потока заявок не зависят от того, в каком состоянии сама СМО (сколько каналов занято). В замкнутой СМО – зависят. Например, если один рабочий обслуживает группу станков, время от времени требующих наладки, то интенсивность потока «требований» со стороны станков зависит от того, сколько их уже исправно и ждет наладки.
Пример замкнутой системы: выдача кассиром зарплаты на предприятии.
По количеству каналов СМО делятся на:
- одноканальные;
- многоканальные.
Характеристики системы массового обслуживания
Основными характеристиками системы массового обслуживания любого вида являются:
- входной поток поступающих требований или заявок на обслуживание;
- дисциплина очереди;
- механизм обслуживания.
Входной поток требований
Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание, и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (количество таких требований в каждом очередном поступлении ). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.
А i – время поступления между требованиями – независимые одинаково распределенные случайные величины;
E(A) – среднее (МО) время поступления;
λ=1/E(A) – интенсивность поступления требований;
Характеристики входного потока:
- Вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание.
- Количество требований в каждом очередном поступлении для групповых потоков.
Дисциплина очереди
Очередь – совокупность требований, ожидающих обслуживания.
Очередь имеет имя.
Дисциплина очереди определяет принцип, в соответствии с которым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами:
- первым пришел – первый обслуживаешься;
first in first out (FIFO)
самый распространенный тип очереди.
Какая структура данных подойдет для описания такой очереди? Массив плох (ограничен). Можно использовать структуру типа СПИСОК.
Список имеет начало и конец. Список состоит из записей. Запись – это ячейка списка. Заявка поступает в конец списка, а выбирается на обслуживание из начала списка. Запись состоит из характеристики заявки и ссылки (указатель, за кем стоит). Кроме этого, если очередь с ограничением на время ожидания, то еще должно быть указано предельное время ожидания.
Вы как программисты должны уметь делать списки двусторонние, односторонние.
Действия со списком:
- вставить в хвост;
- взять из начала;
- удалить из списка по истечении времени ожидания.
- пришел последним - обслуживаешься первым LIFO (обойма для патронов, тупик на железнодорожной станции, зашел в набитый вагон).
Структура, известная как СТЕК. Может быть описан структурой массив или список;
- случайный отбор заявок;
- отбор заявок по критерию приоритетности.
Каждая заявка характеризуется помимо прочего уровнем приоритета и при поступлении помещается не в хвост очереди, а в конец своей приоритетной группы. Диспетчер осуществляет сортировку по приоритету.
Характеристики очереди
- ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»);
- длина очереди.
Механизм обслуживания
Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся:
- количество каналов обслуживания (N );
- продолжительность процедуры обслуживания (вероятностное распределение времени обслуживания требований);
- количество требований, удовлетворяемых в результате выполнения каждой такой процедуры (для групповых заявок);
- вероятность выхода из строя обслуживающего канала;
- структура обслуживающей системы.
Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».
S i – время обслуживания i -го требования;
E(S) – среднее время обслуживания;
μ=1/E(S) – скорость обслуживания требований.
Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода из строя обслуживающего канала по истечении некоторого ограниченного интервала времени. Эту характеристику можно моделировать как поток отказов, поступающий в СМО и имеющий приоритет перед всеми другими заявками.
Коэффициент использования СМО
N ·μ – скорость обслуживания в системе, когда заняты все устройства обслуживания.
ρ=λ/(N μ) – называется коэффициентом использования СМО , показывает, насколько задействованы ресурсы системы.
Структура обслуживающей системы
Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживани .
Пример. Кассы в магазине.
Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно . Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований.
Пример. Медицинская комиссия.
Комбинированное обслуживание – обслуживание вкладов в сберкассе: сначала контролер, потом кассир. Как правило, 2 контролера на одного кассира.
Итак, функциональные возможности любой системы массового обслуживания определяются следующими основными факторами :
- вероятностным распределением моментов поступлений заявок на обслуживание (единичных или групповых);
- мощностью источника требований;
- вероятностным распределением времени продолжительности обслуживания;
- конфигурацией обслуживающей системы (параллельное, последовательное или параллельно-последовательное обслуживание);
- количеством и производительностью обслуживающих каналов;
- дисциплиной очереди.
Основные критерии эффективности функционирования СМО
В качестве основных критериев эффективности функционирования систем массового обслуживания в зависимости от характера решаемой задачи могут выступать:
- вероятность немедленного обслуживания поступившей заявки (Р обсл =К обс /К пост);
- вероятность отказа в обслуживании поступившей заявки (P отк =К отк /К пост);
Очевидно, что Р обсл + P отк =1.
Потоки, задержки, обслуживание. Формула Поллачека–Хинчина
Задержка – один из критериев обслуживания СМО, время проведенное заявкой в ожидании обслуживания.
D i – задержка в очереди требования i ;
W i =D i +S i – время нахождения в системе требования i .
(с вероятностью 1) – установившаяся средняя задержка требования в очереди;
(с вероятностью 1) – установившееся среднее время нахождения требования в СМО (waiting).
Q(t) – число требований в очереди в момент времени t;
L(t) – число требований в системе в момент времени t (Q(t) плюс число требований, которые находятся на обслуживании в момент времени t.
Тогда показатели (если существуют)
(с вероятностью 1) – установившееся среднее по времени число требований в очереди;
(с вероятностью 1) – установившееся среднее по времени число требований в системе.
Заметим, что ρ<1 – обязательное условие существования d, w, Q и L в системе массового обслуживания.
Если вспомнить, что ρ= λ/(N μ), то видно, что если интенсивность поступления заявок больше, чем N μ, то ρ>1 и естественно, что система не сможет справиться с таким потоком заявок, а следовательно, нельзя говорить о величинах d, w, Q и L.
К наиболее общим и нужным результатам для систем массового обслуживания относятся уравнения сохранения
Следует обратить внимание, что упомянутые выше критерии оценки работы системы могут быть аналитически вычислены для систем массового обслуживания M/M/N (N >1), т. е. систем с Марковскими потоками заявок и обслуживания. Для М/G/ l при любом распределении G и для некоторых других систем. Вообще распределение времени между поступлениями, распределение времени обслуживания или обеих этих величин должно быть экспоненциальным (или разновидностью экспоненциального распределения Эрланга k-го порядка), чтобы аналитическое решение стало возможным.
Кроме этого можно также говорить о таких характеристиках, как:
- абсолютная пропускная способность системы – А=Р обсл *λ;
- относительная пропускная способность системы –
Еще один интересный (и наглядный) пример аналитического решения – вычисление установившейся средней задержки в очереди для системы массового обслуживания M/G/ 1 по формуле:
.
В России эта формула известна как формула Поллачека– Хинчина, за рубежом эта формула связывается с именем Росса (Ross).
Таким образом, если E(S) имеет большее значение, тогда перегрузка (в данном случае измеряемая как d ) будет большей; чего и следовало ожидать. По формуле можно обнаружить и менее очевидный факт: перегрузка также увеличивается, когда изменчивость распределения времени обслуживания возрастает, даже если среднее время обслуживания остается прежним. Интуитивно это можно объяснить так: дисперсия случайной величины времени обслуживания может принять большое значение (поскольку она должна быть положительной), т. е. единственное устройство обслуживания будет занято длительное время, что приведет к увеличению очереди.
Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам.
Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса , происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские . В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими. Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему. В случае немарковских процессов задачи исследования систем массового обслуживания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.
Сеть массового обслуживания представляет собой совокупность конечного числа N обслуживающих узлов, в которой циркулируют заявки, переходящие в соответствии с маршрутной матрицей из одного узла в другой.
Узел всегда является разомкнутой СМО (причем СМО может быть любого класса). Отдельные СМО отображают функционально самостоятельные части реальной системы, связи между СМО структуру системы, а требования , циркулирующие по СеМО, составляющие материальных потоков.
СеМО классифицируют по нескольким признакам (рис. 2.5).
Сеть называется линейной, если интенсивности потоков заявок в узлах связаны между собой линейной зависимостью , где коэффициент пропорциональности, или относительно источника .
Коэффициент (коэффициент передачи) характеризует долю заявок, поступающих вj -й узел от источника заявок, либо среднее число прохождений заявки через данный узел за время ее нахождения в сети.
Если интенсивности потоков заявок в узлах сети связаны нелинейной зависимостью (например, ), то сеть называется нелинейной.
Сеть всегда линейна, если в ней заявки не теряются и не размножаются.
Рис. 2.5. Классификация СеМО
Разомкнутая сеть – это такая отрытая сеть, в которую заявки поступают из внешней среды и из которой уходят после обслуживания во внешнюю среду. Особенностью разомкнутой СеМО (РСеМО) является наличие одного или нескольких независимых внешних источников, которые генерируют заявки, поступающие в сеть, независимо от того, сколько заявок уже находится в сети. В любой момент времени в РСеМО может находиться произвольное число заявок (от 0 до ).
В замкнутой СеМО (ЗСеМО) циркулирует фиксированное число заявок, а независимый внешний источник отсутствует. Исходя из физических соображений, в ЗСеМО выбирается внешняя дуга, на которой отмечается псевдонулевая точка, относительно которой могут измеряться временные характеристики. Число заявок в замкнутой сети постоянно.
Комбинированная сеть – это сеть, в которой постоянно циркулирует определенное число заявок и есть заявки, поступающие от внешних независимых источников.
В однородной сети циркулируют заявки одного класса. В неоднородной сети могут присутствовать заявки нескольких классов. Заявки относятся к разным классам, если они различаются хотя бы одним из следующих атрибутов:
– законом распределения длительности обслуживания в узлах;
– приоритетами;
– маршрутами (путями движения заявок в сети).
В экспоненциальной сети длительности обслуживания во всех узлах распределены по экспоненциальному закону и потоки, поступающие в разомкнутую сеть, простейшие (пуассоновские). Во всех остальных случаях сеть является неэкспоненциальной.
Если хотя бы в одном узле осуществляется приоритетное обслуживание, то это – приоритетная сеть. Приоритет – это признак, определяющий очередность обслуживания. Если заявки в узлах обслуживаются в порядке поступления, то такая сеть называется бесприоритетной .
Таким образом, экспоненциальной будем называть СеМО, отвечающую следующим требованиям:
– входные потоки СеМО пуассоновские;
– во всех N СМО время обслуживания заявок имеет экспоненциальную функцию распределения вероятностей, заявки обслуживаются в порядке прихода;
– переход заявки с выхода i -й на вход j -й СМО является независимым случайным событием, имеющим вероятность ,;– вероятность ухода заявки изCeМО.
Для наглядного представления СеМО используется граф, вершины которого (узлы) соответствуют отдельным СМО, а дуги отображают связи между узлами.