|
Источник: Proc. 2003 Winter Simulation Conf., New Orleans, LA, 2003.
http://citeseerx.ist.psu.edu/viewdoc/download;
jsessionid=69584C86208AA051A4D82A4D0BF17E1C?doi=10.1.1.1.4900&rep=rep1&type=pdf
Моделирование широкомасштабных сетей с использованием SSF
David M. Nicol, Jason Liu, Michael Liljenstam
(Дэвид М. Николь, Джейсон Лиу, Михаэль Лильйенстам)
Department of Electrical and Computer Engineering
Coordinated Science Laboratory
University of Illinois at Urbana-Champaign
1308 W. Main St., Urbana, IL 61801, U.S.A.
Guanhua Yan (Гуанхуа Ян)
Department of Computer Science
Dartmouth College
6211 Sudikoff Laboratory
Hanover, NH 03755, U.S.A
Автор перевода: Астахов А.В.
Реферат
Некоторые приложения моделирования требуют, чтобы состояние модели рассчитывалось быстрее, чем протекает обычное время, за которое выполняется процесс моделирования. Это требование "быстрее реального времени" является ключевым, к примеру, когда моделирование используется как часть системы управления реального времени, работающей по результатам спланированных действий управления, чтобы определить подходящие (или даже оптимальные) решения. Это статья рассматривает моделирование "быстрее реального времени" очень больших сетей связи и то, как это достигается с помощью нашей реализации (на C++) масштабируемой структуры моделирования (Scalable Simulation Framework – SSF). Наш инструмент (называемый iSSF) использует иерархические уровни абстракции и параллелизм для достижения ускорения почти на 4 порядка, позволяя выполнять моделирование в реальном времени на больших сетевых моделях. Мы определяем влияние выбора иерархической абстракции, повышающей скорость выполнения моделирования, и опытным путем показываем как изменение сочетания абстракции оказывает воздействие на скорость выполнения примера большой компьютерной сети.
1 ВВЕДЕНИЕ
Дискретно-событийное моделирование – это мощная вычислительная парадигма, позволяющая разработчикам модели изучать возможное поведение многих видов дискретных систем. Некоторые приложения дискретно-событийного моделирования требуют, чтобы модели вычислялись очень быстро. Например, когда моделирование используется в основе оптимизационного решения, ускорение рассчитываемой модели оказывается важнее, чем исследование пространства решений. Еще более важными являются применения, где дискретно-событийное моделирование используется в системе управления реального времени. Часто моделирование должно выполнять быстрее обычного времени, это необходимо, например, в случаях, где результаты многократных решений управления должны быть вычислены и сравнены. Пример этого приведен в статье (Ye, Kaur, Kalyanaraman, Kenneth, Vastola,and Yadav 2002), где моделирование в реальном времени используется для принятия решения выбора входов протокола маршрутизации OSPF.
Сетевая защита – это готовая область применения моделирования "быстрее реального времени". Легко представить себе систему управления, рассматривающую повторную маршрутизацию, декомпозицию и/или профилактические решения, как признак роста кибератак. Имитационная модель может работать через оценки стоимости/прибыли/рисков рассматриваемых действий, используя, вероятно, сложный показатель для поиска эффективного ответа. Однако моделирование "быстрее реального времени" больших сетевых моделей требует активных методов как в моделировании, так и в стратегии выполнения.
Мы рассматриваем производительность симулятора, исходя из "базиса" пакетно-ориентированного моделирования. Здесь большинство нагрузок содержат приписывающие задержки к пакетам, двигающимся по сети, задержки являются функциями установки в очередь на маршрутизаторе и обработки пакетов через стек протоколов. Пакет, двигающийся между двумя узлами через 4 маршрутизатора, содержит по меньшей мере 6 событий пакетов от начальной передачи до последнего приема (одно событие только на посылку и одно на прием, 4 события последовательного приема и посылки). Строго говоря, пакетно-ориентированное моделирование реализовано внутри ядра моделирования, как одно дискретное событие, включающее в себя вычислительное действие, применяемое к члену списка событий с наименьшей будущей отметкой времени. Поэтому мы используем показатель "базиса" скорости производительности симулятора, для которого ядро моделирования вычисляет "события ядра". Мы осознаем то, что данное представление зависит от вопроса размера в той мере, как стоимость доступа к динамически распределяемой памяти зависит от числа элементов в динамической памяти; мы также осознаем, что существует зависимость от вычислительного объема работ, связанного с выполнением каждого события. Тем не менее, данная идея предоставляет полезный "базис", который в рамках данного ядра моделирования может показать чувствительность проблемы размера.
Чувствительность потока данных – это хороший показатель размера модели. Ситуация моделирования 10 000 сетевых устройств за время более быстрое, чем реальное время, при слабой загрузке трафика сильно отличается от моделирования той же сети при интенсивной загрузке. Общая скорость событий пакетов на данной топологии описывает скорость (за время моделирования), за которую состояние сети изменяется. Реализация осуществляется "быстрее реального времени", если изменения состояния, сделанные с обычной скоростью, превышают среднюю скорость событий пакетов, используя те же единицы времени. К примеру, рассмотрим модель с 500 потоками трафика, где нагрузка на поток составляет 10 пакетов в секунду, а среднее число маршрутизаторов на пути пакета равно 3. Это значит, что скорость пакетов равна 50 пакетов за секунду на каждый поток со средней скоростью событий пакетов в 25 000 событий пакетов в секунду. Эта модель может быть запущена в 4 раза быстрее реального времени на ядре моделирования, выполняя 100 000 событий ядра в секунду.
Однако, если мы ограничиваем себя строгим пакетно-ориентированным представления исключительно на последовательном ядре моделирования, наша возможность моделировать "быстрее реального времени" также ограничена скоростью событий ядра. Для того, чтобы управлять большими моделями, необходимо использовать более абстрактные представления моделей, которые могут влиять на состояние модели, а также использовать параллельное выполнение.
Эта статья описывает как наша реализация интерфейса SSF (называемого iSSF) может столкнуться с проблемами моделирования "быстрее реального времени", используя комбинации абстракций модели и параллелизм. Мы разрабатываем простые аналитические модели, которые помогают управлять выбором абстракций для достижения целей выполнения "быстрее реального времени", и демонстрируем их возможности выполнения "быстрее реального времени" на большой сетевой модели.
2 SSF
Масштабируемая структура моделирования SSF определяет интерфейс API для ядра моделирования, допускающего высокопроизводительное широкомасштабное моделирование систем. SSF имеет описания а Java и C++ с различными реализациями на обоих языках. API определяет 5 базовых класса. Класс Entity (объект) служит контейнером для переменных состояния модели, вычислительных процессов и точек соединения. Класс Process (процесс) определяет вычислительный поток, который приостанавливается и возобновляется процессно-ориентированным способом. Process быть приостановлен для ожидания входа на именованный канал (или множество каналов). Классы inChannel (входной канал) и outChannel (выходной канал) определяют конечные точки связи; экземпляры класса Event (событие) посылаются объектам outChannel, которые появляются (после установки пользователем задержки моделирования) на одном или нескольких объектах inChannel. Полный API может быть получен по ссылке www.ssfnet.org.
SSF определяет нижний уровень возможностей ядра моделирования. Пользователи могут (и делают это) разрабатывать модели, непосредственно используя API, однако можно определять структуры с помощью специфичных для предметной области абстракций и реализовывать эти абстракции в общих библиотеках. Такие структуры разрабатываются для специальных беспроводных сетей связи и высокопроизводительной вычислительной архитектуры. SSFNet – это специализированная структура для моделирования проводных компьютерных сетей. Модульность и объектное ориентирование – это характеристики, поддерживающие масштабируемость моделирований. SSFNet использует язык моделирования предметной области (Domain Modelling Language – DML) для описания и настройка моделирования сети. DML представляет собой простой список пар атрибут-значений, которые определены рекурсивно. Ключевое слово (атрибут), которое будет распознано специализированным анализатором, является строкой, связанной с некоторым значением или списком (заключенного в квадратные скобки) пар атрибут-значений, которые сами могут представлять собой списки значений. Компьютерная сеть может быть описана списком устройств, где каждое устройство имеет список атрибутов, таких как характеристики, списком узлов, где узлы имеет список потоков, а каждый поток описывает источника, получателя, входную скорость потока. В DML уровень абстракций, связанный с потоком, можно также определить с помощью нескольких атрибутов. Атрибуты по умолчанию определяют поток (UDP или TCP) как пакетно-ориентированный поток. Когда встречается атрибут, заданный не по умолчанию, этот атрибут определяет, что трафик является динамическим. Изнутри это означает, что поток может быть представлен как множество кусочных постоянных функций скорости. Для определения количества байтов потока трафика, проходящих через некоторую точку в сети за время моделирования на промежутке [a, b], объединяется функция скорости, наблюдаемая в точке, на периоде дискретизации [a, b]. Как рассматривалось в статье (Kesidis, Singh, Cheung, and Kwok 1996, Nicol, Goldsby, and Johnson 1999, Nicol 2001) это представление может быть вычислено более эффективно, чем с использованием пакетно-ориентированного подхода. Дискретные события возникают только тогда, когда скорость пакетов изменяется, например, из-за установки в очередь или из-за потерь. Вычислительная эффективность возникает в случае, когда скорость сильно не изменяется, при этом изменяется только одно событие. В случае TCP это происходит после того, как поток вошел в режим предотвращения перегрузки и окно перегрузки достаточно велико.
Наш опыт с TCP (Nicol 2001, Nicol and Yan 2003) показывает, что обычные условия для данного подхода могут уменьшить вычислительную нагрузку на порядок. Может быть нам следует сказать, что только на порядок, так как наше внимание уделено детализации работы стоимостных TCP-механизмов, по крайней мере, на начало и конец каждого TCP-цикла. Уменьшение нагрузки с UDP потоками может быть довольно значительным, по меньшей мере для "долгоживущих" потоков. Однако, в условиях перегрузки еще возможно получить показатели событий изменения с нескольких потоков. В разделе 3 рассматривается этот феномен и некоторые детали.
Третий уровень абстракция применим для совокупного описания фоновых потоков. Это потоки, которые в совокупности и в соответствии масштабу времени не затрагиваются потоками, выбранными для представления более точно. Однако, так как потоки с низким разрешением представляют поток данных, они должны влиять и на потоки с высоким разрешением. Этот результат может быть получен с маршрутизаторов с помощью простого алгоритма вычитания доступной пропускной способности на связях, несущих потоки данных. Так, вместо того, чтобы моделировать 1000 пакетно-ориентированных потоков, мы могли бы объяснить потребление полосы пропускания 990 из них, периодически изменяя полосу пропускания, доступную 10 потокам с высоким разрешением.
Существует множество способов отобразить модель с низким разрешением. С целью сравнения с потоками других разрешений мы приняли метод, согласно которому отдельный поток, называемый в DML динамически изменяемым, является нечувствительным. DML-файл содержит программу изменений скорости, введенных на узле в сети. Рассмотри фрагмент ниже:
traffic [
pattern [
server 10:0:0 # src host (NHI coordinates)
schedule [ # one @ update
time 0 # update time
target [ # one @ dest
dest 11:1:0 # dest host
rate 300 # flow (Mbps)
]
target [ ... ] # other dest
]
schedule [ ... ] # other update scheds
]
]
Работая "изнутри наружу", target (цель) описывает получателя как поток к этому получателю. Получатель и скорость являются атрибутами цели. Shedule (программа) – это список целей, указывающих на начало моделирования для потоков, описанных целями. Pattern (шаблон) определяет хост и список программ, связанных с этим хостом. Traffic (поток данных) – это список, описывающий список шаблонов. Обычно в сети содержится один список потока данных. Список программ неявно описывает UDP-потоки. Поэтому, все, что нам нужно сделать, так это определить, что поток динамически изменяется и является нечувствительным, он служит для добавления к цели описания атрибутов:
target [ # one @ dest
dest 11:1:0 # dest host
rate 300 # flow (Mbps)
fluid on
insensitive on
]
ССЫЛКИ
- Kesidis, G., A. Singh, D. Cheung, and W. Kwok. 1996, Nov.. Feasibility of fluid event-driven simulation for ATM networks. In IEEE Globecom 1996.
- Moy, J. 1998. OSPF: Anatomy of an internet routing protocol. Addison-Wesley.
- Nicol, D., M. Goldsby, and M. Johnson. 1999, Oct.. Fluid-based simulation of communication networks using SSF. In Proceedings of the 1999 SCS European Simulation Conference. Erlangen, Germany.
- Nicol, D. M. 2001, December. Discrete-event fluid modeling of TCP. In Proceedings of the 2001 Winter Simulation Conference. Arlington, VA.
- Nicol, D. M., and G. Yan. 2003. Discrete-event fluid modeling of TCP for background traffic. Submitted for publication.
- Ross, H. 1983. Stochastic processes. New York: Wiley.
- Ye, T., H. T. Kaur, S. Kalyanaraman, Kenneth, S. Vastola, and S. Yadav. 2002. Dynamic optimization of OSPF weights using online simulation.
|