Содержание к диссертации
Введение
ГЛАВА 1. Анализ текущего состояния сетевых потоковых приложений реального времени 11
1.1 Тенденции развития и перспективы сетевых приложений 11
1.2 Взаимодействие сетевых технологий 19
1.2.1 Базовая модель взаимодействия открытых систем OSI 22
1.2.2 Модель TCP/IP 24
1.2.3 Структура стека протоколов ATM 30
1.2.4 DTM технология 33
1.2.5 Сравнение Архитектур КО ATM и Интернет 35
1.2.6 Перечисление Случаев Взаимодействия 35
1.2.7 Классификация моделей взаимодействия 37
1.2.8 Классификация способов взаимодействия 39
1.3 Теоретические основы построения сетевых приложений 43
1.3.1 Моделирование КО 43
1.3.2 Модели и методы анализа сетевых проблем 52
1.4 Выводы к главе 1 56
ГЛАВА 2. Алгебраические модели при сетевой обработке мультимедийной информации 58
2.1 Основы Мини-плюсового исчисления 58
2.1.1 Инфимум и Минимум 59
2.1.2 Диоид ( R U {+ о},л,+) 59
2.1.4 Псевдо-инверсия неубывающих функций 63
2.1.5 Вогнутые и выпуклые функции 64
2.1.6 Мини-плюсовая свертка 65
2.1.7 Суб-аддитивные функции 69
2.1.8 Суб-аддитивное замыкание 70
2.1.9 Мини-плюсовая развертка 73
2.1.10 Представление Мини-Плюсовой Развертки Инверсией Времени 75
2.1.11 Вертикальное и Горизонтальное отклонение 77
2.2 Кривые поступления и обслуживания 78
2.2.1 Моделирование потоков данных 78
2.2.2 Кривые поступления 81
2.2.3 Алгоритмы «Дырявого ведра» и «Обобщенной Ячеечной Скорости» 85
2.2.4 Суб-аддитивность и кривые поступления 87
2.2.5 Минимальная кривая поступления 91
2.2.6 Кривые обслуживания 93
2.3 Приложение сетевого исчисления к интернету 97
2.3.1 Схема GPS 101
2.3.2 Модель интегрированных услуг института IETF 106
2.4 Выводы к ГЛАВЕ 2 109
ГЛАВА 3. Применение аппарата сетевого исчисления к проблемам обеспечения сквозного одинакового ко при передаче непрерывных потоков данных по сети 110
3.1 Оптимальное сглаживание потоков мультимедийных данных .110
3.1.1 Постановка Задачи 103
3.1.2 Ограничения, Налагаемые Сглаживанием без Потерь 112
3.1.3 Минимальные Требования по Задержкам и Буферу Воспроизведения 113
3.1.4 Стратегии Оптимального Сглаживания 114
3.1.5 Оптимальное сглаживание и «жадное» формирование 119
3.1.6 Сравнение с Уравнением Задержки 122
3.1.7 Сглаживание без Потерь через Две Сети 123
3.2 Агрегация потоков детерминированных служб 129
3.2.1. Введение 129
3.2.2 Класс гарантированного обслуживания института IETF 131
3.2.3 Математический аппарат группирования потоков 134
3.2.4 Применение группирования к агрегации 146
3.3 Выводы к ГЛАВЕ 3 151
ГЛАВА 4. Распределенная система «виртуальная лаборатория» 153
4.1 Система «виртуальной лаборатории» 154
4.1.1 Реализация тактильной и силовой обратной связи в РВС 156
4.2 Особенности трафика тактильной и силовой информации 156
4.2.1 Влияние задержки и ее нестабильности на реализацию тактильной/силовой обратной связи 157
4.3 Сетевое мультимедиа для РВС 160
4.3.1 Проблема задержки и ее нестабильности в рамках управления очередями маршрутизаторов 161
4.3.2 Дифференцированные службы для РВС 164
4.4 Эксперименты с имитационной моделью системы «виртуальная лаборатория» 168
4.4.1 Конфигурация экспериментального стенда 168
4.4.2 Эксперименты с механизмами адаптации к нестабильности задержки 169
4.4.3 Эксперименты с механизмами управления сетевыми ресурсами 170
4.5. Имитационное моделирование для анализа параметрической чувствительности 172
4.5.1 Разное количество потоков 173
4.5.2 Разные размеры очереди 174
4.5.3 Разные интенсивности импульсов («забросов трафика») 175
4.5.4 Разные максимальные размеры пакета 176
4.5.5 Разные размеры потока 177
4.5.6 Разные варианты смешанного трафика 178
4.5.7 Разные стоимостные отношения 179
4.5.8 Разные размеры ОА 180
4.6 Выводы к главе 4 181
Заключение 183
Литература 184
Приложения
- Тенденции развития и перспективы сетевых приложений
- Суб-аддитивное замыкание
- Оптимальное сглаживание и «жадное» формирование
- Влияние задержки и ее нестабильности на реализацию тактильной/силовой обратной связи
Введение к работе
Актуальность проблемы Появление в 1994 году глобальной сети Интернет и последовавший бурный рост «всемирной паутины» (WWW) кардинальным образом изменили мир телекоммуникаций. Эти изменения нашли свое отражение и в коммуникационной промышленности, и в информационных технологиях. Первое десятилетие развития Интернета ознаменовалось массовым подключением обычных пользователей к глобальной сети и развитием целого спектра сетевых приложений, подавляющее большинство которых было ориентировано на статические услуги типа поиска и просмотра информации и электронной почты. Сегодня сообщество пользователей глобальной сети Интернет стоит на пороге качественного скачка в направлении полноценных мультимедийных приложений, то есть услуг с богатым мультимедийным содержанием, включая качественное потоковое видео и аудио, интерактивную трехмерную компьютерную графику в дополнение к обычной информации.
Подобное изменение характера сетевого трафика стимулируется с двух сторон: со стороны промышленности мультимедиа и трехмерной компьютерной графики и со стороны самих покупателей и пользователей мультимедийной и трехмерной графической продукции. В промышленности - оцифровка мультимедийного и трехмерного содержимого, а также оцифровка и перестройка под нужды пользователя самого производства привели к появлению новых производственных процессов. Эти новые процессы выпуска и распространения цифровой мультимедийной и трехмерной графической продукции базируются на, взаимодействуют с и задают особые требования к средствам обеспечения качества и к пропускной способности распределенных сетей и Интернета. Высококачественное мультимедийное содержимое, которое прежде было доступно исключительно теле- и радиовещательным компаниям, теперь стало широко доступным через услуги Интернета. Одновременно, сами покупатели и пользователи сети Интернет генерируют широкополосный богатый мультимедийным содержанием сетевой трафик, обмениваясь музыкальными файлами, фотографиями, видеоклипами и играя в сетевые компьютерные игры.
По мере того, как ориентированные на мультимедиа и трехмерную графику услуги начинают доминировать в сети, происходит очередной технологический сдвиг -развертывание инфраструктуры, которая способна справляться с большим количеством потоковых услуг при одновременной поддержке высокого качества. Сеть Интернет в том виде, как она функционирует сегодня, без дополнительных затрат на чрезмерно избыточные ресурсы не способна поддерживать какие-либо услуги, кроме приложений «максимальной возможности» типа «отослал и молись, чтобы дошло». И даже в условиях, когда были сделаны впечатляющие по объемам инвестиции в развертывание оптоволоконных линий связи, большие затраты, связанные с подсветкой длин волн и добавлением оборудования активной маршрутизации и коммутации, создают серьезную нагрузку на экономику.
Все это серьезно ограничивает применимость в реальной жизни экстенсивного подхода к решению проблем качества сетевого трафика, базирующегося па примитивном запасании избыточных ресурсов. А в совокупности с проблемой конкуренции различных сетевых технологий (IP и ATM) это создает проблемы «маршрутизации трафика в смешанных сетях» и «обеспечения гарантированного сквозного качества обслуживания (КО) на всем пути трафика в смешанной сети». Традиционно проблема управления трафиком в сетях решается с помощью математического аппарата теории массового обслуживания, теории графов, теории сетей, теории автоматов и др., которые были разработаны такими известными российскими и зарубежными учеными как Башарин Г.П., Бочаров П.П., Вишневский В.М., Горбатов В.А., Жожикашвили В.А., Корнеев В.В., Лазарев В.Г., Наумов В.А., Нейман В.И., Степанов СИ., Харкевич А.Д., Шнепс-Шнеппе М.А., Шоргин С.Я., Винер Н. и др.
Несмотря на прогресс в развитии теории компьютерных сетей, эта перспективная область оставляет простор для разработки новых аналитических методов и преодоления недостатков известных. Точно также как в начале XX века потребности развития телефонии привели к появлению и бурному развитию теории массового обслуживания (теории очередей), революционные изменения в характере сетевого трафика в начале XXI века потребовали разработки новых теорий, методов анализа и проектирования сетевой инфраструктуры и приложений. Большие надежды на эффективное решение проблем сетевых потоковых приложений реального времени связываются сегодня, в том числе, с развитием математического аппарата сетевого исчисления, представляющего собой набор последних разработок в области математической теории диоидов и, в частности, «мини-плюсового» диоида (также называемого «мини-плюсовой» алгеброй). Сетевое исчисление относится к той области, которую иногда называют «экзотическими алгебрами» и к которой относятся, в том числе, и сети Петри. Они представляют собой набор математических результатов высокой описательной сложности, обеспечивающих средства адекватного представления таких создаваемых человеком систем, как параллельные программы, цифровые электронные схемы и, конечно, коммуникационные сети.
Таким образом, тематика проводимых в диссертационной работе исследований и полученные результаты являются актуальными и имеют важное практическое значение.
Цель диссертационной работы состоит в развитии теоретических основ и разработке математического аппарата, методов моделирования и анализа, которые обеспечат лучшее понимание проблем потоковых приложений, возникающих в компьютерных сетях. Эти формальные методы и средства призваны обеспечить более адекватное представление некоторых фундаментальных свойств сетей интегрированных услуг, управления потоками, составления расписаний и определения размеров буферов или величин сетевых задержек при проектировании приложений распределенных систем мультимедиа и виртуальной реальности.
Для достижения данной цели в работе сформулированы и решены следующие задачи:
1. Анализ особенностей построения и функционирования сетевых потоковых приложений в локальных и глобальных сетях ЭВМ.
2. Анализ базовых сетевых архитектур глобальных сетей и соответствующих архитектур качества обслуживания, классификация моделей взаимодействия и путей организации взаимодействия сетевых архитектур при построении смешанных сетей.
3. Выбор и обоснование базового математического аппарата для моделирования и анализа фундаментальных проблем потоковых приложений в сетях.
4. Разработка моделей потоков и моделей планировщиков для сетевых узлов на основе кривых поступления и обслуживания и их применение для решения проблем буферной памяти, пропускной способности и задержек при обеспечении гарантий качества обслуживания потокам мультимедийных и графических данных.
5. Разработка методов и средств агрегации прикладных потоков в сетях интегрированного обслуживания с проведением точного анализа проблемы распределения ресурсов для агрегированного трафика.
6. Разработка программного обеспечения системы «Виртуальная лаборатория» на базе интерфейса виртуальной реальности для управления научным оборудованием по сети.
Методы исследования.
При решении поставленных задач в диссертационной работе используются концепции и методы общей теории систем, теории вычислительных сетей, математического аппарата сетевого исчисления, методы имитационного моделирования.
К основным научным результатам, представляемым в диссертационной работе и выносимым на защиту, относятся:
1. Результаты анализа действующих сетевых интерактивных систем мультимедиа и трехмерной графики (виртуальной реальности).
2. Математическая модель описания предметной области потоковых приложений в глобальных сетях с использованием математического аппарата сетевого исчисления.
3. Метод адаптации аудио/видео информации для сглаживания эффекта от нестабильности задержки в потоках данных распределенной системы мультимедиа и виртуальной реальности.
4. Подход «активного управления очередями» к реализации дифференцированных служб в маршрутизаторах для защиты TCP-приложений от непрерывных потоковых приложений реального времени и для обеспечения наилучшей службы доставки пакетов данных.
5. Реализация разработанных моделей и методов в виде программного комплекса распределенной системы виртуальной реальности и методик его исследования и использования.
Практическая ценность и реализация результатов работы. Научные результаты, полученные в диссертации, доведены до практического использования при построении прототипа системы распределенной виртуальной лаборатории, состоящей из географически разнесенных комплектов научного оборудования, компьютеров и пользователей, связанных друг с другом через компьютерную сеть, например, Интернет. Разработанные методы и алгоритмы прошли апробацию и рекомендованы для практического применения в компании ООО «Вимком-Оптик», где предложенные решения используются при построении сетей интерактивных мультимедийных услуг, таких как интерактивное телевидение и видео-по-требованию, а также в разработке приложений телемедицины. Материалы диссертационной работы используются в учебном процессе кафедры «Вычислительные Системы и Сети» (ВСиС) МИЭМ по дисциплинам «Моделирование» и «Новые информационные технологии».
• Достоверность полученных в диссертации результатов и выводов подтверждается их практической реализацией при создании распределенной системы виртуальной лаборатории.
Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:
• Четвертом научно практическом семинаре «Новые информационные технологии» (Москва, 2001);
• Научно - технических конференциях студентов, аспирантов и молодых специалистов МГИЭМ (Москва, 2001, 2003);
• Международной научно-технической конференции, посвященной 80-летию гражданской авиации России (Москва, 2003).
Структура диссертационной работы.
Данная диссертационная работа организована в виде четырех глав. Глава 1 представляет собой детальный аналитический обзор современных интерактивных сетевых приложений, включая анализ перспектив и тенденций в развитии сетевой инфраструктуры, базовых сетевых технологий, архитектур обеспечения качества обслуживания, а также их преимуществ и недостатков. Особое внимание уделено вопросам взаимодействия различных сетевых технологий и архитектур обеспечения качества обслуживания с целью поддержки сетевых услуг реального времени, предъявляющих повышенные требования к своевременности, надежности и качеству обслуживания. Глава 1 завершается обзором основных проблем, выявленных в результате проведенного анализа, решению которых посвящена основная часть диссертации.
Глава 2 содержит основной набор результатов по анализу и развитию математического аппарата разработки и анализа сетевых приложений с особым акцентом на интерактивные приложения потоковой мультимедиа и трехмерной графики в сети Интернет. В качестве основы разрабатываемых методов моделирования и анализа в данной работе предлагается использовать сетевое исчисление, изложению основ которого посвящены Разделы 2.1 и 2.2. В Разделе 2.1 дается определение «мини-плюсового» диоида и его свойств, вводятся такие понятия, как выпуклые и вогнутые функции, мини-плюсовая свертка и ее свойства, суб-аддитивные функции, суб-аддитивное замыкание и его свойства, составляющие основу математического аппарата сетевого исчисления. В Разделе 2.2 дается введение, объяснение и иллюстрация понятий кривых поступления и кривых обслуживания. Такие концепции, как мини-плюсовая свертка и суб-аддитивное замыкание раскрываются в упрощенном виде. В рамках соответствующих постановок задач даются практические определения алгоритмов «дырявого ведра» и «обобщенной ячеечной скорости» (GCRA) и выводятся их фундаментальные свойства. Раздел 2.3 показывает, каким образом фундаментальные результаты Раздела 2.2 применяются к сети Интернет. Например, объясняется, почему в интерсети Интегрированных служб Интернета IntServ любой маршрутизатор может быть абстрагирован кривой обслуживания «скорость-запаздывание». Даются также фундаментальные формальные обоснования для некоторых верхних (нижних) границ, используемых для дифференцированных услуг DiffServ.
Глава 3 посвящена применению аппарата сетевого исчисления к решению проблем обеспечения сквозного одинакового КО при передаче непрерывных потоков данных в смешанных сетях. В разделе 3.1 предложенный формальный аппарат применяется к проблеме сглаживания мультимедийных данных в сетях, предлагающих услуги на базе резервирования (ATM или RSVP/IP), для которых известна одна минимальная кривая обслуживания. Раздел 3.2 посвящен рассмотрению проблемы предоставления интегрированных услуг через общедоступную сетевую инфраструктуру. В частности рассматривается существующее решение института IETF: архитектура Интегрированных Служб Интернета IntServ, которая предлагает набор классов обслуживания, определенных рабочей группой IntServ, и протокол резервирования ресурсов RSVP для «оповещения» о требованиях пользователя относительно классов обслуживания и их параметров. Раздел 3.3 рассматривает системы с агрегированным планированием. Т.е. здесь полученные результаты по проблематике группирования потоков применяются к более общей проблематике агрегации потоков. Для этого в работе вводится концептуальная модель агрегации, а затем приводятся простые численные примеры того, как эта схема работает.
Таким образом, во второй и третьей главах показано, что существует целое множество мало исследованных фундаментальных отношений, которые могут быть выявлены с помощью методов сетевого исчисления. Такие качественные результаты, как «формирователи удерживают трафик в границах поступлений» или «одноразовая расплата за заброс трафика» имеют для сетевых инженеров физическую интерпретацию и практическое значение. Все результаты здесь являются детерминированными. Исследование многих отношений между стохастическими системами и детерминированными отношениями, представленных в диссертационной работе, выходят за рамки диссертации и могут стать предметом будущих исследований по сетевому исчислению.
Экспериментальная работа, представленная в главе 4, направлена на исследование вопроса предоставления приложениям гарантированного КО передачи данных (потоковых и нет) в разных сетевых средах. В частности рассматривается обобщение проблемы сетевой мультимедиа, а именно, проблема поддержки непрерывных информационных потоков, генерируемых приложениями распределенных виртуальных сред (РВС). Подобные приложения заслуживают особого внимания в связи с ростом тенденции использования учеными уникального научного оборудования, имеющего современные компьютерные интерфейсы, такого как, например, сканирующие-зондирующие атомные микроскопы (СЗМ), спектрометры, медицинское оборудование отображения информации, хирургические роботы.
В разделе 4.1 рассматривается проблематика определения степени возможного использования существующих методов максимально возможной адаптации передаваемой информации, разработанных для аудио и видео, для реализации требований производительности, предъявляемых к РВС, а также возможность использования сетевых механизмов, предложенных для улучшенного контроля насыщением сети, и средств дифференцированного обслуживания для изоляции потоков нереального времени от потоков реального времени и обеспечения «лучшей - чем - максимально возможная» службы доставки потоков, генерируемых приложениями РВС. Таким образом, предлагаются методы обеспечения гарантированного КО за счет активной работы с очередями маршрутизаторов.
В разделе 4.2 проблема обеспечения сквозного КО исследуется несколько шире, проводится экспериментальное обоснование теоретических выкладок по группированию и агрегации потоков, изложенных в главе 3. Здесь агрегированная система потоков рассматривается более детально и сравнивается с системой изолированных потоков. Представлены несколько простых численных примеров поиска компромисса между распределением ресурсов в и вне ОА, проводится более глубокая численная оценка предложенного механизма в форме «анализа чувствительности» полученных формул к внешним параметрам, таким как спецификации трафика и параметры конфигурации сети. Анализ основывается на экспериментах, проводимых с использованием среды имитационного моделирования, разработанной специально для этих целей, которая позволяет анализировать и визуализировать чувствительность агрегированной системы к изменениям указанных внешних переменных. В качестве основного сетевого ресурса рассматривается скорость обслуживания, поскольку она выглядит более чувствительной к изменениям параметров, и, кроме того, считается, более важным параметром, чем буферное пространство.
Публикации. По теме диссертации опубликовано 7 работ.
Тенденции развития и перспективы сетевых приложений
Конец 20 столетия ознаменовался бурным развитием информационной отрасли. Неустанное развитие программного обеспечения постоянно стимулировало развитие аппаратного обеспечения, что в свою очередь давало возможность увеличения потребностей конечных пользователей. Потребности необходимо удовлетворять, спрос рождает предложение. Программное обеспечение наращивалось, более мощное ПО требовало более мощного аппаратного обеспечения - круг замкнулся и, таким образом, за короткий промежуток времени произошел огромный скачок в развитии информационных технологий.
Следующим шагом в эволюции информационных технологий явилось возникновение и внедрение локально-вычислительных сетей. Развитие и глобализация сетевых технологий происходила в темпе, аналогичном темпу развития информационных технологий в целом. Бурное развитие сетевых технологий вкупе с увеличением потребностей пользователей привело к появлению новых видов информационного обмена. Если на заре компьютерной эры пользователи могли лишь обмениваться данными, то в процессе эволюции пользовательского мировоззрения и отношения к информационным технологиям пользователи сначала получили общее сетевое хранилище данных с возможностью конфиденциального доступа к ним, а затем и возможность обмена информационными сообщениями, переросшее в организацию глобальной (общемировой) электронной почты. Далее (или наряду с вышеперечисленными) появилась возможность проведения сетевых распределенных вычислений, организации распределенных баз данных. Появилась потребность в организации аудио-, а потом и видео конференций по сети. Кроме этого, возникло понятие «виртуальной реальности» и «видео-по-требованию». Все это, а также многое другое (например, распределенные мультимедийные приложения) привело к возникновению целых потоков информации и требованиям непрерывной передачи этих потоков с гарантированным качеством (т.е., по сути, за гарантированное время).
Конечно же, на протяжении всего процесса эволюции пользовательских потребностей и запросов к информационным технологиям, эти потребности в той или иной мере удовлетворялись бурно развивающейся сетевой инфраструктурой. И сегодня мы имеем дело уже не просто с передачей отдельных пакетов информации, но уже с непрерывными потоками данных. Сегодня рынок телекоммуникационных услуг является одним из наиболее динамичных в своем развитии. По мере того, как борьба за сектора телекоммуникационного рынка становится все сильнее и жестче, доходы операторов от традиционных телефонных услуг падают цри одновременном сохранении модели плоской шкалы цен для услуг Интернета. У операторов есть три пути поддержки уровня доходов и повышения прибыльности бизнеса:
На этом фоне происходит революционная миграция. Промышленность цифровой мультимедиа и развлечений, включая как создателей, так и распространителей цифрового содержимого (контента), постепенно уходят от использования своих собственных эксклюзивных линий производства и распространения продукта в сторону платформ и приложений на базе сети Интернет и там сталкиваются с потребностями своих покупателей в получении большей информации, развлекательного контента и более «богатых» мультимедийным содержанием услуг. Это создает сетевым операторам хорошие предпосылки для развития бизнеса в новых сегментах рынка, которые вырастают на основе смешения ранее разделенных миров - мира телекоммуникаций и мира передачи данных, мультимедиа и развлечений.
Новые услуги охватывают спектр от мультимедийных услуг Интернет/Экстранет для профессиональных бизнес-потребителей и услуг распространения мультимедийной продукции, нацеленных на массового покупателя, до персональных и корпоративных коммуникационных услуг на основе видео, включая такие примеры как:
Передача цифровых материалов для производства телевизионных программ, спортивных передач, редактирование и распространение через смешанную (видео и данные) коммуникационную инфраструктуру на базе оптоволокна по HFC-сетям кабельного телевидения, наращенным средствами доступа к Интернет.
Различные виды типовых корпоративных решений, включая приложения видеоконференций, от семинаров с высоким разрешением видео до приложений типа видеофона, а также надежные соединения виртуальных частных сетей VPN (Virtual Private Network) с гарантированной производительностью и гибкой емкостью (пропускной способностью).
Развлекательные услуги, такие как цифровое телевидение, видео-по-требованию (ВПТ), кабельное телевидение с возможностью просмотра DVD и частичное (сеансовое) ВПТ.
Все эти приложения будут иметь различные требования к качеству и пропускной способности сети, от обработки MPEG-кодированного трафика с узкой полосой пропускания до несжатого высококачественного видео, для передачи которого требуются сотни Мегабит (в секунду). И те операторы, которые смогут развернуть сети, способные выдержать проверку на способность удовлетворения подобных требований, могут надеяться на победу в борьбе за эти новые сегменты рынка.
На сегодняшний день в рамках мультимедийной индустрии, произведено большое количество мультимедийной продукции (контента). Контент доставляется между различными сайтами производителей крайне неэффективно одним из следующих способов: Спутниковые каналы - Спутниковым каналам присущ ряд недостатков. Один недостаток заключается в том, что этот способ является весьма дорогостоящим. Другой недостаток заключается в том, что пропускная способность спутникового канала связи ограничена, и видео поток необходимо сжимать. Качество видео сигналов снижается, а для некоторых приложений, таких как производство фильмов или программ телевидения, при редактировании материала требуется высокое качество.
Видеопленки - Когда требуется более высокое качество, и редактирование проходит в несколько этапов, выпуск видео контента необходимо доставить несжатым, в полном студийном качестве. Так как сейчас не существует никаких экономически приемлемых транспортных технологий, которые могли бы это обеспечить, материал записывают на ленту и доставляют вручную, например автомобилем или самолетом. Это -очень длительный и неэффективный способ доставки контента.
Суб-аддитивное замыкание
Резерв - это количество битов данных, которые удерживаются в системе; если мы рассматриваем отдельный буфер, то резерв - это длина очереди. Для сравнения, если система более сложная, то резерв - это число "транзитных" битов в системе в предположении, что мы можем наблюдать вход и выход одновременно. Виртуальная задержка в момент времени / - это задержка, которую испытал бы бит данных, поступивший в момент времени t, если все полученные до него биты были уже обработаны. На рисунке 2.11 резерв, названный х((), показан как вертикальное расхождение входной и выходной функций. Виртуальная задержка представляется как горизонтальное расхождение функций. Если входная и выходная функции непрерывны («жидкая» модель), то легко видеть, что R (/+ /(/)) = R(t), и что d(i) является наименьшим значением, удовлетворяющим данному уравнению.
На рисунке 2.11 видно, что значения резерва и виртуальной задержки для трех моделей немного различаются. Таким образом, задержка, испытываемая последним битом первого пакета, составляет d(2) = 2 единицы времени на первой части рисунка; в то же время на второй части рисунка она составляет d(\) - 3 единицы времени. Все это получено в соответствии с различными предположениями, сделанными для каждой из моделей. Аналогичным образом задержка для четвертого пакета на второй части рисунка составляет /(8,6) = 5.4 единиц времени, что соответствует 2,4 единицам времени ожидания и 3 единицам времени обслуживания. Для сравнения, на третьей части рисунка это эквивалентно d{9) = 6 единицам времени; разница в значениях представляет собой потерю точности из-за дискретизации. 2.2.2 Кривые поступления 2.2.2.1 Определение Кривой Поступления
Предположим, что мы хотим обеспечить гарантии для потока данных. Это требует определенной поддержки со стороны сети, как это описывается в разделе 2.2.6; с другой стороны, мы должны ограничивать объем трафика от источников. В случае сетей интегрированных служб (ATM или Интегрированных служб Интернета) это реализуется с использованием концепции кривой поступления, определяемой ниже.
Определение 2.2.2 (Кривая поступления). При заданной неубывающей функции а, определенной для t 0 (а именно, аєТ), мы говорим, что поток R является ограниченным функцией а тогда и только тогда, когда для всех s t выполняется:
R{t)-R(s) a(t-s) В этом случае мы говорим, что а является для R кривой поступления, или что поток R является а -гладким или а -сглаженным. Заметим, что данное условие выполняется на множестве пересекающихся интервалов, как показано на рисунке 2.12.
Афинные Кривые Поступления: Например, если a(t) = rt, тогда ограничение означает, что в каждом временном окне шириной г количество битов для потока ограничивается величиной rr. В этом случае мы говорим, что имеем поток с ограничением пиковой скорости. Такое происходит, когда поток поступает по каналу, физическая битовая скорость которого ограничена величиной г бит/сек. Поток, в котором единственным ограничением является ограничение пиковой скорости, зачастую (ошибочно) называют потоком с «постоянной битовой скоростью» CBR (constant bit rate), или потоком с «детерминированной битовой скоростью» DBR (deterministic bit rate).
Если мы имеем в качестве кривой поступления функцию a (t) = b, и Ъ есть константа, тогда максимальное количество битов, которое может быть когда-либо передано в потоке, не превышает Ъ.
В общем случае, часто используются аффинные кривые поступления yrb, определяемые как yrb{t) = rt + b для t 0 и 0 - в противном случае (см. каталог неубывающих функций), из-за их связи с механизмом «дырявого ведра». Использование yrh в качестве кривой поступления предоставляет источнику возможность пересылать b бит за раз, но не более чем г бит/сек при длительной работе. Параметры Ъ и г называются допуском на «забросы» трафика (в единицах данных) и скоростью (в единицах данных за единицу времени), соответственно. Рисунок 2.12 иллюстрирует подобное ограничение.
Ступенчатые Функции как Кривые Поступления: Для ATM мы также используем кривые поступления в форме kvr т, где v7. г - это ступенчатая функция, определяемая как vlr(t)= для t 0 и 0 - в противном случае (см. раздел 2.1.3 с каталогом неубывающих функций). Заметим, что v7-r(/)= v7.0(/ + г), таким образом, v7r получается из vT0 путем сдвига влево по оси времени. Параметр Т ("интервал") и г ("допуск") выражаются в единицах времени. Для пояснения использования vTr рассмотрим поток, который пересылает пакеты фиксированного размера равного к единицам данных (например, поток ATM). Предположим, что пакеты отстоят друг от друга на расстояние не менее чем Т единиц времени. Пример - кодировщик голоса с постоянной битовой скоростью, активно генерирующий пакеты с определенным периодом во время разговора, и «молчащий» в противном случае. Такой поток в качестве кривой поступления имеет vTr.
Теперь предположим, что поток мультиплексируется еще с несколькими потоками. Самый простой путь разрешения такой ситуации - поместить в общую очередь пакеты нескольких потоков. Так происходит в рабочих станциях, в операционных системах или в адаптерах ATM. Очередь вносит переменную задержку. Предположим, что она может быть ограничена некоторым значением эквивалентным г временных периодов. Далее мы увидим, как можно обеспечить такое ограничение. Назовем R{t) входной функцией для потока в мультиплексоре, и R (/) - выходной функцией. У пас R (s) R(s - г), из чего мы получаем R (t)- R (s) R(t)- R(s ) kvTfi(t-s + r)= kvTT(t - s).
Следовательно, kvTz является кривой поступления для R . Мы показали, что kvTx является кривой поступления для периодического потока с периодом Т и пакетами постоянного размера к, который вносит переменную задерэ/ску г. Параметр т часто называют «одноточечным изменением задержки ячейки», так как это соответствует отклонению от периодического потока которое молено наблюдать в одной точке.
В целом, функция vTt может использоваться для выражения минимального расстояния между пакетами, как это показывает следующее утверждение. Утверждение 2.2.1 (Интервал между пакетами как ограничение на поступление данных). Рассмотрим поток с кумулятивной функцией R(t), генерирующей пакеты постоянного размера, эквивалентного к единицам данных, с мгновенным поступлением пакетов. Предположим, что время дискретно или время непрерывно, и R -непрерывна слева. Назовем /„ время поступления п-го пакета. Следующие два свойства эквивачентны:
Оптимальное сглаживание и «жадное» формирование
Предоставление интегрированных услуг через общедоступную инфраструктуру часто видится как "святой Грааль" сетевых технологий. Это позволило бы экономить ресурсы в крупных масштабах и оказалось бы более гибким решением в случае, когда общий объем трафика в сети постоянно меняется, как, например, это, происходит сейчас. Поэтому институт IETF разработал так называемую архитектуру интегрированных служб Интернета, которая предлагает набор классов обслуживания, определенных рабочей группой IntServ, и протокол резервирования ресурсов RSVP для «оповещения» о требованиях пользователя относительно классов обслуживания и их параметров (см. [74]). Эта архитектура разработана очень обобщенно (хотя иногда считается весьма сложной), так чтобы все типы приложений имели возможность воспользоваться предлагаемым сетью КО. Однако из-за того, что предоставление КО осуществляется на прикладном уровне (уровне потоков данных приложений), считается, что она не масштабируема на огромные сети, такие как, например, Интернет. Проблема масштабирования возникает главным образом из-за потенциально большого количества потоков в ядре сети и соответствующей сложности классификации и планирования этих потоков во внутренних (промежуточных) узлах сети. Очевидным подходом к этой проблеме является агрегация прикладных потоков в ядре сети, так чтобы внутренним маршрутизаторам было необходимо осуществлять только управление трафиком агрегированных потоков. Этот подход имеет динамический и статический аспект. Динамический аспект заключается в том, как маршрутизаторы могут осуществлять между собой координацию для обеспечения агрегации и сегрегации (разделения) потоков. Здесь необходимо иметь расширение протокола RSVP или альтернативный протокол (как, например, это описано в [66], [62], [73], или [61]). Статический аспект касается, с одной стороны, необходимости распределения ресурсов среди агрегированных потоков и, с другой стороны, вопроса о том, какие потоки должны группироваться вместе.
В этом разделе мы обратимся к статическому аспекту агрегации для случая регулируемого трафика, требующего детерминированных гарантий обслуживания, преимущественно описываемого на специфическом примере потоков ГО архитектуры IntServ. Особенно интересным для нас является класс приложений ГО в силу его сравнительно стабильных, детерминированных гарантий относительно скорости, задержек и потерь. Такие службы будут играть ключевую роль, особенно, для будущих приложений жесткого реального времени и, возможно, даже для критических приложений, как, например, в области телемедицины, так как они способны изолировать работу таких приложений от других менее критических приложений, несмотря на функционирование на той же самой общедоступной сетевой инфраструктуре. Кроме того, возможность строгого математического описания позволяет проводить точный анализ проблемы распределения ресурсов для агрегированных потоков.
Часть сети, которая обрабатывает/"видит" только агрегированные потоки, далее будет называться областью агрегации. Потоки агрегируются исходя из топологии. Это означает, что потоки, которые будут агрегированы, должны использовать один и тот же путь в области агрегации. Как вариант можно было бы использовать подход, базирующийся на классах трафика, когда все пакеты данных, принадлежащие к одному и тому же классу, получают одинаковую обработку внутри области агрегации. Этот подход привел бы к постоянной размерности состояния системы в пределах области агрегации, соответствующей количеству поддерживаемых классов трафика. С другой стороны, топологическому агрегированию требуется состояние системы в рамках области агрегации размерностью 0(п ), где п - число подсоединенных граничных устройств, расположенных вокруг области агрегации, которые производят объединение потоков до их попадания в область агрегации. Несмотря на это явное преимущество классового агрегирования над топологическим, в работах [67], [64] и [72] было показано, что для детерминированных гарантий обслуживания процент использования ресурсов в области агрегации оказался бы чрезвычайно низким. Так как нас в первую очередь интересуют детерминированные службы, мы рассматрим топологический подход к агрегированию, аргументируя это еще и тем, что благодаря тщательному сетевому проектированию области агрегации с введением достаточной избыточности для избежания узких мест в условиях «нормального» трафика, можно получить такую сложность состояния для наихудшего случая, которая предоставляет достаточно «мягкое» ограничение на действительную сложность состояния, наблюдаемого в реальной жизни.
Поскольку мы выбрали топологическую агрегацию, мы будем исследовать однонаправленные (уни-вещательные) потоки, так как вряд ли мульти-вещательные потоки будут совместно использовать одно и тоже частичное дерево мульти-вещания в области агрегации. Но даже если это было бы и так, например, потому что частичное дерево мульти-вещания оказалось тем же самым тандемом (цепочкой) узлов через область агрегации, то полученные ниже результаты все равно оказались бы применимыми. Заметим, что так или иначе однонаправленные потоки можно считать более «вредными» с точки зрения масштабируемости, так как они, как ожидается, будут гораздо более многочисленными, чем мульти-вещательные потоки. Необходимо отметить, что агрегация и группирование потоков - это разные вещи. Под агрегацией мы понимаем основную проблему слияния различных потоков в рамках области агрегации внутри сети. В случае группирования потоков мы рассматриваем всю сеть в качестве области агрегации, т.е. имеем дело с проблемой сквозной агрегации потоков в сети. Итак, в нашей терминологии группирование является специальным (частным) случаем агрегации. Эти различные концепции схематично изображены на рисунке 3.10.
Влияние задержки и ее нестабильности на реализацию тактильной/силовой обратной связи
Вообще говоря, исследования в области коммуникаций реального времени проводятся по двум параллельным направлениям. Наиболее заметной является работа над новыми моделями сетевых служб для Интернет. Существующая модель пересылки пакетов данных с «максимально возможной» эффективностью была предложена таким образом, чтобы имелась возможность ее расширения для включения гарантий КО, включая гарантии пропускной способности и запаздывания. Эта так называемая архитектура Интегрированных Служб Интернета (IntServ) предлагает процедуру «настройки по вызову», когда ресурсы резервируются вдоль пути от получателя(ей) до отправителя, а сетевые коммутаторы отслеживают состояние каждого соединения и распределяют полосу пропускания канала связи в соответствии с требованиями приложения [64]. Из-за проблем со сложностью архитектуры IntServ доминирующей в изучении стала вторая более простая схема архитектуры Дифференцированных Служб (DiffServ). В архитектуре DiffServ меньший акцент делается на сквозных службах и больший - на режимах пересылки на каждом цикле, таких как приоритетная пересылка или пересылка с малой задержкой [71].
Второй по важности областью исследований является разработка механизмов адаптации (форматирования) передаваемой информации для обеспечения максимально возможной сетевой мультимедиа. Здесь руководящим принципом является следующее соображение: при отсутствии моделей гарантированного обслуживания для Интернет, приложения, требующие передачи данных в реальном времени, должны распознавать состояние насыщения в сети и адаптировать выдаваемые ими в сеть информационные потоки для максимизации вероятности своевременной доставки. Главными предпосылками этому являются, во-первых, тот, факт что пропускная способность сети при ее усреднении вдоль достаточно длительных интервалов времени является достаточной для некоторых минимально приемлемых операций приложения, и, во-вторых, то, что приложения обладают достаточной гибкостью, присущей тому способу, которым создаются информационные потоки, так что они способны адаптироваться к естественным изменениям в доступной пропускной способности сети.
Эта часть главы посвящена проблеме сглаживания эффектов от большой задержки и ее нестабильности при передаче данных, а также важной проблеме потери пакетов данных. В следующем разделе этой главы мы рассмотрим подход DiffServ к снижению этих потерь.
Большие величины задержки и нестабильности задержки при передаче данных вызваны ростом очередей в сети. Процессы отображения информации для периодически генерируемых данных требуют, чтобы единицы информации (кадры) приходили к получателю через регулярные (точные) интервалы времени для избежания «пауз» при воспроизведении. При возрастании и сокращении очередей в сети соответствующим образом изменяется и задержка передачи пакетов данных. Очевидным решением по смягчению эффекта от нестабильности задержки является организация буфера на стороне получателя для сглаживания процесса приема пакетов данных. Если размер буфера равен отношению размера максимально возможной сквозной задержки к периоду времени одной единицы информации, то воспроизведение будет плавным, без «пауз», если буфер будет заполняться до инициации процесса воспроизведения. Однако здесь приходится делать ясный выбор. Несмотря на то, что «глубокий» буфер гарантирует непрерывность воспроизведения, каждый пакет испытывает также эффект задержки, как если бы с ним произошел случай максимальной сетевой задержки. Если случай максимальной задержки является редким, то время запаздывания, связанное с накоплением данных для их последующего воспроизведения, может оказаться неоправданно большим. Более «мелкий» буфер (или его полное отсутствие) может привести к появлению пауз в процессе воспроизведения, но при этом гарантирует, что запаздывание на стороне получателя минимально.
Учитывая то, что в общем случае невозможно определить наихудший вариант сквозной задержки пакета, общепринято, что мультимедийные приложения используют алгоритмы управления буферами для динамической установки размера (глубины) буфера воспроизведения. Эти так называемые «эластичные» схемы буферизации определяют уровень насыщения (состояние очередей) в сети и в соответствии с ним устанавливают глубину буфера. Например, для экспериментальной РВС «виртуальной лаборатории» мы адаптировали схему управления буфером воспроизведения на стороне получателя, называемую «мониторингом очередей» [70]. Мониторинг очередей основан на том, что если при наблюдении в течении заданного интервала времени объем занятости буфера остается постоянным, то мгновенная скорость поступления данных является такой же, как и скорость воспроизведения (независимо от реального количества единиц потока информации в очередях). Это подразумевает, что относительно длительности одной единицы потока информации, степень нестабильности задержки равна нулю. Если объем занятой части буфера меняется с течением времени на ±1 элемент, то степень нестабильности задержки эквивалентна длительности 1 единицы потока информации. В общем случае, если объем занятой части буфера получателя изменяется с течением времени на ±к элементов, то степень нестабильности задержки совпадает с длительностью к единиц потока информации.
Второе ключевое наблюдение заключается в том, что если объем занятой части буфера получателя изменяется с течением времени только на ±к элементов, то буфера глубиной к вполне достаточно для сглаживания эффекта от нестабильности задержки, испытываемой в данное время. В частности, в этой ситуации нет смысла поддерживать буфер глубиной большей, чем к элементов, так как это только увеличивает конечную задержку на накопление информации для последующего воспроизведения. Эти два наблюдения вместе образуют основу алгоритма управления буферами. Можно отслеживать изменение объема занятой части буфера с течением времени и использовать это значение как мерило текущей степени нестабильности задержки. Также эту меру можно использовать для динамической установки глубины (размера) буфера.
В нашей «виртуальной лаборатории», имитируемое научное оборудование использует мониторинг очередей на клиентском персональном компьютере (ПК) для управления очередью единиц информации, поступающих от научного оборудования (например, в случае с AM - с отдельных позиций щупа манипулятора). Каждой позиции в очереди соответствует некое число (значение счетчика) и временной порог. Счетчик для позиции к в очереди отражает наиболее свежие данные о длительности интервала времени (в единицах временных интервалов между поступлениями пакетов данных), в течение которого очередь непрерывно содержала не меньше к элементов. Когда пакет поступает к получателю, и очередь воспроизведения содержит п элементов, счетчики для позиций с 1-й по п-ю наращиваются на единицу. Если счетчик для некоторой позиции к в очереди между 1-й и /7-й превышает свой порог, то приходящие пакеты теряются. Это указывает на то, что так как очередь содержала по крайней мере к элементов в течение достаточно долгого времени, то предполагается, что текущий уровень нестабильности задержки меньше, чем к временных интервалов между поступлениями единиц информации. За счет потери пакетов данных время запаздывания поступающих новых единиц информации, затрачиваемое на накопление информации для воспроизведения, снижается за счет снижения времени, которое они будут тратить в очереди получателя. Однако потеря пакетов данных проявляется как «пауза» в воспроизведении потока. Таким образом, мы должны выбирать между непрерывным воспроизведением и воспроизведением с коротким запаздыванием - это фундаментальная проблема выбора для потоковых приложений. Для информации, генерируемой и воспроизводимой непрерывно и с постоянной скоростью, существует только один путь уменьшения задержки, который заключается в пропуске отдельных единиц потока информации (кадров).
