A multilevel Bit Vector minimization method for fast online detection of conflicting flow entries in OpenFlow table

OpenFlow implements flow-based control over switches with improved network management performance. However, a packet may match more than one flow entry due to the intra-table dependency phenomenon among flow entries. Moreover, different packets may incur different conflicting flow entries under the intra-table dependency. Forwarding packets by the first-match scheme for prioritized flow entries may not always produce the best outcome. Thus, an online conflict detection procedure executed for each incoming packet is needed to flag the conflicts to network administrators. In addition, the SDN controller may frequently update the service provisioning policies that are specified in the flow entries and deliver them to the switches in a large OpenFlow-based environment. This needs a high-performance conflict detection mechanism to support real-time updating. However, performing conflict detection within a large flow table will be very time consuming. This paper first develops a graph-based multilevel redundancy reduction scheme to construct highly compact matching trees that will be used in conflict detection for a large flow table. Then, a conflict detection algorithm with higher performance and lower cost, the Compact Bit Vector algorithm (CBV), is proposed. The performance of the CBV has been validated through an extensive mathematical performance analysis followed by simulations, with good results in terms of requiring less time for the search, lower memory requirement and lower incremental updating time. Obviously, the CBV is very suitable for the conflict detection task of a large and frequently updated flow table.