запись

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

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

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

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

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

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

Допустим, Труди может взломать систему DNS (например, ту ее часть, которая хранится в кэше DNS у провайдера Алисы) и заменить IP-адрес Боба (например, 36.1.2.3) своим IP-адресом (например, 42.9.9.9). Тогда можно провести атаку. То, как все должно работать в нормальной ситуации, показано на рис. 8.42, а: 1) Али­са запрашивает у службы DNS IP-адрес Боба; 2) получает его; 3) она запрашивает домашнюю страничку Боба; 4) получает ее. После того как Труди заменяет IP-ад­рес Боба на свой собственный, мы получаем ситуацию, показанную на рис. 8.42, б. Алиса ищет IP-адрес Боба, а получает вместо него IP-адрес злоумышленницы Труди, поэтому весь трафик Алисы, предназначенный для Боба, приходит, на са­мом деле, Труди. Та может организовать атаку типа «человек посередине», не му­чаясь с установкой «крокодилов» на телефонной линии Алисы. Вместо этого она может заменить всего одну запись на сервере имен DNS. Это, согласитесь, более просто.

Рис. 8.42. Нормальная ситуация (а); атака со взломом DNS и изменением записи,

относящейся к Бобу (б)

Как Труди удалось обмануть DNS? А это оказалось не таким уж сложным де­лом. Если не вдаваться в подробности, можно описать процесс так: Труди обман­ным путем заставляет DNS-сервер провайдера Алисы послать запрос для поиска адреса Боба. К несчастью, так как DNS использует UDP, сервер не может узнать, кто является реальным отправителем ответа. Труди использует это свойство, фальсифицируя ожидаемый ответ и тем самым занося неверные сведения об IP- адресе Боба в кэш DNS-сервера. Для простоты мы будем предполагать, что про­вайдер Алисы изначально не имеет сведений о веб-сайте Боба, bob.com. Если же такие сведения есть, злоумышленник может выждать, пока срок действия записи истечет, и попробовать еще раз (либо применить другие хитрости).

Труди начинает свою атаку с того, что посылает провайдеру Алисы запрос на поиск IP-адреса bob.com. Так как соответствующая запись отсутствует, сервер, в свою очередь, опрашивает сервер домена верхнего уровня (.com). Но Труди опе­режает этот сервер и посылает ложный ответ, в котором сообщается, что IP-ад­рес bob.com якобы 42.9.9.9. Как мы знаем, в реальности это адрес Труди. Так как этот ответ приходит первым, данные из него заносятся в кэш сервера провайде­ра, а настоящий ответ, если он приходит позже, отвергается. Установка ложного IP-адреса называется обманом DNS. А кэш, в котором хранится заведомо лож­ный IP-адрес, называется отравленным кэшем.

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

Во-вторых, для того чтобы DNS-сервер мог понять, какому запросу соответ­ствует ответ, во все запросы добавляются порядковые номера. Чтобы обмануть
провайдера Алисы, Труди должна знать текущий порядковый номер. Самый простой способ узнать его — это зарегистрировать собственный домен, напри­мер, trudy-the-intruder.com.

Предположим, что IP-адрес этого домена также 42.9.9.9. Труди создает DNS- сервер для этого домена: dns.trudy-the-intruder.com. Его IP-адрес тот же самый (42.9.9.9), поскольку оба домена расположены на одном и том же компьютере. Теперь надо заставить провайдера Алисы поинтересоваться DNS-сервером Тру­ди. Сделать это несложно. Требуется лишь запросить, например, foobar.trudy-the- intruder.com, и серверу провайдера Алисы придется опросить сервер верхнего уровня, .com, и узнать у него, кто обслуживает новый домен Труди.

И вот теперь, когда запись dns.trudy-the-intruder.com занесена в кэш провайде­ра, можно спокойно начинать атаку. Труди запрашивает у провайдера Алисы www.trudy-the-intruder.com, а тот в ответ посылает на DNS-сервер Труди соответ­ствующий запрос. Вот в этом-то запросе и содержится нужный злоумышленнице порядковый номер. Теперь Труди должна действовать без промедления: она ищет с помощью провайдера Алисы Боба и тут же отвечает на собственный вопрос, посылая фальшивку: «Адрес bob.com: 42.9.9.9». Этот подделанный ответ несет в себе порядковый номер на единицу больше только что полученного. За время атаки она может послать еще одну фальшивку, с номером, на два больше полу­ченного, а также еще около дюжины таких «ответов» с увеличивающимися но­мерами. Задача одного из них нам уже ясна. Остальные никому не нужны, их просто выкинут. После прибытия фальшивого ответа на запрос Алисы он будет помещен в кэш; к тому времени, когда доберется настоящий ответ, он будет от­вергнут, так как сервер уже ничего не ожидает.

И вот Алиса ищет IP-адрес bob.com и узнает, что он равен 42.9.9.9. Как мы знаем, это адрес Труди, которая провела успешную атаку типа «человек посере­дине», не выходя из своей комнаты. Последовательность предпринятых ею ша­гов показана на рис. 8.43. К сожалению, это еще и не единственный способ обма­нуть DNS. Этих способов действительно много.

К сожалению, такое решение создает новую проблему: как пользователю забрать свою почту у агента передачи сообщений провайдера? Ответ таков: следует соз­дать специальный протокол, который позволил бы пользовательскому агенту (на машине клиента) соединиться с агентом передачи сообщений провайдера (на ма­шине провайдера) и скопировать хранящуюся для него почту. Одним из таких протоколов является РОРЗ (Post Office Protocol v. 3 — почтовый протокол, 3-я версия), определенный в документе RFC 1939.

Ситуация, при которой доставка осуществляется в условиях постоянного со­единения с Интернетом отправителя и получателя, показана на рис. 7.5, а. Ил­люстрация ситуации, в которой отправитель находится в текущий момент на ли­нии, а приемник — нет, приведена на рис. 7.5, б.

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

1. Авторизация.

2.    Транзакции.

3.    Обновление.

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

Можно посмотреть, как все это происходит, набрав команду вида

telnet mail.isp.com 110,

где mail.isp.com следует заменить на DNS-имя почтового сервера провайдера. Telnet устанавливает TCP-соединение с портом 110, прослушиваемым РОРЗ-сервером. После установки TCP-соединения сервер посылает ASCII-сообщение, объявляя о своем присутствии. Обычно оно начинается с +0К, затем следует комментарий. Возможный сценарий после установки TCP-соединения показан в листинге 7.4. Как и раньше, строки, начинающиеся с С:. говорят о том, что данная команда ис­ходит от клиента (пользователя), а начинающиеся с S: — что это сообщения сер­вера (агента передачи сообщений на машине провайдера).

Листинг 7.4. Получение трех сообщений по протоколу РОРЗ

S: +0К РОРЗ-сервер готов

С: USER carolyn

S: +0К

С: PASS vegetables

S: OK вход в систему произведен

С: LIST

S: 1 2505

S: 2 14302

S: 3 8122

S: .

C: RETR 1

S: (отправляет сообщение 1)

С: DELE 1

С: RETR 2

S: (отправляет сообщение 2)

С: DELE 2

С: RETR 3

S: (отправляет сообщение 3)

С: DELE 3

С: QUIT

S: +0К Конец соединения с РОРЗ-сервером

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

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

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

Теперь подведем небольшие итоги того, как происходит работа с электронной почтой клиентов провайдера. Элинор создает сообщение для Кэролайн с помо­щью редактора электронной почты (то есть пользовательского агента) и щелкает на значке, чтобы отослать его. Программа передает письмо агенту передачи сообще­ний на хосте Элинор. Агент передачи сообщений видит, что письмо адресова­но carolyn@xyz.com, и использует DNS для поиска записи MX для xyz.com (где xyz.com — провайдер Кэролайн). В ответ на запрос возвращается DNS-имя поч­тового сервера xyz.com. Агент передачи сообщений после этого снова обращается к DNS (например, используя gethostbyname): на этот раз ему нужно найти IP-ад­рес этой машины. Затем с помощью порта 25 найденной машины устанавливает­ся TCP-соединение с SMTP-сервером. Передавая команды SMTP, аналогичные показанным в листинге 7.3, агент пересылает сообщение в почтовый ящик для Кэролайн и разрывает ТСР-соединение.

Через некоторое время Кэролайн загружает свой компьютер, соединяется с провайдером и запускает программу электронной почты. Та устанавливает ТСР- соединение через порт 110 РОРЗ-сервера, работающего на машине провайдера. Имя DNS или IP-адрес этой машины обычно указывается при установке про­граммы электронной почты либо его получают у провайдера. После установки TCP-соединения почтовая программа Кэролайн запускает протокол РОРЗ для копирования содержимого почтового ящика на локальный жесткий диск. При этом происходит обмен командами, аналогичными показанным в листинге 7.4. По окончании передачи электронной почты ТСР-соединение разрывается. На самом деле в тот же момент можно разорвать и соединение с провайдером, по­скольку вся почта уже находится на жестком диске у Кэролайн. Конечно, чтобы отправить ответ на письма, Кэролайн придется снова соединяться с провайде­ром, поэтому не всегда пользователи разрывают соединение сразу после загруз­ки почты.

IMAP

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

Это неудобство привело к созданию альтернативного протокола доставки со­общений, IMAP (Interactive Mail Access Protocol — протокол интерактивного доступа к электронной почте), определенного в RFC 2060. В отличие от протоко­ла РОРЗ, который подразумевает, что пользователь будет очищать почтовый ящик после каждого контакта с провайдером и будет работать с почтой в отклю­ченном режиме, протокол IMAP предполагает, что вся почта будет оставаться в почтовых ящиках на сервере неограниченно долго. IMAP обладает широким на­бором механизмов для чтения сообщений или даже частей сообщений. Такое свой­ство полезно при использовании медленных модемов, поскольку можно про­честь только текстовую часть письма, к которому приложены большие видео- и аудиофрагменты. Поскольку основное предположение состоит в том, что пользо­ватель не будет копировать на свой компьютер письма, в IMAP входят также ин­струменты для создания, удаления и других видов управления почтовыми ящика­ми, размещающимися на сервере. Таким образом, пользователь может завести собственный почтовый ящик для каждого лица, с которым ведется переписка, и переносить сообщения из почтового ящика для всех входящих писем в эти пер­сональные ящики.

Протокол IMAP обладает разнообразными возможностями, например, способ­ностью упорядочивать почту не по порядку ее поступления, как показано в табл. 7.3, а по атрибутам писем (например, «сначала дайте мне письмо от Бобби»), В отли­чие от РОРЗ, IMAP может заниматься как доставкой исходящей почты от поль­зователя в направлении места назначения, так и доставлять входящую почту пользователя.

В целом стиль протокола IMAP подобен РОРЗ, пример работы которого по­казан в листинге 7.4. Различаются они количеством команд — в IMAP их десят­ки. Сервер IMAP прослушивает порт 143. Сравнение протоколов РОРЗ и IMAP приведено в табл. 7.8. Следует заметить, что не все провайдеры и не все програм­мы работы с электронной почтой поддерживают оба протокола. Поэтому, выби­рая программу и провайдера, следует выяснить, могут ли они работать хоть с од­ним из этих протоколов, и если да, то с какими именно протоколами.

Таблица 7.8. Сравнение протоколов РОРЗ и IMAP Свойство РОРЗ   IMAP

Где определен                                    RFC 1939                                  RFC 2060

Используемый порт TCP                  110                                             143

Место хранения почты                      ПК пользователя                      Сервер

Способ чтения почты                         В автономном режиме            В подключенном режиме

Требуемое время нахождения         Небольшое                               Большое на линии

Конфиденциальность и цензура — это те области, в которых сталкиваются техно­логические аспекты и общественные интересы. Третьей такой областью является защита авторских прав. Авторское право гарантирует свободу распоряжения ин­теллектуальной собственностью ее создателям, которыми могут быть, напри­мер, писатели, художники, композиторы, музыканты, фотографы, кинорежиссе­ры, хореографы и т. д. Авторское право выдается на определенный срок, который обычно равен сроку жизни автора плюс 50 лет (75 лет — в случае корпоративного авторского права). По окончании этого срока интеллектуальная собственность становится достоянием общества, и каждый волен распоряжаться ею, как хочет. Так, например, проект «Gutenberg» (www.promo.net/pg) разместил в Сети тысячи произведений, давно уже ставших общественным достоянием (работы Шекспи­ра, Диккенса, Марка Твена). По просьбе Голливуда в 1998 году Конгресс США разрешил продлить срок действия авторских прав еще на 20 лет, утверждая, что без принятия этой меры больше никто ничего не станет создавать. В то же время, патенты на изобретения действуют в течение всего лишь 20 лет, и никто не жалу­ется — люди продолжают совершать открытия и делать изобретения.

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

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

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

Однако есть еще одна проблема, связанная с авторскими правами. Ведется ожесточенная борьба между Голливудом и компьютерной индустрией. Голливуд требует усилить защиту интеллектуальной собственности, а компьютерщики го­ворят, что они не обязаны сторожить голливудские ценности. В октябре 1998 года Конгресс принял Акт об авторских правах в цифровых технологиях (DCMA — Digital Millenium Copyright Act), в котором говорится о том, что взлом меха­низма защиты, присутствующего в работе, защищенной законом об авторских правах, а также сообщение другим технологии взлома является преступлением. Аналогичный законодательный акт был принят и в Евросоюзе. С одной стороны, все как-то забыли подумать о том, что для пиратов с Дальнего Востока такие ак­ты указом не являются, а с другой стороны, многие считают, что новый закон на­рушил баланс между интересами владельцев авторских прав и общественными интересами.

Взять хотя бы такой пример. В сентябре 2000 года консорциум, связанный с му­зыкальной индустрией, озабоченный созданием надежной онлайновой системы продажи аудиозаписей, организовал конкурс, пригласив всех желающих попро­бовать взломать систему (это действительно очень важный этап, необходимый при создании любой новой системы защиты). Группа ученых из различных уни­верситетов под руководством профессора Эдварда Фельтена (Edward Felten) из Принстона, специализирующихся в области защиты информации, приняли вы­зов и сломали систему. Затем была написана статья, описывающая выводы, еде- данные в ходе исследования. Она была направлена на конференцию USENIX, посвященную проблемам защиты информации. Доклад был рассмотрен и при­нят на соответствующем уровне. Однако незадолго до конференции Фельтен по­лучил уведомление от Ассоциации звукозаписи о том, что эта организация в слу­чае опубликования статьи подаст на авторов в суд за нарушение акта DCMA.

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

С обсуждаемой темой тесно связана доктрина законного использования, ставшая результатом судебных решений во многих странах. Эта доктрина состо­ит в том, что покупатели продукции, защищенной законом об авторских правах, имеют сильно ограниченные права на копирование этой продукции, включая да­же использование ее частей для научных целей (например, в качестве обучающе­го материала в школах и колледжах) и создание архивных резервных копий на тот случай, если что-нибудь случится с исходным носителем. Как проверить, является ли использование продукции законным? Показатели таковы: 1) ком­мерческое использование; 2) количество процентов скопированных данных; 3) вли­яние копирования на объем продаж. Так как DMCA и аналогичные законы, приня­тые Евросоюзом, запрещают взлом систем защиты от копирования, такие законы заодно запрещают легальное добросовестное использование. По сути, DMCA отбирает у потребителей историческое право активно поддерживать продавцов, у которых они приобрели продукцию. Провал этой идеи неизбежен.

Еще одно явление, затмевающее собой по уровню смещения баланса между обладателями авторских прав и потребителями даже DMCA, — это Альянс надеж­ных вычислительных платформ (ТСРА — Trusted Computing Platform Alliance). Разрабатывается этот проект совместными усилиями Intel и Microsoft. Идея со­стоит в том, чтобы процессор и операционная система зорко наблюдали за дей­ствиями пользователя (например, за воспроизведением скопированной незакон­ным образом звукозаписи) и запрещали совершать нежелательные действия. Та­кая система могла бы даже позволить обладателям авторских прав удаленно манипулировать персональными компьютерами пользователей, изменяя при не­обходимости определенные правила. Несомненно, общественный резонанс будет огромен. Конечно, это очень здорово, что индустрия наконец обратила внимание на проблемы защиты информации, однако нельзя не заметить с прискорбием, что большинство усилий направлено на усиление законов об авторских правах, а не на борьбу с вирусами, взломщиками, мошенниками и другими проблемами, волнующими большинство пользователей.

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

Шифры, основанные на методе подстановки, сохраняют порядок символов, но подменяют их. Шифры, использующие метод перестановки, меняют порядок следования символов, но не изменяют сами символы. На рис. 8.2 показан простой перестановочный шифр с колоночной перестановкой. Ключом к шифру служит слово или фраза, не содержащая повторяющихся букв. В данном примере в каче­стве ключа используется слово MEGABUCK. Цель ключа — пронумеровать ко­лонки. Первой колонкой становится колонка под буквой, расположенной ближе всего к началу алфавита, и т. д. Открытый текст записывается горизонтально в строках. Шифрованный текст читается по колонкам, начиная с колонки с млад­шей ключевой буквой.

м	Е	G	А	В	у	С	К
7	4	5	1	2	8	3	6
Р	1	е	а	s	е	t	г
а	п	s	f	е	г	0	п
е	m	1	1	1	i	о	п
d	о	1	1	а	г	S	t
0	m	У	s	w	i	S	S
b	а	п	к	а	с	с	О
u	п	t	s	i	X	t	W
О	t	W	о	а	b	с	d

Открытый текст

pleasetransferonemilliondollarsto myswissbankaccountsixtwotwo

Зашифрованный текст

AFLLSKSOSELAWAIATOOSSCTCLNMOMANT ESILYNTWRNNTSOWDPAEDOBUOERIRICXB

Рис. 8.2. Перестановочный шифр

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

Затем нужно угадать число колонок. Во многих случаях по контексту сооб­щения можно угадать слово или фразу. Например, предположим, что криптоана­литик подозревает, что где-то в сообщении должно встретиться словосочетание milliondollars. Обратите внимание, что в результате того, что эти слова присутст­вуют в исходном тексте, в шифрованном тексте встречаются биграммы МО, IL, LL, LA, IR и OS. Символ О следует за символом М (то есть они стоят рядом по вертикали в колонке 4), так как они разделены в предполагаемой фразе дистан­цией, равной длине ключа. Если бы использовался ключ длиной семь, тогда вме­сто перечисленных выше биграмм встречались бы следующие: MD, Ю, LL, LL, IA, OR и NS. Таким образом, для каждой длины ключа в шифрованном тексте об­разуется различный набор биграмм. Перебрав различные варианты, криптоана­литик часто довольно легко может определить длину ключа.

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

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

чисел 4, 12, 20, 28, 36, 44, 52, 60, 5, 13....... 62. Другими словами, четвертая входная

буква, а, первой появится на выходе, за ней последует двенадцатая, /, и т. д.

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

Для описания алгоритма воспользуемся рис. 5.18, на котором изображен про­цесс, запущенный на узле А, которому необходимо отправить пакет на узел I. Алго­ритм AODV на каждом узле ведет таблицу, доступ к которой осуществляется с помощью поля адреса. Таблица содержит информацию об адресате, в том числе адрес ближайшего соседа, которому необходимо переслать пакет, чтобы он мог достичь пункта назначения. Допустим, А просматривает эту таблицу и не нахо­дит записи для I. Значит, нужно найти маршрут, ведущий к этому узлу. Итак, ал­горитм начинает заниматься поисками маршрутов только тогда, когда они реаль­но требуются. Это и делает его алгоритмом «по требованию».

Для поиска I узел А генерирует специальный пакет запроса маршрута ROUTE REQUEST и распространяет его по сети широковещательным способом. На рис. 5.18, а показано, что этот пакет достигает узлов В и D. На самом деле, при­чиной установления именно узлами В и D соединения с А является то, что они могут получать пакеты от А. Например, F не соединен дугой с А, потому что он не может принимать радиосигнал от этого узла. То есть F не соединен с А.

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

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

Когда пакет запроса маршрута прибывает на узел (например, на узлы В и D), с ним происходит следующее:

1. Пара значений полей Адрес источника и Идентификатор запроса ищется в таблице локальной истории. С их помощью можно выяснить, приходил ли уже этот запрос и обрабатывался ли он. Если обнаруживается, что пакет яв­ляется дубликатом, он отвергается и его обработка прекращается. В против­ном случае указанная пара значений заносится в таблицу истории, чтобы в будущем можно было обнаружить дубликаты. Обработка запроса продолжа­ется.
2. Приемник ищет адрес назначения в таблице маршрутов. Если известен доста­точно свежий маршрут, отправителю посылается пакет наличия маршрута ROUTE REPLY, сообщающий ему о том, как можно достичь получателя (в двух словах: «Используй меня»). Что значит «свежий маршрут»? Имеется в виду, что поле Порядковый номер получателя в таблице маршрутизации имеет зна­чение большее или равное Порядковому номеру получателя из пакета запроса маршрута. Если оно меньше, значит, хранящийся в таблице маршрут явля­ется более старым, нежели предыдущий маршрут, имевшийся у отправителя к тому же пункту назначения. В этом случае выполняется пункт 3.
3. Поскольку у приемника отсутствует свежий маршрут к адресату, он инкре- ментирует поле Счетчик переходов и вновь широковещательным образом рас­пространяет пакет запроса маршрута. Из пакета извлекаются данные и сохраня­ются в виде новой записи в таблице обратных маршрутов. Эти данные будут использоваться для построения обратного пути, по которому впоследствии необходимо будет послать ответный пакет отправителю. Стрелки на рис. 5.18 как раз показывают процесс построения обратного пути. Для записи о только чтй созданном обратном пути запускается таймер. При наступлении тайм- аута запись удаляется.

Ни В, ни D не знают, где находится узел I, поэтому каждый из них создает об­ратный путь к А, как показано стрелками на рис. 5.18, и широковещательным способом распространяет пакет со Счетчиком переходов, установленным в еди­ницу. Этот пакет от В достигает С и D. Узел С делает запись в таблице обратных путей и, в свою очередь, тоже широковещательным способом распространяет па­кет далее. Что касается Д то он отвергает пакет: для него это дубликат. Разуме­ется, и В отвергает пакеты, полученные от D. Тем не менее, F и G принимают ши­роковещательное сообщение от D и сохраняют его, как показано на рис. 5.18, в. После того как Е, Н и I получают широковещательный пакет, запрос маршрута наконец достигает узла назначения (Г). Этот счастливый миг запечатлен на рис. 5.18, г. Обратите внимание: несмотря на то, что мы показали распростране­ние широковещательного пакета в виде трех стадий, на самом деле рассылка это­го пакета разными узлами никак не координируется.

В ответ на пришедший запрос узел I генерирует пакет наличия маршрута ROUTE REPLY, показанный на рис. 5.20. Поля Адрес отправителя, Адрес получателя и Счетчик переходов копируются из ROUTE REQUEST, а Порядковый номер получателя берется из собственного счетчика, хранящегося в памяти. Поле Счетчик перехо­дов устанавливается в 0. Поле Время существования используется для управле­ния реализуемостью маршрута. Данный пакет распространяется методом одно­адресной передачи на тот узел, с которого пришел запрос маршрута. В данном случае он уходит на узел G. Затем, в соответствии с установленным обратным путем, он попадет на D и наконец на А. При проходе каждого узла Счетчик пере­ходов инкрементируется, так что узел-отправитель может увидеть, насколько да­леко от него находится узел-получатель (7).

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

1. Не известен ни один маршрут.
2. Последовательный номер для I в пакете ROUTE REPLY больше, чем значение в таблице маршрутизации.
3. Последовательные номера равны, но новый путь короче.

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

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

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

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

Модель мира, обычно используемая разработчиками сетей, показана на рис. 5.16. Здесь мы видим глобальную сеть, состоящую из маршрутизаторов и хостов. С глобальной сетью соединены локальные и региональные сети и беспроводные соты, которые рассматривались в главе 2.

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

Предполагается, что у всех хостов есть постоянное домашнее местоположе­ние, которое никогда не меняется. Кроме того, у хостов есть постоянный домаш­ний адрес, которым можно воспользоваться для определения домашнего место­положения, аналогично тому, как телефонный номер 1-212-5551212 обозначает США (страна с кодом 1) и Манхэттен (212). Целью маршрутизации в системах с мобильными хостами является обеспечение возможности передачи пакетов мо­бильным пользователям с помощью их домашних адресов. При этом пакеты долж­ны эффективно достигать пользователей, независимо от их расположения. Са­мое сложное здесь, конечно, — найти пользователя.

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

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

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

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

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

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

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

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

Когда пакет посылается мобильному пользователю, он направляется в его до­машнюю локальную сеть на домашний адрес пользователя. На рис. 5,17 это дей­ствие показано как этап 1. Здесь отправитель из северо-западного города Сиэтла хочет отправить пакет хосту, который обычно находится по другую сторону США, в Нью-Йорке. Пакеты, посланные в домашнюю локальную сеть мобильного хос­та (Нью-Йорк), перехватываются внутренним агентом, который узнает новое (временное) расположение мобильной станции (например, Лос-Анджелес) и ад­рес внешнего агента локальной сети, в которой она в данный момент находится.

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

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

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

В-четвертых, схемы различаются способами переадресации пакетов. Один из способов заключается в изменении поля адреса получателя в пакете и передаче измененного пакета. Есть системы, в которых весь пакет, включая домашний ад­рес, может быть помещен внутрь другого пакета, посылаемого по временному ад­ресу. В любом случае, когда хост или маршрутизатор получает сообщение вида «Начиная с этого момента, пожалуйста, пересылайте мне всю почту, адресуемую Стефани», у него могут возникнуть вопросы — например, с кем он разговаривал, соглашаться или нет на данное предложение. Несколько протоколов мобильных хостов обсуждаются и сравниваются в (Нас and Guo, 2000; Perkins, 1998а; Snoe- ren and Balakrishnah, 2000; Solomon, 1998; Wang and Chen, 2001).

Поскольку узлы могут перемещаться и выключаться, топология сети может из­меняться совершенно спонтанно. Например, если на рис. 5.18 узел G выключит­ся, А не поймет, что путь к I (ADGI) больше не может быть реализован. Алгорит­му нужно как-то с этим бороться. Периодически все узлы рассылают сообщение приветствия Hello. Ожидается, что все узлы, будучи истинными джентльменами, ответят на него. Если ответ не приходит, значит, сосед вышел из зоны действия и больше не связан с данным узлом. Аналогичным образом, если он пытается по­слать пакет соседу, который не отвечает, он узнает, что связь с ним недоступна.

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

Рассмотрим наш предыдущий пример, предположив, что G внезапно вык­лючился. Образовавшаяся в результате этого события топология показана на рис. 5.21, б. Когда D обнаруживает, что G ушел из сети, он просматривает свою таблицу маршрутизации и видит, что G стоял на пути к Е, G и I. Объединением активных соседей для данных адресатов является множество {А, В}. Другими словами, А и В содержат записи о маршрутах, проходящих через G, поэтому их нужно проинформировать о том, что эти маршруты больше не работают. D сооб­щает им об этом, посылая специальные пакеты, заставляющие их обновить свои таблицы соответствующим образом. Сам узел D удаляет записи для адресатов Е, G и / из таблицы маршрутизации.

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

AODV, впрочем, может также заниматься широковещательной и групповой маршрутизацией. Детали см. в (Perkins and Royer, 2001). Маршрутизация в спе­циализированных сетях — чрезвычайно популярная сегодня область исследова­ний. Вопросам, связанным с ней, посвящено большое количество материалов. Например, (Chen и др., 2002; Ни and Johnson, 2001; Li и др., 2001; Raju and Garcia-Luna-Aceves, 2001; Ramanathan and Redi, 2002; Royer and Toh, 1999; Spohn and Garcia-Luna-Aceves, 2001; Tseng и др., 2001; Zadeh и др., 2002).

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

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

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

Рис. 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 после­довательных узлов, и круг при этом не разорвется.

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

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

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

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