Системы резервирования трафика в Интернет

Дмитрий Г. Долгих, Андрей М. Сухов

Самарский государственный аэрокосмический университет

e-mail: ddolgikh@ssau.ru, sukhov@ssau.ru

Аннотация

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

Ключевые слова: система резервирования трафика, распределение Zipfa, размер cache

Введение

Настоящая статья посвящена обсуждению путей повышения эффективности использования каналов, ведущих к вышестоящим интернет сервис провайдерам (ISP). Данная статья опирается на опыт Самарской региональной сети для науки и образования, поддерживаемой Самарским государственным аэрокосмическим университетом (СГАУ). В ней также обобщены материалы второго семинара по управлению кэширующими системами европейских научно-исследовательских сетей, проведенного TERENA под эгидой DESIRE в Будапеште в марте 2000 года, где один из авторов делал доклад по анализу преимуществ, получающихся при использовании таких систем.

В качестве объекта исследования выбрана система резервирования трафика в Интернет приложениях. До недавнего времени подобный сервис был необязательным, и пользователи могли по собственному желанию подключаться к подобным системам, настраивая свой браузер для работы через proxy cache. В настоящее время практически все крупные провайдеры, как в России, так и за границей, включили подобные системы на базе Internet Cache Protocol (ICP) в собственную инфраструктуру предоставления услуг.

Цель настоящей статьи создать математическую модель системы резервирования и вычислить оптимальные параметры cache [1], такие как размер cache, максимальная величина эффективности, время жизни документа. На базе полученных результатов даются рекомендации по настройке параметров реальных cache систем. Впервые такой подход был применен в работе Breslau и др. [2].

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

1. Оптимальный размер cache-системы

Пользователи из локальной сети запрашивают информацию в глобальной. Эта информация разбита на порции, называемые документами. Часть документов запрашивается неоднократно и поэтому их выгодно хранить в локальной системе резервирования трафика или, по иному, в cache системе. В этом разделе будет исследоваться оптимальный размер cache системы, используемой для хранения информации.

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

 Рис.1. Схема системы резервирования трафика

Пусть коллективный пользователь запросит из глобальной сети k документов за время t. Очевидно, что

(1)

будет линейной функцией, зависящей от суммарной скорости внешних каналов и времени t , где C- константа. Пусть p из этих документов будут уникальными, тогда эффективность cache системы может быть определена как

(2)

отношение количества документов, запрошенных неоднократно (k-p), к их общему количеству.

Известно, что документы из глобальной сети запрашиваются неравномерно. Некоторые исследователи [3-5] предполагают, что относительная частота запросов документов из глобальной сети подчиняется первому закону Zipf [6]. Он констатирует, что цитирования любого документа из глобальной сети равна

(3)

где - частота упоминания наиболее запрашиваемого документа, а n номер документа в порядке убывания рейтинга цитируемости. Более поздние исследования показали, что действие этого закона можно распространить на коллективного пользователя. Но полученное распределение не будет точно следовать первому закону Zipf, а должно быть заменено обобщенным законом [2,7,8]:

(4)

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

Рис.2. Иллюстрация распределения Zipfа

Из условия нормировки - сумма вероятностей запроса коллективным пользователем всех документов равна 1 - легко найти значение A:

(5)

Подобное условие впервые было применено в работе [2]. Для того, чтобы далее работать с аналитическими выражениями сумму из ур.(5) можно заменить интегралом

(6)

(7)

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

Рис.3. Граничные условия

Применяя первый закон Zipfa к точке с координатами (2,m) можно получить абсолютную величину цитирования первого документа:

(8)

(9)

2. Эффективность системы

В этом разделе хотелось бы оценить предельную величину эффективности системы резервирования трафика для работы одиночного пользователя. Для этого надо попытаться смоделировать его поведение: пользователь работает сеансами длительностью , и во время одного сеанса он выкачивает l документов. Причем оба этих параметра могут меняться в широких пределах.

Cache система должна удовлетворять условиям (8,9) с фиксированными параметрами t=T, m=M

(10)

Кроме этого, с момента ее инсталляции должно пройти время t>T, таким образом осуществляется переход от статической к динамической модели cache, изменяющейся со временем. В динамической модели можно без ограничения общности считать, что сеанс пользователя ограничен моментом (см. рис.4):

Рис.4. Схема динамической модели

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

Ввиду того, что вероятность A обнаружить наиболее цитируемый документ из cache системы мала, то можно воспользоваться распределением Пуассона [9]. Согласно ему вероятность того, что в серии из l испытаний наиболее цитируемый документ будет запрошен из cache, равна:

(11)

(12)

- вероятность не обнаружить документ в cache.

Для второго документа

(13)

Суммируя эти величины для всех документов, находящихся в cache, т.е. до значения M получим вероятность

(14)

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

(15)

3. Системы, подчиняющиеся обобщенному распределению Zipfа

В этом разделе хотелось бы обсудить другие подходы к моделированию cache систем.

Прежде всего, это касается условий нормировки (5). Следует обратить внимание на существенную разницу для суммирования вероятностей от m до p, которые дает распределение, подчиняющееся первому закону Zipfa

(16)

И реальное дискретное распределение (см. рис. 3)

(18)

Поэтому правильнее пользоваться условием

(18)

представляющим собой альтернативное определение , более приемлемое для динамической cache модели. В выражении (18) применено распределение, подчиняющееся обобщенному закону Zipfа. Теперь мы можем легко модернизировать ключевые выражения (7,9,15) для величин A, m,

(19)

(20)

или, учитывая, что на практике [2]

(21)

(22)

4. Рекомендации для систем резервирования на основе ICP протокола

Этот раздел содержит рекомендации, которые помогут правильно настроить cache систему, а также ряд соотношений для реальных систем резервирования трафика. Прежде всего размер cache системы зависит от времени, в течении которого она заполняется. Для реального программного обеспечения используется параметр reference-age T из ур.(21) , представляющий собой время в течении которого документ хранится в системе резервирования. Единственное требование к нему быть значительно больше среднего времени сеанса для пользователя. В нашей сети он принят равным одному месяцу.

Возвращаясь к соотношению (1) заметим, что

(23)

представляет собой объем трафика, прошедшего через cache систему за время T. Постоянная

(24)

есть величина, обратная среднему размеру документа , запрошенному из глобальной сети.

Из экспериментальных данных [2] следует, что эффективность реальных систем резервирования ограничена 45% и размеры ее начинаются с документов, а

(25)

секунд или несколько суток

(26)

то есть, в широких пределах можно считать отношение эффективного размера cache к скорости его заполнения постоянным.

Следующий вопрос касается вычислений величины предельно возможной эффективности cache систем. Выражение (22) достаточно легко исследовать с помощью компьютерной алгебры. Для получения значения эффективности работы коллективного пользователя условие (22) необходимо применить в целом к cache системе. Тогда условие должно быть переписано в виде:

l=k=15M

(27)

Для практических расчетов следует применять менее строгое условие:

l=M

(28)

Полагая , получим следующее ограничение

(29)

При более малых значениях , мало отличается от эффективности cache в целом .

Обсуждение

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

Для дальнейших исследований необходимы более подробные экспериментальные данные. Прежде всего это касается выяснения зависимостей и . Для этого необходимо исследовать полные данные крупных cache систем и их выборки по кластерным технологиям.

После получения обработанных результатов можно будет оптимизировать условия для , , M, A и вывести более определенные аналитические выражения. К сожалению, пока мы не обладаем подобными техническими возможностями.

Литература

[1] M. Abrams, C. Standridge, G. Abdulla, S. Williams, E. Fox, Caching Proxies: Limitations and Potentials,

[2] L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker, Web Caching and Zipf-like Distribution: Evidence and Implications, in: IEEE Infocom, vol. XX, no. V, 1999, pp. 1-9

[3] S. Classmann, A caching relay for the world wide web, in: First International Conference on the World-Wide Web, CERN, Geneva, Switzerland, May, 1999

[4] V. Almeida, A. Bestavrosd, M. Crovella, and A. De Oliveira, Characterizing reference locality in the WWW, in: IEEE International Conference in Parallel and Distributed Information Systems, Miami Beach, Florida, USA, December, 1996

[5] C. Cunha, A. Bestavros, and M. Crovella, Characteristics of WWW client-based traces, Technical Report TR-95-010, Boston University, Computer Science Dept., Boston, MA 02215, USA, April 1995

[6] G.K. Zipf, Relativity frequency as a determinant of phonetic change, Reprinted from the Harvard Studies in Classical Philology, Vol. XL, 1929

[7] N. Nishikawa, T. Hosokawa, Ya. Mori, K. Yoshidab, and H. Tsujia, Memory-based architecture for distributed WWW caching proxy, in: The 7th WWW Conference, April 1998

[8] V. Almeida, M. Cesirio, R. Canado, W. Junior, and C. Murta, Analyzing the behavior of a proxy server in the light of regional and cultural issues, 1998

[9] J. Boucher, Voice teletraffic systems engineering, Charter 2, ISBN 0-89006-335-4