網路拓樸顯示問題

Abstract

網路系統特續快速的成長且日趨複雜，使得有效的網路管理系統更形重要。網路拓樸顯示服務（Network Topology Display Service）是建構管理（configuration mangement）的重要功能之一。大多數既存的網路管理系統，不是藉著以X-視窗系統（X-Window System）為基礎的繪圖工具（drawing tool），就是藉著自動偵測並繪圖程序（automatic detection and drawing procedure），來建立網路管理圖形。當網路系統變得龐大且複雜時，使用者必須花許多時間調整網路設備圖像（ICON）的位置，才能得到一個美觀的網路管理圖形。如何得到一個對稱的網路拓樸顯示圖表便是網路拓樸顯示問題（NTDP）。通常，NTDP由兩個步驟來解決。第一個步驟是「次網路『圖形內部』排圖理論」（"Intra-subnetwork" algorithm），在此步驟中，針對每一種次網路形態，如Ring、Bus等，有不同的排圖方法。第二個步驟是「次網路『圖形之間』排圖理論」（"Inter-subnetworks" algorithm），目的是調整次網路之間的相對位置。會有人提出以適探法（Heuristic Method）來解決次網路「圖形之間」的顯示問題，但當問題龐大且複雜時，應用此法有困難。 本篇論文的目的即在提出一種有效率及效果的圖形之間排圖演算法。在本研究中，提出修正後之適探法（Modified Heuristic method）、作業研究方法（Operations Research method）及類神經網路法（Neural Network method）三種演算法來解決此問題。在比較分析過四種方法的效果、執行速度、優缺點之後，我們的結論是當次網路個數小時（＜50），以修正後之適探法做為次網路「圖形之間」的排圖演算法，而當次網路個數多時（＞50），則以作業研究方法做為次網路「圖形之間」的排圖演算法，因為它在個數多時花費的時間不大且可達到較好的效果。

Since networks continue to grow at a rapid pace and with greater complexity, to have an efficient network management system becomes more important than ever. The network topology display service is one of the essential services that Configuration Management provides. For most existing network management systems, this service is supported by either an X-window based drawing tool or an automatic detection and drawing procedure. When the network grows larger and becomes more complicate, user must spend a great deal of time in adjusting network devices’ ICON, so as to get a good graphic layout. How to acquire a symmetric network topology display is called the Network Topology Display Problem (NTDP). Usually, NTDP is solved by a two-step procedure. In the first step, Intra-subnetwork algorithms are developed according to the types of the subnetwork. such as Ring、Bus etc.. In the second step, the inter-subnetworks algorithm is used to adjust the relative position between subnetworks. A Heuristic method had been proposed to handle the inter-subnetworks display problem. However, this method has difficulties in solving large size problems. The purpose of this paper is to find an efficient and effectiveness inter-subnetworks algorithm. Three methods, Modified Heuristic Method、Operations Research Method, and Neural Network Methods, are proposed Computational results obtained from these four methods are analyzed with respect to their effectiveness, running speed, and complexity. From the analysis, the following conclusions can be drawn. The Modified Heuristic Method performs best when the number of subnetworks is less than 50. However, once the number of subnetworks is over 50, the Operations Research Method has the best result in both running time and effectiveness.