Стислий конспект лекцій з дисципліни "Телекомунікаційні та інформаційні мережі" (тім) (програма бакалаврського мінімуму) Лектор доц. В.І. Тіхонов
| Вид материала | Конспект |
Содержание6.2. Построение маршрутной матрицы 6.3. Задача построения сети абонентского доступа с минимальными 6.4. Определение множества путей заданной транзитности. |
- Конспект лекцій Суми Видавництво Сумду 2010, 2423.29kb.
- Конспект лекцій з дисципліни "Інформаційні системи та технології у фінансових установах", 1112.81kb.
- Назва модуля: Інформаційні системи в менеджменті Код модуля, 40.82kb.
- Робоча навчальна програма з дисципліни «Політичні комунікації» Укладач: к філол н.,, 310.09kb.
- Конспект лекцій з дисципліни „Радіоекологія для студентів спеціальності 040106 „Екологія,, 1393.76kb.
- Виконавці, 499.61kb.
- Конспект лекцій по дисципліні Інформаційні моделі "великих" систем, 1986.92kb.
- Дисципліна «Финанси» Довідник з дисципліни Для спеціальностей 0104, 0105, 0106, 0100, 539.85kb.
- Робоча навчальна програма дисциплiни " планування та проектування інформаційних систем", 115.77kb.
- Конспект лекцій Удвох частинах Частина 1 Суми, 2323.63kb.
6. Задачи анализа и синтеза сетей
6.1. Построение матрицы кратчайших расстояний между узлами сети,
заданной в табличной форме
Рассмотрим задачу построения матрицы кратчайших расстояний между узлами какого-нибудь фрагмента сети (например, магистральной сети). Пусть задана топология сети в виде таблицы, где каждый столбец описывает одну дугу графа (ее начальную и конечную вершины), а также метрику дуги (абстрактный вес). В этой задаче граф предполагается неориентированным (т.е. дуги и их веса – одинаковы в обоих направлениях).
-
Н
Таблица 1
ачало
1
1
1
2
2
3
4
4
Конец
3
4
6
4
5
4
5
6
Метрика
15
30
25
16
12
50
20
55
Преобразуем табличную (дискретную) форму
Сети в графическую (рис. 1).
Для неориентированного графа матрица кратчайших расстояний между вершинами
является симметричной относительно главной диагонали. Поэтому можно рассчитывать только
одну ее половину; вторая заполняется
симметрично.
Для того, чтобы рассчитать матрицу
кратчайших расстояний, можно воспользоваться
Алгоритмом Дейкстры. В результате однократного
выполнения этого алгоритма вычисляются
кратчайшие расстояния от одной исходной точки до
всех остальных (например, пять расстояний от
| Матрица кратчайших расстояний | ||||||
| Вершины | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | х | 46 | 15 | 30 | 50 | 25 |
| 2 | | х | 61 | 16 | 12 | 71 |
| 3 | | | х | 50 | 70 | 40 |
| 4 | | | | х | 20 | 55 |
| 5 | | | | | х | 75 |
| 6 | | | | | | х |
заполнить только первую строку нашей матрицы. Далее нужно снова применить этот алгоритм для нахождения 4-х кратчайших расстояний от точки 2
до точек 3-6 (мы заполним вторую строку матрицы). Всего, для нашего граф, этот алгоритм нужно применить 5 раз, причем, в последний раз нужно будет определить всего одно кратчайшее расстояние – от точки 5 до точки 6.
Таблица 2
| Реализация алгоритма Дейкстры | |||
| Номер шага | Выбранные Вершины и расстояния | Список альтернативных путей | Комментарии |
| 0 1 2 3 4 5 | 1(0) 3(15) 6(25) 4(30) 2/4(46) 5/4(50) | 3(15), 4(30), 6(25) 4(30), 6(25), 4/3(15+50) 4(30), 4/6(25+55) 2/4(30+16), 5/4(30+20) 5/4(30+20) | Исходная точка цикла 1 Выбираем миним. Вычеркиваем худшую альтернативу |
| 0 1 2 3 4 | 1(46), 2(0) 5(12) 4(16) 3/1(61) 6/4(71) | 4(16), 5(12), 3/1(46+15), 4/1(46+30), 6/1(46+25) 4(16), 3/1(61), 6/1(71), 4/5(12+20) 3/1(61), 6/1(71), 3/4(16+50), 6/4(16+55) 6/4(71) | Исходная точка цикла 2 Вычеркиваем худшую альтернативу Путь к 3 выбираем с меньшим транзитом |
| 0 1 2 3 | 1(15), 2(61), 3(0) 4(50) 6/1(40) 5/4(70) | 4(50), 6/1(15+25), 4/2(61+16), 5/2(61+12) 5/2(73), 6/1(40), 5/4(50+20), 6/4(50+55) 5/4(50+20), 6/4(50+55) | Исходная точка цикла 3 |
| 0 1 2 | 1(30), 2(61), 3(50), 4(0) 5(20) 6(55) | 5(20), 6(55), 6/1(30+25), 5/2(61+12) 6(55) | Исходная точка цикла 4 Вычеркиваем худшую альтернативу |
| 0 1 | 1(85), 2(12), 3(70), 4(20) 6/4(75) | 6/1(85+25), 6/4(20+55) | Исходная точка цикла 5 |
Таблица 2
иже в таблице 3 приведен расчет кратчайших расстояний по методу Дейкстры. Запись вида 3(15) означает что расстояние некоторой исходной точки ( в данном случае – от точки 1) до точки 3 равно 15, причем, эти точки имеют непосредственное соединение (без транзитного узла). Запись вида 4/3(15+50) означает, что расстояние от исходной точки до точки 4 через транзитный узел 3 равно расстоянию от исходной точки до транзитного узла (15) плюс расстояние отданного транзитного узла 3 до узла 4 (т.е.+50). Результаты этого рассчета сведены в таблицу 2.
^ 6.2. Построение маршрутной матрицы
Пусть задана топология сети в виде таблицы, где каждый столбец описывает одну дугу графа (ее начальную и конечную вершины), а также метрику дуги (абстрактный вес). В этой задаче граф предполагается неориентированным (т.е. дуги и их веса – одинаковы в обоих направлениях).
-
Н
Таблица 4
ачало
1
1
1
2
2
3
4
4
Конец
3
4
6
4
5
4
5
6
Метрика
15
30
25
16
12
50
20
55
Преобразуем табличную (дискретную) форму
Сети в графическую (рис. 1).
Для того, чтобы построить маршрутную матрицу, нужно сперва определить кратчайшие расстояния
между вершинами, и что очень важно, - маршруты, которые обеспечивают эти кратчайшие расстояния.
Для этого воспользуемся алгоритмом Дейкстры.
Детальнее этот алгоритма описан в предыдущей задаче (п. 6.1). Поскольку исходные данные для этой задачи выбраны такие же, как и в предыдущей, воспользуемся готовой таблицей 3 реализации алгоритма
Дейкстры (предыдущая страница).
Рассмотрим вершину 1. Она имеет кратчайшие
расстояния до вершин 3, 6, 4 без промежуточных
транзитных пунктов. А вот кратчайший путь к точке 2 проходит через транзитный пункт 4. Аналогично, кратчайший путь из точки 1 к точке 5 тоже проходит через транзитную точку 4.
таким образом, вектор маршрутизации для точки 1 будет представлять собой первую строку матрицы маршрутизации в виде:
| Матрица маршрутизации | ||||||
| Вершины | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | х | 4 | | | 4 | |
| 2 | 4 | х | 1 | | | 4 |
| 3 | | 1 | х | | 4 | 1 |
| 4 | | | | х | | |
| 5 | 4 | | 4 | | х | 4 |
| 6 | | 4 | 1 | | 4 | х |
Далее, вершина 2 имеет внетранзитные кратчайшие пути в точкам 5 и 4; кратчайший путь от точки 2 к точке 3 пролегает через вершину 1, а к вершине 6 – через точку 4. Вершина 3 имеет бестранзитный кратчайший путь только к узлу 4; маршруты к узлам 6 и 5 пролегают через транзиты 1 и 4. Вершина 4 имеет нетранзитный кратчайший путь к 5 и 6, а также ко всем остальным вершинам, поэтому ее вектор маршрутизации – чистый (бестранзитный). Вершина 5 имеет кратчайший путь к 6
через точку 4;
В целом, если в матрице кратчайших путей встречается не более одной транзитной вершины, то матрица маршрутизации будет симметрична относительно главной диагонали, т.е. каждая строка совпадает со столбцом такого же номера. Если же, например, кратчайшее расстояние между вершинами 1 и 2 проходило через две транзитные вершины (скажем, через 4 и 5), то тогда в ячейке на пересечении первой строки и второго столбца была бы маршрутная запись 4, а в симметричной относительно диагонали ячейке (на пересечении второй строки и первого столбца) была бы запись 5); это значит, что маршрут от 1 к 2 изображается в виде: 1-4-5-2, а маршрут от 2 к 1 – симметрично: 2-5-4-1. Иными словами, по отношению к вершине 1 первой транзитной вершиной на кратчайшем пути будет 4, а по отношению к вершине 2 – первой будет пункт 5.
Итак, задача построения маршрутной матрицы сводится к решению следующих частных задач: а) преобразование топологии к графическому виду, т.е. к графу; б) решение задачи о нахождении кратчайших расстояний между всеми точками графа (алгоритм Дейкстры); в) из протокола алгоритма Дейкстры определяются кратчайшие маршруты между всеми точками; г) заполняется матрица маршрутизации.
^ 6.3. Задача построения сети абонентского доступа с минимальными
затратами на линейно-кабельные сооружения и определение места
расположения опорного узла коммутации (обеспечивающее
минимизацию общей длины абонентских линий)…………………………….
Решение этой задачи содержит два этапа:
1) Определение т.н. минимального дерева покрытия (с помощью алгоритма Прима), т.е.такой топологии соединения узлов сети, при котором достигается минимизация общей длины линейно-кабельных сооружений (например, траншей под укладку труб кабельной канализации).
2) Определение местоположения опорного узла связи, которое минимизирует общую длину кабеля, прокладываемого в определенные ранее трубы канализации.
Пусть задана дискретная топология сети в виде таблицы:
-
Начало
1
1
1
2
2
3
4
4
Конец
3
4
6
4
5
4
5
6
Метрика (км)
15
30
25
16
12
50
20
55
Пусть стоимость 1 км коммуникаций равна 1000 у.е.
Преобразуем дискретную топологию сети в графическую форму :
- Найдем дерево минимального покрытия
графа. Начнем с любой вершины, например, с первой. Из всех возможных шагов от нее выберем самый короткий - к вершине 3 (и покрасим
вершины 1 и 3 и соединяющее их общее ребро).
Далее рассмотрим все возможные шаги из закрашенных точек 1 и 3; выберем среди них кратчайший и снова покрасим соответствующее
ребро. И так далее. Когда все вершины окажутся закрашенными, просуммируем все закрашенные участки линейно-кабельных сооружений (ЛКС):
15+25+12+20+30 = 102 (км). Отсюда общая
стоимость ЛКС равна 102 км х 1000 у.е./км =102 тыс.у.е.
- Составим матрицу расстояний от каждой вершины до всех остальных и просчитаем общую длину соединительных
линий от каждой вершины до остальных:
| Матрица расстояний | |||||||
| | 1 | 2 | 3 | 4 | 5 | 6 | Сумма |
| 1 | Х | 62 | 15 | 30 | 50 | 25 | 182 |
| 2 | 62 | Х | 77 | 32 | 12 | 87 | 270 |
| 3 | 15 | 77 | Х | 45 | 65 | 40 | 242 |
| 4 | 30 | 32 | 45 | Х | 20 | 55 | 182 |
| 5 | 50 | 12 | 65 | 20 | Х | 75 | 222 |
| 6 | 25 | 87 | 40 | 55 | 75 | Х | 282 |
главной диагонали, поэтому можно вычислять ее половину, а вторую – заполнять симметрично.
Среди всех узлов выберем тот (или те), которые минимизируют общую длину кабеля. Та4ими узлами являются два –
первый и четвертый. Они оба дают минимальную величину – 182. В этих узлах
лучше всего расположить опорный узел связи.
^ 6.4. Определение множества путей заданной транзитности.