|
|
||
Cristian Estan DIMACS Tutorial on Algorithms for Next Generation Networks, August 2007 One of the main challenges for the builders of modern IP routers and switches is to perform data plane functions at high speeds. The need for more and more control over the traffic means that besides traditional operations such as routing table lookup, these devices must perform more and more complex operations such as packet classification and matching signatures against the traffic. While the performance of the underlying hardware technologies is crucial for achieving the high speeds, the algorithms used to perform these functions also have a tremendous effect on performance and cost. In this talk I will present an overview of the best current algorithmic solutions for three important data plane operations: finding the longest matching prefix (used for routing table lookup), packet classification on multiple fields (used for security and QoS), and regular expression matching (used in intrusion prevention). While the talk will focus on algorithmic aspects, I will also present some solutions that use custom hardware (no background in hardware design is required). Presentation in PowerPoint. |
