ПЕРЕДАЧА ДИСКРЕТНОЙ ИНФОРМАЦИИ
Содержание
ЗАДАНИЕ НА КУРСОВОЙ ПРОЕКТ ПО ДИСЦИПЛИНЕ «ПЕРЕДАЧА ДИСКРЕТНОЙ ИНФОРМАЦИИ». 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. Схема расположения узлов сети:
А | В | С | D | Е | F | G | Н | L | J | К | L | |
А | ||||||||||||
В | ||||||||||||
С | ||||||||||||
D | ||||||||||||
Е | ||||||||||||
F | ||||||||||||
G | ||||||||||||
Н | ||||||||||||
L | ||||||||||||
J | ||||||||||||
К | ||||||||||||
L |
2. Количество пользователей на каждом из узлов:
А | В | С | D | Е | F | G | Н | L | J | К | L | |
4. Среднее месячное потребление трафика одним пользователем от серверов каждого узла, МБ:
А | В | С | D | Е | F | G | Н | L | J | К | L |
Средняя месячная величина Р2Р-трафика на одного пользователя, МБ: 20000
Суточный и месячный коэффициенты концентрации нагрузки: 0.2, 0.06
Построение кратчайшесвязанной сети
Исходными данными к расчету является матрица расстояний между n узлами сети. Для выполнения задачи сеть представляется в виде неориентированного графа, в котором вершины соответствуют узлам сети, а вес каждого потенциального ребра равен расстоянию между соответствующими узлами. Для построения графа минимального веса применяется алгоритм Прима.
Искомый граф строится постепенно, добавлением в него рёбер по одному. Изначально
граф полагается состоящим из произвольно выбранной единственной вершины. Затем
выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в
формируемый граф. Далее ищется и добавляется к графу ребро минимального веса, имеющее
один конец в одной из уже включенных в граф вершин, а другой конец — наоборот, в одной
из вершин, в граф еще не включенных. Этот шаг повторяется до тех пор, пока еще остаются
не включенные в граф вершины. Если на каком-либо шаге обнаруживается, что возможных
рёбер с одинаковым минимальным весом несколько, выбирается любое из них.
В аналитическом виде алгоритм Прима может быть выполнен в следующей форме:
1. Составляется пустая таблица, имеющая n-1 столбцов и 2n-3 строк (не включая заголовок), где n – число узлов в сети.
2. Произвольно выбирается начальная вершина. Все остальные вершины записываются в заголовок таблицы по столбцам.
3. В ячейки первой строки записывается вес всех потенциальных ребер, соединяющих начальную вершину с вершинами, соответствующими каждому столбцу.
4. По последней заполненной строке выбирается минимальное ребро и присоединяется к графу. В дальнейшем столбец, в котором находилось это ребро, выбывает из анализа.
5. В ячейки следующей строки записывается вес всех потенциальных ребер, соединяющих вершину, соответствующую выбывшему на шаге 4 столбцу с вершинами, соответствующими остальным столбцам.
6. В следующую строку в каждую ячейку записывается минимум из весов двух ребер, находящихся в том же столбце в предыдущей и пред-предыдущей строках.
7. Если в последней заполненной строке осталось одно ребро, оно присоединяется к графу и работа заканчивается. Если ребер больше, возвращаемся к шагу 4. В качестве примера рассмотрим задачу по построению графа из 6 вершин со следующей матрицей расстояний (веса потенциальных ребер):
Таблица 1 - Рабочая таблица алгоритма Прима
В | С | D | Е | F | G | Н | I | J | К | L | |
41 | Вес ребер, соединяющих начальную вершину А с оставшимися (шаг 3). Выбрано ребро A-E, столбец E оставшимися (шаг 3). далее не используется (шаг 4). | ||||||||||
Вес ребер, соединяющих вершину E с оставшимися (шаг 5). | |||||||||||
68 | Минимум по двум предыдущим строкам (шаг 6). Выбрано ребро A-D | ||||||||||
Вес ребер, соединяющих вершину D с оставшимися | |||||||||||
79 | Минимум по двум предыдущим строкам. Выбрано ребро А-B | ||||||||||
Вес ребер, соединяющих вершину B с оставшимися | |||||||||||
35 | Минимум по двум предыдущим строкам. Выбрано ребро B-I | ||||||||||
Вес ребер, соединяющих вершину I с оставшимися | |||||||||||
60 | Минимум по двум предыдущим строкам. Выбрано ребро B-C | ||||||||||
Вес ребер, соединяющих вершину C с оставшимися | |||||||||||
67 | Минимум по двум предыдущим строкам. Выбрано ребро C-J | ||||||||||
Вес ребер, соединяющих вершину L с оставшимися | |||||||||||
40 | Минимум по двум предыдущим строкам. Выбрано ребро J-L | ||||||||||
Вес ребер, соединяющих вершину J с оставшимися | |||||||||||
22 | Минимум по двум предыдущим строкам. Выбрано ребро J-K | ||||||||||
Вес ребер, соединяющих вершину K с оставшимися | |||||||||||
85 | Минимум по двум предыдущим строкам. Выбрано ребро F-K | ||||||||||
Вес ребер, соединяющих вершину F с оставшимися | |||||||||||
42 | Минимум по двум предыдущим строкам. Выбрано ребро F-H | ||||||||||
Вес ребер, соединяющих вершину H с оставшимися | |||||||||||
97 | Минимум по двум предыдущим строкам. Выбрано ребро G-H |
Таким образом, граф, представляющий кратчайшесвязанную сеть, будет состоять из ребер A-E, A-D, A-B, B-I, B-C, C-J, J-K, J-L, C-F, F-H, G-H