Tsinghua Science and Technology


Software Defined Networks (SDNs), load balancing, per-flow routing, tag-based routing, flow table size constraint, deployment delay constraint


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.


Tsinghua University Press