Понятия о структуре сети, путях и сечениях

Воронежский институт МВД России

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

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

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

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

Лекция №1 «Принципы построения коммутируемых

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

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

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

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

Разработал:

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

Воронеж 2011 г.

Лекция №1 «Принципы построения коммутируемых

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

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

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

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

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

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

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

№	Учебные вопросы	Время, мин
	Организационная часть
	Введение
	Понятия о структуре сети, путях и сечениях.
	Структурные матрицы и операции с ними
	Подведение итогов
	Ответы на вопросы
	Выдача задания на самоподготовку

Литература

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

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

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

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

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

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

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

ПОНЯТИЯ О СТРУКТУРЕ СЕТИ, ПУТЯХ И СЕЧЕНИЯХ

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

Для изучения структурных свойств сетей их удобнее всего представить в виде графа без петель (рис. 1) G = {А, В}, где A = {a₁, ..., a_N} - совокупность пунктов (узлов) сети (вершин графа) и B = {b_ij} - множество ребер, соединяющих узлы а_i и а_j, соответствующих всем линиям или каналам связи между этими узлами.

Рис. 1. Пример сети, изображенной в виде графа

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

Граф может быть записан матрицей смежности (связности) порядка N, по главной диагонали которой поставлены черточки (знак неопределенности), которые в конкретных случаях могут заменяться 0 или 1, а вхождения а_ij принимают значения 1, если есть ребро, связывающее узел а_i, с узлом a_j, и 0, если ребра нет. Если в сети нет направленных ребер, то матрица будет симметричной по отношению к главной диагонали. Для сети рис. 1 матрица смежности имеет вид:

.

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

Пункты (узлы), соединенные ребром, будем называть смежными. Число ребер, инцидентных данному пункту (входящих или исходящих), назовем рангом r(а_i) этого узла. Узел ранга 1 является тупиковым - оконечным, - и через него не могут проходить никакие пути.

Для упрощения записи отдельные ребра могут обозначаться разными символами, например буквами а, b, с, ... При направлении от узла с большим номером к узлу с меньшим, если это важно, над символом будем ставить черту. Если ребро между узлами 1 и 4 обозначено через с, то b₁₄ = с, b₄₁ - . Если в сети имеется возможность передать информацию из a_s в a_t (независимо от того, происходит это по прямым каналам или через промежуточные узлы с коммутацией каналов или сообщений), то будем говорить, что существует связь от a_s к a_t. При двусторонней передаче будем говорить, что между a_s и a_t имеется связь E_st. Для осуществления связи в сети должен быть соответствующий путь или пути.

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

Рангом пути r(μ_st) (иногда этот показатель называют длиной, пути, но мы под длиной пути будем понимать физическую длину, т. е. расстояние между узлами a_s и a_t по данному пути) будем называть число ребер, образующих этот путь. Минимальный ранг пути 1, максимальный N - 1, когда путь проходит через все узлы.

Путь μ^k_st (k - порядковый номер пути) будем записывать перечнем ребер, образующих этот путь, т. е.:

,

или упорядоченным (по их месту в пути) перечнем узлов:

.

Все пути от a_s к a_t образуют множество m_st, а совокупность (объединение) двух множеств, соответствующих противоположным направлениям, - множество M_st всех путей между a_s и a_t: M_st = m_st U m_ts. Для ненаправленных сетей M_st = m_st = m_ts.

В реальной сети, как правило, для связи между заданными узлами a_s и a_t используются не все возможные пути, а только пути, выделенные по какому-либо показателю или обладающие не которыми заданными свойствами. Множество путей, обладающих свойством *, будем соответственно обозначать m*_st, m*_ts или M*_st. Так, могут быть выделены пути: допустимые ; оптимальные , имеющие ранг не более r; и т. п. В некоторых случаях приходится рассматривать независимые (по ребрам или узлам) пути, т. е. пути, не включающие одни и те же ребра или не проходящие через одни и те же узлы.

В сети с одним направленным ребром b₂₄ = е (рис. 2а) между узлами 1 и 3 будет по три пути в каждом направлении: m₁₃ = {ab, cd, aed} = ab\/ cd \/ aed и m₃₁ = ab\/cd\/ bсе. Список множества т₁₃ будет иметь вид:

	a	b	c	d	e

Независимыми по ребрам путями здесь будут оба пути ранга 2, проходящие через узлы 2 и 4.

Связной называется сеть, любые узлы которой связаны хотя бы одним путем. Сеть называется h-связной, если любые два узла связаны независимыми путями, число которых - не менее h. Так, сеть рис. 2 является двухсвязной (h = 2). Понятие связности чаще будем относить не ко всей сети, а к заданным узлам a_s и а_t (h_st-связность), а также к множеству путей, обладающих заданным свойством (h*_st-связность). Так, например, можно говорить об -связности по путям ранга не более r. Например, для сети, изображенной на рис. 2а, h₂₄=3,

Рис. 2. Мостиковая сеть с направленным ребром (а) и

сечения для путей с r£2

Сечением s сети (графа) назовем не избыточную совокупность ребер (линий), которые надо изъять из сети (графа), чтобы нарушилась ее связность. Сечениями a_st по отношению к узлам a_s и a_t будем называть такие сечения, при которых узлы a_s и a_t оказываются в разных подсетях (подграфах). При этом в сети (графе) с направленными ребрами будем различать направленные сечения, нарушающие связи от a_s к a_t или наоборот, и ненаправленные - полностью нарушающие связи между a_s и a_t.

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

.

Рангом сечения r(s^l) будем называть число входящих в него ребер.

Из теории графов известно, что в ненаправленной сети необходимым и достаточным условием г-связности сети является то, что ранг всех сечений этой сети должен быть не менее h: .

Кроме множества S={s¹, ..., s^q} всех возможных сечений сети, разбивающих ее на две связные подсети, нас будут интересовать сечения s_st по отношению к заданной паре узлов a_s и a_t:

а) множество сечений S_st={a^l_st, ..., a^p_st}Î S, рассекающих все пути множества m_st, т. е. нарушающих связи от узла a_s к узлу а_t;

б) множество сечений , рассекающих все пути множества M_st, т. е. нарушающих все связи между узлами a_s и a_t;

в) множество квазисечений S*_st={a*^l_st, …, a*^p_st}, рассекающих все пути множества m*_st путей, обладающих свойством *. При этом в сети между узлами a_s и a_t могут остаться другие пути, т. е. сеть может остаться связной. Так, если сечение разрывает все пути от a_s к a_t, имеющих ранг не более r, то пути большего ранга могут в сети остаться.

Так, например, для связей от узла 1 к узлу 3 (рис. 2а) множество сечений S₁₃={ac, ad, bec, bd}, а для множества путей ранга 2 квазисечения (рис. 3.2б) ={ac, ad, bd, bc}. Отсюда видно, например, что квазисечение . bс, разрывая пути от 1 к 3 ранга 2, оставляет путь ранга 3.

Наряду с сечением введем понятие разреза сети - минимальной совокупности узлов или узлов и ребер, которые надо удалить из сети, чтобы сеть стала несвязной. Практический интерес представляют разрезы R_st по отношению к узлам a_s и a_t, исключающие все пути между этими узлами, или квазиразрезы R*_st, исключающие пути, обладающие свойством *. Для сети, изображенной на рис. 2б, по отношению к связям от узла 1 к узлу 3 будет только один разрез, включающий узлы а₂ и а₄: ,R₁₃ = {а₂а₄} или следующие сечения узлов и ребер: R₁₃ = (а₂с, a₂d, а₄а, а₄b).

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

1. Полно связная сеть (рис. 3а) - «каждый с каждым». В такой сети число ребер равно N(N-1)/2. Связность h = N-1.

Рис. 3. структура сетей различного вида

2.Древовидная сеть (рис. 3б) - «дерево». В такой сети между любыми двумя узлами может быть только один путь, т. е. сеть односвязная (h = 1). Число ребер в такой сети равно N-1. Частными случаями древовидной сети являются:

а) узловая сеть (рис. 3в) с иерархическим построением и соподчинением узлов;

б) звездообразная сеть (рис. 3г) с одним узлом;

в) линейная сеть (рис. 3д).

3.Петлевая (шлейфовая, кольцевая) сеть (рис. 3е). В ней число ребер равно N, и между каждыми двумя узлами имеется Два пути (h = 2).

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

Различают два вида сеток - плоскую (планарную), которая может быть нарисована на плоскости без пересечения ребер (рис 3ж) и неплоскую (непланарную), которую нельзя изобразить без пересечения ребер (рис. 3з). Среди сетеобразных структур можно выделить радиально-петлевую (паутинообразную) сеть которая при одной петле (рис. 3и) имеет 2(N-1) ребер и h = 3 Кроме этого, отметим ряд регулярных структур с равномерным распределением узлов по территории и однотипным соединением между соседними узлами. К последним относятся «ячеистые» структуры, в которых каждый узел (кроме расположенных по краям сети) имеет ранг г = 3, 4, 6 (рис. 3к, л, м) и т. д. При большом числе узлов в таких сетях число ребер приблизительно равно rN/2.

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

Рис. 4 Пример сети с узлами входящего сообщения

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

Рис. 5. Графы допустимых трасс для построения сетей при заданных узлах

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

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