In software defined networks (SDN), the open-source virtual switch tends to face challenges due to enormous rule processing and intricate data forwarding. Packet classification becomes a vitally important topic. A good classification strategy should achieve fast rule lookup and update at reasonable memory cost. It is challenging for both tuple-based and tree-based algorithms to simultaneously maintain desirable lookup and update performance. Tuple-based algorithms may attain efficient updates but experience unappealing lookup, while tree-based algorithms may attain better lookup by tree traversal but surrender update performance to potential rule replication. The main goal of this investigation is to construct a new algorithm to improve the classification efficiency of previous approaches—particularly to secure a proper performance balance between lookup and update. The proposed MLTree algorithm is an essentially tree-based approach. It maintains the lookup benefits of decision trees and also produces desirable updates by tuple-based multilayer partitioning which fits better to the universality of varying field lengths and scalability of multiple fields in SDN. Evaluation results show that, with feasible cost, MLTree realizes steadily better lookup and update performance than previous algorithms.
