Построение кратчайшесвязанной сети

ПЕРЕДАЧА ДИСКРЕТНОЙ ИНФОРМАЦИИ

Содержание

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ ПО ДИСЦИПЛИНЕ «ПЕРЕДАЧА ДИСКРЕТНОЙ ИНФОРМАЦИИ». 3

1 Построение кратчайшесвязанной сети. 3

2 Расчет требуемой пропускной способности каналов передачи. 3

2.1 Расчет трафика от серверов. 3

2.2 Расчет P2P-трафика. 3

2.3 Расчет суммарного трафика. 3

2.4 Расчет требуемой пропускной способности. 3

3 Выбор систем передачи и составление схемы связи. 3

ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ ПО ДИСЦИПЛИНЕ «ПЕРЕДАЧА ДИСКРЕТНОЙ ИНФОРМАЦИИ»

В курсовом проекте прорабатываются следующие вопросы:

1. Построение схемы кратчайшесвязанной сети с заданным количеством узлов.

2. Расчет трафика, передаваемого между узлами в ЧНН.

3. Выбор систем передачи на участках.

4. Составление схемы связи.

Исходные данные:

1. Схема расположения узлов сети:

2. Количество пользователей на каждом из узлов:

4. Среднее месячное потребление трафика одним пользователем от серверов каждого узла, МБ:

Средняя месячная величина Р2Р-трафика на одного пользователя, МБ: 20000

Суточный и месячный коэффициенты концентрации нагрузки: 0.2, 0.06

Построение кратчайшесвязанной сети

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

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

граф полагается состоящим из произвольно выбранной единственной вершины. Затем

выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в

формируемый граф. Далее ищется и добавляется к графу ребро минимального веса, имеющее

один конец в одной из уже включенных в граф вершин, а другой конец — наоборот, в одной

из вершин, в граф еще не включенных. Этот шаг повторяется до тех пор, пока еще остаются

не включенные в граф вершины. Если на каком-либо шаге обнаруживается, что возможных

рёбер с одинаковым минимальным весом несколько, выбирается любое из них.

В аналитическом виде алгоритм Прима может быть выполнен в следующей форме:

1. Составляется пустая таблица, имеющая n-1 столбцов и 2n-3 строк (не включая заголовок), где n – число узлов в сети.

2. Произвольно выбирается начальная вершина. Все остальные вершины записываются в заголовок таблицы по столбцам.

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

4. По последней заполненной строке выбирается минимальное ребро и присоединяется к графу. В дальнейшем столбец, в котором находилось это ребро, выбывает из анализа.

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

6. В следующую строку в каждую ячейку записывается минимум из весов двух ребер, находящихся в том же столбце в предыдущей и пред-предыдущей строках.

7. Если в последней заполненной строке осталось одно ребро, оно присоединяется к графу и работа заканчивается. Если ребер больше, возвращаемся к шагу 4. В качестве примера рассмотрим задачу по построению графа из 6 вершин со следующей матрицей расстояний (веса потенциальных ребер):

Таблица 1 - Рабочая таблица алгоритма Прима

Таким образом, граф, представляющий кратчайшесвязанную сеть, будет состоять из ребер A-E, A-D, A-B, B-I, B-C, C-J, J-K, J-L, C-F, F-H, G-H