Оценка эффективности канала передачи гипертекстовых данных с кэшированием

Размещено на http://www.allbest.ru/

Оценка эффективности канала передачи гипертекстовых данных с кэшированием

Комашинский В.В., Логинов И.В., Иванов И.В.

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

Применение кэширования данных позволяет снизить долю повторно передающихся по каналу связи данных. Указанное обстоятельство вызывает необходимость исследования эффективности каналов передачи данных с кэшированим с целью определения численных характеристик эффективности применения кэширования.

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

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

Входной поток запросов представляет собой сумму потоков запросов от множества пользователей канала передачи данных: ,

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

.

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

Имеется канал передачи данных с кэшированием. Будем рассматривать однонаправленный канала передачи данных (в одну сторону идут только запросы, в другую только ответы). Количество различных гипертекстовых данных в сети Internet в общем случае велико (имеется не менее 100 млн. web-серверов средним размером не менее 1000 объектов). Однако для конкретного канала передачи данных количество разных обрабатываемых ответов не столь велико. В общем случае предположительное число таких ответов можно определить путем экспериментального сбора статистики (использование прокси-серверов) на канале передачи данных в течение достаточного периода времени (неделя, месяц). После сбора такой статистики можно получить следующие величины:

время проведения эксперимента примем равным для конкретного эксперимента;

количество различных ответов системы (запросов, что аналогично в нашем случае) равно ;

Общее количество запросов (ответов) равно ;

Общий размер принятых данных равен .

Требуется построить модель канала передачи и оценить его эффективность при изменяющихся входных данных. Модель канала передачи данных с кэшированием должна отражать влияние размера кэша данных на вероятность попадания ответа на запрос в кэш.

Модель канала передачи данных с кэшированим таких

Исходя из условий постановки задачи можно вычислить следующие характеристики:

средний размер ответа равен ;

значение потока задач составит ;

средняя использованная пропускная способность .

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

Запрос к конкретному ресурсу из множества ресурсов представляет собой случайную величину [2]. При этом размер множества ресурсов равен . Случайная величина распределена по нормальному закону, поскольку общий поток запросов объединяет множество потоков запросов от пользователей [3]. Каждый последующий запрос будем считать независимым от предыдущего вследствие наличия множества пользователей и большого размера множества ресурсов , то есть поток запросов будем рассматривать как поток с отсутствием последействия.

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

В канале передачи данных с кэшированием весь входной поток заявок делится на два: один поток заявок не выходит за пределы кэша данных, а второй выходит из него и поступает в канал передачи данных . Аналогично для ответов на запросы: .

Примем размер кэша данных, равный в байтах или в среднем количестве ответов.

Кэш данных заполняется следующим образом:

Ответ на новый запрос заноситься в кэш (в том случае, если он не заполнен). кэширование данный запрос

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

Вероятность того, что ответ на запрос пользователя находиться в кэше данных (вследствие предположения независимости запросов) составляет отношение среднего количества ответов, находящихся в кэше, к мощности множества ответов [3, 4]:

.

Приведем вероятность попадания в кэш к его размеру в байтах (2):

.

Вероятность того, что ответ на запрос не находится в кэше равен (3):

.

Требуемая пропускная способность канала передачи данных с использованием кэширования для передачи аналогичного потоков запросов и ответов составляет (4):

.

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

Для этого приведем формулу (2) к виду (5):

,

где - время нахождения данных в кэше, которое может принимать значения от 0 до 24 часов. Время проведения эксперимента примем равным недельному периоду сбору статистики и которое равно 192 часа. Предел уменьшения пропускной способности может изменяться в пределах от 1 до , однако в проведенных экспериментах значение не превышало 14, для целей эксперимента возьмем диапазон изменения от 1 до 30, что должно перекрыть возможные варианты каналов передачи гипертекстовых данных.

Рисунок 1 - График зависимости вероятности нахождения данных в кэше от его размера и предела снижения пропускной способности

Следует отметить, что максимальная вероятность попадания в кэш не может превышать следующую величину (6):

Рассмотрим зависимость размера кэша данных от величины пропускной способности канала связи при постоянной вероятности попадания в кэш. Приведем формулу (5) к виду (7):

.

Время эксперимента примем равным недельному периоду сбора статистики и равным 192 часам. Предел уменьшения пропускной способности может изменяться в пределах от 1 до 30, что должно перекрыть возможные варианты каналов передачи гипертекстовых данных. Вероятность попадания в кэш зададим на уровне , реальную пропускную канала передачи данных будем изменять в диапазоне от 100 кбит/с до 10 Гбит/с. Результаты вычислений приведены на рисунке 2.

Рисунок 2 - График зависимости размера кэша данных от величины пропускной способности канала

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

Методика определения эффективности применения кэширования данных

Методика предполагает определение снижения требований к каналу передачи данных через определения вероятности попадания в кэш [5];

- определение рабочих часов пользователей с наибольшей нагрузкой (например, если канал передачи данных проложен от организации, то такими часами будет установленное рабочее время);

- определение значений , , за время часов;

- расчет значений предела снижения пропускной способности ;

- установление предположительного времени нахождения в кэше в пределах часов в зависимости от требования к оперативности данных;

- определение значений вероятности и требуемой пропускной способности канала согласно формулам (2) и (3);

- построение графиков зависимости вероятности попадания в кэш от его абсолютного (в байтах) и относительного (в часах) размера согласно формуле (5).

Экспериментальные данные

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

Таблица 1 - Значения пропускной способности и вероятности попадания в кэш для различных каналов передачи данных

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

Рисунок 3 - График зависимости вероятности попадания в кэш в зависимости от его размера

Построим график вероятности попадания в кэш в зависимости от размера кэша данных (рисунок 4) согласно формуле (5).

В результате проведения расчетов были получены следующие данные:

- вероятность попадания запроса в кэш увеличивается при увеличении размера кэша;

- канал передачи данных 3 имеет наибольшую эффективность при передаче данных с использованием кэширования;

- требования к размеру кэша данных растут прямо пропорционально пропускной способности канала передачи данных.

Заключение

Экспериментальное применение разработанной модели и методик определения эффективности применения кэша осуществлялись для КПД 1. В качестве кэширующеего прокси-сервера использовался squid. Функция устаревания данных информации задавалась в виде константы, равной 4 часам. Размер кэша данных был задан размером 300 Мбайт. В результате обработки данных в течение 182 часов сокращение количества внешних запросов составило порядка 22 % по сравнению с эталонным, что хорошо согласуется с теоретическим значением, полученным в результате расчетов.

Рисунок 4 - График зависимости вероятности попадания в кэш от абсолютного размера кэша данных

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

Литература

1. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы [Текст] / В.Г. Олифер, Н. А. Олифер - СПб.: Издательство «Питер», 1999. - 672 с.: ил.

2. Шмейлин, Б.З. Повышение производительности микропроцессорных систем путем эффективного использования кэш. Системы и средства информатики [Текст]: / Б.З. Шмейлин, Е.Я. Попкова. Ежегодник/ Рос. акад. наук, Ин-т проблем информатики. -М. : Наука. -2006.-526 с. :ил. с. 496-510.

3. Вентцель, Е.С. Теория вероятности и ее инженерные приложения [Текст] / Е.С. Вентцель, Л.А. Овчаров - М.: Высшая школа, - 2000. - 480 с.

4. Деревенсков, С.О. Анализ эффективности алгоритмов Web-кэширования [Текст] / С.О. Деревенсков, А.А. Казаковский, В.Н. Скакунов, П.Е. Смирнов. Материалы VII всероссийской научно-методической конференции «Телемеханика 2000», с. 42-45, 2000 г.

5. Хотелева, А.Л. Исследование эффективности политик кэширования Web-объектов [Текст] / А.Л. Хотелева, В.С. Синепол Материалы межвузовской научно-технической конференции «Неделя науки СПбГПУ». Ч. VI: с. 37-39, 2005 г.

Размещено на Allbest.ru