автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Оценка нагрузки на компьютерную сеть при обработке поисковых запросов в интегрированных информационных системах

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

ГАЛИЕВ ТИМУР ЭРГУНОВИЧ

ОЦЕНКА НАГРУЗКИ НА КОМПЬЮТЕРНУЮ СЕТЬ ПРИ ОБРАБОТКЕ ПОИСКОВЫХ ЗАПРОСОВ В ИНТЕГРИРОВАННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ

Специальность 05.13.15 - Вычислительные машины, комплексы и

компьютерные сети

2 6 ДПР 2012

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва - 2012

005019349

Работа выполнена на кафедре «Вычислительные системы и сети» ФГБОУ ВПО Московский государственный институт электроники и

математики

Научный руководитель: доктор технических наук, профессор

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

Официальные оппоненты: Фролов Евгений Борисович, доктор технических

наук, профессор МГТУ СТАНКИН профессор кафедры «Информационные технологии и вычислительные системы»;

Никитин Евгений Валерьевич, кандидат технических наук, заместитель директора специальных программ ЗАО «РНТ».

Ведущая организация: ФГБОУ ВПО Рязанский государственный

радиотехнический университет.

Защита диссертации состоится «22» мая 2012 г. в 10.00 часов на заседании диссертационного совета Д212.133.03 в Московском государственном институте электроники и математики (Техническом университете) по адресу: 109028, Москва, Б. Трехсвятительский пер., 3.

С диссертацией можно ознакомиться в библиотеке МИЭМ.

Автореферат разослан « Р ъ/Н1Р<?Ф.2012 г.

Ученый секретарь

диссертационного совета, / у

Д 212.133.03, д.т.н., доц. С) '______Леохин Ю.Л.

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

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

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

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

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

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

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

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

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

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

Задачи исследований. Для достижения поставленной цели в работе сформулированы и решены следующие задачи:

1. Анализ процедур поиска, применяемых в современных корпоративных интегрированных информационных системах.

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

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

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

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

программирования, а также современные методы создания распределенных интегрированных информационных систем.

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

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

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

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

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

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

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

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

Апробация работы. Основные положения и результаты диссертации докладывались на научно-техничесих конференциях студентов, аспирантов и молодых специалистов МИЭМ (Москва, 2007, 2008 г.г.), Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций, (Рязань 2008 г.), обсуждались на научно-технических семинарах кафедры ВСиС МИЭМ.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и списка литературы из 117 наименований. Объем диссертации 133 страницы.

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

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

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

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

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

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

Исследованы наиболее распространенные подходы к интеграции данных и их влияние на процесс поиска требуемых данных:

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

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

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

При создании систем корпоративных интегрированных систем возникает

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

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

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

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

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

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

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

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

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

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

Исследованы различные варианты организации поиска в распределенной системе (Интернет, корпоративные информационные системы).

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

В общем случае поисковая система состоит из поисковых серверов и

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

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

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

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

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

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

формируются запросы к узлам.

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

Перечисленные характеристики позволят оценить загрузку каналов связи передаваемыми данными и время до получения ответа пользователем.

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

со оо

распределения такой, что 0 < 6, = \tdBit) < оо и 0<Ь2 = ¡{2с1В(1) <<х>;

о о

длительность обработки запроса на узле /, случайная величина с функцией

сс т

распределения Ь\ (?), такой, что 0 < /„ = \tdF- (I) < оо и 0 < /2, = (?<#; (/)<«>.

О о

Показано, что процессы случайного и поиска последовательным перебором можно описать дискретной конечной поглощающей цепыо Маркова (стохастическая модель). Состояние цепи это число просмотренных после окончания шага поиска узлов. Цепь имеет одно поглощающее состояние - О, которое соответствует прекращению поиска, т.е. нахождению требуемых данных. Общее число состояний цепи равно (К+ 1). Номер состояния цепи (если это не состояние номер 0) совпадает с номером шага поиска. Номер состояния и состояние отличаются в данном случае на 1: состояние 0 имеет порядковый номер 1, а состояние К имеет номер (К + 1).

Из каждого состояния номер г, (К>г> 1) можно перейти только либо в поглощающее - г = 0 (поиск окончен), либо в следующее - (г + 1) (поиск продолжается на следующем шаге). Из состояния номер К+1, соответствующего случаю, когда остается только один узел для просмотра, с вероятностью 1 можно перейти только в поглощающее состояние, в этом случае на оставшемся узле должны находятся искомые данные. Максимальное число шагов - К.

Вероятность перехода цепи из состояния ; в состояниеу - р^, вероятность попадания из состояния / в поглощающее состояние - рт, (/,/ = 0, 1,2,..., К).

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

На т шаге поиска (1 < т < К) с вероятностью 0 < дк (К-т + \)<\ выбирается узел номер кт из оставшихся (К - т +1) узлов (при этом

К-т+1

\<к,„ <К; кт ^к, Фкг и справедливо равенство: -т + [) = 1.

Для этого шага вероятность размещения искомых данных на узле равна: гк {К-т+\)=\1{К-т+\). Также имеем для шага К: дкк(1) = 1 и 2^(1) = 1.

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

вероятностью qk(K-m + \) = \ выбирается узел кт из оставшихся (К - т +1) узлов; здесь 1 <кп <К и задано условие: zot,„ = w max {z,.}, = 1,2,... Д).

Последовательность выбора узлов однозначно задается вектором: к = (к^к2,ку,...,кк). Если вероятности нахождения искомых данных на узлах упорядочены в порядке убывания, то =1, к2 =2, к} =3,..., кК=К.

Матрица переходных вероятностей цепи Р в общем случае имеет вид:

к

На т шаге поиска (1 <т<К) с

' 1 0 0 0 0 ... 0 0 А о 0 1 -р10 0 0 ... 0 0

р20 0 О 1-р20 о ... о о

Р= Рзо 0 0 0 1-Рзо ... 0 0

Ри-цо 0 0 0 0 ... 0 1

, рка о о о о ... о о

Для случайного поиска вероятность попадания в поглощающее состояние при выборе портала на шаге т вычисляется по формуле:

Л'—1

2Х,(ЛГ-/я+1)=—-- ,(« = 1,2, ...,(А-+1)).

Р,„ о;

(К-т+1) (ЛГ-/Я+1)

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

Р\0 = = 201 ,

= г01„, + Рю/(к-1) + р20 /{К - 2) +... + /(/¡Г - т +1), (т= 2, 5,...,К). При этом: рко = 1.

Для вычисления вероятности попадания цепи в какое-либо из состояний на определенном шаге, при заданном начальном состоянии используется формула: 9г=я0Рг Я,. = (Чог>Ч\г>-~'Чкг) - вектор-строка, компонента которой О < д< 1, есть вероятность попадания в состояние у на шаге г,

71 о = (^ор^от'-'-'^оса-н)) - вектор-строка, компоненты которой это вероятности начальных состояний цепи.

Г Б (Л

Матрицу Р можно представить в виде: Р= , где в - матрица,

состоящая из одного элемента, равного 1,0- нулевая матрица.

Среднее число шагов до попадания в поглощающее состояние (среднее число попыток поиска до получения результата) может быть вычислено по

К+1

известной формуле: п = N6, где N=^(2'- фундаментальная матрица, е -

л=О

единичный вектор-столбец размерности К, пг == («, , и2,..., пк ), где п^ среднее число шагов до попадания в поглощающее состояние, при начале в состоянии /'.

Среднее время от начала процесса до попадания в поглощающее состояние: 1 = /,п здесь считаем, что /|(. = /, , 1 - вектор-столбец

размерности К, где - среднее время до попадания в поглощающее состояние при начале в состоянии /'.

Безусловные характеристики алгоритмов:

- среднее число шагов до попадания в поглощающее состояние: ^оо = яоп>

- среднее время до попадания в поглощающее состояние: Т00 — Jt0t.

Для обоих алгоритмов проведена оценка объема передаваемых при поиске данных.

Представляет практический интерес анализ алгоритмов поиска при обработке последовательности (потока) поисковых запросов. Для этого в качестве математической модели использовалась К - фазная СМО. На вход системы поступает поток поисковых запросов от пользователей. Каждое обслуживающее устройство (ОУ) соответствует узлу сети, где может находиться искомая информация. Дисциплина обслуживания запросов FIFO, входящий поток запросов - пуассоновский с параметром Л.

В модели не учитывается фаза обработки на поисковом сервере, что дает возможность сделать модель боле адекватной для случая самостоятельного поиска нужной информации каждым пользователем (без поискового сервера). Если поисковый сервер используется, то время обслуживания запроса на поисковом сервере добавляется ко времени обслуживания запроса на К - фазной СМО.

Пусть pi - вероятность того, что запрос будет обслужен на г-м узле, т.е.

к

искомые данные находятся на узле i (г-й фазе) и £ р, = 1. Значения указанных

м

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

Интенсивность потока запросов от фазы к фазе меняется за счет ухода из системы обслуженных запросов, следовательно, необходимо вычислять среднюю длительность пребывания запроса на фазе к с учетом этого факта. Каждая фаза есть СМО типа M/M/1/co, для которой среднее время пребывания запроса в системе: t = 1 /(// - Л), где и - интенсивность обслуживания запросов, Л - интенсивность входящего потока запросов).

Среднее время пребывания запроса в системе (поиск последовательным перебором узлов): ТХ{ = y£Jpi -Л + Л^Гр,,,)"1 Средне время обслуживания

запроса, с учетом обслуживания запроса на поисковом сервере:

2(1-ЛЬ,) "

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

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

В качестве модели для анализа алгоритма направленного поиска использована двухфазная система массового обслуживания. Фаза I -обработка запроса на поисковом сервере - ОУ0. Фаза II - обработка запроса на обслуживающем устройстве ОУ„ ; = 1 ,К (узле, где находится искомая информация). Задана р,- - вероятность того, что искомая информация находится на / -м узле. На вход первой фазы поступает пуассоновский поток запросов с параметром Л. Длительность обслуживания запроса случайная величина с экспоненциальным распределением и параметром //0. Фаза I есть СМО типа Мд/Мд/1/оо, где /? = 1 / . Поток с фазы I на / узел фазы 2 является пуассоновским, поскольку образуется из входящего пуассоновского потока путем операции просеивания, и Л, = Ар! г = 1, К. Длительность обслуживания одного запроса на ОУ, второй фазы - случайная величина с экспоненциальным распределением и параметром //,, / = 1, К. Получено, что среднее время поиска:

Т 1 V1 А

Г=--+ / ,--—. Среднее число шагов: N=2.

/'о"Л н Д --V,

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

M Я и s «3 се § ш Î.73xl03-

s «■а s Tiafl(i) 4.dxl05-

•♦3 ТгаЛ(х)

n Tiaf3(x> 3.43xl0?"

Э Sä Traf31(ï)

<L> 2-3x10*

s

Ci.

к 1.15x10*'

■LI

о

поиск в заданном _ -порядке

100 200 300 400 500 tSOO

х

Количество поисковых запросов от пользователей

В четвертой главе приведено описание разработанного специализированного программного обеспечения, представлены результаты имитационного моделирования. Для создания имитационных моделей поиска информации в интегрированных распределенных информационных системах был выбран следующий инструментарий: язык программирования Visual С# и Microsoft Visual Studio 2008 .NET в качестве среды разработки.

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

ЗАКЛЮЧЕНИЕ. ОБЩИЕ ВЫВОДЫ

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

2. Показано, что длительность поиска во многом зависит от методов и средств формирования и обработки поисковых запросов, формы представления и объемов дополнительной информации в поисковых системах. Это делает целесообразным построение корпоративных интегрированных информационных

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

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

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

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

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

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

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

1. Галиев Т.Э. Имитационные модели поиска информации в корпоративных

поисковых системах. // Программная инженерия, № 1,2012. - С. 46-47.

2. Галиев Т.Э. Методы ранжирования поисковой информации в

корпоративных поисковых системах. // Открытое образование, № 1, 2012. -

С. 46-51.

3. Галиев Т.Э. Современные технологии передачи данных Triple Play и NGN. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. М.: МИЭМ, 2007. - С. 164.

4. Галиев Т.Э. Интегрированные системы. Метаданные как средство интеграции. // 15 Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Материалы конференции, часть 2, Рязань, РГРТУ, 2008. - С. 3-5.

5. Галиев Т.Э. Применение метаданных при организации доступа в распределенных системах. // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник научных трудов, Рязань, РГРТУ, 2008,- С. 97-99.

6. Галиев Т.Э. Применение метаданных для организации доступа в распределенных системах. // Информационные, сетевые и телекоммуникационные технологии: Сборник научных трудов. М.: МИЭМ, 2008,- С. 91-93.

7. Галиев Т.Э. Проблемы создания интегрированных информационных систем. // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. М.: МИЭМ, 2008. - С. 158 - 159.

8. Галиев Т.Э. Оценка эффективности использования метаданных при поиске информации в распределенных системах. // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник научных трудов. Рязань, РГРТУ, 2009. - С. 105-110.

9. Галиев Т.Э. Рост количества поисковых запросов в интернете. // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник научных трудов. Рязань, РГРТУ, 2011. - С. 61-63.

10. Галиев Т.Э. Организация поиска в интегрированных распределенных системах // Математическое и программное обеспечение вычислительных систем: Межвузовский сборник научных трудов. Рязань, РГРТУ, 2011. -С. 126-129.

Подписано в печать 16.04.2012 г. Формат 60x90 1/16 Печать на ризографе. Тираж 100 экз. Заказ № 7807. Объем: 1,1 усл.п.л.

Отпечатано в типографии ООО "Алфавит 2000", ИНН: 7718532212, г. Москва, ул. Маросейка, д. 6/8, стр. 1, т. 623-08-10, www.alfavit2000.ru

61 12-5/2591

Галиев Тимур Эргунович

ОЦЕНКА НАГРУЗКИ НА КОМПЬЮТЕРНУЮ СЕТЬ ПРИ ОБРАБОТКЕ ПОИСКОВЫХ ЗАПРОСОВ В ИНТЕГРИРОВАННЫХ ИНФОРМАЦИОННЫХ

СИСТЕМАХ

Специальность 05.13.15 - Вычислительные машины, комплексы и

компьютерные сети

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель -доктор технических наук, профессор Е.А. Саксонов

Москва-2012 г.

Оглавление

ВВЕДЕНИЕ..............................................................................................................5

1. ОРГАНИЗАЦИЯ ДОСТУПА К ИНФОРМАЦИИ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ...........................................................................................................10

1.1. Проблема поиска информации в распределенной системе..................10

1.2. Организация данных в интегрированных распределенных системах 13

1.2.1. Консолидация данных........................................................................15

1.2.2. Федерализация данных......................................................................16

1.2.3. Распространение данных...................................................................17

1.3. Архитектурные подходы к построению интегрированной системы ..18

1.3.1. Интегрирующие модели данных......................................................19

1.3.2. Средства семантической интеграции данных.................................19

1.4. Использование метаданных.....................................................................20

1.4.1. Интеграция текстовых ресурсов.......................................................20

1.5. Сети дистрибуции данных.......................................................................28

1.5.1. Преимущества СБЫ...........................................................................28

1.5.2. Технология..........................................................................................30

1.5.3. Маршрутизация контента..................................................................34

Выводы................................................................................................................37

2. ОРГАНИЗАЦИЯ ПОИСКА ИНФОРМАЦИИ В РАСПРЕДЕЛЕННОЙ ИНТЕГРИРОВАННОЙ СИСТЕМЕ.....................................................................39

2.1. Общие принципы организации поиска информации............................39

2.1.1. Средства поиска..................................................................................39

2.1.2. Информационные ресурсы поисковых систем................................41

2.1.3. Проблемы организации поиска.........................................................48

2.2. Организация поиска в Интернет.............................................................52

2.3. Процедуры поиска....................................................................................55

2.4. Использование метаданных.....................................................................56

2.5. Алгоритмы поиска....................................................................................60

2.5.1. Базовые алгоритмы поиска................................................................61

2.5.2. Характеристики алгоритмов поиска информации в распределенных системах...............................................................................................................62

Выводы................................................................................................................63

3. МАТЕМАТИЧЕСКИЕ МОДЕЛИ АЛГОРИТМОВ ПОИСКА...................64

3.1. Описание алгоритмов.................................................................................64

3.2. Модель алгоритма случайного поиска......................................................67

3.2.1. Общее описание....................................................................................67

3.2.2. Модель алгоритма.................................................................................69

3.2.3. Вычисление характеристик алгоритма...............................................73

3.2.4. Оценка размера передаваемых данных при случайном поиске......76

3.3. Модель поиска методом последовательного перебора.........................78

3.3.1. Общее описание....................................................................................78

3.3.2. Математическая модель.......................................................................79

3.4. Расчет временных характеристик алгоритмов......................................83

3.4.1. Общие результаты.................................................................................83

3.4.2. Оптимизация поиска.............................................................................85

3.4.3. Оценка размера передаваемых данных при поиске в заданном

порядке.............................................................................................................90

3.5. Модель поиска последовательным перебором......................................92

3.5.2. Оценка размера передаваемых данных при направленном поиске с использованием метаданных.........................................................................95

Выводы................................................................................................................99

4. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ДЛЯ АНАЛИЗА АЛГОРИТМОВ ПОИСКА..............................................................................................................100

4.1. Имитационные модели поиска информации в распределенных системах ............................................................................................................................100

4.2. Имитационная модель процедуры случайного поиска.......................112

4.3. Имитационная модель процедуры поиска в заданном порядке...........115

4.4. Имитационная модель процедуры направленного поиска...................117

4.3. Скрин-шоты программы........................................................................119

Выводы..............................................................................................................121

ЗАКЛЮЧЕНИЕ. ОБЩИЕ ВЫВОДЫ................................................................122

ЛИТЕРАТУРА.....................................................................................................124

ВВЕДЕНИЕ

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

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

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

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

Применение специализированных поисковых серверов позволяет проводить целенаправленный поиск за счет предварительного сбора и

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

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

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

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

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

Задачи исследований. Для достижения поставленной цели в работе

сформулированы и решены следующие задачи:

1. Анализ процедур поиска, применяемых в современных корпоративных интегрированных информационных системах.

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

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

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

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

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

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

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

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

Научная новизна результатов диссертации заключается:

- в определении базовых алгоритмов поиска информации в распределенных системах;

- в установлении зависимостей между параметрами алгоритмов, априорной информацией о нахождении искомых данных, имеющейся у пользователя, и их характеристиками;

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

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

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

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

Достоверность и обоснованность результатов диссертации основаны:

- на соответствии построенных математических и имитационных моделей реальным процессам, происходящим в распределенных системах при поиске информации;

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

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

Апробация работы. Основные положения и результаты диссертации

докладывались на научно-техничесих конференциях студентов, аспирантов и молодых специалистов МИЭМ (Москва, 2007, 2008 г.г.), Международной научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций, (Рязань 2008 г.), обсуждались на научно-технических семинарах кафедры ВСиС МИЭМ.

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

1. ОРГАНИЗАЦИЯ ДОСТУПА К ИНФОРМАЦИИ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ

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

Основные результаты данной главы опубликованы в следующих работах автора [17, 19, 20, 21, 22, 23]. 1.1. Проблема поиска информации в распределенной системе

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

Особенно это заметно при анализе организации поиска в среде Интернет.

Сегодня в сети Интернет накоплен внушительный объем информации. С каждым годом количество информации увеличивается. В начале 2009 года объем данных, хранящийся, на серверах, подключенных ко Всемирной сети вплотную приблизился к отметке в 500 млрд Гб (по данным аналитической компании ЮС (www.idc.com), проводившей исследование по заказу ЕМС Corporation (www.emc.com)). По прогнозам аналитиков, через полтора года количество данных вырастет еще в 2 раза. Так же с каждым годом растет и количество пользователей сети Интернет. По данным аналитиков компании ComScore (www.comscore.com) к началу 2009 количество пользователей

интернет составило 1 млрд. человек и продолжает расти. На рисунке 1.1 приведена динамика роста количества пользователей поисковой системы Яндекс [95].

Средняя дневная аудитория (будни)

Количество человек, посетивших сервис хотя бы 1 раз за день (среднее за все будние дни месяца)

12 000 000-, 10 000 000 -8 000 000 -

6 000 000- ...............

4 000 000 -2 000 000 -

I I I I I-1-1-1-1-1-1-

июлОЭ авгОЭ сен 09 окт 09 ноя 09 дек 09 дне 10 февЮ иарЮ апрЮ май 10

Рис. 1.1. Количество пользователей поисковой системы Яндекс

Задачу поиска информации в Интернете решают поисковые системы.

Существует большое количество систем, осуществляющих поиск как в русскоязычной части Интернет - Rambler, Aport, Yandex, так и во всем Интернет пространстве - Yahoo, Google, Bing. Каждая поисковая система реализует свой уникальный поисковый алгоритм. Современные поисковые системы позволяют осуществлять поиск с учетом особенностей морфологии языка, находить ошибки в запросах пользователей и предлагать варианты исправления.

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

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

систем. Объем передаваемого при этом трафика зависит от алгоритмов работы поисковых систем.

По данным аналитической компании СотБсоге в декабре 2007 года поисковые сайты обработали 66 млрд. 221 млн. поисковых запросов [93, 94]. Эта цифра продолжает расти.

В таблице 1.1 представлены данные о количестве поисковых запросов в 2008 и 2009 году по данным компании СотЭсоге [96, 97].

Таблица 1.1. Количество поисковых запросов в 2008 и 2009 году по данным компании СотБсоге [96]

Название поисковой Количество Количество Изменение %

системы поисковых поисковых

запросов запросов (млн)

(млн) в июле в июле 2009

2008 года года

Всего 80 554 113 685 41%

Google Sites 48 666 76 684 58%

Yahoo! Sites 8 689 8 898 2%

Baidu.com Inc. 7413 7 976 8%

Microsoft Sites 2 349 3 317 41%

eBay 1 223 1 723 41%

NHN Corporation 1 243 1 526 23%

Ask Network 929 1 291 39%

Yandex 663 1 290 94%

AOL LLC 1 148 1 023 -11%

Facebook.com 743 879 18%

Ниже, в таблице 1.2, приведены данные об объеме поисковых запросов. При

расчете величина одного поискового запроса взята равной 0.1 Мб. Таблица 1.2. Объем поисковых запросов

Период времени Количество запросов (млн) Объем данных (Мб)

Декабрь 2007 год 66 221 66 221 * 105

Июль 2008 год 80 554 80 554 * 103

Июль 2009 год 113 685 113 685 * 105

Легко заметить, что объемы хранимой на серверах сети Интернет информации, количество пользователей и количество поисковых запросов постоянно растут. Количество обрабатываемых запросов, только, русскоязычной поисковой системой Яндекс с июля 2008 по июль 2009 года увеличилось вдвое и продолжает расти. Как следствие, растет и загрузка каналов связи.

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

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

1.2. Организация данных в интегрированных распределенных

системах

Разработка методов интеграции информационных ресурсов - одна из наиболее актуальных проблем в области информационных систем. Особенно большое внимание она стала привлекать в последние годы. Однако