Runtime balancing effect in distributed simulation model

The paper deals with study of the load distribution effect between computing nodes for simulation run-time of a distributed computer network model. Two main types of balancing are considered: computational load balancing and reduction of transmitted amounts of data. Simulation was performed on one computer, and distribution was carried out between the cores of one processor. Simulation experiments showed that the lack of balance in the amounts of data, transferred between parts of a distributed model, leads to decrease of the simulation speed by several times due to overhead charges for data transmission between logical processes because of MPI usage. Model run-time changing at uneven distribution of computational load depends to a large extent on the load, which is created by the applications running on the simulated network nodes. It is shown that a balanced model is performed much faster than unbalanced version even when using applications that do not require significant computing resources. Simulation time reduction can be achieved by model separation in such manner as to reduce amounts of data transferred between its parts and reduce variability of loads generated by applications in different logical processes.

section_content: Большие системы состоят из тысяч, десятков тысяч элементов и еще большего количества связей между ними. Такие системы характеризуются неоднородностью элементов (большим количеством раз-ВЛИЯНИЕ СБАЛАНСИРОВАННОСТИ НА ВРЕМЯ ИСПОЛНЕНИЯ РАСПРЕДЕЛЕННОЙ. . . Научно-технический вестник информационных технологий, механики и оптики, 2015, Том 15, № 1 102 личных типов элементов) и неоднородностью связей. Это приводит к тому, что классические математические методы становятся практически непригодными для описания и анализа больших систем [1]. Примером большой системы может быть компьютерная сеть провайдера или сеть крупного предприятия. Несмотря на то, что отдельные элементы или связи прекрасно описываются моделями дискретной математики или теории массового обслуживания [2], о системе в целом этого сказать нельзя. Естественной альтернативой является использование имитационного моделирования, позволяющего соединить между собой разнородные математические модели элементов системы [3]. 

Имитационное моделирование успешно используется для анализа систем различного масштаба [4]. Но при исследовании больших систем возникают специфические проблемы, требующие использования параллельного или распределенного моделирования и балансировки нагрузки [5] [6] [7] [8] [9] [10]. 

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

Уменьшение времени исполнения распределенной модели относительно последовательной зависит от того, насколько удачно пользователь разбил модель на подмодели до начала процесса моделирования. Однако предугадать нагрузку на узлы моделируемой сети или объем передаваемых данных по линиям связи довольно сложно, и в некоторых случаях необходим детальный анализ структуры моделируемой сети [12, 13]. Таким образом, пользователю сложно эффективно разделить модель, что приведет к увеличению времени выполнения модели. В ситуациях, когда параметры модели меняются в ходе моделирования, эффективно разбить модель перед запуском модельного прогона невозможно [14]. В этом случае необходимо использовать динамическую балансировку нагрузки в процессе моделирования. Цель настоящей работы -экспериментально оценить зависимость времени имитационного эксперимента от способа разбиения модели на логические процессы.
section_name: Введение

section_content: Система моделирования NS-3 служит для моделирования процессов, протекающих в компьютерных сетях [15]. В связи с этим внутреннее устройство системы во многом обусловлено этой спецификой, включая наличие различных стеков сетевых протоколов и передачу данных между узлами при помощи пакетов, структура которых полностью повторяет структуру реальных сетевых пакетов, что также делает возможным использование системы в реальных компьютерных сетях [16]. 

Модель в NS-3 состоит из узлов, выполняющих роль компьютеров, к которым подключаются сетевые адаптеры, которые, в свою очередь, соединяются при помощи каналов передачи данных. Для выполнения какой-либо полезной работы на узлы устанавливаются приложения, которые выполняют необходимую работу (генерация, обработка, прием данных) [17]. 

Распределение модели в NS-3 выполняется следующим образом: узлам при создании присваивается определенный номер, который соответствует номеру логического процесса (ЛП), в котором будет обрабатываться этот узел. ЛП -это последовательная часть модели, которая имеет собственный набор объектов, управляющую программу и часы локального времени. В ЛП происходит моделирование только тех процессов, которые относятся к узлам, привязанным к данному ЛП. При установке приложений на узлы учитывается то, к какому ЛП принадлежит данный узел, и приложения, создающие наибольшую вычислительную нагрузку, не дублируются между подмоделями и выполняются только в пределах своего ЛП. В отличие от приложений, все узлы модели и связи между ними создаются во всех ЛП, т. е. каждый ЛП содержит полную топологию моделируемой сети. Сделано это для упрощения процессов маршрутизации [18]. 

Связь логических процессов между собой осуществляется при помощи MPI (Message Passing Interface). Если канал, соединяющий два моделируемых узла, пересекает границы логических процессов, то пакет, передаваемый по этому каналу, упаковывается в сообщение MPI, передается сетевыми средствами операционной системы, в которой выполняется модель, и после приема пакета ЛП-адресатом извлекается из сообщения и преобразовывается в структуру пакета NS-3 для дальнейшей передачи по каналам связи.
section_name: Особенности распределенной системы моделирования NS-3

section_content: Для демонстрации результатов неэффективного разбиения модели был проведен ряд экспериментов. Были созданы сети сетчатой топологии различных размеров: 20×10, 40×10, 60×10. В каждой моделируемой сети было запущено различное количество приложений. Приложения делятся на два вида: генераторы и приемники трафика. Модель разбивалась на два логических процесса, каждый из которых содержал одинаковое количество моделируемых узлов. Генераторы трафика посылали данные на узлы, расположенные в том же ЛП (трафик между логическими процессами не передавался). Различное распределение приложений между логическими процессами позволяло создавать сбалансированную или несбалансированную распределенную модель. Каждое приложение-генератор создает равномерный поток UDPпакетов в направлении приемника. Скорость потока равна 1 Мбит/с, размер пакетов -512 Б. Генераторы Несбалансированность по объему передаваемых данных В предыдущем эксперименте в разных ЛП модели работало различное количество приложений, которые создавали разную нагрузку на вычислительные узлы. Модель была построена таким образом, что трафик между логическими процессами не передавался. Однако, так как для взаимодействия ЛП используется MPI, то пакеты, пересекающие границы ЛП, должны быть упакованы в сообщения MPI и переданы через сетевую инфраструктуру операционной системы. Это создает дополнительные накладные расходы и должно влиять на время выполнения модели [19, 20]. 

Для следующего эксперимента также были построены модели сетей сетчатой топологии (10×10, 20×20, 30×30), однако трафик между узлами-генераторами и приемниками пересекал границы ЛП (рис. 2). Модель построена так, чтобы в каждом ЛП было одинаковое количество приложенийгенераторов и приемников. Таким образом, исключается влияние количества приложений в логических процессах на время выполнения модели.
section_name: Несбалансированность по вычислительной нагрузке

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

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

Также показано, что изменение количества передаваемых данных между логическими процессами сильно влияет на время выполнения модели из-за значительных накладных расходов на передачу данных между логическими процессами. Для малых сетей соотношение между временем исполнения сбалансированной и несбалансированной модели достигло 9 раз. Для больших моделей (20×20 и 30×30) соотношение составило 2,2-2,5 раза. Связано это с тем, что в больших моделях значительную часть времени выполнения тратится на моделирование работы приложений. Таким образом, бóльшая часть времени работы логических процессов тратится на обработку приложений и передачу данных между узлами внутри отдельного логического процесса. 

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