start = k + 2г (mod 2m),
IP-адрес «преемника» = successor (start[г']).
Заметим, что каждый узел запоминает IP-адреса относительно маленького числа узлов и большинство из них достаточно близки в терминах идентификатора узла.
С использованием таблицы указателей поиск key в узле k происходит следующим образом. Если key попадает между k и successor (k), то узлом, содержащим информацию о key, является successor (k), и поиск завершен. В противном случае в таблице указателей производится поиск записи, в которой поле start — самый близкий предшественник key. Непосредственно на IP-адрес из этой записи отправляется запрос продолжить поиск. Это уже ближе к key, но все еще до него, и есть хороший шанс, что после небольшого количества дополнительных запросов ответ будет получен. Фактически так как каждый поиск вдвое уменьшает остающееся расстояние до цели, можно показать, что среднее число поисков составит
В качестве первого примера рассмотрим поиск key = 3 в узле 1. Так как узел 1 знает, что 3 лежит между ним и его преемником 4, искомый узел это 4, и поиск заканчивается возвращением IP-адреса узла 4.
В качестве второго примера рассмотрим поиск key = 16 в узле 1. Так как 16 не лежит между 1 и 4, происходит обращение к таблице указателей. Самый близкий
предшественник — 16 это 9, так что запрос переслан по IP-адресу 9-й записи, а именно в узел 12. Узел 12 также не знает ответа непосредственно, поэтому он ищет узел ближе всего предшествующий 16, и находит 14, который приводит IP-адрес узла 15. Запрос посылается туда. Узел 15 видит, что 16 лежит между ним и его преемником (20), и прокладывает путь обратно к узлу 1, возвращая IP-адрес 20.
Так как узлы все время присоединяются и отключаются, Chord должен иметь возможность управлять этими действиями. Мы предполагаем, что когда система начала функционировать, количество узлов было достаточно маленьким, и чтобы построить первый круг и таблицы указателей, они могли обмениваться информацией непосредственно. После этого нужна автоматизированная процедура. Когда новый узел r хочет присоединиться, он должен контактировать с каким-то существующим узлом и попросить его найти IP-адрес successor (r). Затем новый узел спрашивает successor (r) о его предшественнике. После этого новый узел просит их обоих вставить r в круг между ними. Например, если на рис. 7.43 хочет присоединиться 24, он просит любой узел найти successor (24), которым является 27. Затем он спрашивает 27 о его предшественнике (20). После этого сообщает им обоим о своем существовании, 20 начинает использовать 24 в качестве преемника, а 27 начинает использовать 24 в качестве предшественника. Кроме того, узел 27 передает ключи в диапазоне 21-24, который теперь принадлежит 24. Теперь 24 полностью вставлен.
Однако теперь многие таблицы указателей содержан неверную информацию. Чтобы исправить их, каждый узел поддерживает фоновый процесс, который периодически повторно вычисляет каждый указатель, запрашивая successor. Когда один из этих запросов указывает на новый узел, соответствующая запись указателя обновляется. Когда узел отключается корректно, он передает ключи своему преемнику и информирует его о своем отключении, так что предшественник отключающегося может соединиться с его преемником. Если же узел выходит из строя, возникает проблема, потому что его предшественник больше не имеет действительного преемника. Чтобы облегчить эту задачу, каждый узел отслеживает не только своего непосредственного преемника, но s последующих преемников, чтобы иметь возможность пропустить вплоть до s - 1 последовательно вышедших из строя узлов и снова замкнуть круг.
С тех пор как были изобретены DHT, в связи с ними было проведено большое количество исследований. Чтобы вы представили себе, насколько много, давайте зададимся вопросом: «Какие исследования в области сетей наиболее цитируемы?» Вы обнаружите, что трудно сравняться с плодовитым Chord (Stoka et а1., 2001). Несмотря на эту гору исследований, приложения DHT начинают медленно появляться. Некоторые клиенты BitTorrent используют DHT для обеспечения полностью распределенного трекера, как мы описали. Большие коммерческие облачные услуги, такие, например, как Dynamo компании Amаzon, также включают методы DHT (DeCаndiа и другие., 2007).
7.6. Резюме
Именование в ARPANET с самого начала было очень простым. В текстовом файле перечислялись имена всех хостов и соответствующие им IP-адреса. Каждую ночь на все машины подгружался этот файл. Но когда ARPANET перерос в Интернет и его объем невероятно увеличился, потребовалась гораздо более изысканная и динамичная схема именования. Сегодня именование доменов в Интернете реализуется при помощи иерархической схемы, называемой службой имен доменов (DNS). Она организует все машины, подключенные к Интернету, в набор деревьев. В системе DNS на верхнем уровне находятся общеизвестные родовые домены, включая com, edu и около двухсот национальных доменов. DNS реализована в виде распределенной базы данных, серверы которой расположены по всему миру. Обратившись к DNS-серверу, процесс может преобразовать имя домена Интернета в IP-адрес, требующийся для общения с компьютером в этом домене.
Электронная почта — это одно из самых популярных приложений Интернета. Ею до сих пор пользуются все, начиная от детей младшего школьного возраста и заканчивая стариками преклонных годов. Большинство систем электронной почты соответствуют стандартам, описанным в RFC 5321 и 5322. Сообщения содержат ASCII-заголовки и данные разных типов, прописанных в MIME-заголовках. Почта передается агентам передачи для доставки и получается от них для представления во множестве пользовательских агентов, включая веб-приложения. Переданная почта доставляется по протоколу SMTP, устанавливающему TCP-соединение между хостом-источником и хостом-приемником.
Всемирная паутина является приложением, которое многие считают Интернетом. Изначально она являлась системой для обработки страниц, написанных на HTML и содержащих гиперссылки на другие страницы, которые загружались при помощи TCP-соединения браузера с сервером. Сегодня большая часть контента является динамической, или на стороне сервера (например, с PHP), или на стороне браузера (например, с JavaScript). Динамические страницы на сервере в сочетании с внутренними базами данных позволяют использовать такие веб-приложения, как электронная торговля и поиск. Динамические страницы браузера превращаются в полнофункциональные приложения, такие как электронная почта, которая работает внутри браузера и использует веб-протоколы для общения с удаленными серверами. Кэширование и постоянные соединения широко используются для улучшения производительности Всемирной паутины.
Использование Всемирной паутины через мобильные телефоны может быть непростой задачей, несмотря на увеличение ширины канала и мощности мобильных устройств. Веб-сайты часто высылают переработанные версии страниц с картинками меньшего размера и более простой навигацией на устройства с маленькими экранами.
Веб-протоколы все чаще используются для коммуникации между машинами. XML является более предпочтительным, чем HTML для описания контента, который легко обрабатывается компьютерами. SOAP является RPC-механизмом, который пересылает XML-сообщения при помощи HTTP.
Цифровое аудио и видео лежали в основе развития Интернета с 2000 года. Сегодня большая часть интернет-трафика — это видео. Значительная его часть передается с вебсайтов при помощи смешанных протоколов (включая RTP/UDP и RTP/HTTP/TCP). Медиа в реальном времени передается многим пользователям. В него входят радио-и телестанции, передающие различные программы. Аудио и видео также используются для конференций в реальном времени. Во многих звонках используется голос поверх IP, а не традиционные телефонные сети, также для них используются видеоконференции.
