Анализ распределений времени поиска web-серверов

Задача адекватного моделирования процессов функционирования телекоммуникационных систем была и остается одной из приоритетных. Существующие подходы могут быть разделены на два больших класса: статистический анализ результатов измерений и построение аналитических моделей обслуживания. Предлагаемая работа, которую можно отнести ко второму типу, опирается на современное понимание фрактальной структуры телетрафика. При этом в статье нагрузка телекоммуникационной сети рассматривается с точки зрения клиента с учетом результатов статистических наблюдений. Анализ нагрузки on-line телекоммуникационной системы. Рассмотрим удаленного пользователя некоторой распределенной телекоммуникационной системы. Примерами таких систем являются образовательные системы, телемедицина, мониторинг различных параметров. Пользователи создают определенную нагрузку, которая в процессе коммутации является частью нагрузки общих сетей и подчиняется законам сетевого взаимодействия. В то же время система связи должна всего лишь удовлетворить запрос клиента с приемлемым качеством. В дальнейшем обсуждении этот момент будет отправным. Нагрузку сети можно описывать на нескольких уровнях. На верхнем описание нагрузки происходит с точки зрения пользователя. Нагрузка на web-сервере — это последовательность переходов между серверами, по порталу, последовательность «кликов» мышкой. В свою очередь, для сервера нагрузкой являются HTTP-запросы, которые сервер получает, анализирует и обрабатывает. Аппаратные компоненты персональных компьютеров, базовых станций операторов связи, размер загружаемых файлов и работающих с ними приложений, а также настройки и тип операционной системы могут быть различными у разных пользователей, обращающихся к серверу данных. В то же время эти факторы оказывают очевидное влияние на скорость загрузки приложений в сети . Описание нагрузки на нижнем уровне — это описание запросов пользователя в терминах занятия ресурсов, таких как среднее время обслуживания одного запроса, количество пакетов, пересылаемых между компьютером пользователя и сервером, и другие параметры . Эффективность функционирования любых on-line систем (мониторинга, Центра дистанционного обучения, информационного портала и т. п.) в наибольшей степени зависит именно от нагрузки на нижнем уровне, так как первым этапом обработки пользовательского запроса является установка соединения с конечным сервером (FS от английского Final Server). Время и надежность установки соединения определяют загруженность этого сервера, а умноженные на число пользователей и количество запросов (многие из которых являются повторными) данные параметры становятся определяющими в вопросе эффективности функционирования FS. Установка соединения зависит от технологии, используемой при обращении к FS. Для примера на рис. 1 и 2 изображены схемы установки соединения в сетях ATM и GSM . Очевидно, что они обладают идентичной структурой. Если учесть, что эти сети поддерживают протокол сетевого уровня IP (рис. 3), то на более подробном изучении последнего и следует остановиться. Рис. 1 Рис. 2 Рис. 3 Моделирование процесса поиска и загрузки web-страниц. Рассмотрим более подробно попытку установления соединения клиента с FS. Адрес, введенный им в адресную строку, необходимо преобразовать в 32-битовое (по версии IPv4) или 128-битовое (IPv6) число. Это преобразование осуществляют серверы доменных имен DNS (Domain Name System), которые поддерживают определенную доменную зону и обмениваются между собой информацией о поддерживаемых доменных зонах. Для дальнейшего анализа остановимся на ключевых этапах этого процесса. Сначала запрос клиента (U от английского user) приходит тому DNS-серверу, который обслуживает сервер самого клиента (через него клиент входит в сеть). Будем обозначать этот сервер входа клиента как US (User Server), а начальный DNS-сервер как DNS0. Этот сервер проверяет, зарегистрирован ли на нем запрашиваемый сайт. Если сайт найден, то к US возвращается его IP-адрес, и устанавливается соединение. Такой короткий маршрут практически не встречается в распределенных системах, поскольку US и FS логически отдалены друг от друга. Если запрашиваемый сайт не зарегистрирован на сервере DNS0 (типичный случай), то запускается рекурсивный поиск адреса. На первом этапе DNS0 анализирует домен высшего уровня (к таким доменам относятся, как известно, домены государств, com, org, gov, edu и т. д.). Если домен высшего уровня в запрашиваемом адресе не опознан, то возвращается сообщение об ошибке сначала к US, а потом и к пользователю. Если домен опознан, то запрашивается сервер (обозначим его DNS1), отвечающий за нужный домен высшего уровня. Тот просматривает свои записи и либо находит в них домен следующего уровня (в этом случае DNS0 получает информацию о том, какой сервер DNS2 обслуживает этот домен), либо не находит и отправляет DNS0 сообщение об ошибке. DNS0 транслирует это сообщение US и пользователю. После этого DNS0 запрашивает сервер DNS2, который просматривает свои записи и либо находит нужный сервер (в этом случае по цепочке возвращается соответствующий IP-адрес и устанавливается маршрутизация), либо ищет сервер, отвечающий за домен следующего уровня DNS3. Структура серверов Интернета на данный момент такова, что может понадобиться еще и запрос сервера DNS4 по описанной схеме. Описанный алгоритм изображен на рис. 4. Рис. 4 Построение математического описания процесса, приведенного выше, начнем с введения обозначений. Пусть время поиска адреса на сервере k обозначено . Поиск состоит в просмотре базы данных, т. е. складывается из большого числа одинаковых операций. При этом время, разумеется, зависит от аппаратно-программной части самого сервера. Таким образом, качественные предпосылки центральной предельной теоремы теории вероятностей выполнены, и время имеет распределение Гаусса с некоторым средним mk и дисперсией . Его плотность имеет вид: (1) Как было отмечено ранее, k принимает значения от 0 до некоторого K. На данный момент это значение максимально равно 4. Время обмена информацией между серверами с номерами k и l будем обозначать как Tkl (сервер DNSk отправляет данные, сервер DNS1 их получает). Потоки up и down между серверами существенно несимметричны, поэтому целесообразно различать сервер-отправитель и сервер-получатель. Время обмена информацией между сервером DNS0 и сервером пользователя US будет по аналогии обозначаться T0 US и TUS 0. Соответственно TU US и TUS U — время закачки информации upload и download для пользователя относительно входа сервера в сеть. Наличие proxy server вносит корректуру в данную модель, но для рассматриваемых приложений (в первую очередь — мониторинга и дистанционного обучения) это не существенно. Все время рассматривается в расчете на одну транзакцию. Пусть pk — вероятность обращения к DNSk. Очевидно, что p1 = 1 ? p2 ? …? pK. Тогда время поиска адреса при условии, что этот адрес существует, имеет вид: (2) Общее время T поиска (удачного) сервера и установления соединения задается аддитивным соотношением: T = T + Tcon. (3) где Tcon — время установления соединения с опознанным по IP-адресу сервером. Подобные конструкции ранее рассматривались в . Для дальнейшего анализа представим (2) в другой форме: (4) В разложении (4) выделяются две качественно разные компоненты: время, проведенное запросом на серверах DNS (5) и время, затраченное на прохождение каналов связи (6) При этом T = TDNS + Tlink. (7) Такое представление отражает разную природу отдельных компонент. Формула (5) представляет собой взвешенную сумму независимых случайных величин, поэтому для соответствующих плотностей распределения (8) Используя для множественной свертки обозначение по аналогии с суммированием и перемножением, представим (8) в более компактном виде: (9) Принимая во внимание, что отдельные компоненты свертки (9) имеют вид (1), получаем, что TDNS имеет распределение Гаусса с параметрами: (10) (11) Время, затраченное на прохождение каналов связи (6), может быть представлено как (12) Такое представление разбивает случайную величину Tlink на три слагаемых, первое из которых учитывает параметры канала пользователя до US и клиентов US, второе — каналов между серверами US и DNS0 и их клиентов, третье — каналов между DNS0 и DNSk, 1 ? k ? K. Учитывая разную природу отдельных слагаемых, можно предполагать их независимыми случайными величинами, поэтому плотность распределения случайной величины Tlink представляет собой композицию плотностей распределения отдельных слагаемых: (13) Распределение отдельных компонент этой свертки имеет похожую природу и активно исследуется в задачах телетрафика. Современные измерения трафика в сетях с коммутацией пакетов обнаружили в них свойство самоподобия (фрактальности) . В таком трафике присутствуют очень сильные выбросы на фоне относительно низкого среднего уровня, и как следствие — увеличение задержки при прохождении трафика через сеть. Самоподобный трафик хорошо моделируется, например, распределением Парето P(b,a), плотность распределения которого имеет вид: (14) где a — параметр формы, а b — параметр масштаба. Для такого распределения параметр Херста H связан с параметром формы соотношением: H = (3 — a)/2. Измерения показывают, что для типичного сетевого трафика показатель a лежит в промежутке (1,2). Следовательно, такая случайная величина имеет математическое ожидание ab/(a — 1) и обладает бесконечной дисперсией. Подстановка распределения (14) с нужными параметрами позволяет решить задачу в аналитическом виде или численными методами. Последний подход предпочтительнее по техническим причинам, природу которых можем показать на простом примере трафика с реальными значениями параметров. Пусть K = 2 и гарантированно запрашивается сервер первого уровня, т. е. p1 = p2 = 1, остальные pk = 0. В этом случае получаем (15) Предполагая для простоты все трафики одинаковыми и имеющими распределение P(1;1,5) (рис. 5), получаем, что отдельные суммы в скобках имеют распределение вероятностей с плотностью Рис. 5 (16) График этой функции и ее свертки предста лены на рис. 6 и 7. Рис. 6 Рис. 7 Дальнейшие расчеты аналитически весьма затруднительны и должны быть выполнены численно. А ведь это простейший случай одинаково распределенных слагаемых! При рассмотрении общего случая аналитические методы пасуют уже на первом шаге, поскольку для величин с распределениями P(b1,a1) и P(b2,a2), a1 ? a2, b1 ? b2 , их свертка (17) при x ? b1 + b2 выражается через обобщенные гипергеометрические функции 2F1: (18) где и (t)k = t(t + 1)…(t + k — 1) — символ Похгаммера. Очевидно, что последующие свертки функции G(x) с подобными ей следует выполнять только в численном виде. Возвращаясь к общему случаю (12), можно получить среднее время прохождения по каналам связи: (19) или с учетом (14) (20) Как уже отмечалось выше, дисперсия в этом случае бесконечна, поэтому разброс имеет смысл анализировать с помощью квантилей заданного уровня p (обычно 0,05 или 0,01), которые находятся численно как решения уравнения (21) Это гарантирует, что с вероятностью p время T не превысит значения tp. Графически нахождение этого решения показано на рис. 8. Рис. 8 Возвращаясь к разложению (7), получаем для окончательной плотности распределения (22) где (23) параметры mDNS и sDNS задаются уравнениями (10) и (11) соответственно, а плотность распределения времени Tlink определяется уравнениями (13)-(14) с надлежащими параметрами. К сожалению, свойства описанных распределений, не позволяют работать с ними традиционными средствами в силу бесконечной дисперсии распределения Парето при наблюдаемых в реальных трафиках значениях параметра формы. Поэтому имеет смысл только анализировать выход суммарного времени на определенный уровень с помощью соотношения (21). Заключение. Выведенные в статье соотношения позволяют оценить вероятность выхода времени обслуживания на заданную границу и могут быть использованы для определения границ семантической прозрачности сети. Полученные выражения приемлемы для наиболее разреженной топологии размещения DNS-серверов и учитывают требования к каналам их обслуживания. Все эти характеристики кардинальным образом сказываются на сервисах типа мониторинга, обучения и т. п. Анализ трафика предложенными методами позволяет оптимизировать сетевую составляющую такого процесса. Кроме того, предложенная методика анализа дополняет описанную в и может быть обобщена на другие сетевые задачи. . Мультисервисные телекоммуникационные сети. — М: Изд-во МГТУ им. , 2003. — 432 с. . . Базы данных. Интеллектуальная обработка информации. — М.: Нолидж, 2000. — 352 с. Arlitt M.. Williamson С. Web Server Workload Characterization: The Search for Invariants / Proc. ACM 1996 SIGMETRICS Conf. Measurement Comput. Syst.. Philadelphia, Pennsylvania. — May 1996. Р. 126-137. Barford P. Crovella M. Measuring Web Performance in the Wide Area bu.edu. tech reports.99-004-wi de-area- web-measurement.ps. Z Введение в технологию ATM / Пер. с англ. Под ред. . — М.: Радио и связь, 1997. — 126 c. Нумерация в сетях электросвязи. — М.: ИРИАС, 2004. — 232 с. Интеграция в электросвязи. — М.: ИРИАС, 2001. — 168 с. Моделирование распределений времени поиска и загрузки страниц в Internet / Тр. МТУСИ. — 2004. — С. 44-50. Leland W.E., Taqqu M.S., Willinger W. and Wilson D.V. On the self-similar nature of Ethernet traffic (extemded version) // IEEE/ACM Transactions of Networking, (TON). — Feb. 1994. — Vol. 2. №1. — P. 1-15. , , Фрактальные процессы в телекоммуникациях: Монография / Под ред. . — М.: Радиотехника, 2003 — 480 с. , , , Учет влияния спектральных свойств трафика на параметры сети с технологией АТМ // Электросвязь. — 2001. — №11. — С. 24-26. , Трафик радиосистем со случайным множественным доступом //Физика волновых процессов и радиотехнические системы. — 2004. — Т.7. — №2. — С. 59-63.