Hybrid Data Structure for IP Lookup in Virtual Routers Using FPGAs

Erdem O., Le H., Prasanna V. K., BAZLAMAÇCI C. F.

22nd IEEE International Conference on Application-Specific Systems, Architectures and Processors (ASAP), California, United States Of America, 11 - 14 September 2011, pp.95-102 identifier

  • Publication Type: Conference Paper / Full Text
  • City: California
  • Country: United States Of America
  • Page Numbers: pp.95-102
  • Middle East Technical University Affiliated: Yes


Network router virtualization has recently gained much interest in the research community, as it allows multiple virtual router instances to run on a common physical router platform. The key metrics in designing network virtual routers are (1) number of supported virtual router instances, (2) total number of prefixes, and (3) ability to quickly update the virtual table. Existing merging algorithms use leaf pushing and a shared next hop data structure to eliminate the large memory bandwidth requirement. However, the size of the shared next hop table grows linearly with the number of virtual routers. Due to the limited amount of on-chip memory and the number of I/O pins of Field Programmable Gate Arrays (FPGAs), existing designs cannot support large number of tables and/or large number of prefixes.