Моделирование объекта системы и сети электросвязи

Кратчайший путь к ( k+1)-ому ближайшему узлу проходит по узлам из Р

Источник                                                          j-это (k+1)-й ближайший узел

Множество Р из k ближайших узлов к узлу 1                   дополнение к Р

 

Основная идея алгоритма Дейкстра: на k-ом шаге имеется множество Р из k ближайших узлов к узлу 1, D _i – кратчайшее расстояние от узла 1 до каждого узла i из Р. Среди всех путей, соединяющих узел 1 с каким-либо узлом не из Р, самый кратчайший путь должен пройти по узлам из Р ( так как d _{i j} > 0 ). Поэтому ( k+1 ) – й ближайший узел и соответствующее кратчайшее расстояние получаются минимизацией по j Ì P величины min _{i Ì P} ( D _i + d _{i j} ), в результате получается сложность порядка 0 (N ² ).

Задание 4

По известной  топологии сети:

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

2.Определить число каналов в системе с коммутацией пакетов, если известно число узлов N;

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

4.Указать последовательности, которые являются циклом или путем.

Исходные  данные: 

 
 
 
 
 
 
 
 

                                                        10

                              4                           

                                                        6                           2

                                    1                                 3

 
 
 
 

5. МОДЕЛЬ РАСЧЕТА  ТОЧЕК КОММУТАЦИИ  КОММУТАЦИОННЫХ СХЕМ 
 

Выбор точки коммутации может производиться двумя путями:

1. если  управление организовано по выходам коммутационной схемы, то необходимо определить, какие входы схемы должны быть соединены с соответствующими выходами – « управление по выходу»;
2. если управление организовано по входам коммутационной схемы, то нужно определить, какие выходы должны быть соединены с соответствующими входами – « управление по входу»;    

 

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

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

Число битов  информации, требуемой для управления каждым селектором, равно log ₂ N, где N – число входов;

Суммарное число  битов для определения соединения в рассматриваемой конфигурации равно M log ₂ N. 

Управление по входу можно реализовать, используя  обычные линейные декодеры ( демультиплексоры ); выходы объединяют в виде « монтажных ИЛИ».

Суммарное число  битов информации, требуемое для  полного определения соединения в такой схеме равно N log ₂M.

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

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

Из – за более  высокого быстродействия цифровые системы  коммутации строятся с управлением  по выходу. 

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

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

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

Схема пространственно  – временной коммутации

 

 

                           один цикл

                  2  1   .......  3  2  1                                   2   1  ........  3  2  1    

            1 

                ..............                                                            .............

                   1  ... 17.... 3  2  1                                   2  1     ...    17.... 2  1

               

            N 

Для примера  на схеме показано соединение канала 3 первого тракта с ВРК с каналом 17 последнего тракта с ВРК:

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

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

Работа схемы  временной коммутации сводится к  записи информации и считыванию ее из ЗУ.

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

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

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

Дуплексное  соединение каналов i и j трактов с ВРК означает, что адрес i поступает в ЗУ в течение j –го временного интервала, и наоборот, т.е. в течение каждого временного интервала к ЗУ производятся два обращения:

1. когда управляющее устройство выбирает номер времннного канала, который определяет адрес записи в ЗУ;     
2. когда содержимое управляющей памяти, соответствующее определенному временному каналу, выбирается в качестве адреса считывания;

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

                                                     c = 125 \ 2 t _C

 где цифра  125 означает длительность цикла  в мкс ( для частоты дискретизациии  речевого сигнала, равной 8 кГц  );

t_C - длительность цикла обращения ЗУ в мкс; 

При цикле 500 нс коммутационная схема на ЗУ может обслужить 125 дуплексных каналов ( 62 соединения ) при условии строгой неблокируемости схемы.

ЗУ хранит один информационный цикл, организованный как с слов  по 8 бит каждое, управляющая память также имеет объем с слов длиной равной log ₂ c ( равной 7 ).

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

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

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

Существуют два  способа управления работой ЗУ звена  временной коммутации:

• последовательная запись и произвольное считывание;
• произвольная запись и последовательное считывание;

 

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

1)                               3                                                     17

                                                                         3

 

                                                                                    3

 
 

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