  OpenFlow switches are fundamental components of software defined networking,
where the key operation is to look up flow tables to determine which flow an
incoming packet belongs to. This needs to address the same multi-field
rule-matching problem as legacy packet classification, but faces more serious
scalability challenges. The demand of fast on-line updates makes most existing
solutions unfit, while the rest still lacks the scalability to either large
data sets or large number of fields to match for a rule. In this work, we
propose TupleChain for fast OpenFlow table lookup with multifaceted
scalability. We group rules based on their masks, each being maintained with a
hash table, and explore the connections among rule groups to skip unnecessary
hash probes for fast search. We show via theoretical analysis and extensive
experiments that the proposed scheme not only has competitive computing
complexity, but is also scalable and can achieve high performance in both
search and update. It can process multiple millions of packets per second,
while dealing with millions of on-line updates per second at the same time, and
its lookup speed maintains at the same level no mater it handles a large flow
table with 10 million rules or a flow table with every entry having as many as
100 match fields.
