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

1

2 Проблемы создания математического обеспечения моделирования инфо- телекоммуникационных сетей А.С.Родионов Институт Вычислительной математики и математической геофизики СО РАН, Лаврентьева, 6, Новосибирск, (383-2) ,

3 Инфо-телекоммуникационные сети как объект моделирования Общие свойства: Большая (супербольшая) размерность; Наличие очевидной структурированности и распределённости; Наличие большого количества стандартных компонентов; Ненадёжность; Конфликтный характер поведения (борьба за использование общих ресурсов); Сложность получения исходной информации для моделирования (данные обычно секретны)

4 Задачи и решения (1) Большая размерность требует специальных средств для эффективного исполнения моделей на распределённых или параллельных ВС. Очевидные структурированность и распределённость позволяют: –Создавать дружественный графический интерфейс. –Естественным образом организовывать распределённые модели. Существование большого количества стандартных компонентов также хорошо для дружественного интерфейса и позволяет создавать базы подмоделей.

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

6 Критический вопрос: Как представлять модель? При использовании некоторого математического описания модели (например, СМО) мы выигрываем в простоте, интерфейсе и стоимости пакета моделирования (нам необходима единственная программа моделирования, обрабатывающая данные о модели) и теряем в гибкости и общности. При использовании некоторого стандартного подхода к описанию модели (например, транзактно- ориентированного в GPSS, процессно- ориентированного в Симула или событийно- ориентированного в Simscript) мы выигрываем в гибкости и общности и теряем в простоте, интерфейсе и стоимости.

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

8 Специальные генераторы случайных объектов Для адекватного моделирования нам необходимы средства для: Коррелированных процессов (A.S. Rodionov, H. Choo and H.Y. Youn. Process simulation using randomized Markov chain and truncated marginal distribution / Supercomputing, no.1, 2002, - P.69-85); Случайных структур (A.S. Rodionov and H. Choo. On Generating Random Network Structures: Trees / LNCS, Vol. 2658, 2003 P and A.S. Rodionov and H. Choo. On Generating Random Network Structures: Connected Graphs / ICOIN 2004, Vol. III, P );

9 Два процесса с одинаковой плотностью (e -x ) и разными АКФ

10 Моделирование M/M/1 с интенсивностью обслуживания μ=1.5 и интенсивностью входного потока 1 при независимом порядке даёт среднее время ожидания ω=7.94. При использовании интервалов межу поступлениями требований, распределённых согласно показанным процессам имеем ω= и ω=7.62, соответственно. Разность значима по t-критерию с 95%-ым уровнем значимости.

11 Наш подход заключается в применении рандомизиро- ванных цепей Маркова (РЦМ). Это означает, что мы имеем цепь Маркова распределений F i и каждое новое значение процесса получается с использованием соответствующего распределения. В качестве F i мы используем исходное распределение усеченное на межквантильных интервалах. АКФ аппроксимируется решением следующей задачи оптимизации: ||τ(x)-τ*(x)|| min где τ(x) есть исходная автокорреляционная функция (АКФ), а τ*(x) есть АКФ РЦМ. В качестве нормы обычно берётся сумма квадратов отклонений.

12 Пример экспоненциального распределения и τ(x) =e -0.1t cos(0.4t)

13 Случайные структуры сетей должны быть правдоподобны

14 Получение случайных структур «похожих на реальные сети» - трудная задача

15 История вопроса В последнее десятиление задача обсуждалась, например, следующими авторами: B.M. Waxman (1993), M. Doar (1993,1996), Chai-Keong Toh (1993), E.W. Zegura, K.L. Calvert, and S. Bhattacharjee (1996), R. Kumar, P. Raghavan, S. Rajagopalan, D. Sivakumar, A. Tomkins, and E. Upfal (2000). Они представляли быстрые алгоритмы, в частности дающие структуры со свойствами, схожими со свойствами структур реальных сетей. Но никто из них не обсуждал стохастические свойства получаемых случайных графов.

16 Мы используем Метод допустимого выбора Пусть A i есть множество рёбер, допустимых к включению в граф на i-м шаге; In i – множество рёбер, добавляемых к A i перед (i+1)-м шагом; Ex i – множество рёбер, исключаемых из A i перед (i+1)-м шагом. На каждом шаге к графу добавляется новое ребро и A i+1 =A i \Ex i In i ЕСЛИ (A i+1 =Ø) ТО ОТКАТ НА ШАГ ЕСЛИ e st есть последнее перед откатом выбранное ребро, то оно переводится из A i в Ex i.

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