A Dynamic Method of Constructing MST Based on OpenFlow Protocol

Haike Liu, Jilin Li, Kai YangInternational Journal of Computer and Communication Engineering 2016 · DOI

Abstract

Traditional Layer 2 networks rely on the Spanning Tree Protocol (STP) to prevent loops, but this approach suffers from slow convergence and poor resource utilization. Specifically, static forwarding topologies cannot adapt to real-time traffic changes, often leading to bottlenecks at root nodes. This paper proposes a dynamic construction method for the Minimum Spanning Tree (MST) within a Software Defined Networking (SDN) architecture using the OpenFlow protocol. By monitoring network traffic distribution, the controller dynamically adjusts the no-loop forwarding topology to achieve global load balancing. Simulation results demonstrate that this method significantly improves network stability, reducing delay jitter and packet loss ratios.

Introduction

In traditional Ethernet environments, the Spanning Tree Protocol (STP) is essential for maintaining a loop-free topology. However, STP is fundamentally static; once the tree is calculated based on fixed link costs, it remains unchanged regardless of traffic fluctuations. This often results in "root node bottlenecks," where switches near the root carry excessive loads while alternative paths remain idle. To address this, we propose leveraging the centralized control of SDN to transform the MST from a static safety mechanism into a dynamic load-balancing tool.

Proposed Methodology

The system architecture utilizes the OpenFlow protocol to bridge the gap between the control plane and the physical network. The process involves three primary stages: traffic monitoring, weighted node modeling, and topology recalculation.

System architecture and workflow for dynamic MST construction.

Traffic Monitoring and Node Weighting

The OpenFlow controller periodically polls switches for traffic statistics. Unlike traditional MST algorithms that only consider link costs (e.g., bandwidth), our model introduces node weights. We define "transit traffic" as the total data handled by a switch minus the traffic destined for its local network. This metric identifies switches that are becoming pass-through bottlenecks.

Modified Prim’s Algorithm

Finding an MST with weighted nodes is an NP-hard problem. To solve this efficiently, we employ an improved version of Prim’s algorithm. We calculate an "equivalent edge weight" that integrates physical link costs with the real-time traffic weights of the connected nodes. When the controller detects congestion, it triggers a recalculation and pushes new flow rules to the switches to reconfigure the topology.

Experimental Setup

The method was validated using a simulation environment built with Mininet and Open vSwitch (OVS), managed by a POX controller. The testbed consisted of seven OpenFlow switches (A-G) and seven hosts. To simulate congestion, multiple UDP flows were introduced with bandwidth requirements that exceeded the capacity of primary links in a static configuration.

Key Results and Discussion

The dynamic MST method successfully identified and mitigated congestion. In the initial static topology, the link between nodes A and B reached its capacity, causing high packet loss. The system automatically shifted the topology to redirect traffic through underutilized nodes.

Comparison between the original static topology and the dynamic load-balancing topology.

As shown in the figure above, the monitoring points indicate a shift in traffic distribution. Quantitatively, the results were significant:

  • Jitter Reduction: Delay jitter for a critical flow dropped from 3.677ms to 1.075ms.
  • Packet Loss: The packet loss rate plummeted from 6.7% to a negligible 0.0039%.
  • Resource Utilization: Traffic was more evenly distributed across the network, providing more headroom for bursty data.

Conclusion

By integrating real-time traffic statistics into the MST calculation via OpenFlow, we can achieve a more resilient and efficient network. This dynamic approach overcomes the limitations of traditional STP, ensuring that network resources are utilized effectively even under heavy load. Future work will focus on mitigating potential oscillation risks during rapid traffic shifts and evaluating the scalability of the controller's polling mechanism in larger data center environments.

Summary updated

Abstract

The MST algorithm has the disadvantage of slow convergence and low resource utilization in the traditional two layer network. The forwarding topology cannot be adjusted in real time to realize the load balance of the whole network. In the SDN architecture, a dynamic construction method for MST based on OpenFlow is proposed in this paper. The controller can adjust no-loop forwarding topology of the underlying network dynamiclly based on the current network traffic distribution to achieve the whole network load balancing. Through simulation, the whole network traffic distribution is more balanced after the topology adjustment, and the index of delay jitter and packet loss ratio has greatly improved.
BibTeX
@article{liu2016dynamic,
  author = {Haike Liu and Jilin Li and Kai Yang},
  title = {{A Dynamic Method of Constructing MST Based on OpenFlow Protocol}},
  journal = {International Journal of Computer and Communication Engineering},
  year = {2016},
  doi = {10.17706/ijcce.2016.5.6.398-408},
}
Figure