файловые системы

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

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

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

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

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