光突發性交換網路架構上使用頻繁樣本樹(Burst Frequent-Pattern Tree)進行路徑繞送規劃

Burst Frequent-Pattern Tree Routing Planning in Optical Burst Switching Networks

徐任德(Zen-Der Shyu)

指導教授 ： 黃依賢 博士

元智大學/資訊學院/資訊工程學系/碩士(2004年)

摘要

隨著網路上語音、影像等多媒體資料量不斷的增加，如何使資料的傳輸能夠更安全快速的送達目的端，便顯得更加的重要。如此瞬間大量的，且無法預估的資料傳輸，若是沒有事先經過規劃而讓傳送的過程中產生斷訊或是嚴重延遲的結果，勢必影響到整體網路的使用效能。為了提升資料的傳送成功機率，如何在資料送達目的端之前能有妥善的規劃，就成了一個重要的議題。因此，為了要找出網路拓撲(Network topology)合適的繞送路徑，我們使用資料探勘(Data mining)，結合數理統計、人工智慧等相關技術，進行這方面的研究。本篇論文採用具有多重協定標籤交換(Multi Protocol Label Switching, MPLS)特性的標籤光突發性封包交換(Labeled Optical Burst Switching, LOBS)網路架構，提出Burst Frequent-Pattern Tree(BFP-tree)的演算法，藉由探勘歷史繞送路徑資料庫修正繞送路徑，以達到機器學習的目的，並作為日後網路繞送決策的規劃。我們使用實際的網路拓樸(NSFNet, USANet)，利用關聯性規則(Association Rule)找尋適合的繞送路徑。在過程中使用不同的統計分配產生網路節點的Blocking probability，以驗證BFP-tree方法的可行性，結果令人滿意。本篇論文可使用在檢視繞送路徑演算法的優劣，以此作為網路管理決策者對於繞送路徑演算法的選擇，以及投資網路硬體線路設備時的依據。

關鍵字

網路拓撲 ； 資料探勘 ； 多重協定標籤交換 ； 標籤光突發性封包交換 ； 關聯規則

並列摘要

The last few years have seen explosive growth in Internet Protocol traffic. Transmitting data quickly and safely is more important than ever. One of the critical design issues in the utilization of networks is careful planning to minimize burst dropping resulting from resource contention. The provision of suitable planning before metadata are sent is critical to improving the rate of successful transmission. Therefore, this study applies data mining which combines artificial intelligence and statistics, to determine a suitable routing path in Network topology. The labeled optical burst switching network structure with MPLS characteristics is used to propose the Burst Frequent-Pattern Tree (BFP-Tree) algorithm. The BFP-Tree algorithm revises the routing path within the database of historical records to enable the purpose of machine learning. The Association Rule is applied to elucidate suitable routing paths in the real-life Network topologies (NSFNet, USANet). Various statistical distributions are adopted to generate the blocking probability of the network to verify the feasibility of the BFP-tree algorithm. The results are more satisfactory than those obtained by the Apriori algorithm. Simulation results show that the successful rate of routing paths obtained by the BFP-tree algorithm effectively converge to the upper bounds (best cases). The results are excellent references to be used by network management policy-makers in selecting routing paths. Moreover, they can be a basis for investing in network hardware circuit equipment.

並列關鍵字

Network topology ； data mining ； MPLS ； labeled optical burst switching ； association rule

參考文獻

[2]C. Qiao, “Labeled optical burst switching for IP-over-WDM integration”, IEEE Communications Magazine, Volume: 38, Issue: 9, pp. 104-114, September 2000.

[3]J. Y. Wei and R. I. McFarland, “Just-in-time signaling for WDM optical burst switching networks”, Journal of Lightwave Technology, 18(12) : 2019 - 2037, December 2000.

[6]I-Shyan Hwang and Chin-Chiung Hsieh, “Association Rules Based Burst Routing Algorithm Network Management in Optical Burst Switching Networks”, Active Networking Workshop 2004, pages 163-170, September 2004.

[9]R. Agrawal and R. Srikant, “Fast algorithms for mining association rules”, Proceedings of the 20th VLDB Conference, pp. 478-499, September 1994.

[10]Han, J., Pei, J., Yin, Y., and Mao, R. “Mining Frequent Patterns without Candidate Generation: A Frequent-pattern Tree Approach”. Data Mining and Knowledge Discovery, 8, 53-57, 2004.