приложение

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

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

Методы, рассмотренные нами ранее, направлены на уменьшение перегрузок и по­вышение производительности в сетях передачи данных.

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

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

Процесс принятия решения об обработке или игнорировании потока сложнее, нежели простое сравнение запрашиваемых потоком параметров (пропускной спо­собности, буферной памяти, времени центрального процессора) с имеющимися. Во-первых, хотя многие приложения и знают свои требования к пропускной способности, они понятия не имеют, какой объем буферной памяти и сколько тактов работы процессора им требуется. Следовательно, нужен, по крайней мере, иной способ описания потоков. Далее, приложения весьма различаются по толе­рантности в отношении пропущенного предельного срока обработки. Наконец, некоторые приложения могут поторговаться за параметры пакетов, а некоторые не могут. Скажем, проигрыватель видео, предоставляющий обычно 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-мегабайтный поток тем же са­мым маршрутизатором мог бы быть принят.

Стандарт Н.323 был разработан ITU. В Интернет-сообществе многим он показался типичным продуктом телефонной компании: громоздким, сложным и недостаточ­но гибким. Было решено организовать специальный комитет IETF для создания более простой и гибкой системы передачи речи поверх IP. Основным результа­том деятельности этого комитета стал протокол SIP (Session Initiation Protocol — протокол запуска соединения), описанный в RFC 3261. Протокол оговаривает способ установки телефонных соединений через Интернет, технологию организа­ции систем для видеоконференций и способы создания других мультимедийных приложений. В отличие от Н.323, представляющего собой целый набор протоко­лов, SIP — это единый модуль, способный взаимодействовать с разнообразными интернет-приложениями. Например, номера телефонов определяются в виде URL, то есть на веб-страницах можно размещать гиперссылки, щелкнув на которых, пользователь сможет установить телефонное соединение (примерно так же схема mailto позволяет написать электронное письмо и отправить его по указанному в ссылке адресу).

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

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

Телефонные номера в SIP представляются в виде URL со схемой sip. Напри­мер, sip:ilse@cs.university.edu свяжет вас с пользователем по имени Ilse, хост кото­рого определяется DNS-именем cs.university.edu. SIP URL могут содержать так­же адреса формата IPv4, IPv6 или реальные номера телефонов.

Протокол SIP является текстовым, он построен по модели HTTP. Одна из сторон посылает ASCII-сообщение, в котором первая строка содержит имя мето­да, а ниже следуют дополнительные строки, содержащие заголовки для передачи параметров. Многие заголовки взяты из стандарта MIME, что позволяет SIP взаи­модействовать с существующими интернет-приложениями. Шесть методов, оп­ределяемых базовой спецификацией, перечислены в табл. 7.18.

Таблица 7.18. Методы SIP, определяемые базовой спецификацией Метод Описание INVITE Запрос запуска сеанса связи АСК Подтверждение запуска сеанса BYE Запрос окончания сеанса OPTIONS Опрос возможностей хоста CANCEL Отмена запроса REGISTER Информирование сервера переадресации о текущем местоположении пользователя

Для установки сеанса связи звонящий должен либо создать ТСР-соединение с вызываемым абонентом и послать по нему сообщение INVITE, либо послать это же сообщение в UDP-пакете. В обоих случаях заголовки, содержащиеся во вто­рой и всех последующих строках, описывают структуру тела сообщения, содер­жащего информацию о возможностях звонящего, типах мультимедиа и форма­тах. Если вызываемый абонент принимает звонок, он посылает в качестве ответа трехразрядный код результата типа HTTP (группы этих кодов перечислены в табл. 7.13, код 200 означает прием вызова). Следом за строкой с кодом результа­та вызываемый абонент может также сообщить данные о своих возможностях, типах мультимедиа и форматах.

Соединение устанавливается путем тройного рукопожатия, звонящий высы­лает А СК как для окончания работы протокола, так и для подтверждения приема кода 200.

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

Метод OPTIONS применяется для опроса возможностей машины. Обычно это делается перед запуском сеанса связи для того чтобы определить, поддержива­ется ли тип сеанса, на который рассчитывает вызывающая сторона (например, передача голоса поверх IP).

Метод REGISTER относится к возможности протокола SIP разыскивать поль­зователя и соединяться с ним, даже если его нет дома. Сообщение, содержащее данный метод, отправляется на поисковый сервер SIP, хранящий данные о том, кто где находится в данный момент. Впоследствии с помощью этого сервера мож­но попробовать найти абонента. Операция переадресации, используемая при этом, показана на рис. 7.35. На этом рисунке мы видим, что звонящий отправляет со­общение INVITE на прокси-сервер. Это делает возможную переадресацию неза­метной. Прокси пытается разыскать абонента и посылает INVITE по найденному адресу. Дальнейшее общение представляет собой коммутацию последовательно­сти сообщений при «тройном рукопожатии». Сообщения LOOKUP и REPLY не входят в протокол SIP; на этой стадии может использоваться любой подходящий протокол в зависимости от типа поискового сервера.

Рис. 7.35. Использование прокси и серверов переадресации в протоколе SIP

ЗВО!

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

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

Первые четыре приложения предъявляют высокие требования к надежности. Некорректная доставка битов должна быть исключена. Обычно это достигается подсчетом контрольной суммы для каждого пакета и ее проверкой у получателя.

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

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

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

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

В сетях ATM принята следующая классификация потоков по требованиям к качеству обслуживания:

1. 
   Постоянная битовая скорость (например, телефония);
2. Переменная битовая скорость в реальном времени (например, сжатые видео­данные при проведении видеоконференций);
3. Переменная битовая скорость не в реальном времени (например, просмотр фильмов через Интернет);
   
4. Доступная битовая скорость (например, передача файлов).

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

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

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

Передача сообщения членам такой группы называется многоадресной рассыл­кой, а алгоритм маршрутизации этой операции — многоадресной маршрути­зацией. В этом разделе будет описан один из способов реализации многоадресной маршрутизации. Дополнительные сведения см. в (Chu и др., 2000; Costa и др., 2001; Kasera и др., 2000; Madruga and Garcia-Luna-Aceves, 2001; Zhang and Ryu, 2001).

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример работы алгоритма продвижения по встречному пути показан на рис. 5.14. Слева изображена подсеть, посередине —входное дерево для маршру­тизатора I этой подсети. На первом транзитном участке маршрутизатор I посы­лает пакеты маршрутизаторам F, Н, J и N, являющимся вторым ярусом дерева. Все эти пакеты прибывают к I по предпочитаемым линиям (по пути, совпадаю­щему с входным деревом), что обозначается кружками вокруг символов на рис. 5.14, в. На втором этапе пересылки формируются восемь пакетов — по два каждым маршрутизатором, получившим пакет после первой пересылки. Все во­семь пакетов попадают к маршрутизаторам, не получавшим ранее пакетов, а пять из них приходят по предпочитаемым линиям. Из шести пакетов, формируемых на третьем транзитном участке, только три прибывают по предпочитаемым ли­ниям (на маршрутизаторы С, Е и К). Остальные оказываются дубликатами.

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

Для таких приложений как аудио- и видеопередача, не так уж важно, 20 или 30 мс занимает доставка пакетов, до тех пор, пока время доставки постоянно. Колеба­ние (то есть, среднеквадратичное отклонение) времени доставки пакетов называет­ся флуктуацией. Если одни пакеты будут доставляться за 20 мс, а другие — за 30 мс,
изображение или звук начнет дрожать. В этом случае говорят о наличии сильных флуктуаций. На рис. 5.26 изображены примеры флуктуаций. Внутри системы, с другой стороны, может существовать договоренность о том, что 99 % пакетов должны быть доставлены с задержкой в диапазоне от 24,5 до 25,5 мс, и качество при этом будет вполне приемлемым.

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

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

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

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

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

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

Маршрутизатор, заваленный пакетами, может -выбирать пакеты просто слу­чайным образом, но обычно имеются более оптимальные варианты. Выбор пакета, который будет отвергнут, может зависеть от приложения, пересылающего этот пакет. Для передачи файла более старый пакет ценится выше нового, так как от­вержение пакета номер б и сохранение пакетов с номерами с 7-го по 10-й может привести к тому, что получатель запросит еще раз пакеты с 6-го по 10-й (если полу­чатель просто отвергает все пакеты, приходящие не в том порядке). В файле, со­стоящем из 12 пакетов, выбрасывание 6-го пакета может потребовать повторной передачи пакетов с 7-го по 12-й, тогда как выбрасывание пакета номер 10 может потребовать повторной передачи только пакетов с 10-го по 12-й. Для мультиме­дийных приложений, напротив, новый пакет важнее старого. Первую стратегию (старое лучше нового) часто называют винной стратегией, а вторую (новое луч­ше старого) — молочной стратегией.

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

Для реализации интеллектуальной стратегии выбрасывания части информа­ции приложения должны помечать свои пакеты классами приоритетов, соответ­ствующими их важности. В этом случае маршрутизаторы смогут сначала выбросить пакеты нижнего класса, затем следующего за ним и т. д. Конечно, при отсутствии стимула все будут помечать свои пакеты не иначе как ОЧЕНЬ ВАЖНО — НИ В КОЕМ СЛУЧАЕ НЕ ВЫБРАСЫВАТЬ.

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

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