Маршрутизация сетей по принципу пчелиного роя

комментировать
версия для печати

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

Традиционные, «централизованные» способы маршрутизации были разработаны для относительно маленькой сети. Списки доменов, которые хранятся на каждом сервере, постоянно обновляются и растут прямо пропорционально количеству узлов в сети, а количество этих узлов растет в геометрической прогрессии. Это серьезная проблема. Ученые считают, что интернет нуждается в принципиально новой системе маршрутизации.

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

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

Такой тип кооперации присутствует во множестве природных сетей, например, среди насекомых. Каждый узел в сети имеет ограниченный набор правил поведения, но при этом вся система обладает предсказуемыми глобальными свойствами. При копировании такой системы в интернете проблема заключается в том, чтобы обеспечить максимальную скорость взаимодействия между узлами. К решению именно этой проблемы приблизились исследователи из Калифорнийского университета, которые разработали быстрый алгоритм, который использует локальные правила, для поиска узлов и информации в случайным образом сформированных, масштабируемых сетях, таких как интернет. Их работа под названием «Масштабируемый перколяционный поиск в сетях со степенным распределением» («Scalable Percolation Search in Power Law Networks») опубликована в онлайне.

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

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

Алгоритм включает три базовых этапа: кэширование контента, внедрение запроса и перколяцию связей. Кэширование контента происходит когда узел присоединяется к пиринговой сети: он добавляет список своего содержимого на соседние узлы. Этап внедрения запроса происходит аналогичным образом, но происходит при выполнении каждого запроса. На этапе перколяции связей запрос попадает на один из базовых серверов интернета, которые соединены друг с другом мощными каналами связи. Это ключевой этап. Американскими учеными совершен концептуальный прорыв, потому что они обнаружили, что полноценный процесс поиска может проводить «локально», то есть при опросе только соседних серверов.

При таком методе каждый запрос генерирует относительно малый трафик, и его количество растет медленнее, чем растет вся сеть в целом. Например, в сети со 100 млн узлов, каждая «случайная проходка» затрагивает около 100 узлов, а общее количество запросов не превышает 10 тыс.

Использование нового алгоритма может быть особенно эффективным в файлообменных Р2Р-сетях, где можно уменьшить общий объем передаваемого трафика на один или два порядка. Сейчас ученые работают над программной библиотекой, которую можно было бы включить в комплект программного обеспечения Gnutella и совершить переход на новую технологию маршрутизации в течение одного-двух лет.

Другие