Кеширование информацонных потоков и стратегия оптимизации маршрутов в распределенных системах

С.А. Крашаков, Л.Н. Щур

Тезисы докл. Всерос. конф. "Научный сервис в сети ИНТЕРНЕТ", г.Новороссийск, 18-23 сентября 2000, с. 145-148

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

I. Введение

За последние годы коннективность Российских сетей существенно возросла. Большинство общероссийских сервис-провайдеров соединены друг с другом на скорости 10 Мбит/с, а некоторые - на скорости 155 Мбит/сек посредством Московской опорной сети (RMIX) и точки межсетевого обмена M9-IX (Москва). Типичная пропускная способность каналов подсоединения региональных сетей - 2 Мбит/сек. Наиболее узким местом российских сетей остаются зарубежные каналы. Однако и в этом в последние годы наметился некоторый прогресс. Например, в рамках Российско-американского проекта MirNet, в частности, организован виртуальный канал между сетью FREEnet и vBNS (США).

Системы кеширования интернетовского траффика (в первую очередь - WWW) успешно развиваются во всем мире уже 5-6 лет и позволяют увеличить пропускную способность канала связи почти вдвое, дновременно снизив среднее время ожидания ответа на запрос пользователя. Суть кеширования www-траффика состоит в том, что запрос пользователя на получение документа перенаправляется на кеш-сервер, который сначала проверяет наличие документа в своем кеше, после чего продолжает обслуживание запроса. Если документ в кеше не найден, то кеш-сервер направляет запрос на сервер-источник документа или другому кеш-серверу.

На сегодняшний день насчитывается свыше десятка программных и аппаратно-программных решений кеш-серверов, в первую очередь, следует упомянуть Squid [1], Novell Internet Cache System, Network Appliance
NetCache, Cisco Cache Engine, Infolibria DynaCache/DynaLink и ряд других. Многие производители компьютеров (IBM, Compaq, Dell, Swell и др.) выпускают кеш-серверы на базе своих серверов с предустановленными
Novel ICS или Squid. Ряд фирм выпускают решения для "прозрачного" кеширования, когда  пользователю не надо менять настройки броузера, и кеширование производится незаметно для пользователя.

Второй подход к оптимизации информационных потоков состоит в создании иерархической сети кеш-серверов. При создании сети кеш-серверов появляется возможность установки отношений наследования нформации (parent) и взаимоподдержки (sibling). В тех случаях, когда разные кеш-сервера имеют различную коннективность, появляется возможность динамической оптимизации "расстояния" от источника информации до потребителя, которое измеряется в числе скачков и среднем времени прохождения тестовых пакетов. Такая возможность реализована, например, в squid, начиная с версии 2.

Система кеширования национального уровня с иерархической сетью создана, например, в США.  Система кеширования IRCache/NLANR (США), одна из первых в мире, состоит из серверов, расположенных в 5 основных суперкомпьютерных центрах США и объединенных скоростным каналом связи vBNS - 625 Mbps - 2.4 Gbps, а также в FIX-West (Сан-Хосе), DEC-IX (Пало-Альто) и Research Triangle Park (Северная Каролина) [2]. Каждый из серверов имеет собственную коннективность в Интернет, и запрос, поступающий на любой из кеш-серверов NLANR (при отстутствии информации в кеше) направляется на сервер, "ближайший" к источнику информации.

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

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

Однако на сегодня нам практически неизвестны работы, в которых проводилось бы сравнение алгоритмов выбора parent-серверов с точки зрения выбора оптимального маршрута и балансировки траффика между различными маршрутами.

Настоящая работа посвящена сравнительному изучению возможности выбора оптимального маршрута получения документов через систему связанных друг с другом кеш-серверов. Мы изучаем некий усредненный параметр, тесно связанный с временем получения информации. Именно, мы поставили серию экспериментов, целью которых является измерение средней скорости потока информации от различных доменов в зависимости от схемы отношений доступных нам кэш-серверов. Измерения проведены на основе анализа реальных запросов пользователей в автономной системе AS-9113 (сеть Chg-FREEnet).

В разделе II мы подробно описываем постановку задачи, а в разделе III - методику проведения эксперимента. В разделе IV приведены результаты эксперимента и их обсуждение. Наконец, в Заключении (раздел V)
обсуждаются конкретные примеры, в которых могут быть важны полученные нами результаты.

II.  Постановка задачи

В кэш-сервер squid, начиная с версии 2.0, введена возможность netprobe database. При поступлении TCP GET запросов к кеш-серверу на каждый n-й запрос к определенному адресу кеш-сервер посылает ICMP ECHO-запросы (аналог traceroute) на сервер-источник информации. Информация о RTT и числе скачков (hop) до различных серверов накапливается в базе netprobe database. Периодически (по умолчанию, 1 раз в час) происходит обмен этой базой между соседними кеш-серверами (parent и sibling). Использование содержимого этой базы позволяет кеш-серверу, в принципе, выбирать кратчайший маршрут до нужной информации при поступлении к нему от клиента очередного TCP GET запроса. Это может происходить или напрямую (direct) или через один из соседних кеш-серверов (parent).

В стандартном Squid-2 база данных содержит время t_{pd} от сервера parent до источника информации {destination} и время t_{od} от сервера {original} до сервера-источника {destination} и для выбора оптимального
маршрута сравниваются t_{pd} и t_{od}. Однако ряде случаев такой не всегда яляяется наилучшим. Например, время t_{op} от сервера оriginal до сервера parent может быть достаточно большим. Наше предложение состоит в сравнении времени t_{od} со временем t_{op}+t_{pd}, а не просто со временем t_{pd}, что применяется сегодня в кеш-сервере squid 2.x. С этой целью мы использовали squid-2.3.STABLE2 [3], в код которого были внесены необходимые дополнения.

III.  Методика эксперимента.

Для эксперимента были установлены два почти идентичных кеш-сервера с объемом оперативной памяти 256МБ и емкостью дискового кеша 9ГигаБайт, работающих под управлением FreeBSD и использующие squid-2.3.STABLE2 [3]. Первый сервер (setup#1) был сконфигурирован без использования "соседей", второй (setup#2) мог использовать 5 основных серверов NLANR (uc.cache.nlanr.net, bo.cache.nlanr.net, pb.cache.nlanr.net, sd.cache.nlanr.net, sv.cache.nlanr.net) в качестве parent с опцией closest-only (т.е. запросы через них производились только тогда, когда соответствующий маршрут оказывался кратчайшим). Оба сервера располагались в сети Chg-FREEnet.

Эксперимент состоял в анализе http-запросов, исходящих из сети Chg-FREEnet. На момент эксперимента сеть состояла из 12 сетей класса С, число компьютеров около 1000. Большинство сетей класса С объединены 10 Мбит/сек оптоволоконной опорной сетью. Автономная система подсоединена на скорости 2 Мбит/сек к российской точке обмена M9-IX. Внешний канал 2 Мбит/сек до M9-IX в среднем загружен на прием - на 45-50%, на передачу - на 70-80%. Для связи с серверами NLANR использовался канал 2 Мбит/сек Mir-net. Для связи типа direct использовался 512 кбит/сек канал РФФИ, арендуемый у компании Демос, demos.net (Москва)-- cw.net (Нью-Йорк), а также канал RBnet (Москва) -- TeleGlobe (Нью-Йорк) (для доступа в ряд европейских сетей).

Было сгенерировано 4 различных набора данных, которые были использованы для сравнения разных способов доступа - напрямую или канал MirNet через NLANR parents. Для этого использовался реальные log-файлы кеш-сервера www-cache.chg.ru за один или несколько предыдущих дней, из которого извлекались GET-запросы (исключая запросы к домену .ru) и генерировались запуски wget с соответствующими URL, причем интервалы времени делались равными (или пропорционально, например, в 2 раза, меньшими) интервалам между запросами в исходном log-файле. Тесты запускались в различные дни, преимущественно в выходные или в рабочие дни по ночам одновременно на двух машинах, использующих различные прокси-серверы (setup#1 и setup#2).

Для анализа результатов использовалась программа calamaris-2.29 [4], которая, в частности, подсчитывает среднюю скорость передачи данных для различных видом запросов (DIRECT, PARENT, и т.д.). При анализе мы не учитывали попадания в кеш (HIT), а сравнивали только MISS - DIRECT и PARENT-{HIT, MISS, и т.д.}.

IV. Результаты эксперимента

В качестве основного критерия сравнения использовали отношение скорости получения документов через parent посредством кеш-сервера setup#2 к скорости получения документа напрямую от источника посредством кеш-сервера setup#1. В дальнейшем мы будем называть отношение средних скоростей получения документов через parent к получению документов напрямую параметром эффективности системы кеширования U.

Значения параметра эффективности сильно меняются от набора к набору, что обусловлено, по-видимому, различной загрузкой линий связи в разные дни недели и в разное время суток. Для ряда доменов (ca, de, edu, se) параметр эфффективности близок к 1. Это те домены, прямой доступ которых осуществляется через достаточно свободный канал RBnet, сравнимый с каналом MIRnet, через который доступны parent серверы в случае setup#2.

В других случаях (домены au, com, gov, it, jp, nu, tw, uk) эффективность многоуровневой системы кеширования ясно выражена.

V.  Заключение

В целом, показано преимущество многоуровневой системы кеширования. Использование netprobe database является довольно эффективным алгоритмом выбора оптимального маршрута в иерархической системе кеш-серверов. Особенно наглядно это проявляется для таких доменов, как .com, .net, .org, а также URL, использующих IP-адреса вместо доменных имен, которые географически разбросаны по всему земному шару, включая и Российские сети.

Одна из сложностей проведения вышеуказанных измерений состоит в том, что помимо сравнения оптимального пути, кеш-сервер при работе использует и такие алгоритмы, как ICP или Cache-Digest (запрос на родительский сервер, имеющий информацию в кеше). В подобных случаях не исключены запросы к parent, которые могут оказаться менее эффективными, чем direct.

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

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

Литература.
[1] http://www.squid-cache.org/
[2] http://www.ircache.net/Cache/
[3] http://www.squid-cache.org/Versions/v2/2.3/
[4] http://Cord.de/tools/squid/calamaris/