利用動態叢集技術建構兼具高效能及自我調適特性之網路系統

Design and Implementation of High-Performance and Reconfigurable Network Systems with Adaptive Clustering

蔡攀龍(Pan-Lung Tsai)

指導教授 ： 雷欽隆

國立臺灣大學/電機資訊學院/電機工程學研究所/博士(2006年)

https://doi.org/10.6342/NTU.2006.00718

摘要

隨著通訊技術的進步，電腦與通訊網路的可用頻寬持續地以倍數成長，而網際網路的興起也帶動了各類型網路應用程式的發明與演進，使得現今的網路時時刻刻都充滿著由各式各樣網路應用程式所產生的大量資料封包。為了避免成為網路資料傳輸的效能瓶頸，負責處理封包轉送的網路系統在設計與製作上必須採用更先進、執行效率更高的軟、硬體架構與工作模式，才能夠以符合期望的處理效能完成高速封包轉送的任務。更精確地說，對於高效能網路系統的需求主要是由兩項因素所驅動：新型通訊協定與網路服務的產生使得處於資料傳輸路徑上的網路系統必須針對每個封包進行更複雜的檢驗與後續處理，而網路可用頻寬的提昇則使得網路系統在單位時間內必須處理的封包數量不斷地增加；兩相夾擊的結果導致網路系統必須在更少的時間之內完成更多的工作。在這樣的情況下，對於高效能網路系統的需求也自然而然地與日俱增。
叢集式的架構對於網路系統的設計與製作來說是一大突破。如果能夠使用得宜，藉由特別設計的方法將封包處理的工作均勻地分配給構成同一個叢集的數個網路裝置來加以執行，整體網路系統的封包處理速率就能夠大幅提昇。叢集式架構除了具有集結多重網路裝置的處理效能、以成本效益較高的方式實現高效能網路系統的特性之外，由於構成叢集的網路裝置在彼此之間仍保有一定程度的獨立性，因此，這樣的架構也能夠很容易地支援容錯備援、動態調整等等的進階功能。
本篇論文提出一個能夠被用來製作高效能網路系統的動態叢集技術，同時也探討隱含在叢集式架構背後的網路流量分配問題。本篇論文所描述的動態叢集技術採用完全對稱的分散式系統架構，藉此避免由專屬網路流量分配器可能造成的效能瓶頸與單一弱點問題，並且利用獨特的位址解析方法在協同工作的數個網路裝置之間進行工作量的分配與重分配。在理論分析方面，本篇論文正式地定義「多重裝置網路流量分配問題」，同時也提出解決這個問題的演算法以及實驗結果。此外，本篇論文也包含了動態叢集技術與相關理論分析結果被應用在網路系統實際建置的設計與製作過程，以高效能虛擬私用網路閘道裝置與高效能頻寬限制裝置兩種不同的形式呈現。上述兩項實作的成果皆通過網路模擬裝置的效能測試，分別驗證動態叢集技術對於邊緣網路裝置與透通式網路裝置的適用性及其自我調適能力，也更進一步地證實了本篇論文所提出的動態叢集技術的確為兼具高效能及自我調適特性網路系統的建構方式提供了嶄新而有效的選擇。

關鍵字

Cluster Computing ； Network-System Design ； Distributed System ； Load Balancing ； Fault Tolerance ； Optimization Problem ； Virtual Private Network ； Bandwidth Management

並列摘要

The advancement of communication technologies and optical components has led to a data rate beyond tens of gigabits per second in current computer and communication networks. As there are numerous network packets traversing the Internet at any time instant, modern network systems failing to process incoming packets in a high speed are likely to become the performance bottleneck of their respective networking environment. Even at network edges, network systems are expected to finish the processing of each packet in few microseconds or less. On the other hand, the emergence of new communication protocols and network applications keeps increasing the complexity of various packet-processing functions employed by a wide range of network systems. These two driving factors together stimulate the demands for high-performance network systems.
Clustering is one of the approaches proposed to satisfy such demands, and it can be viewed as an architectural improvement to network-system designs. When used appropriately, clustering schemes offer scalable and cost-effective solutions for building high-performance network systems. In addition, the loosely coupled nature and the inherent redundancy of the clustered network devices grant clustering schemes the potentials to incorporate advanced features such as dynamic expansion and fault tolerance, making clustering an even more promising approach to the construction of future network systems.
In this dissertation, we investigate the theoretical aspects of the underlying traffic-distribution problem behind clustering and propose an adaptive clustering scheme for building high-performance network systems. The proposed scheme makes use of a fully decentralized system architecture and is able to deal with the dynamic nature of network traffic by redistributing workload over the clustered network devices on a periodic basis. The basic version of the proposed adaptive clustering scheme achieves the goal of load balancing with a heuristic-based technique, and is further enhanced with the support for both run-time cluster expansion and fault tolerance. Another load-balancing technique based on the key findings of the theoretical analysis is also developed as an alternative. It takes advantage of global workload information and may be used to replace the heuristic-based one for reducing time to reach the balanced state.
The proposed adaptive clustering scheme is initially designed for clusters of edge devices and then extended to support clusters of in-line devices. To verify the applicability and practicability of the proposed scheme, we create a high-performance and reconfigurable security-gateway cluster and a high-performance and reconfigurable bandwidth-controller cluster as two real-world examples. The implementations are based on our custom Linux distribution and take care of not only general considerations for building network systems but also issues specific to virtual private networks and bandwidth management, respectively. We further conduct a series of tests to explore the behavioral characteristics of these clusters with a world-recognized test equipment. The results of performance evaluation confirm that the proposed adaptive clustering scheme is highly scalable and provides a practical solution for building high-performance and reconfigurable network systems with little clustering overhead.

並列關鍵字

叢集式運算 ； 網路系統設計 ； 分散式系統 ； 負載平衡 ； 容錯 ； 最佳化問題 ； 虛擬私用網路 ； 頻寬管理

參考文獻

[5] Azer Bestavros, Mark Crovella, Jun Liu, and David Martin, "Distributed Packet Rewriting and Its Application to Scalable Server Architectures," Proceedings of 6th IEEE International Conference on Network Protocols (ICNP '98), pp. 290-297, October 1998.

[10] Alberto Caprara, Hans Kellerer, and Ulrich Pferschy, "The Multiple Subset Sum Problem," SIAM Journal on Optimization, Vol. 11, No. 2, pp. 308-319, September 2000.

[11] Valeria Cardellini, Emiliano Casalicchio, Michele Colajanni, and Philip S. Yu, "The State of the Art in Locally Distributed Web-Server Systems," ACM Computing Surveys (CSUR), Vo. 34, No. 2, pp. 263-311, June 2002.

[13] Marco Carugi and Jeremy De Clercq, "Virtual Private Network Services: Scenarios, Requirements and Architectural Constructs from a Standardization Perspective," IEEE Communications Magazine, Vol. 42, No. 6, pp. 116-122, June 2004.

[14] Thomas L. Casavant and Jon G. Kuhl, "A Taxonomy of Scheduling in General-Purpose Distributed Computing Systems," IEEE Transactions on Software Engineering, Vol. 14, No. 2, pp. 141-154, February 1988.