A Heuristic and Hybrid Hash-based Approach to Fast Lookup

Add to your list(s) Download to your calendar using vCal

• Gianni Antichi (University of Pisa)
• Thursday 13 May 2010, 16:00-17:00
• FW26, Computer Laboratory, William Gates Builiding.

If you have a question about this talk, please contact Eiko Yoneki.

IP address lookup is a fundamental task for Internet routers. Because of the rapid growth of both traffic and links capacity, the time budget to process a packet continues to decrease and lookup tables unceasingly grow; therefore, new algorithms are required to improve lookup performance. However, the large density disparity on the prefix range within real lookup tables suggests a hybrid adaptive technique as effective and simple solution. Therefore, this talk presents a novel approach in which various prefix length ranges are represented with distinct data structures and stored in different memories. In this way, the different frequencies of forwarding rules can be taken in account and the memory hierarchy of real platforms can be exploited. This leads to small structures to be put in fast memory for the most dense ranges and larger structures (with a lower number of accesses) in the slower memories for the other ranges. The results remark the low number of off-chip memory accesses of our scheme and a valuable speedup.

Bio: Gianni Antichi received his Laurea degree in Telecommunication Engineering on September 2007 from University of Pisa, by discussing a thesis on “BRUNO: A High Performance Traffic Generator on Network Processor”. In January 2008 he entered, as PhD student, the Department of Information Engineering at the University of Pisa, where he is currently doing research in the area of Next Generation Networks using FPGA and Network Processors.

This talk is part of the Computer Laboratory Systems Research Group Seminar series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• CL's SRG seminar
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Computer Laboratory Systems Research Group Seminar
• Department of Computer Science and Technology talks and seminars
• FW26, Computer Laboratory, William Gates Builiding
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• rp587

Note that ex-directory lists are not shown.