Системы резервирования трафика в Интернет
Дмитрий Г. Долгих, Андрей М. Сухов
Самарский государственный аэрокосмический университет
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] следует, что эффективность реальных систем резервирования ограничена 4
5% и размеры ее начинаются с документов, а
(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