Оптимизация сетей связи

1.3 БЛОКИ ОПТИМИЗАЦИИ

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

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

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

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

необходимостью целочисленного решения, вызванной дискретностью ряда технических средств;

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

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

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

Рассмотрим задачу синтеза коммутируемой сети связи. Будем считать, что известны следующие данные:

структура G(V, U) первичной сети, где V — множество коммутационных узлов сети; U — множество линий связи сети;

матрица Y=|| || нагрузки, характеристики потоков заявок, структура приоритетов;

матрица S=|| || арендной платы за использование единицы пропускной способности (канала) между узлами i, , причем Sij — ступенчатая функция расстояния, не зависящая от i, j;

вероятности {q(i),q (u)} отказов узла и линии связи. ;

вероятности {P( )} аварийного или преднамеренного одновременного повреждения n1, узлов и m1 линий связи.

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

матрицы допустимых потерь (задержек);

матрицы допустимых потерь (задержек) при одновременном отказе n1 узлов и m1 линий связи;

ограничение l на максимальное число транзитов (переприемов) при передаче информации между каждой парой узлов сети;

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

При синтезе сети связи следует определить: структуру сети (граф сети), канальные емкости линий связи сети, коммутационные и кроссовые требования к узлам сети, требуемые емкости ЗУ на узлах сети (для сетей с пакетной коммутацией и коммутацией сообщений);

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

В качестве критерия оптимальности синтеза сети связи при­мем арендную плату за суммарную канальную емкость линий связи сети при отсутствии ограничений на емкость линий.

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

Анализ задачи синтеза распределенных сетей связи позволяет выделить следующие основные частные задачи проектирования:

ГС — генерация начальных структур сети для последующего этапа локальной оптимизации. Исходными данными ГС являются число п узлов синтезируемой сети и требования на иерархичность сети, результатом — некоторый граф сети на п вершинах, удовлетворяющий требованиям на иерархичность. Как правило, без учета требований на иерархичность в качестве исходной структуры принимаются минимальное (по расстояниям, по стоимости, при учете нагрузки Y) связывающее дерево, звездный граф, полный граф, пустой граф, граф, ребра которого соответствуют ненулевым значениям матрицы Y, и т.д.;

AW-—анализ сети на связность по параметру ω или λ (выбор ω или λ определен условиями задачи синтеза). В общем случае необходим анализ на любой требуемый показатель надежности;

Ad — анализ сети на метрическое свойство (максимальное число переприемов);

CW — синтез сети по параметру ω или λ. Анализ и синтез графов со степенью связности больше трех не представляет практического интереса, что объясняется возможностями систем управления по выбору путей передачи информации;

Cd — синтез сети по параметру d;

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

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

В случае использования методов замены (удаления, добавления) ветвей необходимы следующие этапы:

ВК — выбор ветви-кандидата на замену в соответствии с определенным критерием замены;

ЗВ — собственно замена (удаление, добавление) ветви.

Одним из важнейших этапов синтеза коммутируемой сети связи является СУ — статистическое моделирование процесса функционирования сети при различных законах управления сетью связи. В настоящее время не существует методов расчета сети связи, адаптивных к законам управления ее ресурсами и нагрузкой. Более того, не существует и общих методов расчета канальных емкостей сети для произвольных процедур выбора путей передачи информации. В связи с этим представляют существенный интерес программы имитационного моделирования, позволяющие определить показатели качества обслуживания абонентов сети связи при различных законах управления и процедурах выбора путей передачи информации. К ним относятся, например, программы имитации метода рельефов [8], имитации игрового способа выбора соединительного пути [28], имитации изоритмического управления сетями [130], имитации статической и динамической стратегии выбора путей [84] (программы [84, 130] моделируют сеть пакетной коммутации) и т. д. Программы статистической оценки качества обслуживания, как правило, определяют только интегральный показатель качества, так как для вычисления с одинаковой точностью всех дифференцированных критериев качества время моделирования, определяемое необходимой статистикой для потока минимальной интенсивности, слишком велико. В связи с этим получили распространение уже упоминавшиеся программы АС—анализа сети связи, позволяющие вычислять дифференцированные показатели качества обслуживания.

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

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

Естественно, что возможны различные последовательности процедур проектирования, но, учитывая, что ГС — инициальная процедура, СУ «альтернативна» АС, ЗВ непосредственно следует за. ВК. процедуре CW(Cd) предшествует процедура AW(Ad), процедуре PC — процедуры РП, Ad, Cd, процедуре СУ (АС) — AW, CW, PC, число возможных последовательностей процедур существенно уменьшается.

Полагая, что:

процесс синтеза сети связи является пошаговой итерационной процедурой, причем число шагов проектирования равно числу исходных структур сети, а число итераций в каждом шаге или определено заранее, или зависит от результата сравнения стоимостей вариантов сети [итерации прекращаются, если стоимость варианта сети на i-м шаге итерации больше стоимости варианта; сети на (i—1)-м шаге];

последовательность Ad, Cd, связанная с распределением потоков по индивидуальным и общим пучкам каналов сети связи должна выполняться после процедуры РП;

процедура замены ветвей производится в конце каждой итерации (с учетом того, что процедуры CW, Cd являются по сути процедурами замены — в данных случаях добавления);

процедура СУ или АС выполняется при каждой итерации; процедуры СУ и АС совместно выполняются в конце каждого шага проектирования;

наиболее целесообразной представляется последовательность процедур синтеза, представленная на рис. 3.1, где С — процедура представления структуры

сети связи, «стоимость» — процедура расчета суммарной стоимости канальных емкостей сети связи, 1 — счетчик числа итераций, 2 — счетчик числа начальных структур сети. Место последовательности A W, CW непосредственно перед РП или непосредственно после PC определяется типом предъявляемого варианта структуры. Предельные случаи: если С — дерево, то AW, CW следует за С, если С —полный граф, то A W, CW следует за PC. В соответствии с предлагаемой методикой синтеза основными процедурами проектирования являются процедуры ГС, AW, CW, РП, Ad, Cd, PC, АС, СУ и ЗВ.

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

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

При рассмотрении графа G(Y)(G(Y\ε)) в качестве исходной структуры процесса проектирования распределенной сети связи

*) Поскольку граф G(Y) для сетей связи общего назначения является, как правило, полносвязным, то его преобразование в граф G(У\ε) необходимо.

последовательность процедур синтеза сети представляется схемой рис. 3.2 [здесь: G(Y) — начальная структура].

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

определение процесса локальной оптимизации заключается в выборе алгоритмов процедур AW, CW, Ad, Cd и PC. Рассмотрим некоторые варианты решения этой задачи.

ЗОНИРОВАНИЕ СЕТИ

В общем случае решение проблемы синтеза распределенных сетей

связи методами замены ветвей (процедуры CW, Cd, РП, ЗВ) требует проведения 0(n³)—О(n⁶) вычислений, где n — число узлов сети, и для сетей, число узлов в которых превышает несколько сотен, не представляется возможным [63]. Одним из возможных путей уменьшения сложности проектирования являются представление синтезируемой большой сети как совокупности более мелких сетей (зон) и сведение решения задачи синтеза большой сети к решению задач синтеза сетей, ее составляющих (зоновых и межзоновых сетей). Второй причиной целесообразности разбиения (зонирования) сети связи является необходимость выделения зон управления сетью связи с локализацией внутри каждой зоны информации контроля и управления.

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

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

Число Nc блоков разбиения сети по структуре выбирается исходя из минимального объема проектирования и определяется [63] как , где n - общее число узлов синтезируемой сети;

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

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

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

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