Содержание к диссертации
Введение
ГЛАВА 1 Принципы компрессии и кодирования видеоинформации 21
1.1 Введение 21
1.2 Обзор международных стандартов компрессии и кодирования видеоинформации 21
1.3 Принципы компрессии и кодирования видеоинформации 24
1.3.1 Представление цветовых компонентов в стандарте MPEG-X 24
1.3.2 Основные принципы компрессии и кодирования 25
1.3.3 Структура группы кадров 29
1.3.4 DCT преобразование 30
1.3.5 Квантование 31
1.3.6 Энтропийное кодирование 31
1.3.7 Компенсация движения 32
1.4 Особенности стандарта MPEG-2 33
1.4.1 Уровни и профили стандарта MPEG-2 33
1.4.2 Функции адаптации к средам хранения и передачи информации. 35
1.4.3 Транспортный поток 36
1.4.4 Структура заголовка пакета транспортного потока 40
1.5. Временная модель стандарта MPEG-2 41
Выводы 43
ГЛАВА 2 Статистические характеристики видеотрафика 45
2.1 Введение 45
2.2 Исходные данные эмпирических последовательностей размеров кадров 45
2.3 Статистические характеристики на уровне кадров 47
2.3.1 Процесс генерации кадров 47
2.3.2 Процессы генерации I, Р и В кадров 53
2.4 Статистические характеристики на уровне групп кадров 60
2.4.1 Процесс генерации групп кадров 60
2.5 Алгоритм временного сглаживания 64
2.5.1 Интерактивность 64
2.5.2 Методы определения требуемой полосы пропускания 65
2.5.3 Алгоритм временного сглаживания 69
Выводы 72
ГЛАВА 3 Разработка модели видеотрафика MPEG 74
3.1 Введение 74
3.2 D-BMAP процесс 74
3.2. J Определение D-BMAP процесса 74
3.2.2 Вероятностные характеристики D-BMAP процессов 78
3.3 Моделирование видеотрафика MPEG на уровне групп кадров 84
3.3.1 Выбор метода получения D-BMAP процесса 84
3.3.2 Аппроксимация эмпирической функции автокорреляции 88
3.3.3 Синтез D-BMAP процесса, аппроксимирующего эмпирическую функцию автокорреляции 89
3.3.4 Аппроксимация гистограммы относительных частот размеров групп кадров 97
3.4 Пример использования алгоритма моделирования 101
Выводы 111
ГЛАВА 4 Анализ характеристик обслуживания видеотрафика mpeg в узле коммутации ATM 112
4.1 Введение .112
4.2 Модель обслуживания ячеек на уровне atm в буферном накопителе узла коммутации atm 113
4.3 Моделирование конкурирующего и мультиплексированного трафика 117
4.3.1 Моделирование конкурирующего трафика 117
4.3.2 Моделирование мультиплексированного трафика 119
4.4 Анализ характеристик обслуживания мультиплексированного видеотрафика MPEG 119
4.4.1 Функция распределения вероятностей количества ячеек в системе 119
4.4.2 Средние значения количества ячеек в системе и задержки ячейки 123
4.4.3 Функция распределения вероятностей времени ожидания 124
4.4.4 Функция распределения вероятностей количества потерянных ячеек 126
4.5 Анализ характеристик обслуживания видеотрафика mpeg одного источника 128
4.5.1. Функция распределения вероятностей количества потерянных ячеек 130
4.5.2 Функция распределения вероятностей времени ожидания 134
4.6 Численные исследования 137
Выводы 148
Заключение 150
Список литературы
- Принципы компрессии и кодирования видеоинформации
- Статистические характеристики на уровне кадров
- Вероятностные характеристики D-BMAP процессов
- Анализ характеристик обслуживания мультиплексированного видеотрафика MPEG
Введение к работе
Актуальность проблемы. Характерной чертой современного этапа развития электросвязи является тенденция к объединению информационных и телекоммуникационных технологий и услуг. Большинство таких услуг являются широкополосными, а их предоставление оконечному пользователю предполагает интерактивный обмен информацией в реальном масштабе времени.
Концепция построения перспективных сетей передачи информации должна обеспечивать в одной сети эффективную реализацию услуг, которые в настоящее время предоставляются оконечным пользователям различными сетями связи: телефонной, телевизионной, сетями передачи данных. [16,23,25,27].
В качестве транспортной технологии для построения таких сетей может использоваться технология асинхронного режима доставки (Asynchronous Transfer Mode, ATM). Сети передачи информации на основе технологии ATM способны предоставлять гарантии качества обслуживания (Quality of Service, QoS) различным приложениям [127].
Предполагается, что одну из основных составляющих мультимедийной нагрузки в ближайшем будущем будут создавать услуги передачи компрессированной цифровой видеоинформации [30,37,51,68,109,121]. Такие услуги генерируют потоки видео- и аудиоинформации, которые затем должны быть доставлены при помощи сети терминалу-приемнику оконечного пользователя. К ним можно отнести услуги передачи видеоинформации по требованию (Video-on-Demand, VoD), услуги телевидения высокой четкости (High Definition Television, HDTV) и услуги видеоконференции.
Для снижения требований к полосе пропускания [44,120], необходимой источнику для передачи видеоинформации, видеоинформация подвергается компрессии (сжатию) и кодированию в соответствии с одним из существующих стандартов [75,76,109,121].
На сегодняшний день наиболее перспективными и динамично развивающимися стандартами компрессии и кодирования видеоинформации являются стандарты экспертной группы по кодированию и компрессии
подвижных изображений (Moving Pictures Experts Group, MPEG) [74,76]. Стандарты MPEG обеспечивают возможность компрессии видеоинформации в широком диапазоне качества изображения.
Известно, что вышеуказанные процедуры предъявляют дополнительные требования к параметрам качества обслуживания видеотрафика в сетях передачи информации [37,39,41,43]. Видеотрафик имеет жесткие требования к задержке доставки информации и величине потерь [49,58,64]. Принимая во внимание тот факт, что для мультисервисных сетей на основе технологии ATM источники видеоинформации могут создавать значительную часть общей нагрузки, задачи моделирования и исследования характеристик обслуживания видеоинформации, подвергшейся компрессии и кодированию в соответствии со стандартом MPEG (далее видеотрафик MPEG), в узле коммутации сети ATM являются актуальными.
В последнее десятилетие вопросы моделирования видеотрафика рассматривались в работах Г.Г. Яновского, Е.А. Кучерявого, D. Heyman, А. Lombardo, G. Schembra, S.-Q. Li [30,31,34,35,37,39,40,43,64,69-72,82-86,95-102] и ряда других авторов. Анализ опубликованных исследований показывает, что недостаточное внимание было уделено математическому моделированию видеотрафика MPEG. В большинстве работ разрабатывались алгоритмы имитации видеотрафика на ЭВМ [30,31,34,35,69-72]. Такие модели имеют ограниченную область применения и могут быть использованы при имитационном моделировании сетей передачи информации [28,29]. Необходимость анализа характеристик обслуживания видеотрафика MPEG в узлах коммутации сети ATM определяет актуальность разработки математической модели такого трафика.
Цель и задачи исследований. Целью диссертационной работы является математическое моделирование и анализ характеристик обслуживания видеотрафика MPEG в узле коммутации сети ATM. Поставленная цель достигается путем решения в диссертационной работе ряда задач, среди которых необходимо выделить следующие: 1. Аналитический обзор принципов алгоритмов компрессии и кодирования
видеоинформации. Определение структурных особенностей потока
видеоинформации.
Анализ статистических характеристик видеотрафика MPEG. Определение возможных подходов к моделированию видеотрафика MPEG.
Исследование методов временного сглаживания видеотрафика MPEG.
Разработка математической модели видеотрафика MPEG.
Разработка модели обслуживания ячеек на уровне ATM в буферном накопителе узла коммутации ATM.
Численные исследования и анализ характеристик обслуживания видеотрафика MPEG в узле коммутации сети ATM на основе модели видеотрафика MPEG и модели обслуживания ячеек на уровне ATM в буферном накопителе узла коммутации ATM.
Методы исследования. Проведенные в диссертационной работе исследования основываются на теории вероятностей, теории марковских процессов, теории массового обслуживания, теории телетрафика, математической статистике и высшей алгебре.
Для проведения численных расчетов и статистического анализа в диссертационной работе использовались библиотека функций для языка программирования С пакета GNU Scientific Library [130] и программа расчета стационарных распределений двойных марковских процессов Teletraffic Package [129]. Программное обеспечение, необходимое для решения задач, использующих имитационное моделирование, реализовано на языке программирования С.
Научная новизна. Основными результатами диссертационной работы, обладающими научной новизной, являются:
алгоритм временного сглаживания видеотрафика MPEG;
математическая модель видеотрафика MPEG на уровне групп кадров;
математические выражения для вероятностей потерь и задержки ячеек в системе массового обслуживания D-BMAP/D/1/AT для случая поступления нескольких конкурирующих потоков.
Практическая ценность. Основным результатом диссертационной работы, обладающим практической ценностью, является аналитическое представление характеристик обслуживания видеотрафика MPEG в узле коммутации ATM.
Использование результатов работы на этапе проектирования и разработки программного обеспечения приложений, обеспечивающих передачу видеоинформации в сетях, основанных на технологии ATM, позволит выбирать необходимые параметры качества обслуживания, запрашиваемые на этапе установления соединения. Результаты работы также могут быть использованы на этапе планирования сетей передачи информации, в частности, для выбора оптимальных объемов буферных накопителей узлов коммутации и канального ресурса сетей ATM, обслуживающих трафик услуг передачи видеоинформации.
Апробация работы и публикации. Результаты диссертационной работы были представлены в форме докладов [17-22,80,81,106,131,132] на следующих научно-технических семинарах и конференциях:
VIII Российская научная конференция профессорско-преподавательского состава, научных сотрудников и аспирантов, Самара, Академия телекоммуникаций и информатики, 19-23 февраля, 2001 г.
III Международная научно-техническая конференция студентов, аспирантов и молодых специалистов стран СНГ "Техника и технология связи", Одесса, Академия связи им. Попова, 11-12 сентября, 2001 г.
VIII Международная конференция "Информационные сети, системы и технологии", Минск, БГЭУ, 2-4 октября, 2001 г.
Международный семинар "Telecommunication networks and teletraffic theory", Санкт-Петербург, ЛОНИИС, 29 Января - 1 Февраля, 2002 г.
Международный семинар по вопросам телетрафика "Nordic Teletraffic Seminar", Эспо (Финляндия), Технологический Университет Хельсинки, 21-23 Августа, 2002 г.
Международная конференция "Network Control and Engineering for QoS", Париж (Франция), Технологический университет Труа, 21-23 Октября, 2002 г.
а также на научно-технических конференциях профессорско-преподавательского состава, научных работников и аспирантов ГУТ им. проф. М.А. Бонч-Бруевича в 2000-2002 гг.
Основные положения, выносимые на защиту: - статистические характеристики видеотрафика MPEG;
алгоритм временного сглаживания видеотрафика MPEG;
математическая модель видеотрафика MPEG на уровне групп кадров;
модель обслуживания ячеек на уровне ATM в буферном накопителе узла коммутации ATM;
математические выражения для вероятностей потерь и задержки ячеек в системе массового обслуживания D-BMAP/D/1/АГ для случая поступления нескольких конкурирующих потоков;
характеристики обслуживания видеотрафика MPEG в буферном накопителе узла коммутации ATM.
Личный вклад автора. Основные положения, теоретические выводы и рекомендации, содержащиеся в диссертационной работе, получены автором самостоятельно.
Публикации. Основные результаты диссертационной работы представлены в 10 печатных работах.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и трех приложений.
Работа содержит 179 страниц машинописного текста, включая 48 рисунков, список литературы из 132 наименований, и приложения.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность исследования, сформулированы цели и задачи диссертационной работы, перечислены основные полученные результаты диссертации, определены практическая ценность и области использования полученных результатов. Приведены сведения об апробации работы, представлены основные положения, выносимые на защиту.
В первой главе проводится аналитический обзор базовых принципов компрессии и кодирования видеоинформации и функций адаптации к различным приложениям и средам хранения и передачи информации, определенных в стандартах MPEG.
Обзор базовых принципов компрессии и кодирования видеоинформации, показал, что алгоритм компрессии и кодирования видеоинформации стандарта
MPEG-1 является основой для стандартов MPEG-2 и MPEG-4. Стандарты MPEG-2/4 расширяют возможности стандарта MPEG-1, определяя функции адаптации к различным приложениям и средам хранения и передачи информации.
Анализ функций адаптации к различным приложениям и средам хранения и передачи информации показал, что базовой единицей моделирования видеотрафика MPEG является элементарный поток MPEG-1, образуемый последовательностью кадров, прошедших обработку в соответствии с алгоритмом компрессии и кодирования стандарта MPEG-1. Таким образом, в качестве модели видеотрафика MPEG необходимо использовать модель элементарного потока.
Рассматривая принципы адаптации к среде хранения и передачи информации, отмечено, что процедура создания транспортного потока является процессом мультиплексирования. Используя модель элементарного потока можно получить как модель пакетизированного потока, так и модель транспортного потока.
В элементарном потоке MPEG-1 определены два логических уровня: уровень кадров, образуемый последовательностью кадров на выходе кодера, и уровень групп кадров, образуемый последовательностью групп кадров. Кроме того, следует различать процесс генерации кадров, процессы генерации различных типов кадров и процесс генерации групп кадров. Таким образом, для того чтобы определить подходы к моделированию видеотрафика MPEG необходимо исследовать статистические характеристики процесса генерации кадров, процессов генерации различных типов кадров и процесса генерации групп кадров, образующих элементарный поток.
Во второй главе исследуются статистические характеристики видеотрафика MPEG на уровнях кадров и групп кадров.
В работе получены и проанализированы статистические характеристики десяти эмпирических последовательностей размеров кадров видеотрафика MPEG-1, доступные на сервере университета города Вурзбург (Германия). Эмпирические последовательности представляют собой запись 40000 размеров кадров. Группа кадров имеет структуру (12,3,2).
Определены и исследованы статистические характеристики процессов генерации I, Р и В кадров, групп кадров, и процесса генерации кадров. Показано,
что процесс генерации кадров не является стационарным процессом. Процессы генерации I, Р и В кадров и процесс генерации групп кадров являются стационарными в широком смысле процессами. Установлено наличие корреляционной зависимости между процессами генерации I, Р я В кадров. Отмечено, что эмпирическая функция автокорреляции размеров групп кадров может быть аппроксимирована суммой геометрических составляющих.
В процессе анализа статистических характеристик определены три подхода к моделированию видеотрафика MPEG: моделирование процесса генерации кадров на уровне кадров, моделирование процессов генерации I, Р и В кадров на уровне кадров и моделирование процесса генерации групп кадров.
Показано, что детерминированная периодическая структура процесса генерации кадров не позволяет представить такой процесс при помощи стационарного случайного процесса. Модель видеотрафика MPEG на уровне кадров может состоять из трех коррелированных стационарных в широком смысле случайных процессов. Модель видеотрафика MPEG на уровне групп кадров может использовать один стационарный в широком смысле случайный процесс. Учитывая тот факт, что модель видеотрафика MPEG на уровне кадров может состоять из трех коррелированных случайных процессов, каждый из которых обладает свойствами зависимости в широком и узком диапазонах, в работе предложено моделировать видеотрафик MPEG на уровне групп кадров.
В заключение исследуются принципы временного сглаживания видеотрафика MPEG, позволяющие снизить требования к полосе пропускания, необходимой для передачи видеотрафика MPEG без потерь. Показано, что видеотрафик MPEG предъявляет высокие требования к полосе пропускания, требуемой для передачи в сети. В качестве алгоритма, позволяющего снизить требования к полосе пропускания, предложено использовать алгоритм временного сглаживания. Предложенный алгоритм не изменяет временной структуры видеотрафика MPEG на уровне групп кадров. В этом случае модель видеотрафика MPEG на уровне групп кадров можно также использовать в качестве модели видеотрафика MPEG, прошедшего процедуру временного сглаживания.
В третьей главе предложена математическая модель видеотрафика MPEG на уровне групп кадров.
В последнее десятилетие в ряде зарубежных работ было доказано, что на характеристики обслуживания трафика в сети с коммутацией пакетов основное влияние оказывают функция распределения вероятностей (ФРВ) количества поступающих требований и функция автокорреляции процесса поступления требований [84-94]. Также было отмечено [86], что ФРВ и функция автокорреляции количества поступающих требований модели трафика должны аппроксимировать их эмпирические аналоги. Таким образом, при математическом моделировании видеотрафика MPEG основное внимание необходимо сосредоточить на аппроксимации гистограммы относительных частот и эмпирической функции автокорреляции размеров групп кадров.
В качестве базового процесса, используемого для математического моделирования видеотрафика MPEG, выбран пачечный процесс поступления требований, модулируемый марковским процессом с дискретным временем и дискретным пространством состояний (Discrete-time Batch Markovian Arrival Process, D-BMAP [39,40]). Показано, что для такого процесса количество поступающих требований в каждом из М состояний марковской цепи может быть задано как некоторым аналитическим законом, так и гистограммой относительных частот, а функция автокорреляции количества поступающих требований D-BMAP процесса может являться суммой геометрических составляющих, образуемых собственными значениями матрицы переходов за один шаг модулирующего марковского процесса.
Задача моделирования видеотрафика MPEG сведена к решению вопроса поиска D-BMAP процесса, аппроксимирующего гистограмму относительных частот и эмпирическую функцию автокорреляции размеров групп кадров эмпирической последовательности. Матрица переходов за один шаг модулирующего марковского процесса искомого D-BMAP процесса должна содержать собственные значения, который являются геометрическими составляющими входящими в выражение автокорреляционной функции D-BMAP процесса.
Искомый D-BMAP процесс представляется при помощи N, N>1, коммутируемых D-BMAP процессов (Switched D-BMAP, SD-BMAP). В таком случае любое собственное значение матрицы переходов D за один шаг модулирующего марковского процесса вносит геометрическую составляющую в выражение функции автокорреляции искомого D-BMAP процесса. Известно, что матрицы переходов за один шаг марковских процессов модулирующих SD-BMAP процессы имеют только одно собственное значение, отличное от единицы, которое является действительным числом на отрезке (0,1). В этом случае функция автокорреляции количества поступающих требований искомого D-BMAP процесса будет являться суммой геометрических составляющих, образуемых собственными значениями матрицы переходов D за один шаг модулирующего марковского процесса.
Предлагаемый метод поиска D-BMAP процесса с вероятностными характеристиками, аналогичными статистическим характеристикам эмпирических данных, состоит из трех последовательных этапов:
аппроксимация эмпирической функции автокорреляции размеров групп кадров, используя определенное количество геометрических составляющих;
получение D-BMAP процесса, аппроксимирующего функцию автокорреляции эмпирической последовательности размеров групп кадров и обладающим математическим ожиданием, равным по величине среднему значению размеров групп кадров эмпирической последовательности;
определение для каждого состояния модулирующего марковского процесса ФРВ размеров групп кадров таким образом, чтобы ФРВ размеров групп кадров D-BMAP процесса аппроксимировала гистограмму относительных частот эмпирической последовательности размеров групп кадров.
В четвертой главе исследуются характеристики обслуживания видеотрафика MPEG в буферном накопителе узла коммутации сети ATM на основе разработанной модели видеотрафика MPEG.
Для достижения поставленной цели определяется модель обслуживания ячеек ATM (далее ячеек) на уровне ATM в буферном накопителе узла коммутации ATM с внутренней неб локируемой коммутационной системой. В классификации Кендалла модель является системой с ожиданием вида GfD/l/К, где К - емкость системы.
Далее рассматриваются три случая:
исходящий канал связи буферного накопителя узла коммутации ATM обслуживает видеотрафик MPEG одного источника, и параметрами, подлежащими изучению, являются характеристики обслуживания видеотрафика MPEG одного источника;
исходящий канал связи буферного накопителя узла коммутации ATM обслуживает мультиплексированный видеотрафик MPEG N источников, и параметрами, подлежащими изучению, являются характеристики обслуживания мультиплексированного видеотрафика MPEG от TV источников;
исходящий канал связи буферного накопителя узла коммутации ATM обслуживает мультиплексированный видеотрафик MPEG N источников, и параметрами, подлежащими изучению, являются характеристики обслуживания видеотрафика MPEG одного источника.
Показано, что в перечисленных случаях система с ожиданием, описывающая буферный накопитель узла коммутации ATM является частным случаем системы D-BMAP/D/1/^Г. Для каждого из перечисленных вариантов постановки задачи получены выражения для ФРВ количества потерянных ячеек в произвольный временной интервал и ФРВ задержки ячейки в системе.
На основе разработанной модели видеотрафика MPEG и модели обслуживания ячеек на уровне ATM в буферном накопителе узла коммутации ATM, проводятся численные исследования характеристик обслуживания видеотрафика MPEG. Рассматриваются три случая:
- система с ожиданием имеет вид D-BMAP[1]/D/1/AT, где D-BMAP[1] процесс
является моделью видеотрафика MPEG одного источника;
система с ожиданием имеет вид D- где D-BMAP1 процесс является суперпозицией десяти D-BMAP процессов, каждый из которых является моделью видеотрафика MPEG одного источника;
система с ожиданием имеет вид D-BMAP[9]+D-BMAPm/D/l//:, где D-ВМАР[9] процесс является суперпозицией девяти D-BMAP процессов, каждый из которых является моделью видеотрафика MPEG одного источника, D-BMAP[1] процесс является моделью видеотрафика MPEG одного источника.
В перечисленных случаях получены ФРВ количества потерянных ячеек и ФРВ времени ожидания ячейки в системе, зависимости среднего значения количества потерянных ячеек и среднего времени ожидания ячейки в системе от полосы пропускания обслуживающего канала связи и емкости системы.
Проведено сравнение вышеуказанных параметров, полученных при помощи предлагаемой модели видеотрафика MPEG, с аналогичными параметрами, полученными при помощи имитационного моделирования процесса обслуживания ячеек каналом связи на основе эмпирических данных размеров групп кадров. На основе полученных результатов можно сделать вывод о том, что предлагаемая модель позволяет достаточно точно оценивать характеристики обслуживания видеотрафика MPEG в буферном накопителе узла коммутации ATM.
Проведено сравнение вышеуказанных параметров, полученных при помощи предлагаемой модели видеотрафика MPEG, с аналогичными зависимостями, полученными при помощи модели не учитывающей автокорреляционные свойства видеотрафика MPEG ("гистограммной" модели). На основе полученных результатов сделан вывод о том, что модель видеотрафика MPEG должна учитывать автокорреляционные свойства эмпирических данных.
ФРВ количества потерянных ячеек в произвольный временной интервал и ФРВ времени ожидания ячейки в системе, полученные в результате моделирования обслуживания видеотрафика MPEG в системе с ожиданием, позволяют получить количественные оценки характеристик обслуживания такого
трафика в буферном накопителе узла коммутации ATM. Приведены численные примеры получения подобных величин.
Принципы компрессии и кодирования видеоинформации
Как известно, воспринимаемый человеком цвет является результатом воздействия света в спектре от 400 до 700 нм на сетчатую оболочку глаза. Известно также, что сетчатая оболочка глаза имеет четыре цветовых рецептора, которые реагируют на свет в различных областях видимого спектра. Один из цветовых рецепторов реагирует только на короткие длины волн видимого спектра и, следовательно, хотя и является необходимым для человеческого зрения, не влияет на восприятие визуального изображения [75].
Учитывая наличие трех рецепторов цвета, влияющих на восприятие визуального изображения, для представления цвета в цифровой форме достаточно использовать три числовых компонента. В 1931 году Интернациональная Комиссия по Излучению (Commission Internationale de L Eclairage, CIE) определила принципы представления распределения спектральных мощностей света в видимой области спектра при помощи набора из трех числовых параметров.
Одной из основных концепций, введенных CIE, является изоляция яркостной составляющей света от цветовой (хроминантной) составляющей. На основе документов CIE Национальный Комитет по Телевидению США, а также европейские институты по стандартизации определили собственные цветовые пространства. Для стандартов PAL (Phase Alternation Line) и SECAM (Systeme En Couleur Avec Memoire) принято пространство YUV, где Y - яркостная составляющая, U - хроминантная составляющая и V - квадратурно-хроминантная составляющая. Цифровым эквивалентом пространства YUV является пространство YCbCr, где хроминантный компонент Сь соответствует компоненту U, хроминантный компонент Сг - компоненту V.
Алгоритм компрессии и кодирования видеоинформации стандарта MPEG-1 использует цветовое пространство YCbCr в качестве пространства представления цветовых компонентов. Для стандарта MPEG-1 определен формат 4:2:0, в котором хроминантные составляющие имеют плотность в два раза меньшую, чем яркостные составляющие, как по вертикальной, так и по горизонтальной оси [75]. Для стандарта MPEG-2 определены несколько форматов, включая 4:2:0.
Известно, что любое видеоизображение содержит в себе три типа избыточности: - пространственную; - временную; - психовизуальную. Пространственная и временная избыточности являются результатом того, что значения ячеек растра (пикселей) определенного кадра видеоизображения зависят от значений соседних ячеек растра в пространстве (в данном кадре) и от их значений во времени в предыдущих и последующих кадрах. Это дает возможность предсказывать их значения на некотором ограниченном отрезке как пространства, так и времени. Психовизуальная избыточность зависит от физических ограничений человеческого глаза. Примером может служить ограниченная возможность различения мелких пространственных деталей в углах кадра или низкая чувствительность глаза к резкому изменению деталей изображения. Таким образом, при компрессии и кодировании можно минимизировать количество бит, используемых для представления видеоизображения, поддерживая при этом постоянное для человеческого глаза качество.
Для устранения пространственной избыточности в стандарте MPEG-1 используется дискретное косинусное преобразование (Discrete Cosine Transform, DCT) и энтропийное кодирование (Entropy Coding, ЕТ). Процедуры компенсации движения используются для устранения временной избыточности. Матрицы квантования необходимы для устранения психовизуальной избыточности.
Алгоритм компрессии и кодирования стандарта MPEG-1 состоит из нескольких последовательных этапов: компенсации движения, дискретного косинусного преобразования (Discrete Cosine Transform, DCT), квантования с потерями и окончательного кодирования. На этапе компенсации движения устраняется временная избыточность. Этап DCT преобразования концентрирует полученную информацию в коэффициентах трансформации. На этапе квантования осуществляется устранение визуальной избыточности. На этом этапе возникают основные потери качества изображения. На последнем этапе осуществляется кодирование с последующим сжатием данных.
Стандарт MPEG-1 определяет алгоритм компрессии и кодирования видеоизображений с потерями, так как декодированное изображение не является точной копией оригинала.
В стандарте MPEG-1 определены следующие основные единицы представления визуальной информации:
- Блок. Блок является минимальной единицей представления информации, используемой в стандарте MPEG-1. Блок представляет собой квадрат 8x8 пикселей. В соответствии с форматом YCbCr блок может иметь один из трех типов: яркостный (У), красный хроминантный (Сг) или синий хроминантный (Сь). Блок является основной единицей для DCT преобразования.
- Макроблок. Макроблок является основной единицей представления визуальной информации процедур компенсации движения алгоритма MPEG. Он составляет квадратный сегмент размером 16x16 пикселей. В зависимости от используемого формата представления цветовых компонентов макроблок может состоять из различных блоков, однако основной формат (4:2:0) использует четыре блока типа Y, один Сг и один Сь.
- Слайс. Это горизонтальная полоса изображения в пределах одной "картинки" видеоизображения. Кодирование и декодирование блоков и макроблоков возможно только при наличии всех значений пикселей в пределах слайса. Кроме того, кодирование слайса производится независимо от соседних слайсов. Таким образом, слайс является автономной единицей алгоритма MPEG-1. Слайс также служит единицей синхронизации потока. - Кадр. Отдельная "картинка" видеоизображения (далее кадр MPEG). - Группа кадров (Group of Pictures, GoP). Группа кадров является наименьшей единицей последовательности кадров, к которой возможен независимый доступ. Понятие группы кадров является концептуальным для стандарта MPEG-1.
Статистические характеристики на уровне кадров
В процессе подготовки диссертационной работы были проанализированы статистические характеристики десяти эмпирических последовательностей размеров кадров видеотрафика MPEG-1, доступные на сервере университета города Вурзбург (Германия) [128]: http://www-info3.informatik.uni-wuerzburg.de/MPEG/. Рассматриваемые эмпирические последовательности были использованы в ряде работ, посвященных анализу статистических характеристик и моделированию видеотрафика MPEG [30,31,37,64,69-72,95-97]. Их названия и сокращенные ссылочные формы, используемые в диссертационной работе, представлены в табл. 2.1. Эмпирические последовательности имеют длины, равные 40000 кадрам.
Все рассматриваемые эмпирические последовательности используют одинаковую структуру группы кадров IBBPBBPBBPBB, которая позволяет достигать высоких коэффициентов компрессии, однако, как будет показано далее, представляет наибольшую сложность для моделирования. С другой стороны, моделирование такой структуры группы кадров позволяет предположить относительную простоту расширения модели на ряд других структур групп кадров, таких как IPP или IBBP.
Далее в работе для демонстрации табличных данных будут использованы пять эмпирических последовательностей размеров кадров: "Star", "Dino", "Bond", "Soccer" и "Talk". В некоторых случаях будут использованы три эмпирических последовательности: "Star", "Dino" и "Bond". Для демонстрации диаграмм и рисунков в качестве репрезентативной эмпирической последовательности выбрана последовательность "Bond".
Пусть случайный процесс {Х(п), « = 0,1,..} определяет размеры кадров, генерируемых кодером MPEG-1 в последовательные временные интервалы. Эмпирические последовательности размеров кадров являются реализациями случайного процесса {Х{п), и = 0,1,..}. Каждая эмпирическая последовательность размеров кадров содержит N групп кадров. Группа кадров состоит из lGoP кадров. Учитывая тот факт, что последовательность кадров состоит из последовательности групп кадров, пусть случайный процесс {Xk(h), к = 0,1,..,lGoP-l, /z = 0,1,.., -1} определяет размер к-то кадра в /г-ой группе кадров, генерируемой кодером MPEG-1. Эмпирическая последовательность размеров кадров, таким образом, является реализацией случайного процесса {Х(п), п = 0,1,..} или эквивалентного случайного процесса {Xk(h), к = 0,1,..,lGoP-\, /z = 0,l,..,iV-l}. Для « 0 имеем: Xk(h) = X(h-lGoP+k), = 0,l,..,/Go/ -l, / = 0,l,..,iV-l. (2.1) где lGoP - длина группы кадров; N— количество групп кадров в эмпирической последовательности кадров.
Для эмпирических последовательностей, используемых в диссертационной работе, lGoP =12 и структура группы кадров - IBBPBBPBBPBB. Введем четыре множества: UGoP ={0,1,2,3,4,5,6,7,8,9,10,11}, 1 (2.2) = {3,6,9}, UB= {1,2,4,5,7,8,10,11}. Из (2.1) и (2.2) можно видеть, что Xk{h), & = 0,1,..,/Gop-1, A = 0,1,..,JV-1, соответствует размеру кадра / при k eUj, размеру кадра Р при к є Up и размеру кадра В при к є UB. Также видно, что Хк (Л) - размер произвольного кадра эмпирической последовательности при к є UGoP.
На рис. 2.1а показана зависимость размера кадра от номера кадра для первых 3000 кадров эмпирической последовательности размеров кадров "Bond", где Xk(h), & = 0,1,..,/Gop-l, /i = 0,l,..,JV-l, обозначает размеры кадров в эмпирической последовательности, kh - 0,1,..,(./V-1)/Gap - номер кадра. Принимая во внимание постоянное количество кадров, генерируемых кодером за определенный интервал времени (здесь - 24 кадра в секунду), данную зависимость можно рассматривать в качестве временной диаграммы.
Вследствие достаточно большого количества представленных кадров, на рис. 2.1а можно наблюдать лишь динамику изменения размеров / кадров, обладающих наибольшими размерами в эмпирической последовательности. Более точное представление о динамике изменения размеров различных типов кадров может быть получено из рис. 2.16, на котором представлена аналогичная зависимость для первых 50 кадров эмпирической последовательности "Bond". Глубокие спады на рисунке соответствуют размерам В кадров, пики соответствуют размерам / кадров. Между двумя последовательными / кадрами три визуальных вершины соответствуют размерам Р кадров.
Вероятностные характеристики D-BMAP процессов
Определим вероятностные характеристики D-BMAP процессов, которые позволяют эффективно использовать такие процессы при моделировании процессов поступления требований для широкого класса мультимедийных приложений. Вначале определим, какие из статистических характеристик трафика оказывают влияние на характеристики обслуживания трафика в узлах коммутации сетей передачи информации.
Развитие теории моделирования процессов поступления требований, основанных на статистических измерениях (Measurements-based Traffic Modeling, МТМ) [84-94], позволило определить основные характеристики процессов поступления требований, которые оказывают влияние на характеристики обслуживания входящих потоков требований в системах с ожиданием, моделирующих буферные накопители узлов коммутации сетей передачи информации. Доказано [84-86], что основное влияние на характеристики обслуживания требований в системе с ожиданием оказывает ФРВ количества поступающих требований, а также функция автокорреляции (энергетический спектр функции автокорреляции) процесса поступления требований. Более того, предполагается [89-94], что основное влияние на характеристики обслуживания трафика оказывает структура энергетического спектра функции автокорреляции в области низких частот, что соответствует структуре функции автокорреляции в области больших значений автокорреляционных интервалов. Также было показано [86], что ФРВ и функция автокорреляции количества поступающих требований модели трафика должны аппроксимировать их эмпирические аналоги (эмпирическую функцию автокорреляции и гистограмму относительных частот). Необходимо отметить, что ранее в теории моделирования трафика сетей передачи информации использовались принципы соответствия ФРВ количества поступающих требований эмпирической гистограмме относительных частот, и не учитывались временные зависимости в структуре трафика. Более того, в качестве моделируемых параметров часто использовались только первые и вторые моменты эмпирических данных (среднее значение и коэффициент вариации [1,3,41,79]). Авторами в [86] отмечено, что такой подход может приводить к значительным ошибкам анализа характеристик обслуживания трафика мультимедийных служб в системах с ожиданием, моделирующих буферные накопители узлов коммутации сетей передачи информации [45,48,74,94-97].
В соответствии с (3.6) и (3.8) D-BMAP процесс допускает использование гистограммы относительных частот в качестве ФРВ количества поступающих требований. Таким образом, ФРВ количества поступающих требований D-BMAP процесса будет состоять из суммы ФРВ, определенных для каждого из состояний процесса, с учетом стационарных вероятностей модулирующего марковского процесса. Такое свойство позволяет использовать D-BMAP процессы при моделировании процессов поступления требований для широкого класса мультимедийных приложений в тех случаях, когда гистограмма относительных частот не может быть аппроксимирована ни одной известной ФРВ.
Рассмотрим автокорреляционную последовательность D-BMAP процесса. Пусть {S(n), п = 0,1,..}, S(n) є {l,2,..,MJ, является однородным эргодическим модулирующим марковским процессом для D-BMAP процесса поступления требований {W(n), п = 0,1,..}. Предположим, что для процесса {W(n), п = 0,1,} существуют средние значения количества поступающих требований в каждом из состояний Gj, і = 1,2,..,М, в соответствии с (3.13). Вектор G = (Gl,G2,--,GM) содержит средние значения количества поступающих требований в каждом из состояний процесса. Пусть случайная величина Е в произвольный временной интервал принимает одно из возможных значений среднего количества поступления требований Е є {Gl,G2,--,GM}. Процесс поступления среднего количества требований в каждом из М состояний модулирующего марковского процесса образует стационарный случайный процесс {Е(п), п = 0,1,..}, определенный на пространстве значений случайной величины Е є {G1,G2,..,GM} и модулируемый марковским процессом {S(n), « = 0,1,..}, S(n)e{\,2,..,M} [39,40]. Одним из важных свойств процессов {Е(п), п - 0,1,..} и fyV(n), п = 0,1,..} является равенство их математических ожиданий [39,40]. По определению автокорреляционная последовательность случайного процесса {Е(П), и = 0,1,..} определяется как последовательность математических ожиданий произведений сечений данного процесса в точках, соответствующих периоду корреляции: RE (т) = М[Е(п) Е(п + т)],т = 0,1,.., (3.15) где т - значение автокорреляционного интервала; Rgim) - значение коэффициента автокорреляции для автокорреляционного интервала т.
Для процесса поступления среднего количества требований в каждом из М состояний модулирующего марковского процесса {Е(п), п = 0,1,..} можно показать, что автокорреляционная последовательность может быть представлена следующим образом [117]:
Анализ характеристик обслуживания мультиплексированного видеотрафика MPEG
Анализ характеристик обслуживания трафика в узлах коммутации является приоритетной задачей на этапах планирования сетей передачи информации и пользовательских услуг передачи информации. На этапе планирования сетей передачи информации необходимо определить требования к емкости буферных накопителей узлов коммутации и канальному ресурсу сети при заданных параметрах потерь и задержки обслуживаемого трафика. С другой стороны на этапе планирования пользовательских услуг передачи информации важно знать значения потерь и задержки обслуживаемого трафика при заданных размерах буферных накопителей и полосах пропускания обслуживающих каналов связи. Кроме того, с точки зрения планирования пользовательских услуг передачи информации необходимо определить значения потерь и задержки трафика одного источника учитывая наличие "конкурирующего трафика". В данной главе термин "конкурирующий трафик" определяет трафик, конкурирующий за обслуживание исходящим каналом связи с трафиком анализируемого источника.
Целью данной главы является анализ характеристик обслуживания видеотрафика MPEG в буферном накопителе узла коммутации сети ATM на основе модели видеотрафика MPEG, предложенной в Главе 3. Для достижения поставленной цели в разделе 4.2 разрабатывается модель обслуживания ячеек ATM (далее ячеек) на уровне ATM в буферном накопителе узла коммутации ATM с внутренней неблокируемой коммутационной системой в виде системы с ожиданием, постоянным временем обслуживания и ограниченной емкостью накопителя. В разделе 4.3 определяется модель мультиплексированного видеотрафика MPEG и предлагается модель конкурирующего трафика. В разделе 4.4 проводится анализ характеристик обслуживания источников видеоинформации. В разделе 4.5 представлены результаты численных исследований.
Предположим, что узел коммутации ATM имеет М исходящих и N входящих портов. Каждый из исходящих портов имеет буферный накопитель, который обслуживается исходящим каналом связи. Модель обслуживания ячеек на уровне ATM в узле коммутации ATM, представлена на рис. 4.1. Необходимо отметить, что такая система является моделью обслуживания ячеек на уровне ATM произвольного сетевого устройства ATM. Так мультиплексор ATM может быть представлен моделью обслуживания, имеющей N входов и один выход, коммутатору соответствует модель обслуживания с N входами и М выходами.
Предположим далее, что узел коммутации имеет внутреннюю неблокируемую коммутационную систему (Internal Switching System, ISS) и время передачи одной ячейки по внутренней коммутационной системе пренебрежимо мало по сравнению с временем обслуживания ячейки любым из исходящих каналов связи. В таком случае ячейки, поступающие в буферные накопители входящих портов узла коммутации, незамедлительно направляются коммутационной системой в буферные накопители исходящих портов в соответствие с внутренней таблицей коммутации и идентификаторами виртуального пути (Virtual Path Identifier, VPI) и виртуального канала (Virtual Channel Identifier, VCI), указанными в заголовке ячеек. Ячейки, поступающие на исходящие порты узла коммутации, буферизируются в буферных накопителях. Предположим, что в соответствие с децентрализованным управление коммутационной системой, каждый из исходящих портов узла коммутации имеет собственное управляющее устройство. Используя указанные предположения, можно констатировать, что процессы обслуживания ячеек в буферных накопителях исходящих портов узла коммутации являются взаимно независимыми. Таким образом, процессы обслуживания ячеек в буферных накопителях исходящих портов узла коммутации можно рассматривать изолированно.
Для обеспечения требуемых параметров качества обслуживания (Quality of Service, QoS), предположим, что на каждом из исходящих портов узла коммутации используются несколько буферных накопителей. Соединения услуг постоянной скорости передачи (Constant Bit Rate, CBR) и переменной скорости передачи (Variable Bit Rate, VBR) используют общий буферный накопитель -буферный накопитель CBR/VBR. Соединения услуги доступной скорости передачи (Available Bit Rate, ABR) используют второй буферный накопитель -буферный накопитель ABR. Трафик соединений услуги неопределенной скорости передачи (Unspecified Bit Rate, UBR) буферизируется последним буферным накопителем - буферным накопителем UBR. Известно, что для обеспечения требуемых параметров QoS, трафик соединений услуг CBR и VBR должен иметь приоритет в обслуживании над трафиком соединений услуги ABR. Трафик соединений услуги ABR, в свою очередь, должен иметь приоритет в обслуживании над трафиком соединений услуги UBR. Предположим, что между буферными накопителями CBR/VBR, ABR и UBR используется дисциплина обслуживания с жесткими приоритетами. Согласно такой дисциплине обслуживания исходящий канал связи обслуживает ячейки, которые находятся в буферном накопителе с наивысшим приоритетом до тех пор, пока в нем остаются не обслуженные ячейки. Модель обслуживания ячеек на уровне ATM в буферном накопителе j -го исходящего порта узла коммутации представлена на рис. 4.2.
