автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Метод расчета и оптимизации параметров системы кэширования Интернет-трафика

На правах рукописи

Долгих Дмитрий Геннадьевич

МЕТОД РАСЧЕТА И ОПТИМИЗАЦИИ ПАРАМЕТРОВ СИСТЕМЫ КЭШИРОВАНИЯ ИНТЕРНЕТ-ТРАФИКА

Специальность 05.13.01 -Системный анализ, управление и обработка информации (технические системы и связь)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Самара - 2009

003473530

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева»

Научный руководитель:

кандидат технических наук, доцент

Симановский Евгений Аркадьевич

Официальные оппоненты:

доктор технических наук, профессор

Коварцев Александр Николаевич

кандидат технических наук, доцент

Родичев Юрий Андреевич

Ведущая организация:

Государственное образовательное учреждение высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики»

Защита состоится 30 июня 2009 г. в 10 часов на заседании диссертационного совета Д 212.215.07 при государственном образовательном учреждении высшего профессионального образования «Самарский государственный аэрокосмический университет имени академика С. П. Королева» по адресу: 443086, г. Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке СГАУ.

Автореферат разослан 28 мая 2009 г. Ученый секретарь

диссертационного совета Д 212.215.07

доктор технических наук, профессор

Белоконов И. В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

На данный момент существуют два основных подхода, которые описывают взаимосвязь параметров системы кэширования. Первый из них основан на экспериментальных результатах, полученных для частных случаев, как, например, в работах В. Алмейды, Л. Бента, А. Сарайя и других. Этот подход дает рекомендации по выбору параметров существующих систем кэширования. Данный подход требует наличия экспериментальной информации о настраиваемой системе, которая не всегда присутствует, а получение такой информации занимает продолжительное время из-за инертности систем кэширования. Второй подход основан на построении аналитической модели системы кэширования. Первоначально он был представлен в работах Л. Бреслау и А. Вольмана. Однако существующие модели дают только качественные зависимости параметров системы. Кроме того, в рамках существующих подходов рассматривается ограниченное количество факторов, влияющих на работу системы. Таким образом, в настоящее время отсутствуют методы, позволяющие выполнить расчет параметров системы кэширования и установить зависимость между параметрами системы и параметрами смежных систем. С этой точки зрения поиск новых подходов к анализу систем кэширования и расчету и оптимизации ее параметров является актуальной задачей.

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

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

1) Анализ принципов работы, взаимосвязей и параметров, влияющих на функционирование системы кэширования и определение критериев ее эффективности.

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

3) Экспериментальная проверка адекватности созданной математической модели.

4) Разработка алгоритмов выбора оптимальных параметров системы кэширования и проверки эффективности ее работы.

Научная новизна заключается в следующем:

1) Построена математическая модель системы кэширования, описывающая взаимосвязь ее параметров и показателей эффективности, отличающаяся от

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

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

3) Впервые получена зависимость производительности системы кэширования от объема ее памяти, скорости внешнего канала и показателя распределения Зипфа, и предложен способ учета влияния обновлений документов в Интернет на производительность системы путем изменения значения показателя распределения Зипфа.

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

Практическая ценность и реализация результатов работы:

1) Создано программное обеспечение, позволяющее проводить детальное исследование запросов пользователей сети, анализ работы системы кэширования и расчет всех параметров, входящих в модель.

2) Полученные теоретические результаты и программные продукты были использованы при начальной установке и используются для контроля работы систем кэширования трафика локальной сети Межвузовского медиацентра г. Самары (ММЦ), Самарского государственного аэрокосмического университета имени академика С.П.Королева (СГАУ) и коммерческого поставщика услуг Интернет ЗАО «Самара Телеком», о чем получены соответствующие акты внедрения.

На защиту выносятся:

1) Математическая модель системы кэширования, учитывающая комплекс факторов, включающий характер распределения запросов пользователей, ограничения объема памяти системы кэширования, влияние обновлений документов в сети Интернет, конечную скорость передачи внешнего канала связи и экономическую эффективность применения системы.

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

3) Способ учета влияния скорости внешнего канала и обновления документов в Интернет на эффективность системы кэширования.

4) Алгоритмы определения оптимальных настроек системы кэширования и проверки эффективности ее применения.

Апробация работы. Теоретические и практические аспекты работы докладывались и обсуждались на международном рабочем семинаре «Цифровые сети в Среднем Поволжье», Самара, СГАУ, 1998; втором международном семинаре администраторов систем кэширования «DESIRE-II», Будапешт, 2000; ежегодной международной конференции союза научно-образовательных сетей «TERENA», Анталия, 2001; восьмой всероссийской конференции представителей региональных научно-образовательных сетей «RELARN-2001», Санкт-Петербург - Петрозаводск, 2001; VI рабочем совещании по электронным публикациям «El-Pub2001», Новосибирск, 2001; X, XI и XIV всероссийских научно-методических конференциях «Телематика», Санкт-Петербург, 2003, 2004 и 2007;

научном семинаре МГУ «Современные сетевые технологии», 30.03.2004, Москва, 2004; II международной научно-технической конференции «Информационные технологии в науке, образовании и производстве», Орел, 2006.

Публикации. Всего по теме диссертации опубликовано 14 печатных работ, из них 5 работ в изданиях, рекомендуемых ВАК, в том числе одна в зарубежном англоязычном рецензируемом журнале.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников из 107 наименований и 5 приложений. Работа изложена на 137 страницах, содержит 34 рисунка и 4 таблицы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Проведен анализ подходов к описанию распределения запросов пользователей к документам сети Интернет. Существующие теоретические и практические исследования в этой области таких авторов, как С. Глассман, М. Кровелла, В. Алмейда, С. Крашаков, А. Беставрос, М. Гакку и других, а также собственные данные [3, 6, 11], позволили сделать вывод о том, что распределение количества запросов документов подчиняется обобщенному распределению Зипфа. При этом вероятность р, запроса /'-го по популярности документа, определяется выражением:

О)

где: А - нормировочная постоянная, которую выбирают таким образом, чтобы сумма всех вероятностей была равна единице; а - константа для группы пользователей, характеризующая степень схожести их запросов и принимающая значения в пределах от нуля до единицы (0 < а < 1).

Выполнен анализ существующих исследований работы систем кэширования и их результатов. Были проанализированы работы, основанные на экспериментальных исследованиях (В. Алмейда, Л. Бент, А. Сарайя и др.), работы, использующие имитационное моделирование (В. Прищепа, М. Арлитт, П. Као, Л. Черкасова и др.), исследования, в которых строятся аналитические модели (Л. Бреслау, А. Вольман), а также работы, использующие стоимостные оценки (Л. Келли). На основе анализа рассмотренных исследований, был сделан вывод, что наиболее перспективным методом анализа работы системы кэширования является построение ее аналитической модели. В то же время было отмечено что, существующие методы не предлагают решений, которые связывали бы параметры системы с параметрами смежных систем и позволяли бы выполнить аналитический расчет значений параметров системы.

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

Рассмотрены данные, с которыми работает система кэширования. Было установлено, что элементарной единицей информации для системы кэширования является документ -

5

результат выполнение одного НТТР-запроса, и каждый такой документ имеет свой уникальный адрес (URL). Было отмечено, что документы делятся на кэшируемые и некэшируемые. Содержание кэшируемых документов постоянно или меняется редко в сравнении со средним временем пользовательской сессии. Некэшируемые документы - это документы, содержание которых создается динамически. Сохранение некэшируемых данных в системе нецелесообразно, так как они оказываются устаревшими сразу после исполнения запроса. Отмечено, что соотношение количества запросов кэшируемых документов к общему количеству запросов будет влиять на верхнюю границу производительности системы. Кроме того, была рассмотрена другая характеристика документов - их объем, среднее значение которого остается постоянным в течение нескольких последних лет.

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

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

Организация I

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

Рисунок 1 - Составляющие комплексной модели системы кэширования

Система кэширования рассмотрена с точки зрения системного подхода. Анализ взаимодействия системы кэширования со смежными системами, а также процессов, происходящих в самой системе, показал, что для оптимизации эффективности системы кэширования по выделенным критериям необходимо учитывать комплекс явлений, влияющих на систему (рис. 1). Распределение запросов пользователей соответствует распределению Зипфа с параметром а. Объем используемой памяти является параметром самой системы кэширования, объем памяти реальных систем конечен. Параметрами документов в Интернет является средний размер и время их обновления, так как оно определяет, насколько часто некоторые документы придется запрашивать повторно. Для

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

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

Основные предположения модели, сформулированы следующим образом:

1) Скорость поступления информации в систему кэширования и1П, ограничена скоростью доступа к глобальной сети «тах.

2) Все документы являются одиночными, все запросы к документам являются независимыми.

3) Популярность документов в запросах пользователей подчиняется обобщенному распределению Зипфа.

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

5) Средний размер документа одинаков для документов всех типов и обозначен Вср .

Производительность идеальной системы с неограниченной памятью НШеа1

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

H¡„

A\-dx,

(2)

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

1

AÍ—dx = 1,

J Y"

(3)

где: Ь - количество уникальных документов среди всех переданных документов.

Рассмотрены специальные

I 10 100 1000 10000 м

Рейтинг документа

Рисунок 2 - Специальные точки распределения Зипфа

АК Ма

точки

распределения Зипфа (рис.2). Первая из них имеет координаты (М, 2). Эта точка соответствует последнему документу, переданному более одного раза. Она определяет количество документов, которые вносят вклад в полезную работу системы. Вторая точка имеет координаты (Ь, 1). Эта точка соответствует последнему запрошенному уникальному документу. Записав уравнения в соответствии с распределением Зипфа для этих точек, получим выражения для связи величин А, Ь, М и К между собой:

= 2,

АК

La ~ '

(4)

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

Следствия из выражений (2) - (4) позволяют определить взаимосвязи между основными параметрами системы кэширования.

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

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

Ятах=2(«-1">с. (5)

Полученное выражение показывает, что даже в случае отсутствия изменений документов предельная производительность будет составлять порядка 50% при типичных значениях а = 0.8; рс = 0.6, что согласуется с практическим опытом и отличается от предыдущих исследований, согласно которым значение производительности может достигать рс.

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

= . (6)

'.-4т)

где: Я - число документов, хранящихся в системе.

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

Hr =#max

2l/ar(l -HR)

(7)

Тоб„(\~а)

где: Т0бн - средний период обновления документов; г- относительный объем памяти системы кэширования. Использование относительного объема памяти в качестве параметра позволяет сравнивать системы, работающие в разных условиях. Он имеет размерность времени и вычисляется как:

5й

Г = (8) int

,В

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

Получена зависимость для объема памяти системы кэширования от желаемой производительности:

<?в _ в 0 ~ сс)Тобн " — ■ -

21/а(1-#к)

Л

Границы применимости данных выражений определены как:

1

Н-£-\'а. (9)

— "max 2./«(1_Яд)- (Ю)

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

C^w^Lc- (и)

8

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

= (12) К

где: - д соотношение между количеством запросов к популярным документам и общим количеством запросов; Т5, - время сбора статистики; /л - частота обновления популярных документов. Конечное значение показателя распределения Зипфа вычисляется как:

асог = а-Аа. (13)

Критерий экономической эффективности системы в виде значения чистой экономии Еч можно определить как разницу между экономией от ее использования и затратами на

ее установку и поддержание:

(14)

М 7-1

где: Ич - общее количество статей расходов, которые сокращаются при использовании

системы; (У, - объем экономии по ¡-й статье; N г- общее количество статей расходов,

которые сопряжены с использованием системы; - объем затрат поу'-той статье.

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

' в 4

т-

Т

"Р у

(15)

где: Z(fev - единовременные затраты на закупку оборудования, программного обеспечения

и другие, не связанные с закупкой памяти системы; 2В - цена единицы объема памяти;

Бв - объем памяти системы; 2за1 - периодические затраты на обслуживание; Тгер - период

замены оборудования.

Экономия от использования системы кэширования определяется как стоимость получения объема информации, равного объему, передаваемого из памяти системы кэширования:

2(0 = а,,/', (16)

где: 2,га/ - цена получения информации в единицу времени; //" - производительность системы кэширования по объему информации.

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

/ и \

(2 , 1

Т гер У

(17)

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

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

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

В качестве объекта для проведения первого эксперимента была использована система кэширования трафика сети СГАУ. Во время эксперимента изменялся объем доступной памяти Бв при постоянной скорости внешнего канала. Измеряемым значением при этом была производительность системы. Эксперимент занял шесть месяцев, в течение которых были исследованы четыре экспериментальных интервала для значений объема памяти системы кэширования, равных 0.41, 1.0, 1.90 и 3.25 Гбайт.

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

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

—теоретически« расчет

вычисли теленыиексврименг

0,00 1,00 2,00 3,00 4,00 3.00 6,00 7,00

Относительный объем памяти системы г. дней

0,00 1,00 2,00 3,00 4,00 5,00 6,00

Относительный объем памяти системы т. дней

Рисунок 3 - Результаты эксперимента на системе кэшировании СГАУ (слева) и вычислительного эксперимента по статистике системы кэширования сети г. Черноголовка (справа)

Анализ результатов эксперимента позволил найти соотношение между производительностью по количеству документов Н и производительностью по объему Нв:

нв =1_ Вю^У^Н)

в„,„

(18)

где: ВтХ- средний размер документа, полученного из Интернет; Вда - средний размер документа, переданного пользователям. Это соотношение может быть использовано при вычислении чистой экономии и, в соответствии с экспериментальными данными, может быть оценено как:

Второй эксперимент был проведен с использованием элементов имитационного моделирования. Для его проведения была создана программа, которая эмулирует работу системы кэширования, анализируя статистику запросов пользователей реальной системы. В качестве входных данных была использована статистика запросов пользователей к системе кэширования сети г. Черноголовка за шесть произвольных месяцев одного года. В процессе эксперимента задавались ограничения на объем памяти для хранения документов, проводился расчет производительности системы для каждого значения объема. Результаты эксперимента представлены на рис. 3 справа. На нем показана теоретическая зависимость, рассчитанная по параметрам, вычисленным в результате анализа статистики запросов, и результаты работы имитационной модели. Анализ данных показывает, что относительная ошибка вычисления по полученным теоретическим зависимостям не превышает 5% в области значений относительного объема памяти системы, превышающего 0.5 дней.

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

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

Алгоритм определения оптимальных настроек системы позволяет оптимизировать значение объема памяти системы в соответствии с критериями эффективности. Предлагаемый алгоритм схематически изображен на рис. 4.

Алгоритм состоит из следующих шагов:

1) Определение исходных параметров. На этом шаге определяются или оцениваются показатель а распределения Зипфа, вероятность кэшируемости документов рс, время

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

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

3) Расчет зависимостей для критериев эффективности - производительности от объема памяти системы кэширования и чистой экономии, а также определение зависимости для скорости ее изменения.

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

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

и

Рисунок 4 - Схема алгоритма определения огггимальных настроек

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

Основными шагами данного алгоритма являются:

1) Сбор статистики о работе системы. Минимальное время сбора статистики должно быть в несколько раз больше, чем относительный объем памяти системы кэширования.

Это время Тможет быть грубо оценено с помощью максимальной скорости внешнего

канала Ц^х:

^шах

2) Вычисление исходных параметров и теоретических зависимостей в соответствии с полученными выражениями.

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

4) Уточнение и решение задачи оптимизации в соответствии с приоритетами и ограничениями на пределы изменения параметров для заданной организации.

5) Принятие решения об эффективности системы по результатам расчета.

^ Начало ^

Сбор статистики

Вычисление Расчет Н(5-8) и у, (У) - 1 ■

Рассчитать

при > О

У

Рассчитать ^ по целевой функции

Система —У экономически / не оправдана

Рассчитать 5" = а^тах Н(3") при У, (.Г) >0

^ Настройка ~~У оптимальна / /

Выполнить оптимизацию

Изменить настройку

Расширить канал

<»_

^ Конец ^^^

Рисунок 5 - Схема алгоритма проверки эффективности применения системы кэширования

Практическая проверка работоспособности предложенных алгоритмов была проведена при определении настроек системы кэширования Межвузовского медиацентра г. Самары. Исходные данные для расчета выбраны из предположения, что параметры распределения запросов пользователей будут приблизительно равны параметрам, полученным для сети СГАУ, поскольку обе организации являются образовательными. В качестве исходных значений выбраны следующие: а = 0.792, рс =0.57, Ти =168. Оценка

максимальной производительности в этом случае дает величину #тах я 0,475. Входящая скорость была оценена исходя из максимальной скорости внешнего подключения: u,snt =(0.5^0.8)^=6 Мбит/с.

В качестве основного критерия оптимизации была выбрана величина чистой экономии. В дополнение были наложены ограничения на объем памяти системы. Объем памяти изменяется дискретно и должен быть кратен 150 Гбайт. Это ограничение связано с типом применяемых дисковых накопителей на сервере, предназначенном для установки системы кэширования. В результате численной оптимизации по этим критериям был выбран объем памяти для системы кэширования ММЦ, равный 600 Гб. При этом ожидаемое значение производительности равно 36%, период окупаемости составит 17 месяцев, а чистая экономия — 51 тысячу рублей в год. Зависимости скорости изменения чистой экономии от производительности и периода окупаемости от объема системы, полученные в результате расчетов, представлены на рис. 6.

N

\

О 0.1 0,2 0.3 0,4 0,5 Производительность. Я

я в

й 5 4

tj* ь ?

в

я и0

п .2

и « -Л 9

k № Й-6 К

а- -в

/

0 500 1000 1500 2000 2500 Объем памяти, S* Гб

120

О

V 96

А

т 72

X с. О 48

и С 5 24

с i

0

о

/

/

[/

К-- t

О 500 1000 1500 2000 Объем памяти, S" Гб

Рисунок б - Зависимость скорости изменения чистой экономия от производительности (слева), скорости изменения чистой экономии от объема памяти системы кэширования (в центре) и зависимость периода окупаемости системы кэширования от объема ее памяти (справа)

После установки системы кэширования ММЦ и по прошествии периода начального заполнения объема памяти системы и набора статистики, среднемесячная производительность системы составила 34,6%. Таким образом, относительная ошибка расчета составила 4,04%.

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

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

2) Алгоритм управления документами для каждого раздела выбирается независимо. Для вспомогательной части алгоритм основывается на времени хранения. Для ядра предлагается ввести метрическую функцию на основе распределения Зипфа, учитывающую популярность, время после последнего изменения документа и его размер.

3) Время хранения статистики в информационной части должно превышать время хранения популярных документов.

В заключении обобщены результаты проведенных исследований.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1) Проведен анализ особенностей функционирования системы кэширования Интернет-трафика и ее взаимодействия со смежными системами. Сформулированы критерии эффективности применения системы кэширования с точки зрения организации.

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

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

3) Проведена обширная экспериментальная проверка, включающая исследование реальной системы и ее имитационной модели, которая показала адекватность созданной математической модели. Относительная ошибка расчета производительности системы кэширования по полученным аналитическим зависимостям не превышает 5%. Разработана методика обработки экспериментальных данных и соответствующее программное обеспечение. Найдена зависимость между производительностью по количеству документов и производительностью по объему информации, позволяющая уточнить расчет значения чистой экономии.

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

В изданиях, рекомендуемых ВАК:

1 Долгих, Д.Г. Системы резервирования трафика. Аналитическая модель [Текст]/Д.Г. Долгих, A.M. Сухов //Телекоммуникации. - 2007. - № 3. - С. 8-11.

2 Долгих, Д.Г. Системы резервирования трафика. Архитектура и алгоритмы [Текст] / Д.Г. Долгих, A.M. Сухов // Телекоммуникации. - 2007. - № 4. - С. 24-27.

3 Долгих, Д.Г. Системы резервирования трафика. Экспериментальные данные и их обработка [Текст] / Д.Г. Долгих, A.M. Сухов // Телекоммуникации. - 2007. - № 4. -С. 22-24.

4 Долгих, Д.Г. Системы резервирования трафика. Эффект изменения документов в глобальной сети [Текст] / Д.Г. Долгих, A.M. Сухов // Телекоммуникации. -2007.-№5.-С. 29-31.

5 Dolgikh, D.G. Parameters of cache system based on a Zipf-like distribution [Текст] / D. G. Dolgikh, A. M. Sukhov // Computer Networks. - 2001. - № 37(6). - P. 711-716.

В других изданиях:

6 Грачев, В.Г. Опыт создания и эксплуатации каналов связи, основанных на технике ИКМ [Текст] / В.Г. Грачев, Д.Г. Долгих // Сборник докладов международного рабочего семинара "Цифровые сети в Среднем Поволжье". - Самара, 1998. - С. 61-63.

7 Долгих, Д.Г. Интегрированная система кэширования информации межвузовского медиацентра [Текст] / Д.Г. Долгих // Сборник докладов II международной научно-технической конференции «Информационные технологии в науке, образовании и производстве». - Орел, 2006. - С. 49-53.

8 Долгих, Д.Г. Интегрированная система кэширования информации межвузовского медиацентра г. Самары [Текст] / Д.Г. Долгих, Е.А. Симановский // Труды XIV Всероссийской научно-методической конференции «Телематика-2007». — СПб., 2007.-С. 60-65.

9 Долгих, Д.Г. Интегрированная система управления корпоративной сетью [Текст] / Д.Г. Долгих, В.Г. Грачев, B.C. Кузьмичев, Е.А. Симановский // Труды XI Всероссийской научно-методической конференции «Телематика-2004». - СПб., 2004. -С. 34-39.

10 Долгих, Д.Г. Оптимизация систем кэширования трафика [Текст] / Д.Г. Долгих, A.M. Сухов, Е.А. Симановский // Труды X Всероссийской научно-методической конференции «Телематика-2003». - СПб., 2003. - С. 29-32.

11 Долгих, Д.Г. Повышение эффективности внешних каналов [Текст] / Д.Г. Долгих, A.M. Сухов // VIII конференция представителей региональных научно-образовательных сетей "RELARN 2001": материалы конф. - Петрозаводск. - 2001. - С. 29-35.

12 Долгих, Д.Г. Системы резервирования трафика в Интернет [Электронный ресурс] / Д.Г. Долгих, A.M. Сухов // VI рабочее совещание по электронным публикациям "El-Pub2001". [Новосибирск, 2001]. URL: http://www.ict.tisc.ru/ws/elpub2001/1859/ (дата обращения: 14.03.2008).

13 Dolgikh, D.G. Cost benefit analysis [Текст] / D.G. Dolgikh, A.M. Sukhov, A.A. Shavaldin // Second Web Cache Managers Workshop, TERENA and DESIRE. - 2000. - P. 121-127.

14 Dolgikh, D.G. Parameters of Cache Systems based on Zipf-like Distribution [Текст] / D.G. Dolgikh, A.M. Sukhov // TERENA Networking Conference. - 2001. - P. 4243.

Подписано в печать 26.05.2009 г. Формат 60x48 1/16. Усл. печ. л. 1. Тираж 100 экз.

Отпечатано в Самарском государственном аэрокосмическом университете. 443086, г. Самара, Московское шоссе, 34

Введение.

ГЛАВА 1 ИСХОДНЫЕ ПОЛОЖЕНИЯ И ПОСТАНОВКА ЗАДАЧИ.

1.1 Общие сведения.

1.2 Критерии эффективности использования системы кэширования.

1.3 Анализ распределения запросов пользователей.

1.4 Подходы к анализу систем кэширования.

1.5 Взаимодействие пользователей с системой кэширования.

1.6 Данные системы кэширования.

1.7 Обобщенная конструкция системы кэширования.

1.8 Алгоритмы управления хранением документов.

1.9 Составляющие модели системы кэширования.

1.10 Выводы и результаты.

ГЛАВА 2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ СИСТЕМЫ КЭШИРОВАНИЯ.

2.1 Постановка задачи и исходные предположения.

2.2 Оценка производительности идеальной системы кэширования.

2.3 Специальные точки распределения Зипфа.

2.4 Оценка предельной производительности.

2.5 Учет влияния ограничения объема памяти и скорости внешнего канала.

2.6 Учет влияния обновления документов.

2.7 Критерий экономической эффективности.

2.8 Выводы и результаты.

ГЛАВА 3 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ СИСТЕМЫ КЭШИРОВАНИЯ.

3.1 Постановка эксперимента на реальной системе.

3.2 Технология проведения эксперимента.

3.3 Программы обработки данных.

3.4 Результаты эксперимента на реальной системе и их анализ.

3.5 Проверка теоретических зависимостей на имитационной модели системы.

3.6 Выводы и результаты.

ГЛАВА 4 АЛГОРИТМЫ И МЕТОДИКИ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ СИСТЕМЫ КЭШИРОВАНИЯ.

4.1 Алгоритм определения оптимальных настроек.

4.2 Алгоритм проверки эффективности применения системы кэширования.

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

4.4 Определение настроек системы кэширования для ММЦ.

4.5 Выводы и результаты.

Компьютерная сеть и подключение к сети Интернет являются непременным атрибутом любого современного предприятия, организации, научного или образовательного учреждения. Развитие современных технологий, таких как дистанционное обучение, информационные порталы, поисковые системы, электронная коммерция и других, привело к многократному росту требований к скорости получения данных из сети Интернет. Возможны несколько вариантов увеличения скорости получения запрашиваемых данных. Наиболее часто встречаются два из них: увеличение пропускной способности внешнего канала связи и оптимизация потока информации, запрашиваемой из сети Интернет. Увеличение пропускной способности внешнего канала связи является наиболее простым способом, но и наиболее затратным. К сожалению, данный способ не всегда приводит к желаемым результатам из-за сложности и неоднородности сети Интернет, а также из-за особенностей построения сети связи поставщиков услуг Интернет (ПУИ). Оптимизация потока информации является более сложным способом, чем увеличение скорости внешнего канала, однако это потенциально более выгодно для организации или предприятия [8, 14, 70]. Оптимизация потока информации требует понимания особенностей, связанных с формированием, запросами и передачей этой информации.

Исследования потоков информации во внешнем канале связи, то есть в канале, который связывает сеть организации с сетью Интернет, показывают [4, 5, 12, 13, 44, 47, 50, 51, 58, 64, 65, 84, 85, 102], что около 85% приходится на данные, передаваемые по протоколам HTTP (Hyper Text Transfer Protocol - протокол передачи гипертекста) [42] и FTP (File Transfer Protocol — протокол передачи файлов) [90]. Они являются основными протоколами для передачи веб-страниц. Оба протокола основываются на протоколе TCP (Transmission Control Protocol - протокол управления передачей [18]), то есть они осуществляют гарантированную доставку информации с сохранением порядка следования пакетов. Общая доля 5 информации, передаваемой по этим протоколам, относительно всего объема информации, запрашиваемой из глобальной сети, будет определять принципиальную границу эффективности применения системы кэширования с точки зрения уменьшения общего количества передаваемой информации через внешний канал. Исследования показывают, что с течением времени запросы к веб-страницам повторяются [12, 13, 32, 34, 39, 40, 54, 55, 58, 83], при этом около 60% от количества запросов производится к документам, которые не изменяются или изменяются редко [12, 13, 21, 33, 34, 43, 52, 58, 76, 89, 92]. Это делает возможным локальное сохранение таких документов при их первом запросе для последующей передачи при последующих запросах. Такой процесс называется кэшированием, а системы, которые реализуют кэширование, называют системами кэширования трафика. Кэширование позволяет повысить скорость передачи данных локальным пользователям без увеличения пропускной способности внешнего канала организации за счет передачи части информации из локального хранилища. Протокол HTTP и язык разметки веб-страниц HTML (Hyper Text Markup Language - язык разметки гипертекста) содержат возможности, облегчающие кэширование. Протокол HTTP позволяет определить время последнего изменения веб-страницы без передачи самой страницы, а язык HTML содержит возможности указания того, что вебстраница может быть сохранена в системе кэширования, а также значение времени, по истечению которого страница должна быть заново загружена с сервера. Эти возможности помогают определить моменты, когда информация в системе кэширования устарела и должна быть запрошена заново. Последние исследования демонстрируют некоторое уменьшение доли информации, передаваемой по протоколам HTTP и FTP, в пользу данных, передаваемых в рамках, так называемых, пиринговых систем (Реег-То-Peer). Несмотря на то, что готовых систем кэширования для таких потоков данных пока нет, в ряде работ [78, 94, 101], показано, что к ним также можно применять кэширование.

Системы кэширования широко применяются при организации доступа к сети Интернет. Нередко это делается без ведома пользователей. Поставщики услуг Интернет предлагают специальный тип подключения — подключение пользователей только через систему кэширования или только к системе кэширования. Некоммерческие организации также часто используют системы кэширования для увеличения скорости передачи информации конечным пользователям при неизменной скорости внешнего подключения. В настоящее время построено множество систем, позволяющих осуществлять кэширование [22, 24, 80, 97]. В сетях некоммерческих организаций ' наибольшее распространение получили программные решения, основанные на бесплатно распространяемом программном обеспечении. Одним из таких решений является система Squid. Коммерческие системы кэширования предлагают такие известные фирмы как CISCO Systems, Alcatel-Lucent, IBM и другие. Существуют варианты систем, которые представляют собой программные, программно-аппаратные или чисто аппаратные комплексы. Кроме того, в настоящее время получили широкое распространение распределенные системы, предназначенные для ускорения доставки информации пользователям, устанавливаемые владельцами веб-серверов. Такие системы называются сетями распределения контента (Content Distribution Network — CDN). Таким сетям уделяется особое внимание на современных научных конференциях, посвященных кэшированию [71, 72, 103]. Принципы их построения идентичны принципам построения систем кэширования, что позволяет надеяться, что зависимости и закономерности, верные для системы кэширования, будут применимы и для сетей распределения контента.

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

На данный момент существуют два основных подхода, которые описывают взаимосвязь параметров системы кэширования. Первый из них основан на экспериментальных результатах, полученных для частных случаев [32, 35, 41, 98]. Этот подход дает рекомендации по настройке конкретных системы кэширования, но не объясняет причин наблюдаемого поведения. Кроме того, подход требует наличие экспериментальной информации о настраиваемой системе, которая не всегда присутствует, а ее получение занимает продолжительной время. Второй подход основан на построении аналитической модели системы кэширования [45, 46, 105]. К сожалению, существующие модели дают только качественные зависимости параметров системы. Такие модели не предлагают решений, которые позволили бы оценить границы изменения производительности системы кэширования, выявить зависимости между параметрами системы, связать параметры системы кэширования с параметрами, описывающими среду ее использования, то есть дать рекомендации по настройке системы кэширования или оценить эффективность уже работающей системы. С этой точки зрения, поиск новых подходов к анализу систем кэширования, расчету и оптимизации ее параметров является актуальной задачей.

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

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

1) Анализ принципов работы, взаимосвязей и параметров, влияющих на функционирование системы кэширования и определение критериев ее эффективности.

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

3) Экспериментальная проверка адекватности созданной математической модели.

4) Разработка алгоритмов выбора оптимальных параметров системы кэширования и проверки эффективности ее работы.

Объектом исследования является одиночная система кэширования запросов пользователей в сети Интернет, с ограниченными ресурсами и находящаяся в локальной вычислительной сети (ЛВС) организации.

Предметом исследования являются зависимости между параметрами системы кэширования, определяющие ее эффективность.

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

Научная новизна заключается в следующем:

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

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

3) Впервые получена зависимость производительности системы кэширования от объема ее памяти, скорости внешнего канала и показателя распределения Зипфа, и предложен способ учета влияния обновлений документов в Интернет на производительность системы путем изменения значения показателя распределения Зипфа.

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

Практическая ценность и реализация результатов работы.

1) Создано программное обеспечение, позволяющее проводить детальное исследование запросов пользователей сети, анализ работы системы кэширования и расчет всех параметров, входящих в модель.

2) Предложенные алгоритмы позволяют оптимизировать и контролировать значения параметров системы кэширования, а также рассчитывать экономический эффект от ее использования.

3) Полученные теоретические результаты и программные продукты были использованы при начальной установке и используются для контроля работы систем кэширования трафика локальной сети Межвузовского медиацентра г. Самары (ММЦ), Самарского государственного аэрокосмического университета имени академика С.П.Королева (СГАУ) и коммерческого ПУИ ЗАО

Самара Телеком», о чем получены соответствующие акты внедрения, представленные в приложении А.

На защиту выносятся:

1) Математическая модель системы кэширования, учитывающая комплекс факторов, включающий характер распределения запросов пользователей, ограничения объема памяти системы кэширования, влияние обновлений документов в сети Интернет, конечную скорость передачи внешнего канала связи и экономическую эффективность применения системы.

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

3) Способ учета влияния скорости внешнего канала и обновления документов в Интернет на эффективность системы кэширования.

4) Алгоритмы определения оптимальных настроек системы кэширования и проверки эффективности ее применения.

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

• Цифровые сети в Среднем Поволжье. Международный рабочий семинар, Самара, СГАУ, 1998.

• DESIRE-II. Второй международный семинар администраторов систем кэширования, Будапешт, 2000.

• Выделение передовых сетей и услуг. Ежегодная международная конференция союза научно-образовательных сетей «TERENA», Анталия, 2001.

• RELARN-2001. Восьмая всероссийская конференция представителей региональных научно-образовательных сетей, Санкт-Петербург - Петрозаводск, 2001.

• Е1-РиЬ2001. VI рабочее совещание по электронным публикациям, Новосибирск, 2001.

• Телематика 2003. X Всероссийская научно-методическая конференция, Санкт-Петербург, 2003.

• Современные сетевые технологии. Научный семинар МГУ, 30.03.2004, Москва, 2004.

• Телематика 2004. XI Всероссийская научно-методическая конференция, Санкт-Петербург, 2004.

• Информационные технологии в науке, образовании и производстве. II Международная научно-техническая конференция, Орел, 2006.

• Телематика 2007. XIV Всероссийская научно-методическая конференция, Санкт-Петербург, 2007.

Публикации. Всего по теме диссертации опубликовано 14 печатных работ, список которых приведен в списке использованных источников, из них 5 работ в изданиях, рекомендуемых ВАК, в том числе одна в зарубежном англоязычном рецензируемом журнале.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников из 107 наименований и приложений. Работа изложена на 137 страницах, содержит 34 рисунка и 4 таблицы.

Основные результаты диссертационной работы заключаются в следующем:

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

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

3) Проведена обширная экспериментальная проверка, включающая исследование реальной системы и ее имитационной модели, которая показала адекватность созданной математической модели. Относительная ошибка расчета производительности системы кэширования по полученным аналитическим зависимостям не превышает 5%. Разработана методика обработки экспериментальных данных и соответствующее программное обеспечение. Найдена зависимость между производительностью по количеству документов и производительностью по объему информации, позволяющая уточнить расчет значения чистой экономии.

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

Заключение

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

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

1. Антонов, А. В. Системный анализ. Учеб. для вузов Текст. / А. В. Антонов. М.: Высшая школа. - 2004. - 454 с.

2. Бронштейн, И.Н. Справочник по математике для инженеров и учащихся ВТУЗОВ Текст. / И.Н. Бронштейн, К.А. Семендяев. М.: Наука. - 1980.-976 с.

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

4. Грачев, В.Г. Исследование структуры трафика корпоративной сети Самарского государственного аэрокосмического университета Текст. / В.Г. Грачев, Е.А. Симановский // Телекоммуникации и информатизация образования. 2002. - №2(9). - С. 76-84.

5. Грачев, В.Г. Операционная система Linux Текст. / В.Г. Грачев, Д.Г. Долгих, A.A. Шавалдин // Сборник докладов международного рабочего семинара "Цифровые сети в Среднем Поволжье". Самара, 1998.-С. 24-27.

6. Грачев, В.Г. Опыт создания и эксплуатации каналов связи, основанных на технике ИКМ Текст. / В.Г. Грачев, Д.Г. Долгих // Сборник докладов международного рабочего семинара "Цифровые сети в Среднем Поволжье". Самара, 1998. - С. 61-63.

7. Долгих, Д.Г. Интегрированная система кэширования информации межвузовского медиацентра Текст. / Д.Г. Долгих // Сборник докладов II международной научно-технической конференции

8. Информационные технологии в науке, образовании и производстве». -Орел, 2006.-С. 49-53.

9. Долгих, Д.Г. Интегрированная система кэширования информации межвузовского медиацентра г. Самары Текст. / Д.Г. Долгих, Е.А. Симановский // Труды XIV Всероссийской научно-методической конференции «Телематика-2007». СПб., 2007. - С. 60-65.

10. Долгих, Д.Г. Интегрированная система управления корпоративной сетью Текст. / Д.Г. Долгих, В.Г. Грачев, B.C. Кузьмичев, Е.А. Симановский // Труды XI Всероссийской научно-методической конференции «Телематика-2004». СПб., 2004. - С. 34-39.

11. Долгих, Д.Г. Оптимизация систем кэширования трафика Текст. / Д.Г. Долгих, A.M. Сухов, Е.А. Симановский // Труды X Всероссийской научно-методической конференции «Телематика-2003». СПб., 2003. - С. 29-32.

12. Долгих, Д.Г. Повышение эффективности внешних каналов Текст. / Д.Г. Долгих, A.M. Сухов // VIII конференция представителей региональных научно-образовательных сетей "RELARN 2001": материалы конф. Петрозаводск. - 2001. - С. 29-35.

13. Долгих, Д.Г. Системы резервирования трафика. Аналитическая модель Текст. / Д.Г. Долгих, A.M. Сухов // Телекоммуникации. -2007.-№3.-С. 8-11.

14. Долгих, Д.Г. Системы резервирования трафика. Архитектура и алгоритмы Текст. / Д.Г. Долгих, A.M. Сухов // Телекоммуникации. -2007. № 4. - С. 24-27.

15. Долгих, Д.Г. Системы резервирования трафика. Экспериментальные данные и их обработка Текст. / Д.Г. Долгих, A.M. Сухов // Телекоммуникации. 2007. - № 4. - С. 22-24.

16. Долгих, Д.Г. Системы резервирования трафика. Эффект изменения документов в глобальной сети Текст. / Д.Г. Долгих, A.M. Сухов // Телекоммуникации. 2007. - № 5. - С. 29-31.

17. Камер, Д. Сети TCP/IP. Принципы, протоколы и структура Текст. / Д. Камер.-4-е изд. М.: Вильяме, 2003. - Т 1. - 880 с.

18. Клейнрок, JI. Вычислительные системы с очередями Текст. / JI. Клейнрок. М.: Мир. - 1979. - 600 с.

19. Клейнрок, JI. Теория массового обслуживания Текст. / JI. Клейнрок. М.: Машиностроение. - 1979. - 432 с.

20. Крашаков, С. А. Об универсальности рангового распределения популярности вэб-серверов Текст. / С.А. Крашаков, А.Б. Теслюк, Л.Н. Щур // Вестник РФФИ. 2004. - №1(35). - С. 46-66.

21. Крашаков, С.А. Оптимизация интернет-трафика с помощью сети кеширующих серверов Текст. / С.А. Крашаков, JI.H. Щур // Информационное общество. -2001. № 5. - С. 10-13.

22. Ларичев, О. И. Теория и методы принятия решений: Учебник Текст. / О. И. Ларичев. М.: Логос. - 2000. - 296 с.

23. Прищепа, В.В. Эффективный алгоритм кэширования в сети Интернет Текст. / В.В. Прищепа, Л.Б. Соколинский // Труды Всероссийской научной конференции «Научный сервис в сети Интернет». 2003. - С. 176-178.

24. Таненбаум, Э. Современные операционные системы Текст. / Э. Таненбаум. 2-е изд. - СПб.: Питер, 2002. - 1040 с.

25. Олифер, В.Г. Компьютерные сети. Принципы, технологии, протоколы Текст. / В. Г. Олифер, Н. А. Олифер. СПб.: Питер, 2002. - 672 с.

26. Уолл, JI. Программирование на Perl Текст. / JI. Уолл, Т. Кристиансен, Д. Орвант; перевод с англ. СПб.: Символ-Плюс, 2002. - 1152 с.

27. Хаггет, П. География: синтез современных знаний Текст. / П. Хаггет. М.: Прогресс. - 1979. - 684 с.

28. Хайтун, С. Д. Наукометрия: состояние и перспективы Текст. / С. Д. Хайтун. М.: Наука. - 1983. - 345 с.

29. Яблонский, А. И. Стохастические модели научной деятельности Текст. / А. И. Яблонский // Системные исследования. Ежегодник. -М.: Наука. 1975. - С.5-43.

30. Almeida, V. Analyzing the behavior of a proxy server in the light of regional and cultural issues Текст. / V. Almeida, M. Cesirio, R. Canado, W. Junior, C. Murta // 3rd International WWW Caching Workshop. -1998.-P. 271-276.

31. Almeida, J. Characterization of user access to streaming media files Текст. / J. Almeida, J. Krueger, M. Vernon // ACM SIGMETRICS/Performance 2001. -2001. P. 340-341.

32. Almeida, V. Characterizing reference locality in the WWW Текст. / V. Almeida, A. Bestavros, M. Crovella, A. De Oliveira // IEEE International Conference in Parallel and Distributed Information Systems. 1996. - P. 184-190.

33. Almeida, J. Measuring Proxy Performance with the Wisconsin Proxy Benchmark Текст. / J. Almeida, Cao. Pei // Computer Networks. 1998. -№ 30(22-23). - P. 2179-2192.

34. Arlitt, M. Evaluating content management techniques for Web proxy caches Текст. / M. Arlitt, L. Cherkasova, J. Dilley, R. Friedrich, T. Jin //

35. ACM SIGMETRICS Performance Evaluation Review. 2000. - Vol. 27. -Issue4.-P.3- 11.

36. Arlitt, M. Performance Evaluation of Web Proxy Cache Replacement Policies Текст. / M. Arlitt, R. Friedrich, T. Jin // Computer Performance Evaluation (Tools). 1998. - P. 193-206.

37. Arlitt, M. Workload Characterization of a Web Proxy in a Cable Modem Environment Текст. / M. Arlitt, R. Friedrich, T. Jin // Performance Evaluation Review. 1999. - P. 79-84.

38. Barford, P. Changes in Web Client Access Patterns: Characteristics and Caching Implications Текст. / P. Barford, A. Bestavros, A. Bradley, M. Crovella // Special Issue on Characterization and Performance Evaluation. 1999.-Vol. 2.-P. 15-28.

39. Barford, P. Generating Representative Web Workloads for Network and Server Performance Evaluation Текст. / P. Barford P, M. Crovella // ACM SIGMETRICS '98. 1998. - P. 151-160.

40. Bent, L. Whole Page Performance Текст. / L. Bent, G. Voelker // 7th International Workshop on Web Content Caching and Distribution (WCW). 2002. - P. 211-218.

41. Berners-Lee, T. Hypertext Transfer Protocol HTTP/1.0 Электронный ресурс. / Т. Berners-Lee, R. Fielding, H. Frystyk. [1996]. URL: http://www.ietf.org/rfc/rfcl945.txt (дата обращения: 03.02.2008).

42. Bilchev, G. Modelling HTTP Traffic Generated by Community of Users Текст. / G. Bilchev, I. W. Marshall, S. Olafsson, C. Roadknight // HPCN Europe 1999. 1999. - P. 1266-1269.

43. Braun, H. Network analysis issues for a public Internet Текст. / H. Braun, K. Claffy // Public access to the Internet. 1995. - P. 350-377.

44. Breslau, L. On the Implications of Zipf s Law for Web Caching Текст. / L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker // 3rd International WWW Caching Workshop Manchester. 1998. - P. 91-99.

45. Breslau, L. Web Caching and Zipf-like Distribution: Evidence and Implications Текст. / L. Breslau, P. Cao, L. Fan, G. Phillips, S. Shenker // IEEE Infocom. 1999. - Vol. 20. - № 5. - P. 126-134.

46. Brownlee, N. Understanding Internet Traffic Streams: Dragonflies and Tortoises Текст. / N. Brownlee // IEEE Communications Magazine. -2002.-P. 33-41.

47. Cao, P. Cost-aware WWW-proxy caching algoritms Текст. / P. Cao, S. Irani // Proceedings of the USENIX Symposium on Internet technology and Systems. 1997. - P. 193-206.

48. Cherkasova, L. Improving WWWProxies Performance with Greedy-Dual-Size-Frequency Caching Policy Текст. / L. Cherkasova // Technical Report HPL-98-69R1. 1998. - P. 68-75.

49. Claffy, K. Long-term traffic aspects of the NSFNET Электронный ресурс. / К. Claffy, H.-W. Braun, G. Polyzos // Proceedings of INET'93. [1993]. URL: http://www.caida.org/publications/papers/1993/lta/ (дата обращения: 30.07.2004).

50. Claffy, К. Recent Traffic Measurements from an Internet backbone Электронный ресурс. / К. Claffy, G. Miller, K. Thompson [1998]. URL: http://www.caida.0rg/publicati0ns/papers/l998/Inet98/ (дата обращения: 12.06.2004).

51. Crovella, M. Explaining World Wide Web Traffic Self-Similarity Текст. / M. Crovella, A. Bestavros // Technical Report TR-95-015. Boston University Computer Science Department. 1995. - P. 185-194.

52. Crovella, M. Heavy-Tailed Probability Distributions in the World Wide Web Текст. / M. E. Crovella, M. Taqqu, A. Bestavros // A Practical Guide To Heavy Tails. № 1. - New York. - P. 3-26.

53. Crovella, M. Self-Similarity in World Wide Web Traffic: Evidence and Possible Causes Текст. / M. Crovella, A. Bestavros // IEEE/ACM, Transactions on Networking. 1997. - №5(6). - P. 835-846.

54. Cunha, С. Characteristics of WWW Client-based Traces Текст. / С. Cunha, A. Bestavros, M. Crovella // Technical Report TR-95-010. Boston University Computer Science Department. 1995. - P. 87-93.

55. Development of a European Service for Information on Research and Education (DESIRE) Электронный ресурс. // 1998. URL: http://www.desire.org (дата обращения: 16.04.2008).

56. Dilley, J. Improving Proxy Cache Performance: Analysis of Three Replacement Policies Текст. / J. Dilley, M. Arlitt // IEEE Internet Computing. 1999. - № 3(6). - P. 44-50.

57. Dolgikh, D.G. Cost benefit analysis Текст. / D.G. Dolgikh, A.M. Sukhov, A.A. Shavaldin // Second Web Cache Managers Workshop, TERENA and DESIRE. 2000. - P. 121-127.

58. Dolgikh, D.G. Parameters of cache system based on a Zipf-like distribution Текст. / D. G. Dolgikh, A. M. Sukhov // Computer Networks. 2001. -№37(6).-P. 711-716.

59. Dolgikh, D.G. Parameters of Cache Systems based on Zipf-like Distribution Текст. / D.G. Dolgikh, A.M. Sukhov // TERENA Networking Conference. 2001. - P. 42-43.

60. Duska, B. The Measured Access Characteristics of World-Wide Web Client Proxy Caches Текст. / В. Duska, D. Marwood, M. Feeley // Proceedings of USENIX Symposium of Internet Technologies and Systems (USITS). 1997. - P. 23-35.

61. Feldmann, A. Performance of Web Proxy Caching in Heterogeneous Bandwidth Environments Текст. / A. Feldmann, R. Caceres, F. Doughs, G. Glass, M. Rabinovich // INFOCOM. 1999. - P. 107-116.

62. Fielding, R. Hypertext Transfer Protocol ~ HTTP/1.1 Электронный ресурс. / R. Fielding, J. Gettys, J. Mogul, H. Frystyk, L. Masinter, P. Leach, T. Berners-Lee. [1999]. URL: http://www.ietf.org/rfc/rfc2616.txt (дата обращения: 12.03.08).

63. Gadde, S. Reduce, Reuse, Recycle: An Approach to Building Large Internet Caches Текст. / S. Gadde, M. Rabinovich, J. Chase // Workshop on Hot Topics in Operating Systems. 1997. - P. 93-98.

64. Gadde, S. Web caching and content distribution: a view from the interior Текст. / S. Gadde, J. Chase, M. Rabinovich // Computer Communications. 2001. - № 24(2). - P. 222-231.

65. Glassman, S. A Caching Relay for the World Wide Web Текст. / S. Glassman // Computer Networks and ISDN Systems. 1994. - № 27(2). -P. 165-173.

66. Gribble, S. System Design Issues for Internet Middleware Services Текст. / S. Gribble, E. Brewer // Deductions from a Large Client Trace: Proceedings of USENIX Symposium of Internet Technologies and Systems (USITS). 1997. - P. 207-218.

67. Hannigan, B. Why caching matters Текст. / В. Hannigan, C.D. Howe, S. Chan, T. Buss // Technical Report, Forrester Research Inc. 1997. — P. 176-182.

68. Internet Software Consortium Электронный ресурс. [2001]. URL: http://www.isc.org (дата обращения: 26.06.04).

69. Internet Web Cache Workshop Электронный ресурс. [1996]. URL: http://www.iwcw.org (дата обращения: 26.06.04).

70. Jiang, Y. Web Prefetching: Costs, Benefits and Performance Текст. / Y. Jiang, M. Wu, W. Shu // 7th International Workshop on Web Caching and Content Distribution. 2002. - P. 345-352.

71. Jin, S. GreedyDual* Web caching algorithm: exploiting the two sources of temporal locality in Web request streams Текст. / S. Jin, A. Bestabros // Computer Communications. 2001. - № 24(2). - P. 174-183.

72. Kelly, T. Optimal Web cache sizing: scalable method for exact solutions Текст. / Т. Kelly, D. Reeves // Computer Communications. 2001. - № 24(2). - P. 163-173.

73. Krashakov, S.A. On the universality of rank distributions of website popularity Текст. / S.A. Krashakov, A.B. Tesluk, L.N. Shchur // Computer Networks. 2006. - No 11. - P. 1769-1780.

74. Lee, K. Workload Requirements for a Very High-Capacity Proxy Cache Design Текст. / К. Lee, D. Tomlinson // The 4th International Web Caching Workshop. 1999. - P. 237-243.

75. Leibowitz, N. Are File Swapping Networks Cacheable? Characterizing P2P Traffic Текст. / N. Leibowitz, A. Bergman, R. Ben-Shaul, A. Shavit // 7th International Workshop on Web Content Caching and Distribution (WCW). 2002. - P. 84-88.

76. Leland, W. E. On the self-similar nature of ethernet traffic (extended version) Текст. / W. E. Leland, M. S. Taqqu, W. Willinger, D. V. Wilson // IEEE/ACM Transactions of Networking. № 2(1). - 1993. - P. 1-15.

77. Luotonen, A. CERN HTTPD public domain full featured hypertext/proxy server with caching Текст. / A. Luotonen, H. Frystyk, N. Berners-Lee. -1994. URL: http://info.cern.ch/hypertext/WWW/Daemon/Status.html (дата обращения: 20.06.04).

78. Maltzahn, С. Performance Issues of Enterprise Level Web Proxies Текст. / С. Maltzahn, К. Richardson // Proceedings of the 1997 ACM SIGMETRICS Conference on the Measurement and Modeling of Computer Systems. 1997. - P. 13-23.

79. Mandelbrot, В. В. Long-Run Linearity, Locally Gaussian Processes, H-Spectra and Infinite Variances Текст. / В. В. Mandelbrot // International Economic Review. № 10. - 1969. - P. 82-113.

80. Marshall, I. W. Linking Cache Performance to User Behaviour Текст. / I. W. Marshall, C. Roadknight // Computer Networks. 1998. - № 30(22-23).-P. 2123-2130.

81. MRTG Multi Router Traffic Grapher Электронный ресурс. [2000]. URL: http://people.ee.ethz.ch/~oetiker/webtools/mrtg (дата обращения: 18.06.04).

82. National Laboratory for Applied Network Research (NLANR) Электронный ресурс. [2006]. URL: http://www.nlanr.net/ (дата обращения: 08.04.08).

83. Nishikawa, N. Memory-based architecture for distributed WWW caching proxy Текст. / N. Nishikawa, T. Hosokawa, Ya. Mori, K. Yoshidab, H. Tsujia // The 7th WWW Conference. 1998. - P. 118-126.

84. Park, K. On the Effect of Traffic Self-similarity on Network Performance Текст. / К. Park, G. Kim, M. Crovella // Proceedings of the SPIE International Conference on Performance and Control of Network Systems.-1997.-P. 32-38.

85. Postel, J. RFC959 File Transfer Protocol (FTP) Электронный ресурс. / J. Postel, J. Reynolds. - 1985. URL: http://www.faqs.org/rfcs/rfc959.html (дата обращения: 17.03.08).

86. Postel, J. RFC793 Transmission Control Protocol. - Электронный ресурс. 1981. URL: http://www.faqs.org/rfcs/rfc793.html (дата обращения: 17.03.08).

87. Rabinovich, M. Not all Hits are Created Equal: Cooperative Proxy Caching Over a Wide-Area Network Текст. / M. Rabinovich, J. Chase, S. Gadde // Computer Networks. 1998. - № 30(22-23). - P. 2253-2259.

88. Raggett, D. HTML 4.01 Specification. Электронный ресурс. 1999. URL: http://www.w3.org/TR/html4 (дата обращения: 02.04.08).

89. Rizzo, L. Replacement policies for a proxy cache Текст. / L. Rizzo, L. Vicisano // IEEE/ACM Transactions on Networking. 2000. - Vol. 8(2). -P. 158-170.

90. Roadknight, C. Variations in Cache Behavior Текст. / С. Roadknight, I. W. Marshall // Computer Networks. 1998. - № 30(1-7). - P. 733-735.

91. Saraiya, A. Measuring Network Cache Performance Текст. / A. Saraiya, T. Vasudevan // The 4th International Web Caching Workshop. 1999. -P. 102-110.

92. Squid 2.4 Configuration Manual Электронный ресурс. [2002]. URL: http://squid.visolve.com/squid24sl (дата обращения: 22.05.08).

93. Squid: Optimising Web Delivery Электронный ресурс. [2009]. URL: http://www.squid-cache.org (дата обращения: 29.01.09).

94. Sripanidculchai, К. The popularity of Gnutella queries and its implications on scalability. Электронный ресурс. 2001. URL: http://www-2.cs.cmu.edU/.kunwadee/research/p2p/gnutella.html (дата обращения: 18.04.04).

95. Thompson, К. Wide area Internet traffic patterns and characteristics Текст. / К. Thompson, G. Miller, R. Wilder // IEEE Network. 1997. -Vol. 11.-P. 387-399.

96. WCW 2005 Technical Program Электронный ресурс. [2005]. URL: http://2005.iwcw.org/pprogram.html (дата обращения: 30.09.05).

97. Williams, S. Removal Policies in Network Caches for World-Wide Web Documents Текст. / S. Williams, M. Abrams, C. Standridge, G. Abdulla, E. Fox // Proceedings on ACM SIGCOMM '96. 1996. - P. 293305.

98. Wolman, A. On the scale and performance of cooperative Web proxy caching Текст. / A. Wolman, G. Voelker, N. Sharma, N. Cardwell, A. Karlin, H. Levy // Operating Systems Review. 1999. - № 34(5). - P. 16-31.

99. Zipf, G.K. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology Текст. / G.K. Zipf. Cambridge, MA: Addison-Wesley, 1949. - 573 p.

100. Zipf, G.K. Relativity frequency as a determinant of phonetic change Текст. / G.K. Zipf; Reprinted from the Harvard Studies in Classical Philology, Vol. XL, 1929. 95 p.

101. Акты внедрения результатов диссертационной работы

102. Федеральное агентство по образованию

103. Государственное образовательное учреждение высшего профессионального образования

104. Закрытое акционерное общество «Самара Телеком» рассмотрело теоретические и практические результаты исследований, представленных в диссертационной работе Д. Г. Долгих «Метод расчета и оптимизации параметров системы кэширования Интернет-графика».

105. Программа для построения зависимости производительности системы кэширования от ее относительного размера и показателя распределения

106. Зипфа для пакета Mathematika 5.

107. Content-type: application/mathematica **************

108. CreatedBy='Mathematica 5.0'

109. Mathematica-Compatible Notebook

110. Notebook reader applications are available free of charge from

111. Wolfram Research. ***********************************************

112. NotebookFileLineBreakTest NotebookFileLineBreakTest*)

113. NotebookOptionsPosition 193828, 3567.*)

114. NotebookOutlinePosition 194473, 3589.*)

115. CellTagsIndexPosition 194429, 3585.*)1. WindowFrame->Normal*)1. Notebook{ Cell[BoxData[

116. H\max := 2\*\(\((\Alpha. 1)\)/\[Alpha]\)*p\c\)], \ "Input"],1. CellBoxData[ \(Hfunc :=

117. H\max*\((\(\((1 H)\)*\Tau.\)\/\(\ \((1 - \[Alpha])\)*p\c*T\u\))\)\A\ \(1 - \[Alpha]\)\)], "Input"],1. CellCellGroupData[{1. CellBoxData[

118. HValueFunc = FindRootH \[Equal. Hfunc, \ {H, \ 0.1}]\)], \ "Input"],1. CellBoxData[

119. FindRootH \[Equal. Hfunc, {H, 0.1'}]\)], "Output"] }, Open ]],1. CellBoxData [

120. Alpha. := 0.8\)], "Input"],1. CellBoxData[p\c := 0.6\)., "Input"],1. CellBoxData[1. T\u 168\)., "Input"],1. CellCellGroupData[{1. Cell BoxData[ \ (Plot3D[

121. H /. HValueFunc, \ {\Tau., \ 0.1, \ 0.9}, \

122. AxesLabel \Rule. {"\<\[Tau]\>", \ Viewpoint -> {1.457, \ \(-2.917\),60}, \ {\Alpha., \ 0.4,\

123. Alpha.\>",\ "\<H\>"},\ \ 0.906}]\)], "Input"],

124. End of Mathematica Notebook file. **********************************************

125. Программа построения распределения запросов пользователей в зависимости от их популярности для протокольных файлов системыкэширования Squidusr/bin/perl -w1. Использование:cat access.log | finddistribution.pl filedistr.

126. Вспомогательная переменная для разбора строк my $foo = "";

127. Строка протокольного файла my $line = "";

128. Переменные сохранения статистикиmy $statnblines =0; # общее количество строк my $statK = 0; ту $statM = 0; ту $statL = 0;ту %statrequests = (); # Хеш-массив для хранения статистикихеш-ключ адрес документа (URL)значение количество запросов

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

130. Переменные для вывода my $outurl = ""; # адресту $outnb =0; # количество запросовmy $filetowrite = ""; # имя файла для вывода распределения ту $iswritetofile =0; # булевый флаг записи в файл

131. Вывести сообщение о завершении работыprint "\nFinished.\n"; #=============================================================

132. Экспериментальные распределения запросов пользователей1 10 100 1000 10000 100000 1в*0061. Рейтинг документе

133. Рис. 1 Рейтинговое распределение для интервала с объемом памяти 0.41 Гб1 ю юо 1ооо юооо юоооо 1е-юое1. Рейтинг документа

134. Рис. 2 Рейтинговое распределение для интервала с объемом памяти 1.00 Гб1 ю к» 1000 юооо юоооо 1а->-ооб1. Рейтинг документа

135. Рис. 3 Рейтинговое распределение для интервала с объемом памяти 1.90 Гб1 10 100 1000 10000 100000 1е"-0061. Реитинг документа

136. Рис. 4 Рейтинговое распределение для интервала с объемом памяти 3.25 Гб