Методические указания по выполнению лабораторной работы № 1

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

Задание на выполнение лабораторной работы №1

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

Таблица 1.1. Варианты заданий

№ вар.

Номер оконечного пункта и его координаты

x

y

x

y

x

y

x

y

x

y

x

y

x

y

x

y

x

y

x

y

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

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

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

Совокупность каналов, соединяющих непосредственно пару узлов a_i и a_j сети, образует ветвь b_ij. Простейшей записью структуры сети в графовых моделях является матрица связности, в которой элементы матрицы a_ij принимают значение 1, если есть ветвь, связывающая узлы a_i и a _j, и 0 – в противном случае. Если в сети нет направленных ветвей, то матрица связности будет симметричной относительно главной диагонали. Если такие ветви есть, то сеть будет несимметричной. Ненаправленная ветвь, соединяющая узлы a_i и a_j может быть обозначена двумя символами b_ij = b_ji.

Путь m_xy из узла a_x в узел a_y, представляющий собой упорядоченный набор ветвей, начинающихся в узле a_x и заканчивающихся в узле a_y, причем конец каждой предыдущей ветви совпадает в промежуточном для данного пути узле с началом последующей ветви, называется самонепересекающимся, то есть не проходящим дважды через один и тот же узел. Если путь состоит из ненаправленных ветвей, то он будет ненаправленным или двусторонним m_xy = m_yx. Пути могут быть зависимыми и независимыми. Рангом p(m_xy) пути называется число ветвей, входящих в данный путь. Связностью сети называется минимальное число независимых путей, имеющихся между каждой парой узлов. Сечение сети есть неизбыточная совокупность ветвей, которые нужно изъять из сети, чтобы нарушилась ее связность. Рангом сечения называется число входящих в него ветвей.

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

Для решения задач оптимизации структуры сети ПДС в целом необходимо численное представление структуры. Одной из таких моделей является геометрическая модель. Для упрощения геометрической модели принимаются следующие допущения:

1. Территория многополюсной сети ограничена прямоугольником.

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

3. Число типовых структур сети сокращается до пяти: радиальная, кольцевая, решетчатая, полносвязная, кратчайшесвязная.

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

Одним из частных случаев численной модели является описание структуры кратчайшесвязной сети. Каждая ветвь сети характеризуется такими параметрами как длина l_ij, емкость, надежность и многими другими. Длина ветви определяется расстоянием между узлами a_i и a_j или другими параметрами ветви (например, стоимостью).

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

Разработано большое количество различных эвристических алгоритмов, базирующихся на принципах Прима и позволяющих построить кратчайшесвязную сеть. Исходные данные для построения такой сети содержатся в матрице L=çl_ij÷ расстояний между узлами сети, где l_ij - расстояние между вершинами a_i и a_j. На первом шаге алгоритма Прима находится минимальный элемент матрицы L. Пусть таким элементом оказался элемент l_ij = l_ji. Тогда первой ветвью дерева минимальной длины будет ветвь, соединяющая вершины a_i и a_j. В строках матрицы с номерами i и j отыскивается следующий минимальный элемент. Допустим, этим элементом является элемент l_jk в строке k. Тогда второй ветвью дерева минимальной длины будет ветвь, соединяющая вершины a_j и a_k. Далее процедура повторяется для строк i, j и k. Таким образом, на каждом шаге построения дерева минимальной длины отыскивается ветвь минимальной длины, соединяющая еще не соединенные вершины. Связное дерево минимальной длины будет содержать n-1 ветвей, где n -число вершин графа или число оконечных пунктов сети.

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

Рис. 1.1. План сети

и матрица L расстояний между ними (табл.1.2).

Таблица 1.2. Матрица расстояний
		5,3	5,4	8,6	12,7	12,6	11,7	13,4	12,1	19,8
	5,3		7,0	8,0	8,9	7,3	6,4	11,7	11,8	16,7
	5,4	7,0		3,6	9,6	12,6	13,3	8,5	6,7	15,5
	8,6	8,0	3,6		6,8	11,5	13,7	4,9	3,8	12,0
	12,7	8,9	9,6	6,8		7,4	11,8	5,6	8,3	8,0
	12,6	7,3	12,6	11,5	7,4		5,7	12,5	14,4	14,2
	11,7	6,4	13,3	13,7	11,8	5,7		16,3	17,4	19,3
	13,4	11,7	8,5	4,9	5,6	12,5	16,3		3,5	7,4
	12,1	11,8	6,7	3,8	8,3	14,4	17,4	3,5		10,6
	19,8	16,7	15,5	12,0	8,0	14,2	19,3	7,4	10,6

Минимальным элементом матрицы является элемент l₈₉ = l₉₈ = 3,5. Тогда в соответствии с алгоритмом Прима выписываем восьмую и девятую строки, вычеркнув восьмой и девятый столбцы.

	13,4	11,7	8,5	4,9	5,6	12,5	16,3	7,4
	12,1	11,8	6,7	3,8	8,3	14,4	17,4	10,6

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

	12,1 (9)	11,7 (8)	6,7 (9)	3,8 (9)	5,6 (8)	12,5 (8)	16,3 (8)	7,4 (8)

Цифрой в скобках указывается, из какой строки взят тот или иной элемент. Выбираем минимальный элемент первой вспомогательной строки l₉₄ = l₄₉ = 3,8. С учетом этого выписываем первую вспомогательную строку и четвертую строку матрицы, предварительно вычеркнув из нее восьмой, девятый и четвертый столбцы.

	12,1 (9)	11,7 (8)	6,7 (9)	5,6 (8)	12,5 (8)	16,3 (8)	7,4 (8)
	8,6	8,0	3,6	6,8	11,5	13,7	12,0

Формируем вторую вспомогательную строку.

	8,6 (4)	8,0 (4)	3,6 (4)	5,6 (8)	11,5 (4)	13,7 (4)	7,4 (8)

Выбираем из нее минимальный элемент l₄₃ = l₃₄ = 3,6.

Продолжая далее аналогичным образом, получим остальные ветви кратчайшесвязной сети: l₃₁ = l₁₃ = 5,4; l₁₂ = l₂₁ = 5,3; l₈₅ = l₅₈ = 5,6; l₂₇ = l₇₂ = 6,4; l₇₆ = l₆₇ = 5,7; l₈₁₀ = l₁₀₈ = 7,4, структура которой будет выглядеть так, как показано на рис. 1.2.

 

Рис. 1.2. Структура кратчайшесвязной сети

При этом общая длина сети будет составлять 3,5+3,8+3,6+5,4+5,3+5,6+6,4+5,7+7,4=46,7 условных единиц.

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

Контрольные вопросы к лабораторной работе №1 [1, с. 8-28]

1-1. Чем продиктована необходимость создания ИС?

1-2. Без чего невозможно создание ИС?

1-3. Что является теоретической основой создания ИС?

1-4. Сколько уровней выделяется в ЭМВОС?

1-5. В чем состоит основная идея ЭМВОС?

1-6. Какими средствами реализуются функции уровней ЭМВОС?

1-7. Какими средствами реализуются функции высших уровней ЭМВОС?

1-8. Какими средствами реализуются функции сетевого и канального уровней ЭМВОС?

1-9. Какими средствами реализуются функции физического уровня ЭМВОС?

1-10. Какой уровень ЭМВОС является наиболее близким к пользователю?

1-11. Какой уровень ЭМВОС является наиболее далеким от пользователя?

1-12. Что называется каналом передачи данных?

1-13. Какие параметры соединения определяет физический уровень?

1-14. Какие основные функции реализует физический уровень?

1-15. Какой уровень называют уровнем управления звеном данных?

1-16. Какие функции реализуются средствами канального уровня?

1-17. Как называется блок данных, сформированный на канальном уровне?

1-18. Как называется аппаратно-программный комплекс, реализующий функции физического и канального уровней?

1-19. Что называется системой обработки данных?

1-20. Что входит в состав технических средств СОД?

1-21. Для чего предназначено программное обеспечение СОД?

1-22. В чем состоят функции СОД?

1-23. Что представляет собой информационная сеть?

1-24. В чем состоит эффект от объединения СОД в ИС?

1-25. Какие составляющие входят в структуру ИС?

1-26. Что называется каналом связи?

1-27. Что используется в качестве среды распространения сигнала в каналах ИС?

1-28. В чем состоит назначение оконечного оборудования данных?

1-29. Для чего предназначена аппаратура передачи данных?

1-30. Для чего предназначены центры коммутации?

1-31. Что входит в состав центров коммутации?

1-32. Как ИС подразделяются по категории абонентов?

1-33. Что представляет собой коммутируемая телефонная сеть общего пользования?

1-34. По какому принципу строятся КСДОП?

1-35. Какое устройство называется концентратором нагрузки?

1-36. Какое устройство называется шлюзом?

1-37. На основе каких принципов строятся ЦСИУ?

1-38. Из каких подсетей состоит структура ЦСИУ?

1-39. Какие новые составляющие входят в структуру интеллектуальной сети связи?

1-40. Что включает в себя надстройка интеллектуальной сети связи?

1-41. Как ИС подразделяются по скорости передачи сообщений?

1-42. На какие классы ИС подразделяются по размеру сети?

1-43. Чем отличаются глобальные и локальные ИС?

1-44. На какие классы ИС подразделяются по типу структуры?

1-45. Что является достоинством сетей с иерархической структурой?

1-46. От чего зависит выбор той или иной структуры сети?

1-47. Что называется топологией сети?

1-48. Чем отличаются сети со статической и динамической топологией?

1-49. Перечислите параметры, используемые при описании топологии сети.

1-50. Чему равен размер сети?

1-51. Как определяется число связей сети?

1-52. Что называется диаметром сети?

1-53. Что называется порядком узла?

1-54. К чему приводит увеличение порядка узла?

1-55. Что характеризует пропускная способность сети?

1-56. Что называется задержкой сети?

1-57. Что называется связностью сети?

1-58. Что характеризует связность сети?

1-59. Что называется срезом сети?

1-60. Что называется бисекцией сети?

1-61. Чем характеризуется ширина бисекции сети?

1-62. На какие классы подразделяются топологии сети по размерности?

1-63. Чем характеризуется линейная топология?

1-64. Что представляет собой кольцевая топология?

1-65. Что представляет собой двунаправленное кольцо?

1-66. Что представляет собой хордальное кольцо?

1-67. Чем характеризуется звездообразная топология?

1-68. Чем характеризуется древовидная топология?

1-69. Чем характеризуется топология, называемая толстым деревом?

1-70. Что представляет собой решетчатая топология?

1-71. Что представляет собой цилиндрическая топология?

1-72. Что представляет собой тороидальная топология?

1-73. Что представляет собой полносвязная топология?

1-74. Опишите алгоритм получения сети с гипркубической топологией.

1-75. За счет чего обеспечивается изменение топологии сети в сетях с динамической топологией?

1-76. Чем характеризуются неблокирующие сети?

1-77. Чем характеризуются блокирующие сети?

1-78. К какому типу топологий относится шинная топология?

1-79. Чему равны порядок узла, диаметр и ширина бисекции сети с шинной топологией?

1-80. Что называется кластером?

Дата добавления: 2014-11-29