бит

вый блок складывается по модулю 2 со случайным вектором инициализации, IV (Initialization Vector), передаваемым вместе с зашифрованным текстом.

Ро Р1 Рг Рз 1111

Режим шифрованной обратной связи" title="Режим шифрованной обратной связи" border=0 width=279 height=77 src="http://s16.radikal.ru/i190/1007/20/aab6e803acc1.jpg"> Со С1 Сг С з а

Однако у метода сцепления блоков шифра есть и недостаток, заключающийся в том, что прежде чем может начаться шифрование или дешифрация, должен по­явиться целый 64-битовый блок данных. Для пользователей интерактивных тер­миналов, набирающих строки короче восьми символов и ждущих ответа, такой
метод не подходит. Для побайтового шифрования может применяться режим шифрованной обратной связи с использованием (тройного) DES, как показано на рис. 8.11. Для стандарта AES идея остается той же самой, только используется 128-разрядный сдвиговый регистр. На рисунке мы видим состояние шифрующей машины после того, как байты с 0 по 9 уже зашифрованы и посланы. Когда при­бывает десятый байт открытого текста, как показано на рис. 8.11, а, алгоритм DES обрабатывает 64-разрядный сдвиговый регистр, чтобы произвести 64-раз- рядный зашифрованный блок. Самый левый байт этого зашифрованного текста извлекается и складывается по модулю 2 с Р10. Этот байт передается по линии. Затем сдвиговый регистр сдвигается влево на 8 разрядов. При этом байт С2 извле­кается с левого конца регистра, а байт С10 вставляется в него на освободившееся место справа от С9. Обратите внимание на то, что содержимое сдвигового регист­ра зависит от всей предыстории открытого текста, так что повторяющиеся фраг­менты исходного текста будут кодироваться каждый раз по-разному. Как и для метода сцепленных блоков шифра, для начала шифрования этим методом требу­ется вектор инициализации.

 

64-разрядный сдвиговый регистр С2 Сз с4 с5 С6 С7 С8 С9 64-разрядный сдвиговый регистр Сг Сз С4 С5 С6 С7 Cg С9

Шифратор

Шифратор Выбор левого байта

Ключ •

Ключ

I

Выбор левого байта

 

--------------- С10

- Сложение по модулю 2

а                                                                                                 б

Рис. 8.11. Режим шифрованной обратной связи (а); обратная связь по выходу (б)

При использовании режима шифрованной обратной связи дешифрация ана­логична шифрованию. В частности, содержимое сдвигового регистра шифрует­ся, а не дешифруется, поэтому байт, который складывается по модулю 2 с Ci0 для получения Pw равен тому байту, который складывается по модулю 2 с PlQ для получения С10. Пока содержимое двух сдвиговых регистров идентично, де­шифрация выполняется корректно. Это показано на рис. 8.11, б.

>1*0

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

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

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

Относительно новым явлением являются равноранговые сети, в которых боль­шое количество пользователей, имеющих обычно постоянное кабельное соедине­ние с Интернетом, работает с разделяемыми ресурсами. Первым широко извест­ным применением равноранговых сетей стало создание нелегальной системы Napster, 50 миллионов пользователей которой обменивались звукозаписями без разрешения обладателей авторских прав. Это продолжалось до тех пор, пока сеть Napster после бурной полемики не была закрыта решением суда. Тем не менее, У равноранговых сетей есть множество интересных и в то же время легальных применений. С ней связаны некоторые проблемы, сходные с проблемой маршру­тизации, хотя и не такие же, как мы только что изучили. Сейчас мы их вкратце рассмотрим.

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

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

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

Для решения этой проблемы было предложено несколько различных алго­ритмов. Мы рассмотрим метод хорды (Dabek и др., 2001а; Stoica и др., 2001). Несколько упрощенное объяснение принципа его работы таково. Пусть система состоит из п пользователей. У каждого из них есть какие-то записи, и каждый го­тов хранить биты и части индекса, которые могут быть использованы другими. У каждого узла есть IP-адрес, который может быть закодирован ш-битным номе­ром с помощью хэш-функции. В методе хорды используется алгоритм SHA-1 для вычисления значения хэш-функции. SHA-1 применяется в криптографии, и мы рассмотрим его в главе 8. А сейчас нам просто надо знать, что это некоторая функция с аргументом в виде строки переменной длины и значением — 160-бит­ным числом высокой степени случайности. Таким образом, любой IP-адрес мож­но закодировать 160-битным числом, называемым идентификатором узла.

Концепция состоит в том, что вообще все 2160 идентификаторов располагают­ся в возрастающем порядке, образуя большой круг чисел. Некоторые из иденти­фикаторов соответствуют реально существующим узлам, но это лишь малая часть из них. На рис. 5.22 показан круг идентификаторов для т = 5 (на дуги внутри круга пока внимания не обращайте). В этом примере реальным узлам соответст­вуют идентификаторы 1, 4, 7, 12, 15, 20 и 27. На рисунке кружочки с этими номе­рами закрашены. Всем остальным идентификаторам нельзя поставить в соответ­ствие какие-либо узлы.

Определим функцию определения последователя successor{k) как идентифи­катор первого реального узла, следующего после k в описанном нами круге (по часовой стрелке). Например, successor^) = 7, successor^8) = 12, successor^22) = 27.

Названия записей (например, названия песен, имена предков и т. п.) также обрабатываются хэш-функцией hash (с помощью алгоритма SHA-1) и превраща­
ются в 160-битные числа, называемые ключами. Таким образом, чтобы получить ключ (key) из названия записи (пате), необходимо вычислить key = hash(name). Такое вычисление является просто локальной процедурой, вызовом функции hash. Если держатель генеалогической записи хочет сделать ее доступной всем, он должен построить кортеж (набор взаимосвязанных величин), состоящий из по­лей (пате, мой_1Р-адрес), и затем выполнить функцию successor(hash(name)) для сохранения кортежа в общепринятой форме. Если существует несколько запи­сей (на разных узлах) для одного и того же названия, все их кортежи будут хра­ниться на одном и том же узле. То есть индекс распределяется случайным обра­зом между узлами. Во избежание сбоев системы, для хранения кортежей на р узлах используется р различных хэш-функций, но далее мы не будем учитывать этот нюанс.

 

J	'4
2	А
3	4
5	7
9	12
17	20
м
5	7
6	7
8	12
12	12
20	20
/4
13	15
14	15
16	20
20	20
28	1

Таблица указателей узла 1

Таблица указателей узла 4

Таблица указателей узла 12

Поиск узла в равноранговых сетях" width=299 height=319 src="http://s58.radikal.ru/i161/1007/f4/be943eb71cbd.jpg" align=left hspace=12>

(18;                ......                      (14)

(31)              , . зо.; •••••■ - ц Реальный ,"2g'.                                  / узел                                                  ' (2В)                                     :

Поиск узла в равноранговых сетях" width=44 height=93 src="http://s58.radikal.ru/i161/1007/f4/be943eb71cbd.jpg" align=left hspace=12>

^Идентификатор (24)                узла (23) (22)

 

Рис. 5.22. Набор из 32 идентификаторов узлов, выстроенных по кругу (а). Закрашенные кружочки соответствуют реальным узлам. Дугами обозначены указатели с узлов 1,4 и 12. Подписи на дугах соответствуют индексам таблицы. Примеры таблиц указателей (б)

Если кто-то из пользователей затем захочет найти название записи (пате), он вычислит значение хэш-функции, получит ключ (key) и затем с помощью функ­ции successoiikey) сможет найти IP-адрес узла, хранящего кортежи индексов. Первый шаг осуществляется довольно просто, не в пример второму. Для того чтобы можно было найти IP-адрес узла, соответствующего какому-либо ключу, каждый узел должен поддерживать определенные служебные структуры данных. Одной из них является IP-адрес последователя. Например, на рис. 5.22 последо­ватель узла 4 — это узел 7, а последователь узла 7 — узел 12.

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

В качестве первой оптимизации алгоритма предлагается следующее: каждый узел должен знать IP-адрес не только последователя, но и предшественника, то­гда запрос можно будет распространять одновременно в двух направлениях — по часовой стрелке и против часовой стрелки, в зависимости от того, какой из путей кажется более коротким. Например, на рис. 5.22 узел 7 может отправить пакет по часовой стрелке, если ищется узел 10. А если ищется узел 3, то логичнее напра­вить пакет против часовой стрелки.

Даже с этой возможностью выбора направления линейный поиск остается крайне неэффективным методом для больших равноранговых сетей, поскольку среднее число узлов, которое потребуется обойти для поиска записи, равно п/2. Значительно ускорить поиск позволяет поддерживаемая каждым узлом специ­альная таблица, которая в методе хорд носит название таблицы указателей. В ней имеется т записей, пронумерованных от 0 до т - 1. Каждая запись содержит два поля: начало и IP-адрес последователя — successoristart), как показано на рис. 5.22, б. Значения полей записи i на узле k равны:

Start = k + 2' (modulo2m), IP-адрес successor (start [г]).

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

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

В качестве первого примера рассмотрим поиск ключа key = 3 на узле 1. Узел с идентификатором 1 знает, что 3 лежит где-то между ним самим и его последова­телем — узлом 4. Он делает вывод о том, что ключ находится на узле 4, и поиск прекращается. Результатом является IP-адрес узла 4.

Второй пример. Пусть узлу 1 теперь понадобилось найти ключ key = 14. Чис­ло 14 не находится между 1 и 4, поэтому необходимо заглянуть в таблицу указа­телей. Ближайшим предшественником 14 является 9, поэтому запрос направля­ется на IP-адрес, хранящийся в записи с полем начало, равным 9. Конкретно, это узел 12. Последний видит, что 14 находится между ним самим и последовате­лем — узлом 15, поэтому результатом поиска является IP-адрес узла 15.

Третий пример. Допустим, узлу 1 нужно найти ключ key =16. Запрос, как и в предыдущем примере, отправляется на узел 12. Но на этот раз узел не может са­мостоятельно ответить на него. Он пытается найти тот узел, который находится ближе всего к 16, но имеет меньший идентификатор. Им является узел 14, кото­рый ссылается, в свою очередь, на узел 15. Запрос туда и посылается. Узел 15 ви­дит, что 16 находится между ним самим и его последователем (20), поэтому он возвращает IP-адрес 20 просителю. Ответ возвращается сразу на узел 1.

Поскольку узлы могут появляться в сети и исчезать из нее в любое время, в ме­тоде хорд необходимо как-то обрабатывать подобные ситуации. Мы предполага­ем, что когда система начинала работать, она была достаточно небольшой, и узлы могли обмениваться информацией напрямую, выстраивая первичный круг иден­тификаторов и таблицы указателей. После этого уже необходима автоматизиро­ванная процедура. Когда новый узел г собирается войти в сеть, он должен войти в контакт с какой-либо из уже находящихся в сети станций и попросить ее поис­кать для него IP-адрес successor(r). Затем новый узел выясняет, кто будет его предшественником (successor(r) для предшественника). Все это нужно для того, чтобы можно было определить свое место в круге идентификаторов. Например, если узел 24 на рис. 5.22 захочет войти в сеть, он может поинтересоваться у лю­бого узла, чему равно значение successor(24). Выясняется, что оно равно 27. За­тем у узла 27 надо узнать, кто является его предшественником (20). После того как обоим этим узлам сообщается о существовании нового узла, узел 20 помеча­ет себе, что его последователем становится узел 24, а узел 27 — что этот узел ста­новится его предшественником. Кроме того, узел 27 передает ключи диапазона 21-24 новичку. С этого момента последний считается зарегистрированным в рав- норанговой сети.

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

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

Поиск узла в равноранговых сетях" width=248 height=149 src="http://s58.radikal.ru/i161/1007/f4/be943eb71cbd.jpg">

Максимальная пропускная способность подсети

Идеально

Перегрузка

Посланные пакеты

Рис. 5.23. При слишком высоком уровне трафика начинается перегрузка, и производительность сети резко снижается

/

Желательно

Метод хорд используется для создания распределенных файловых систем (Dabek и др., 2001b) и других приложений; научные изыскания в этой области идут и сейчас. Одна из равноранговых систем, Pastry, и ее приложения описаны в (Rowston and Druschel, 2001а; Rowston and Druschel, 2001b). Еще одна система, Freenet, обсуждается в (Clarke и др., 2002). Наконец, четвертая система этого ти­па описана в (Ratnasamy и др., 2001).

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

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

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

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

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

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

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

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

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

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

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

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

Все системы с обратной связью предполагают, что получившие информацию о перегрузке в сети хосты и маршрутизаторы предпримут какие-нибудь дейст­вия для устранения перегрузки. Чтобы данная схема работала, необходимо тща­тельно настроить временные параметры. Если каждый раз, когда два пакета прихо­дят одновременно, какой-нибудь нервный маршрутизатор будет кричать «Стоп1», а простояв без работы 20 мкс, он же будет давать команду «Давай!», система бу­дет находиться в состоянии постоянных незатухающих колебаний. С другой сто­роны, если маршрутизатор будет спокоен, как слон, и для большей надежности станет ждать 30 минут, прежде чем что-либо сообщить, то механизм борьбы с пе­регрузкой будет реагировать слишком медленно, чтобы приносить вообще ка­кую-либо пользу. Для правильной работы необходимо некоторое усреднение, однако правильный выбор значения постоянной времени является нетривиаль­ной задачей.

Известны различные алгоритмы борьбы с перегрузкой. Янг (Yang) и Редди (Reddy) (1995) даже разработали специальный метод классификации этих алго­ритмов. Они начали с того, что разделили все методы на алгоритмы с обратной Связью и без нее, как уже описывалось ранее. Затем они разделили алгоритмы без обратной связи на работающие у отправителя и у получателя. Алгоритмы с обратной связью также были разделены на две подкатегории: с явной и неявной обратной связью. В алгоритмах с явной обратной связью от точки возникнове­ния перегрузки в обратном направлении посылаются пакеты, предупреждающие о заторе. В алгоритмах с неявной обратной связью источник приходит к выводу о наличии перегрузки, основываясь на локальных наблюдениях, — например, по значению интервала времени, требующегося для получения подтверждения.

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

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

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

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

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

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

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