Модернизация компьютерной сети предприятия с целью достижения заданной пропускной способности

Содержание

Введение 3

1 Общая часть 5

1.1 Постановка  задачи 5

1.2 Способы решения задачи. Преимущества и недостатки 6

1.3 Определение выбора алгоритма 8

1.4 Определение  метода и технологий проектирования 8

1.5 Выбор инструментальных  средств 9

2 Расчётная  часть 11

2.1 Построение  математической модели 11

2.2 Организация  входной информации и выходных  данных 14

2.3 Описание основных модулей программы 16

Заключение 17

Список литературы 18

Приложения 

Приложение  А Техническое задание

Примечание  Б Спецификация

Приложение В Руководство пользователя

Приложение  Г Текст программы

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

Данный программный  продукт должен выполнять ряд  следующих функций:

• графическое отображение сети;
• возможность добавлять и удалять элементы сети;
• возможность добавлять и удалять связи элементов сети;
• рассчитывать пропускную способность между элементами такой сети.

 

 

 

Целью данной работы является:

• упростить работу системных администраторов по модернизации сетей их предприятий;
• насколько задача написания готового полноценного программного продукта выполнима для одного человека и сколько это потребует времени;
• является ли каскадный метод разработки программ подходящим для написания полноценного конкурентно способного программного обеспечения  при работе над продуктом всего одного человека;
• перспективна ли разработка маленьких программ направленных на облегчение выполнения какой-либо определенной задачи;

 

1 Общая часть

1.1 Постановка задачи

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

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

Требования  к программному средству:

1. Должно очень наглядно отображать план компьютерной сети;
2. Оптимально и быстро рассчитывать пропускную способность между двумя узлами данной сети;

 

 

 

 

 

 

 

 

1.2 Способы решения задачи. Преимущества и недостатки

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

Метод	Сложность	Описание
Линейное программирование	Зависит от конкретного  алгоритма.  Для симплекс-метода экспоненциальна.	Представить задачу о максимальном потоке как задачу линейного программирования. Переменными  являются потоки по рёбрам, а ограничениями — сохранение потока и ограничение пропускной способности.
Алгоритм Форда-Фалкерсона	Зависит от алгоритма  поиска увеличивающего пути.  Требует O(max| f |) таких поисков.	Найти любой  увеличивающий путь. Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей. Повторять, пока увеличивающий путь есть. Алгоритм работает только для целых пропускных способностей. В противном случае, он может работать бесконечно долго, не сходясь к правильному ответу.
Алгоритм Эдмондса-Карпа	O(VE²)	Выполняем алгоритм Форда-Фалкерсона, каждый раз выбирая кратчайший увеличивающий путь (находится поиском в ширину).
Алгоритм Диница	O(V²E)   для единичных пропускных способностей   с использованием динамических деревьев Слетора и Тарьяна	Усовершенствование  алгоритма Эдмондса-Карпа (но хронологически был найден раньше). На каждой итерации, используя поиск в ширину, определяем расстояния от источника до всех вершин в остаточной сети. Строим граф, содержащий только такие рёбра остаточной сети, на которых это расстояние растёт на 1. Исключаем из графа все тупиковые вершины с инцидентными им рёбрами, пока все вершины не станут нетупиковыми. (Тупиковой называется вершина, кроме источника и стока, в которую не входит ни одно ребро или из которой не исходит ни одного ребра.) На получившемся графе отыскиваем кратчайший увеличивающий путь (им будет любой путь из s в t). Исключаем из остаточной сети ребро с минимальной пропускной способностью, снова исключаем тупиковые вершины, и так пока увеличивающий путь есть.
Алгоритм проталкивания  предпотока	O(V²E)	Вместо потока оперирует с предпотоком. Отличие  в том, что для любой вершины u, кроме источника и стока, сумма  входящих в неё потоков для  потока должна быть строго нулевой (условие сохранения потока), а для предпотока — неотрицательной. Кроме того, для каждой вершины алгоритм сохраняет дополнительную характеристику, высоту, являющуюся целым неотрицательным числом. Алгоритм использует две операции: проталкивание, когда поток по ребру, идущему из более высокой в более низкую вершину, увеличивается на максимально возможную величину, и подъём, когда переполненная вершина, проталкивание из которой невозможно из-за недостаточной высоты, поднимается. Проталкивание возможно, когда ребро принадлежит остаточной сети, ведёт из более высокой вершины в более низкую, и исходная вершина переполнена. Подъём возможен, когда поднимаемая вершина переполнена, но ни одна из вершин, в которые из неё ведут рёбра остаточной сети, не ниже её. Он совершается до высоты на 1 большей, чем минимальная из высот этих вершин. Изначально высота источника, по всем рёбрам, исходящим из источника, течёт максимально возможный поток, а остальные высоты и потоки нулевые. Операции проталкивания и подъёма выполняются до тех пор, пока это возможно.
Алгоритм «поднять в начало»	O(V³)  O(VE log(V²/E)) с использованием динамических деревьев	Вариант предыдущего  алгоритма, специальным образом  определяющий порядок операций проталкивания  и подъёма.

 

1.3 Определение выбора алгоритма и определение его сложности

Для решения  задачи о максимальном потоке будем  использовать алгоритм Диница, так  как он наиболее оптимален по времени работы, и время его работы O(V²E) в большей мере зависит от количества вершин графа, добавление ребер на время работы сильно не повлияет.

1.4 Определение метода и технологий проектирования

Для своего курсового  проекта я выбрал каскадный метод  разработки программ, так как он является лучшим выбором для разработки небольшой программы одним человеком. Разработка будет выполняться последовательно этап за этапом:

1. Требования заказчика
2. Прототипирование
3. Проектирование
4. Разработка
5. Тестирование
6. Сопровождение

Новый этап будет  начинаться только после полного  завершения предыдущего.

Для реализации программы  больше всего подходит технология Объектно-ориентированное программирование (в дальнейшем ООП).

ООП — парадигма программирования, в которой основными концепциями являются понятия объектов и классов. В случае языков с прототипированием вместо классов используются объекты-прототипы.

1.5 Выбор инструментальных средств

В качестве инструмента  разработки будем использовать Microsoft Visual Studio 2012. Язык программирования, на котором будет реализовано программное решение – С#.

Visual C# является реализацией  языка C# корпорацией Майкрософт. Visual Studio поддерживает Visual C# с полнофункциональным редактором кода, компилятором, шаблонами проектов, конструкторами, мастерами кода, мощным и простым в использовании отладчиком и многими другими средствами.

С# разрабатывался как язык программирования прикладного уровня для CLR (Common Language Runtime — виртуальная машина, интерпретирующая и исполняющая программный код) и, как таковой, зависит, прежде всего, от возможностей самой CLR. Это касается, прежде всего, системы типов C#, которая отражает BCL (Base Class Library — стандартная библиотека классов платформы .NET Framework). Присутствие или отсутствие тех или иных выразительных особенностей языка диктуется тем, может ли конкретная языковая особенность быть транслирована в соответствующие конструкции CLR. Так, с развитием CLR от версии 1.1 к 4.5 значительно обогатился и сам C#; подобного взаимодействия следует ожидать и в дальнейшем. (Однако эта закономерность была нарушена с выходом C# 3.0, представляющим собой расширения языка, не опирающиеся на расширения платформы .NET.) CLR предоставляет C#, как и всем другим .NET-ориентированным языкам, многие возможности, которых лишены "классические" языки программирования. Например, сборка мусора не реализована в самом C#, а производится CLR для программ, написанных на C# точно так жe, как это делается для программ на VB.NET, J# и др.

Среда разработки Microsoft Visual Studio 2012 предназначена для создания надежных многоуровневых приложений для Windows («smart clients»), интернета, мобильных устройств и для приложений Microsoft Office.

Профессиональные  разработчики найдут в Visual Studio 2012 высокоэффективную среду разработки, с улучшенными графическими конструкторами, редакторами кода и несколькими языками программирования;

Для профессиональных разработчиков, работающих индивидуально  или в небольших коллективах, Microsoft предлагает два продукта: профессиональную версию Visual Studio 2012 Professional и Visual Studio 2012 C# Express бесплатную версию этой среды разработки. В обеих версиях добавлены средства для разработки и отладки на удаленных серверах, для разработки под SQL Server 2012, а также задействованы все возможности среды разработки. Каждый из этих продуктов можно приобрести как отдельно, так и в составе подписки MSDN.

 

2 Расчетная часть

2.1 Построение  математической модели

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

Транспортной сетью будем называть неориентированный связный граф G(V,E) без петель, в котором каждое ребро (u,v) принадлежащее E имеет неотрицательную пропускную способность c(u,v) ≥ 0 и поток f(u,v). Выделяются две вершины: источник s и сток t такие, что любая другая вершина сети лежит на пути из s в t. Потоки в неориентированных графах можно изобразить в виде потоков в соответствующих ориентированных.

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

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

1. линейное программирование (сложность зависит от конкретного алгоритма, в случае симплекс-метода экспоненциальна);
2. алгоритм Форда-Фалкерсона (сложность O(E*f), где f – максимальный поток в графе);
3. алгоритм Эдмондса-Карпа (сложность O(VE²));
4. алгоритм Диница (сложность O(V²E));
5. алгоритм проталкивания предпотока (сложность O(V²E)).

Наиболее простым  оптимальным по скорости вычислений является алгоритм Диница. Далее, рассмотрим как он работает.

Введём три  необходимых определения (каждое из них является независимым от остальных), которые затем будут использоваться в алгоритме Диница.

Остаточной  сетью G^R по отношению к сети G и некоторому потоку в ней называется сеть, в которой каждому ребру (u, v) ∈ G с пропускной способностью c_uv и потоком f_uv соответствуют два ребра:

• (u, v) с пропускной способностью c_uv = c^R_uv - f_uv
• (v, u) с пропускной способностью c_vu = f_uv

Остаточное  ребро можно интуитивно понимать как меру того, насколько ещё можно  увеличить поток вдоль какого-то ребра. В самом деле, если по ребру (u, v) с пропускной способностью c_uv протекает поток f_uv, то потенциально по нему можно пропустить ещё c_uv - f_uv единиц потока, а в обратную сторону можно пропустить до f_uv единиц потока, что будет означать отмену потока в первоначальном направлении.

Блокирующим потоком в данной сети называется такой поток, что любой путь из истока s в сток t содержит насыщенное этим потоком ребро. Иными словами, в данной сети не найдётся такого пути из истока в сток, вдоль которого можно беспрепятственно увеличить поток. Блокирующий поток не обязательно максимален.

Слоистая  сеть для данной сети строится следующим образом. Сначала определяются длины кратчайших путей из истока s до всех остальных вершин; назовём уровнем level[u] вершины её расстояние от истока. Тогда в слоистую сеть включают все те рёбра (u, v) исходной сети, которые ведут с одного уровня на какой-либо другой, более поздний, уровень, т.е. level[u] + 1 = level[v] (почему в этом случае разница расстояний не может превосходить единицы, следует из свойства кратчайших расстояний). Таким образом, удаляются все рёбра, расположенные целиком внутри уровней, а также рёбра, ведущие назад, к предыдущим уровням.

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

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

В таблице 1 приведена симуляция алгоритма Диница. Во вспомогательной сети G_L вершины с красными метками — значения dist(v).

Таблица 1. «Симуляция алгоритма Диница».

	G	Gf	GL
1
	Блокирующий поток  состоит из путей: {s, 1, 3, t} с 4 единицами потока, {s, 1, 4, t} с 6 единицами потока, и {s, 2, 4, t} с 4 единицами потока. Следовательно, блокирующий поток содержит 14 единиц, а величина потока |f| равна 14. Заметим, что дополняющий путь имеет 3 ребра.
2
	Блокирующий поток  состоит из путей: {s, 2, 4, 3, t} с 5 единицами потока. Следовательно, блокирующий поток содержит 5 единиц, а величина потока |f| равна 14 + 5 = 19. Заметим, что дополняющий путь имеет 4 ребра.
3
	Сток t не достижим в сети Gf. Поэтому алгоритм останавливается и возвращает максимальный поток величины 19. Заметим, что в каждом блокирующем потоке количество рёбер в дополняющем пути увеличивается хотя бы на одно.