1 Лекция 2 Математическое описание сетей связи

2 Вопросы лекции 2 1. Морфологическое описание сети с помощью графа 2. Морфологическое описание в матричной форме 3. Потоковая модель сети 4. Вероятностная модель сети

3 Морфологическое описание сети Формализация описания сети необходима для решения задач анализа и синтеза ( проектирования) Описание телекоммуникационной сети может быть Морфологическое Функциональное Морфологическое описание – это описание состава, конфигурации сети и взаимосвязей ее элементов Морфоло́гия (от греч. μορφή «форма» + греч. λογία «наука») в широком понимании наука о формах и строении.греч. наука Функциональное описание - это описание процессов функционирования сети и закономерностей изменения ее параметров

4 Морфологическое описание сети с помощью графа Основные понятия теории графов Граф - математический инструмент морфологического описания сети. Граф G( N, M ) описывает структуру сети, в котором количество вершин N соответствует количеству коммутационных центров ( КЦ), а ребра M – ветвям/линиям/каналам связи, соединяющим КЦ Граф называется помеченным, если его вершины и ребра имеют идентификационные надписи Граф называют ориентированным, если в нем есть ориентированные ребра

5 Морфологическое описание сети с помощью графа Вершины n i и n j смежные, если существует ребро m ij Ребро m ij является инциндентным ( прилегающим) для вершин n i и n j Пример графа, отображающего структуру 4- узловой сети

6 Морфологическое описание сети с помощью графа Свойство декомпозиции графа Любой граф G ( N, M ) можно разбить на два подграфа G ( N 0, M 0 ) и G ( N T, M T ): G ( N, M ) = G ( N 0, M 0 ) U G ( N T, M T ) Подграф G ( N T, M T ) соответствует сети транзитных КЦ Подграф G ( N 0, M 0 ) соответствует сети оконечных КЦ

7 Морфологическое описание сети с помощью графа Изоморфизм (от греч. ísos равный, одинаковый, подобный и морфо- форма).греч. Общее понятие изоморфизма означает наличие сходства у разных объектов. Два графа G ( N, M ) и G ( N, M ) называются изоморфными, если между множеством их вершин и ребер можно существует однозначное соответствие вершин {n i } {n i } и ребер {m ij } {m ij } Пример изоморфных графов

8 Морфологическое описание сети с помощью графа Маршрут ( путь) Маршрутом в графе называется чередующаяся последовательность вершин и ребер Последовательность начинается и заканчивается вершиной Каждое ребро последовательности инциндентно двум вершинам = n 1 U n 2 U n 3 U…U n k-1 U n k, где n k О N Маршруты или пути в графе обычно определяется для выделенного направлений связи (между любой парой вершин) Маршруты ( пути) бывают: Независимые – это маршруты, которые не имеют общих ребер (ветвей) n i ( 1 ) П N ( 2 ) и n i ( 2 ) П N ( 1 ) N ( 1 )/ N ( 2 ) = Ж Зависимые – маршруты с общими ребрами ( ветвями) N ( 1 )/ N ( 2 ) = N ( 2 )* N ( 1 ) = Ж

9 Морфологическое описание сети с помощью графа Пример независимых маршрутов в сети в направлении 1-5 N ( 1 ) = { 1, 2, 3, 11, 4, 5} N ( 2 ) = { 1,9,10,6,5} Длина пути в графе – количество входящих в него ребер D( 1 ) = 5 ; D( 2 ) = 4 Кратчайший путь между двумя вершинами – это минимальное расстояние между этими вершинами, выраженное в числе ребер min ( 1 -5) = 4

10 Морфологическое описание сети с помощью графа Диаметром графа D называется минимальное расстояние между наиболее удаленными вершинами D= min max (i,j) i,j Диаметр графа: D = 4 Каждая вершина графа n i имеет степень Deg n i. Deg n i – это число равное числу инцидентных ребер Например. Deg 7 = 3; Deg 6 = 4; Deg 1= 2

11 Морфологическое описание сети с помощью графа Подграфы: G 1 (1,9,8) и G 2 ( 3,4,5,6,11,) Сечение графа G ( N, M ) по вершинам n i представляет собой множество вершин {n i }, удаление которых приводит к образованию несвязанных подграфов. Сечение графа G ( N, M ) по ребрам m ij ( или реберное сечение) представляет собой множество ребер {m ij }, удаление которых приводит к образованию несвязанных подграфов. Сечение графа G по вершинам: {2,10,7} Сечение графа G по ребрам: {m 23, m 10,11, m 11,6, m 65 } Подграфы: G 1 (1,2,9,10,7,8,6) и G 2 ( 3,4,5,11,)

12 Морфологическое описание в матричной форме Для аналитических исследований применяется матричная форма описания структуры сети. Основные типы матриц Связности || A|| Мощностей ||V|| ( N*N) Инциденций ||B|| Матрицы ||A|| и ||V|| имеют размерность ( N*N), где N – число узлов (вершин) a ij = { 1, если КЦ i и КЦ j соединены ветвью 0, если КЦ i и КЦ j не соединены ветвью v ij – параметр линии связи на ветви m ij (число каналов)

13 Морфологическое описание в матричной форме Если ij = ji, то матрицы ||A|| и ||V|| можно представить в треугольной форме ( включены только наддиагональные элементы) Пример описания 5 узловой сети

14 Морфологическое описание в матричной форме Матрица инциденций ||B||- это матрица размерностью N*M, в которой ||В|| = {b ij }, b ij = { 1, если ветвь m ij инцидентна вершине n i 0, если ветвь m ij не инцидентна вершине n i Между матрицами связности и инциденции существует взаимное соответствие А=В Т В – 2*I, где В Т – транспонированная матрица инциденций, I – единичная матрица, размерности М*М

15 Потоковая модель сети Для функционального описания сети используются Потоковая модель сети Вероятностная модель сети Функциональное описание сети характеризует основные процессы ее функционирования: Передача сообщений Распределение информации Выход из строя и восстановление элементов сети Качество обслуживания на ветвях и направлениях связи сети

16 Потоковая модель сети Потоковая модель характеризует способность сети по передаче сообщений от источников информации к потребителям в условиях нормального ее функционирования Процесс передачи сообщений по сети можно описать матрицей где C ij (t ij,p ij ) – количество сообщений, обслуженных на ветви mij за время tij при соблюдении вероятностно временного параметра рij C ij (t ij,p ij ) = 0 при а ij =0 ( при условии отсутствия ветви m ij )

17 Потоковая модель сети Потоковая модель характеризует способность сети по передаче сообщений от источников информации к потребителям в условиях нормального ее функционирования Процесс передачи сообщений по сети можно описать матрицей где C ij (t ij,p ij ) – количество сообщений, обслуженных на ветви mij за время tij при соблюдении вероятностно временного параметра рij C ij (t ij,p ij ) = 0 при а ij =0 ( отсутствии ветви m ij )

18 Потоковая модель сети Среднее число одновременно функционирующих сообщений в сети можно рассчитать в виде С ф = C ij (t ij,p ij ) Среднее число сообщений одновременно передаваемых в направлении связи можно также рассчитать как сумму переданных сообщений по всем ветвям, входящим во все пути данного направления Сн = Cм(tij,pij)

19 Вероятностная модель сети В любой произвольный момент времени t канал ветви m ij может быть в состоянии Свободен/ Занят Для установившегося режима работы сети нахождение каждой ветви m ij в занятом состоянии можно описать матрицей где p m ij (t) – вероятность отказа в обслуживании на ветви m ij в произвольный момент времени t

20 Вероятностная модель сети Оценить вероятность обслуживания сообщения в направлении связи можно с помощью формулы. при =1 ( одном пути установления соединения) q= П (1 – p ij ) ij p= 1- q = 1- П (1 – p ij ) ij при =k> 1 ( при k путей установления соединений) Q=1- П (1 - П (1 – p ij )) k ij P= П (1 - П (1 – p ij )) k ij

21 Вероятностная модель сети Надежность сети может быть описана в виде матрицы где r m ij (t) – вероятность безотказной работы ветви m ij в произвольный момент времени t

22 Литература Романов А. И. Телекоммуникационные сети и управление: Учебное пособие –К. ИПЦ « Киевский университет», 2003, -247с. Корнышев Ю.Н., Фань Г.Л. Теория распределения информации – М.: Радио и связь, 1985 Сети ЭВМ. Под редакцией В.М. Глушкова – М.: Связь, 1977 Бусленко Н. П. Моделирование сложных систем – М. : Наука, 1978 Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания – М.: Наука, 1966 Клейнрок Л. Коммутационные сети – М.: Наука, 1970 Шварц М. Сети ЭВМ. Анализ и проектирование - М.: Радио и связь, 1981 Советов Б.Я. и др. Построение сетей интегрального обслуживания – Л.: Машиностроение, Лен отд-е, 1990 Клейнрок Л. Вычислительные сети с очередями – М.: Мир, 1979 Хилс М.Т. Принципы коммутации в электросвязи - М.: Радио и связь, 1984 Френк Г., Фриш И. Сети, связь и потоки – М.: Связь, 1978

23 Спасибо за внимание!