Глава 4. ВОПРОСЫ ПРОЕКТИРОВАНИЯ СЕТЕЙ ПЕРЕДАЧИ ИНФОРМАЦИИ АСУ

4.1. ЗАДАЧИ СИСТЕМНОГО ПРОЕКТИРОВАНИЯ СЕТЕЙ

Общие сведения

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

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

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

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

Исходные данные при проектировании

Исходными данными для системного проектирования обычно являются следующие сведения:

1. Совокупность и характеристика объектов системы управления.

2. Требования системы управления к процессу обмена информацией.

3. Условия создания и функционирования сети.

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

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

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

Условия создания и функционирования сети могут включать такие сведения, как:

наличие первичной сети связи и ее структура;

параметры технических средств и их связь с экономическими затратами;

наличие внешних факторов, влияющих на функционирование сети.

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

по созданию новых образцов, либо номенклатурой серийной аппаратуры.

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

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

Общая характеристика задачи системного проектирования

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

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

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

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

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

В процессе решения задачи обычно определяются: число и координаты размещения узлов коммутации;

структура межузловых соединений; мощность линий связи и узлов коммутации; параметры надежности и живучести элементов.

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

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

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

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

Число вариантов размещения М узлов на территории, аппроксимированной дискретными координатными точками, равно

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

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

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

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

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

для заданного множества абонентов синтезируется связанная структура сети, минимизирующая затраты на соединительные линии, линии связи и узлы коммутации;

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

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

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

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

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

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

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

Содержание задачи состоит в следующем.

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

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

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

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

Задача оптимизации надежности элементов сети формулируется аналогично, однако, учитывая отсутствие источника целенаправленного воздействия, единственным критерием оптимальности является минимум затрат.

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

Прогнозирование потоков сообщений между абонентами сети

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

Таким образом, необходимо выбирать значения параметров потоков на основе информации, которая имеется в распоряжении

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

Для решения задачи прогнозирования потоков может быть использован принцип максимума неопределенности [5]. Сущность данного принципа состоит в выборе таких искомых параметров, которые являются наименее предубежденными, а следовательно, и наименее ошибочными с учетом имеющихся априорных сведений о системе. Количественной мерой неопределенности при выборе является энтропия, максимум которой по множеству наборов значений вероятностей и дает наименее ошибочное решение. При этом имеющаяся информация играет роль ограничений.

Если — искомый параметр потока сообщений между абонентами, а то величина может интерпретироваться как вероятность того, что произвольное сообщение, передаваемое в сети, принадлежит потоку от к Таким образом, в формализованном виде задача прогнозирования потоков может быть сформулирована следующим образом: найти значения при которых обеспечивается

где — множество возможных наборов значений ограниченное имеющейся информацией; — число абонентов.

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

где — коэффициенты, определяемые характером используемой информации.

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

где — неопределенные множители.

В соответствии с теоремой Лагранжа решение задачи (4.1) при ограничениях (4.2) максимизирует определяется системой уравнений

и имеет вид

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

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

При отсутствии какой-либо дополнительной информации, кроме общей нагрузки сети А, из (4.2) и (4.5) получим тривиальное решение

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

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

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

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

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

или

где километрическое расстояние между абонентами.

С учетом приведенных ограничений решение (4.5) преобразуется к виду

Подставляя (4.11) в ограничение (4.7), получаем

Отсюда

Вводя (4.13) в (4.11), найдем решение с неизвестными

Для вычисления используем (4.8) и (4.9). Подставляя в них (4.14), получаем систему из двух трансцендентных уравнений с двумя неизвестными:

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