Visible to the public Scalable Packet Classification for Datacenter Networks

TitleScalable Packet Classification for Datacenter Networks
Publication TypeJournal Article
Year of Publication2014
AuthorsPi-Chung Wang
JournalSelected Areas in Communications, IEEE Journal on
Date PublishedJanuary
Keywordsclassification rules, computer centres, data structures, datacenter network, datacenter networks, Decision trees, encoded rule expansion, encoding, firewalls, Hardware, hardware parallelism, hash table, Indexes, IP networks, length combinations, Local area networks, packet classification, packet forwarding, router architectures, Scalability, Software, storage penalty, telecommunication network routing, virtual machines, VLAN, VLANs

The key challenge to a datacenter network is its scalability to handle many customers and their applications. In a datacenter network, packet classification plays an important role in supporting various network services. Previous algorithms store classification rules with the same length combinations in a hash table to simplify the search procedure. The search performance of hash-based algorithms is tied to the number of hash tables. To achieve fast and scalable packet classification, we propose an algorithm, encoded rule expansion, to transform rules into an equivalent set of rules with fewer distinct length combinations, without affecting the classification results. The new algorithm can minimize the storage penalty of transformation and achieve a short search time. In addition, the scheme supports fast incremental updates. Our simulation results show that more than 90% hash tables can be eliminated. The reduction of length combinations leads to an improvement on speed performance of packet classification by an order of magnitude. The results also show that the software implementation of our scheme without using any hardware parallelism can support up to one thousand customer VLANs and one million rules, where each rule consumes less than 60 bytes and each packet classification can be accomplished under 50 memory accesses.

Citation Key6689489