программа

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

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

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

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

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

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

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

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

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

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

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

Та же самая идея применима к пакетам, как показано на рис. 5.28, 6. Принцип таков: каждый хост соединяется с сетью через интерфейс, содержащий дырявое ведро, то есть конечную внутреннюю очередь. Если пакет появляется в очереди, когда очередь полная, пакет игнорируется. Другими словами, если несколько процессов хоста пытаются послать пакеты, когда в очереди уже стоит макси­мально допустимое число пакетов, новый пакет игнорируется. Такой интерфейс может быть реализован как аппаратно, так и программно операционной системой хоста. Он был предложен Тернером (Turner, 1986) и называется алгоритмом дырявого ведра. По сути это не что иное, как однолинейная система массового обслуживания с постоянным временем обслуживания.

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

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

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

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

В качестве примера представьте, что компьютер может производить данные со скоростью 25 млн байт в секунду (200 Мбит/с) и что сеть также работает на этой скорости. Однако маршрутизаторы могут поддерживать эту скорость пере­дачи данных лишь на коротких интервалах (пока не заполнится их буферная па­мять). В течение больших интервалов времени они могут обеспечить не более 2 млн байт в секунду. Теперь предположим, что данные поступают пачками по 1 млн байт, одна пачка продолжительностью 40 мс в каждую секунду. Чтобы уменьшить среднюю скорость до 2 Мбайт/с, можно воспользоваться алгоритмом дырявого ведра с выходной скоростью р = 2 Мбайт/с и емкостью С = 1 Мбайт. Это означает, что пачки до 1 Мбайта могут обрабатываться без потерь и что та­кие пачки будут передаваться в сеть за 500 мс независимо от того, как быстро они приходят.

На рис. 5.29, а показан вход дырявого ведра, на который со скоростью 25 Мбайт/с поступает пачка в течение 40 мс. На рис. 5.29, б показан выход, через который данные проходят с постоянной скоростью 2 Мбайт/с в течение 500 мс.

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

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

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

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

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

Другим важным протоколом с учетом состояния линий является IS-IS (Intermediate System to Intermediate System — связь между промежуточными сис­темами) — протокол, разработанный для сети DECnet и принятый впоследствии Международной организацией по стандартизации ISO для использования вме­сте с протоколом сетевого уровня CLNP, не требующим соединений. С тех пор он был модифицирован для поддержки также и других протоколов, в частности IP. Протокол IS-IS используется в некоторых магистралях сети Интернет (включая старую магистраль NSFNET) и в некоторых цифровых сотовых системах, напри­мер, в CDPD. В сети Novell NetWare применяется разновидность протокола IS­IS (NLSP) для маршрутизации IPX-пакетов.

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

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

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

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

Таблица 7.3. Пример отображения содержимого почтового ящика # Флаги Размер Отправитель Тема 1 К 1030 asw Изменение в системе MINIX 2 КА 6348 vovka Не все Вовки так уж противны 3 KF 4519 Amy N. Wong Запрос сведений 4 1236 bal Биоинформатика 5 104110 kaashoek Материалы по одноранговым сетям 6 1223 Frank Re: Вы рассмотрите мой запрос на грант? 7 3110 guido Наша статья принята 8 1204 dmr Re: посещение моего студента

Каждая отображаемая строка содержит несколько полей, извлеченных из кон­верта или заголовка соответствующего сообщения. В простой системе электрон­ной почты список отображаемых полей встроен в программу. В более сложных системах пользователь может выбрать отображаемые поля, а настройки пользо­вателя будут храниться в специальном файле, называющемся профилем пользо­вателя. В данном примере первое отображаемое поле — номер сообщения. Вто­рое поле, Flags (флаги) может содержать флаг К, означающий, что сообщение не является новым, уже было прочитано и хранится в почтовом ящике; флаг А, означающий, что на данное сообщение уже был отправлен ответ; и/или флаг F, означающий, что сообщение было переадресовано кому-то еще. Возможно также использование и других флагов.

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

После того как программа отобразила заголовки, пользователь может выпол­нить одну из нескольких команд: чтение, удаление письма и т. д. Старые систе­мы с текстовым интерфейсом обычно управлялись с помощью односимвольных команд, таких как Т (вывести сообщение), А (создать ответ), D (удалить сообще­ние) и F (переслать). Более современные системы имеют графический интер­фейс. Обычно пользователь выбирает сообщение с помощью мыши, затем щел­кает на значке, соответствующем определенному действию (выводу сообщения, созданию ответа, удалению и переадресации).

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