頁籤選單縮合
題名 | A New Goniometry-based Routing Algorithm for ATM Networks=基於測角術之新穎且有效的非同步傳輸模式網路路由安排方法 |
---|---|
作者 | 王國禎; 吳俊昌; Wang, Kuochen; Wu, Chung-chang; |
期刊 | Journal of the Chinese Institute of Electrical Engineering |
出版日期 | 19990200 |
卷期 | 6:1 1999.02[民88.02] |
頁次 | 頁51-61 |
分類號 | 448.6 |
語文 | eng |
關鍵詞 | 非同步傳輸模式網路; 有效頻寬; 基於測角術; 服務品質; 路由安排演算法; ATM network; Effective bandwidth; Goniometry-based; QOS; Routing algorithm; |
中文摘要 | 在本篇論文中,我們針對非同步傳輸模式網路提出了一個以測角術為基礎之新穎 且有效的分散式路由安排方法。我們採用一般性的網路拓樸型態,其每個節點皆有處理資源 分配及呼叫允許控制的能力。非同步傳輸模式網路需要確保使用者的服務品質。為滿足非同 步傳輸模式網路的高速需求,我們根據起點與終點的連線及起點與每一相連節點的連線之間 夾角,發展出一個快速的啟發式路由安排方法。我們的演算法以跳躍方式嘗試最有可能的路 徑(最小夾角)來對每一對起點與終點找到一條合適路徑,並且此路徑能保證使用者要求的 服務品質。如此可避免搜尋幾乎不可能的連線及節點,因而可大量節省路由安排時間。本篇 論文最大的貢獻在於設計一個新穎且需較少呼叫建立時間的非同步傳輸模式網路路由安排演 算法。它的時間複雜度為 O(N log N),其中 N 是網路節點的數目。我們以模擬的方式評估 所提出的方法。模擬結果顯示我們提出的路由安排演算法比最著名且複雜度為 O(N �� ) 的 Djkstra 演算法(含服務品質限制)的平均呼叫建立時間減少 40% 到 90%, 而路由成本和 呼叫被拒絕比率都只比 Dijkstra 的演法略高 0% 到 7%。 |
英文摘要 | In this paper, we present a novel and efficient distributed ATM (Asynchronous Transfer Mode ) network routing algorithm based on goniometry. A general network topology model is used and each node has the capability of handling resource allocation and CAC (call admission control) functions. An ATM network is supposed to provide guaranteed users' QOS (quality of service). To meet the high speed requirement of the ATM network, we develop a fast heuristic routing method based on the intersection angle between the line connecting source and destination and each outgoing edge which is connected to the source. Our algorithm tries the most desirable way (the minimum intersection angle) hop by hop to find a routing path for each source and destination pair and the path that meets the users' QOS. Consequently, routing time is reduced significantly by avoiding the search for impossible edges and nodes. The main contribution of this paper is in designing a new ATM routing algorithm with low call setup time, and the complexity of our algorithm is O(N log N), where N is the number of nodes in the network. The algorithm has been simulated to analyze the figures of merit. Simulation results show that our algorithm reduces the call setup time by 40% to 90% of the most known Dijkstra's algorithm with the QOS constraint, which has the complexity of O(N �� ). The routing cost and the call blocking rate of our algorithm are only slightly larger (0% to 7%) than those of Dijkstra's algorithm with the QOS constraint, respectively. |
本系統之摘要資訊系依該期刊論文摘要之資訊為主。