雷欽隆臺灣大學：電機工程學研究所黃韻穎Huang, Yun-YinYun-YinHuang2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53325由於Internet不斷的擴張與發展，網路路由器不再只需做單純的封包傳遞，而逐漸需要支援更上層的網路服務。因此路由器功能的延展也漸漸成為一個重要的課題。一般來說，路由器的延展可以分為兩個方向：scale-up與scale-out。前者主要是利用改變路由器的軟硬體架構來提升路由器的效能；而後者則是利用分散式的路由架構來達到提升的目的。 在這篇論文中，將提供一個可以調節與擴充的叢集式封包處理架構。我們利用透明式橋接器的第二層MAC位址自動學習機制來達到分流的目標。每一個路由器在收到原來的ARP request後，由一個預先定義的雜湊函式決定該由何者進一步的回應。為了進一步的流量平衡，路由器在回應的同時利用雜湊值計算出對應的虛擬MAC。 然而，很難找到一個雜湊函數可以適當地分配任何的網路狀況。因此，為了解決此類不公平的情形，我們利用路由器間的訊息傳遞來達到進一步的流量平衡。路由器藉由分析本身及周遭兩個路由器的統計資訊來重新分配流量，並利用交換機的自動學習機制來達到流量平衡。 在論文的最後我們利用Smartbits來產生特定的網路流量，並評估我們的演算法是否可以平均分配流量到此叢集式路由架構中。由實驗的結果可以了解，我們的架構對於任意的網路流量均可以達到相當好的流量平衡。在之後的實驗我們也分析了架構中可調節的幾個參數對於系統平衡的影響結果。Several novel network services are proposed in these years. Routers are expected to perform more works than before to face the trend. The speeding network transmission aggregates the performance requirement problem of the router. A traditional router no longer affords to these expectations, so router enhancement becomes an important issue today. Methods used to extend router performance can be separated into two dimensions: scale-up which improves the hardware architecture of the router; and scale-out which uses cluster-based architecture. In this thesis, we provide an adaptive and scalable scheme for packet processing based on clustered-router architecture. We use MAC address automatic learning feature on the bridge to dispatch network traffics to the routers. Each router receives the original ARP requests, and processes the broadcast frame with same hashing function. Only one and exactly one router would response the request and then sends the corresponding MAC address back to the sender. However, it is difficult to find a hash function that can fairly separate all kinds of traffic patterns. To solve the unfairness, we use interconnection mechanism between each router to adjust the traffic distribution. Router can shape the traffic distribution based on the statistics from its neighbors and itself. It then updates its responsible area by sending specific frames for switch learning to achieve load balancing. We use Smartbits to generate specific traffic pattern, and measure how fair our dispatching algorithm is. The results show that our packet-processing scheme provides good load balance. We then do some experiment to measure the control factors of our scheme. The experiment reveals that the interval for how long to justify traffic load is one of the major factors for the performance of our dispatching scheme.Abstract II Tables of Content III List of Tables VII List of Figures VIII 1. Introduction 1 1.1. Motivation and Objectives 1 1.2. System Design Overview 2 1.3. Thesis Architecture 3 2. Related Works 4 2.1. Linux Netfilter/Iptables Project 4 2.1.1. Introduction 4 2.1.2. Netfilter Architecture 6 2.1.3. Packet filtering in Netfilter 7 2.1.4. NAT in Netfitler 8 2.2. MIT Click Modular Router Project 9 2.2.1. Click Router Architecture 9 2.2.1.1. Push and Pull Connections 10 2.2.1.2. Flow-Based Router Context 11 2.2.2. Click IP Router 12 2.3. Princeton Extensible Router Project 16 2.3.1. Extensible Router Architecture 16 2.3.2. Router Abstraction 17 2.3.3. Distributed Router Operating System 19 2.3.3.1. Internal Packet Routing 19 2.4. Linux Virtual Server Project (LVS) 20 2.4.1. Architecture of LVS 21 2.4.2. LVS/NAT 22 2.4.3. LVS/TUN 24 2.4.4. LVS/DR 26 2.4.5. Constraints of LVS 28 3. Load Balancing in Clustered-Router Architecture 30 3.1. Overview 30 3.2. Local Processing 31 3.2.1. Packet Processing 31 3.2.2. Statistics 32 3.3. Interconnection Scheme 32 3.3.1. Load Balancing Scheme 33 3.3.2. Traffic Pattern Analysis 35 4. Implementation 38 4.1. Dispatch Algorithm Using ARP Protocol 38 4.1.1. ARP Protocol 38 4.1.2. Address Table Generation in Transparent Bridge 40 4.1.3. Traffic Dispatching Scheme 40 4.2. System Implementation 42 4.2.1. Statistic Module/Daemon 43 4.2.2. Decision Making Daemon 43 4.2.3. Execution Daemon 43 4.2.4. Regular Updating Daemon 43 4.3. Implementation Details of Kernel Modules 44 4.3.1. Building Standard Linux Kernel Module 44 4.3.2. ARP Request/Reply Parsing 45 4.3.3. Netfilter/ Iptables Modules 46 4.3.3.1. Iptables Match Modules 47 4.3.3.2. Arptables Target Modules 50 4.3.4. Statistic Modules 52 4.4. Implementation Details of User-space Daemons 53 4.4.1. Statistic Daemon 53 4.4.2. Decision Making Daemon 53 4.4.3. Execution Daemon 54 4.4.4. Regular Daemon 55 4.5. Implementation Details of Procfs (/proc File System) 56 5. Performance Analysis 58 5.1. Testing Environment 58 5.1.1. Blade Server 58 5.1.2. Performance Metrics 59 5.1.3. Control Factors for Load Balancing 60 5.2. Performance Analysis 61 5.2.1. Performance Analysis with Random Traffic Pattern 61 5.2.2. Performance Analysis with Static Traffic Pattern 63 5.2.3. Performance Analysis of Traffic Differentiation Threshold 65 5.2.4. Performance Analysis of Decision Making Interval 66 5.2.5. Performance Analysis of Statistic Collection Interval 69 6. Discussion and Conclusion 72 6.1. Discussion and Enhancement 72 6.2. Future Works 74 Reference 75en-US可擴充叢集式路由架構封包處理架構流量平衡流量分配ARP可調節packet processingadaptivetraffic dispatchingload balancingclustered-router architecturescalablethesis