Сеть связи

Первый фрагмент построен на базе ана-логового коммутационного оборудования. Второй фрагмент построен на аналого-вом и цифровом коммутационном оборудовании и третий фрагмент построен только на цифровом оборудовании с использованием ОКС№7.
Современный этап развития коммутационного оборудования телефонных сетей характеризуется:
использованием ОКС№7 как основной системы сигнализации;
большой абонентской емкостью оконечных станций (ОС);
возможностью организации распределенной структуры ОС со значи- тельным количеством подстанций и концентраторов;
интеграции разнородных услуг и служб.
Следует отметить, что в настоящее время развитие базововой сети осуще-
ствляется в основном за счет расширения емкости существующих АТС, а разви-тие сети электросвязи города в основном осуществляется за счет перехода к сети
NGN.
Соединительные линии, используемые на сети могут быть как односторон-него, так и двухстороннего занятия. Использование двухсторонних линий поз-воляет повысить пропускную способность этих линий за счет концентрации наг-рузки, так как линия двухстороннего занятия пропускает как исходящую, так и входящую нагрузку. Если качество обслуживания вызовов в прямом и обратном направлениях различное, то используются линии одностороннего занятия даже при применении ОКС№7. При связи цифровых ОС с аналоговыми станциями или узлами, а также аналоговых станций и узлов с цифровыми используются только линии одностороннего занятия.
Цифровая транзитная станция может одновременно выполнять функции око-нечной станции, узла входящего, узла исходящего сообщения. В некоторых слу-чаях транзитная станция ГТС может выполнять и функции АМТС.
Многофункциональное использование цифрового коммутационного оборудо-вания приводит к увеличению емкости (мощности) транзитной станции. Вслед-ствие чего существенно уменьшается стоимость одного порта проектируемой оконечно-транзитной станции (ОТС).
Настоящее время на ГТС ведется активная работа, связанная с внедрением
технологии NGN.

Принципы построения сельских телефонных сетей

Связь в сельской местности – это система электросвязи сельского админи-стративного района (САР). Для ее организации на территории района создается местная сельская первичная сеть (СПС). Эта сеть служит основой для создания сельских вторичных сетей, включая сеть ТфОП. Сельская телефонная сеть (СТС) представляет собой совокупность местных телефонных станций, межстанцион-ных соединительных линий, организуемых по физическим цепям, включая ВОЛС, и каналами различных систем передачи, включая PDH и SDH , абонентских линий и оконечных абонентских устройств. Сеть СТС предназначается для установления соединений в пределах САР и выхода абонентов на сети внутризоновой, междуго-родной и международной связи. В состав СТС входят технические средства теле-фонных сооружений населенных пунктов, отнесенных к сельской местности, а также райцентров, городов районного подчинения и поселков городского типа.
При выборе способа построения СТС необходимо знать основные особенности САР, на территории которого создается эта сеть. В общем случае, к этим особенностям можно отнести следующее:
низкая плотность населения;
значительная территория, охватываемая САР;
большое число населенных пунктов с незначительным числом жителей (менее 1000 человек);
меньшая потребность в современных услугах электросвязи, чем у жителей города;
наличие существенного информационного тяготения между периферийными населенными пунктами и райцентром, по сравнению с тяготением между периферийными населенными пунктами САР;
более сложные условия эксплуатации средств связи, чем в городе;
невозможность, в ряде случаев осуществления, телефонизации с использование проводных средств связи.
Указанные выше особенности приводят к тому, что:
средняя емкость сельских АТС много меньше средней емкости городских АТС;
среднее расстояние между АТС на СТС значительно превышает среднее расстояние между станциями ГТС;
среднее число СЛ в пучках между станциями СТС меньше, чем на ГТС;
разброс длин абонентских линий на СТС значительно больше, чем на ГТС.
Эти особенности СТС обуславливают более высокие, по сравнению с ГТС, капитальные вложения и эксплуатационные расходы по линейным и станцион-ным сооружениям в расчете на один номер емкости сети. Поэтому при проектиро-вании СТС предусматриваются следующие меры для повышения использования соединительных и абонентских линий:
применение радиального или радиально-узлового способа построения сети;
использование линий двухстороннего занятия;
увеличение норм допустимых потерь вызовов по сравнению с нормами потерь для ГТС;
использование универсальных СЛ, обеспечивающих все виды связи (местной, междугородной и внутризоновой);
применение спаренного включение телефонных аппаратов.
По назначению и месту расположения станции СТС делятся на следующие виды:
ЦС, расположеннная в районном центре, выполняющая одновременно функции телефонной станции районного центра и транзитного узла СТС. В ЦС включаются узловые станции (УС) и оконечные станции (ОС). Через ЦС осуществляется связь со спецслужбами и справочно-информационными службами, МТС райцентра и АМТС;
УС, расположенные в любых населенных пунктах сельского района с учетом технико-экономических соображений. Через УС осуществляется транзитная связь между включенными в нее ОС, а также между этими ОС и ЦС или другими УС (при использовании прямых путей на уровне УС);
ОС, расположенные в любых населенных пунктах сельского района. Стан-ции ОС включаются в ЦС или УС. Возможна организация прямых путей между ОС или ОС и другими УС. Сеть СТС, имеющая структуру ОС – ЦС получила название одноступенчатой. При наличии на СТС и УС, структура
сети называется двухступенчатой. Выбор схемы построения СТС (одноступенч-той или двухступенчатой) производится при проектировании на основе технико-экономического сравнения вариантов построения СТС. Для обеспечения необходимого качества и нормы по затуханию тракта телефонной передачи, УС и ЦС должны обеспечивать четырехпроводные соединения.
Связь станций СТС между собой может осуществляться по односторонним, двухсторонним, раздельным или общим для местной междугородной связи (универсальным СЛ). При внедрении ОКС№7, как правило, используются двухсторонние СЛ. Структурная схема СТС приведена на рис. 25.


Рис. 25. Схема СТС

Внедрение цифровых систем коммутации на СТС позволяет включить:
индивидуальные аналоговые двухпроводные линии непосредственно в
АТС, через цифровые концентраторы и абонентские мультиплексоры. Выбор включения тем или иным способом аналоговых абонентских линий определяется экономическими соображениями;
цифровые абонентские линии для реализации услуг N–ISDN;
линий радиотелефонной связи (системы Алтай, DECT, CDMA и др.);
использование многоточечного подключения цифровых АТС малой емкости или концентраторов в кольцевую распределительную цифровую систему передачи;
оптические кабели (при использовании соответствующих интерфейсов);
использование спутниковых систем передачи с учетом сложного географи-ческого и климатического положения САР, низкой плотности населения и отсутствие связи населенного пункта с сельской администрацией и РЦ.
обходные направления.
На рис. 26 представлена схема построения цифровой СТС.



Рис. 26. Схема построения цифровой СТС.

С экономической точки зрения рекомендуется организация одной цифровой ЦС на несколько САР. При этом одна СТС охватывает территорию нескольких сельских районов. В настоящее время, как и на ГТС, на СТС ведется активная работа по внедрению технологии NGN.

Принципы построения внутризоновой телефонной сети

Внутризоновая сеть объединяет местные сети зоны нумерации в единую зоновую сеть связи. Внутризоновая сеть представляет собой совокупность СЛ и каналов, обеспечивающих взаимодействие коммутационного оборудования раз-ных местных сетей между собой и с автоматической междугородной телефонной станцией (АМТС). Станция АМТС предназначена,с одной стороны, для организации внутризоновой связи, выполняя функции зонового узла, а с другой ,-для пропуска междугородного и международного трафика от/к местных сетей зоны нумерации. На сети зоны нумерации могут быть установлены одна или несколько АМТС.
Типовой схемой организации внутризоновой сети является включение всех местных зоны в АМТС по радиальному принципу, т.е. по заказно-соединительным линиям(ЗСЛ) для исходящей связи и по междугородным соединительным линиям(СЛМ) для входящей связи. На рис. 27 представлена схема построения внутризоновой телефонной сети.


Рис. 27. Схема построения внутризоновой телефонной сети.

Принцип построения междугородной телефонной сети

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


Рис. 28. Схема построения междугородной телефонной сети.

Пример
Известно:
количество станций (n = 6);
емкость станций (N =600 №№, при этом все станции имеют одинаковую емкость);
местоположение оконечных станций на территории сельского администра-тивного района (САР) (рис.26);
расстояния между станциями (таб. 8);
все станции цифровые;
вероятность потери вызова при установлении межстанционного соединения составляет Р =0.02.
Необходимо:
- нарисовать две схемы построения сети, используя способы построения сети “каждая с каждой” и типа “звезда (радиальный)”;
- рассчитать и сравнить коэффициенты среднечасового использования каналов пучков соединительных линий для обоих вариантов построения сети;
- рассчитать объем затрат в канало-километрах, необходимых для реализации обоих вариантов построения сети;
- определить суммарную длину кабельных линий связи;
- выбрать оптимальный вариант построения сети.
При решении задачи считать, что структура построения ПС совпадает со структурой построения вторичной сети.
На рисунке 29. представлено количество и местоположение станций на территории САР.



Рис. 29. Местоположение станций на территории САР

В таблице 9 представлены расстояния в километрах между различными станциями сети
Таблица 9. Матрица расстояний между станциями сети в километрах.
Номер ОС ОС1 ОС2 ОС3 ОС4 ОС5 ОС6
(ЦС) ОС1 15 30 35 20 17 ОС2 15 35 30 14 ОС3 20 35 14 ОС4 20 14 ОС5 15 ОС6
В таблице 9 представлены значения емкость ОСi и удельной межстанцион-ной нагрузки для различных вариантов задания. При емкости станции N =600№№
удельная исходящая межстанционная нагрузка от одного абонента будем считать равной а=0.0125 Эрл.
Решение задачи включает несколько шагов.
1. Необходимо рассчитать исходящую внешнюю нагрузку для каждой станции.
2. Распределить нагрузку между станциями сети.
3. Построить два варианта сети: ” каждая с каждой “ и “радиальный”.
4. Рассчитать нагрузку на пучки СЛ для обоих вариантов.
5. Задавшись нормой потерь, определить емкости пучков СЛ.
6. Рассчитать коэффициент среднечасового использования СЛ для обоих вариан-тов и сравнить их.
7. Определить число каналокилометров СЛ для обоих вариантов сети. Сравнить их.
8. Определить общую длину кабельных линий связи, необходимых для реализа-ции двух вариантов построения сети. Сравнить полученные результаты.
9. Выбрать оптимальный вариант построения сети.
В соответствии с выше приведенным алгоритмом приведем решение постав-ленной задачи.
1. Используя исходные данные произведем расчет исходящей межстанционной нагрузки для одной станции.
Ai = N*a =600*0.0125 = 7.5 Эрл.
Поскольку емкости всех станции одинаковая, то и исходящая межстанционная нагрузка для всех станций сети будет также одинаковой..
2. Будем считать, что тяготение между АТС пропорционально исходящей меж-станционной нагрузке. Тогда нагрузка между двумя станциями сети будет равна
Aij = Ai / 5 = 1.5 Эрл.
3.Построим два варианта структуры сети. На рис.30 представлены два варианта построения сети –“ каждая с каждой ” и “ радиальный”.


а) “ каждая с каждой ” б) “ радиальный ”

Рис. 30. Варианты построения сети.

4. Рассчитаем нагрузку на СЛ.
Для варинта а) Асл = 2* 1.5 = 3 Эрл
Для варинта б) Асл = 2* 7.5 = 15 Эрл
5. Рассчитаем емкости пучков СЛ. Поскольку потери в обоих случаях должны быть равны, то для варианта “ каждая с каждой ” величина потерь составляет
Р = 0.02, а для варианта “ радиальный ” – Р =0.01, так как путь. связывающий
две станции включает два участка сети. Для этого используем рассчитанные значения нагрузок на СЛ, величины потерь для каждого варианта построения сети и таблицу Пальма (табл. 8).
При способе построения “ каждая с каждой ” емкость пучка СЛ равна
Vсл= 8 сл.
При способе построения “ радиальный ” емкость пучка СЛ равна
Vсл = 23 сл.
6. Рассчитаем коэффициенты среднечасового использования СЛ для обоих вари-антов построения сети по формуле:
И = А(1 – Р)/ V,
где И - коэффициент среднечасового использования одной СЛ;
А – нагрузка, поступающая на пучок СЛ;
Р – вероятность потерь на пучке СЛ.
Для варианта а) И1= 3(1- 0.02)/8 = 0.368 Эрл/сл
Для варианта б) И2= 15(1- 0.01)/23 = 0.646 Эрл/сл
Введение транзитного узла существенно повышает коэффициент среднеча-сового использования одной СЛ за счет концентрации нагрузке на пучке СЛ.
7. Определим число канало-километров СЛ для обоих вариантов сети. Расчет про-
изведем по формуле:
К = ,
где K – число канало-километров, необходимых для реализации сети;
Li – длина i –ой линии связи;
Vi – требуемое число каналов в i -ой линиисвязи;
m – число линий связи, в которых используются каналы связи.
Используя структуры сетей, длину линий связи (табл. 9) и соответствующие емкости пучков каналов, рассчитаем требуемое число канало-километров СЛ для обоих вариантов сети.
К1 = 329*8 = 2632 кан.км;
К2 = 74*23 = 1702 кан.км;
7. При этом суммарная длина используемого кабеля будет:
для варианта а) - L1 = 329 км ;
для варианта б) - L2 = 74 км.
Таким образом, оптимальным с точки зрения затрат на построение сети, будет
“ радиальный ” способ построения сети.




Методические указания к задаче 5

Методы управления потоками вызовов на сетях связи.
 
  Общие понятия и определения.
 
Распределение информации на сети связи производится с учетом оптимальности путей. При этом, очевидно, информацию целесообразно передавать в первую очередь по наиболее “коротким” путям, или, как говорят, по кратчайшим путям.
Для оценки “длины” пути могут быть использованы различные критерии: число транзитных узлов в пути, протяженность пути (например, в км.), качество тракта, вероятность передачи информации (или вероятность установления соединения), вероятность перерыва связи, величина затухания и т.п. Значения многих из этих критериев не являются независимыми, поэтому рассматриваются лишь некоторые из них. Так, в однородной сети связи качество тракта зависит от затухания, которое, в свою очередь, определяется числом транзитных узлов и протяженностью пути. Если протяженность ветвей сети примерно одинаковая; то качество тракта непосредственно определяется числом транзитных узлов в пути. Число транзитных узлов в значительной степени определяет вероятность прерывания связи, вероятность установления всего соединения и т.п. В связи с этим основным критерием длины пути в настоящее время часто принимают число в нем транзитных узлов или ветвей в этом пути. В ряде случаев в качестве дополнительного критерия рассматривается протяженность пути.
Кратчайшим путем передачи информации называется путь, для которого длина пути имеет наименьшее значение по сравнению с его значениями для других возможных путей. Все способы выбора кратчайших путей основаны на достаточно очевидном утверждении о том, что, если кратчайший путь µiN от произвольного узла Узi к узлу УзN проходит через промежуточные узлы Узε , …, Узk , то кратчайшие пути µεN , …, µkN от узлов Узε , …, Узk , к узлу УзN соответственно являются частями кратчайшего пути µiN от Узi к УзN .
 

Рис.28 Структура кратчайшего пути.
 
Если длина пути µεN равна LεN , то LiN = liε + LεN .
Так как путь µiN является кратчайшим путем, то LiN = min( lij + LjN ), где j = 1, …, n; n – число узлов сети.
Таким образом, чтобы найти кратчайший путь от узла i к узлу N, необходимо просмотреть все возможные пути и выбрать из них путь с наименьшей длиной.
Под планом распределения информации на коммутируемой сети связи и сети коммутации сообщений понимается заданная очередность выбора исходящих направлений из каждого узла ко всем остальным узлам сети. При этом установление очередности выбора исходящих направлений зависит от длины рассматриваемых путей, поэтому исходящее направление из рассматриваемого узла связи, которое совпадает с кратчайшим путем, относится к направлению первого выбора. Исходящее направление, которое совпадает с путем, длина которого больше длины кратчайшего пути, но меньше всех остальных путей, относится к направлению второго выбора и т.д. Если два или более исходящих направлений совпадают с равными по длине путями, то очередность выбора любого из них устанавливается произвольно, например по приписанным им номерам.
Выбор плана распределения информации для коммутируемой сети рассмотрим применительно к сети коммутации каналов. Порядок выбора исходящих направлений (ветвей) из УКi ко всем остальным узлам сети, т.е. план распределения информации для узла УКi , можно представить матрицей маршрутов Мi для УКi :

В матрице маршрутов число строк равно (N-1), где N – число узлов на сети (строка в матрице Мi для узла i не отводится), а число столбцов равно числу n соседних с рассматриваемым УКi узлов. Элемент mjr матрицы Мi указывает номер очередности выбора ветви ßj при установлении соединения к узлу УКr , т.е. mjr ( {1,2,…,n}.
Все существующие способы получения очередности выбора направлений можно разделить на две группы: детерминированные и статистические. В свою очередь, эти способы делятся на разовые и групповые. При этом матрицы маршрутов вычисляются применительно к ситуации на сети, сложившейся на данный момент без учета предшествующих ситуаций.
Статистические способы позволяют получать рекомендации об очередности выбора исходящих направлений на основе статистики о возможной длине пути по вероятности отказа в том или ином направлении, полученной в результате обслуживания предыдущих заявок. При этом разовые статистические способы позволяют корректировать матрицу маршрутов после обслуживания каждой заявки, а групповые – после обслуживания нескольких заявок.

Метод рельефов

Метод рельефов – метод динамического управления трафиком в сети. Является детерминированным без ограничения нагрузки групповым. Алгоритм реализации данного метода включает три этапа:
Построение рельефа для каждого узла сети (i- рельефа).
Формирование матриц рельефов Rj для каждого узла сети, на основании полученных рельефов на предыдущем шаге.
Формирование матриц маршрутов Mj для каждого узла с использованием матриц рельефов, построенных на предыдущем шаге.


а. Алгоритм построения i- рельефа включает следующие шаги:
1. Определение критерия длины используемого для связи пути. В качестве длины пути при решении задачи будем использовать ранг пути r, определяемого числом ребер графа модели сети.
2. В качестве модели сети возьмем простой неориентированный граф.
3. Выбираем i – вершину (узел) графа сети, для которой строится i - рельеф.
4. Ребрам выбранного узла поставим веса равные 0. Ребрам остальных вершин графа поставим в соответствие исходящую стрелку и вес равный .
5. Выбираем любую вершину k графа сети, кроме ранее выбранной вершины i, и любое ребро инцидентное вершине k. Например, ребро bkj.
6. Определяем новый вес ребра bkj по формуле:
Ukj нов = 1+ Ujm,
где 1 соответствует длине ребра bkj по рангу;
Ujm – минимальный вес ребра из множества ребер инцидентных вершине j.
7. Сравниваем старый вес ребра bkj с новым весом данного ребра.
Если Ukj нов < Ukj, то старый вес ребра меняется на новый вес Ukj нов.
В противном случае вес ребра bkj не меняется и остается прежним.
8. Переходим к следующему ребру вершины k и далее к шагу 6 алгоритма. Просмотрев все ребра, принадлежащие вершине k, переходим к шагу 6. с учетом
изменения номера вершины графа.
Шаги 5- 8 повторяются до тех пор, пока веса ребер графа не будут меняться.
Построенный таким образом взвешенный граф, является i – рельефом и харак-
теризует веса путей минимальной длины по рангу от любой вершины графа до вершины i при использовании любого ребра от рассматриваемой вершины графа.
в. Формирование матриц рельефов Rj.
Матрица рельефов Rj строится на основании i – рельефов графа сети. Матрица рельефов имеет число строк равное числу вершин смежных с вершиной j, а число столбцов равное числу узлов в графе сети. Вершина j смежна с вершинами j1, j2, …. jk. Вхождение матрицы Rj равно весу кратчайшего пути между вершиной j графа сети и любой вершиной графа при использовании соответствуюшей смежной вершины ji . Следовательно, все вхождения для j -ого столбца равны 0. В нашем случае вхождение матрицы Rj равно рангу соответствующего пути.
с. Формирование матриц маршрутов Mj.
Матрица маршрутов Mj определяет порядок выбора путей передачи инфор-мации от узла j к любому узлу сети. При этом для связи используются, в нашем случае, кратчайшие по рангу пути.
Матрица Mj формируется на основании матрицы рельефов. Она сдержит n ─ 1 строк и k столбцов. Из нее исключается строка, соответствующая вершину j. Номер столбца определяет порядок выбора путей от вершины j через смежные ей вершины. В нашем случае их k.
Вхождение матрицы Mj представляет номер смежной вершины с вершиной j. Самый короткий по рангу путь является путем первого выбора, а самый длинный – путем k-ого выбора. При равенстве ранга путей, вводится дополнительные условия определения порядка выбора путей. Например, преимущество имеют пути через смежную вершину с меньшим номером. Не заполненная матрица Mj имеет следующий вид:

1 2 ... k 1 … 2 … . . . . j ─ 1 … j + 1 … . ... n …


Mj =






Пример 1
Ниже приведены i - рельефы, матрицы рельефов Rj и матрицы маршрутов Mj для графа сети, представленного на рис. 28.


Рис. 31. Исходный граф сети.

Для формирования i – рельефов был использован выше приведенный алгоритм. На рис. 32. представлены рельефы для 1, 2, 3 и 4 вершин.


Рис. 32. Рельефы для 1, 2, 3 и 4 вершин.

Для формирования матрицы рельефов, например R1, т.е. для первой верши-
ны, были определены ее параметры. В соответствии со схемой сети, матрица R1 содержит две строки и четыре столбца. Смежной с вершиной 1 являются вер-шины 2 и 4. Через эти вершины может быть осуществлена связь от вершины 1 к любой вершине сети.
Для определения вхождений матрицы рельефов R1, используем рельефы для 2, 3 и 4 вершин. Обращаясь к рельефу для второй вершины, видим, что от вершины 1 к вершине 2 может быть использованы два пути. Первый путь проходит через узел 2. Второй - через узел 4. Минимальный ранг первого пути равен 1 (r =1), второго – r = 2. Заполняем первый столбец матрицы R1.
Аналогичные рассуждения позволяют заполнить второй ,третий и четвер-тый столбцы матрицы R1. Аналогичные рассуждения позволяют сформировать матрицы R2, R3 и R4. На рис. 33. представлены матрицы рельефов R1, R2, R3 и R4.



Рис. 33. Матрицы рельефов R1, R2, R3 и R4.

На основании матриц рельефов, формируются матрицы маршрутов Mj. Рассмотрим формирование матрицы М1. Матрица М1 имеет три строки и два столбца, так как вершина может быть связана со 2 –ой, 3 –ей и четвертой вершинами. Количество столбцов определяется числом смежных вершин с вершиной 1. Это 2 и 4 вершины. Обращаясь к матрицы рельефов для 1-ой вершины, видно, что при связи 1 –ой и 2 –ой вершин через вершину 2 длина кратчайшего по рангу пути будет равна 1 (r = 1), а при связи через 4 – ую вершину длина кратчайшего пути равна 2 (r = 1). Следовательно, путь первого выбора от вершины 1 ко второй вершины пройдет через вершину 2, путь второго выбора через вершину 4.
Аналогичные рассуждения позволяют заполнить до конца матрицу М1, далее М2, М3 и М4. Полученные матрицы приведены на рис.34.



Рис.34. Матрицы маршрутов М1, М2, М3 и М4.

Пример 2
Построить i – рельефы для графа сети, представленного на рис. 28, при условии, что ребро между узлом 1 и 4 удалено ребро b14. Структура графа сети в данном случае представлена на рис. 35.



Рис. 35. Граф сети, в которой ребро b14 удалено.

Для данного случая i – рельефы построены и представлены на рис. 36.


Рис. 36. Рельефы для вершин 1, 2, 3 и 4 после удаления ребра b14.

Используя, представленные на рис. 33 рельефы, построим матрицы рель-ефов R1, R2, R3 и R4. Эти матрицы представлены на рис. 37.


Рис. 37. Матрицы рельефов при удалении ребра b14.

Сформируем матрицы маршрутизации при удалении ребра b14, используя выше представленные матрицы рельефов. На рис. 38 представлены матрицы М1, М2,
М3 и М4.


Рис.38. Матрицы маршрутизации для сети при удалении ребра b14.


Пример 3

Для сети, представленной на рис. 31 , необходимо:
а) составить рельеф для 1-ого узла;
б) используя полученный рельеф, для узла 4 – ого составить 1-ый столбец матрицы рельефов R4;
в) на основании столбца матрицы R4, для узла 4 составить 1 –ую строку матрицы маршрутизации М4;
г) переформировать рельеф для 1 – ого узла и составить один столбец матри-цы рельефов R4, а затем составить строку матрицы маршрутизации М4 при удалении ребра b14;
д) сравнить полученные результаты и сделать вывод о возможности исполь-
зовании метода рельефов для управления потоками сообщений на сети связи.
Решение
Для сети, представленной на рис.31, при исправных ребрах, для 1-ого узла был составлен i – рельеф. Он имеет вид

Рис .39. Рельеф для 4 – ого узла.

Используя полученный рельеф, заполним 1 – ый столбец для матрицы рельефов R4 и, затем, первую строку матрицы маршрутизации М4. На рис.40. представлен первый столбец матрицы R4, характеризующий длину путей по ран--гу от 4 –ого узла до 1 –ого узла через смежные узлы с 4 –ым узлом. На этом же рисунке представлена первая строка матрицы маршрутизации для 4 –ого узла, характеризующая порядок занятия путей от 4 –ого узла до 1 –ого, которая состав-лена на основании матрицы R4.

Рис.40. Первый столбец матрицы R4 и первая строка матрицы М1.

На рис. 41 представлен граф (рис. 31), у которого удалено ребро b14.

Рис. 41. Исходный граф после удаления ребра b14.

Рис. 42. Рельеф для 1 –ой вершины после удаления ребра b14.
Используя рельеф для 1 –ой вершины после удаления ребра b14, заполним 1 –ый столбец для матрицы рельефов R4 и, затем, первую строку матрицы маршрутиза-ции М4. На рис. 43 матрица R4 и М4 для данного случая.

Рис. 43. Матрица R4 и матрица М4 для первой строки и первого столбца в случае удаления ребра .

Сравнивая матрицы, изображенные на рис.40 и рис.43, приходим к выводу, что метод рельефов может быть использован для маршрутизации, так как матрицы М4 при наличии ребра b14 существенно отличается от матрицы М4 после удаления ребра b14.


Методические указания к задаче 6 

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

Для нахождения плана распределения каналов (ПРК) первичной сети для удовлетворения требований в каналах связи между узлами вторичной сети существуют точные и приближенные методы. При большом числе узлов в сети применяют более простые приближенные методы. Одним из таких методов является параллельный метод распределения ресурсов ПС. Поясним на примере этот метод.
Пусть заданы – структура первичной сети в виде взвешенного графа, где веса ребер графа соответствуют числу каналов между различными узлами сети, а также требования между различными корреспондирующими парами узлов в виде необходимого числа каналов. На рисунке 1 представлена структура сети, емкость каждой линии связи которой составляет 20 каналов.


Рис. 1 Структура сети

Пусть необходимо, чтобы между узлами 1-3, 2-4, 3-6 и 5-6 в путях передачи информации было соответственно: φ13 =18; φ36 =16; φ24 =12; φ56 =16 каналов. В этом случае матрица требований Ф будет иметь вид (таблица 1).
Таблица 1 Матрица требований Ф

№Уз 1 2 3 4 5 6 1 0 0 18 0 0 0 2 0 0 0 12 0 0 3 18 0 0 0 0 16 4 0 12 0 0 0 0 5 0 0 0 0 0 16 6 0 0 16 0 16 0





Ф =









По данным структуры первичной сети можно простроить матрицу емкостей ребер U, которая представлена в виде таблиц 2.

Таблица 2 Матрица емкостей ребер U
№ Уз. 1 2 3 4 5 6 1 0 20 0 20 20 0 2 20 0 20 0 0 20 3 0 20 0 20 20 0 4 20 0 20 0 0 20 5 20 0 20 0 0 0 6 0 20 0 20 0 0




U=





Заданные требования, на первом этапе решения задачи, распределяются по возможным кратчайшим путям для каждой пары узлов независимо друг от друга, т.е. составляется идеальный ПРК. Этот план распределения каналов был бы оптимален, если бы ребра первичной сети имели неограниченную емкость. Затем идеальный ПРК корректируется до тех пор, пока не будут выполнены ограничения по емкостям на всех ветвях первичной сети. Коррекция первоначального плана осуществляется за счет перераспределения требуемого числа каналов между корреспондирующими узлами на ранее выбранных путях. При этом учитывается емкость ребер первичной сети. Процесс повторяется до тех пор, пока все требования не будут удовлетворены или дальнейшее удовлетворение требований станет невозможным.
Более детально использование параллельного метода для распределения каналов первичной сети рассмотрим для сети, представленной на рисунке 1 с матрицей требований Ф (таблица1) и матрицей емкостей ребер U(таблица 2).
1. Из матрицы Ф выбираем требование φ13 = 18 каналов.
2. По рис. 8 определяем кратчайшие пути, которые могут быть использованы для связи узлов 1 и 8:
μ11,2,3; μ21,4,3; μ31,5,3.
3. Определяем число каналов в каждом из этих путей, распределяя требуемое число каналов между 1 и 8 узлами равномерно по этим путям:
С1(1,3) = C2(1,3) = C3(1,3) = 6 каналов.
4. Аналогично, все три пункта 1, 2, 3 выполняем для трех других пар узлов. В результате получаем:
φ36 = 16 μ13,2,6 ; μ23,4,6;
φ24 = 12 μ12,1,4; μ22,3,4;
φ56 = 16 μ15,1,2,6 ; μ25,3,2,6; μ35,1,4,6; μ45,3,4,6.
Число каналов в соответствующих путях:
C1(3,6) = С2(3,6) = 8
С1(2,4) = С2(2,4) = 6
С1(5,6) = С2(5,6) = С3(5,6) =С4(5,6) = 4.
5. Далее составляем матрицу С - емкостей кратчайших путей и ребер для сделанного идеального варианта ПРК, представленную в табл. 3.
6. Подсчитываем для каждого ребра bij его емкость, полученную в результате загрузки в соответствии с идеальными ПРК и определяем Dij по формуле: 
                                      Dij = С(bij) - Σ C(μr ij),    μr ij ( bij.
В графе Dij ставим со знаком «+» то число каналов, которое осталось не загруженным (ненасыщенные ребра) и со знаком «-» - число каналов, на которое загрузка ребра в соответствии с идеальным ПРК превышает заданное число каналов в ребре. Поскольку в строке Dij отмечены перегруженные ветви (b23 и b34), то идеальный ПРК недопустим.
7. По матрице С определяем, что перенасыщенной ветви b23 соответствуют пути С1(1-3), С1(3-6), С2(2-4) и С2(5-6).
8. Определяем пару узлов УК, которой соответствует первый из найденных в п.7 путей. Это будет пара узлов 1-3. Далее определяем, есть ли кратчайший путь, соответствующий паре узлов 1-3 и проходящий через ненасыщенных ребера.
Если такой путь найден, то переходим к п.9. Если такого пути нет, т.е. все кратчайшие пути проходят хотя бы через одно насыщенные или перенасыщенные ребра, то переходим к п.11.
9. Путь между парой узлов 1-3, проходящий через ненасыщенные ребра, найден – это путь С3(1-3). Путь С2(1-3) использовать для перераспределения нельзя, так как он проходит через перенасыщенное ребро b34. Определяем величину перераспределяемой с пути С1(1-3) на путь С3(1-3) емкости. Так как в ребре b23 следует уменьшить число каналов на 4, с тем, чтобы его емкость не превышала заданную, то на всем пути С1(1-3) – в ребрах b12 и b23 – число требований следует уменьшить на 4, а в пути С3(1-3) – ребрах b15 и b35 – увеличить на 4. Старые значения (они в таблице 3 указаны в скобках) исправляем на новые. Новые значения емкостей проставлены сверху. В строке D'ij рассчитаны новые величины Dij, с учетом откорректированного плана распределения каналов.
10. ПРК остался недопустимым, так как еще перенасыщена ветвь b34. Повторяем действия пп. 7, 8, 9. В результате находим, что для пары 2-4 существует путь С1(2-4), который проходит по ненасыщенным ребрам b1,2 и b14. В пути С2(2-4) емкости ребер уменьшаем на 4, а в пути С1(2-4) – увеличиваем на ту же величину. В строке D''ij рассчитаны новые величины Dij, с учетом откорректированного плана распределения каналов.
Данный ПРК допустим, так как в строке D''ij все значения положительные. Полученные элементы матрицы С определяют искомый ПРК.
11. Если кратчайшего пути с ненасыщенными ребрами для данной пары не найдено, то переходим к следующему пути, соответствующему ненасыщенной ветви, и повторяем п.9. Процесс повторяем до тех пор, пока не будет найден для какой-либо пары УК ненасыщенный кратчайший путь. Если для всех пар не найдено путей с ненасыщенными ветвями, то требования не могут быть удовлетворены по кратчайшим путям, и следует найти путь, содержащий большее число транзитных участков и состояний из ненасыщенных ребер. Если такого пути не существует, то требования не могут быть удовлетворены полностью. В этом случае необходимо уменьшить величину требований или увеличить число каналов первичной сети и решать эту задачу заново.

Таблица 3 План распределения каналов
Номер пары УК Номер пути b12 b14 b15 b23 b26 b34 b35 b46


1-3
С1 2

(6) 2

(6) С2 6 6
С3 10

(6) 10

(6) 3-6 С1 8 8 С2 8 8

2-4
С1 10

(6) 10

(6)
С2 2

(6) 2

(6)
5-6 С1 4 4 4 С2 4 4 4 С3 4 4 4 С4 4 4 4 Dij +4 +4 +6 -4 +4 -4 +6 +4 ПРК недопустим D'ij +8 +4 +2 0 +4 -4 +2 +4 ПРК недопустим D''ij +4 0 +2 +4 +4 0 +2 +4 ПРК допустим






















 

















5




20

20

20

20

20

20

20

20

3

2

4

6

1