Воронежский институт мвд России

Кафедра телекоммуникационных систем

Тезисы лекции

по дисциплине «Сети электросвязи»

Тематический модуль №5 «Принципы построения коммутируемых систем электросвязи»

Лекция №2 «Расчет коммутируемых сетей связи»

Обсуждены и одобрены

на заседании кафедры ТКС

Протокол №__ от «___» ________2011г.

Разработал:

Ст. преподаватель кафедры ТКС майор милиции ______________ А.Н. Глушков

Воронеж 2011 г.

Лекция №2 «Расчет коммутируемых сетей связи»

Учебно - воспитательные цели:

1. Ознакомить слушателей со структурным анализом сети

2. Вооружить слушателей основой по оценке ребер и путей в сети.

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

Время: 2 часа.

Учебные вопросы и расчет времени:

№	Учебные вопросы	Время, мин
	Организационная часть	3
	Введение	4
1	Структурный анализ сети.	15
2	Оценки ребер и путей в сети.	35
3	Односвязные кратчайшие сети.	10
	Подведение итогов	3
	Ответы на вопросы	7
	Выдача задания на самоподготовку	3

Литература

1. Защищённые системы связи ОВД: учебное пособие /А.Н. Бабкин, С.Н. Хаустов, В.С. Зарубин. – Воронеж: Воронежский институт МВД России, 2009. – 91 с.

2.Системы мобильной связи: учебное пособие /С.Н. Хаустов, В.С. Зарубин, А.Н. Бабкин. – Воронеж: Воронежский институт МВД России, 2008.–127 с.

3. В.П. Ипатов, В.К. Орлов, И.М. Самойлов, В.Н. Смирнов. Системы мобильной связи: Учебное пособие для вузов /Под ред. В.П. Ипатова. – М.: Горячая линия – Телеком, 2003. – 272с.

4. Основы построения систем и сетей передачи информации: Учебное пособие для вузов / В.В. Ломовицкий, А.Н.Михайлов, К.В. Шестак, В.М. Щекотихин; под ред. В.М. Щекотихина – М.: Горячая линия – Телеком, 2005. – 382с.

5. Телекоммуникационные системы и сети: Учебное пособие, В.3 Томах / Б.Н.Крук, В.Н. Попантонопуло, В.П. Шувалов; под ред. В.П. Шувалова. – М.: Горячая линия – Телеком, 2003. – 647с.

6. А.В. Петраков. Основы практической защиты информации. – М.: Радио и связь, 2001. – 360с.

7. А.В. Шмалько. Цифровые сети связи. Основы планирования и построения. – М.: Эко–Трендз, 2001. – 283с.

Тезисы лекции

1. Структурный анализ сети

Используя граф G или структурную матрицу В сети, можно найти интересующие нас множества путей (как всех, так и удовлетворяющих некоторому заданному свойству) между любой парой узлов. Для нахождения всех возможных путей между всеми узлами можно воспользоваться последовательным возведением структурной матрицы В во вторую, третью и т. д. степени до тех пор, пока матрица не перестанет изменяться, т. е. станет характеристической. Если интересуют пути ранга не более q, то матрицу следует возводить только до q-й степени. Из структурной же матрицы В может быть найдено множество m_st всех путей от узла a_S к узлу a_t раскрытием определителя подматрицы B_ts, полученной из структурной матрицы В вычеркиванием s-гo столбца и t-и строки:

.

Так, из матрицы b₁ для узлов 1 и 5 (рис. 6 (Лекция2 Т.3)) получим

.

Первый из полученных определителей раскладываем по диагоналям, а второй - равен единице. Окончательно получим , т. е. имеется по одному пути ранга 1 (b), 2 (ас), 3 (adh) и 4 (adfg).

Графическим эквивалентом этого метода является построение дерева путей для заданного начального узла а_s которое строится по матрице В следующим образом:

1. Обозначаем узел через s и берем s-ю строчку матрицы В.

2. По этой строке выбираем номера узлов j₁ для которых b_Sj  Q и образуем множество узлов, имеющих от узла 5 путь ранга 1 (узлы первого яруса).

3. Узлы r•-го яруса с путями ранга r от узла s находятся под поочередным просмотром строк узлов j_r-1 в (r - 1)-м ярусе, которые не встречались в пути от s к j_r-1.

4. Построение дерева продолжается либо до получения путей максимально допустимого ранга, либо до тех пор, пока для узла j_r-1 не окажется, что все узлы уже вошли в путь sj_r-1

На рис. 1a показано дерево путей из узла 1 сети, изображенной на | •рис. 6 (Лекция2 Т.3) (матрица В1), а на рис. 1б - дерево путей, сходящихся к узлу 1, построенному аналогично предыдущему.

Сечения или квазисечения, рассекающие заданное множество m_st, M_st или M*st путей от узла a_s к узлу a_t (всех или обладающих определенными свойствами), определяют по следующему алгоритму, основанному на нахождении двойственной булевой функции.

Для этого:

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

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

3) раскрываются все скобки в соответствии с законами булевой алгебры. Каждое слагаемое полученного выражения будет представлять одно из возможных сечений ^l_st (или квазисечений *_st). Напоминаю, что при перемножении булевых многочленов удобно пользоваться формулой (а V х) (а V y)=а V xy и следует исключать лишние члены, пользуясь формулой a \/ab = a.

Рис. 1 Деревья входящих и исходящих путей от узла 1 сети изобр. на рис. 6 лекция 2 т.3

Для схемы рис. 2а между узлами 1 и 3 имеются пути М₁₃ =аd Vahe V

V agde Vcde Vcdhb Vcgb Vcghe, откуда получим S₁₃ =( aVb )( aVhVe ) ( aVgVdVe ) ( cVdVe ) ( cVdVhVb ) ( cVgVb ) ( с V g V h V e) = be V bhd V Vac Vadg Vaegh Vbcgh, т. е. имеется шесть сечений рангов 2, 3 и 4, показанных на рис. 2б. Для той же сети множество путей ранга не более трех будет = ab Vahe Vcde Vcgb, откуда получим = (aVb) (aVhVe)  (cVdVe) (c VgVb) = beVac Vabd Vadg Vage Vbch Vbdh, т. е. получается семь сечений (рис. 2в) рангов 2 и 3, причем некоторые из них (не входящие в S₁₃ как, например abd) не разрезают сети и в сети остается путь ранга 4. Этот же метод может быть применен для нахождения разрезов только по узлам или по узлам и ребрам, если пути записать с включением символов узлов.

Рис. 2 Пример нахождения сечений и квазисечений