Основы математического моделирования

Размещено на http://www.allbest.ru/

КОНТРОЛЬНАЯ РАБОТА

ОСНОВЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ

Содержание

Введение

Основные понятия сетевого моделирования

Цели сетевого моделирования

Параметры процесса моделирования

Подходы к процессу моделирования

Оптимизация сетевого моделирования

Заключение

Используемая литература

Введение

В 60-70-е гг. XX в. теория сетевого планирования и управления широко применялась в нашей стране. Однако позднее к этой теории стали относиться сдержаннее, что объясняется рядом недостатков СПУ.

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

И во-вторых, что наиболее существенно и неустранимо, при формировании сетевых планов необходимо участие высококвалифицированных специалистов, хорошо знающих процессы в системе (эту работу нельзя поручить техническим работникам, которые полезны лишь при оформлении сетевых графиков и об работке результатов оценки). При этом по результатам исследования оказалось, что доля «ручного» труда ЛПР при разработке сетевого графика составляет, по оценкам специалистов, до 95% от общих затрат времени на анализ ситуаций и процессов. Эти недостатки явились одной из причин того, что впоследствии теория СПУ сохранилась только для планирования одно направленных производственных процессов типа конвейерных и т.п. Однако привлекательность применения графических методов привела к тому, что для отображения различных ситуаций, не подчиняющихся ограничениям однонаправленности графа, был предложен термин сетевое моделирование (см.), снимающий требование однонаправленности. Позднее возник ряд методов статистического сетевого моделирования с использованием вероятностных оценок графов.

Для снижения доли «ручного» труда полезно сочетать графические представления с лингвистическими и семиотическими, разрабатывая языки автоматизации формирования сетевой модели. На основе такого сочетания методов возникли новые направления - структурно-лингвистическое моделирование (см.), графо'Семиотическое моделирование и т.п.

Основные понятия сетевого моделирования

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

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

Если рассматриваемые пары вершин являются упорядоченными, т.е. на каждом ребре задается направление, то граф называется ориентированным; в противном случае - неориентированным. Последовательность неповторяющихся ребер, ведущая от некоторой вершины к другой, образует путь. Граф называется связным, если для любых двух его вершин существует путь, их соединяющий; в противном случае граф называется несвязным. В экономике чаще всего используется два вида графов: дерево и сеть. Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями. Сеть - это ориентированный конечный связный граф, имеющий начальную вершину (источник) и конечную вершину (сток). Таким образом, сетевая модель представляет собой граф вида "сеть".

В экономических исследованиях сетевые модели возникают при моделировании экономических систем и процессов методами сетевого планирования и управления (СНУ).

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

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

Основными понятиями СМ являются следующие: работа, событие, путь. Работа характеризует материальное действие, требующее использования ресурсов, или логическое, требующее лишь взаимосвязи событий. При графическом распределении работа изображается стрелкой, которая соединяет два события. Ома обозначается парой заключенных в скобки чисел (i,j), где i - номер события, из которого работа выходит, a j - номер события, в которое она входит. Работа не может начаться раньше, чем свершится событие, из которого она выходит. Каждая работа имеет определенную продолжительность t(i,j). К работам относятся также такие процессы, которые не требуют ни ресурсов, ни времени выполнения. Они заключаются в установлении логической взаимосвязи работ и показывают, что одна из них непосредственно зависит от другой и не может выполняться, прежде чем эта другая будет завершена; такие работы называются фиктивными и на графике изображаются пунктирными стрелками.

Событиями называются результаты выполнения одной или нескольких работ. Они не имеют протяженности во времени. Событие свершается в тот момент, когда оканчивается последняя из работ, входящая в него. События обозначаются одним числом и при графическом представлении СМ изображаются кружком (или иной геометрической фигурой), внутри которого проставляется его порядковый номер (i = 1, 2,... N). В СМ имеется начальное событие (с номером 1), из которого работы только выходят, и конечное событие (с номером N), в которое работы только входят.

Путь в СМ - это цепочка следующих друг за другом работ, соединяющих начальную и конечную вершины, например, в приведенной на рис. 3.7 модели путями являются L1 = (1, 2, 5), L2 = (1, 4, 5) и др. Продолжительность пути определяется суммой продолжительностей составляющих его работ. Путь, имеющий максимальную длину, называют критическим и обозначают Lкр, а его продолжительность - tкр Работы, принадлежащие критическому пути, называются критическими. Их несвоевременное выполнение ведет к срыву сроков всего комплекса работ.

Цели сетевого моделирования

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

Исходные данные о структуре и параметрах сети берутся из базы данных. Ряд параметров сети задаются конфигурационным файлом (профайлом). Сюда могут записываться емкость буфера интерфейса и драйвера, время задержки обработки запроса (хотя в общем случае эта величина может также иметь распределение) и т.д.. К таким параметрам относятся также: MTU, MSS, TTL, window, некоторые значения таймаутов и т.д.

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

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

Распределение по проценту времени использования каждого из узлов для того или иного вида приложений.

Распределение узлов сети по их активности.

Распределение по используемым протоколам

Распределение по длинам пакетов.

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

Параметры процесса моделирования

Ни один проект крупной сети со сложной топологией в настоящее время не обходится без исчерпывающего моделирования будущей сети (речь, разумеется, идет не о России). Программы, выполняющие эту задачу, достаточно сложны и дороги. Целью моделирования является определение оптимальной топологии, адекватный выбор сетевого оборудования, определение рабочих характеристик сети и возможных этапов будущего развития. Ведь сеть, слишком точно оптимизированная для решений задач текущего момента, может потребовать серьезных переделок в будущем. На модели можно опробовать влияние всплесков широковещательных запросов или реализовать режим коллапса (для Ethernet), что вряд ли кто-то может себе позволить в работающей сети. В процессе моделирования выясняются следующие параметры:

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

Время отклика основных серверов в самых разных режимах, в том числе таких, которые в реальной сети крайне нежелательны.

Влияние установки новых серверов на перераспределение информационных потоков (Proxy, Firewall и т.д.).

Решение оптимизации топологии при возникновении узких мест в сети (размещение серверов, DNS, внешних шлюзов, организация опорных каналов и пр.).

Выбор того или иного типа сетевого оборудования (например, 10BaseTX или 100BaseFX) или режима его работы (например, cut-through, store-and-forward для мостов и переключателей и т.д.).

Выбор внутреннего протокола маршрутизации и его параметров (например, метрики).

Определение предельно допустимого числа пользователей того или иного сервера.

Оценка необходимой полосы пропускания внешнего канала для обеспечения требуемого уровня QOS.

Оценка влияния мультимедийного трафика на работу локальной сети, например, при подготовке видеоконференций.

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

Результаты моделирования должны иметь точность 10-20%, так как этого достаточно для большинства целей и не требует слишком много машинного времени. Следует иметь в виду, что для моделирования поведение реальной сети, надо знать все ее рабочие параметры: длины кабеля от концентратора до конкретной ЭВМ, задержки используемых кабелей, задержки концентраторов (этот параметр часто отсутствует в документации и его придется брать из документации на сетевой протокол, например из IEEE 802.3). Параметры могут быть определены и прямым измерением. Чем точнее вы воспроизводите поведение сети, тем больше машинного времени это потребует. Кроме того, вам предстоит сделать некоторые предположения относительно распределения загрузки для конкретных ЭВМ и других сетевых элементов, задержек в переключателях, мостах, времени обработки запросов в серверах. Здесь нужно учитывать и характер решаемых на ЭВМ задач. www/ftp-сервер или обычная персональная рабочая станция создают различные сетевые трафики. Определенное влияние на результат могут оказывать и используемые ОС. В случае моделирования реальной сети можно произвести соответствующие измерения, что иногда тоже не слишком просто. Учитывая сложность моделирования на одной ординарной ЭВМ, следует ограничиваться моделированием не более чем одной минуты для каждого из наборов параметров (этого времени достаточно для копирования практически любого файла через локальную сеть). Исключение может составлять моделирование внешнего трафика, но в этом случае весь локальный трафик должен рассматриваться как фоновый.

Подходы к процессу моделирования

Возможны разные подходы к моделированию.

Классический подход заключается в воспроизведении событий в сети как можно точнее и поэтапное моделирование последствий этих событий. В реальной жизни события могут происходить одновременно в различных точках сети. По этой причине для моделирования идеально подошел бы многопроцессорный компьютер, где можно воспроизводить любое число процессов одновременно. В любом случае необходимо выбрать некоторый постоянный временной интервал и считать, что события произошли одновременно, если расстояние между ними меньше этого интервала. Для сетей типа ethernet таким временным интервалом может быть бит-тайм (для 10-мегагбитного ethernet это 100нс). Понятно, что это уже отступление от реальности (ведь задержки в сетевом кабеле не кратны этому времени), но не слишком значительное. Надо сказать, что такого рода предположений при моделировании приходится делать много. По этой причине крайне важно сравнивать результаты моделирования с данными, полученными для реальной сети. Если отличия лежат в пределах 10-20%, можно считать, что сделанные предположения не увели программу слишком далеко от жизни и ею можно пользоваться для расчетов. Рассмотренный выше подход пригоден для моделирования сетевого коллапса, так как скорость расчетов здесь зависит от числа узлов и почти не зависит от сетевой загрузки.

Другим подходом может стать метод, где для каждого логического сегмента (зоны столкновений) сначала моделируется очередь событий. При этом в каждой рабочей станции моделируется последовательность пакетов, ожидающих отправки. Эта очередь может время от времени модифицироваться, например, при получении ЭВМ пакета извне и необходимости послать на него отклик. После того как такая очередь для каждого сетевого объекта (сюда помимо ЭВМ входят мосты, переключатели и маршрутизаторы) построена, запускается программа отправки пакетов. При этом выбирается самый первый по времени пакет (ожидающий дольше других) и проверяются для него условия начала передачи (отсутствие несущей на входе сетевого интерфейса в данный момент и в течение 9,6 мксек до рассматриваемого момента - 96 тайм-битов). Если условия отправки выполнены, он "посылается" в сеть. Вычисляются моменты достижения им всех узлов данного логического сегмента, проверяются условия его столкновения с другими пакетами. Следует заметить, в этом подходе снимаются ограничения "дискретности" временной шкалы, использованной в предыдущем "классическом" подходе. Этот подход позволяет заметно ускорить расчеты при большом числе узлов, но малой загрузке сети. Проблемы реализации данной концепции моделирования связаны с обслуживанием довольно сложного списка, описывающего очередь пакетов, ожидающих отправки. В структуру этого списка включается и описание ситуации в сети на данный временной период. Дополнительные трудности сопряжены с поведением мостов, переключателей и маршрутизаторов, так как они могут вставлять в очередь дополнительные элементы, требующие немедленного обслуживания. Аналогичные вставки в очередь будут вызывать полученные станцией пакеты ICMP или TCP, требующие откликов. Причем такое вставление в очередь асинхронно по отношению к процедуре "отправки" пакетов. Очередь для всей локальной сети может быть единой, тогда пакеты разных логических сегментов должны быть помечены определенными флагами. При переходе из сегмента в сегмент флаг будет меняться. Возможно и построение независимых очередей для каждого из логических сетевых сегментов. сетевой моделирование математический

Оптимизация сетевого моделирования

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

Оптимизация может осуществляться за счет совершенствования выполнения работ критического пути;

изменения топологии сети (изменение последовательности выполнения работ);

детализации работ (когда сложные работы можно разбить на несколько более простых) и др.

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

частная

комплексная

оптимизация по времени

оптимизация по ресурсам

оптимизация по стоимости

оптимизация по потоку

Частная оптимизация предполагает улучшение сетевого графика только по одному критерию.

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

Заключение

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

Каждый из продуктов действительно имеет свою собственную "экологическую" нишу. Одни средства рассчитаны на управление локальными сетями, а другие предназначены для администраторов территориально-распределенных сетей. Одни просто позволяют строить схемы сетей и обладают ограниченными возможностями моделирования, другие же способны производить сложный анализ глобальных сетей.

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

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

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

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

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

Используемая литература

1. Абланская Л. В., Бабешко Л. О., Баусов Л. И. Экономико-математическое моделирование: М.: Экзамен, 2006г. - 800с.

2. Баканов М. И., Шеремет А. Д. Теория экономического анализа: Учебник. - М.: Финансы и статистика, 1997.

3. Дрогобыцкого И. Н Экономико-математическое моделирование: М.: Экзамен, 2004г. - 323с.

4. Казаков О. Л., Миненко С. Н., Смирнов Г. Б. Экономико-математическое моделирование: учебно-методическое пособие. - М.: МГИУ, 2006. - 136 с.

5. Конюховский П. В Математические методы исследования операций в экономике: С-Петербург: Питер 2003г. - 208 с.

Размещено на Allbest.ru