автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Разработка и анализ распределенных систем интерактивной мультимедиа и графики в глобальных сетях

На правах рукописи

КУТНЕНКО Василий Васильевич

«Разработка и анализ распределенных систем интерактивной мультимедиа и графики в глобальных сетях»

Специальность 05.13.13 - «Телекоммуникационные системы и компьютерные сети»

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва-2004

Работа выполнена в Московском государственном институте электроники и математики

Научный руководитель:

кандидат технических наук, доцент Панфилов Петр Борисович

Официальные оппоненты:

доктор технических наук,

профессор Соломенцев Виктор Владимирович

кандидат технических наук,

доцент Будихин Анатолий Владимирович

Ведущая организация:

Институт проблем передачи информации РАН

Защита диссертации состоится «25» января 2005г. в 16 час 00 мин. На заседании диссертационного совета Д 212.133.03 в Московском государственном институте электроники и математики по адресу:

Москва, Б. Трехсвятительский пер., д. 3/12-1, стр.8

С диссертацией можно ознакомиться в Научной библиотеке Московского государственного

института электроники и математики по адресу:

109028, Москва, Б. Трехсвятительский пер., д. 3/12-1, стр.8

Автореферат разослан «_» декабря 2004 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук

доцент

И.В. Прокофьев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы Появление в 1994 году глобальной сети Интернет и последовавший бурный рост «всемирной паутины» (WWW) кардинальным образом изменили мир телекоммуникаций. Первое десятилетие развития Интернета ознаменовалось массовым подключением обычных пользователей к глобальной сети и развитием целого спектра сетевых приложений, подавляющее большинство которых было ориентировано на статические услуги типа поиска и просмотра информации и электронной почты. Сегодня сообщество пользователей глобальной сети Интернет стоит на пороге качественного скачка в направлении полноценных интерактивных мультимедийных приложений, то есть услуг с богатым мультимедийным содержанием, включая качественное потоковое видео и аудио, трехмерную графику, виртуальную реальность в дополнение к обычной информации.

По мере того, как ориентированные на мультимедиа услуги начинают доминировать в сети, происходит очередной технологический сдвиг - развертывание инфраструктуры, которая способна справляться с большим количеством потоковых услуг при одновременной поддержке высокого качества обслуживания. Сеть Интернет в том виде, как она функционирует сегодня, без дополнительных затрат на избыточные сетевые ресурсы не способна поддерживать каких-либо услуг, кроме приложений «максимальной возможности» типа «отослал и молись, чтобы дошло». В реальной жизни применимость экстенсивного подхода к решению проблем качества сетевого трафика, базирующегося на примитивном запасании избыточных ресурсов, серьезно ограничена чисто экономическими причинами. А с учетом растущей конкуренции различных сетевых технологий (IP и ATM) это создает проблемы «маршрутизации трафика в смешанных сетях» и «обеспечения гарантированного сквозного качества обслуживания (КО) на всем пути трафика в смешанной сети». Поэтому тематика проводимых в диссертационной работе исследований и полученные результаты являются актуальными и имеют важное практическое значение.

Цель диссертационной работы состоит в развитии теоретических основ и разработке математического аппарата, методов моделирования и анализа, которые обеспечат лучшее понимание проблем потоковых приложений, возникающих в компьютерных сетях. Эти формальные методы и средства призваны обеспечить более адекватное представление некоторых фундаментальных свойств сетей интегрированных услуг, управления потоками, составления расписаний и определения размеров буферов или величин сетевых задержек при проектировании приложений распределенных систем мультимедиа и виртуальной реальности. Для достижения данной цели в работе сформулированы и решены следующие задачи:

• Анализ особенностей построения и функционирования сетевых потоковых приложений в локальных и глобальных сетях ЭВМ.

• Анализ базовых сетевых архитектур глобальных сетей и соответствующих архитектур качества обслуживания, классификация моделей взаимодействия и путей организации взаимодействия сетевых архитектур при построении смешанных сетей.

• Выбор и обоснование базового математического аппарата для моделирования и анализа фундаментальных проблем потоковых приложений в сетях.

• Разработка моделей потоков и моделей планировщиков для сетевых узлов на основе кривых поступления и обслуживания и их применение для решения проблем буферной памяти, пропускной способности и задержек при обеспечении гарантий качества обслуживания потокам мультимедийных и графических данных.

• Разработка методов и средств агрегации прикладных потоков в сетях интегрированного обслуживания с проведением точного анализа проблемы распределения ресурсов для агрегированного трафика.

• Разработка программного обеспечения системы «Виртуальная лаборатория» на базе интерфейса виртуальной реальности для управления научным оборудованием по сети. Методы исследования. При решении поставленных в диссертации задач использованы

концепции и методы общей теории систем, дискретной математики, теории вычислительных сетей, математический аппарат сетевого исчисления, методы имитационного моделирования.

К основным научным результатам, представляемым в диссертационной работе и выносимым на защиту, относятся:

• Результаты анализа действующих сетевых интерактивных систем мультимедиа и трехмерной графики (виртуальной реальности).

• Математическая модель описания предметной области потоковых приложений в глобальных сетях с использованием математического аппарата сетевого исчисления.

• Метод адаптации аудио/видео информации для сглаживания эффекта от нестабильности задержки в потоках данных распределенной системы мультимедиа и виртуальной реальности.

• Подход «активного управления очередями» к реализации дифференцированных служб в маршрутизаторах для защиты TCP-приложений от непрерывных потоковых приложений реального времени и для обеспечения наилучшей службы доставки пакетов данных.

• Реализация разработанных моделей и методов в виде программного комплекса распределенной системы виртуальной реальности и методик его исследования и использования.

Практическая ценность и реализация результатов работы. Научные результаты, полученные в диссертации, доведены до практического использования при построении прототипа системы распределенной виртуальной лаборатории, состоящей из географически разнесенных комплектов научного оборудования, компьютеров и пользователей, связанных друг с другом через компьютерную сеть, например, Интернет. Разработанные методы и алгоритмы прошли апробацию и внедрены для практического применения в Группе Компаний «Вимком», где предложенные решения используются при построении сетей интерактивных мультимедийных услуг, таких как интерактивное телевидение и видео-по-требованию, а также в разработке приложений телемедицины. Материалы диссертационной работы используются в учебном процессе кафедры «Вычислительные Системы и Сети» (ВСиС) МИЭМ по дисциплинам «Сети ЭВМ» и «Новые информационные технологии».

Достоверность полученных в диссертации результатов и выводов подтверждается их практической реализацией при создании распределенной системы виртуальной лаборатории.

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на: Четвертом научно-практическом семинаре «Новые информационные технологии» (Москва, 2001); Научно-технических конференциях студентов, аспирантов и молодых специалистов МГИЭМ (Москва, 2001, 2003); Международной научно-технической конференции, посвященной 80-летию гражданской авиации России (Москва, 2003); Заседаниях кафедры ВСиС МИЭМ.

Публикации. По теме диссертации опубликовано 7 работ.

Структура и объем диссертации. Диссертация состоит из введения, 4 глав, заключения, списка литературы из 90 наименований. Диссертация содержит 182 страницы текста, 55 рисунков, 9 таблиц.

СОДЕРЖАНИЕ РАБОТЫ Во введении обоснована актуальность темы диссертации, приведен обзор публикаций по этой теме, сформулирована цель исследований, кратко изложены содержание и основные результаты по главам, охарактеризованы их научная новизна и практическая ценность.

Первая глава представляет собой детальный аналитический обзор современных интерактивных сетевых приложений, включая анализ перспектив и тенденций в развитии сетевой инфраструктуры, базовых сетевых технологий, архитектур обеспечения качества обслуживания, а также их преимуществ и недостатков. Особое внимание уделено вопросам взаимодействия различных сетевых технологий и архитектур обеспечения качества обслуживания с целью поддержки сетевых услуг реального времени, предъявляющих повышенные требования к своевременности, надежности и качеству обслуживания. Глава 1 завершается обзором проблем, выявленных в результате анализа, решению которых посвящена основная часть диссертации.

Вторая глава содержит основной набор результатов по анализу и развитию математического аппарата разработки и анализа сетевых приложений с особым акцентом на интерактивных приложениях потоковой мультимедиа и трехмерной графики в сети Интернет. В качестве основы разрабатываемых методов моделирования и анализа в данной работе предлагается использовать аппарат сетевого исчисления, представляющего собой набор последних разработок в области математической теории диоидов и, в частности, мини-плюсового диоида (также называемого мини-плюсовой алгеброй). Таким образом, сетевое исчисление относится к тому же семейству «экзотических алгебр», что и сети Петри, и представляет собой математический аппарат с высокой описательной сложностью, который обеспечивает средства анализа таких создаваемых человеком систем, как параллельные программы, цифровые электронные схемы и, конечно, коммуникационные сети.

В Разделе 2.1 излагается концепция «мини-плюсовой» алгебры (диоида). В отличие от традиционной алгебры, где мы обычно имеем дело с алгебраической структурой или

<Z,+,x>, в диоиде операция «+» превращается в операцию « Л» (вычисления инфимумума inf или минимума min), а операция «х» - в операцию «+». Во множество элементов включается

элемент +°о, так что алгебраическая структура диоида выглядит как <Жи{+°о},л,+ >

Главными объектами для операций мини-плюсовой алгебры являются элементы множества F неотрицательных неубывающих последовательностей или функций таких, что f(t) = О для t<0. Обозначение f + g (соответственно, fAg) представляет поточечную сумму (соответственно, минимум) функций f и g: (f+g)(t)=f(t) + g(t) и (f /g)(t) = f(t)A g(t) • Обозначение / ¿(=,ä)g указывает на то, что Vi /(i)^ (=,>)g(i). В мини-плюсовой алгебре интеграл функции f превращается в последовательности - в

ieÄM.V leZmi.bsssl

К наиболее важным функциям из множества F относятся функции пиковой скорости Ля , «импульс-задержка» ST, «скорость-запаздывание» ßnT, аффинная yr)i, шаговая ит, и

ступенчатая vT. Путем комбинирования этих функций с использованием операций мини-плюсовой алгебры можно строить кусочно-линейные функции общего вида из множества F. Важными классами функций в сетевом исчислении являются выпуклые и вогнутые функции, а также суб-аддитивные функции, определения которых и примеры также приводятся в этом разделе. Рассматривается и такое базовое понятие мини-плюсовой алгебры, как субаддитивное замыкание функции, в основе которого лежит операция мини-плюсовой свертки. При этом традиционное определение операции свертки двух функций в мини-плюсовой алгебре превращается в (/® g)(i)= inf {/(/-i)+ g(s)} (если t<0, (/®g)(?) = 0), а операция

развертки функции f по g выглядит как . Последняя операция

позволяет просто выражать такие важные в сетевом исчислении величины, как максимальное вертикальное и горизонтальное отклонения двух функций f иgиз множества F.

В Разделе 2.2 вводятся понятия кривых поступления и обслуживания. Потоки данных удобно описывать посредством кумулятивной функции R(t), определяемой как число битов, «видимых» в потоке за интервал времени [0, t]. Обычно принимается соглашение о том, что R(0) = 0. Кумулятивная функция R(t) - это всегда неубывающая функция, принадлежащая пространству F. Можно рассматривать следующие типы моделей:

• модель дискретного времени: feN ={0,1,2,3,...};

• «жидкая» модель: t6 R+ = [0, +оо) и R(t) - это непрерывная функция;

• общая модель (непрерывного времени): t€ &1" и R(t) непрерывна слева или справа. Модели дискретного времени, в основном, используются в контексте сетей ATM; и

наоборот, обработка пакетов переменного размера обычно выполняется моделью непрерывного времени (не обязательно «жидкой»).

Рассмотрим некоторую систему S, которую представим в виде «черного ящика»: система S получает входные данные, описываемые их кумулятивной функцией R(t), и отправляет данные с некоторой переменной задержкой. На выходе системы S имеем кумулятивную функцию R*(t). В качестве системы Sможно рассматривать отдельный буфер, обслуживаемый с постоянной скоростью, сложный коммуникационный узел, или даже всю сеть. Из входной и выходной функций системы S можно вывести две важные величины: резерв и задержку. Резерв - это количество битов данных, удерживаемых в системе. Если система S- это отдельный буфер, то резерв - это длина очереди. Если система более сложная, то резерв - это число «транзитных» битов в системе в предположении, что вход и выход наблюдаются одновременно. Виртуальная задержка в момент времени t - это задержка, которую испытал бы бит данных, поступивший в момент времени t, если все полученные до него биты были бы уже обработаны. Формально, для системы без потерь резерв в момент времени / определяется как разность R(t)-R*(t), в то время как виртуальная задержка есть d{f) = illf [г R (/ + т)}. При графическом представлении резерв x(t) показывается как

вертикальное отклонение входной и выходной функций системы, а виртуальная задержка d(f) - как горизонтальное отклонение. Если обе функции непрерывны («жидкая» модель), то R (t+d(t)) = R(t), и d(t) есть наименьшее значение, удовлетворяющее данному уравнению.

Обеспечение гарантий потоку данных требует определенной поддержки со стороны сети. С другой стороны, необходимо ограничивать объем трафика от источников. В случае сетей интегрированных служб (ATM или Интегрированные службы Интернета IntServ) это реализуется с использованием концепции кривой поступления.

Определение (Кривая поступления). При заданной неубывающейфункции а. определенной для ti.0(m.e. аеТ), говорят, что потокRявляется ограниченнымфункцией а тогда и только тогда, когда для всех s <t выполняетсяусловие: R(t)-R(s)< a(t-s)

Принято говорить, что а является для потока R(t) кривой поступления, или что поток R является а-гладким или а-сглаженным. Заметим, что данное условие выполняется на множестве пересекающихся интервалов, как показано на рисунке.

Рисунок. Пример ограничения потока с помощью кривой поступления.

Суть концепции кривой поступления связана с фундаментальными отношениями в мини-плюсовой алгебре. Эта связь выражается в том, что выбор кривых поступления должен ограничиваться функциями определенного вида, называемыми «хорошими» функциями, т.е. такими функциями аеТ, для которых выполняется любое из следующих условий:

1. асуб-аддитивна и о(0)= 0;

2. а = а®а;

3. а0а = а;

4. а = а (суб-аддитивное замыканиес

Основной результат использования кривых поступления заключается в том, что любая кривая может быть заменена ее суб-аддитивным замыканием, т.е. «хорошей» кривой поступления, т.е. утверждение, что поток ограничен неубывающей функцией а , равносильно утверждению, что он ограничен суб-аддитивным замыканием этой функции а .

Одним из основных принципов сетей интегрированных услуг является наложение ограничений кривой поступления на поток. Для проведения резервирования сетевые узлы, в свою очередь, должны предоставить потоку некоторые гарантии, что осуществляется планировщиками пакетов. Детали пакетного планирования описываются с помощью кривой обслуживания.

Определение (Кривая обслуживания). Рассмотрим систему S и поток через S с входной функцией и выходной функцией Щ^. Система 8 предлагает потоку кривую

обслуживания тогда и только тогда, когда ¡1 еИ и В.' 2: Я® ¡}

Иначе говоря, выходная функция К' должна быть выше кривой й®/?, которая является самой низкой огибающей всех кривых Л-> й((0)+/?(/—/0), как показано на рисунке, где представлена часто используемая кривая обслуживания типа «скорость-запаздывание».

Рисунок. Определение понятия кривой обслуживания.

Примеры фундаментальных кривых обслуживания, которые используются в реальной жизни, включают кривые «узла с гарантированной задержкой», «узла приоритетного планирования без вытеснения задач», «узла переменной пропускной способности», а также важный класс сетевых узлов, объединенных общим понятием «строгих кривых обслуживания».

Определение (Строгая кривая обслуживания). Будем говорить, что система Sпредлагает потоку строгую кривую обслуживания если в течение любого зарезервированного периода времени длительностью и выходной поток поменьшеймереравен ¡¡(л).

Свойство строгости кривой обслуживания является удобным свойством визуализации концепции кривой обслуживания: в данном случае /¡(и) является минимальным объемом услуг, гарантированно предоставляемым в течение периода занятости. Примером сетевого узла, предлагающего потоку строгую кривую обслуживания вида /?(() = г/, является узел, реализующий схему планирования GPS, известную как «обобщенное разделение процессора».

Комбинирование гарантий кривой обслуживания с ограничениями кривой поступления образует формальную основу для вычисления детерминированных ограничений, используемых в сетях интегрированных услуг. Важными результатами применения математического аппарата сетевого исчисления являются такие ограничения для систем без потерь с гарантированными услугами, как ограничение резерва, ограничение задержки и ограничение выходного потока, задаваемые следующими выражениями.

Теорема. Пусть имеется поток, ограниченный кривой поступления а, который проходит через систему, предлагающую кривую обслуживания Тогда для всех t

1)резервR{t)-К()удовлетворяетограничению^!)-R'(i) <supaa{a{s) ~ ffls))

2)виртуальнаязадержкаё^)удовлетворяетограничению d(t) < h(a, ¡!).

3) выходной поток ограничивается кривой поступления а ={а£>р).

Раздел 2.3 показывает, каким образом фундаментальные результаты Раздела 2.2 применяются к сети Интернет. Например, объясняется, почему в интерсети интегрированных услуг Интернета любой маршрутизатор может быть абстрагирован кривой обслуживания «скорость-запаздывание». Также приводятся фундаментальные обоснования для некоторых верхних (нижних) ограничений, используемых для сетей дифференцированных услуг.

Глава 3 посвящена применению аппарата сетевого исчисления к решению проблем обеспечения сквозного одинакового КО при передаче непрерывных потоков данных в смешанных сетях. В разделе 3.1 предложенный формальный аппарат применяется к проблеме сглаживания мультимедийных данных в сетях, предлагающих услуги на базе резервирования (ATM или RSVP/EP), для которых известна одна минимальная кривая обслуживания.

В качестве основы для выработки математических соотношений рассматривается обобщенная прикладная система, реализующей интерактивную сетевую потоковую услугу типа «видео-по-требованию», как это представлено на следующем рисунке. Здесь видеопоток, хранимый на диске видео-сервера, доставляется по сети клиенту. На стороне отправителя, сглаживающее устройство считывает кодированный поток видео R(t) и пересылает поток x(t), который должен соответствовать кривой поступления <7, которая считается «хорошей» функцией, т.е. суб-аддитивной и такой, что о(0)=0. На практике простейшей и наиболее популярной сглаживающей кривой является кривая постоянной скорости (или, что то же самое, с ограничением пиковой скорости) <т = Л,, для некоторой r>0. На стороне получателя поток видео R(t) будет воспроизводиться через D единиц времени, представляющих задержку воспроизведения: выходная функция буфера декодера В, таким образом, должна быть R(t-D).

Рисунок. Сглаживание ввдеопогока в рамках отдельной сети.

Сеть предлагает гарантированные услуги потоку х. Если обозначить выходной поток как у, то в общем случае невозможно представить у как функцию от х. Однако гарантии услуг можно выразить с помощью кривой обслуживания ß. Например, согласно предположениям института IETF маршрутизаторы RSVP предлагают кривую обслуживания ß типа «скорость-запаздывание». Другой пример - это полностью «прозрачная» для потока сеть (т.е. сеть, которая не вносит в поток никакой нестабильности задержки или ограничений скорости, даже если она и вносит фиксированную задержку). Такая сеть называется нулевой сетью. Она предлагает кривую обслуживания ß(t)=Sn{() (типа «импульс-задержка» с нулевой задержкой).

Для сохранения простоты математических манипуляций можно предположить, что объем буфера кодера на стороне видео-сервера достаточно велик для хранения всех данных потока. С другой стороны, буфер получателя (декодера) - это намного более дефицитный ресурс. Его конечный объем обозначается В. Так как поток записан заранее и хранится на видео сервере, то сглаживатель может осуществлять предварительную выборку и пересылку данных с опережением расписания. Предполагается, что сглаживатель может просматривать данные на d временных интервалов вперед. Эта задержка упреждения может иметь величину в пределах от нуля (при наиболее жестких ограничениях, когда предварительное считывание данных невозможно) и вплоть до длины всего потока. Сумму задержки упреждения и задержки воспроизведения называют общей задержкой, и обозначают Т: T=D+d.

Общий алгоритм решения проблемы сглаживания мультимедийных данных в сети при использовании положений сетевого исчисления заключается в следующем: Шаг 1. Вычисление минимальных требований к параметрам D, d и В, гарантирующих

передачу данных без потерь для заданных кривых сглаживания и обслуживания (Tand ß, Шаг 2. Вычисление всех стратегий планирования для сглаживателя, удовлетворяющих параметрам передачи, рассчитанным на предыдущем шаге. Результирующее планирование называется «оптимальным сглаживанием». Шаг 3. Вычисление окончательных выражений для минимальных значений D, T=D+d и В, необходимых для сглаживания без потерь данных.

Ограничения, определяющие проблему сглаживания (потока, его гладкости, запаздываний воспроизведения и упреждения) формализуются в виде системы неравенств:

Решение х проблемы сглаживания существует тогда и только тогда, когда одновременно выполняются оба этих неравенства, что равносильно требованию того, чтобы максимальное решение для первого неравенства было больше, чем правая часть второго неравенства для всех t. Это максимальное решение есть:

(')=а(») Л {(а ® Я X» + й)} Л {(а в К\1- В) ■+■5}.

Вычислить наименьшие значения задержки воспроизведения D, общей задержки Т и буфера воспроизведения В, обеспечивающие существование решения проблемы сглаживания, можно благодаря следующей теореме.

Теорема. Наименьшие значения В, Т и В, обеспечивающие сглаживание без потерь к «хорошей» кривой через сеть, предлагающую кривую обслуживанф,таковы

От = й(д, {р®о)) = Ы{1гО:(К0{р® сг)Х- () 5 0} Т^ = А ((Я04(/! ® (т))=И Цъ 0: ((Й0Я)0(/3 ® «т)Х- /) 2 0} В„ц = у{(Я0Я),(Р ® сг)) = ((Я0Л)0(£ ®

гдеh и vобозначаюm, соответственно, горизонтальное и вертикальное отклонения функций.

Стратегией оптимального сглаживания является решение x(t) проблемы сглаживания без потерь, где параметры D, T=D+d и В принимают минимальные значения, задаваемые теоремой. Представленное выше максимальное решение является «оптимальным» в смысле этого определения, но оно не является единственным. Пользуясь свойствами операции развертки 0, можно переформулировать неравенства, определяющие проблему сглаживания, и их решение дает нам минимальное решение в виде (/) = (Л0(У? ® (т)Х? - Щ . Любая функция такая, что и , следовательно, также является решением

проблемы сглаживания без потерь для тех же самых минимальных значений задержки воспроизведения, задержки упреждения и объема буфера на стороне клиента. Это дает нам множество «оптимальных» решений. Среди них можно выбрать конкретное решение, которое минимизирует другие показатели призводительности, например, вариативность скорости.

В работе представлены примеры решения проблемы оптимального сглаживания без потерь «трассы» трафика МРЕО-кодированного видео R(t) для разных комбинаций сглаживающей кривой и кривой обслуживания, например, сглаживающей кривой постоянной скорости (СБЯ) а = X, с кривой обслуживания /?(0=|5Ь(0 или сглаживающей кривой переменной скорости (УБЯ) а — Ур,м лУг.ь с кривой обслуживания /?(0=А! г Также решается и двойственная проблема расчета минимальной скорости г, необходимой для доставки видео с требуемым запаздыванием воспроизведения D запаздыванием упреждения d и объемом клиентского буфера В.

Более сложной является ситуация, когда клиента от видео сервера отделяют две сети: основная (магистральная) сеть, предлагающая потоку кривую обслуживания /?1, и сеть локального доступа, предлагающая кривую обслуживания , как показано на рисунке.

Хранилище промежуточного узла —

?Г

Сглаживатель Сглаживатель

Видео „ дисплеи| клиента

воспроиЗвёдения клиента

Рисунок. Сглаживание через две сети узлом локального кэширования.

Эта ситуация моделирует интеллектуальное динамическое кэширование, часто реализуемое в головных узлах локальных сетей. Здесь необходимо вычислять как требования к параметрам D, d и В, так и к буферу X этого промежуточного узла. В этом случае необходимо рассчитать два потока: первый x(t) на входе в основную сеть, и второй x(t) на входе в сеть локального доступа, как показано на рисунке. Однако, в общем, подход к решению проблемы оптимального сглаживания остается аналогичным случаю одной сети, т.е. сначала вычисляется максимальное решение, а затем получаются ограничения на параметры D,T (и, следовательно, d), Хи B, обеспечивающие существование этого решения.

Ограничения на оба потока, определяющие проблему сглаживания через две сети, формализуются следующей системой неравенств:

х, (/)<£„{/) л R(t + d) л (<j, ® *,Х/)л(х2(г)+Х) *2(t) 5 {й(г - /))+5}л (Д ® х,ДОл (ст2 ® *2Х<)

Для решения этой системы можно применить тот же метод, что и в случае одной сети, за исключением, того, что теперь размерность системы J есть 2 вместо 1, и можно воспользоваться элементами матричной алгебры для решения. В этом случае две координаты максимального решения выглядят как

*,„»(<)= <х,(г)л{а(0 + *}л(<г, ® R\t + ¿)л{(а ® R\t + d)+ X]

л {(сг, ® аг ® R\t-D) + В + Х} л {(а ® Rfa - D) + В + 2Х] »!-(')= «(')а(«® Rlt + d)A {(аг ® Rit - D)+ В} A{(a®R\t-D)+B + X}

С помощью следующей теоремы можно выразить ограничения на X, В, D и d, которые гарантируют существование решения, потребовав, чтобы х2щ() было больше, чем x(t). Теорема. Сглаживание без потерь потока к (субаддитивным) кривым 0\ и соответственно, через две сети, предлагающие кривые обслуживания и fyu имеет решение тогдаитолькотогда,когдаО, Т,ХжВудовлетворяютследующемумножествунеравенств, с параметром а, задаваемымкак а = 17, ® сгг ® ¡пф'"1'+пх}= а, ® СТ2 ® Д ® Д + X :

((Л0Л)0((г2®Д2)Хо)^г {{Rm)Z{a® В + X

По аналогии с вариантом одной сети в работе показано, как осуществляется использование данных неравенств при вычислении «оптимальных» значений Д Ти В для случая двух сглаживающих кривых постоянной скорости (CBR) а, = Лп и <т2=Л^ в предположении, что каждая сеть предлагает кривую обслуживания «скорость-запаздывание» Д=Д^, i = 1, 2. Здесь решение проблемы усложняется тем, что надо рассматривать разные

варианты в зависимости от значения X, а именно: l)XèrLi; 2) Q<X<rLi~, и 3)Х= 0 < rL\.

В работе показано, что для сглаживающих кривых постоянной скорости и кривых обслуживания «скорость-запаздывание» размер буфера клиента В можно снизить за счет реализации специальной стратегии сглаживания в промежуточном узле вместо планирования на основе очереди FIFO.

Раздел 3.2 посвящен рассмотрению проблемы предоставления интегрированных услуг через общедоступную сетевую инфраструктуру. В частности рассматривается существующее решение института IETF: архитектура Интегрированных Служб Интернета IntServ, которая предлагает набор классов обслуживания, определенных рабочей группой IntServ, и протокол резервирования ресурсов RSVP для «оповещения» о требованиях пользователя относительно классов обслуживания и их параметров. Эта архитектура разработана очень обобщенно, так чтобы все типы приложений имели возможность воспользоваться предлагаемым сетью КО.

Однако из-за того, что предоставление КО осуществляется на прикладном уровне, считается, что она не масштабируема на огромные сети, такие как, например, Интернет. Проблема масштабирования возникает главным образом из-за потенциально большого количества потоков в ядре сети и сложности их классификации и планирования во внутренних узлах сети.

В работе предлагается решение, связанное с агрегацией прикладных потоков в ядре сети («остовной», магистральной сети), так чтобы внутренним маршрутизаторам было необходимо осуществлять управление только трафиком агрегированных потоков. Особое внимание уделено проблематике агрегации, связанной, с одной стороны, с распределением ресурсов среди агрегированных потоков и, с другой стороны, с поиском ответа на вопрос о том, какие потоки должны группироваться вместе. Рассматривается случай регулируемого трафика, требующего детерминированных гарантий обслуживания, преимущественно описываемого на специфическом примере потоков гарантированного обслуживания ГО архитектуры ШЗегу. ГО обеспечивает гарантированный уровень скорости, сквозной задержки и отсутствие потерь в очередях тем потокам данных, которые согласуются с заданной спецификацией трафика Т8рес(г,Ь,р,М), которая, по сути, является схемой двойного «дырявого ведра жетонов», характеризующегося следующими параметрами: г - это поддерживаемая скорость «ведра», Ь - это толерантность к «забросам» трафика или глубина «ведра»,р - это пиковая скорость и М- это максимальный размер пакета.

Особое внимание классу приложений ГО уделяется потому, что такие услуги будут играть ключевую роль в будущих приложениях жесткого реального времени и, возможно, даже в таких критических приложениях, как, например, в области телемедицины, так как они способны изолировать работу таких приложений от других менее критических приложений, несмотря на функционирование на той же самой общедоступной сетевой инфраструктуре. Кроме того, возможность строгого математического описания позволяет проводить точный анализ проблемы распределения ресурсов для агрегированных потоков.

Математика ГО в основном базируется на результатах сетевого исчисления по кривым поступления и обслуживания. В случае ШЗегу кривая поступления, соответствующая спецификации трафика Т8рес(г,Ь,р,М), задается как

тогда как кривая обслуживания для ГО представляет собой е(() = ЯА - V)*

, где V = — + И и Я

Л

- это скорость обслуживания в предположении, что выполняется условие стабильности Я '¿.г. Здесь члены С и В представляют, соответственно, зависимое и независимое от скорости отклонение пакетного планировщика от идеальной модели потока («жидкой» модели). Эти ошибочные члены суммируются вдоль всего пути передачи данных по каждому серверу/маршрутизатору на протяжении всей фазы оповещения. Для такой сложной кривой поступления, как в случае двойного «ведра жетонов» спецификации Т8рес(г,Ь,р,М), ограничение на значение сквозной задержки получается в виде

(Ь-МХр-Я) М + С

«О»-г)

М+С

+1>

Если требование к максимальной задержке очереди для получателя составляет dmI¡x, то скорость обслуживания Я (в байтах/сек), которая должна резервироваться в маршрутизаторах на пути от отправителя к получателю, напрямую может быть получена из этих выражений как

Для гарантированного обслуживания без потерь в случае двойного «ведра жетонов» спецификации Т8рее формула для вычисления объема буфера выглядит следующим образом:

Смысл «ошибочных членов» С и D хорошо иллюстрируется случаем использования планировщика схемы «Попакетного Обобщенного Разделения Процессора» PGPS, когда эти члены имеют значения С = М и D = М/с, где М - это максимальный размер пакета, М' - это Максимальный Передаваемый Блок MTU и с - это скорость канала связи. В реальных маршрутизаторах существует также множество других факторов, вносящих свой вклад в эти «ошибочные члены», как, например, издержки канального уровня на сегментацию и сборку (данных) в случае ATM или время чередования ключа для FDDI или сети Token Ring.

Существуют две соответствующие проблемы, связанные с ГО:

1. Данное решение не масштабируется в достаточной степени для использования в «основе» Интернета, так как не поддерживается механизм агрегации из-за обеспечения КО каждому потоку и изоляции потоков между собой. Таким образом, число очередей (а следовательно, и размерность состояния системы) пропорционально числу потоков.

2. Оно непроизводительно расходует много ресурсов, особенно для потоков типа «низкая пропускная способность (скорость), малая задержка».

Агрегируя/группируя потоки ГО можно решить обе проблемы, так как маршрутизаторам в этом случае нужно управлять состоянием меньшей размерности, а результирующие агрегированные потоки получают более высокую пропускную способность.

В данной работе предлагается модель группирования и агрегации потоков данных в сети на базе концепций и математического аппарата сетевого исчисления и выводятся ряд фундаментальных формул для таких потоков. Показывается, как группирование потоков помогает экономить ресурсы в сравнении со случаем изолированных потоков. При этом агрегация и группирование потоков рассматриваются здесь как разные понятия. Под агрегацией понимается основная проблема слияния различных потоков в рамках области агрегации (ОА), представляющей собой часть сети, которая обрабатывает/«видит» только агрегированные потоки. Потоки агрегируются исходя из топологии. Это значит, что потоки, которые будут агрегированы, должны использовать один и тот же путь в области агрегации. В случае же группирования потоков в качестве области агрегации рассматривается вся сеть, т.е. здесь мы имеем проблему сквозной агрегации потоков в сети. Таким образом, группирование является специальным (частным) случаем агрегации.

Для анализа и моделирования группирования потоков в качестве кривой поступления для групповых потоков используется спецификация трафика «суммарная TSpec», как это определено стандартом RFC 2212, т.е. сумма п спецификаций трафика TSpec, задаваемая как

Анализ и оценка эффективности разрабатываемой модели основывается на сравнении скорости для групповых потоков с суммой скоростей для изолированных потоков. При использовании упрощенной модели трафика на базе одиночных «ведер жетонов» Л=(г, Ь) для характеризации изолированных потоков, скорость для системы ^ из я получателей (потоков) с =(г, Ь) и желаемой максимальной задержкой dmaxl равна

6,+С

тогда как для групповой системы из этих и потоков, когда сумма отдельных «ведер жетонов» определяется как «суммарная Т8рес», скорость есть

Эффективность группирования ОБ определяется как разность выделяемых суммарных скоростей обслуживания для потоков с 1-го по и-ный для изолированной и групповой систем:

Таким образом, проблема определения того, какие потоки нужно группировать вместе, формулируется следующим образом:

Для множества из презервированийскорости 1Ь/ = (гь Ь^или Т8рес(г„ Ь„ р,, М) с

заданными с1тса11 найти разбиение на подмножества Р = (Рь ... ,Ртакое, что

максимальна, и к-минимально.

Из выражения для эффективности группирования хорошо видно, что выгодно группировать те потоки, которые имеют одинаковые или, как минимум, близкие требования к задержкам. Поэтому, можно упорядочить потоки по задержкам и ограничить поиск пространством упорядоченных разбиений для оптимального назначения потоков в группы. Теорема. Пуе^Ъ,...,«} естьупорядоченноемножестворезервированийскорост^Ь, -¿1) с 4л<и,/), / = 1,...д Критерийупорядочения есть ¿„ял. Тогдаоптимальноепоскорости разбиение множествана подмножестваявляетсяупорядоченным по ¿„¡а /. Здесь скорость

дляразбиенияР — {Р1, .., Рк] определяетсякакЛ(Р) =

В общем случае, в любой момент времени в сети существует достаточно большое количество потоков, так что можно предположить, что потоки, группируемые вместе, имеют одинаковую задержку. Для п таких потоков с «однородной» задержкой получаем следующее уравнение для эффективности группирования в случае простой модели (при = ¿„„V/):

■ Ь, +С

¿„-л <1^-0

Это означает, что группирование дает выигрыш для однородных по задержкам потоков независимо от резервируемой скорости, т.е. этот выигрыш будет относительно наибольшим, когда отдельные потоки имеют низкие требования к полосе пропускания (скорости). Можно также видеть, что ОБ растет с ростом п, С и О и уменьшается с ростом dmax. Этот эффект экономии сетевых ресурсов в результате группирования потоков является результатом «совместного использования ошибочных членов» для потоков группы, в то время как для изолированных потоков эти «ошибочные члены» должны учитываться по отдельности.

Для более сложной модели ШЗегу спецификации Т8рес (двойного «ведра жетонов») получаем более сложную формулу для эффективности группирования л произвольных потоков (произвольных в смысле требований к задержкам и параметрам Т8рес), где используется «суммарная Т8рес» в качестве кривой поступления для группового потока:

С£(5) = У

резервируемая скорость К меньше, чем пиковая скорость соответствующего потока.

Хотя все еще справедливо, что требование одинаковости задержек для групповых потоков способствует получению выигрыша в ресурсах за счет группирования, оно больше не является достаточным условием для фактического получения этого выигрыша. Однако для однородных по задержкам потоков с одинаковой TSpec (TSpec-однородных потоков) можно показать, что GE всегда >0 при слабых условиях.

Теорема. Для множества 8 из п >1 потоков однородных по Т8рес и задержкам, ОЕУв, если

С > М-. [Это очень слабое условие, принимая во внимание, что с одной стороны для

многихпланировщиков М- этозависимый от скорости ошибочный член и, с другой стороны,

что г зачастую будет намного меньше, чемр, так что-— будет намного меньше, чем 1.]

р-г

В работе показано, что группирование потоков почти всегда способно обеспечить снижение требований потоковых приложений к сетевым ресурсам в случае потоков однородных по их TSpec и требованиям к задержкам. Однако для TSpec-неоднородных потоков существует также и отрицательный момент в группировании из-за переоценки кривой поступления при использовании характеризации группового потока на основе «суммарной TSpec». Этот эффект зависит от того, насколько неоднородными являются изолированные потоки на самом деле (разнородность здесь главным образом фиксируется по двум характеристикам: «забросам» трафика, т.е. размеру Ъ, и интенсивности р/г). В любом случае, параметр GE может быть использован как подсказка к решению относительно того, нужно ли группировать вместе потоки и, соответственно, должен ли новый поток добавляться в существующую группу потоков,- просто на основании того факта, что GE>0 или <0.

Ослабить первую предпосылку TSpec-однородности можно при использовании для характеризации групповых потоков более «тесной» кривой поступления, чем «суммарная TSpec». Можно, например, рассмотреть последовательность «ведер жетонов», которая, как это может быть показано, является кривой поступления для группового потока. Эта «тесная» кривая поступления для группирования и потоков ГО эквивалента конкатенации (п+1)-го «ведра жетонов», т.е.

где - это оператор конкатенации для «ведер жетонов».

Такую кривую поступления называют «каскадной TSpec». Ее использование позволяет резервировать меньше ресурсов для группового потока по сравнению с «суммарной TSpec». Если взглянуть на проблему более формально, то в общем случае «тесная» кривая поступления 1ас($ для п спецификаций трафика TSpec имеет следующий вид:

Первый член представляет К (8), а второй - К (8), оба для «обычного» случая, когда

где х - длительность импульса («заброса» трафика) для потока у, задаваемая какд^ = —-,

и М=тах(М1,...,Мп)-Здесь предполагается, чтоХ| <... ^ хп

При применении известных результатов сетевых исчислений по «тесным» кривым поступления в предположении кривой обслуживания ГО, имеем следующее ограничение на величину задержки:

с!т < И(шс, с) = вир,^ (inf{Г: Т 0 л /ае(г) 5 с(г + Т)})

С

--х, + — + С ' Я

и 1 м ) М + С

+ £>

где

4 е {!,...,И}

является таким, что:^р; + •

Если Я > У. р, (т.е. не существует таких к), тогда Л <,

м+с

Для сравнения, ограничение на величину задержки для «суммарной Т8рес» из п потоков есть

М + С

я

+д

Л1+1-г> Х-1 V

!• 1

Можно показать, что для заданной скорости Л йт всегда больше чем или равно йас, так как «суммарная Т8рес» является «внешней огибающей» для «каскадной Т8рес». Формулы для скорости обслуживания при условии задания определенной величины задержки выглядят следующим образом. Для «суммарной Т8рес» (где снова М = тах(М1,..., Мп)) получаем:

Для «каскадной Т8рес» получаем для некоторого Ш {1, ..., п} следующие скорости:

случай 1: ílPJ+YrJ>R^

> I ы

1-1

случай 2:

С помощью этих формул можно сравнивать схемы распределения ресурсов для изолированных и групповых потоков, характеризуемых «суммарной» или «каскадной» Т8рес.

Раздел 3.3 рассматривает системы с агрегированным планированием. Т.е. здесь полученные результаты по проблематике группирования потоков применяются к более общей проблематике агрегации потоков. Для этого в работе вводится концептуальная модель агрегации, а затем приводятся простые численные примеры того, как эта схема работает. Концептуальная модель агрегации рассматривается как двухуровневая система распределения сетевых ресурсов, соответствующая ситуации внутри и вне области агрегации (ОА). Вне ОА распределение ресурсов выполняется для отдельных потоков, в то время как внутри ОА оно выполняется для агрегированных потоков. Подлежащие агрегации потоки должны разделять один и тот же путь через ОА, но вне ОА могут следовать различными маршрутами.

При попытках применить результаты по группированию к этой общей модели агрегации, мы сталкиваемся с тремя проблемами:

1. Необходима фиксированная задержка для ОА, то есть часть ограничения каждого потока на величину сквозной задержки в очереди должна быть отдана ОА.

2. Возможны искаженные (относительно их Т8рес), то есть несогласованные входные потоки на входе в ОА. Они могут занимать общий буфер их группы и уничтожить гарантии скорости, задержки и обслуживания без потерь для других потоков этой группы.

3. Возможное искажение группового потока может привести к переполнению в маршрутизаторах после выхода из ОА.

В работе предложен подход к первой проблеме, который заключается в разбиении задержки на две части: задержку внутри и снаружи ОА. Главный вопрос здесь, каким образом назначать эти две части общей задержки? Хотя невозможно точно определить частичную задержку ё потока, доступную подпути через ОА, мы имеем следующее соотношение:

М + С

Л

К(р-г) Я

где ^ И DAR - это накопленные «ошибочные члены» для подпути через ОА. Нижняя граница соответствует пессимистическому предположению о том, что пакеты «расплачиваются за забросы своего трафика» вне ОА, в то время как верхняя граница представляет случай, когда «расплата за заброс трафика» происходит внутри ОА. Из-за того, что предоставляемые ГО гарантии базируются на ситуации «наихудшего случая», мы должны, однако, предположить, что нижняя граница - это доступная частичная задержка. Таким образом, частичная задержка может оказаться очень малой, если «ошибочные члены» являются малыми по сравнению с первым членом («членом заброса трафика») в выражении для верхней границы. Это привело бы к относительно большому выделению ресурсов в ОА. Для того чтобы обойти эту проблему, механизм протокола должен объявлять большой «ошибочный член» DAR для ОА.

С точки зрения ситуации вне ОА, сама ОА, таким образом, могла бы рассматриваться как элемент сети с фиксированной задержкой на пути от отправителя к получателю. Недостатком этого подхода является то, что маршрутизаторам вне ОА потребовалось бы резервировать больше ресурсов, чем в случае раздельных потоков. Очевидно, здесь приходится выбирать между сохранением ресурсов внутри ОА за счет объявления более высокой ошибки DAR И выделением большего количества ресурсов вне ОА. Две чаши на весах этого выбора могут быть взвешены тем, насколько дефицитны ресурсы внутри и вне ОА. Альтернативой увеличения DAR может быть использование в ОА члена «резерва» для увеличения ее бюджета задержки. Но для этого нужно, чтобы получатель знал о том, что его запросы ресурсов потенциально могут быть агрегированы.

Решение второй проблемы состоит в «переформировании» отдельных потоков для приведения к их исходной Т8рес на входе в ОА. Хотя это решение может увеличить среднюю задержку пакетов потока ГО, было показано, что ограничение на величину задержки данным «переформированием» не нарушается.

Третья проблема может быть решена за счет «переформирования» агрегированного потока на выходе ОА в соответствии с «каскадной Т8рес» групповых потоков. Конечно, «переформирование» на выходе могло бы выполняться и для отдельных потоков. Однако это более дорогостоящее решение, так как для группы из п потоков необходимо было бы пройти через 2п «ведер жетонов», тогда как для первого варианта это только п+1 «ведро жетонов». Заметим, что «переформирование» потоков не может быть выполнено с использованием упрощенных кривых поступления. Они предназначены для использования внутри ОА.

С учетом этих предпосылок можно использовать формулы, выведенные для группирования потоков, для распределения ресурсов внутри ОА.

Таким образом, в работе показано, что существует целое множество мало исследованных фундаментальных отношений, которые могут быть выявлены с помощью методов сетевого исчисления. Такие качественные результаты, как «формирователи удерживают трафик в границах поступлений» или «одноразовая расплата за заброс трафика» имеют для инженеров-сетевиков физическую интерпретацию и практическое значение. Все представленные в работе результаты являются детерминированными. Исследование отношений между стохастическими системами и детерминированными отношениями, представленными в работе, выходят за рамки диссертации и могут стать предметом будущих исследований по сетевому исчислению.

Экспериментальная работа, представленная в главе 4, направлена на исследование вопроса предоставления приложениям гарантированного КО передачи данных (потоковых и нет) в разных сетевых средах. В частности рассматривается обобщение проблемы сетевой мультимедиа, а именно, проблема поддержки непрерывных информационных потоков, генерируемых приложениями распределенных виртуальных сред (РВС). Подобные приложения заслуживают особого внимания в связи с ростом тенденции использования учеными уникального научного оборудования, имеющего современные компьютерные интерфейсы, такого как, например, сканирующие-зондирующие атомные микроскопы (СЗМ), спектрометры, медицинское оборудование отображения информации, хирургические роботы.

В качестве экспериментальной системы рассматривается распределенная система «Виртуальная лаборатория», которая является интерфейсом на базе виртульной реальности (ВР) лабораторного оборудования, распределенного по глобальным и локальным сетям, обеспечивающим возможность интерактивного управления этим оборудованием и получения определенных результатов как ответной реакции оборудования на команды управления и манипуляции удаленного пользователя. Приложение «Виртуальная лаборатория» реализовано как три процесса, работающие на двух рабочих станциях Windows 2000, как это представлено на рисунке. Одна машина непосредственно подключена к эмулятору научного оборудования (например, СЗМ) и управляет им. Другая машина - графическая двухпроцессорная станция с платой ускорителя трехмерной графики. Один процессор выделен для процесса управления устройством силовой обратной связи в режиме жесткого реального времени. Второй процессор обрабатывает основное приложение виртуальной лаборатории, включая графику, пользовательский интерфейс, и сетевые коммуникации Выделенная сеть используется графической станцией для передачи и приема данных, команд и данных о позициях/усилиях от имитатора силовой обратной связи в режиме реального времени.

Рисунок. Конфигурация имитационно-моделирующего стенда.

Для моделирования сети предприятия или института с единственным 10-мегабитным каналом доступа к Интернет-провайдеру, была использована управляемая сеть лаборатории. Один конец системы «виртуальной лаборатории» был размещен в сети лаборатории на стороне «Института», а другой - на стороне «Интернет-провайдера». Система «виртуальной лаборатории» разделяла канал к провайдеру с большим числом (тысячи) имитируемых Веб-браузеров. Веб-браузеры генерировали запросы к Веб-серверам, находящимся вне сети провайдера, которые возвращали ответы, генерируемые на основе эмпирической модели Веб-трафика. За счет возможности конфигурирования количества Веб-браузеров и серверов можно было оперативно управлять уровнем насыщения канала к провайдеру. На этом канале трафик «виртуальной лаборатории» конкурировал с Веб-трафиком и, следовательно, уровень насыщения канала был переменным (но предсказуемым и воспроизводимым)

Эксперименты, представленные в разделе 41 сфокусированы на проблематике определения степени возможного использования существующих методов «максимально возможной» адаптации передаваемой информации, разработанных для потокового аудио и видео, для удовлетворения требований производительности, предъявляемых к РВС, а также возможности использования сетевых механизмов, предложенных для контроля насыщением сети, и средств дифференцированного обслуживания для изоляции потоков не-реального времени от потоков реального времени и обеспечения «лучшей - чем - максимально возможная» службы доставки потоков, генерируемых приложениями РВС.

Общепринято, что мультимедийные приложения используют алгоритмы управления буферами для динамической установки размера (глубины) буфера воспроизведения. Эти так называемые «эластичные» схемы буферизации определяют уровень насыщения (состояние очередей) в сети и соответственно этому устанавливают глубину буфера. Например, в данной работе для экспериментальной РВС «виртуальной лаборатории» была предложена модификация схемы управления буфером воспроизведения на стороне получателя, называемой мониторингом очереди Этот механизм используется на графической станции пользователя для управления очередью единиц информации, поступающих от удаленного научного оборудования. Суть этого механизма заключается в том, что можно отслеживать

изменение объема занятой части буфера с течением времени и использовать это значение как мерило текущей степени нестабильности задержки. Также эту меру можно использовать для динамической установки размера буфера. Мониторинг очередей предполагает, что поток информации имеет точку истока и точку стока, которые непрерывно производят и потребляют пакеты с одинаковой скоростью. Таким образом, только за счет анализа занятости буфера через регулярные интервалы времени, имеется возможность квантования времени.

Хотя это неплохо работает для процессов воспроизведения аудио/видео, в «виртуальной лаборатории» процессы генерации данных и процессы их отображения работают с разными скоростями: пользователь посылает запросы к оборудованию со скоростью 10-60 Гц, в то время как скорость ответов от оборудования широко варьируется из-за задержек самого оборудования. Процесс на стороне пользователя пытается восстановить временную последовательность получения удаленным оборудованием единиц информации. Это требует расширения механизма мониторинга очередей для работы на уровне временных интервалов меньшего размера, чем время одного кадра, что ведет к более сложной и менее детерминированной реализации. Вместо обработки одной единицы информации из очереди в каждом кадре процесс получения данных должен непосредственно отслеживать среднее значение интервала времени между поступлениями единиц информации от оборудования и использовать его как эффективное межкадровое время для обработки очереди воспроизведения. При таком отслеживании времени эффективность управления очередью зависит от точности вычисления интервалов времени поступления единиц информации, и если вычисления достаточно точны, мы должны быть в состоянии скомпенсировать временную нестабильность оборудования (вариации времени обработки запроса) в дополнении к временной нестабильности сети. Для обратного конвертирования скорости полученных ответов в скорость, которую может обрабатывать оборудование, в нашей «виртуальной лаборатории» используется обновляемая очередь. Обновляемая очередь - это НБО-буфер, который сопоставляет ключ каждому элементу буфера и отбрасывает любой элемент с ключом к перед добавлением нового элемента с ключом к.

Был проведен ряд экспериментов по оценке адаптации к нестабильности задержки. Использование мониторинга очередей для сглаживания нестабильности задержки в системе «виртуальной лаборатории» было проверено на трех вариантах мониторинга очередей, соответствующих «низкому», «среднему» и «высокому» уровню толерантности к нестабильности задержки. Для каждого варианта были измерены: частота потерь (мера насыщения сети и значение, которое должно было оставаться константой между экспериментами, так как как потеря пакетов данных здесь не рассматривалась); частота, с которой пакеты отбрасываются алгоритмом мониторинга очередей (для снижения запаздывания при воспроизведении); результирующая частота пауз (пропусков кадров) при воспроизведении этих данных в приложении, и сквозное запаздывание в системе.

Результаты экспериментов показывают, что отсутствие адаптации к нестабильности задержки приводит к такой частоте пауз, которая делает работу приложения совершенно неприемлемой для пользователя. Даже при небольшом значении параметра для мониторинга очередей, очередь вряд ли когда-либо опустеет. При пороге равном интервалу времени 30-ти последовательных поступлений пакетов для очереди длиной 2 или больше имеем уменьшение частоты потерь до 0.6%, и частота пауз лишь немногим выше частоты потерь. На высших уровнях толерантности к нестабильности задержки частота потерь продолжает уменьшаться, и частота пауз приближается к частоте потерь. Хотя заметно небольшое увеличение запаздывания при использовании мониторинга очередей по сравнению с системами без мониторинга, это увеличение является терпимым и стоит уменьшения частоты пауз.

В дополнение к нестабильности задержки приложения РВС должны также обрабатывать и ситуацию потерь пакетов. В данной работе разрабатывается механизм управления сетевыми ресурсами, который обеспечивает баланс между противоречивыми требованиями непрерывности передачи данных и управления насыщением трафика. Для удовлетворения обоих требований исследуется подход, ориентированный на

маршрутизаторы, который распределяет емкость очереди маршрутизатора между классами трафика. Практика управления очередями маршрутизаторов для оказания влияния на работу сетевых соединений известна как Активное Управление Очередями (АУО). В данной работе предлагаются облегченные схемы АУО для маршрутизаторов, которые защищают ТСР-соединения от «простоев» из-за «безответственных» UDP-соединений и резервируют емкость маршрутизатора для UDP-приложений, требующих непрерывной передачи данных и называемых иногда приложениями длительных однонаправленных передач (ДОП).

Для сети Интернет сейчас активно продвигается специфическая форма АУО для маршрутизаторов, известная как Раннее Случайное Обнаружение (РСО). В РСО пакеты данных отбрасываются из неполной очереди случайным образом с вероятностью отбрасывания пакета в данный момент времени, получаемой как значение функции средней длины очереди за недавний период времени. Механизм РСО предотвращает появление ситуаций взаимных блокировок за счет равномерного отбрасывания пакетов от всех потоков. Было показано, что за счет обеспечения раннего оповещения о насыщении трафика схема РСО дает в результате более короткую среднюю длину очереди в маршрутизаторах.

Были проведены эксперименты с расширениями схемы РСО, которые изолируют потоки TCP от не-ТСР-потоков и, в тоже самое время, обеспечивают ДОП-приложениям доступ к настраиваемому объему сетевых ресурсов. Потоки TCP изолируются от других потоков за счет установления ограничения на среднее число не-ТСРишных пакетов, которые одновременно могут находиться в очереди маршрутизатора. Классы не-ТСР-трафика также изолируются друг от друга. Это достигается за счет пометки пакетов ДОП-потоков прежде, чем они достигнут маршрутизатора, так что они могут быть соответствующим образом классифицированы. Эта пометка выполняется или оконечными системами или сетевыми администраторами как часть более крупной архитектуры Дифференцированных Служб Интернета DiffServ. Как только потоки помечены, маршрутизатор начинает собирать простую статистику для ограниченного числа классов трафика. Для простоты рассматриваются три класса трафика: TCP, помеченный не-ТСР и все остальные («другие»). Пропускная способность классов трафика ограничивается во время насыщения трафика на основе введения ограничений на среднее число пакетов, которое каждый класс трафика может поставлять в очередь маршрутизатора. Когда пакет приходит в маршрутизатор, он относится к одному из трех классов трафика. Пакеты TCP подчиняются алгоритму РСО. Для классов не-ТСР-трафика хранится средне-взвешенное число пакетов в очереди из каждого класса. Когда приходит не-ТСРишный пакет, средне взвешенное число для соответствующего класса обновляется и сравнивается с максимальным порогом этого для класса. Если среднее число для класса превышает порог, то пришедший пакет отбрасывается, иначе - ставится в очередь. Хотя пакеты классифицированы, для каждого исходящего соединения в маршрутизаторе имеется только одна очередь пакетов, доступная всем классам трафика, и все пакеты ставятся в очередь и извлекаются из нее в соответствии с FIFO-стратегией.

Эта схема называется пороговой, основанной на классах (ПОК). Схема ПОК обеспечивает изолирование классов трафика за счет использования отдельного порога для каждого класса. Эти пороги эффективно выделяют каждому классу объем очереди и гарантируют доступность этого объема данному классу независимо от интенсивности передачи данных других классов. Эта часть объема очереди соответствует части пропускной способности исходящего соединения. Таким образом, за счет подстройки долей очереди можно управлять пропускной способностью (скоростью) исходящего соединения, выделяемой классу трафика.

Для демонстрации эффективности схемы ПОК ее производительность эмпирически сравнивается с производительностью схем простой FIFO-очереди и РСО на базе использования экспериментального стенда. Маршрутизатор между сетью института и Интернет-провайдером реализует ПОК-схему и обслуживает 3 описанных выше класса трафика. Класс TCP состоит из набора имитаций Веб-соединений, потенциально потребляющих 98% пропускной способности 10-Мбитного канала, соединяющего институт с

Интернет-провайдером. Класс помеченного не-ТСР-трафика является комбинацией имитаций приложений сетевых видео-конференций и приложения «виртуальной лаборатории», которые вместе генерируют приблизительно 200 Кбит/сек «помеченного» трафика UDP. Третий, так называемый «другой» класс трафика содержит объемное одиночное UDP-приложение с высокой пропускной способностью.

Были выполнены эксперименты с использованием в маршрутизаторе схем очередей FIFO, PCO и ПОК. Не явилось сюрпризом, что организация очереди FIFO приводит к самой низкой производительности для всех потоков. «Безответственное» UDP-приложение высокой пропускной способности приводит к насыщению сети, и потери пакетов происходят с высокой интенсивностью. TCP-соединения реагируют на потери снижением интенсивности передачи и потреблением меньшего объема буферной памяти в маршрутизаторе. Объемная UDP-передача тоже видит высокую частоту потерь пакетов, но, тем не менее, никак не реагирует на это. И так как в случае FIFO и РСО буферы в маршрутизаторе остаются полными, все сетевые соединения продолжают терять пакеты. Производительность TCP резко падает с максимальной в 1000 Кбит/сек, достигнутой в отсутствие приложений, осуществляющих объемные передачи, до 200 Кбит/сек, поскольку соединения TCP испытывают нехватку доступной полосы пропускания. ПОК также демонстрирует снижение производительности TCP, но это снижение порядка 10-20%, так как ПОК использует часть пропускной полосы, которую может потреблять UDP-поток.

В дополнение, для защиты TCP схема ПОК также отделяет помеченные не-ТСРишные ДОП-потоки от «безответственных» потоков «другого» класса. Это можно видеть по частоте потерь помеченных ДОП-пакетов. И FIFO и РСО имеют высокую частоту потерь для ДОП-потоков, тогда как ПОК имеет частоту потерь всего лишь чуть больше 1%, что является достаточно хорошей апроксимацией производительности более сложной схемы коммутации пакетов, предусматривающей абсолютную изоляцию классов трафика между собой. В частности, ПОК демонстрирует результаты в частоте потерь для помеченных ДОП-потоков, которые вероятно окажутся приемлемыми для ДОП-приложений.

Было также проведено сравнение среднего сквозного сетевого запаздывания помеченных ДОП-пакетов в каждой схеме. Максимальное запаздывание происходит при использовании FIFO-очереди, т.к. очередь постоянно заполнена. РСО и ПОК поддерживают более короткие в среднем очереди и, следовательно, создают более короткое запаздывание.

В разделе 4.2 проблема обеспечения сквозного КО исследуется несколько шире, проводится экспериментальное обоснование теоретических выкладок по группированию и агрегации потоков, изложенных в главе 3. Здесь агрегированная система потоков рассматривается более детально и сравнивается с системой изолированных потоков. Представлены несколько простых численных примеров поиска компромисса между распределением ресурсов в и вне ОА, проводится более глубокая численная оценка предложенного механизма в форме «анализа чувствительности» полученных формул к внешним параметрам, таким как спецификации трафика и параметры конфигурации сети. Анализ основывается на экспериментах, проводимых с использованием среды имитационного моделирования, разработанной специально для этих целей, которая позволяет анализировааь и визуализировать чувствительность агрегированной системы к изменениям указанных внешних переменных. В качестве основного сетевого ресурса рассматривается скорость обслуживания, поскольку она выглядит более чувствительной к изменениям параметров, и, кроме того, считается, более важным параметром, чем буферное пространство.

Эксперименты проводились на модели сети, представленной на следующем рисунке и имеющей область агрегации (ОА) из пяти сетевых «переходов», каждый характеризующийся двумя параметрами: размером максимального передаваемого блока MTU = 9188 байт и скоростью передачи с = 155Мбит/сек («ATM-переходы»). Для области вне ОА было взято по 2 «перехода» до и после ОА, все они с MTU = 1500 байтов и с = 100 Мбит/сек («переходы быстрого Ethernet»). Кроме того, предполагалось, что вместе группируются 10 потоков, каждый из которых имеет ограничение на величину сквозной задержки dmax= 100 мсек.

••конечная система маршрутизатор области доступа

изолированный -"ПОТОК

»агрепфо ванный .граничное устройство ПОТОК

Рисунок. Пример сценария имитационного моделирования.

Проведенные прогоны имитационной модели и вычисления показывают, что агрегация может быть выгодной в смысле использования ресурсов при условии аккуратного разбиения сквозной задержки на части. Данные численных экспериментов показывают, что оптимальное значение задержки для области внутри ОА для скорости агрегированной системы составляет 40 мсек, что дает уменьшение скорости порядка 13.74 %, в то время как для буфера агрегированной системы это дает меньше чем половину (46.67 %) того, что требуется для системы раздельных потоков (относительно буфера это разбиение задержки не является оптимальным, однако вариации размеров буфера между различными вариантами разбиения задержки незначительны). Даже если применить простой подход по использованию нижней границы задержки внутри ОА (в данном примере это - 22,949 мсек), то можно получить значительно лучшие значения скорости и буфера для агрегированной системы, чем для раздельной системы (9.81 % для скорости и 53.78 % для буфера).

Были также проведены ряд экспериментов для анализа зависимости результатов агрегации потоков от различных параметров, включая количество потоков в системе, размеры очередей, размеры импульсов трафика, размеры пакетов данных, размеры потоков, разные варианты смешанного трафика, разные стоимостные отношения между областями внутри и вне ОА, размеры ОА. Чтобы иметь более удобный показатель для сравнения различных экспериментов, чем распределение агрегированной скорости, используется понятие ЭффективностиАгрегации АЕ, которая определяетсякак

Лигг Н-щ

АЕ = -

Е

АЕ > 0 означает, что агрегированная система работает лучше, чем система раздельных потоков в смысле распределения скорости, тогда как отрицательная АЕ показывает обратное.

Во всех экспериментах фиксировались значения всех параметров кроме одного и исследовалось, как изменения этого параметра отражаются на эффективности агрегации АЕ. Разбиение задержки выбирается в качестве проектной переменной агрегированной системы и, поэтому, полученная в рамках экспериментов АЕ показывается в зависимости от задержки, назначенной сетевым переходам внутри ОА. Все эксперименты повторялись до тех пор, пока они не достигли доверительного интервала <0.01 во всех точках измерения, что потребовало около 20-50 прогонов имитационной модели для каждого эксперимента.

Проведеный ряд прогонов имитационной модели для исследования условий, при которых агрегация может оказаться выгодной с точки зрения использования ресурсов, показывает, что хотя агрегированная система не превосходит систему из раздельных потоков в отношении использования ресурсов во всех случаях, существуют численные доказательства существования определенного количества ситуаций, в которых это происходит. Это представляет дополнительный аргумент в пользу использования агрегированных потоков в ядре сети, помимо его основного плюса в сокращении размерности состояния в ядре крупномасштабной сети.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

1. Представлены результаты анализа действующих сетевых интерактивных систем мультимедиа и трехмерной графики (виртуальной реальности).

2. Рассмотрена математическая модель описания предметной области потоковых приложений в глобальных сетях с использованием математического аппарата сетевого исчисления.

3. Предложен метод адаптации форматов аудио/видео информации для сглаживания эффекта от нестабильности задержки в потоках данных распределенных систем мультимедиа и виртуальной реальности.

4. Предложен и исследован подход «активного управления очередями» к реализации дифференцированных служб в маршрутизаторах для защиты TCP-приложений от непрерывных потоковых приложений реального времени и для обеспечения «лучшей-чем-махсимально возможная» службы доставки пакетов данных.

5. Разработан программный комплекс распределенной системы виртуальной реальности, реализующий математическую модель и методики ее исследования и использования.

Основные положения и результаты диссертационной работы отражены в следующих публикациях:

1. Кутненко В.В., Кудинов ГА., Трубочкина Н.К., Петросянц К.О. Методические указания по использованию программного комплекса Tophist97: Учебное издание М.: МГИЭМ 2000, - 20 с.

2. Панфилов П.Б., Кутненко В.В., Васильев Е.Н., Громыко А.А. Оптимизация доступа к информации диспетчерского центра в SCADA системах // Новые информационные технологии: Материалы 4 науч.-практич. семинара. - М., МИЭМ, 2001. - С.45-46.

3. Панфилов П.Б., Кутненко В.В., Громыко АА. Программное обеспечение сервера удаленного доступа к базе данных диспетчерского центра управления мобильными объектами // Тез. докл. науч.-техн. конф. студ., аспир. и мол. спец. МИЭМ - М.: МГИЭМ, 2001. - С. 207208

4. Панфилов П.Б., Кутненко В.В. Проектирование имитационно-моделирующих систем реального времени на базе распределенных вычислительных комплексов // Информационные, сетевые и телекоммуникационные технологии: Сб. науч. трудов, под ред. проф., д.т.н. Жданова B.C. / Моск. гос. ин-т электроники и математики - М.:, МИЭМ, 2001. - С.126-149.

5. Кутненко В.В. Архитектура сетевых служб для реализации виртуального интерфейса удаленного доступа к лабораторному оборудованию в сети Интернет // Тез. докл. науч.-техн. конф. студ., аспир. и мол. спец. МИЭМ-М.: МГИЭМ,. 2003., С.ЗО 1-303

6. Кутненко В.В., Панфилов П.Б. ВР-интерфейс для управления оборудованием удаленной лаборатории по сети // Гражданская авиация на современном этапе развития науки, техники и общества: Тез докл. Междунар. науч.-технич. конф., Москва, 17-18 апреля 2003 г. - М.: МГТУ ГА,2003.-С178.

7. Кутненко В.В., Панфилов П.Б., Григорьев О.Г. Оптимизация сетевого трафика при создании распределенных систем виртуальной реальности // Научный Вестник МГТУ ГА. Серия Информатика. Прикладная математика. - М., 2003. -№ 65. - С. 71-74.

-9 54

Принято к исполнению 20/12/2004 Заказ № 525

Исполнено 21/12/2004 Тираж: 100 экз.

ООО «11-й ФОРМАТ» ИНН 7726330900 Москва, Балаклавский пр-т, 20-2-93 (095) 747-64-70 (095)318-40-68 www.autoreferat.ru

ВВЕДЕНИЕ.

ГЛАВА 1. АНАЛИЗ ТЕКУЩЕГО СОСТОЯНИЯ СЕТЕВЫХ ПОТОКОВЫХ ПРИЛОЖЕНИЙ РЕАЛЬНОГО ВРЕМЕНИ.

1.1 Тенденции развития и перспективы сетевых приложений.

1.2 Взаимодействие сетевых технологий.

1.2.1 Базовая модель взаимодействия открытых систем OSI.

1.2.2 Модель TCP/IP.

1.2.3 Структура стека протоколов ATM.

1.2.4 DTM технология.

1.2.5 Сравнение Архитектур КО ATM и Интернет.

1.2.6 Перечисление Случаев Взаимодействия.

1.2.7 Классификация моделей взаимодействия.

1.2.8 Классификация способов взаимодействия.

1.3 Теоретические основы построения сетевых приложений.

1.3.1 Моделирование КО.

1.3.2 Модели и методы анализа сетевых проблем.

1.4 выводы к главе 1.

ГЛАВА 2. АЛГЕБРАИЧЕСКИЕ МОДЕЛИ ПРИ СЕТЕВОЙ ОБРАБОТКЕ МУЛЬТИМЕДИЙНОЙ ИНФОРМАЦИИ.

2.1 Основы Мини-Плюсового Исчисления.

2.1.1 Инфимум и Минимум.

2.1.2 Диоид( ВШ{+°о},л,+).

2.1.4 Псевдо-инверсия неубывающих функций.

2.1.5 Вогнутые и выпуклые функции.

2.1.6 Мини-плюсовая свертка.

2.1.7 Суб-аддитивные функции.

2.1.8 Суб-аддитивное замыкание.

2.1.9 Мини-плюсовая развертка.

2.1.10 Представление Мини-Плюсовой Развертки Инверсией Времени.

2.1.11 Вертикальное и Горизонтальное отклонение.

2.2 Кривые поступления и обслуживания.

2.2.1 Моделирование потоков данных.

2.2.2 Кривые поступления.

2.2.3 Алгоритмы «Дырявого ведра» и «Обобщенной Ячеечной Скорости».

2.2.4 Суб-аддитивность и кривые поступления.

2.2.5 Минимальная кривая поступления.

2.2.6 Кривые обслуживания.

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 Разные размеры OA.180

4.6 Выводы к главе 4.181

ЗАКЛЮЧЕНИЕ.183

ЛИТЕРАТУРА.184

ПРИЛОЖЕНИЯ

Введение

Актуальность проблемы Появление в 1994 году глобальной сети Интернет и последовавший бурный рост «всемирной паутины» (WWW) кардинальным образом изменили мир телекоммуникаций. Эти изменения нашли свое отражение и в коммуникационной промышленности, и в информационных технологиях. Первое десятилетие развития Интернета ознаменовалось массовым подключением обычных пользователей к глобальной сети и развитием целого спектра сетевых приложений, подавляющее большинство которых было ориентировано на статические услуги типа поиска и просмотра информации и электронной почты. Сегодня сообщество пользователей глобальной сети Интернет стоит на пороге качественного скачка в направлении полноценных мультимедийных приложений, то есть услуг с богатым мультимедийным содержанием, включая качественное потоковое видео и аудио, интерактивную трехмерную компьютерную графику в дополнение к обычной информации.

Подобное изменение характера сетевого трафика стимулируется с двух сторон: со стороны промышленности мультимедиа и трехмерной компьютерной графики и со стороны самих покупателей и пользователей мультимедийной и трехмерной графической продукции. В промышленности - оцифровка мультимедийного и трехмерного содержимого, а также оцифровка и перестройка под нужды пользователя самого производства привели к появлению новых производственных процессов. Эти новые процессы выпуска и распространения цифровой мультимедийной и трехмерной графической продукции базируются на, взаимодействуют с и задают особые требования к средствам обеспечения качества и к пропускной способности распределенных сетей и Интернета. Высококачественное мультимедийное содержимое, которое прежде было доступно исключительно теле- и радиовещательным компаниям, теперь стало широко доступным через услуги Интернета. Одновременно, сами покупатели и пользователи сети Интернет генерируют широкополосный богатый мультимедийным содержанием сетевой трафик, обмениваясь музыкальными файлами, фотографиями, видеоклипами и играя в сетевые компьютерные игры.

По мере того, как ориентированные на мультимедиа и трехмерную графику услуги начинают доминировать в сети, происходит очередной технологический сдвиг -развертывание инфраструктуры, которая способна справляться с большим количеством потоковых услуг при одновременной поддержке высокого качества. Сеть Интернет в том виде, как она функционирует сегодня, без дополнительных затрат на чрезмерно избыточные ресурсы не способна поддерживать какие-либо услуги, кроме приложений максимальной возможности» типа «отослал и молись, чтобы дошло». И даже в условиях, когда были сделаны впечатляющие по объемам инвестиции в развертывание оптоволоконных линий связи, большие затраты, связанные с подсветкой длин волн и добавлением оборудования активной маршрутизации и коммутации, создают серьезную нагрузку на экономику.

Все это серьезно ограничивает применимость в реальной жизни экстенсивного подхода к решению проблем качества сетевого трафика, базирующегося па примитивном запасании избыточных ресурсов. А в совокупности с проблемой конкуренции различных сетевых технологий (IP и ATM) это создает проблемы «маршрутизации трафика в смешанных сетях» и «обеспечения гарантированного сквозного качества обслуживания (КО) на всем пути трафика в смешанной сети». Традиционно проблема управления трафиком в сетях решается с помощью математического аппарата теории массового обслуживания, теории графов, теории сетей, теории автоматов и др., которые были разработаны такими известными российскими и зарубежными учеными как Башарин Г.П., Бочаров П.П., Вишневский В.М., Горбатов В.А., Жожикашвили В.А., Корнеев В.В., Лазарев В.Г., Наумов В.А., Нейман В.И., Степанов С.И., Харкевич А.Д., Шнепс-Шнеппе М.А., Шоргин С.Я., Винер Н. и др.

Несмотря на прогресс в развитии теории компьютерных сетей, эта перспективная область оставляет простор для разработки новых аналитических методов и преодоления недостатков известных. Точно также как в начале XX века потребности развития телефонии привели к появлению и бурному развитию теории массового обслуживания (теории очередей), революционные изменения в характере сетевого трафика в начале XXI века потребовали разработки новых теорий, методов анализа и проектирования сетевой инфраструктуры и приложений. Большие надежды на эффективное решение проблем сетевых потоковых приложений реального времени связываются сегодня, в том числе, с развитием математического аппарата сетевого исчисления, представляющего собой набор последних разработок в области математической теории диоидов и, в частности, «мини-плюсового» диоида (также называемого «мини-плюсовой» алгеброй). Сетевое исчисление относится к той области, которую иногда называют «экзотическими алгебрами» и к которой относятся, в том числе, и сети Петри. Они представляют собой набор математических результатов высокой описательной сложности, обеспечивающих средства адекватного представления таких создаваемых человеком систем, как параллельные программы, цифровые электронные схемы и, конечно, коммуникационные сети.

Таким образом, тематика проводимых в диссертационной работе исследований и полученные результаты являются актуальными и имеют важное практическое значение.

Цель диссертационной работы состоит в развитии теоретических основ и разработке математического аппарата, методов моделирования и анализа, которые обеспечат лучшее понимание проблем потоковых приложений, возникающих в компьютерных сетях. Эти формальные методы и средства призваны обеспечить более адекватное представление некоторых фундаментальных свойств сетей интегрированных услуг, управления потоками, составления расписаний и определения размеров буферов или величин сетевых задержек при проектировании приложений распределенных систем мультимедиа и виртуальной реальности.

Для достижения данной цели в работе сформулированы и решены следующие задачи:

1. Анализ особенностей построения и функционирования сетевых потоковых приложений в локальных и глобальных сетях ЭВМ.

2. Анализ базовых сетевых архитектур глобальных сетей и соответствующих архитектур качества обслуживания, классификация моделей взаимодействия и путей организации взаимодействия сетевых архитектур при построении смешанных сетей.

3. Выбор и обоснование базового математического аппарата для моделирования и анализа фундаментальных проблем потоковых приложений в сетях.

4. Разработка моделей потоков и моделей планировщиков для сетевых узлов на основе кривых поступления и обслуживания и их применение для решения проблем буферной памяти, пропускной способности и задержек при обеспечении гарантий качества обслуживания потокам мультимедийных и графических данных.

5. Разработка методов и средств агрегации прикладных потоков в сетях интегрированного обслуживания с проведением точного анализа проблемы распределения ресурсов для агрегированного трафика.

6. Разработка программного обеспечения системы «Виртуальная лаборатория» на базе интерфейса виртуальной реальности для управления научным оборудованием по сети.

Методы исследования.

При решении поставленных задач в диссертационной работе используются концепции и методы общей теории систем, теории вычислительных сетей, математического аппарата сетевого исчисления, методы имитационного моделирования.

К основным научным результатам, представляемым в диссертационной работе и выносимым на защиту, относятся:

1. Результаты анализа действующих сетевых интерактивных систем мультимедиа и трехмерной графики (виртуальной реальности).

2. Математическая модель описания предметной области потоковых приложений в глобальных сетях с использованием математического аппарата сетевого исчисления.

3. Метод адаптации аудио/видео информации для сглаживания эффекта от нестабильности задержки в потоках данных распределенной системы мультимедиа и виртуальной реальности.

4. Подход «активного управления очередями» к реализации дифференцированных служб в маршрутизаторах для защиты ТСР-приложений от непрерывных потоковых приложений реального времени и для обеспечения наилучшей службы доставки пакетов данных.

5. Реализация разработанных моделей и методов в виде программного комплекса распределенной системы виртуальной реальности и методик его исследования и использования.

Практическая ценность и реализация результатов работы. Научные результаты, полученные в диссертации, доведены до практического использования при построении прототипа системы распределенной виртуальной лаборатории, состоящей из географически разнесенных комплектов научного оборудования, компьютеров и пользователей, связанных друг с другом через компьютерную сеть, например, Интернет. Разработанные методы и алгоритмы прошли апробацию и рекомендованы для практического применения в компании ООО «Вимком-Оптик», где предложенные решения используются при построении сетей интерактивных мультимедийных услуг, таких как интерактивное телевидение и видео-по-требованию, а также в разработке приложений телемедицины. Материалы диссертационной работы используются в учебном процессе кафедры «Вычислительные Системы и Сети» (ВСиС) МИЭМ по дисциплинам «Моделирование» и «Новые информационные технологии».

• Достоверность полученных в диссертации результатов и выводов подтверждается их практической реализацией при создании распределенной системы виртуальной лаборатории.

Апробация работы. Основные результаты, изложенные в диссертации, докладывались на:

• Четвертом научно практическом семинаре «Новые информационные технологии» (Москва, 2001);

• Научно - технических конференциях студентов, аспирантов и молодых специалистов МГИЭМ (Москва, 2001, 2003);

• Международной научно-технической конференции, посвященной 80-летию гражданской авиации России (Москва, 2003).

Структура диссертационной работы.

Данная диссертационная работа организована в виде четырех глав. Глава 1 представляет собой детальный аналитический обзор современных интерактивных сетевых приложений, включая анализ перспектив и тенденций в развитии сетевой инфраструктуры, базовых сетевых технологий, архитектур обеспечения качества обслуживания, а также их преимуществ и недостатков. Особое внимание уделено вопросам взаимодействия различных сетевых технологий и архитектур обеспечения качества обслуживания с целью поддержки сетевых услуг реального времени, предъявляющих повышенные требования к своевременности, надежности и качеству обслуживания. Глава 1 завершается обзором основных проблем, выявленных в результате проведенного анализа, решению которых посвящена основная часть диссертации.

Глава 2 содержит основной набор результатов по анализу и развитию математического аппарата разработки и анализа сетевых приложений с особым акцентом на интерактивные приложения потоковой мультимедиа и трехмерной графики в сети Интернет. В качестве основы разрабатываемых методов моделирования и анализа в данной работе предлагается использовать сетевое исчисление, изложению основ которого посвящены Разделы 2.1 и 2.2. В Разделе 2.1 дается определение «мини-плюсового» диоида и его свойств, вводятся такие понятия, как выпуклые и вогнутые функции, мини-плюсовая свертка и ее свойства, суб-аддитивные функции, суб-адцитивпое замыкание и его свойства, составляющие основу математического аппарата сетевого исчисления. В Разделе 2.2 дается введение, объяснение и иллюстрация понятий кривых поступления и кривых обслуживания. Такие концепции, как мини-плюсовая свертка и суб-аддитивное замыкание раскрываются в упрощенном виде. В рамках соответствующих постановок задач даются практические определения алгоритмов «дырявого ведра» и «обобщенной ячеечной скорости» (ОСЯА) и выводятся их фундаментальные свойства. Раздел 2.3 показывает, каким образом фундаментальные результаты Раздела 2.2 применяются к сети Интернет. Например, объясняется, почему в интерсети Интегрированных служб Интернета ¡ЩБегу любой маршрутизатор может быть абстрагирован кривой обслуживания «скорость-запаздывание». Даются также фундаментальные формальные обоснования для некоторых верхних (нижних) границ, используемых для дифференцированных услуг □¡ГГСсгу.

Глава 3 посвящена применению аппарата сетевого исчисления к решению проблем обеспечения сквозного одинакового КО при передаче непрерывных потоков данных в смешанных сетях. В разделе 3.1 предложенный формальный аппарат применяется к проблеме сглаживания мультимедийных данных в сетях, предлагающих услуги на базе резервирования (ATM или RSVP/IP), для которых известна одна минимальная кривая обслуживания. Раздел 3.2 посвящен рассмотрению проблемы предоставления интегрированных услуг через общедоступную сетевую инфраструктуру. В частности рассматривается существующее решение института IETF: архитектура Интегрированных Служб Интернета IntServ, которая предлагает набор классов обслуживания, определенных рабочей группой IntServ, и протокол резервирования ресурсов RSVP для «оповещения» о требованиях пользователя относительно классов обслуживания и их параметров. Раздел 3.3 рассматривает системы с агрегированным планированием. Т.е. здесь полученные результаты по проблематике группирования потоков применяются к более общей проблематике агрегации потоков. Для этого в работе вводится концептуальная модель агрегации, а затем приводятся простые численные примеры того, как эта схема работает.

Таким образом, во второй и третьей главах показано, что существует целое множество мало исследованных фундаментальных отношений, которые могут быть выявлены с помощью методов сетевого исчисления. Такие качественные результаты, как «формирователи удерживают трафик в границах поступлений» или «одноразовая расплата за заброс трафика» имеют для сетевых инженеров физическую интерпретацию и практическое значение. Все результаты здесь являются детерминированными. Исследование многих отношений между стохастическими системами и детерминированными отношениями, представленных в диссертационной работе, выходят за рамки диссертации и могут стать предметом будущих исследований по сетевому исчислению.

Экспериментальная работа, представленная в главе 4, направлена на исследование вопроса предоставления приложениям гарантированного КО передачи данных (потоковых и нет) в разных сетевых средах. В частности рассматривается обобщение проблемы сетевой мультимедиа, а именно, проблема поддержки непрерывных информационных потоков, генерируемых приложениями распределенных виртуальных сред (РВС). Подобные приложения заслуживают особого внимания в связи с ростом тенденции использования учеными уникального научного оборудования, имеющего современные компьютерные интерфейсы, такого как, например, сканирующие-зондирующие атомные микроскопы (СЗМ), спектрометры, медицинское оборудование отображения информации, хирургические роботы.

В разделе 4.1 рассматривается проблематика определения степени возможного использования существующих методов максимально возможной адаптации передаваемой информации, разработанных для аудио и видео, для реализации требований производительности, предъявляемых к РВС, а также возможность использования сетевых механизмов, предложенных для улучшенного контроля насыщением сети, и средств дифференцированного обслуживания для изоляции потоков нереального времени от потоков реального времени и обеспечения «лучшей - чем - максимально возможная» службы доставки потоков, генерируемых приложениями РВС. Таким образом, предлагаются методы обеспечения гарантированного КО за счет активной работы с очередями маршрутизаторов.

В разделе 4.2 проблема обеспечения сквозного КО исследуется несколько шире, проводится экспериментальное обоснование теоретических выкладок по группированию и агрегации потоков, изложенных в главе 3. Здесь агрегированная система потоков рассматривается более детально и сравнивается с системой изолированных потоков. Представлены несколько простых численных примеров поиска компромисса между распределением ресурсов в и вне ОА, проводится более глубокая численная оценка предложенного механизма в форме «анализа чувствительности» полученных формул к внешним параметрам, таким как спецификации трафика и параметры конфигурации сети. Анализ основывается на экспериментах, проводимых с использованием среды имитационного моделирования, разработанной специально для этих целей, которая позволяет анализировать и визуализировать чувствительность агрегированной системы к изменениям указанных внешних переменных. В качестве основного сетевого ресурса рассматривается скорость обслуживания, поскольку она выглядит более чувствительной к изменениям параметров, и, кроме того, считается, более важным параметром, чем буферное пространство.

Публикации. По теме диссертации опубликовано 7 работ.

4.6 Выводы к главе 4

Виртуальная лаборатория» - это интерфейс виртуальной среды для лабораторного и научного оборудования различной сложности и задач. Равно как и интерактивные аудио/видео приложения, «виртуальная лаборатория» требует передачи данных в квази-реально.м масштабе времени. В этой главе рассматривались средства адаптации передаваемой информации в оконечной системе, изначально разработанные для аудио- и видео-приложений, для снижения эффекта сетевого насыщения на потоки данных, генерированные «виртуальной лаборатории», а также рассматривался вопрос о снижении пиковой нагрузки на маршрутизаторы, за счет группирования потоков. Дополнительно, в маршрутизаторе использовался механизм дифференцированных сервисов, основанный на явном распределении буферной памяти для защиты ТСР-приложений от РВС и других (желаемых) приложений длительных передач, которые не реагируют на потерю пакетов как на индикатор насыщения сети.

Экспериментальная работа была направлена исследование вопроса предоставления приложениям гарантированного КО передачи данных (потоковых и нет) по разным сетевым средам.

Эксперименты показывают, что схема адаптации к нестабильности задержки на основе мониторинга очереди способна достаточно успешно смягчать последствия от нестабильности задержки. Более того, когда она реализуется в сети, поддерживающей маркирование пакетов в дифференцированных службах, простая активная схема управления очередью в маршрутизаторе, которая управляет распределением буферной памятью между классами трафика, может обеспечивать и "лучшую — чем - максимально возможная " службу пересылки данных для РВС и других длительных отоков информации, и защищать ТСР от потенциальных «нежелательных эффектов» от "безответственных" по своей природе длительных потоков информации.

Таким образом, агрегация потоков состоятельных приложений внутри сети является необходимым механизмом не только для сохранения возможности расширения больших сетей, таких как, например, Интернет, но и для снижения негативного эффекта от передачи длинных потоков. Рассмотрены статические аспекты агрегации, т.е. какие потоки агрегируются, и сколько требуется выделять ресурсов агрегированному потоку для конкретного случая класса приложений ГО архитектуры МБегу. Показано, как можно обеспечить каждому потоку строгие гарантии, предоставляемые детерминированными сервисами, несмотря на агрегацию в ядре сети. Положительным моментом экспериментальной работы является установления факта того, что при правильном группировании потоков и распределении ресурсов агрегация может предложить интересные ресурсные отношения между областями внутри ОА и вне ОА. В приведенном примере видно, что агрегированная система даже превзошла систему из раздельных потоков, тогда как интуитивно можно было предположить, что агрегация потребует большего количества ресурсов.

Проведеный ряд прогонов имитационной модели для исследования условий, при которых агрегация может оказаться выгодной с точки зрения использования ресурсов, показывает, что хотя агрегированная система не превосходит систему из раздельных потоков в отношении использования ресурсов во всех случаях, существуют численные доказательства существования определенного количества ситуаций, в которых это происходит. Это представляет дополнительный аргумент в пользу использования агрегированных потоков, помимо его основного плюса в сокращении размерности состояния в ядре крупномасштабной сети.

Заключение

В диссертациоиной работе были рассмотрены вопросы разработки математического аппарата, методов моделирования и анализа, обеспечивающих проникновение вглубь проблем потоковых приложений, возникающих в компьютерных сетях. Эти формальные методы и средства помогают понять некоторые фундаментальные свойства сетей интегрированных услуг, оконного управления потоками, составления расписаний и определения размеров буферов или величин сетевых задержек.

Для достижения поставленной цели в работе были сформулированы и решены следующие задачи:

1. Анализ особенностей построения и функционирования сетевых потоковых приложений в локальных и глобальных сетях ЭВМ.

2. Анализ базовых сетевых архитектур глобальных сетей и соответствующих архитектур качества обслуживания, классификация моделей взаимодействия и путей организации взаимодействия сетевых архитектур при построении смешанных сетей.

3. Выбор и обоснование базового математического аппарата для моделирования и анализа фундаментальных проблем потоковых приложений в сетях.

4. Разработка моделей потоков и моделей планировщиков для сетевых узлов на основе кривых поступления и обслуживания и их применение для решения проблем буферной памяти, пропускной способности и задержек при обеспечении гарантий качества обслуживания потокам мультимедийных и графических данных.

5. Разработка методов и средств агрегации прикладных потоков в сетях интегрированного обслуживания с проведением точного анализа проблемы распределения ресурсов для агрегированного трафика.

6. Разработка программного обеспечения системы телеуправления удаленным научным оборудованием по сети «Виртуальная лаборатория» на базе интерфейса виртуальной реальности.

1. Башарин Г.П., Бочаров П.П., Коган Я.А. Анализ очередей в вычислительных сетях. Теория и методы расчета. — М.: Наука, 1989.

2. Башарин Г.П., Толмачев АЛ. Теория сетей массового обслуживания и ее приложения к анализу информационно-вычислительных систем // В кн.: Итоги науки и техники. Теория вероятностей. Математическая статистика. Теоретическая кибернетика. М.: ВИНИТИ. - 1983.

3. Бочаров П.П. Сеть массового обслуживания с сигналами со случайной задержкой // Автоматика и телемеханика. — 2002 №9 С.90 -101.

4. Бочаров П.П., Печинкин А.В. Теория массового обслуживания М.: Изд-во Рос. Ун-та дружбы народов. - 1995

5. Олифер В. Г., Олифер Н. А. Средства анализа и оптимизации локальных сетей Центр информационных технологий wvvvv.citforum.ru 1998

6. Олифер В. Г., Олифер Н. А. Сетевые операционные системы СПб.: Питер 2001

7. Бронштейн О.И., Духовный И.М. Модели приоритетного обслуживания в информационно — вычислительных сетях. -М.: Наука. 1976

8. Вишневский В.М., Пороцкий С.М. Динамическая маршрутизация в ATM сетях проблемы и решения // Автоматика и телемеханика. - 2003. - №6.

9. Вишневский В.М., Дмитриев В.П., Жданов B.C. Основы передачи информации в вычислительных системах и сетях. Учебное пособие. М.:МГИЭМ, 1998.

10. Вишневский В.М. Теоретические основы проектирования компьютерных сетей М.: Техносфера, 2003.

11. Кутненко В.В., Кудинов Г.А., Трубочкина Н.К., Петросянц К.О. Методические указания по использованию программного комплекса Tophist97: Учебное издание М.: МГИЭМ 2000.

12. Панфилов П.Б., Кутненко В.В., Васильев Е.Н., Громыко А.А. Оптимизация доступа к информации диспетчерского центра в SCADA системах // Новые информационные технологии: Материалы 4 науч.-практич. семинара. М., МИЭМ, 2001. - С.45-46.

13. Кутненко В.В. Архитектура сетевых служб для реализации виртуального интерфейса удаленного доступа к лабораторному оборудованию в сети Интернет//Тез. докл. науч.-техн. конф. студ., аспир. и мол. спец. МИЭМ М.: МГИЭМ,. 2003., С.301-303

14. Кутненко В.В., Панфилов П.Б., Григорьев О.Г. Оптимизация сетевого трафика при создании распределенных систем виртуальной реальности // Научный Вестник МГТУ ГА. Серия Информатика. Прикладная математика.-М., 2003.-№ 65.-С. 71-74.

15. P.Newman: IP+ATM: If You Can't beat Them, Join Them, IEEE ATM Workshop '97, Slide Presentation, May 1997.

16. R.Braden, L.Zhang, S.Berson, S.Herzog, S.Jamin: Resource Reservation Protocol (RSVP)-Version 1 Functional Specification, Internet RFC 2205, September 1997.

17. The ATM Forum: Traffic Management (TM) Specification 4.0, April 1996.

18. The ATM Forum: User-Network-Interface Signalling (SIG) Specification 4.0, July 1996.

19. V. Firoiu, J. Kurose, D. Towsley: Performance Evaluation of ATM Shortcut Connections in Overlaid IP/ATM Networks, University of Massachusetts, CMPSCI Technical Report 97-40, July 1997.

20. S.Shenker, C.Partridge, R.Guerin: Specification of Guaranteed Quality of Service, Internet RFC 2211, September 1997.

21. A.Viswanathan, N.Feldman, R.Boivie, R.Woundy: ARIS: Aggregate Route-Based IP-Switching, Internet Draft, work in progress, March 1997.

22. M.Borden, E.Crawley, B.Davie, S.Batsell: Integration of Real-Time Services in an IP-ATM Network Architecture, Internet RFC 1821, August 1995.

23. The ATM Forum: Private Network-Node Interface (PNNI) Signalling Specification, February 1996.

24. O. Fourmaux, S.Fdida: Multicast for RSVP Switching An Extended Multicast Model with QoS for Label Swapping in an IP over ATM Environment, Telecommunication Systems Journal (this issue).

25. G.Armitage: Support for Multicast over UNI 3.1 based ATM Networks, Internet RFC 2022, November 1996.

26. J.Luciani, D.Katz, D.Piscitello, B. Cole, N. Doraswamy: NBMA Next Hop Resolution Protocol (NHRP), Internet RFC 2332, April 1998.

27. Y.Rekliter, B.Davie, D.Katz, E.Rosen, G.Swallow: Cisco Systems' Tag Switching Architecture Overview, Internet RFC 2105, February 1997.

28. A. Acharya, R.Dighe, F.Ansari: IPSOFACTO: IP Switching Over Fast ATM Cell Transport, Internet Draft, work in progress, July 1997.

29. R. Callon, P.Doolan, N. Feldman, A. Fredette, G. Swallow, A. Viswanathan: A Framework for Multiprotocol Label Switching, Internet Draft, work in progress, November 1997.

30. Y.Katsube, K.Nagami, H.Esaki: Toshiba's Router Architecture Extensions for ATM: Overview, RFC 2098, February, 1997.

31. A.Birman, V.Firoiu, R.Guerin, D.Kandlur: Support for RSVP-based Services over ATM Network, IEEE Global Internet, 1996.

32. T.Braun, S.Giorcelli: Quality of Service Support for IP Flows over ATM, Proc. KIVS '97, February 1997.

33. L.Salgarelli, A.Corghi, M. Smirnow, H. Sanneck, D. Witaszek: Supporting IP Multicast Integrated Services in ATM Networks, Internet Draft, work in progress November 1997.

34. L.Sagarelli, M.DeMarco, G.Meroni, V.Trecordi: Efficient transport of IP Flows Across ATM Networks, IEEE ATM '97 Workshop Proceedings, May 1997.

35. A.Schill, S.Kiihn, F.Breiter: Internetworking over ATM: Experiences with IP/IPng and RSVP, Computer Networks and ISDN Systems, Vol. 28, 1996.

36. The ATM Forum: MPOA Version 1.0, July 1997.

37. The ATM Forum: Issues and Approaches for Integrated PNNI (Draft), April 1996.

38. The ATM Forum: VTOA Desktop Baseline Text (Draft), January 1997.

39. Cells in Frames Alliance: ATM over Anything Cells in Frames, Cornell University, White Paper, 1996.

40. Jeremy Gunawardena. From max-plus algebra to nonexpansive mappings: a nonlinear theory for discrete event systems, pre-print, 1999.

41. Baccelli F., Cohen G., Olsder G. J., , and Quadrat J.-P. Synchronization and Linearity, An Algebra for Discrete Event Systems. John Wiley and Sons, 1992.

42. J. Naudts. Towards real-time measurement of traffic control parameters. Computer networks, 34:157-167, 2000.

43. Keshav. Computer Networking: An Engineering Approach. Prentice Hall, Englewood Cliffs, New Jersey 07632, 1996.

44. G. De Veciana, July 1996. Private Communication.

45. A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single node case. IEEE/ACM Trans. Networking, vol 1-3, pages 344— 357, June 1993.

46. A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The multiple node case. IEEE/ACM Trans. Networking, vol 2-2, pages 137-150, April 1994.

47. N. G. Duffield, K. K. Ramakrishan, and A. R. Reibman. Save: An algorithm for smoothed adaptative video over explicit rate networks. IEEE/ACM Transactions on Networking, 6:717-728, Dec 1998.

48. J. Rexford and D. Towsley. Smoothing variable-bit-rate video in an internetwork. IEEE/ACM Transactions on Networking, 7:202-215, April 1999.

49. J. D. Salehi, Z.-L. Zhang, J. F. Kurose, and D. Towsley, Supporting stored video: Reducing rate variability and end-to-end resource requirements through optimal smoothing. IEEE/ACM Transactions on Networking, 6:397-410, Dec 1998.

50. J. M. McManus and K.W. Ross. Video-on-demand over ATM: Constant-rate transmission and transport.

51. EE Journal on Selected Areas in Communications, 7:1087-1098, Aug 1996.

52. W.-C. Feng and J. Rexford. Performance evaluation of smoothing algorithms for transmitting variable-bit-rate video. IEEE Transactions on Multimedia, 1:302-312, Sept 1999.

53. C. S. Chang. Stability, queue length and delay, part i: Deterministic queuing networks. Technical Report Technical Report RC 17708, IBM, 1992.

54. M. Andrews. Instability of fifo in session-oriented networks. In Eleventh Annual ACM-S1AM Symposium on Discrete Algorithms (SODA 2000), January 2000.

55. I. Chlamtac, A. Farag' o, H. Zhang, and A. Fumagalli. A deterministic approach to the end-to-end analysis of packet flows in connection oriented networks. IEEE/ACM transactions on networking, (6)4:422-431,08 1998.

56. Hongbiao Zhang. A note on deterministic end-to-end delay analysis in connection oriented networks. In Proc of IEEE ICC'99, Vancouver, pp 1223-1227, 1999.

57. J.-Y. Le Boudec and G. Hebuterne. Comment on a deterministic approach to the end-to-end analysis of packet flows in connection oriented network. IEEE/ACM Transactions on Networking, February 2000.

58. R. L. Cruz. Sced+ : Efficient management of quality of service guarantees. In IEEE Infocom'98, San Francisco, March 1998.

59. F. Baker, C. Itturalde, F. Le Faucheur, and B. Davie. Aggregation of RSVP for IPv4 and IPv6 Reservations, March 2000. Internet Draft, work in progress.

60. S. Berson and S. Vincent. Aggregation of Internet Integrated Services State. In Proceedings of 6th IEEE/IFIP International Workshop on Quality of Service, Napa, CA, USA. IEEE/IFIP, May 18-20 1998.

61. J.-Y. Le Boudec. Application of Network Calculus To Guaranteed Service Networks. IEEE Trans, on Information Theory, 44(3), May 1998.

62. A. Charny. Delay bounds in a network with aggregate scheduling, February 2000. Cisco.

63. Rene L. Cruz. Quality of Service Guarantees in Virtual Circuit Switched Networks. IEEE Journal of Selected Areas in Communication, 13(6), August 1995.

64. R. Guerin, S. Blake, and S. Herzog. Aggregating RSVP-based QoS Requests, November 1997. Internet Draft, work in progress.

65. J.Y. LeBoudec. A proven delay bound for a network with aggregate scheduling. Technical Report DSC2000/002, EPFL-DSC, January 2000.

66. Abhay K. Parekh and Robert G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: The Single-Node Case. IEEE/ACM Transactions on Networking, 1(3), June 1993.

67. Abhay K. Parekh and Robert G. Gallager. A Generalized Processor Sharing Approach to Flow Control in Integrated Services

68. S. Shenker, C. Partridge, and R. Guerin. Specification of Guaranteed Quality of Service, September 1997. RFC 2212.

69. S. Shenker and J. Wroczlawski. General Characterization Parameters for Integrated Service Network Elements, September 1997. RFC 2216.

70. I. Stoica and H. Zhang. Providing guaranteed services without per-flow management. Technical Report CMU-CS-99-133, Carnegie-Mellon University, May 1999.

71. A. Terzis, J. Krawczyk, J. Wroczlawski, and L. Zhang. RSVP Operation over IP Tunnels, January 2000. RFC 2746.

72. Paul White and Jon Crowcroft. Integrated Services in the Internet: State of the Art. Proceedings of IEEE, 85(12), December 1997.

73. John Wroclawski. RFC 2210 The Use of RSVP with IETF Integrated Services. Informational RFC, September 1997.

74. Hui Zhang. Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks. Proceedings of the IEEE, 83(10), October 1995.

75. Anderson & Spong, "Bilateral Control of Teleoperators with Time Delay," IEEE Transactions on Automatic Control, v34, n5 (May 1989) pp. 494-501.

76. Braden, Clark, & Shenker, "Integrated Services in the Internet Architecture: an Overview," IETF RFC-1633, July 1994.

77. Burdea, Force and Touch Feedback for Virtual Reality, John Wiley & Sons, New York, 1996.

78. Christiansen, Jeffay, Ott, & Smith, "Tuning RED for Web Traffic," Proceedings of ACM S1GCOMM 2000, Stock-holm, Sweden, August-September 2000, pp. 139-150.

79. Floyd & Jacobson, "Random Early Detection gateways for Congestion Avoidance," IEEE/ACM Trans, on Network-ing, vl, n4, August 1993, p. 397-413.

80. Floyd & Fall, "Promoting the Use of End-to-End Congestion Control in the Internet," IEEE/ACM Transactions on Networking, August 1999.

81. Kessler & Hodges, "A Network Communication Protocol for Distributed Virtual Environment Systems," Proceedings of Virtual Reality Annual International Symposium '96, March 1996, pp. 214221.

82. Mark, Randolph, Finch, Van Verth & Taylor, "Adding Force Feedback to Graphics Systems: Issues and Solutions," Proceedings of Siggraph 96, New Orleans, LA, August, 1996, pp. 447-452.

83. Parris, Jeffay, & Smith, "Lightweight Active Router-Queue Management for Multimedia Networking," Multimedia Computing & Networking 1999, SPIE Proceedings Series, Vol. 3020, San Jose, CA, January 1999, pp. 162- 174.

84. Stone & Jeffay, "An Empirical Study of Delay Jitter Man-agement Policies," Multimedia Systems, v2, n6 (January 1995) pp. 267-279.88. http://www.ietf.org/html.charters/diffserv-charter.html

85. Rockafellar R. T. Convex Analysis. Princeton University Press, Princeton, 1970.