|
We're training the next generation of computer scientists to find creative solutions to real-world problems. Join CACS to fulfil your dream as a computer expert or scientist!
|
|
Colloquium, "Fast IP Address Lookups for High-Performance Routers", Dr. Nian-Feng Tzeng
Abstract
Essential for the Internet in handling its massive data volumes daily, routers connect wires operating at various speeds, possibly up to 40 Gbps. Fast IP address lookups have become indispensable for all routers, whether core or edge ones, but they are challenging, involving longest prefix matching (LPM, which chooses the longest prefix among those which match the given IP address). Earlier solutions for IP address lookups were mostly trie-based to match an IP address progressively a few bits at a time against prefixes stored in a tree-like data structure. Given rapid surges in the routing table sizes and widespread deployment of 10Gbps Ethernet switches lately, the LPM lookup rate of tens of million of packets per second (MPPS) cannot be achieved by classical LPM solutions, prompting active research. This talk surveys representative trie-based LPM methods, examines hash-based LPM techniques, and briefly introduces our proposed LPM scheme with superior storage-efficiency to yield over 100 MPPS for high-performance routers.
DATE: FRIDAY, JANUARY 22, 2010
TIME: 11:00 A.M. - 12:00 NOON
LOCATION: ACTR AUDITORIUM, ROOM 112
