Метод расчета и оптимизации параметров системы кэширования Интернет-трафика тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Долгих, Дмитрий Геннадьевич

• Долгих, Дмитрий Геннадьевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Долгих, Дмитрий Геннадьевич

Введение.

ГЛАВА 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) На основе теоретических и практических результатов предложены алгоритмы определения оптимальных настроек системы и проверки эффективности ее применения. Кроме того, предложены архитектурные изменения принципа организации системы кэширования и новые алгоритмы управления документами, учитывающие характер распределения запросов пользователей, эффект от обновления документов в Интернет и размер документов. Проведена проверка работы алгоритма определения оптимальных настроек на примере системы кэширования межвузовского медиацентра г. Самары.

Заключение

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

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

Список литературы диссертационного исследования кандидат технических наук Долгих, Дмитрий Геннадьевич, 2009 год

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 Гб