программный

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

1.   Как называется эта страница?

2.    Где она расположена?

3.    Как получить к ней доступ?

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

В результате было принято решение идентифицировать страницы способом, решающим сразу все три проблемы. Каждой странице назначается унифициро­ванный указатель информационного ресурса (URL, Uniform Resource Locator), который служит уникальным именем страницы. URL состоят из трех частей: про­токола (также называемого схемой), DNS-имени машины, на которой располо­жена страница, и локального имени, единственным образом идентифицирующе­го страницу в пределах этой машины (обычно это просто имя файла). Например, веб-сайт факультета, на котором работает автор, содержит несколько видеофраг­ментов об университете и городе Амстердаме. Унифицированный указатель страницы с видео выглядит следующим образом: http://www.cs.vu.nl/video/index-en.html

Этот URL состоит из трех частей: протокола (http), DNS-имени хоста (www.cs.vu.nl) и имени файла (video/index-en.html). Отдельные части URL-указа­теля разделяются специальными знаками пунктуации. Имя файла представляет собой относительный путь по отношению к веб-катологу cs.vu.vu.nl.

У сайтов могут быть сокращенные имена для ускоренного доступа к опреде­ленным файлам. Скажем, при отсутствии в URL имени файла может выводиться главная (домашняя) страница сайта. Если имя файла заканчивается именем ка­талога, то из него по умолчанию выбирается файл с именем index.html. Наконец, имя -user/ может соответствовать WWW-каталогу пользователя, причем может быть также задано имя файла по умолчанию, например, index.html. Так, на до­машнюю страницу автора можно попасть по адресу

http://www.cs.vu.nl/~ast/ несмотря на то, что действительное имя файла (index.html) отличается от указан­ного.

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

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

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

Таблица 7.9. Некоторые распространенные URL-указатели Имя Применение Пример http Гипертекст (HTML) http://www.cs.vu.nl/~ast/ ftp FTP ftp://ftp.cs.vu.nl/pub/minix/README file Локальный файл file:////usr/suzanne/prog.c news Телеконференция news:comp.os.minix news Статья новостей news:AA0134223112@cs.utah.edu gopher Gopher gopher://gopher.tc.umn.edU/11/Libraries mailto Отправка электронной почты mailto:JohnUser@acm.org telnet Удаленный терминал telnet://www.w3.org:80

Кратко рассмотрим этот список. Протокол http является родным языком Все­мирной паутины, на нем разговаривают веб-серверы. HTTP — это сокращение, которое расшифровывается как HyperText Transfer Protocol (протокол передачи гипертекста). Более подробно мы рассмотрим его далее в этой главе.

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

К локальному файлу также можно обратиться как к веб-странице, либо ис­пользуя протокол file, либо просто указав имя файла. Такой подход напоминает FTP, но не требует наличия сервера. Разумеется, он работает только с локальны­ми файлами, а не с расположенными на удаленных терминалах.

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

Для протокола news поддерживается два формата URL-указателей. Первый формат указывает телеконференцию, и с его помощью можно получить список новых статей с указанного заранее сайта новостей. Второй формат позволяет по­лучить конкретную статью по ее идентификатору, например, AA0134223112@cs. utah.edu. Для получения этой статьи с заранее настроенного сайта браузер ис­пользует протокол NNTP (Network News Transfer Protocol — сетевой протокол передачи новостей). Мы изучим NNTP в этой книге, однако надо понимать, что это нечто вроде SMTP, они весьма похожи даже по стилю.

Протокол gopher используется системой Gopher, разработанной в универси­тете штата Миннесота и получившей свое название от университетской спортив­ной команды «Golden Gophers» («Золотые суслики»). (Гоферами называют уро­женцев штатов Миннесота, Арканзас и Флорида. Кроме того, на американском сленге это слово означает «добывать», «копать», «искать».) Система Gopher поя­вилась в Интернете на несколько лет раньше Всемирной паутины. Концепту­ально они похожи: и та, и другая представляют собой схему поиска и получения информации, хранящейся на различных серверах, однако система Gopher под­держивала только тексты и не поддерживала изображений. Сейчас ее можно счи­тать полностью устаревшей, используется она крайне редко.

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

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

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

Несмотря на все перечисленные достоинства, все продолжающийся рост по­пулярности Всемирной паутины выявил один врожденный недостаток URL-схе­мы. URL указывает на определенный хост. Часто запрашиваемые по сети стра­ницы было бы лучше дублировать и хранить копии в удаленных концах сети, чтобы снизить сетевой трафик. Беда в том, что URL-указатели не предоставляют возможности для ссылки на страницу без указания ее точного адреса. Нельзя сказать: «Мне нужна страница abc, и мне все равно, где вы ее раздобудете». Для решения задачи репликации страниц проблемная группа проектирования Ин­тернета IETF (Internet Engineering Task Force) работает над системой URN (Uniform Resource Name — универсальное имя ресурса). Универсальное имя ре­сурса URN можно считать обобщенным URL-указателем. В настоящее время этот вопрос находится в стадии исследования, хотя уже предложен синтаксис, опи­санный в RFC 2141.

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

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

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

С другой стороны, если рассматривать видео по заказу скорее как обычное те­левидение с заранее составленным расписанием, тогда возможен другой подход, при котором популярный фильм передается сразу по нескольким каналам с ин­тервалом в 10 минут. Пользователь, желающий посмотреть этот фильм, должен подождать начала фильма несколько минут. Хотя при такой реализации приос­тановка и возобновление просмотра невозможны, пользователь, вернувшийся к телевизору после короткого перерыва, может переключиться на один из сосед­них каналов и найти тот же фильм, но идущий с отставанием на 10 или 20 ми­нут. Такую схему называют «почти видео по заказу». Ее реализация обходится значительно дешевле, так как хотя для передачи одного фильма и используется полтора десятка параллельных каналов, но предполагается, что этот фильм од­новременно смотрят тысячи зрителей. Различие между видео по заказу и этой схемой примерно такое же, как между личным и общественным транспортом.

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

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

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

Видеосерверы

Для предоставления видео по заказу необходимы специализированные видеосер­веры, способные хранить и передавать одновременно большое количество филь­мов. Общее число когда-либо снятых фильмов было оценено в 65 ООО (Minoli, 1995). В сжатом с помощью алгоритма MPEG-2 виде обычный фильм занимает около 4 Гбайт, таким образом, для хранения 65 ООО фильмов потребуется около 260 Тбайт. Добавьте к этому все когда-либо сделанные старые телевизионные программы, спортивные передачи, новости, рекламу и т. д., и станет ясно, что мы имеем дело с проблемой хранения данных в промышленных масштабах.

Дешевле всего хранить большие объемы информации на магнитной ленте. Так было раньше, возможно, так будет и в дальнейшем. На кассету типа Ultrium мож­но записать 200 Гбайт (50 фильмов) по цене около $1-2 за фильм. Уже сейчас можно приобрести большие механические кассетные серверы, хранящие тысячи кассет, снабженные автоматическими манипуляторами, способными менять кас­сеты в магнитофоне. Основными проблемами таких систем остаются время доступа (особенно к 50-му фильму на кассете), скорость передачи и ограничен­ное количество магнитофонов (для одновременного показа п фильмов нужно п магнитофонов).

К счастью, опыт работы с пунктами видеопроката, библиотеками и другими подобными организациями показывает, что не все фильмы (книги) одинаково популярны. Экспериментально доказано, что если в пункте проката есть N филь­мов, то доля заявок на конкретный фильм, стоящий на k-м месте в списке попу­лярности, примерно равна C/k. Здесь С — это число, дополняющее сумму долей до 1, а именно:

С = 1/(1 + 1/2 + 1/3 + 1/4 + 1/5 + ... + 1/N).

Таким образом, например, самый популярный фильм берут примерно в семь раз чаще, чем седьмой в списке популярности. Такая зависимость называется за­коном Ципфа (Zipf, 1949).

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

Фильмы можно хранить и на компакт-дисках. Современные диски DVD по­зволяют хранить 4,7 Гбайт данных, чего вполне достаточно для записи одного филь­ма, однако следующее поколение дисков будет иметь примерно удвоенную ем­кость. Хотя по сравнению с жесткими магнитными дисками время поиска на оп­тическом диске на порядок выше (50 мс вместо 5 мс), их низкая цена и высокая надежность делает автомат с тысячами сменных DVD хорошей альтернативой магнитной ленте для более часто используемых фильмов.

На следующем уровне в этой иерархии находятся жесткие магнитные диски. Они обладают малым временем доступа (5 мс), высокой скоростью передачи (320 Мбайт/с для SCSI 320) и значительной емкостью (свыше 100 Гбайт), что делает их вполне подходящими для хранения фильмов, которые действительно смотрят зрители (в отличие от тех, что хранятся на тот случай, если кто-либо за­хочет их посмотреть). Основной недостаток накопителей на жестких дисках за­ключается в их слишком высокой цене, чтобы хранить на них редко просматри­ваемые фильмы.

На вершине пирамиды, показанной на рис. 7.45, находится ОЗУ. Оператив­ная память является самым быстрым запоминающим устройством, но в то же время и самым дорогим. Оперативная память лучше всего подходит для хранения фильмов, посылаемых в данный момент различным получателям одновременно (например, настоящее видео по заказу 100 пользователям, начавшим просмотр в различное время). Когда цены на микросхемы памяти упадут до 50 долларов за гигабайт, 4 Гбайт ОЗУ, необходимые для хранения одного фильма, будут стоить 200 долларов, а 100 фильмов, находящихся в памяти, потребуют ОЗУ на 20 000 долларов (400 Гбайт). То есть видеосервер, имеющий в наличии 100 фильмов, скоро сможет позволить себе хранить их все в ОЗУ. А если у видеосервера всего 100 клиентов, которые день за днем смотрят одни и те же 20 фильмов, это уже не только реальное, но и выгодное решение.

Поскольку видеосервер представляет собой в действительности просто ог­ромное устройство ввода-вывода, работающее в режиме реального времени, его аппаратная и программная архитектура должна отличаться от используемой в PC или рабочей станции UNIX. Аппаратная архитектура типичного видеосерве­ра показана на рис. 7.46. Сервер состоит из одного или нескольких высокопроиз­водительных процессоров, у каждого из которых есть своя локальная память, па­мять общего доступа, большой кэш ОЗУ для хранения популярных фильмов, множества различных накопителей для хранения фильмов, а также сетевое обо­рудование, например, оптического интерфейса с магистралью SONET или ATM с каналом ОС-12 или выше. Все эти подсистемы соединены сверхскоростной ши­ной (по меньшей мере 1 Гбайт/с).

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

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

магнитных лент             оптических дисков                  диски RAID Рис. 7.46. Аппаратная архитектура типичного видеосервера

В основе второго типа интерфейса лежит модель видеомагнитофона. Сервер получает команды открытия, начала или приостановки воспроизведения, а также команды быстрой перемотки в обе стороны. Основное отличие этого интерфейса от модели UNIX состоит в том, что, получив команду PLAY (воспроизведение), сервер начинает выдавать данные с постоянной скоростью без необходимости передачи новых команд.

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

Возможны два способа организации дискового хранения: дисковая ферма и дисковый массив. Дисковая ферма подразумевает хранение на каждом диске нескольких фильмов целиком. Каждый фильм должен дублироваться на двух или даже более дисках, чтобы обеспечить высокую надежность и производитель­ность. Дисковый массив, или набор RAID (Redundant Array of Independent Disks — матрица независимых дисковых накопителей с избыточностью), являет­ся формой организации хранения, в которой фильм хранится сразу на несколь­ких дисках, например, блок 0 на диске 0, блок 1 на диске 1 и так далее цикличе­ски. Такая организация хранения называется разбиением на полосы.

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

Другая задача дискового программного обеспечения состоит в обслуживании выходных потоков реального времени и удовлетворении соответствующих времен­ных требований. Еще несколько лет назад это было связано с необходимостью реализации сложных алгоритмов планирования, однако по мере снижения цен на модули памяти стал возможен более простой подход. Для передачи каждого видеопотока необходимо хранить в буфере ОЗУ отрезок фильма длиной, ска­жем, 10 с (5 Мбайт). Буфер заполняется путем выполнения дисковой операции и освобождается сетевым процессом. Имея 500 Мбайт оперативной памяти, мы сможем одновременно буферизировать 100 потоков. Конечно, дисковая подсис­тема должна обладать устойчивой скоростью передачи данных 50 Мбайт/с для нормального заполнения буферов, однако матрица RAID, составленная из высо­копроизводительных дисков типа SCSI, запросто может справиться с этой задачей.

Распределительная сеть

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

Основным требованием, предъявляемым к магистрали, является высокая про­пускная способность. Раньше вторым требованием был низкий уровень флук­туации (джиттера), то есть неравномерности трафика, однако теперь, когда даже самые дешевые ПК получили возможность буферизировать 10 с высококачест­венного видео в формате MPEG-2, это требование перестало быть актуальным.

Локальное распределение представляет собой чрезвычайно неупорядоченное, хаотическое явление — это связано с тем, что различные компании пытаются предоставлять услуги в различных регионах по различным сетям. Телефонные компании, компании кабельного телевидения, а также совершенно новые орга­низации пытаются первыми застолбить участок. В результате наблюдается бы­строе распространение новых технологий. В Японии некоторые компании, зани­мающиеся канализационными трубами, утверждают, что именно они обладают преимуществом, так как принадлежащие им трубы большого диаметра подведе­ны в каждый дом (через них действительно прокладывается оптоволоконный ка­бель, однако нужно очень аккуратно следить за местами его вывода из труб). В настоящее время уже используется множество схем локального распределения видео по заказу, из которых четырьмя основными являются ADSL, FTTC, FTTH и HFC. Мы рассмотрим их все по очереди.

Система ADSL (Asymmetric Digital Subscriber Line — асимметричная цифро­вая абонентская линия) была первой попыткой телефонных компаний поучаст­вовать в деле локального распределения. Мы изучали ADSL в главе 2 и сейчас не будем повторять этот материал. Идея состояла в том, что практически каж­дый дом в США, Европе и Японии уже оснащен медными витыми парами (для аналоговой телефонной связи). Если бы эти провода можно было использовать для видео по заказу, то телефонные компании могли бы сорвать большой куш.

Проблема заключалась в том, что по этим проводам невозможно передать на их обычную длину в 10 км даже поток данных MPEG-1, не говоря уже о MPEG-2. Для передачи полноцветного видео с плавными движениями и высоким разре­шением необходима скорость 4-8 Мбит/с в зависимости от требуемого качества. Таких скоростей с помощью ADSL достичь невозможно (вернее, возможно, но только при передаче на очень малые расстояния).

Второй вариант распределительной сети был также разработан телефонными компаниями. Он получил название FTTC (Fiber То The Curb — оптоволоконный кабель к распределительной коробке). В данной модели телефонная компания прокладывает оптический кабель от каждой конечной телефонной станции до устройства, расположенного по соседству с абонентами и называющегося бло­ком ONU (Optical Network Unit — блок оптической сети). К блоку ONU может быть подключено около 16 медных витых пар. Поскольку эти витые пары корот­кие, по ним можно передавать дуплексные потоки Т1 или Т2 и, соответственно, фильмы в форматах MPEG-1 или MPEG-2. Более того, благодаря симметрично­сти схемы, FTTC может поддерживать видеоконференции.

Третье решение, предложенное телефонными компаниями, состоит в проклад­ке оптоволоконного кабеля в каждый дом. Эта схема называется FTTH (Fiber То The Home — оптоволоконный кабель к дому). При этом каждый абонент полу­чит возможность пользоваться каналом связи ОС-1, ОС-3 или даже выше. Такое решение очень дорого и вряд ли получит широкое распространение в ближай­шие годы, но очевидно, что возможности этого варианта практически безгранич­ны. На рис. 7.31 мы видели схему, используя которую, каждый желающий может содержать собственную радиостанцию. А как вам идея о том, чтобы каждый член семьи был главой собственной телестудии? Все перечисленные системы— ADSL, FTTC и FTTH— представляют собой локальные распределительные сети с топо­логией «точка—точка», что неудивительно, учитывая то, как создавалась совре­менная телефонная система.

Полностью противоположный подход реализуется в настоящее время постав­щиками кабельного телевидения. Он называется HFC (Hybrid Fiber Coax — гиб­рид оптоволоконного и коаксиального кабелей) и показан на рис. 2.41, а. Суть подхода в следующем. Современные коаксиальные кабели с полосой пропуска­ния от 300 до 450 МГц будут заменены кабелями с полосой в 750 МГц, что повы­сит их пропускную способность с 50-75 каналов шириной в 6 МГц до 125 таких каналов. 75 из 125 каналов по-прежнему будут использоваться для передачи ана­логового телевизионного сигнала.

В 50 новых каналах будет использоваться квадратурная амплитудная моду­ляция QAM-256, в результате чего по каждому каналу можно будет передавать данные со скоростью около 40 Мбит/с, что в сумме составит 2 Гбит/с. Каждым кабелем предполагается охватить около 500 домов, Таким образом, каждому дому может быть предоставлен выделенный канал с пропускной способностью 4 Мбит/с, который можно будет использовать для передачи MPEG-2.

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

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

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

На локальные серверы можно заранее копировать фильмы. Если пользовате­ли отошлют заявки на фильмы, которые они хотели бы просмотреть, заранее, та­кие фильмы могут копироваться на локальные серверы в периоды минимальной загрузки линий. Можно ввести гибкие тарифы на заблаговременные заказы филь­мов по аналогии с бронированием авиабилетов. Так, например, можно давать 27-процентную скидку при заблаговременном заказе фильмов (от 24 до 72 ча­сов) для просмотра во вторник или в четверг до 18:00 или после 23:00. Фильмы, заказанные в первое воскресенье месяца до 8:00 для просмотра в среду после по­лудня в день, дата которого является простым числом, получают 43-процентную скидку, и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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