Technical Report Number
The growth and diversiﬁcation of the Internet imposes increasing demands on the performance and functionality of network infrastructure. Routers, the devices responsible for the switch-ing and directing of trafﬁc in the Internet, are being called upon to not only handle increased volumes of trafﬁc at higher speeds, but also impose tighter security policies and provide support for a richer set of network services. This dissertation addresses the searching tasks performed by Internet routers in order to forward packets and apply network services to packets belonging to deﬁned trafﬁc ﬂows. As these searching tasks must be performed for each packet traversing the router, the speed and scalability of the solutions to the route lookup and packet classiﬁcation problems largely determine the realizable performance of the router, and hence the Internet as a whole. Despite the energetic attention of the academic and corporate research communities, there remains a need for search engines that scale to support faster communication links, larger route tables and ﬁlter sets and increasingly complex ﬁlters. The major contributions of this work include the design and analysis of a scalable hardware implementation of a Longest Preﬁx Matching (LPM) search engine for route lookup, a survey and taxonomy of packet classiﬁcation techniques, a thorough analysis of packet classiﬁcation ﬁlter sets, the design and analysis of a suite of performance evaluation tools for packet classiﬁcation algorithms and devices, and a new packet classiﬁcation algorithm that scales to support high-speed links and large ﬁlter sets classifying on additional packet ﬁelds.
Taylor, David Edward and Turner, Jonathan S., "Models, Algorithms, and Architectures for Scalable Packet Classification" Report Number: WUCSE-2004-40 (2004). All Computer Science and Engineering Research.