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.