SRAM-based architectures for high-speed IP address lookup and packet classification

Abstract

When a packet arrives at a flow-aware router in the Internet, the router performs two basic functions, namely IP address lookup and packet classification, to decide how to process the packet. First, the packet header is checked against an access control list and/or firewall to determine whether it will be accepted or rejected. This operation uses multiple TCP/IP header fields to classify packets into flows, and it is called packet classification. Packet classification is also used to support access control, per-flow based quality-of-service provisioning, traffic policing, billing and accounting, and policy-based forwarding for virtual private network (VPN). For the basic packet forwarding, the router uses the packet's IP destination address as the key to look up its routing table to determine the packet's next hop. This operation is called IP address lookup. IP address lookup and packet classification are the two most computation intensive tasks, and they are often the bottlenecks of packet processing in high-speed routers. For 100 Gbps communication line, the packet arrival rate can be up to 312.5 million packets per second. In this thesis, application-specific hardware architectures to speed up these two operations are presented. An algorithmic RAM-based IP address lookup method called bit-shuffled trie is presented in the thesis. By rearranging the bits of the prefixes, memory efficient index tables can be constructed to support IP address lookup. The address lookup engine can be implemented using pipelined architecture with simple processing logic. The proposed method has superior memory efficiency. The memory cost for a 474K prefixes IPv4 routing table is only 1.1MB, and the memory cost for a 215K 64-bit prefixes IPv6 routing table is about 1.7MB. The exceptional memory efficiency of the proposed method allows us to implement the IP address lookup engine for both IPv4 and IPv6 on a single FPGA device. Incremental updates to the routing table can be handled efficiently. On average, about 8 memory-write operations to the data structures are required to process an insertion or deletion. In typical algorithmic packet classification methods, the data structure is tailored for the given ruleset. It is common among published algorithmic methods that the worst case number of memory accesses per classification depends on the properties of the ruleset, such as the distribution of the address prefixes and port ranges. As a result, existing methods do not guarantee constant classification rate. A novel multi-pipeline architecture for packet classification is presented in this thesis. The method has outstanding performance in both space and time. The method incorporate the prefix inclusion coding scheme to achieve outstanding memory efficiency. For rulesets with 10 thousand rules, the storage cost of our method is between 16 to 24.5 bytes per rule. The hardware uses fixed-length linear pipelines. Hence, the classification rate is constant regardless of the ruleset properties. To demonstrate the feasibility of the method, the proposed architecture is implemented on a Virtex-6 FPGA and the device can achieve a classification rate of 340 million packets per second (MPPS).

Date of Award	3 Oct 2014
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chi Wai Derek PAO (Supervisor)