Портал GPSS.RU

А. М. Пуртов, В. Н. Задорожный

ИСПОЛЬЗОВАНИЕ ГРАФОВ ДЛЯ СОКРАЩЕНИЯ ИМИТАЦИОННЫХ ЭКСПЕРИМЕНТОВ (на примере анализа модели сети провайдера Интернет)


 

 

1.         Введение

Совместное использование имитационных моделей (ИМ) и графовых моделей процессов позволяет повысить информативность и сократить трудоемкость имитационных экспериментов [1]. Разработанная авторами методика демонстрируется на примере моделирования сети провайдера Интернет.


 

 

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

Рассмотрим структуру технических средств провайдера, приведенную на рис. 1. За основу взята сеть провайдера Интернет для учреждений науки, образования и культуры г. Омска [2]. Для связи с первичным провайдером используются полудуплексные каналы К1 и К2. Канал К1 служит для передачи данных между провайдером и междугородней телефонно-телеграфной станцией (МТТС). Сотрудники провайдера работают в локальной сети и имеют доступ в Интернет. В одном здании с провайдером находятся организации, сотрудникам которых также предоставляется доступ в Интернет. Локальные сети этих организаций и провайдера объединены с помощью коммутатора.

Пользователи вне здания провайдера связываются с ним по выделенным линиям или коммутируемым каналам. Для обеспечения доступа пользователей в Интернет по коммутируемым каналам (режим dial-up) провайдер имеет N1 модемов. Для постоянного подключения пользователей провайдер арендует N2 выделенных линий. Трафиком, проходящим через провайдера, управляет магистральный маршрутизатор. Требуется оценить влияние параметров системы на среднее время T получения информации из Интернет и оптимизировать параметры технических средств сети.


 

 

3.         Объекты и процессы ИМ


Уровень детализации ИМ выбирается так, чтобы отразить процессы, которые заведомо наиболее существенно влияют на показатели производительности сети.
Оборудование. Моделями каналов К1, К2 и магистрального маршрутизатора являются одноканальные устройства. Время обработки запросов на МТТС и первичным провайдером считается нулевым. Считается также, что коммутатор слабо влияет на время выполнения запросов, поэтому в ИМ он отсутствует. Моделями коммутируемых каналов с модемами являются N1 одноканальных устройств. Моделями выделенных линий с модемами являются N2 одноканальных устройств.
Сеансы связи пользователей. Все пользователи локальных сетей в здании про-вайдера являются источниками запросов на передачу данных в Интернет и приемника-ми данных из Интернет. Пользователи генерируют запросы на сеансы связи. В каждом сеансе связи запускается случайное количество параллельных процессов. Каждый про-цесс генерирует случайное количество запросов на получение данных из Интернет. Процесс генерирует следующий запрос только после получения ответа на предыдущий. Количество данных в ответе на запрос – случайная величина. Модель Интернет пред-ставляет собой приемник запросов и генератор ответов.
Запрос передается в Интернет через маршрутизатор и каналы К1, К2. Время об-работки запросов маршрутизатором не зависит от их длины. Время передачи запроса по каналам К1 и К2 зависит от их быстродействия и длины запроса. После поступления запроса в Интернет происходит его обработка в течение случайного промежутка вре-мени. Затем генерируется ответ и определяется количество блоков в ответе. Первый блок ответа передается через каналы К2, К1 и маршрутизатор пользователю. Если по-лучен не весь ответ, процесс посылает в сторону Интернет блок, разрешающий переда-чу из Интернет следующего блока ответа. Если ответ полностью получен, процесс мо-жет сгенерировать новый запрос. Если лимит запросов для процесса исчерпан, он за-крывается. Если у сеанса связи закрыты все процессы, он завершается.
У всех пользователей, работающих по выделенным линиям, процессы выполне-ния запросов претерпевают на этих линиях дополнительную задержку.
Пользователи, подключаемые по коммутируемым каналам, генерируют заявки на их резервирование. Если есть свободный канал, он резервируется. В противном слу-чае пользователь получает отказ в обслуживании. Когда канал зарезервирован, начина-ется сеанс связи. После окончания сеанса связи канал освобождается. Сеанс связи про-текает так же, как у пользователей, работающих по выделенным линиям. Для программирования модели использована бесплатно распространяемая сту-денческая версия GPSSW. Текст программы содержит около150 блоков GPSS.


 

 

4.         Граф процесса обработки запроса пользователя


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

Неизвестные средние задержки Ti процесса в вершинах i = 2, ... ,14 и переходные вероятности Pij в точках ветвления маршрутов определяются с помощью ИМ. В табли-це приводится описание задержек во всех вершинах графа. Возвращение блока данных из Интернет через вершины 8 – ... – 14 – 1 повторяет в обратном порядке движение за-проса в Интернет через вершины 1 – ... –7 – 8, но характеризуется другими значениями задержек, т. к. блоки данных, идущие в Интернет, обычно короче блоков данных, по-ступающих из Интернета.

Граф с параметрами Ti и Pij, найденными с помощью ИМ, обрабатывается про-граммой редукции, которая вычисляет следующие дополнительные характеристики:
– аналитическую оценку среднего Т и дисперсии D общего времени процесса;
– аналитическую оценку абсолютных и относительных коэффициентов чувстви-тельности (КЧ) этих показателей к параметрам Ti и Pij.


 

 

5.         Расширенный метод редукции графов с анализом КЧ


Метод редукции графов для определения среднего T и дисперсии D времени процесса предложен Байцером [3]. Феррари [4] предлагает дополнить его анализом чувствительности величин T и D к параметрам графа, вычисляя соответствующие част-ные производные методом малых приращений. В работе [5] метод редукции графа расширен набором подстановок и пересчетных соотношений, позволяющих получать в однократном процессе редукции сразу все необходимые КЧ, вычисленные по точным формулам аналитического дифференцирования.
Метод редукции графа заключается в последовательной замене типовых фраг-ментов графа на более простые фрагменты, эквивалентные в смысле времени прохож-дения через них исследуемого процесса. Пересчетные формулы, по которым определя-ются параметры вершин и дуг заменяющего фрагмента через параметры заменяемого, достаточно легко выводятся в предположении статистической независимости всех за-держек в вершинах и случайных переходов. Обычно редукция завершается стягивани-ем графа в одну вершину, параметры которой T и D являются искомыми характеристи-ками длительности всего процесса.
Метод редукции, предложенный в [5], содержит расширенный набор типовых замен. Наряду со «свертыванием цепочки вершин», «размыканием петли», «параллель-ным объединением» и т. д. он позволяет трансформировать некоторые циклы специ-ального вида, присущие процессам в вычислительных системах и характеризуемые за-висимостью переходов. Кроме того, в этом варианте метода состав всех пересчетных соотношений расширен дополнительными соотношениями, по которым рассчитывают-ся частные производные параметров заменяющего подграфа по всем параметрам заме-няемого подграфа. Эти дополнительные соотношения получены путем формального дифференцирования основных пересчетных соотношений. Они позволяют на каждом шаге редукции (с учетом правил дифференцирования суперпозиции функций многих переменных) вместе с параметрами нового подграфа вычислять их частные производ-ные по изначально заданным параметрам исходного графа.
Таким образом, в результате редукции графа вместе с показателями T и D опре-деляются значения их частных производных по всем n параметрам исходного графа (абсолютные КЧ), а также относительные КЧ, имеющие вид:

Метод эффективно реализован программой COIN1 (COefficients of INfluence – коэффициенты влияния), которая написана на Borland C++ 3.1. Она позволяет выпол-нять редукцию полных графов с отмеченными начальной и конечной вершинами. Входные данные для программы представляются в текстовом файле, выходные данные отображаются в графической форме и выводятся в текстовый файл.


 

 

6.         Описание имитационных экспериментов


В первом прогоне ИМ задавались следующие значения основных параметров:
– число модемов для коммутируемых каналов N1 = 5;
– скорость передачи по коммутируемому каналу – 30 000 бит/c;
– скорость обработки пакетов на маршрутизаторе – 1000 пак/c;
– скорость передачи данных по каналу К1 – 1 000 000 бит/c;
– скорость передачи данных по каналу К2 – 500 000 бит/c;
– максимальная длина блока данных, передаваемого из Интернет – 80 000 бит;
– время обработки блока данных в Интернет составляет в среднем 1c;
– количество информации, поступающей из Интернет по одному запросу, в среднем равно 1 600 000 бит.
Две последние величины распределены по экспоненциальному закону.
Графовая модель (рис. 2) с параметрами, найденными с помощью ИМ, обраба-тывалась программой COIN1, которая выдала коэффициенты Kb[T,Ti], графически представленные на рис. 3. Поскольку T является линейной комбинацией параметров Ti (при фиксированных Pij) то, как следует из (1), сумма этих КЧ должна быть равна еди-нице.
По данным ИМ среднее время выполнения процесса T составило 177 c, по графу – 190 с. Близость экспериментальной и аналитической оценок свидетельствует о том, что граф удовлетворительно аппроксимирует моделируемую сеть, хотя в ней задержки (и переходы) в общем случае не являются независимыми, как предполагается в графе.
Из рис. 3 видно, что наибольший относительный вклад в Т формирует параметр T14 – среднее время передачи данных пользователю по коммутируемому каналу. С этим же каналом связаны задержки в вершинах 2, 3, 13. Провайдер не может регулировать эти задержки, т. к. они связаны со скоростью работы модемов пользователей и количе-ством получаемой ими информации из Интернет по одному запросу, т. е. относятся к внешней среде провайдера. С ресурсами провайдера связаны задержки в вершинах 6 и 9, также сильно влияющие на Т и определяемые скоростью канала К2. Увеличиваем скорость канала К2 вдвое (дихотомический шаг), т. е. до 1 Мбит/c. Снова запускаем на выполнение ИМ, потом программу COIN1 и получаем КЧ, представленные на рис. 4.

Из рис. 4 видно, что во втором прогоне модели наибольшее влияние на время Т оказывают задержки T2, T13, T14 (все – на коммутируемом канале) и задержка T8, зави-сящая от времени обработки запроса в Интернет. По результатам ИМ среднее время выполнения процесса сократилось до значения T=143 c, по графовой модели – до 138 с.
Таким образом, благодаря КЧ понадобилось всего два прогона имитационной модели, чтобы подобрать рациональные параметры сети провайдера. Близость к нулю коэффициентов Kb[T,T6] и Kb[T,T9] говорит о том, что в существующей внешней среде дальнейшее повышение скорости канала K2 практически не скажется на времени T.


 

 

7.         Анализ КЧ и оптимизация


Разработанную методику можно распространить и на решение задач оптимиза-ции в классической постановке, если аргументы целевой функции f включают показа-тели времени ответа T и D, а параметры Ti и Pij выражаются в явном виде (точно или с помощью аппроксимаций) через технические параметры сети. Поскольку редукция графа реализует суперпозицию функций, то ее можно достроить начальным и финаль-ным пересчетами, чтобы сразу вычислялись частные производные функции f по всем контролируемым техническим параметрам. Это позволит использовать в имитацион-ном моделировании сетей массового обслуживания градиентные методы оптимизации.
Концептуально использование для оптимизации сети наряду с ИМ ее высоко-аналитичной и быстрой графовой аппроксимации можно уподобить применению квад-ратичной аппроксимации функций при поиске их локальных экстремумов методом Ньютона.


 

 

8.         Литература


1. Пуртов А. М. Анализ производительности сетей ЭВМ на графах и имитационных моделях.: Автореф. дисс. на соиск. учен. степени канд. техн. наук (05.13.16)/ Науч. рук. В.А.Шапцев. – Омск: ИИТПМ СО РАН, 1995. –17 с.
2. Алгазин В. А. Создание высокоскоростной СПД для информационного обмена между членами научных коллективов (в рамках проекта КС ОКНО)//RELARN – 2001: Матер. VIII конф. представителей регион. научно-образов. сетей. – Петроза-водск: Изд-во ПетрГУ, 2001. –С. 101–105.
3. Байцер Б. Микроанализ производительности вычислительных систем: Пер. с англ./Под ред.В. В. Мартынюка. – М.: Радио и связь, 1983. – 360 с.
4. Феррари Д. Оценка производительности вычислительных систем. – М.: Мир, 1981. – 576 с.
5. Задорожный В. Н., Мызникова Т. А. Рекурсивный анализ чувствительности для метода Байцера. – Деп. в ВИНИТИ, 1988. N 5490-B88.

 


Распечатано с портала GPSS.RU (c) А. М. Пуртов, В. Н. Задорожный , 2005 г.