DonNTU   Masters' portal

Abstract on theme: "Research and development of software and system synthesis optimizing the network topology in class tree structures"

Table of contents

1. Relevance of the topic

The task of finding the shortest (or optimal) path always relevant. Nowadays in the field of solving transport problems added new – delivery of education in various places around the globe. One of the main problems for distance learning network was searching the optimal route of transmission of data as to the quality of distance learning universities should cooperate closely with the students. It is important to quickly and deliver lossless output data.

2. The purpose and objectives of the study and planned results

The study is analysis and software development system synthesis and optimization of network topology in the class tree structure .

Research objectives:

1. Review of existing approaches to solving the problem synthesis of network topology in the class tree structure

2. Analysis of specific algorithms synthesis topology networks

3. Optimal schemes synthesis of network topology in class tree structure

4. Software implementation of the chosen scheme

5. Analysis of the software

Planned results:

1. Improving existing methods of synthesis topology networks

2. Improving the quality of data transmission systems in distance education

3. Comparison of the developed system with existing analog

3. Scientific novelty

For quality distance learning universities should cooperate closely with the students. At the moment there are not many systems that can ensure the smooth delivery of education in various places around the globe. The disadvantage of existing systems is slow work, and sometimes loss reporting purposes. The system being developed should get rid of existing sources currently total inefficient work.

4. Research and analysis of algorithms of network topology in the class tree structure

In distance education can be used as a dedicated network and a worldwide global network Internet.

As network training are linked to one tuition in a tree structure, so the formation of network learning algorithms can use the minimum spanning tree. There are exact and heuristic algorithms that can solve this problem. The most common among the exact algorithms are Prima, Kruskal, Charm, Ysau-Williams and Fogel [1,3].

To solve this problem (the organization computer network training) to the input bound to submit an undirected graph G = (V, E), where V – the number of vertices and E – the number of edges (a set of links), W (and, j) – weight edges, shows the cost of connection and communication and j. Need to find acyclic subset that connects all vertices, the one whose total weight is minimal.

Computational complexity of algorithms (time) depends on the method of storage nodes. If the graph represented as adjacency matrix, the time of the algorithm Prima will be O(V2). The theoretical time of Kruskal algorithm depends on the time and sort of edges is O(E * lg (V)). Using fibonach pyramids Prima algorithm can be accelerated to O (E + V * lg (V)), which is quite a significant acceleration in |V| << |E|.

For practical problem solving large dimensions of the order of the usual traditional methods of synthesis of network topology is not suitable, there is a problem – the development of efficient approximate methods.

Among the many heuristic algorithms can be divided into two classes. One is based on the algorithm of finding the minimum charging tree (MST (Minimum Spanning Tree). Another class is based on the classical approach of finding the shortest route – « from point to point » algorithm or construction wood (Forest Build Tree – FBT).

Two algorithms, KMB (Kou, Markowsky, Berman) and RS (Rayward-Smith) are known as the most common in these two classes [6].

To heuristic algorithms include genetic algorithms and ant colony algorithms.

Comparative analysis of algorithms performed in «System design and optimization of network topology» . As a software development environment was selected environment Embarcadero ® RAD Studio 2010 version of Embarcadero Technologies 14.0, Inc.. For visualization system used on the workstation AMD Athlon X2 (CPU 2200 MHz, RAM 2048 Mb).

The work is driven evaluation of algorithms for synthesis of network topology in the class tree structure from a distance (total length of pulling trees) and computation time and computation time increase with increasing number of vertices in the graph.

Based on the results, we can conclude that a small number of nodes spread over more precise algorithms apply profitable. The best performance among the exact algorithm gives Prima.

With increasing number of vertices, computing time increases, so heuristic methods can solve problems at the right time calculation. The two main criteria to evaluate these algorithms is the speed of convergence and the proximity of the resulting solution to the optimal or a better solution.

Both KMB and RS algorithms have lower performance than MST and FBT but give solutions closer to optimal.

When implementing the algorithm of construction of ant colonies important indicator on which the computational complexity is the choice of search strategies.

Reseach of genetic algorithm shows that to reduce the computation time should allocate area source data for creating the initial population.

Conclusions

There are many algorithms synthesis and optimization of network topology in the class tree structure. Depending on the method of work time each one is different.

As part of the research carried:

1. Overview of exact and heuristic algorithms for solving the problem synthesis of network topology in the class tree structure

2. Comparing the results of exact and heuristic algorithms, the conclusion about the effectiveness

3. Analysis algorithms work Prima, Kruskal, KMB, RS, MST and FBT

4. The principles of action and time algorithms for ant colony and genetic algorithms

5. Compared to the work of the above algorithms, the conclusion about the effectiveness.

Further investigation focused on the following aspects:

    1. Selection of the optimal scheme synthesis of network topology in the class tree structure
    2. Software implementation of the chosen scheme
    3. Analysis of the software

In writing this essay master's work is not completed. Final completion: December 2012. Full text of the and materials on the topic can be obtained from the author or his head after that date.

References

  1. Кормен Т. Аглоритмы: построение и анализ, 2-е издание. Пер. с англ. / Т.Кормен, Ч.Лейзерсон, Р.Ривест. – М. : Издательский дом «Вильямс», 2005. – 1296 с.
  2. Кристофидес Н. Теория графов. Алгоритмический подход [Електронний ресурс]. – Режим доступу: http://mirknig.com/knigi/nauka_ucheba/1529-teorija_grafov.html
  3. Ахо Альфред В. Структуры данных и алгоритмы / Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман –  М. : Издательский дом «Вильямс», 2003. – 384 с.
  4. Лекции по курсу «Компьютерная дискретная математика» [Електронний ресурс]. – Режим доступу: http://itlcvs.wordpress.com/2011/09/06/лекции-по-курсу-компьютерная-дискрет/
  5. Бондаренко М. Ф., Білоус Н. В., Руткас А. Г. Комп'ютерна дискретна математика [Електронний ресурс]. – Режим доступу: http://pikkalo.com/2700-kompyuterna-diskretna-matematika.html
  6. Guo-Quing Hu. Forest build tree algorithms for multiple destinations // The Potential. №3, 1998.- с. 13-16.
  7. Алексеев В.Е. Графы. Модели вычислений. Структуры данных [Електронний ресурс]. – Режим доступу: http://mirknig.com/knigi/estesstv_nauki/1181451717-grafy-modeli-vychisleniy-struktury-dannyh.html
  8. Топп У. Структуры данных в С++ / У. Топп, У. Форд; [пер. с англ.] – М.: ЗАО «Издательство БИНОМ», 1999. – 816 с.
  9. Мартин Дж. Планирование развития автоматизированных систем /   Мартин Дж. – М. : Финансы и статистика, 1984. – 196 с.
  10. Трамбле Ж., Соренсон П. Введение в структуры данных [Електронний ресурс]. – Режим доступу: http://mirknig.com/knigi/os_bd/1181478197-vvedenie-v-struktury-dannyh.html
  11. Руденко В.Д. Курс информатики / В.Д. Руденко, А.М. Макарчук, М.А. Патланжоглу. – К. : Феникс, 2000. – С. 230-235.
  12. Татт У. Теория графов [Електронний ресурс]. – Режим доступу: http://www.kodges.ru/15890-teorija-grafov.html
  13. Вирт Н. Алгоритмы и структуры данных / Вирт Н. – [2-е изд.] – СПб.: Невский Диалект, 2001. – 352 с.
  14. Седжвик Р. Фундаментальные алгоритмы на С++. Алгоритмы на графах / Седжвик Р. – СПб.: ООО «ДиаСофтЮП», 2002 – 496 с.
  15. Субботін С.О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / С.О. Субботін, А.О. Олійник, О.О. Олійник. – Запоріжжя: ЗНТУ, 2009. – 375 с.
  16. Зингеренко Ю. Основы построения телекоммуникационных систем и сетей [Електронний ресурс]. – Режим доступу: http://mirknig.com/knigi/seti/1181446491-osnovy-postroeniya-telekommunikacionnyh-sistem-i-setey.html
  17. Седжвик Р. Фундаментальные алгоритмы на С++. Анализ. Структуры данных. Сортировка. Поиск. / Седжвик Р. – К.: «ДиаСофт», 2001 – 688 с.
  18. Свами М., Тхуласираман К. Графы, сети, алгоритмы [Електронний ресурс]. – Режим доступу: http://www.kodges.ru/131137-grafy-seti-algoritmy.html
  19. Tree data structure [Електронний ресурс]. – Режим доступу: http://ideainfo.8m.com/
  20. Глебовский А.Ю. Исследование и разработка методов и средств повышения структурной и функциональной устойчивости научных и университетских сетей [Електронний ресурс]. – Режим доступу: http://www.dissercat.com/content/issledovanie-i-razrabotka-metodov-i-sredstv-povysheniya-strukturnoi-i-funktsionalnoi-ustoic