уменьшить

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

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

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

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

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

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

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

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

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

В-третьих, может произойти искажение порядкового номера — например, вмес­то номера 4 будет принято число 65 540 (ошибка в 1-м бите); в этом случае паке­ты с 5-го по 65 540-й будут игнорироваться некоторыми маршрутизаторами как устаревшие.

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

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

Структура данных, используемая маршрутизатором В для работы с подсетью, изображенной на рис. 5.11, а, показана на рис. 5.12. Каждый ряд здесь соответству­ет недавно полученному, но еще не полностью обработанному пакету состояния линий. В таблице записываются адрес отправителя, порядковый номер, возраст и данные. Кроме того, в таблице содержатся флаги рассылки и подтверждений для каждой из трех линий маршрутизатора В (к А, С и F соответственно). Флаги отсылки означают, что этот пакет следует отослать по соответствующей линии. Флаги подтверждений означают, что нужно подтвердить получение этого пакета по данной линии.

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

Однако ситуация с третьим пакетом, полученным от маршрутизатора Е, отли­чается. Он был получен дважды, по линиям ЕАВ и EFB, Следовательно, его нуж­но отослать только С, но подтверждения выслать и А, и jF, как указывают биты.

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

Представьте себе ведро с маленькой дырочкой в днище, как показано на рис. 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 мс.

В январе 1977 году правительство Соединенных Штатов приняло продукцион­ный шифр, разработанный фирмой IBM, в качестве официального стандарта для несекретных сведений. Этот шифр, получивший название DES (Data Encryption Standard — стандарт шифрования данных), получил широкое распространение в промышленности для защиты информации. В своем исходном виде он уже боль­ше не является надежным, но в модифицированном виде все еще полезен. Сейчас мы объясним принципы его работы.

Схема DES-шифра показана на рис. 8.6, а. Открытый текст шифруется блоками по 64 бита, в результате чего на выходе получаются 64-битные блоки зашифро­ванного текста. Алгоритм, использующий 56-разрядный ключ, состоит из 19 от­дельных этапов. На первом этапе выполняется независимая перестановка 64 раз­рядов открытого текста. Последний представляет собой обратную перестановку. Предпоследний этап меняет местами левые и правые 32 разряда. Остальные 16 эта­пов функционально идентичны, но управляются разными функциями входного ключа. Алгоритм был разработан так, чтобы дешифрация выполнялась тем же ключом, что и шифрование. Это обеспечивает соответствие алгоритма принципу симметричных ключей. Этапы при расшифровке просто выполняются в обрат­ном порядке.

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

Функция состоит из четырех последовательно выполняемых шагов. Сначала из 32 разрядов правой части Rhl с помощью фиксированной перестановки и дуб­лирования формируется 48-разрядное число Е. На втором шаге число Е и ключ Kt складываются по модулю 2. Затем выход разделяется на восемь групп по шесть разрядов, каждая из которых преобразуется независимым S-блоком в 4-раз­рядные группы. Наконец, эти 8 • 4 разряда пропускаются через Р-блок.

На каждом из 16 этапов используются различные функции исходного ключа. Перед началом работы алгоритма к ключу применяется 56-разрядная переста­новка. Перед каждым этапом ключ разделяется на две группы по 28 разрядов, каж­
дая из которых вращается влево на число разрядов, зависящее от номера этапа. Ключ К{ получается из результата этой операции при помощи еще одной пере­становки 56 разрядов. На каждом этапе из 56 разрядов ключа выбираются 48 раз­рядов, которые также переставляются местами.

 

L,-

64-разрядный открытый текст j j | У Ц У У

1-1

illlllll UUUU

Стандарт шифрования данных DES" title="Стандарт шифрования данных DES" border=0 width=194 height=197 src="http://s55.radikal.ru/i147/1007/25/e1da771fc25d.png">

ы *

Начальная перестановка

У V У У У У У

Итерация 1

У У У У У У У У

Итерация 2

Итерация 16

У У У X У У

Перестановка 32 битов

у у у у у у уу

Инверсная перестановка

 

ttfттттУ

32 бита L,

32 бита Я/

64-разрядный зашифрованный текст а

 

Рис. 8.6. Стандарт шифрования данных DES: общий вид (а); детализация одного из этапов (б)

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

Стандарт шифрования данных DES был полон противоречий с самого мо­мента его создания. Он основывался на шифре Люцифер (Lucifer), разработан­ном и запатентованном корпорацией IBM, с той разницей, что IBM использова­ла 128-разрядный, а не 56-разрядный ключ. Когда федеральное правительство

Соединенных Штатов пожелало стандартизировать какой-то шифр для несек­ретного применения, оно «пригласило» IBM на «обсуждение» этого вопроса с Агентством национальной безопасности, NSA (National Security Agency), являю­щимся самым крупным в мире работодателем в области математики и крипто­анализа. Агентство национальной безопасности США настолько секретно, что существует даже такая популярная шутка:

Вопрос: Что означает аббревиатура NSA?

Ответ: No Such Agency — такого агентства нет.

После этих обсуждений корпорация IBM уменьшила длину ключа со 128 до 56 бит и решила держать в секрете процедуру разработки стандарта DES. Мно­гие полагали, что длина ключа была уменьшена, чтобы гарантировать, что NSA сможет взломать DES, но организациям с более низким финансированием это будет не по силам. Вероятно, цель засекречивания проекта состояла в сокрытии потайного хода, позволяющего Агентству национальной безопасности еще легче взламывать шифр DES. Когда сотрудник этого управления предложил Институ­ту инженеров по электротехнике и электронике (IEEE) отменить планирую­щуюся конференцию по криптографии, ощущения комфорта это не прибавило. Агентство национальной безопасности всегда препятствовало всему.

В 1977 году ученые Стэнфордского университета, занимающиеся исследова­ниями в области криптографии, Диффи (Diffie) и Хеллман (Hellman), разрабо­тали машину для взлома кода DES и оценили стоимость ее создания в 20 млн долларов. По небольшому участку открытого текста и соответствующего ему за­шифрованному тексту эта машина путем полного перебора 256 вариантов за один день могла найти 56-разрядный ключ. На сегодняшний день такая машина могла бы стоить около 1 млн долларов.

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

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

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

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

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

Реализация исходного алгоритма маркерного ведра подразумевает наличие пе- ременной, считающей маркеры. Счетчик увеличивается на единицу через равные интервалы времени ДГи уменьшается при посылке пакета. Когда счетчик уменьша- „ ется до нуля, передача пакетов останавливается. В варианте с учетом количества переданных байт счетчик увеличивается на k байт каждые AT секунд и уменьшается на размер переданного пакета.

Суть алгоритма маркерного ведра состоит в том, что он допускает передачу Данных пачками, но ограничивает длительность пачки. Для примера рассмотрим рис. 5.29, в, на котором изображено маркерное ведро емкостью 250 Кбайт. Мар­керы появляются с частотой, соответствующей выходной скорости 2 Мбайт/с. Предположим, что маркерное ведро заполнено, когда прибывает пакет данных , размером 1 Мбайт. Ведро может быть освобождено с максимальной скоростью 25 Мбайт/с примерно за 11 мс. Затем оно должно уменьшить скорость передачи ' До 2 Мбайт/с, пока не будет передан весь входной пакет данных.

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

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

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

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

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

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

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

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

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

Хорошо известно, что при борьбе с перегрузкой гораздо проще вовремя обнару­жить затор, чем дать ему развиться до критических размеров, а потом думать, что делать в сложившейся ситуации. Это соображение приводит к идее отвержения некоторых пакетов еще до того, как все буферное пространство будет заполнено скопившимися необработанными данными. Популярный алгоритм, реализующий данную идею, называется случайным ранним обнаружением (RED — Random Ear­ly Detection, Floyd и Jacobson, 1993). Некоторые транспортные протоколы (вклю­чая TCP) на потерю своих пакетов отвечают снижением трафика от источника, чего мы, в сущности, и добиваемся. Обоснование такой логики состоит в том, что TCP предназначен для проводных сетей, которые по сути своей являются очень надежными, и потеря пакетов в них чаще всего сигнализирует о переполнении буфера, а не об ошибках передачи. Этот факт и используется для уменьшения пе­регрузок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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