RuleAlchemy: Bidirectional Conflict-Aware Rule Aggregation for Crossed Probing Paths in SDN
摘要
Active probing techniques based on cross verification can accurately locate network failures by injecting probe packets along multiple explicit paths. Software Defined Networking (SDN) facilitates explicit path control by inserting forwarding rules in all switches traversed by each path. Given the limited number of entries that Ternary Content Addressable Memory (TCAM) can accommodate on switches, we aim to construct all crossed probing paths in SDN in a more light-weight manner. To address the high latency issue introduced by frequent rule updates, we present RuleAlchemy, a static rule aggregation method. It fully aggregates all forwarding rules with the same action into a single generalized rule, thereby minimizing TCAM entry usage. Since the generalization of rules may cause routing conflicts, RuleAlchemy further splits the conflicting aggregated rules and employs a conflict-aware best-fit algorithm to minimize the number of additional split rules. We evaluate RuleAlchemy using real-world network topologies and find that, compared to other rule aggregation methods, RuleAlchemy improves TCAM compression rates by approximately 59% on average and achieves a gap of within 6% compared to the optima obtained by complete aggregation.