Hybrid Routing by Joint Optimization of Per-Flow Routing and Tag-Based Routing in Software-Defined Networks

In recent years, Software-Defined Networks (SDNs) have become a promising technology to improve network utilization. However, limited flow table size and long deployment delays may result in low network performance in large-scale networks and a poor user experience. While a typical solution to this issue is routing aggregation (i.e., wildcard routing), the aggregation feasibility problem and reduced network performance may be encountered. To address this dilemma, we first design a novel wildcard routing scheme, called the Tag-based Rule Placement Scheme (TRPS). We then formulate a Hybrid Routing by Joint optimization of Per-flow routing and Tag-based routing (HR-JPT) problem, and prove its NP-hardness. An algorithm with a bounded approximation factor is designed for this problem, and the proposed methods are implemented on a Mininet platform. Extensive simulation results show that our methods are efficient for wildcard/hybrid routing. For example, our proposed tag-based wildcard rule placement scheme can reduce the number of required rules by about 65% on average compared with previous wildcard routing methods. Our proposed hybrid routing algorithm can increase network throughput by about 43% compared with existing hybrid routing solutions.