имя

Беспроводные веб-технологии — это, конечно, замечательное изобретение по­следних лет, однако далеко не единственное. Для многих не что иное, как мульти­медиа, служит чашей святого Грааля сетевых технологий. Слово «мультимедиа» возбуждает и физиков, и лириков, и разработчиков, и коммерсантов. Одни видят в мультимедиа бесконечный источник интересных технических проблем, связанных, например, с доставкой (интерактивного) видео по заказу, другие — не меньший источник прибыли. Поскольку для передачи мультимедийных данных требуется очень высокая пропускная способность, довольно трудно заставить систему рабо­тать даже поверх стационарных соединений. Что касается беспроводных техно­логий, то добиться даже VHS-качества пока что не удается, и на решение этой проблемы потребуется, как минимум, несколько лет. Мы будем рассматривать далее методы передачи мультимедийных данных по проводным сетям.

Буквально мультимедиа означает использование двух или более средств аудио­визуальной информации. Если бы издатель этой книги захотел присоединиться к всеобщей моде пускания пыли в глаза, он мог бы разрекламировать ее как ис­пользующую мультимедийные технологии. В конце концов, в ней действительно используются два средства информации: текст и графика (рисунки). Тем не ме­нее, когда употребляется это слово, обычно имеются в виду некие информаци­онные сущности, длящиеся во времени, то есть проигрываемые в течение опре­деленного интервала времени, обычно во взаимодействии с пользователем. На практике чаще всего это аудио и видео, то есть звук плюс движущееся изобра­жение.

Несмотря на такое довольно понятное определение, многие, говоря «мульти­медиа», имеют в виду только чисто звуковую информацию, например интернет- телефонию или интернет-радио. Строго говоря, они не правы. Более удачным термином в данном случае является словосочетание потоковая информация (strea­ming media), однако мы, поддавшись стадному инстинкту, все же будем имено­вать аудиоданные, передающиеся в реальном масштабе времени, «мультимедиа». В следующих разделах мы узнаем, как компьютер обрабатывает звук и видео и как он сжимает такого рода данные. Затем мы рассмотрим некоторые сетевые технологии, связанные с мультимедиа. Довольно понятно и в хорошем объе­ме (три тома) взаимодействие сетевых и мультимедийных технологий описано в (Steinmetz и Nahrstedt, 2002; Steinmetz и Nahrstedt, 2003а; Steinmetz и Nahr- stedt, 2003b),

Все идеи, рассматривавшиеся до сих пор, соответствуют модели, показанной в листинге 6.1: клиент сообщает серверу имя файла, а тот в ответ возвращает файл.

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

В 1995-1997 годы проблемная группа проектирования сети Интернет (IETF) прилагала множество усилий по продвижению архитектуры потокового мульти­медиа.

В результате появилось две дюжины документов RFC, начинающихся с префикса RFC и включающих порядковые номера 2205-2210. Общее название этих трудов — потоковые алгоритмы или интегральное обслуживание. Предла­гаемая технология предназначена как для одноадресных, так и для многоадрес­ных приложений. Примером первых может быть видеоклип на сайте новостей, доставляемый в виде потока пользователю, пожелавшему посмотреть его. При­мер вторых — набор станций цифрового телевидения, осуществляющих широко­вещательное распространение своих программ в виде потоков IP-пакетов. Дан­ной услугой может пользоваться большое число абонентов, расположенных в разных географических точках. Далее мы более подробно рассмотрим многоад­ресную рассылку, поскольку однонадресная передача — это лишь особый случай многоадресной. Во многих приложениях с многоадресной маршрутизацией груп­пы пользователей могут меняться динамически. Например, люди могут подклю­чаться к участию в видеоконференциях, но со временем это занятие им надоеда­ет, и они переключаются на мыльные оперы или спортивные каналы. В данном случае стратегия предварительного резервирования пропускной способности не совсем подходит, потому что при этом каждому источнику пришлось бы запоми­нать все изменения в составе аудитории. В системах, предназначенных для пере­дачи телевизионного сигнала миллионам абонентов, такой подход и вовсе не го­дится.

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

Каждый мар­шрутизатор может запросто следить за использованием своих выходных линий и других ресурсов. Например, с каждой линией может быть связана вещественная переменная и, значение которой в пределах от 0,0 до 1,0 отражало бы использова­ние линии за последнее время. Такую усредненную оценку загруженности линии можно получить с помощью несложных вычислений, периодически замеряя мгновенную загруженность линии /(0 либо 1) и рассчитывая новое значение пе­ременной и по формуле.

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

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

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

В очень больших сетях двухуровневой иерархии может оказаться недостаточ­но. Может потребоваться группировать регионы в кластеры, кластеры в зоны, зоны в группы, и т. д., пока у нас не иссякнет фантазия на названия для новых образований. В качестве примера многоуровневой иерархии рассмотрим марш­рутизацию пакета, пересылаемого из университета Беркли (Berkeley), штат Ка­лифорния, в Малинди (Malindi) в Кении. Маршрутизатор в Беркли знает детали топологии в пределах Калифорнии, но трафик, направляющийся за пределы шта­та, он посылает маршрутизатору в Лос-Анджелесе. Маршрутизатор в Лос-Анд­желесе может выбрать маршрут для трафика в пределах США, но все пакеты, на­правляемые за рубеж, переправляет в Нью-Йорк. Нью-йоркский маршрутизатор направит трафик на маршрутизатор страны назначения, ответственный за прием
трафика из-за границы. Он может располагаться, например, в Найроби. Нако­нец, направляясь вниз по дереву иерархии уже в пределах Кении, пакет попадет в Малинди.

На рис. 5.13 приведен количественный пример маршрутизации в двухуровне­вой иерархии с пятью регионами. Полная таблица маршрутизатора 1А, как пока­зано на рис. 5.13, б, состоит из 17 записей. При использовании иерархической маршрутизации, как показано на рис. 5.13, в, таблица, как и прежде, содержит сведения обо всех локальных маршрутизаторах, но записи обо всех остальных регионах концентрируются в пределах одного маршрутизатора, поэтому трафик во второй регион по-прежнему пойдет по линии 1В — 2А, а во все остальные ре­гионы — по линии 1С — ЗВ. При иерархической маршрутизации размер таблицы маршрутов уменьшается с 17 до 7 строк. Чем крупнее выбираются регионы, тем больше экономится места в таблице.

К сожалению, этот выигрыш памяти не достается бесплатно. Платой за умень­шение размеров таблицы маршрутов является увеличение длины пути. Напри- Мер, наилучший маршрут от 1А до 5С проходит через регион 2, однако при ис­пользовании иерархической маршрутизации весь трафик в регион 5 направляет­ся через регион 3, поскольку так лучше для большинства адресатов в регионе 5.

Когда единая сеть становится очень большой, возникает интересный вопрос: сколько уровней должна иметь иерархия? Для примера рассмотрим подсеть с 720 маршрутизаторами. Если иерархии нет, то каждому маршрутизатору необхо-

димо поддерживать таблицу из 720 строк. Если подсеть разбить на 24 региона по 30 маршрутизаторов в каждом регионе, тогда каждому маршрутизатору потребу­ется 30 локальных записей плюс 23 записи об удаленных регионах, итого 53 за­писи. При выборе трехуровневой иерархии, состоящей из 8 кластеров по 9 ре­гионов из 10 маршрутизаторов, каждому маршрутизатору понадобится 10 строк в таблице для локальных маршрутизаторов, 8 строк для маршрутизации в дру­гие регионы в пределах своего кластера, плюс 7 строк для удаленных кластеров, итого 25 строк. Камоун (Kamoun) и Кляйнрок (Kleinrock) в 1979 году показа­ли, что оптимальное количество уровней иерархии для подсети, состоящей из N маршрутизаторов, равно In N. При этом потребуется е In Дозаписей для каждо­го маршрутизатора. Они также показали, что увеличение длины эффективного среднего пути, вызываемое иерархической маршрутизацией, довольно мало и обычно является приемлемым.

Маршрутизация на основе векторов расстояний использовалась в сети ARPANET вплоть до 1979 года, когда ее сменил алгоритм маршрутизации с учетом состоя­ния линий. Отказаться от прежнего алгоритма пришлось по двум причинам. Во- первых, старый алгоритм при выборе пути не учитывал пропускную способность линий. Пока все линии имели пропускную способность 56 Кбит/с, в учете пропу­скной способности не было необходимости. Однако стали появляться линии со скоростью 230 Кбит/с, а затем и 1,544 Мбит/с, и не принимать во внимание про­пускную способность стало невозможно. Конечно, можно было ввести пропуск­ную способность в качестве множителя для единицы измерения, но имелась еще и другая проблема, заключавшаяся в том, что алгоритм слишком долго приходил к устойчивому состоянию (проблема счета до бесконечности). Поэтому он был заменен полностью новым алгоритмом, который сейчас называется маршрутиза­цией с учетом состояния линий. Варианты этого алгоритма широко применяют­ся в наши дни.

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

1. Обнаруживать своих соседей и узнавать их сетевые адреса.
2. Измерять задержку или стоимость связи с каждым из своих соседей.
3. Создавать пакет, содержащий всю собранную информацию.
4. Посылать этот пакет всем маршрутизаторам.
5. Вычислять кратчайший путь ко всем маршрутизаторам.

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

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

Процесс принятия решения об обработке или игнорировании потока сложнее, нежели простое сравнение запрашиваемых потоком параметров (пропускной спо­собности, буферной памяти, времени центрального процессора) с имеющимися. Во-первых, хотя многие приложения и знают свои требования к пропускной способности, они понятия не имеют, какой объем буферной памяти и сколько тактов работы процессора им требуется. Следовательно, нужен, по крайней мере, иной способ описания потоков. Далее, приложения весьма различаются по толе­рантности в отношении пропущенного предельного срока обработки. Наконец, некоторые приложения могут поторговаться за параметры пакетов, а некоторые не могут. Скажем, проигрыватель видео, предоставляющий обычно 30 кадров/с, хожет согласиться работать на 25 кадрах/с, если для 30 не хватает пропускной способности. Аналогично, можно настраивать количество пикселов на кадр, по­лосу пропускания для аудиоданных и другие свойства потоков различных при­ложений.

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

В качестве содержимого спецификации потока рассмотрим пример, базирую­щийся на RFC 2210 и RFC 2211 (табл. 5.4). В спецификации содержится пять параметров, первый из которых, Скорость маркерного ведра, хранит число бай­тов, поступающих в «ведро» за секунду. Это максимум, который отправитель мо­жет поддерживать в течение длительного времени, усредненный по большому временному отрезку.Второй параметр — размер маркерного ведра в байтах. Если, к примеру, Ско­рость маркерного ведра составляет 1 Мбит/с, а размер ведра равен 500 Кбайт, то его можно будет наполнять данными в течение 4 с. Все, что будет посылаться по­сле этого, будет теряться.

Третий параметр, Пиковая скорость передачи данных, — это максимальная до­пустимая скорость даже для коротких промежутков времени. Отправитель ни в коем случае не должен превышать это значение.

Наконец, последние два параметра определяют минимальный и максималь­ный размеры пакетов, включая заголовки транспортного и сетевого уровней (на­пример, TCP и IP). Минимальный размер важен, поскольку обработка каждого пакета занимает какое-то, пусть даже очень малое, время. Маршрутизатор, мо­жет быть, готов принимать 10 000 пакетов в секунду по 1 Кбайт каждый, но не готов обрабатывать 100 ООО пакетов по 50 байт в секунду несмотря на то, что во втором случае скорость передачи данных меньше, чем в первом. Максимальный размер пакета не менее важен, но уже по другой причине. Дело в том, что сущест­вуют определенные внутрисетевые ограничения, которые ни в коем случае не должны быть превышены. Например, если путь потока лежит через Ethernet, то максимальный размер пакета будет ограничен 1500 байтами независимо от того, какого размера пакеты могут поддерживать другие части сети.

Интересно, каким образом маршрутизатор преобразует спецификацию пото­ка в набор определенных резервируемых ресурсов? Это отображение является специфическим и не стандартизованным действием. Допустим, маршрутизатор может обрабатывать 100 000 пакетов/с. Если ему предлагается пропустить через себя поток со скоростью 1 Мбайт/с с максимальным размером пакета, состав­ляющим 512 байт, он может легко посчитать, что такой поток дает 2048 паке­тов/с, значит, под него необходимо отвести 2 % времени работы процессора, а лучше немного больше, чтобы избежать больших задержек обслуживания. Ес­ли политика маршрутизатора не позволяет ему резервировать более 50 % про­цессорного времени (что подразумевает половинную задержку) и если 49 % уже зарезервировано, то поток будет отвергнут. Подобные вычисления необходимо производить для всех резервируемых ресурсов.

Чем строже спецификация потока, тем лучше для маршрутизаторов. Если же в спецификации говорится, что Скорость маркерного ведра составляет 5 Мбайт/с, однако пакеты могут быть размером от 50 до 1500 байт, значит, скорость переда­чи пакетов может колебаться от 3500 до 105 000 пакетов/с. Маршрутизатор, ужаснувшись при виде последнего числа, может отвергнуть такой поток. При ми­нимальном размере пакета, равном 1000 байт, 5-мегабайтный поток тем же са­мым маршрутизатором мог бы быть принят.

Возможность управления трафиком — это неплохой начальный шаг в деле обес­печения гарантированного качества обслуживания. Однако на самом деле исполь­зование этих методов неявно означает, что все пакеты в потоке должны следовать по одному и тому же пути. При распределении их случайным образом между не­сколькими маршрутизаторами невозможно что-либо гарантировать. Следовательно, между источником и приемником должно быть установлено нечто вроде вир­туального канала, и все пакеты, принадлежащие данному потоку, должны следо­вать по указанному маршруту.

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

1. Пропускная способность.
2. Буферное пространство.
3. Время центрального процессора.
   

Наиболее очевидно резервирование пропускной способности. Если потоку не­обходима скорость 1 Мбит/с, а исходящая линия может работать со скоростью 2 Мбит/с, то направить три потока с такими параметрами по этой линии не уда­стся. То есть резервирование пропускной способности означает предотвращение предоставления канала большему числу абонентов, чем канал может обработать.

Вторым дефицитным ресурсом является буферное пространство. Когда при­бывает пакет, он обычно оседает на сетевой интерфейсной карте (это действие управляется аппаратно). Затем программному обеспечению маршрутизатора не­обходимо скопировать пакет в буфер оперативной памяти и поставить содержи­мое этого буфера в очередь на отправку по выбранной исходящей линии. Если буферное пространство недоступно, входящий пакет приходится игнорировать, Поскольку его просто негде сохранить. Для обеспечения хорошего качества об­служивания можно резервировать некоторую часть буферной памяти под кон­кретный поток, чтобы ему не пришлось бороться за буфер с другими потоками. И тогда при передаче потока ему всегда будет предоставляться выделенная часть буфера, вплоть до некоторого максимума.

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

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

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

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

Мы уже видели различия характеристик сети при высокой и низкой флуктуа­ции на рис. 5.26. На рис. 5.27 изображен поток пакетов, доставляемый при значи­тельной флуктуации. Пакет 1 посылается с сервера в момент времени ( = 0 с и прибывает в момент времени t = 1 с. Задержка пакета 2 составляет уже не 1, а 2 с. Прибывающие пакеты буферизируются на клиентской машине.

В момент времени 10 с начинается воспроизведение, при этом пакеты с 1-го по 6-й уже находятся в буфере, поэтому их можно оттуда извлекать через равные интервалы и воспроизводить. К сожалению, пакету 8 не повезло: он задержался настолько, что его невозможно воспроизвести вовремя. Выдача пакетов приоста­навливается до его прибытия. Возникает досадная задержка в проигрывании му­
зыки или фильма. Проблему можно решить увеличением задержки начала выда­чи пакетов, но для этого потребуется буфер большей емкости. Все коммерческие веб-сайты, на которых содержится потоковое видео или аудио, используют про­игрыватели, которые начинают воспроизведение только после примерно десяти- секундной буферизации.

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

Одним из первых был алгоритм справедливого обслуживания (Nagle, 1987). Суть его состоит в том, что маршрутизаторы организуют отдельные очереди для каждой исходящей линии, по одной для каждого потока. Как только линия осво­бождается, маршрутизатор начинает циклически сканировать очереди, выбирая первый пакет следующей очереди. Таким образом, если за данную исходящую линию борются п хостов, то каждый из них имеет возможность отправить свой пакет, пропустив п - 1 чужих пакетов. Агрессивному хосту не поможет то, что в его очереди стоит больше пакетов, чем у остальных.

Однако и с этим алгоритмом связана одна проблема: предоставляемая им про­пускная способность напрямую зависит от размера пакета, используемого хос­том: большая часть предоставляется хостам с большими пакетами, и меньшая — хостам с небольшими пакетами. В книге (Demers и др., 1990) предлагается улуч­шенная версия, в которой циклический опрос производится с целью выхватыва­ния не пакета, а байта. То есть очереди сканируются побайтно до того момента, пока не будет выхвачен последний байт последнего пакета. После этого пакеты Отправляются в том порядке, в котором они заканчивались при опросе очередей. 

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

видеосерверам большую пропускную способность, чем обычным файл-серверам, чтобы они могли посылать два или более байт за такт опроса. Такая модифика­ция алгоритма называется взвешенным справедливым обслуживанием. Иногда весовой коэффициент эквивалентен числу потоков, генерируемых машиной, та­ким образом все процессы получают равные доли пропускной способности. Од­на из эффективных реализаций данного алгоритма описывается в (Shreedhar и Varghese, 1995). Все чаще и чаще встречаются аппаратные реализации передачи пакетов через маршрутизаторы или коммутаторы (Elhanany и др., 2001).