4.1 Разработка проекта построения DWDM сети в поселке Ростоши
Известными для решения поставленной задачи являются: карта местности, место расположения узла доступа и точки конечного пользователя (абонента). Необходимо выбрать оптимальный путь прокладки кабеля из места расположения узла доступа до места расположения каждого пользователя, а так же расположить оборудование в различных узлах сети таким образом, чтобы снизить общую стоимость проекта.
Существует ряд реализованных программ, позволяющих искать кратчайший путь проезда по дорожной сети на электронной карте. В рассмотренных системах используются различные критерии оптимальности пути - от критерия кратчайшего расстояния до сложных критериев оценки времени с учетом информации о пробках. В отмеченных работах в основном рассматривается алгоритмы поиска только оптимального пути.
Математическая модель. Множество всех возможных трасс прокладки кабеля по улицам города представляется в виде ориентированного графа G = (A, W), где A – множество вершин, W – множество дуг. Вершинам этого графа соответствуют: перекрестки на улицах города, место расположения узла доступа i ∈ A и место нахождения абонентов j ∈ A. Вершины графа - это места дорожной сети, где имеются возможности выбора дальнейшего маршрута прокладки кабеля по улицам. Ребрам графа соответствуют магистрали и улицы между двумя вершинами. Для ребер графа задаются матрица расстояний L = |lsd| и матрица нужного колличества оборудования с заданными характеристиками С = |сsd|, s, d ∈ A. Для каждой вершины графа s ∈ A с учетом наличия или отсутствия оборудования задаются значения zs – требуемые характеристики. Тогда tsd - количество оборудования ребре (s, d) определяется по формуле
tsd = lsd/ сsd + zs, s, d ∈ A, (4.1)
Для заданных начальных и конечных вершин графа i и j требуется определить маршрут прокладки кабеля Rij, затрачивающего наименьшее количество самого кабеля, а так же дополнительного оборудования (разветвители и опто-розетки).
Алгоритм решения. Алгоритм решения задачи состоит из двух этапов. Определения кратчайшего по времени маршрута проезда Rij сводится к решению известной задачи кратчайшего пути на ориентированном графе. Для ее решения применяются известный алгоритм Дейкстры, основанный на расстановке пометок на вершинах графа. Для определения множества всех вариантов расположения оборудования применяется алгоритм, основанный на методе последовательного анализа вариантов и использовании правила отбраковки бесперспективных вариантов до получения окончательного решения.
Как известно, в алгоритме Дейкстры для поиска кратчайшего пути вершинам графа приписывают временные или постоянные пометки. Пометки определяют для вершины верхнюю границу длины пути от i вершины до текущей. Величины временных пометок вершин постепенно уменьшаются. Значение пометки определяет возможную длину пути от начальной до этой вершины. На каждом шаге алгоритма только одна из пометок с минимальным значением на рассматриваемом уровне выбирается в качестве постоянной.
Это значит, что значение пометки является длиной кратчайшего пути из i вершины в текущую вершину.
Введем следующие обозначения: V(s) – множество ребер, входящих или выходящих из вершины s (V(s) ⊆ W); |V(s)| – мощность множества; psj – пометки вершины s ∈ A, j = 0, 2, …,|V(s)|-1; B – множество вершин с постоянными пометками для j = 0.
Алгоритм первого этапа поиска оптимального маршрута состоит из шести шагов:
Шаг 1. Присвоить пометке начальной вершины pi0 = 0 и считать постоянной. Для всех остальных вершин s ∈ A\{i} установить ps0 = ∞ и считать эти пометки временны-ми. Установить d = i; B = {i}. Обновить метки.
Шаг 2. Для всех вершин s ∈ V(d) вычисляются новые значения
psj = pdj + tds , j = 0, 2, …, |V(s)|-1 (4.2)
Таким образом, для каждой вершины будет определено время проезда для всех возможных путей от исходной вершины i до вершины s .
Для j = 0 временные пометки вычисляются, используя выражение
ps0 = min[ ps0 , ( pd0 + tds )] (4.3)
и превращаются эти пометки в постоянные.
Шаг 3. Среди всех вершин с временными пометками s ∈ A\B найти такую вершину k, для которой значение пометки минимально pk0 = min ps0 .
Шаг 4. Считать пометку pk0 постоянной и установить d = k. В множество B добавить вершину k.
Шаг 5. Если d ≠ j, то перейти к шагу 2. Если d = j, то pk0 является длиной кратчайшего пути Rij из вершины i в вершину j.
Шаг 6. Если все пометки всех вершин постоянные, т.е. B = A, то на этом определение времени оптимального пути прокладки кабеля завершается.
После этого происходит восстановление маршрута прокладки кабеля от узла доступа до всех абонентов сети.
На втором этапе алгоритма задается допустимое значение отклонения от оптимального значения E. На первом этапе, в отличие от алгоритма Дейкстры, для каждой вершины в зависимости от мощности множества V(s) вычисляются по формуле (2) и запоминается не одно, а ряд значений пометок. Затем для каждой вершины отбрасываются те значения пометок, для которых выполняется соотношение
psj > (pk0 + E), s ∈ V(d), j = 0, 2, ..., |V(s)|-1 (4.4)
На рисунке 4.1 приведена схема работы предложенного алгоритма для простого примера графа, состоящего из 9 вершин и 20 ребер.
Приведенные для всех вершин ряд значений чисел внутри выделенных прямоугольников представляют собой ряд значений пометок, которые получены на втором этапе алгоритма.
На первом месте в этом ряду располагаются пометки, получаемые по алгоритму Дейкстры. Эти пометки выделены жирным шрифтом. Полученный оптимальный маршрут длиной 7 проходит через вершины 1 - 7 - 4. Для поиска значения необходимого количества оборудования задано значение E=27. Зачеркнутые значения величин пометок означают отброшенные варианты путей согласно неравенству (4). В конце работы алгоритма получены два близких к оптимальному маршрута с длинами 16 и 34, проходящие, соответственно, через вершины 1 – 2 – 7 – 4 и 1 – 8 – 5 – 4.
Рисунок 4.1 – Схема работы алгоритма состоящего из 9 вершин и 20 ребер.4.2 Расчеты и анализ полученных результатов
С помощью разработанного ПК проведены расчеты с целью исследования производительности алгоритмов от входных данных. При проведении всех расчетов задавались параметры: K = 5, E ≤ 3.
Расчеты зависимости поиска кратчайшего маршрута прокладки кабеля от узла доступа до абонентов и нахождение оптимального количества оборудования с заданными техническими характеристиками проводились на карте города Оренбурга, п.Ростоши, представляющей собой граф с 1221 вершинами и 3559 ребрами. Была выбрана одна начальная вершина и несколько конечных вершин на разных расстояниях от начальной вершины. Для каждой такой пары вершин произведен поиск маршрутов прокладки кабеля с помощью трех алгоритмов, причем каждый из алгоритмов запускался несколько раз, а время поиска, измеряемое в миллисекундах, было усреднено.
В таблице 4.1 приведены результаты расчетов, выполненных для центра поселка.
Начальный пункт выбирался из узла связи на ул.Газпромовская, а конечный пункт назначался на улицах:
− Самарской, дом 60 (606 м, 35 вершин);
− Цветного бульвара, дом 31 (902 м, 67 вершин);
− Российской, дом 47 (1006 м, 88 вершин);
− Успенской, дом 23 (1507 м, 117 вершин);
− Ковыльной, дом 23 (3304 м, 172 вершины).
Таблица 4.1. Зависимость времени поиска от числа вершин графа
|
Число вершин графа |
35 |
67 |
88 |
117 |
172 |
|
Алгоритм Дейстры |
0,01 |
0,03 |
0,13 |
0,24 |
0,27 |
|
К маршрутов |
3,94 |
7,41 |
27,34 |
66,41 |
117,63 |
|
Е необходимое |
9 |
18 |
14 |
20 |
29 |
Результаты расчетов показывают, что время поиска всех E близких к оптимальному и имеет хорошую производительность. Эффективность алгоритма объясняется тем, что дорожная сеть п.Ростоши представляется весьма неполным графом. Поэтому отбраковка заведомо неоптимальных маршрутов происходит на ранних шагах построения вариантов. При этом полученное оптимальное решение позволяет эффективно отбрасывать те частичные решения, для которых не выполняются условия (4). Значительное возрастание времени поиска K маршрутов происходит потому, что алгоритм осуществляет поиск всех возможных отклонений по вершинам предыдущего маршрута и только после этого выбирает нужное число маршрутов прокладки кабеля.
Для реализованных алгоритмов исследовались зависимости времени поиска маршрутов от размерности графа. Для проведения этих расчетов использованы четыре карты п.Ростоши разного размера:
− весь п.Ростоши – граф с 1221 вершинами и 3559 ребрами;
− центр п.Ростоши – граф с 475 вершинами и 1444 ребрами;
− северная часть п.Ростоши– граф c 200 вершинами и 611 дугами;
− южная часть п.Ростоши – граф c 186 вершинами и 453 дугами.
Для расчетов выбраны две вершины, присутствующие на всех четырех картах.
Произведен поиск пути между этими вершинами на каждой из четырех карт с помощью трех алгоритмов. Усредненное время поиска маршрутов прокладки кабеля при проведенных многочисленных расчетах, измеряемое в секундах, сведено в таблицу 4.2.
Таблица 4.2. Зависимость времени поиска маршрутов от размерности графов
|
Число вершин графа |
186 |
200 |
475 |
1221 |
|
Алгоритм Дейстры |
0,005 |
0,006 |
0,009 |
0,012 |
|
K маршрутов |
0,056 |
0,41 |
0,954 |
2,348 |
|
Е необходимое |
0,5 |
2 |
5 |
8 |
Полученные расчеты показывают, что время работы всех трех алгоритмов зависит нелинейно от числа вершин графа. Результаты расчетов показывают, что изложенный в работе алгоритм нахождения всех E необходимых является весьма эффективным для графов значительных размеров.
Предложена математическая модель задачи выбора оптимального пути прокладки кабеля в виде задачи дискретного программирования и алгоритм ее решения являются эффективными. Определение всех нужного количества оборудования с заданными техническими характеристиками позволяет при окончательном выборе маршрута учесть дополнительные неформализованные требования.
Предложенный алгоритм, являющийся модификацией известного алгоритма Дейкстры, реализован в виде программного комплекса на языке JAVA. Результаты проводимых расчетов представляются в удобном виде на электронной карте города.
Проведенные расчеты подтверждают, что алгоритм Дейкстры более эффективен для поиска оптимального пути. Предложенный алгоритм поиска оптимального маршрута прокладки кабеля показывает хорошую производительность для графов достаточно больших размеров.
4.3 Описание программного средства автоматизации процесса проектирования сетей DWDM
На базе разработанного алгоритма создан программный комплекс для автоматизации процесса проектирования сетей DWDM, который представляет собой комплексный инструмент проектирования сетей DWDM и оптимизации подбора необходимого пассивного оборудования на линейной части проектируемой сети, помогающий создать оптимальную инфраструктуру сети DWDM, поддерживающую предоставление современных телекоммуникационных услуг.
Программа представляет собой клиентскую часть, выполненную в среде программирования Java SE 1.7. Java SE – это платформа программирования для разработчиков, создающих апплеты для браузера, средства командной строки и приложения с графическим интерфейсом, предназначенные для пользователей рабочей среды. Приложения, написанные на языке Java, выполняются в операционных системах Windows, Mac OS, Linux, Solaris и др.
На данный момент это единственная технология, которая:
− промышленная и предназначена для создания больших систем;
− кросс-платформенная;
− не контролируется одним производителем;
− открытая (да, вы можете скачать C++ код виртуальной машины Java и помучить его);
− с автоматическим управлением распределением памятью, дающим прирост до 30% производительности труда программистов по-сравнению с С/С++;
− имеет большое количество модулей, каркасов, проектов и инструментов с открытым исходным кодом;
− имеет давние традиции совместной разработки открытых стандартов;
− преподается практически во всех западных университетах;
− большое количество исследовательских университетских проектов.
Универсальность, эффективность, портативность платформ и безопасность технологии Java делают эту технологию идеальным выбором для сетевых вычислений. От портативных компьютеров до центров сбора данных, от игровых консолей до суперкомпьютеров, используемых для научных разработок, от сотовых телефонов до сети Интернет — Java используется повсюду.
Следующие успешные проекты реализованы с привлечением Java (J2EE) технологий: RuneScape, Amazon, eBay, Yandex (неоднозначная информация в отношении Java), LinkedIn, Yahoo!.
Следующие компании в основном фокусируются на Java (J2EE) технологиях: SAP, IBM, Oracle. В частности, СУБД Oracle включает JVM как свою составную часть, обеспечивающую возможность непосредственного программирования СУБД на языке Java, включая, например, хранимые процедуры.
Производительность. Программы, написанные на Java, имеют репутацию более медленных и занимающих больше оперативной памяти, чем написанные на языке С, скорость выполнения программ, написанных на языке Java, была существенно улучшена с выпуском в 1997—1998 годах так называемого JIT-компилятора в версии 1.1 в дополнение к другим особенностям языка для поддержки лучшего анализа кода (такие как внутренние классы, класс StringBuffer, упрощенные логические вычисления и т. д.). Кроме того была произведена оптимизация виртуальной машины Java — с 2000 года для этого используется виртуальная машина HotSpot. По состоянию на февраль 2012 года, код Java 7 приблизительно лишь в 1.8 раза медленнее кода, написанного на языке C.
Некоторые платформы предлагают аппаратную поддержку выполнения для Java. К примеру, микроконтроллеры выполняющие код Java на аппаратном обеспечении вместо программной JVM, а также основанные на ARM процессоры, которые поддерживают выполнение байткода Java через опцию Jazelle.
Основные возможности:
— автоматическое управление памятью;
— расширенные возможности обработки исключительных ситуаций;
— богатый набор средств фильтрации ввода/вывода;
— набор стандартных коллекций, таких как массив, список, стек и т. п.;
— наличие простых средств создания сетевых приложений (в том числе с использованием протокола RMI);
— наличие классов, позволяющих выполнять HTTP-запросы и обрабатывать ответы;
— встроенные в язык средства создания многопоточных приложений;
— унифицированный доступ к базам данных:
— на уровне отдельных SQL-запросов — на основе JDBC, SQLJ;
— на уровне концепции объектов, обладающих способностью к хранению в базе данных — на основе Java Data Objects (англ.) и Java Persistence API (англ.);
— поддержка шаблонов (начиная с версии 1.5);
— параллельное выполнение программ.
Программы на Java транслируются в байт-код, выполняемый виртуальной машиной Java (JVM) — программой, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор.
Достоинством подобного способа выполнения программ является полная независимость байт-кода от операционной системы иоборудования, что позволяет выполнять Java-приложения на любом устройстве, для которого существует соответствующая виртуальная машина. Другой важной особенностью технологии Java является гибкая система безопасности благодаря тому, что исполнение программы полностью контролируется виртуальной машиной. Любые операции, которые превышают установленные полномочия программы (например, попытка несанкционированного доступа к данным или соединения с другим компьютером) вызывают немедленное прерывание.
Часто к недостаткам концепции виртуальной машины относят то, что исполнение байт-кода виртуальной машиной может снижать производительность программ и алгоритмов, реализованных на языке Java. В последнее время был внесен ряд усовершенствований, которые несколько увеличили скорость выполнения программ на Java:
− применение технологии трансляции байт-кода в машинный код непосредственно во время работы программы (JIT-технология) с возможностью сохранения версий класса в машинном коде;
− широкое использование платформенно-ориентированного кода (native-код) в стандартных библиотеках;
− аппаратные средства, обеспечивающие ускоренную обработку байт-кода (например, технология Jazelle, поддерживаемая некоторыми процессорами фирмы ARM).
По данным сайта shootout.alioth.debian.org, для семи разных задач время выполнения на Java составляет в среднем в полтора-два раза больше, чем для C/C++, в некоторых случаях Java быстрее, а в отдельных случаях в 7 раз медленнее. С другой стороны, для большинства из них потребление памяти Java-машиной было в 10-30 раз больше, чем программой на C/C++. Также примечательно исследование, проведённое компанией Google, согласно которому отмечается существенно более низкая производительность и бо́льшее потребление памяти в тестовых примерах на Java в сравнении с аналогичными программами на C++.
Идеи, заложенные в концепцию и различные реализации среды виртуальной машины Java, вдохновили множество энтузиастов на расширение перечня языков, которые могли бы быть использованы для создания программ, исполняемых на виртуальной машине. Эти идеи нашли также выражение в спецификации общеязыковой инфраструктуры CLI, заложенной в основу платформы .NET компанией Microsoft.
Проектирование и оптимизация сети DWDM – это интерактивный процесс, требующий учета всех ограничений системы:
1) Расстояния на отрезках сети;
2) Типы и число услуг, которые должны быть предоставлены в каждой точке, подключенной к сети;
3) Особенности местности, для которой проектируется сеть;
4) Количество узлов доступа (необходимая емкость сети);
5) Экономические показатели.
На основании этих требований при проектировании сети DWDM необходимо оптимально расположить оборудование в различных узлах сети таким образом, чтобы снизить общую стоимость проекта.
Разработанный комплекс предоставляет набор функций, которые дают телекоммуникационным компаниям возможность планировать и проектировать изменения и обновления в сетях.
При запуске программы открывается карта, загружаемая в режиме on-line, с ресурсов Ethernet. На основание выбора города, района изображение карты масштабируется до удобного в использовании пользователю варианта, рисунок 4.2.
Рисунок 4.2 – Карта п.Ростоши в масштабе 1:60
Созданный программный комплекс автоматизированного проектирования сетей DWDM, учитывая выше указанные ограничения, позволяет проектировать, а так же оптимизировать сети DWDM, что повышает их производительность и позволяет снизить эксплуатационные расходы, рисунок 4.3.
Удобный графический интерфейс позволяет использовать ряд возможностей необходимых для оперативной и комфортной работы пользователя. Графический интерфейс использует визуализацию разнотипных объектов, которые находятся под одной географической или физической локацией, позволяет упорядочить разными способами, разместить их на карте, применить цветовую маркировку для улучшения визуального восприятия.
Рисунок 4.3 – Интерфейс пользователя
Инструмент учитывает топологию сетей, типы и протяженность используемого оптического волокна, а также текущие и будущие потребности в отношении трафика, рисунок 4.4.
Рисунок 4.4 – Пример расчета расхода кабеля и необходимого количества сплитеров
Программный комплекс автоматизированного проектирования сетей DWDM так же позволяет проектировать сети возможностью соединения любых точек, помогает разработать проект сети DWDM, обладающей полной гибкостью как в отношении возможностей соединения начальных и конечных точек, так и в отношении интерфейсов и услуг.
Рисунок 4.5 – Экранная форма «Просмотр полученного результата»
Таким образом, пользователь получает возможность учитывать различные сетевые сценарии и снизить общую стоимость сети. Полученные результаты проектирования можно сохранить (пользователь сам выбирает путь сохранения файла) или же сбросить, для того чтобы выбрать новый вариант проектирования сети, рисунок 4.6.
Рисунок 4.6 – Экранная форма «Сохранение полученного результата»
Благодаря, вышеуказанным возможностям, программный комплекс автоматизированного проектирования сетей DWDM, в корне изменяет процедуру проектирования городских сетей DWDM. Возможности программного комплекса автоматизированного проектирования сетей DWDM позволят значительно снизить капиталовложения и эксплуатационные расходы на проектирование современных городских сетей.
Достоверность разработанного программного комплекса автоматизированного проектирования сетей DWDM проверена путем сравнения численных результатов проектирования сети FTTH для п.Ростоши рисунок 4.7.
Рисунок 4.7 – Схема прокладки кабеля по технологии xPON п.Ростоши