АЛМАТИНСКИЙ ИНСТИТУТ ЭНЕРГЕТИКИ И СВЯЗИ

 

 

 

 

Кафедра автоматической электросвязи

 

 

 

 

 

 

 

 

 

СЕТИ ЭЛЕКТРОСВЯЗИ

 

                                                               

Программа, методические указания и контрольные задания

(для студентов специальностей

3801- Сети связи и системы коммутации;  3802-Многоканальные телекоммуникационные системы

заочной формы обучения).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Алматы 2001

 

 

СОСТАВИТЕЛЬ: Г. П. Данилина

         Сети электросвязи. Программа, методические указания и контрольные задания  (для специальностей 3801, 3802). Алматы: АИЭС, 2001 г. -30 с.

 

 

 

 

 

 

 

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

 

Ил. 11  , табл. 5  , библиогр.-4

 

 

 

 

 

 

Рецензент: доц. кафедры Электроники и компьютерных технологий, канд.техн.наук З.А. Жунусов

 

    

 

 

 

Печатается по плану издания Алматинского института энергетики и связи на 2001 г.

 

 

 

 

 

©   Алматинский институт энергетики и связи, 2001 г.

 

I ПРОГРАММА КУРСА

 

 

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

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

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

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

 

        Согласно программе, на изучение курса отведено 114 часов, в том числе:

- лекции – 14 час;

- лабораторные занятия – 8 час;

- практические – 6 час;

- самостоятельная работа – 86 час (в том числе 2 контрольных работы).

 

          1.1 Содержание учебного материала

 

          Введение.

Предмет и задачи курса. Сеть электросвязи как система.

          1.1.1 Виды и типы сетей

Элементы сети. Структура и архитектура. Прохождение сообщения в сети.

Показатели эффективности.

          1.1.2 Большие системы и методы их моделирования. Свойства больших систем: иерархичность, стохастика, динамичность. СЭС - как большая система. Первичные и вторичные сети.

          1.1.3 Задачи анализа и синтеза

Специфика сетей ЭС как объекта анализа и синтеза.

Схемы задач. Методы анализа.

          1.1.4 Методы оптимизации

Критерии. Безусловная оптимизация. Система ограничений. Математическое программирование. Многокритериальные задачи.

 

          1.1.5 Методы синтеза объектов проектирования

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

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

          1.1.7 Надежность сетей связи

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

          1.1.8 Динамика развития сетей.

 

1.2 Перечень практических работ

 

          1.2.1 Определение кратчайших расстояний.

          1.2.2 Распределение каналов на вторичных сетях.

          1.2.3 Синтез централизованных сетей.

 

1.3 Перечень лабораторных работ

 

          1.3.1 Выбор  оптимального  месторасположения объектов (АТС, распределительных шкафов и т.д.) .

          1.3.2 Решение задачи районирования .

 

1.4 Контрольные работы

 

          1.4.1 Задачи синтеза первичной сети.

          1.4.2 Задача распределения каналов на вторичной некоммутируемой сети.

          Список литературы

 

1.   Теория сетей связи /Под ред. В.Н.Рогинского/ - М: Радио и связь, 1981. -192 с.

2. Давыдов Г. Б. Рогинский В.Н., Толчан А.Я. Сети электросвязи. -М: Связь, 1977. –360 с.

3. Глушков В. М. Сети ЭВМ. - М: Наука,1977.

4. Бертсекас Д., Галлагер Р. Сети передачи данных. -М: Мир,1989. – 542 с.

5. Норенков И.Г., Трудоножин В.А. Телекоммуникационные технологии и сети. – М., 1998.

 

6. Куин Л, Рассел Р. Fast Ethernet: Описание технологии, вопросы организации и управления, сетевые компоненты. – гуд. Группа BHV, 1998.

7. Лохмотко В. В., Пирогов К.И., Анализ и оптимизация цифровых сетей интегрального обслуживания. –Минск: Навука i тэхнiка, 1991.- 191 c

8. Ниеталин Ж.Н., Данилина Г. П. Методические указания к лабораторным работам. АИЭС, 1994.

9. Шварц М. Сети ЭВМ. Анализ и проектирование. -М: Радио и связь, 1981.

 

II МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КОНТРОЛЬНЫМ РАБОТАМ

 

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

        

          2.1 Синтез централизованных сетей [1] (контрольная работа № 1)

 

Централизованной называется сеть связи, если в ней можно выделить два иерархических уровня:

- терминалы Тi , которые могут подключаться к концентратору или непосредственно к ЭВМ;

- концентраторы Кj, соединяемые с центральной ЭВМ.

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

 

           2.1.1 Упрощенный вариант задачи синтеза

Упростим задачу, предположив возможность ее замены одноуровневой, т. е. сначала решается задача прикрепления терминалов к концентраторам, а затем – концентраторов к ЭВМ. Иными словами, решим задачу в следующей постановке: задано некоторое множество генераторов (источников) информации Si , i=1,..n, которые должны быть соединены сетью минимальной стоимости с приемником информации So. Допускается соединение Si между собой.

         Заданными являются стоимости Cij соединения Si и Sj,пропускная способность rij, интенсивности источников аi, интенсивность стока

ао= - аi .

        

Исходные данные задаются в виде таблиц.

Если пропускные способности одинаковы для всех линий (Si , Sj) , то задается число rij =R.

 

Таблица 1                                                 Таблица 2

                  

Сij

S0

S1

- -

Sn

 

rij

S0

S1

- -

Sn

S1

C10

-

- -

C1n

 

S1

r10

-

- -

r1n

S2

C20

C21

- -

C2n

 

S2

r20

r21

- -

r2n

-

-

-

-

-

-

- -

-

-

 

-

-

-

-

-

-

- -

-

-

Sn

Cn0

Cn1

- -

-

 

Sn

rn0

rn1

- -

-

                    

        Задание к контрольной работе

В приложении I даны варианты заданий: первая цифра номера варианта показывает номер специальности (3801-1, 3802-2), а вторая соответствует последней цифре зачетной книжки; в зависимости от первой буквы фамилии студента стоимостные коэффициенты Cij умножаются на следующие коэффициенты k:

 А,Б,В,Г- k=1; Д,Ж,З,И- k=2; К,Л,М,Н- k=3; О,П,Р,С- k=4; Т...Я- k=5.

     а) Используя исходные данные решить вручную задачу синтеза двумя методами (Ежи- Вильямса и Прима), сравнить полученные результаты.

     б) Разработать блок- схему алгоритма одного из методов.

 

          2.1.1.1 Алгоритм Ежи – Вильямса

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

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

Шаг 0. Вычисляется система пометок

tij= Cij- Cio  для всех i, j N, i j                                                    (1)

Параметр tij представляет собой разницу стоимости соединения узла i c узлом j или непосредственно с центром- узлом So.

         Шаг 1. Выбрать наименьшее tij

                   {tij}= tkl .

Если tkl <0, то перейти к шагу 2, при tkl 0- Шаг 4.

         Шаг 2. Проверить аk>0 (нужно ли передавать информацию?) и аk rkl; (аk+ аl)  rlo (есть ли свободная пропускная способность).

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

         Шаг 3. Если tkl <0, то производится соединение Sk и Sl и пересчет показателей:    аk1=0 аl1= al+ak

                                       rkl=r- аk

                                       F1  =F+ Сkl.

         Полагаем tkl= и переходим к шагу 1.

         Шаг 4. Если наименьшее tkl 0, это значит, что затраты на соединение Sk-го узла с Sl-м больше, чем на соединение с S0. В этом случае, Sk соединяется с S0.

         Полагаем:  аkн=0

                            a0но+ аk

                            Fн=F1ko

Процесс продолжается до тех пор, пока все аi не станут равны 0.

Проиллюстрируем алгоритм небольшим примером.

 

          Пример

Определить сеть минимальной стоимости, соединяющую терминал S1,S2, S3 с ЭВМ S0.

Стоимости линий Cij приведены в таблице 3, пропускные способности всех линий приняты одинаковыми, rij=5.

 

Таблица 3                           

 

 

 

 

а0=-8; а1=2; а2=3; а3=3.

 

S0

S1

S2

S3

S1

1

-

2

4

S2

4

3

-

1

S3

3

1

5

-

                           

 

         Шаг 0. Подсчитаем множество пометок по формуле:

                   tij= Cij- Cio 

         t12= C12- C10=2-1=1

         t13= C13- C10=4-1=3

         t21= C21- C20=3-4=-1;                                                                       (1)                                     

         t23= C23- C20=1-4=-3;

         t31= C31- C30=1-3=-2;

t32= C32- C30=5-3=2

Итерация 1.

         Шаг 1. Определяем наименьшую пометку в множестве (1)

                            { tij}= t23=-3

         Это означает, что нужно проверить возможность соединения вершин S2 и S3 (S2=>S3).

         Шаг 2. Проверяем величину интенсивности в вершине S2

                                               а2=3>0; а2=3<r=5.

                            А2+ а3=3+3>r- следовательно соединение S2 => S3 невозможно, полагаем t23= и переходим к выполнению итерации 2.

Итерация 2.

         Шаг 1. Определяем

                             { tij}= t31=-2, что соответствует соединению S3 и S1.

         Шаг 2. а3=3>0   а3+ а1=3+2=5=r, следовательно, это соединение возможно.

         Шаг 3. Подсчитаем:

-         затраты  F=C31=1;

-          новые интенсивности терминалов S3 и S1

a31=0     а11=2+3=5

-        

S1

S3

r=2

Рисунок 1

пропускную способность

r131=5-3=2.

         Положим t31= .          

 

  

 

        

Переходим к шагу 1 итерации 3.

Итерация 3.

         Шаг 1. Определим { tij} = t21.

         Шаг 2. Проверим:

         a2=3>0;  а2<r=5;  а21= 3+5>r=5, следовательно, это соединение невозможно, положим t21= и переходим к  итерации 4.

Итерация 4.

         Шаг 1.     {tij}= t12>0, значит все  tij – положительны, переходим к шагу 4 .

         Шаг 4. Определим вершины с положительной интенсивностью и соединим их с S0.

                               A1=5<r10    a111=0   а10=-8+5=-3    F11=F+C10=1+1=2. 

                               А2=3<r20    a12=0   а110=-3+3=0    F111=F11+C20=2+4=6. 

                   A13=0

 

         Следовательно, расчет окончен, оптимальная схема приведена на рисунке 2. Затраты равны 6 ед.

S1

S3

S0

S2

Рисунок 2

 

 

 

 

 

 


                                                          

                

  

 

     2.1.1.2 Метод Прима

Алгоритм этого метода отличается от вышеописанного только способом выбора вершины- претендента, т. е. построением множества пометок tij(Шаг 0). Описываемый подход основан на идее выбора вершины, ближайшей к S0 (центральному обрабатывающему устройству) или к вершине Sj, уже соединенной сетью с S0.

Каждой вершине Sj приписывается пометка wj, причем в начале расчетов w0=0, wj=- , т.е. в сеть входит только вершина S0.

Шаг 0. Подсчитывается множество Т= { tij}

                    tij= Cij- wj  для тех вершин, где wj=0.

         Конечные значения имеют только ti0, равные стоимости Ci0(т. к. w0=0), а все остальные равны . Дальше выполняются те же шаги, что и в методе Ежи- Вильямса.

Шаг 1. Определяется наименьшее значение tij, т. е. вершина Si, ближайшая к S0(на 1 итерации).

                               { tij}= tkj

S0

 

wk=0

w0=0

Рисунок 3

Sк

 

Шаг 2. Осуществляются проверки:                                            

                            ak>0            ak<rkj                                                                          

                                                       ak+aj<rj0

Шаг 3. Вычисляются значения:                                                                 

                            akн=0           ajн=aj+ak                                                                                                

                            rkjн=rij-ak          F=F0+Ckj     

                Полагается wk=0                                                                            

         Переход к шагу 0 следующей итерации.

 

          Пример

Проиллюстрируем алгоритм, описанный выше, примером. Пусть w0=0, wj=- . С учетом данных таблицы 3 подсчитаем значения tij.

Шаг 0.

         Т:  t10= C10- w0=1-0=1

         t20= C20- w0=4-0=4

         t30= C30- w0=3-0=3                                                                                     

         t12= C12- w2=2+ w2= , t13= ;

         t21= C21-  w1=3+ w1= , t23= ;

t31= C31-  w1=1+ w1= ; t32= .

Шаг 1. Определим  { tij}

S0

Рисунок 4

S1

                    { tij}= t10=1

Шаг 2.        а1=2>0; r10=5; a1<r10.

Выполнение условий позволяет перейти к шагу 3.

Шаг 3. Вычислим новые значения:                                                    

         а11=0; a10=-8+2=-6; r110=5-2=3; F=C10=1.                          

Положим w1=0; t10=  и перейдем к шагу 0.                                       

         Шаг 0. Подсчитаем:

Т1:      t21= C21-  w1=3- 0=3;

 t31= C31-  w1=1- 0=1.

         Шаг 1.        {TUT1}= t31, т. е. S3=>S1.

Шаг 2.        а3=3>0; r31=5>a3; a11+a3=0+3 r10=3.

Шаг 3.  

Рисунок 5

S0

S3

S1

                                                        a31=0; a011=-6+3=-3.

                                                        r1011=3-3=0.

                                                         r311=5-3=2.

                                                        F1=F=C31=1+1=2

 

 

 

 

Положим  w3=0; t31= и перейдем к шагу 0.

         Шаг 0.

         Т2: t2323- w3=1.

         Шаг 1. Определим {TUT1 UT2}= {tij}=t23.

         Шаг 2. а2=3>0; r23=5>a2; r311=2<a2, следовательно соединение S2=>S3 невозможно, положим t23= и перейдем к шагу 1.

         Шаг 1. {TUT1 UT2}= t20=2.

         Шаг 2. а2=3>0; r20=5>а2,

         Шаг 3. а21=0; r201=5-3=2; а0111=-3+3=0

                   F=2+4=6

         Поскольку все аi1=0, задача решена.

S2

S3

S0

S1

 


        

 

 

 

 

                                  

 

 

 

Рисунок 6

    

 

        

 

 

      

          2.1.1 Синтез двухуровневой централизованной сети

             Задание к контрольной работе

   Варианты задания даны в Приложении II (номер задания соответствует последней цифре зачетки). Кроме того, все стоимости Cij и fj следует умножать на последнюю цифру года (в 2001- на 1, в 2002- на 2 и т.д.).

а) Решить задачу синтеза вручную. Результат представить в виде рисунка оптимальной схемы соединения терминалов с ЭВМ и соответствующей этой схеме стоимости.

б) Разработать и описать блок- схему алгоритма.

 

     Рассмотрим алгоритм синтеза двухуровневой сети, включающей заданное число терминалов Ti, i=1,..n, некоторое допустимое множество концентраторов Kj (j=1,..m), места, расположения которых известны, а количество должно быть выбрано в результате решения задачи. Центральное обрабатывающее устройство (ЭВМ) обозначим К0. Заданы стоимости создания концентраторов fj и количество терминалов, которые можно подключить к каждому концентратору, rj.Если к концентратору подключен хотя бы один терминал, то он называется открытым, в противном случае – закрытым.

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

             Итак, заданными являются:

- множества терминалов Тi и концентраторов Kj (i=1,..n; j=1,2,…m), ЭВМ – К0;

- стоимости линий связи, заданные матрицей стоимости С=ççСijçç, i=1,..n; j=0,1,…m;

- стоимости создания концентраторов f1,f2,…fm;

- количество возможного подключения терминалов rj.

Определить:

- количество открытых концентраторов;

- схему подключения к ним терминалов;

- стоимость сети.

Для реализации этой задачи разработано большое число методов, рассмотрим алгоритм одного из них.

 

          2.1.2.1 Алгоритм метода добавления

Алгоритм представляет собой итерационный процесс последовательного

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

         Шаг 0. Первоначально считаем, что все концентраторы закрыты, а терминалы присоединены к ЭВМ - к К0. Затраты на создание такой сети равны сумме соединения терминалов с ЭВМ, т. е. сумме элементов столбца, соответствующего К0, т. е.

F0= Сi0.

         Очевидно, что это самое дорогое решение.

Итерация 1.

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

         Шаг 1. Откроем К1. Эффект от изменения присоединения Si к К1 вместо К0 определим по формуле:

Сi0- Ci1.                                                               (*)

         Очевидно, что присоединить к К1 целесообразно только те Si, для которых подсчитанные разности (*) будут положительными. Однако число таких присоединяемых Si ограниченно r1. Подсчитаем эффект, учитывая затраты f1 на создание концентратора К1.

F11=F0- (Ci0-Ci1)- … (Cj0-Cj1) +f1.

(включены только (Ci0-Ci1)>0, число их меньше r1).

Аналогичных шагов будет m (по числу концентраторов).

         Шаг (m+1). Определяются наименьшие затраты:

{F11, F21, … Fm1}= Fj1

Следовательно, откроем концентратор Кj, присоединив к нему {Sg, Sl, … Sк}.

Итерация 2.

 Считая открытым концентратор Kj, будем открывать по очереди еще по одному концентратору.

         Шаг 1. Откроем К1при открытом Kj,оценим:

(Ci0-Ci1) для i, не присоединенных к Kj;                                             (**)

(Cgj-Cg1) для g, l, … k, т. е. для тех S1, которые присоединены к Kj.

         Выбираются r1 наибольших разностей (**) и подсчитываются затраты:

F1,j2=Fj- (Cgx-Cg1)+f1.

Шагов будет m-1 (по числу закрытых еще концентраторов).

         Шаг m. Определяется наименьшее значение функции:

min {Fj12, Fj22, … Fjm2}, j m.

Итерация 3.

Анализируется возможность открытия третьего концентратора при уже открытых двух.

Последняя итерация состоит в открытии всех концентраторов одновременно. Проиллюстрируем описанный алгоритм примером.

 

          Пример

Пусть задано 5 терминалов и 3 концентратора, к каждому из которых можно присоединить по 2 терминала. В таблице 4 приведена матрица затрат.

 

Таблица 4                              

 

K0

K1

K2

K3

T1

8

4

6

6

T2

10

5

3

8

T3

3

4

0

7

T4

4

12

6

1

T5

12

10

8

0

 

 

 

f1=4; f2=3; f3=2; r=2



Шаг 0. Присоединим все терминалы к ЭВМ (рисунок 7) и подсчитаем затраты:

 

F0= Сi0=8+10+3+4+12=37.

K0

Рисунок 7

Т1

Т2

Т3

Т4

Т5

K3

K1

K2

 

 

 

 

 

 

 

 


                                                                 

 

 

 

 

Итерация 1.

Шаг 1. Откроем К1.

C10- C11=8-4=4

C20- C21=10-5=5

C30- C31=3-4=-1

C40- C41=4-12=-8

C50- C51=12-10=2

Выберем две наибольших разности и подсчитаем новое значение функции стоимости:

F11=37-(C10-C11)-(C20-C21)+f1=37-4-5+4=32.

T1, T2=>K1.

Шаг 2. Откроем К2:

C10- C12=8-6=2

         C20- C22=10-3=7

C30- C32=3-0=3                                                                                     

C40- C42=4-6=-2

         C50- C52=12-8=4

Выберем две наибольшие разности, соответствующие варианту прикрепления Т2 и Т5 к К2.

F21=37-(C20-C22)-(C50-C52)+f2=37-7-4+3=29.

T2, T5=>K2.

Шаг 3. Откроем концентратор К3:

C10- C13=8-6=2

         C20- C23=10-8=2

C30- C33=3-7=-4                                                                                                  C40- C43=4-1=3

         C50- C53=12-0=12

 

F31=37-(C40-C43)-(C50-C53)+f3=37-3-12+2=24.

T4, T5=>K3.

Шаг 4. Выберем наилучший вариант прикрепления:

{F1, F2, F3}= {32,29,24}=24,

что соответствует T4, T5=>K3.

 

Рисунок 8

K0

Т1

Т2

Т3

Т4

Т5

K3

K1

K2

 

 

 

 

 

 

 

 

 

 

 


Итерация 2.

Шаг 1. При открытом К3 откроем К1: подсчитаем Ci0-Ci1 для i=1,2,3;  Ci3-Ci1 для i=4,5.

C10- Ci1=8-4=4                                  C43- C41=1-12=-11

C20- C21=10-5=5                               C53- C51=0-10=-10

C30- C31=3-4=-1

F3,12=24-(C10-C11)-(C20-C21)+f1=24-4-5+4=19.

T1, T2=>K1.

Шаг 2. При открытом К3 откроем К2: подсчитаем Ci0-Ci2 для i=1,2,3;  Ci3-Ci2 для i=4,5.

C10- Ci2=8-6=2                                  C43- C42=1-6=-5

C20- C22=10-3=7                               C53- C52=0-8=-8

C30- C32=3-0=3

F3,22=F31-(C20-C22)-(C30-C32)+f2=24-7-3+3=17.

T2, T3=>K2.

          Шаг 4.

{F312, F322}= {19,17}=17, T2, T3=>K2.

K0

Т1

Т2

Т3

Т4

Т5

K3

K1

K2

Рисунок 9

 

 

 

 

 

 

 

 

 

 

 


Итерация 3.

Откроем концентратор К1 при открытых К2 и К3. Подсчитаем целесообразность подсоединения к нему всех терминалов:

C10- C11=8-4=4

         C22- C21=3-5=-2

C32- C31=0-4=-4                                                                                                  C43- C41=1-12=-11

         C53- C51=0-10=-10

Положительная разность только одна:

F33,2,1=F23,2=(C10-C11)+f1=17-4+4=17.

Поскольку открытие К1 не уменьшит целевую функцию в качестве оптимального можно принять любой вариант сети- при открытых концентраторах К2 и  К3 (рисунок 9) или открытых всех трех концентраторах (рисунок 10), F3,2,13=17.

 

K0

Т1

Т2

Т3

Т4

Т5

K3

K1

K2

Рисунок 10

                                                                                                       

 

 

 

 

 

 

 

 

 

          2.2 Распределение каналов на вторичной некоммутируемой сети(контрольная работа № 2)

          Задание к контрольной работе

В приложении III приведены варианты заданий (кодирование вариантов то же, что в пункте 2.1.1).

а) Построить таблицу, отражающую исходную информацию и условия задачи.

б) Все итерации сопровождать подсчетом числа каналов.

в) В случае невозможности построить бездефицитную сеть,       преобразовать ее к виду, требующему минимум модернизации.

 

          2.2.1 Постановка задачи

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

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

         Структуру первичной сети будем изображать в виде графа, ребрам которого приписываются некоторые значения – веса (стоимости, длина) и пропускные способности в числе каналов. Для примера рассмотрим сеть, состоящую из 6 вершин и 8 ребер. Пусть емкость каждого ребра bij=20 каналам. Необходимо построить план распределения каналов при котором: емкость пучка между вершинами 1 и 3 равнялась 18, между вершинами 3 и 6 -16, 2 и 4 –15, 5 и 6 –16 каналам, т. е. Y13=18; Y36=16; Y24=15; Y56=16; при этом число транзитных участков в каждом пути не должно превышать трех.

2

 

                              

1

4

3

5

6

1

 

 

 

 

 

 


Рисунок 11

        

 

 

Путь между вершинами i и j будем представлять упорядоченным набором узлов (или набором ребер).

         Например, вершины 3 и 6 могут быть соединены путями:

         m361={3,2,6};                 m362={3,5,1,2,6};            m363={3,5,1,4,6};

         m364={3,2,1,4,6};            m365={3,4,6};                 m366={3,4,1,2,6};

 

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

r(m1)=2; r(m2)=4; r(m3)=4; r(m4)=4; r(m5)=2; r(m6)=4.

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

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

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

 

          2.2.2 Алгоритм

Шаг 1. Для каждой пары вершин (i j), для которой необходимо построить пучок прямых каналов, строится множество путей, и выбираются те из них, чей ранг удовлетворяет ограничению.

Шаг 2. Требуемое количество каналов Yij делится поровну между путями.

Шаги 1 –2 выполняются для всех пар (i j).

Шаг 3.Строится матрица емкостей допустимых путей, представляющая собой таблицу, строки которой соответствуют путям mi, k, а столбцы ребрами графа. На пересечении строки mi, … k и столбца (i j) записывается число каналов х этого ребра, выделенных для данного пути, т. е.

xi jm i, … k

 

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

         Шаг 4. Проверяются выполнения ограничений на каждом ребре. Если они выполняются, задача решена, переход к шагу 6 – конец решения. В противном случае – к шагу 5.

 

 

 

 

 

 

 

 

 

          Таблица 5

 

Yij

Емкость

пути

Ребра

Число

каналов

1-2

1-4

1-5

2-3

2-6

3-4

3-5

4-6

 

Y13

Х1,2,3

6/3

 

 

6/3

 

 

 

 

12

6

Х1,4,3

 

6/3

 

 

 

6/3

 

 

12

6

Х1,5,3

 

 

6/9/12

 

 

 

6/9/12

 

12

24

Y36

Х3,2,6

 

 

 

8

8

 

 

 

16

16

Х3,4,6

 

 

 

 

 

8

 

8

16

16

Y24

Х2,3,4

 

 

 

5

 

5

 

 

10

10

Х2,1,4

5/6

5/6

 

 

 

 

 

 

10

12

Х2,6,4

 

 

 

 

5/4

 

 

5/4

10

8

Y56

Х5,1,2,6

4

 

4

 

4

 

 

 

12

12

Х5,1,4,6

 

4

4

 

 

 

 

4

12

12

Х5,3,2,6

 

 

 

4

4

 

4

 

12

12

Х5,3,4,6

 

 

 

 

 

4

4

4

12

12

 

DХij

+5

+5

+6

-3

-1

-3

+6

-1

 

 

 

DХ2ij

+8

+5

+3

0

-1

-3

+3

-1

 

 

 

DХ3ij

+7

+4

+3

0

0

-3

+3

0

 

 

 

DХ4ij

7

7

0

0

0

0

0

0

 

 

 

         Шаг 5. Для перенасыщенных ребер производится разгрузка (если возможно) и переход к шагу 4. Если разгрузить некоторые ребра невозможно – переход к шагу 7.

 

         Шаг 6. Выдается план распределения каналов.

 

         Шаг 7. Решение невозможно из–за недостаточной емкости сети.

Проиллюстрируем выполнение алгоритма описанным примером.

 

         Шаг 1. Построим множества путей ранга  3.

m131={1,2,3}; m132={1,5,3}; m133={1,4,3};

m361={3,2,6}; m362={3,4,6};

m241={2,3,4}; m242={2,1,4}; m243={2,6,4};

m561={5,1,2,6}; m562={5,1,4,6}; m563={5,3,2,6}; m564={5,3,4,6};

 

Шаг 2. Количество каналов делится поровну на все пути:

x123=x153=x143=18/3=6; x326=x346=16/2=8; x234=x214=x264=15/3=5;

 

Шаг 3. Построим матрицу емкости (Таблица  5).

Столбцы матрицы соответствуют ребрам заданной сети: (1- 2), (1- 4), (1- 5), (2- 3) … , а строки путям  mi, jk: в I строке в столбцах (1- 2) и (2- 3) записано число каналов, равное 6, во II строке – в столбцах (1- 4) и (3- 4) и т. д.

 

         Шаг 4. Просуммируем количество каналов в каждом столбце и, учитывая, что емкость каждого ребра равна 20, проверим условие:

 xi-j  20,

где М – множество всех допустимых путей, проходящих через ребро (i-j).

        

Подсчитаем:

Dx=20- x i-j

и запишем в çМç+1 строку. Отрицательная величина Dx говорит о недопустимости анализируемого плана распределения каналов и необходимости его корректировки. Например, в столбце, соответствующем ребру (1-2) число каналов равно:

6+5+4=15

и в строке Dx поставим:

20-15=5,

а в столбце (2-3):

6+8+=5+4=23

Dx1=20-23=-3.

Следовательно, ребро (2-3) перегружено.

Последние столбцы фиксируют число каналов в каждой строке после каждого распределения.

         Дальнейшие действия – последовательно переместить каналы с перегруженного пути – на недогруженный путь того же потока (шаг 5).

 

         Шаг 5(I). Снимем лишнюю нагрузку (3 канала) с ребра (2-3), входящего в путь m1,2,3 , и следовательно, со всех ребер этого пути (в матрице зачеркнули цифры 6 и записали 3). Добавим эти каналы (3) к недогруженным ребрам пути этого же пучка Y13 , т. е. к каналам ребер (1-5) и (3-5).

 

         Шаг 4(II). Подсчитаем элементы строки Dx2. Отрицательными являются Dx2-62 и Dx4-62.

 

         Шаг 5(II). Уменьшим на 1 количество каналов в пути m2,4,6 , добавив в пути m2,1,4 (на ребрах (1-2) и (1-4)).

 

         Шаг 4(III). Подсчитав Dx3, видим, что перегружено только ребро(3-4).

 

         Шаг 5(III). Уменьшив количество каналов в пути m1,4,3 , увеличим в m1,5,3

 

         Шаг 4(IV). Проверка показала, что перегруженных ребер нет, следовательно, план допустим.

 

         Шаг 6. Решение окончено: построен план распределения каналов, удовлетворяющий заданным условиям.

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

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

        

 

 

 

Список литературы

1.     Шварц М. Сети ЭВМ. Анализ и проектирование. – М: Радио и связь, 1981.

2.     Глушков В. М. Сети ЭВМ. – М: Наука, 1977.

3.     Теория сетей связи. / Под ред. В.Н.Рогинского/ -М: Радио и связь, 1981.

4.     Основы построения сетей и систем электросвязи. Методические указания и контрольное задание. / Сост. А.П.Пшеничников,     Г.Л. Слепова / -М: НИС, 1991.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


ПРИЛОЖЕНИЕ I                                                                

№ 1.0.

 

S0

S1

S2

S3

S4

S5

a0=-15

S1

5

-

3

8

7

2

a1=3

S2

7

4

-

5

4

3

a2=4

S3

2

3

1

-

4

1

a3=3

S4

1

7

4

6

-

5

a4=2

S5

4

8

3

4

5

-

a5=3

r=6

№1.2.

 

S0

S1

S2

S3

S4

S5

a0=-18

S1

2

-

7

9

6

3

a1=3

S2

5

7

-

11

10

4

a2=5

S3

6

9

11

-

7

3

a3=4

S4

1

6

10

7

-

7

a4=2

S5

10

3

4

3

7

-

a5=4

r=7

№ 1.4.

 

S0

S1

S2

S3

S4

S5

S6

a0 =

-22

S1

10

-

6

4

5

7

3

a1=2

S2

3

6

-

2

4

8

6

a2=4

S3

4

4

2

-

7

9

3

a3=2

S4

5

5

4

7

-

4

6

a4=3

S5

2

7

8

9

4

-

5

a5=5

S6

4

3

6

3

6

5

-

a6=5

r=8

№ 1.6.

 

S0

S1

S2

S3

S4

S5

a0=-22

S1

10

-

8

13

15

11

a1=5

S2

14

8

-

7

4

15

a2=4

S3

17

13

7

-

11

9

a3=5

S4

21

15

4

11

-

7

a4=2

S5

12

11

15

9

7

-

a5=6

r=10

№ 1.8.

 

S0

S1

S2

S3

S4

S5

a0=-15

S1

5

-

3

8

7

2

a1=3

S2

7

4

-

5

4

3

a2=4

S3

2

3

1

-

4

1

a3=3

S4

1

7

4

6

-

5

a4=2

S5

4

8

3

4

5

-

a5=3

r=6

 

 

№ 1.1.

 

S0

S1

S2

S3

S4

S5

а0=-15

S1

2

-

7

9

6

4

a1=3

S2

5

7

-

11

10

8

a2=5

S3

1

9

11

-

10

8

a3=2

S4

6

4

10

8

-

11

a4=2

S5

10

11

8

4

7

-

a5=3

r=5

№ 1.3.

 

S0

S1

S2

S3

S4

S5

a0=-12

S1

3

-

5

4

7

10

a1=2

S2

5

5

-

2

1

10

a2=1

S3

7

4

2

-

4

2

a3=3

S4

6

7

1

4

-

8

a4=4

S5

1

10

6

1

8

-

a5=2

                   r=5

№ 1.5.

 

S0

S1

S2

S3

S4

S5

S6

a0=

-23

S1

5

-

4

3

7

5

2

a1=4

S2

7

4

-

8

3

1

4

a2=4

S3

8

3

8

-

11

17

9

a3=6

S4

2

7

3

11

-

6

5

a4=2

S5

4

5

1

17

6

-

7

a5=3

S6

11

2

4

9

5

7

-

a6=4

                   r=6

№ 1.7.

 

S0

S1

S2

S3

S4

S5

a0=-25

S1

6

-

8

12

4

10

a1=7

S2

12

8

-

11

6

9

a2=4

S3

15

12

11

-

7

13

a3=5

S4

9

4

6

7

-

5

a4=3

S5

7

10

9

13

5

-

a5=6

                   r=7

№ 1.9.

 

S0

S1

S2

S3

S4

S5

a0=-27

S1

11

-

9

7

11

4

a1=7

S2

13

9

-

6

10

12

a2=3

S3

17

7

6

-

4

8

a3=9

S4

10

11

10

4

-

5

a4=2

S5

14

4

12

8

5

-

a5=6

                   r=9

 



 

          

№ 2.0.

 

S0

S1

S2

S3

S4

S5

a0=-16

S1

2

-

3

4

5

1

a1=2

S2

7

4

-

3

2

3

a2=4

S3

4

3

3

-

5

4

a3=5

S4

5

7

2

4

-

6

a4=2

S5

3

8

4

1

1

-

a5=3

r=6

№ 2.2.

 

S0

S1

S2

S3

S4

S5

S6

a0=-22

S1

5

-

4

3

6

4

1

a1=2

S2

2

6

-

2

4

5

7

a2=3

S3

7

3

3

-

3

4

2

a3=5

S4

8

2

6

2

-

4

3

a4=3

S5

4

5

4

4

4

-

3

a5=5

S6

10

2

1

5

2

4

-

a5=4

r=8

№ 2.4.

 

S0

S1

S2

S3

S4

S5

a0 =-20

S1

8

-

3

5

7

2

a1=5

S2

4

3

-

2

6

5

a2=4

S3

3

4

10

-

6

2

a3=5

S4

1

2

6

6

-

4

a4=2

S5

2

5

8

2

4

-

a5=4

r=8

№ 2.6.

 

S0

S1

S2

S3

S4

S5

a0=-19

S1

8

-

4

7

6

3

a1=4

S2

12

4

-

5

10

8

a2=6

S3

15

7

5

-

3

4

a3=3

S4

4

6

10

3

-

1

a4=2

S5

7

3

8

4

4

-

a5=4

r=6

№ 2.8.

 

S0

S1

S2

S3

S4

S5

a0=-23

S1

3

-

8

12

4

1

a1=7

S2

4

8

-

3

1

5

a2=3

S3

1

12

3

-

6

2

a3=5

S4

4

4

1

6

-

7

a4=4

S5

3

1

5

2

5

-

a5=4

r=7

 

 

№ 2.1.

 

S0

S1

S2

S3

S4

S5

а0=-12

S1

3

-

5

4

7

8

a1=2

S2

5

5

-

2

1

9

a2=1

S3

7

3

2

-

4

2

a3=3

S4

2

4

4

4

-

8

a4=4

S5

3

7

3

1

8

-

a5=2

r=5

№ 2.3.

 

S0

S1

S2

S3

S4

S5

S6

a0=-19

S1

7

-

6

4

5

3

1

a1=2

S2

3

6

-

4

2

5

4

a2=4

S3

4

4

4

-

3

5

6

a3=2

S4

5

5

5

2

-

1

7

a4=3

S5

3

7

3

4

3

-

7

a5=3

S6

4

2

1

3

1

8

-

A6=5

                   r=8

№ 2.5.

 

S0

S1

S2

S3

S4

S5

a0=

-15

S1

11

-

9

7

11

4

a1=3

S2

12

9

-

4

2

7

a2=4

S3

8

7

4

-

12

8

a3=2

S4

7

11

12

10

-

13

a4=3

S5

10

4

8

4

6

-

a5=3

                   r=6

№ 2.7.

 

S0

S1

S2

S3

S4

S5

a0=-18

S1

2

-

7

9

3

6

a1=3

S2

5

7

-

11

10

4

a2=5

S3

6

9

11

-

5

6

a3=4

S4

1

3

10

5

-

4

a4=2

S5

10

6

4

6

4

-

a5=4

                   r=7

№ 2.9.

 

S0

S1

S2

S3

S4

S5

a0=-17

S1

4

-

7

9

3

4

a1=2

S2

2

7

-

3

5

2

a2=3

S3

7

9

3

-

4

6

a3=3

S4

3

4

5

4

-

3

a4=6

S5

4

3

2

7

8

-

a5=3

                   r=6

                                                                

№ 4.0.

 

S0

S1

S2

S3

S4

S5

a0=-15

S1

7

-

2

9

11

4

a1=4

S2

11

7

-

7

13

10

a2=2

S3

10

13

 

-

 

 

a3=3

S4

4

6

 

 

-

 

a4=2

S5

5

10

 

 

 

-

a5=4

r=7

 

№ 4.2.

 

S0

S1

S2

S3

S4

S5

a0=-19

S1

6

-

7

9

3

4

a1=3

S2

4

7

-

11

4

6

a2=5

S3

8

9

11

-

5

10

a3=6

S4

9

3

4

5

-

7

a4=3

S5

11

4

6

10

8

-

a5=2

r=6

№ 4.4.

 

S0

S1

S2

S3

S4

S5

a0 =-18

S1

4

-

6

2

5

7

a1=2

S2

2

6

-

4

7

1

a2=4

S3

5

2

4

-

2

5

a3=2

S4

7

5

7

2

-

3

a4=5

S5

6

7

1

5

3

-

a5=5

r=6

№ 4.6.

 

S0

S1

S2

S3

S4

S5

a0=-16

S1

3

-

5

6

2

1

a1=4

S2

5

5

-

7

4

8

a2=3

S3

10

6

7

-

3

10

a3=2

S4

11

2

4

3

-

13

a4=5

S5

13

1

8

10

13

-

a5=2

r=7

№ 4.8.

 

S0

S1

S2

S3

S4

S5

a0=-23

S1

4

-

3

6

5

7

a1=5

S2

5

3

-

2

4

8

a2=3

S3

3

6

2

-

5

3

a3=4

S4

6

5

4

3

-

6

a4=5

S5

7

7

8

5

6

-

a5=6

r=8

 

 

 

№ 4.1.

 

S0

S1

S2

S3

S4

S5

а0=-22

S1

4

-

6

5

3

1

a1=4

S2

5

6

-

7

4

2

a2=8

S3

7

5

7

-

3

5

a3=2

S4

6

3

4

3

-

8

a4=6

S5

3

1

2

5

8

-

a5=2

r=8

 

№ 4.3.

 

S0

S1

S2

S3

S4

S5

a0=-21

S1

7

-

3

5

8

10

a1=7

S2

9

3

-

6

7

9

a2=3

S3

3

5

6

-

2

4

a3=5

S4

4

8

7

2

-

 

a4=2

S5

6

10

9

4

 

-

a5=4

                   r=7

№ 4.5.

 

S0

S1

S2

S3

S4

S5

a0-18

S1

4

-

6

2

4

3

a1=4

S2

8

6

-

5

9

10

a2=5

S3

3

2

5

-

7

6

a3=3

S4

2

4

9

7

-

4

a4=2

S5

5

3

10

6

4

-

a5=4

                   r=6

№ 4.7.

 

S0

S1

S2

S3

S4

S5

a0=-20

S1

5

-

11

2

3

6

a1=1

S2

3

11

-

5

1

4

a2=4

S3

8

2

5

-

3

2

a3=7

S4

12

3

1

3

-

4

a4=3

S5

10

6

4

2

1

-

a5=5

                   r=7

№ 4.9.

 

S0

S1

S2

S3

S4

S5

a0=-24

S1

4

-

11

2

13

5

a1=3

S2

5

11

-

4

2

8

a2=7

S3

7

2

4

-

6

9

a3=5

S4

3

13

2

6

-

5

a4=4

S5

6

5

8

9

5

-

a5=5

                   r=9

 

 

                           ПРИЛОЖЕНИЕ II

№ 1.

 

K0

K1

K2

K3

T1

7

4

6

9

T2

5

2

0

8

T3

2

4

6

5

T4

1

4

2

10

T5

8

7

4

12

T6

7

5

9

0

T7

10

6

11

4

r=3; f1=4; f2=2; f3=5.

 

№ 2.

 

K0

K1

K2

K3

K4

T1

7

8

0

6

4

T2

4

5

2

5

3

T3

9

7

12

3

6

T4

12

7

9

0

10

T5

4

5

7

3

2

T6

7

0

5

4

13

T7

10

5

10

11

15

r=2; f1=1; f2=5; f3=4; f4=2.

 

№ 3.

 

K0

K1

K2

K3

T1

7

4

5

3

T2

5

4

7

9

T3

12

8

11

0

T4

10

4

5

7

T5

14

8

6

9

T6

8

3

2

4

r=3; f1=5; f2=6; f3=4.

 

№ 4.

 

K0

K1

K2

K3

K4

T1

5

7

3

0

4

T2

6

7

4

2

8

T3

8

5

0

10

11

T4

10

8

9

13

15

T5

15

11

8

12

0

T6

8

3

4

5

6

r=3; f1=4; f2=5; f3=6; f4=2.

 

 

 

№ 5.

 

K0

K1

K2

K3

T1

4

0

3

5

T2

3

4

2

1

T3

2

4

0

6

T4

3

2

4

5

T5

5

6

3

2

r=2; f1=2; f2=3; f3=2.

 

 

 

№ 6.

 

K0

K1

K2

K3

T1

4

2

5

3

T2

2

5

3

6

T3

5

8

0

7

T4

7

4

4

2

T5

3

4

5

1

r=2; f1=6; f2=2; f3=3.

 

 

 

№ 7.

 

K0

K1

K2

K3

T1

4

0

2

3

T2

8

5

4

10

T3

7

4

1

2

T4

4

5

2

0

T5

3

4

2

5

T6

9

7

4

3

r=3; f1=f2=4; f3=2.

 

№ 8.

 

K0

K1

K2

K3

K4

T1

4

0

2

2

3

T2

8

5

6

4

10

T3

7

4

3

1

2

T4

4

5

11

2

0

T5

3

4

9

2

5

T6

9

7

10

4

3

r=2; f1=3; f2=2; f3=3.



Продолжение приложения II

 

№ 9.

 

K0

K1

K2

K3

T1

4

0

2

3

T2

8

5

4

10

T3

5

4

7

9

T4

7

4

1

2

T5

14

8

6

9

T6

3

4

2

5

r=2; f1=f2=f3=2.

 

 

 

 

 

№ 10.

 

K0

K1

K2

K3

T1

4

0

3

5

T2

3

4

2

1

T3

2

4

0

6

T4

3

2

4

5

T5

5

6

3

2

T6

8

3

2

4

r=3; f1=2; f2=4; f3=5.

 

 


 

ПРИЛОЖЕНИЕ III


 

 

 

ПРИЛОЖЕНИЕ III (продолжение)

 

 

 

22

24

30

21

7

 

4

5

3

6

2

1

8

10

17

22

15

13

18

20

20

22

30

30

25

32

31

25

33

34

20

29

4

6

8

1

7

 

5

2

3

8

10

25

30

45

42

40

20

24

34

52

5

3

7

 

1

6

4

2

8

20

20

14

28

44

18

24

55

25

35

40

3

1

4

2

6

7

 

5

35

20

21

15

10

17

12

20

21

12

8

32

3

4

8

7

 

5

2

1

6

18

15

11

14

28

10

16

20

15

7

8

22

3

7

 

2

1

5

4

6

8

9

18

25

35

25

30

38

36

30

36

28

3

2

1

5

4

6

8

7

 

35

25

25

27

24

15

24

16

30

18

28

2

1

5

4

6

8

7

 

3

21

25

20

19

14

15

11

28

12

18

30

20

2

1

5

4

8

7

 

3

9

6

23

10

18

20

30

31

20

40

20

20

31

14

28

2

1

4

7

 

3

9

6

8

5

Структура сети

Yi j

Структура сети

Yi j

 

 

2.0

 

Y18 = 18

Y25 = 25

Y36 = 35

Y82 = 15

 

 

2.1

 

Y14 = 24

Y26 = 21

Y37 = 28

Y15 = 34

 

 

 

2.2

 

 

 

Y28 = 24

Y17 = 28

Y36 = 12

Y53 = 48

 

 

 

2.3

 

 

 

 

 

 

Y17 = 24

Y25 = 31

Y36 = 44

Y24 = 20

 

 

 

2.4

 

 

 

 

 

 

 

Y14 = 10

Y15 = 15

Y27 = 12

Y36 = 20

 

 

 

2.5

 

Y14 = 10

Y29 = 15

Y36 = 7

Y47 = 6

 

 

 

2.6

 

 

 

 

 

 

 

 

Y16 = 20

Y27 = 30

Y38 = 20

Y47 = 10

 

 

 

2.7

 

 

Y16 = 23

Y27 = 20

Y38 = 15

Y54 = 30

 

 

 

2.8

 

 

 

 

 

 

 

 

Y17 = 18

Y25 = 8

Y48 = 15

Y61 = 28

 

 

 

2.9

 

 

Y17 = 20

Y48 = 28

Y51 = 13

Y79 = 16

 

 

 

ПРИЛОЖЕНИЕ III (продолжение)

 

Структура сети

Yi j

Структура сети

Yi j

16

2

4

3

6

5

1

10

15

7

28

22

15

5

18

1

2

3

5

4

35

42

25

30

45

27

 

4.0

 

 

 

 

 

 

 

Y13 = 20

Y38 = 20

Y43 = 24

 

 

4.1

 

Y14 = 10

Y26 = 15

Y37 = 7

Y45 = 10

1

2

3

6

5

4

40

30

25

18

24

24

20

25

16

21

2

3

6

4

1

5

21

12

17

20

20

25

8

32

 

 

4.2

 

 

 

Y14 = 10

Y15 = 15

Y26 = 12

Y36 = 22

 

 

 

4.3

 

 

 

 

 

 

Y25 = 31

Y36 = 44

Y24 = 30

28

2

3

6

7

5

1

4

40

14

24

25

20

16

30

15

18

20

1

2

3

7

6

5

4

10

15

42

50

20

45

30

40

30

25

17

 

 

4.4

8

10

25

30

45

42

40

20

24

34

52

5

3

7

 

1

6

4

2

8

20

 

 

 

 

 

 

Y27 = 24

Y16 = 28

Y53 = 50

 

 

 

 

4.5

 

Y14 = 24

Y25 = 31

Y36 = 22

Y53 = 48

2

1

5

6

3

4

20

40

30

25

20

20

40

24

25

2

3

7

6

5

1

4

45

40

40

20

24

42

40

20

10

 

 

4.6

 

 

 

 

 

 

 

 

Y27 = 24

Y17 = 28

Y36 = 12

Y53 = 40

 

 

 

4.7

 

 

Y26 = 24

Y15 = 28

Y53 = 48

 

2

2

2

2

2

2

2

38

30

34

25

22

25

30

30

33

3

1

5

6

2

4

10

30

34

25

20

25

25

30

 

 

4.8

 

 

 

 

 

 

 

 

Y14 = 24

Y26 = 21

Y15 = 34

 

 

 

 

4.9

 

 

Y14 = 24

Y26 = 21

Y15 = 34

 

 

 

 

 

                                                    СОДЕРЖАНИЕ

I ПРОГРАММА КУРСА........................................................................... 2

Предисловие...................................................................................…3

1.1 Содержание учебного материала.................................................... 3

1.2 Перечень практических работ......................................................... 3

1.3 Перечень лабораторных работ........................................................ 3

1.4 Расчетно-графические (или контрольные) работы......................... 4

 Список литературы.............................................................................. 4

 

II  МЕТОДИЧЕСКИЕ УКАЗАНИЯ К КОНТРОЛЬНЫМ РАБОТАМ..... 4

2.1Синтез централизованных сетей [1]................................................. 4

2.1.1 Упрощенный вариант задачи синтеза....................................... 4

2.1.2 Синтез двухуровневой централизованной сети...................... 14

2.2 Распределение каналов на вторичной некоммутируемой сети..... 20

2.2.1 Постановка задачи................................................................... 20

2.2.2 Алгоритм.................................................................................. 21

Список литературы............................................................................. 23

ПРИЛОЖЕНИЕ I.................................................................................... 24

ПРИЛОЖЕНИЕ II................................................................................... 24

ПРИЛОЖЕНИЕ III.................................................................................. 35

 

 

 

 

 

 

Сводный план 2001, поз.108

 

 

Галина Петровна Данилина

 

 

 

Сети электросвязи

 

 

Программа, методические указания и контрольные задания

(для студентов специальностей 3801, 3802 заочной формы обучения)

 

 

 

 

 

Редактор В. В. Шилина

 

 

 

 

 

Подписано в печать                                                   Формат 60´84. 1/16.

Тираж     300 экз.                                                                  Бумага типографическая № 1.

Объем      1,8      уч.- изд. л.                                        Заказ               . Цена

 

 

 

 

Ротапринт Алматинского института энергетики и связи  

 

 

480013, Алматы, Байтурсынова, 126.