При построении распределенной АСУ можно исходить из разныx уровней определенности ее структуры. В зависимости от выбранного уровня определённости приходится решать одну из трех задач формулируемых последовательно.

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

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

3) Структурный граф АСУ построен и его параметры заданы; иными словами, аппаратура и её размещение выбраны. Требуется оптимально распределить операции обработки между узлами базовой сети либо установить протокол их динамического распределения.

Задачу 1 назовем общей задачей оптимального проектирования распределенной АСУ. Это - нелинейная комбинаторная задача. Уже при пяти-шести узлах базовой сети высокая размерность, обусловленная числом допустимых комбинаций переменных и необходимостью учета многочисленных ограничений, не позволяет строго решить общую задачу. Поэтому обычно для решения подобных задач применяются декомпозиционные процедуры, разлагающие общую задачу на ряд связанных между собой частных подзадач.

Опыт практической разработки распределенных АСУ еще незначителен, однако стоящие здесь задачи во многом сходны с задачами, которые решаются при разработке сетей ЭВМ иного назначения, а в этой области за последние 10 - 15 лет уже накоплен значительный опыт как для сетей, распределенных по обширной территории, так и для локальных сетей. При проектировании сетей ЭВМ чаще всего выделяют следующие подзадачи:

А. Выбор оптимальной топологии вычислительной сети.

В. Выбор аппаратуры обработки данных.

С. Оптимальное распределение данных и программ по вычислительной сети.

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

Несмотря на сложность общей задачи проектирования вычислительной сети в ряде работ делаются попытки решения задачи без декомпозиции ее на подзадачи. В некоторых работах две из трех подзадач А - С объединяются в одну. Естественно, что ввиду огромной размерности этих задач такие попытки осуществляются успешно, если благодаря вводимым при постановке ограничениям удается выделить достаточно узкий класс структур сети, удовлетворяющих этим ограничениям.

Характеристики сети передачи и аппаратуры обработки данных, булевы переменные, характеризующие распределение данных и программ по сети, параметры самих данных и программ выступают в качестве переменных и ограничений единой задачи оптимального размещения вычислительных центров в отраслевых АСУ. Решение достигается путем значительного сокращения перебора благодаря введению достаточно жестких ограничений. Выбор топологии в этих постановках ограничен заданием так называемого графа возможных связей, для которого исходя из ограничений на показатели качества обслуживания рассчитываются матрицы стоимости каналов связи и матрицы стоимости передачи информации между всеми вершинами.

Оптимизация сети осуществляется при заданном распределении данных и программ по узлам обработки данных. Ввиду большей информационной связности процессов АСУ по сравнению с отраслевыми АСУ такое эвристическое априорное распределение в АСУ может быть оправдано только для программ обработки некоторых простых видов запросов. Например, если результат обработки в АСУ требуется практически в том месте, где собираются исходные данные, то естественно размещение программы обработки этих данных в процессоре, расположенном в непосредственной близости от места сбора данных. Это приводит к повышению надежности передачи данных. При этом может достигаться и экономия на самой аппаратуре передачи данных. Впрочем, эвристическое распределение сложных прикладных программ, требующих сбора данных от территориально удаленных друг от друга источников информации, может привести к решению, сильно отличающемуся от оптимального.

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

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

MaxE_0=max (E-Q/T₀) (64)

Основным же критерием функционирования АСУ должна быть максимальная эффективность выполнения ею предписанных ей функций. Эта эффективность характеризуется средней экономией, приносимой АСУ в единицу времени.

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

алгоритм топология сеть вычислительная

На уровне, следующем за средней экономией, располагаются так называемые частные эффективности Е_i - средние значения эффективности выполнения функций АСУ. На третьем уровне дерева эффективностей располагаются факторы, оказывающие основное влияние на частные эффективности: прежде всего надежность выполнения функций, а также запаздывание в реализации функций, точность реализации функций. Пожалуй, наиболее практично в качестве критериев функционирования АСУ использовать максимум (минимум) некоторой функции от показателей третьего уровня дерева эффективностей, например минимум суммы взвешенных значений запаздывания в реализации функций. При этом веса выбираются или экспертами, или в соответствии с функциями штрафов f (ф_i), где ф_i - запаздывание в реализации i-й функции, изменяющееся от нуля до момента времени ф_0i когда окончание реализации данной функции равнозначно ее невыполнению (рис. 5.5). В качестве другого оптимизируемого функционала можно предложить максимум минимального показателя надежности; согласно этому критерию повышается вероятность предотвращения невыполнения функции, надежность реализации которой имеет минимальное значение.

2. Методы оптимального проектирования (алгоритмы синтеза) вычислительной сети

Рис. 5.6. Схема алгоритма синтеза распределённой АСУ

Оптимальному проектированию топологии сетей ЭВМ посвящена обширная литература, основываясь на которой, можно предложить методы и модели, подходящие для проектирования распределенных АСУ.

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

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

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

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

Надежность сети ЭВМ можно определить так способность сети обеспечить непрерывную связь между всеми действующими парами узлов. Для измерения надежности сети обычно пользуются понятием связности сети. Сеть называется м - связной, если для каждой пары узлов существует минимум м связывающих их и непересекающихся путей. Иными словами, чтобы некоторая пара узлов сети оказалась несвязной, должно отказать не менее ц вершин и (или) ребер сети.

Для распределенной АСУ характеристика надежности в виде-связности представляется недостаточной, в связи с чем для характеристики надежности выполнения функций вводятся показатели готовности и интенсивности отказов. Задача их вычисления гораздо более трудна, чем вычисление связности сети, так как связность определяется только конфигурацией сети, а для вычисления коэффициентов готовности и интенсивности отказов нужно знать и дисциплину резервирования, определяемую структурой распределенной АСУ, протоколами обмена между узлами сети, организацией программного обеспечения АСУ.

Особенности топологического проектирования распределенных АСУ по сравнению с сетями ЭВМ состоят и в разных порядках размерности соответствующих задач. Размерность терминальной сети в распределенных АСУ может иметь тот же порядок, что и в сетях ЭВМ, размерность же базовой сети может колебаться всего от нескольких узлов до нескольких десятков (последнее лишь в исключительных случаях). Поэтому средняя размерность базовой сети распределенных АСУ меньше, чем сети ЭВМ, а это может упростить оптимальное проектирование. В то же время АСУ могут повторно проектироваться для аналогичных технологических процессов, и, как правило, чем меньше сама АСУ, тем больше ее тираж, следовательно, тем тщательнее нужно добиваться оптимума при ее проектировании. Поэтому следует считать обоснованным применение строгих математических методов оптимизации при топологическом проектировании распределенных АСУ при условии, конечно, возможности решения задачи по таким методам в приемлемые для разработки сроки.

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

матрица тяготения (траффика), характеризующая интенсивность

обмена сообщениями для каждой пары узлов сети;

характеристики каналов связи;

число узлов сети;

граф возможных связен между узлами сети,

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

Применение строгих методов оптимального топологического проектирования вычислительных сетей крайне затруднено в связи с большой размерностью и целочисленностью задачи. Например, при числе узлов, равном 10, число переменных, входящих в модель, равно примерно 10⁴. Задачу целочисленного программирования такой размерности невозможно решить в реальные сроки. Наиболее распространенные строгие методы оптимизации топологии вычислительной сети основаны на принципе ветвей и границ, хотя достижение в реальное время оптимального решения этим методом может быть получено для сетей с числом узлов не более десяти. Принцип ветвей и границ, применяется для оптимизации топологии межцентровой распределенной сети передачи данных. Каждой вершине дерева ветвлений сопоставляется подмножество ветвей, уже включенных в искомую сеть; подмножество ветвей, запрещенных для включения в искомую сеть; подмножество ветвей, для которых еще не принято решение об их включении в сеть. При ветвлении из активной вершины проводятся две дуги: одна из них предопределяет включение в сеть некоторой дуги, другая запрещает его.

Ввиду перечисленных выше причин, затрудняющих применение строгих методов, развиваются эвристические методы топологической оптимизации.

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

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

Контрольные вопросы