Размещено на http://www.allbest.ru/

Оглавление

• Техническое задание
• 1. Теоретическая часть
• 1.1 Разные подходы к выполнению коммутации
• 1.2 Коммутация каналов
• 1.3 Коммутация пакетов
• 1.4 Коммутация сообщений
• 2. Алгоритм Флойда для выбора кратчайшего пути между всеми узлами сети
• 2.1 Алгоритм Флойда
• 2.2 Описание интерфейса и работы программы
• 3.Экспериментальная часть
• 3.1 Анализ технического задания на проектирование РИВС
• 3.2 Проектирование региональных вертикальных сетей
• 3.3 Проектирование межрегиональной горизонтальной сети
• Заключение
• Литература
• Приложение
• Техническое задание

1. Тема проектирования : Распределенная вычислительная сеть

2. Уровень проектирования : 5

3. Теоретический вопрос для проработки : Метод коммутации каналов и сообщений. Технологии на основе этих методов.

4. Задание на разработку программных элементов : Алгоритм Флойда для выбора кратчайшего пути между всеми узлами сети

Разработать программу для указанного выше алгоритма.

5. Язык программирования : По выбору студента

6. Требования к программе : Дружественный интерфейс.

Сервисные функции по вводу, отображению и выводу данных.

7. Детализация этапа проектирования ВСПД : Все вертикальные регионы

8. Детализация этапа проектирования ГСПД : Анализ всех возможных топологий

Исходные данные для проектирования РИВС с использованием программно-инструментального комплекса NET-PRO.

10. Тип проектируемой топологии : Оптимальная

11. Критерий оптимизации : Общая стоимость сети

Ограничения на проектирование

12. 12 секунд(ы) : - Максимальное время задержки

13. 2 секунд(ы) : - Среднее время задержки

14. Исходные данные для зоны проектирования РИВС: : Должны быть сгенерированы с помощью ПИК NET-PRO.

Произвести синтез СПД с вертикальными связями для 8 регионов:

Регион N 1 содержит 11 городов.

Название города долгота широта трафик

Вышелей 44.15 53.18 26

Каменка .12 53.15 170

Пенза .80 53.23 888

Городищи .33 53.23 26

Сосновоборск .43 53.07 17

Золотаревка .80 53.02 31

Кондоль .12 52.78 11

Сурск .87 52.78 82

Неверкино .67 52.67 47

Колышлей .57 52.38 49

Сердобск .37 52.35 188

Регион N 2 содержит 15 городов.

Название города долгота широта трафик

Петропавловск-Камча 8.82 53.03 622

Слаутное .08 63.03 41

Каменское .82 62.50 39

Тиличики .27 60.35 42

Пахачи .37 60.35 41

Ильпырский .23 60.00 48

Оссора .08 59.28 46

Палана .00 59.10 49

Большерецк .47 52.50 38

Тигиль .63 57.85 48

Усть-Хайрюзово .90 57.85 35

Усть-Камчатск .07 56.07 88

Атласово 159.42 55.72 44

Мильково .82 54.82 13

Кировский 156.18 54.28 31

Регион N 3 содержит 17 городов.

Название города долгота широта трафик

Верх.Золотица .48 65.67 48

Карьеполье .48 65.50 31

Азаполье .25 65.20 13

Кулой .37 64.95 32

Кушара .00 64.92 31

Вожгора .00 64.67 29

Пинега .87 64.57 39

Архангельск .75 64.28 526

Кянда .48 64.50 42

Новодвинск .25 64.37 262

Олема .87 63.95 34

Холмогоры .25 64.15 46

Верх.Паленьга .75 64.08 34

Карпогоры .00 63.08 47

Щилега .37 63.53 36

Малошуйка .25 63.15 10

Обозерский .00 62.08 26

Регион N 4 содержит 18 городов.

Название города долгота широта трафик

Горький .00 56.45 856

Сява .28 58.02 41

Вахтан .62 57.93 33

Ветлуга .72 57.88 33

Пижма .10 57.88 16

Шахунья .62 57.67 73

Урень .80 57.48 94

Варнавино .15 57.40 29

Тонкино .45 57.30 25

Дзержинск .67 56.22 735

Богородск .67 56.05 307

Лысково .15 56.50 109

Сергач .55 55.55 139

Кулибаки .62 55.42 296

Вознесенское .77 55.88 45

Первомайск .92 54.88 67

Арзамас .92 55.37 281

Сеченово 46.03 55.23 46

Регион N 5 содержит 19 городов.

Название города долгота широта трафик

Сурское 46.83 54.43 38

Языково .48 54.27 31

Карсун .12 54.17 23

Майна .70 54.03 34

Плотовка .83 53.90 14

Инза .47 53.82 107

Барыш .27 53.60 67

Кузоватово .77 53.47 34

Николаевка .27 52.93 25

Новоспасское .85 52.93 40

Стар.Кулатка .70 52.70 23

Павловка .80 52.67 17

Цельна .22 54.53 36

Ульяновск .35 54.27 509

Стар.Майна .93 54.57 23

Чердаклы 48.87 54.30 17

Новочеремшанск 50.10 54.30 10

Нов.Малыкла .88 54.17 41

Сенгилей .87 53.90 20

Регион N 6 содержит 18 городов.

Название города долгота широта трафик

Донецк .88 48.00 793

Красный Лиман .80 48.92 321

Славянск .63 48.75 479

Краматорск .55 48.62 650

Константиновка .72 48.48 497

Артемовск .03 48.53 240

Доброполье .07 48.43 169

Горловка .12 48.27 861

Мариуполь .55 47.08 576

Красноармейск .15 48.22 215

Енакиево .85 48.22 352

Макеевка .03 48.10 817

Иловайск .28 47.90 84

Амвросиевка .60 47.73 64

Комсомольское .20 47.62 58

Докучаевск .72 47.70 59

Волноваха .55 47.57 78

Новоазовск .12 47.13 100

Регион N 7 содержит 20 городов.

Название города долгота широта трафик

Соликамск .68 66.30 334

Усолье .78 66.30 25

Березники .30 66.25 581

Яйва .48 66.10 51

Александровский 56.10 66.72 136

Пожва .68 65.92 39

Углеуральский .40 64.93 71

Перьм .00 64.83 666

Кормовищи .00 64.73 10

Серга .18 64.68 24

Юг .48 64.20 48

Сук-Сун .10 63.93 46

Медянка .10 63.47 41

Чернушка .30 63.47 115

Октябрьский .18 63.68 30

Губаха .48 65.83 180

Усьва .60 65.57 49

Теплая Гора .00 65.47 15

Сарань .78 65.52 31

Ремячинск .90 65.47 79

Регион N 8 содержит 19 городов.

Название города долгота широта трафик

Краснодар .97 45.03 531

Красное .63 46.70 32

Ейск .30 46.70 315

Староминская .03 46.48 87

Кущевская .70 46.48 126

Ясинская .37 46.38 43

Ленинградская .40 46.32 137

Приморск-Ахтарск 38.22 46.05 120

Каневская .97 46.05 127

Павловская .70 46.17 72

Белая Глина .73 46.05 119

Новопокровская 40.60 45.95 120

Тихорецк .07 45.83 289

Тимошевск .97 45.52 306

Кореновск .40 45.47 123

Славянск-на-Кубани 38.15 45.25 315

Кропоткин .52 45.47 313

Тамань .82 45.18 14

Новотитаровская .97 45.18 62

Общее количество городов: 137

Синтезировать СПД c горизонтальными связями для городов, полученных в результате выполнения предыдущих этапов.

Топология проектируемой сети: ОПТИМАЛЬНАЯ

Критерий синтеза СПД для минимизации: общая стоимость сети

Зависимость стоимости каналов от длины и пропускной способности

1. Теоретическая часть

1.1 Разные подходы к выполнению коммутации

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

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

· коммутация каналов (circuit switching);

· коммутация пакетов (packet switching).

Внешне обе эти схемы соответствуют приведенной на рис. 1.1 структуре сети, однако возможности и свойства их различны.

Рис. 1.1. Общая структура сети с коммутацией абонентов

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

1.2 Коммутация каналов

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

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

Например, если сеть, изображенная на рис. 1.1, работает по технологии коммутации каналов, то узел 1, чтобы передать данные узлу 7, сначала должен передать специальный запрос на установление соединения коммутатору A, указав адрес назначения 7. Коммутатор А должен выбрать маршрут образования составного канала, а затем передать запрос следующему коммутатору, в данном случае E. Затем коммутатор E передает запрос коммутатору F, а тот, в свою очередь, передает запрос узлу 7. Если узел 7 принимает запрос на установление соединения, он направляет по уже установленному каналу ответ исходному узлу, после чего составной канал считается скоммутированным, и узлы 1 и 7 могут обмениваться по нему данными.

Рис. 1.2. Установление составного канала

Техника коммутации каналов имеет свои достоинства и недостатки.

Достоинства коммутации каналов

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

2. Низкий и постоянный уровень задержки передачи данных через сеть. Это позволяет качественно передавать данные, чувствительные к задержкам (называемые также трафиком реального времени) -- голос, видео, различную технологическую информацию.

Недостатки коммутации каналов

1. Отказ сети в обслуживании запроса на установление соединения. Такая ситуация может сложиться из-за того, что на некотором участке сети соединение нужно установить вдоль канала, через который уже проходит максимально возможное количество информационных потоков. Отказ может случиться и на конечном участке составного канала -- например, если абонент способен поддерживать только одно соединение, что характерно для многих телефонных сетей. При поступлении второго вызова к уже разговаривающему абоненту сеть передает вызывающему абоненту короткие гудки -- сигнал "занято".

2. Нерациональное использование пропускной способности физических каналов. Та часть пропускной способности, которая отводится составному каналу после установления соединения, предоставляется ему на все время, т.е. до тех пор, пока соединение не будет разорвано. Однако абонентам не всегда нужна пропускная способность канала во время соединения, например в телефонном разговоре могут быть паузы, еще более неравномерным во времени является взаимодействие компьютеров. Невозможность динамического перераспределения пропускной способности представляет собой принципиальное ограничение сети с коммутацией каналов, так как единицей коммутации здесь является информационный поток в целом.

3. Обязательная задержка перед передачей данных из-за фазы установления соединения.

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

1.3 Коммутация пакетов

коммутация канал алгоритм сеть

Эта техника коммутации была специально разработана для эффективной передачи компьютерного трафика. Первые шаги на пути создания компьютерных сетей на основе техники коммутации каналов показали, что этот вид коммутации не позволяет достичь высокой общей пропускной способности сети. Типичные сетевые приложения генерируют трафик очень неравномерно, с высоким уровнем пульсации скорости передачи данных. Например, при обращении к удаленному файловому серверу пользователь сначала просматривает содержимое каталога этого сервера, что порождает передачу небольшого объема данных. Затем он открывает требуемый файл в текстовом редакторе, и эта операция может создать достаточно интенсивный обмен данными, особенно если файл содержит объемные графические включения. После отображения нескольких страниц файла пользователь некоторое время работает с ними локально, что вообще не требует передачи данных по сети, а затем возвращает модифицированные копии страниц на сервер -- и это снова порождает интенсивную передачу данных по сети.

Коэффициент пульсации трафика отдельного пользователя сети, равный отношению средней интенсивности обмена данными к максимально возможной, может достигать 1:50 или даже 1:100. Если для описанной сессии организовать коммутацию канала между компьютером пользователя и сервером, то большую часть времени канал будет простаивать. В то же время коммутационные возможности сети будут закреплены за данной парой абонентов и будут недоступны другим пользователям сети.

При коммутации пакетов все передаваемые пользователем сообщения разбиваются в исходном узле на сравнительно небольшие части, называемые пакетами. Напомним, что сообщением называется логически завершенная порция данных -- запрос на передачу файла, ответ на этот запрос, содержащий весь файл и т.д. Сообщения могут иметь произвольную длину, от нескольких байт до многих мегабайт. Напротив, пакеты обычно тоже могут иметь переменную длину, но в узких пределах, например от 46 до 1500 байт. Каждый пакет снабжается заголовком, в котором указывается адресная информация, необходимая для доставки пакета на узел назначения, а также номер пакета, который будет использоваться узлом назначения для сборки сообщения (рис. 1.3). Пакеты транспортируются по сети как независимые информационные блоки. Коммутаторы сети принимают пакеты от конечных узлов и на основании адресной информации передают их друг другу, а в конечном итоге -- узлу назначения.

Рис. 1.3. Разбиение сообщения на пакеты

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

Действительно, для пары абонентов наиболее эффективным было бы предоставление им в единоличное пользование скоммутированного канала связи, как это делается в сетях с коммутацией каналов. В таком случае время взаимодействия этой пары абонентов было бы минимальным, так как данные без задержек передавались бы от одного абонента другому. Простои канала во время пауз передачи абонентов не интересуют, для них важно быстрее решить свою задачу. Сеть с коммутацией пакетов замедляет процесс взаимодействия конкретной пары абонентов, так как их пакеты могут ожидать в коммутаторах, пока по магистральным связям передаются другие пакеты, пришедшие в коммутатор ранее. Тем не менее, общий объем передаваемых сетью компьютерных данных в единицу времени при технике коммутации пакетов будет выше, чем при технике коммутации каналов. Это происходит потому, что пульсации отдельных абонентов в соответствии с законом больших чисел распределяются во времени так, что их пики не совпадают. Поэтому коммутаторы постоянно и достаточно равномерно загружены работой, если число обслуживаемых ими абонентов действительно велико. На рис. 1.4 показано, что трафик, поступающий от конечных узлов на коммутаторы, распределен во времени очень неравномерно. Однако коммутаторы более высокого уровня иерархии, которые обслуживают соединения между коммутаторами нижнего уровня, загружены более равномерно, и поток пакетов в магистральных каналах, соединяющих коммутаторы верхнего уровня, имеет почти максимальный коэффициент использования. Буферизация сглаживает пульсации, поэтому коэффициент пульсации на магистральных каналах гораздо ниже, чем на каналах абонентского доступа -- он может быть равным 1:10 или даже 1:2.

коммутация канал алгоритм сеть

Рис. 1.4. Сглаживание пульсаций трафика в сети с коммутацией пакетов

Более высокая эффективность сетей с коммутацией пакетов по сравнению с сетями с коммутацией каналов (при равной пропускной способности каналов связи) была доказана в 60-е годы как экспериментально, так и с помощью имитационного моделирования. Здесь уместна аналогия с мультипрограммными операционными системами. Каждая отдельная программа в такой системе выполняется дольше, чем в однопрограммной системе, когда программе выделяется все процессорное время, пока ее выполнение не завершится. Однако общее число программ, выполняемых за единицу времени, в мультипрограммной системе больше, чем в однопрограммной.

Сеть с коммутацией пакетов замедляет процесс взаимодействия конкретной пары абонентов, но повышает пропускную способность сети в целом.

Задержки в источнике передачи:

· время на передачу заголовков;

· задержки, вызванные интервалами между передачей каждого следующего пакета.

Задержки в каждом коммутаторе:

· время буферизации пакета;

· время коммутации, которое складывается из:

o времени ожидания пакета в очереди (переменная величина);

o времени перемещения пакета в выходной порт.

Достоинства коммутации пакетов

1. Высокая общая пропускная способность сети при передаче пульсирующего трафика.

2. Возможность динамически перераспределять пропускную способность физических каналов связи между абонентами в соответствии с реальными потребностями их трафика.

Недостатки коммутации пакетов

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

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

3. Возможные потери данных из-за переполнения буферов.

В настоящее время активно разрабатываются и внедряются методы, позволяющие преодолеть указанные недостатки, которые особенно остро проявляются для чувствительного к задержкам трафика, требующего при этом постоянной скорости передачи. Такие методы называются методами обеспечения качества обслуживания (Quality of Service, QoS).

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

1.4 Коммутация сообщений

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

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

По такой схеме обычно передаются сообщения, не требующие немедленного ответа, чаще всего сообщения электронной почты. Режим передачи с промежуточным хранением на диске называется режимом "хранения-и-передачи" (store-and-forward). Режим коммутации сообщений разгружает сеть для передачи трафика, требующего быстрого ответа, например трафика службы WWW или файловой службы. Количество транзитных компьютеров обычно стараются уменьшить. Если компьютеры подключены к сети с коммутацией пакетов, то число промежуточных компьютеров уменьшается до двух. Например, пользователь передает почтовое сообщение своему серверу исходящей почты, а тот сразу старается передать его серверу входящей почты адресата. Но если компьютеры связаны между собой телефонной сетью, то часто используется несколько промежуточных серверов, так как прямой доступ к конечному серверу может быть в данный момент невозможен из-за перегрузки телефонной сети (абонент занят) или экономически невыгоден из-за высоких тарифов на дальнюю телефонную связь. Техника коммутации сообщений появилась в компьютерных сетях раньше техники коммутации пакетов, но потом была вытеснена последней, как более эффективной по критерию пропускной способности сети. Запись сообщения на диск занимает достаточно много времени, и кроме того, наличие дисков предполагает использование в качестве коммутаторов специализированных компьютеров, что влечет за собой существенные затраты на организацию сети. Сегодня коммутация сообщений работает только для некоторых не оперативных служб, причем чаще всего поверх сети с коммутацией пакетов, как служба прикладного уровня.

Сравнение способов коммутации

2. Алгоритм Флойда для выбора кратчайшего пути между всеми узлами сети

2.1 Алгоритм Флойда

Этот алгоритм более общий по сравнению с алгоритмом Дейкстры, так как он находит кратчайшие пути между любыми двумя узлами сети. В этом алгоритме сеть представлена в виде квадратной матрицы с n строками и n столбцами. Элемент (i, j) равен расстоянию d_ij от узла i к узлу j, которое имеет конечное значение, если существует дуга (i, j), и равен бесконечности в противном случае.

Покажем сначала основную идею метода Флойда. Пусть есть три узла i, j и k и заданы расстояния между ними (рис.2.1). Если выполняется неравенство d_ij + d_jk < d_ik, то целесообразно заменить путь i -> k путем i -> j -> k. Такая замена (далее ее будем условно называть треугольным оператором) выполняется систематически в процессе выполнения алгоритма Флойда.

Рис.2.1. Треугольный оператор

Алгоритм Флойда требует выполнения следующих действий.

Шаг 0. Определяем начальную матрицу расстояния D₀ и матрицу последовательности узлов S₀. Диагональные элементы обеих матриц помечаются знаком "-", показывающим, что эти элементы в вычислениях не участвуют. Полагаем k = 1:



Рис.2.2 Начальная ситуация

Основной шаг k. Задаем строку k и столбец k как ведущую строку и ведущий столбец. Рассматриваем возможность применения треугольного оператора ко всем элементам d_ij матрицы D_k-1. Если выполняется неравенство d_ik + d_kj < d_ij, (i <> k, j <> k, i <> j), тогда выполняем следующие действия:

· создаем матрицу D_k путем замены в матрице D_k-1 элемента d_ij на сумму d_ik + d_kj,

· создаем матрицу S_k путем замены в матрице S_k-1 элемента s_ij на k. Полагаем k = k + 1 и повторяем шаг k.

Поясним действия, выполняемые на k-м шаге алгоритма, представив матрицу D_k-1 так, как она показана на рисунке 2.3. На этом рисунке строка k и столбец k являются ведущими. Строка i - любая строка с номером от 1 до k - 1, а строка p - произвольная строка с номером от k + 1 до n. Аналогично столбец j представляет любой столбец с номером от 1 до k - 1, столбец q - произвольный столбец с номером от k + 1 до n. Треугольный оператор выполняется следующим образом. Если сумма элементов ведущих строки и столбца (показанных в квадратах) меньше элементов, находящихся в пересечении столбца и строки (показанных в кружках), соответствующих рассматриваемым ведущим элементам, то расстояние (элемент в кружке) заменяется на сумму расстояний, представленных ведущими элементами:



Рис 2.3. Иллюстрация алгоритма Флойда

После реализации n шагов алгоритма определение по матрицам D_n и S_n кратчайшего пути между узлами i и j выполняется по следующим правилам.

1. Расстояние между узлами i и j равно элементу d_ij в матрице D_n.

2. Промежуточные узлы пути от узла i к узлу j определяем по матрице S_n. Пусть s_ij = k, тогда имеем путь i -> k -> j. Если далее s_ik = k и s_kj = j, тогда считаем, что весь путь определен, так как найдены все промежуточные узлы. В противном случае повторяем описанную процедуру для путей от узла i к узлу k и от узла k к узлу j.

2.2 Описание интерфейса и работы программы

Рис.2.4. Интерфейс программы

По описанному выше алгоритму была разработана и написана программа.

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

Порядок работы с программой:

1) Выставить вершины на поле графа. Вершины выставляются щелчком левой кнопки мыши.

2) Выбрать режим соединения вершин. Соединить вершины между собой. Граф должен быть связным, т.е. граф, в котором все вершины связаны.

3) Нажать кнопку "Рассчитать". После этого произойдет оптимизация матрицы расстояний и последовательности узлов по алгоритму Флойда.

4) Ввести номер 1 и 2 вершины, по нажатию кнопки "Найти кратчайшее расстояние" оно будет рассчитано.

Рис.2.5 Построение графа.Вычисление кратчайшего расстояния.

3. Экспериментальная часть

3.1 Анализ технического задания на проектирование РИВС

Программным комплексом NetPRO были сгенерированы 8 вертикальных сетей с начальной звездообразной топологией. Выбирая центр передачи данных необходимо добиться оптимального размещения связей между городами. Определяется начальная стоимость сети путем изменения пропускной способности канала в зависимости от трафика этого канала. И в дальнейшем сгенерировать начальные данные для проектирования горизонтальной сети, для обеспечения минимума критерия оптимальности - общей стоимости сети. Количество городов в регионах указано в таблице 1.

Таблица 3.1

№ п.п.	№ региона	Кол-во городов (узлов)
1	1	11
2	2	15
3	3	17
4	4	18
5	5	19
6	6	18
7	7	20
8	8	19
Всего:	10	137

3.2 Проектирование региональных вертикальных сетей

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

Регион 1

В исходном варианте центром сети является Вышелей и начальная стоимость сети - 3012 руб/сутки. Каналы связи между городами, в результате автоматической оптимизации, представлены на рисунке 3.1.

Рис. 3.1. Автоматическая оптимизация региона 1.

В ходе ручной оптимизации 1 региона удалось уменьшить стоимость сети на 46,9%. После оптимизации топология и параметры приняли следующий вид и значения (рисунок 3.2):

Рис. 3.2 Оптимизированная топология региона 1.

Полная стоимость С П Д в сутки - 1664 pублей

Центp С П Д - Сосновоборск

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

Регион 2

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



Рис. 3.3. Автоматическая оптимизация 2 региона.

После оптимизации топология сети имеет вид представленный на рисунке 3.4. Полная стоимость СПД в сутки - 11130 pублей. Центp СПД переместился в Усть-Камчатск. В ходе оптимизации 2 региона удалось уменьшить стоимость сети на 35,5%.

Рис.3.4 Ручная оптимизация региона 2.

Полная стоимость С П Д в сутки - 11770 pублей

Центp С П Д - Усть-Камчатск

Meста pазмещения концентpатоpов

Регион 5

В исходном варианте центром сети является Сурское и начальная стоимость сети - 6599 руб/сутки. Каналы связи между городами, в результате автоматической оптимизации, представлены на рисунке 3.5

Рис. 3.5 Автоматическая оптимизация региона 5.

После оптимизации топология сети имеет вид представленный на рисунке 3.6. Полная стоимость СПД в сутки - 3160 pублей. Центp СПД переместился в Ульяновск. В ходе оптимизации 5 региона удалось уменьшить стоимость сети на 68,1%.

Рис. 3.6 Ручная оптимизация 5 региона.

Полная стоимость С П Д в сутки - 3160 pублей

Центp С П Д - Ульяновск

Meста pазмещения концентpатоpов

Произведен анализ улучшения критерия оптимальности результирующего окончательного варианта по сравнению со стартовым автоматически оптимизированным вариантом. Результаты анализа приведены в таблице 3.2.

Таблица 3.2

№ региона	Стоимость начальной сети (руб/сутки)	Стоимость автоматически оптимизированной сети (руб/сутки)	Стоимость оптимизированной сети (руб/сутки)	% улучшения*
1	7339	6567	3438	й
2	1194	1063	922
3	32761	14672	8160	й
4	7339	4543	4492
5	6599	3931	3160
6	3205	3315	3284	й
7	7547	4698	4424
8	5909	4470	4025	й

* процент улучшения оптимизированной в ручную сети по отношению к автоматической оптимизации.

3.3 Проектирование межрегиональной горизонтальной сети

Горизонтальный синтез проектируемой сети организуется как процесс синтеза одной из возможной топологий в соответствии со следующими алгоритмами (алгоритм синтеза кольцеобразной, звездообразной и древовидной сети). После этого приступают к разработке распределенной вычислительной сети. Для синтеза кольцеобразной сети решается задача коммивояжера. Данная задача выбрана для начального этапа синтеза из соображений надежности (требование двухсвязности сети), а также для минимизации общей стоимости сети (минимизация суммарной длины связей). Задача оптимальной древовидной сети использует алгоритм Прима, который порождает минимальное связанное дерево. При синтезе звездообразной сети используется критерий минимальная стоимость, а точнее говоря, по критерию минимальной суммарной длины связей, достаточно проста. Достаточно просто перебрать все возможные варианты звездообразных сетей и выбрать вариант, имеющий минимальную стоимость. Каждая задача также основывается на удалении плохих маршрутов т.е. решается алгоритм маршрутизации. После удаления этих маршрутов подгоняется параметры сети в заданные пределы. При этом стоимость может возрасти, но в конечном итоге, изменяя пропускную способность каналов, добиваются оптимальной стоимости сети и заданных параметров. Результаты приведены в таблице 3.3.

Таблица 3.3

№ п.п.	Тип топологии	Общая стоимость	T макс, сек	Т ср, сек	Кол-во плохих маршрутов	% оптимальности
1	Кольцо	11266	44,83	2,12	19
2	Звезда	10246	3,56	1,69	0	100
3	Дерево	10452	6,25	1,27	19
4	Распределенная	17924	108,33	9,25	0

Анализируя полученные результаты проектирования горизонтальной сети, сделаем вывод, что оптимальным вариантом в соответствии с заданием является звездообразная структура (рисунок 3.7), т.к. максимальное и среднее время задержки не превышают заданного, не имеет плохих маршрутов, а также имеет наименьшую стоимость из возможных вариантов.

Рис. 3.7 Звездообразная топология сети

Отчет о результатах синтеза СПД с горизонтальными связями.

Количество городов: 10

Рассчитанные характеристики каналов

Матрица смежности B

Матрица трафиков F

Матрица пропускных способностей каналов Cap

Матрица стоимостей каналов C

Матрица загрузки каналов Ro

Матрица задержки каналов T

Маршрутизация

Интегральные оценки сети

Длина всей сети = 26117(км)

Стоимость всей сети = 10946(тыс. руб.)

Общий трафик сети = 36999 (бод)

Загрузка сети = 0.70

Макcимальная задержка сети = 3.562 (сек) в канале 8 - 7

Минимальная задержка сети = 0.740 (сек) в канале 8 - 1

Средняя задержка сети = 1.694 (сек)

Длина сообщений = 1300 (бит)

Ограничение на количество переприемов 2

Количество "плохих маршрутов" 0

Заключение

В соответствии с техническим заданием была проведена работа по проектированию горизонтальной компьютерной сети оптимальной топологии. Для выполнения задания были использованы 10 вертикальных сетей передачи данных. Для горизонтальной сети были проанализированы такие топологии как: кольцо, звезда, дерево и распределенная. В итоге оптимальной сетью для передачи данных получилась сеть со звездообразной топологией (рисунок 17). Интегральными оценками данной сети являются:

Стоимость всей сети = 10946(тыс. руб.)

Макcимальная задержка сети = 3.562 (сек)

Минимальная задержка сети = 0.740 (сек)

Количество "плохих маршрутов" 0

Для дальнейшего уменьшения стоимости необходимо установить большее значение переприемов и снизить ограничения на максимальное и минимальное время задержки в среднем на 1 секунду.

Литература

1. В.Олифер,Н.Олифер. Компьютерные сети. Учебник. М.: Питер, 2008

2. http://khpi-iip.mipk.kharkiv.edu/library/datastr/book_sod/kgsu/din_0124.html - Алгоритм Флойда

3. Решетняк В.Н., Гузик В.Ф., Сидоренко В.Г. Проектирование распределенных информационно-вычислительных сетей. Учебное пособие. Таганрог: Изд-во ТРТУ, 1996.

Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, ExtCtrls, Grids, StdCtrls;

type

TForm1 = class(TForm)

Image1: TImage;

D: TStringGrid;

S: TStringGrid;

Label1: TLabel;

Label2: TLabel;

CheckBox1: TCheckBox;

Button1: TButton;

Bevel1: TBevel;

Bevel2: TBevel;

Edit1: TEdit;

Edit2: TEdit;

Label3: TLabel;

Label4: TLabel;

Button3: TButton;

Label5: TLabel;

Label6: TLabel;

procedure Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure FormCreate(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

PP = record

x:integer;

y:integer;

end;

var

Form1: TForm1;

PointMas: array [1..50] of pp;

n:integer=0;

FO:integer;

flag:boolean=false;

implementation

{$R *.dfm}

procedure MatrixD(flag:boolean;FP:integer;SP:integer);

var

i,j,DecShir, DecDolg:integer;

begin

if not flag then begin

for i:=0 to N do

for j:=0 to N do

begin

if i=j then Form1.D.Cells[i,j]:='----';

if (i=0) and (j<>0) then Form1.D.Cells[i,j]:=inttostr(j);

if (i<>0) and (j=0) then Form1.D.Cells[i,j]:=inttostr(i);

If (i<>0) and (j<>0) and (i<>j) then

begin

Form1.d.Cells[i,j]:=inttostr(2147483647);

end;

end;

end

else begin

DecShir:=sqr(PointMas[fp].x-PointMas[sp].x);

DecDolg:=sqr(PointMas[fp].y-PointMas[sp].y);

Form1.d.Cells[fp,sp]:=copy(floattostr(SQRT(DecShir + DecDolg)),0,5);

Form1.d.Cells[sp,fp]:=copy(floattostr(SQRT(DecShir + DecDolg)),0,5);

end;

end;

procedure MatrixS;

var

i,j:integer;

begin

for i:=0 to N do

for j:=0 to N do

begin

if i=j then Form1.s.Cells[i,j]:='----';

if (i=0) and (j<>0) then Form1.s.Cells[i,j]:=inttostr(j);

if (i<>0) and (j=0) then Form1.s.Cells[i,j]:=inttostr(i);

if (i<>0) and (j<>0) and (i<>j) then begin

Form1.S.Cells[j,i]:=inttostr(j);

end;

end;

end;

procedure TForm1.Image1MouseDown(Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

var

i:integer;

dlinaX, DlinaY:integer;

begin

if not checkbox1.Checked then

begin

inc(n);

PointMas[n].x:=x;

PointMas[n].y:=y;

Image1.Canvas.Ellipse(x-8,y-8,x+8,y+8);

Image1.Canvas.TextOut(x-5,y-20,inttostr(n));

d.Cells[0,0]:='# points';

Form1.D.ColCount:=N+1;

Form1.D.RowCount:=N+1;

Form1.s.ColCount:=N+1;

Form1.s.RowCount:=N+1;

matrixd(false,0,0);

matrixS;

end

else begin

for i:=1 to n do begin

if (x>PointMas[i].x-8) and (x<PointMas[i].x+8) and

(y>PointMas[i].y-8) and (y<PointMas[i].y+8) then

if not flag then begin

flag:=true;

FO:=i;

end

else begin

flag:=false;

Image1.Canvas.MoveTo(PointMas[FO].x,PointMas[FO].y);

Image1.Canvas.lineto(PointMas[i].x,PointMas[i].y);

matrixd(true,i,fo);

end;

end;

end;

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Image1.Canvas.Pen.Width:=2;

end;

procedure TForm1.Button1Click(Sender: TObject);

var

i,j,m:integer;

k:integer;

begin

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if (i<>j) and (i<>k) and (j<>k) then

if (strtofloat(d.Cells[k,i])+strtofloat(d.Cells[j,k])<strtofloat(d.Cells[j,i]))

or (d.Cells[j,i]='----') then begin

D.Cells[j,i]:=floattostr(strtofloat(d.Cells[k,i])+strtofloat(d.Cells[j,k]));

s.Cells[j,i]:=inttostr(k);

end;

end;

procedure TForm1.Button3Click(Sender: TObject);

var

i,j,one,two:integer;

Way: string;

dlina: real;

begin

if (strtoint(edit1.Text)>n) or (strtoint(edit2.Text)>n) then

messagebox(0,'Tръюую ъюышўхёЄтр тхЁ°шэ эхЄ!','+°шсър', 0)

else begin

one:=strtoint(edit1.Text);

two:=strtoint(edit2.Text);

way:=inttostr(one);

i:=one;

dlina:=0;

if strtoint(S.Cells[two,i])<>two {and strtoint(s.Cells[two,i])<>0)} then

while strtoint(S.Cells[two,i])<>two do begin

j:=strtoint(S.Cells[two,i]);

while (strtoint(S.Cells[j,i])<>j) do

j:=strtoint(S.Cells[j,i]);

way:=way+', '+S.Cells[j,i];

dlina:=dlina+strtofloat(d.Cells[j,i]);

i:=j;

end;

way:=way + ', ' + inttostr(two);

dlina:=dlina + strtofloat(d.Cells[two, i]);

label5.Caption:='Кратчайшее растояние: '+ way;

label6.Caption:='Минимальная длина: ' + floattostr(dlina); end;

end;

end.

Размещено на Allbest.ru