Performance Improvements of Ethernet Using Multiple Spanning Trees

乙太網路使用快速擴展樹協定建立邏輯拓樸，以避免廣播風暴問題。此邏輯拓樸為一擴展樹，擴展樹可以在交換機和物理鏈結加入或移除/故障時，自我配置與自我恢復，然而快速擴展樹協定的建樹與故障恢復機制影響了封包轉發的效能。快速擴展樹協定所使用的鏈結故障恢復機制，會因其復原時間過長而導致封包傳輸中斷的情形。過去研究以多重擴展樹協定建立多重替代樹，避免發生鏈結故障後傳輸中斷的問題。然而，標準協定中的根交換機選擇機制使用於多重擴展樹時，會造成多重擴展樹皆選擇同一台交換機為其樹之根節點。因此，過去這些研究可能會因根節點相同，導致所建立的多重替代樹也相似或相同。當一鏈結故障時，所有或大部份的多重替代樹都會受到影響。我們基於乙太網路所提出的拓樸可適性多重擴展樹機制，能避免單一鏈結故障導致多重替代樹受影響之問題。此外，封包在多重替代樹間傳送時，通常會有較長的傳輸路徑。鑒於此，我們在多重替代樹之間建立捷徑路徑以縮短封包傳輸之路徑長度。在擴展樹的建立過程中，根交換機為媒體存取控制位址最小值之交換機。因此，網路中的任何交換機都可能成為根交換機。當任意一對交換機透過擴展樹進行通信時，其最長傳輸路徑之長度，在最壞情況下是物理拓撲直徑的兩倍。為了解決根交換機的位置問題，我們提出了最小深度擴展樹協定尋找網路中心節點，進而建立最小深度擴展樹。通過此協定可以縮短交換機之間的傳輸路徑長度。在乙太網路中，故障恢復和根交換機位置影響網路的整體效能。根據實驗顯示，我們提出的拓樸可適性多重擴展樹機制和最小深度擴展樹協定可以有效提高乙太網路的可靠性和可擴展性。Ethernet exploits the rapid spanning tree protocol (RSTP) to build a logical topology for avoiding the problem of broadcast storm. Although the logical topology can be self-configured and self-recovered when a physical link or a switch of the spanning tree joins or fails/leaves, the performance of frame forwarding is effected by the construction and recovery of RSTP. The standard mechanisms of link-failure recovery in RSTP may cause interruptions of data transmission because of long recovery time. Several previous approaches construct multiple alternative trees avoid such interruptions caused by single or multiple failed links based on multiple spanning tree protocol (MSTP). However, the prototypical protocol of standard of root election would result in the same root switch for different spanning trees. Hence, the alternative trees may become invalid if a failed link appears in more than one spanning tree. Our scheme, failure-adaptive spanning trees (FAST), avoids simultaneous faults of multiple spanning trees by incorporating a new approach to electing an appropriate root switch for each spanning tree. FAST also employs active links of alternative spanning trees for data transmission. The paths of different spanning trees can thus act as shortcuts to shorten frame paths. When RSTP builds a spanning tree, the root switch is determined by the lowest MAC address. Therefore, the elected root switch could be any switch in the network. When an arbitrary pair of switches communicates via the built spanning tree, the longest path length is two times the diameter of the physical topology in the worst case. In order to deal with the location problem of root switch, we propose minimum-depth spanning tree protocol (MDSTP) to find the center node and build a minimum-depth spanning tree for an Ethernet network. With our scheme, the locations of root switches can be improved to shorten the longest path length between leaf switches. Failure recovery and the location of root switch affect critical performance in Ethernet networks. The experimental results demonstrate that the proposed FAST and MDSTP can improve both reliability and scalability of Ethernet.摘要 i Abstract ii Chapter 1 Introduction 1 1.1 Background 1 1.2 Motivation and Objective 2 1.3 Thesis Organization 3 Chapter 2 Failure-Adaptive Spanning Trees 4 2.1 Introduction 4 2.2 Legacy Schemes for Failure Recovery 4 2.2.1 Single Failure Recovery Schemes 4 2.2.2 Multiple Failure Recovery Schemes 5 2.3 The Proposed Scheme 6 2.3.1 State-based Root Election in MSTP 6 2.3.2 Resilient Frame Forwarding 8 2.3.3 Shortcut Forwarding 10 2.3.4 Implementation 15 2.4 Evaluation 18 2.4.1 Network Throughput 19 2.4.2 Load Balancing 22 2.4.3 Path Length 25 2.5 Summary 26 Chapter 3 Minimum Depth Spanning Tree Protocol 27 3.1 Introduction 27 3.2 RSTP Issues in Ethernet 28 3.3 Mathematics Issues of Network Diameter and Radius 29 3.3.1 Minimum Spanning Trees in Mathematics 29 3.3.2 Camille Jordan’s Theorem 30 3.4 The Proposed Algorithm 32 3.4.1 Assumptions 33 3.4.2 Applying Camille Jordan’s Theorem in Ethernet 34 3.4.3 Probing Center Nodes 36 3.4.4 Eliminating Center Nodes 37 3.4.5 Summary of the Proposed Algorithm 39 3.5 Analysis of the Proposed Algorithm 40 3.5.1 Effectiveness of Acquiring Center Nodes by Using the Jordan’s Theorem 40 3.5.2 Difference Between Calculated and Accurate Lengths of P_R 42 3.5.3 False Negative Caused by Intersection 43 3.6 The Proposed Spanning-Tree Protocol for Ethernet 44 3.6.1 The Prerequisites of the Proposed Protocol 44 3.6.2 The Proposed Protocol 48 3.6.3 Discussion 50 3.7 Evaluation 51 3.7.1 The Accuracy of Calculated P_D 51 3.7.2 Intersection 52 3.7.3 The Number of VLANs 54 3.7.4 Tree Depth 56 3.7.5 Path Length 57 3.7.6 The Traffic Load for Building an MDST 59 3.7.7 The Building Time of MDST 60 3.8 Summary 61 Chapter 4 Conclusion 62 References 63 Appendix A MDSTP State Machines 6