Skip to main content
USENIX
  • Conferences
  • Students
Sign in
  • Overview
  • Registration Information
  • Registration Discounts
  • Symposium Organizers
  • At a Glance
  • Calendar
  • Technical Sessions
  • Live Streaming
  • Purchase the Box Set
  • Tutorial on GENI
  • Posters and Demos
  • Sponsorship
  • Activities
  • Hotel and Travel Information
  • Services
  • Students
  • Questions?
  • Help Promote
  • For Participants
  • Call for Papers
  • Past Proceedings

sponsors

Silver Sponsor
Silver Sponsor
Silver Sponsor
Bronze Sponsor
Bronze Sponsor
Bronze Sponsor
General Sponsor
General Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor

twitter

Tweets by @usenix

usenix conference policies

  • Event Code of Conduct
  • Conference Network Policy
  • Statement on Environmental Responsibility Policy

You are here

Home » Wire Speed Name Lookup: A GPU-based Approach
Tweet

connect with us

http://www.twitter.com/usenix
https://www.facebook.com/usenixassociation
http://www.linkedin.com/groups/USENIX-Association-49559/about
https://plus.google.com/108588319090208187909/posts
http://www.youtube.com/user/USENIXAssociation

Wire Speed Name Lookup: A GPU-based Approach

Authors: 

Yi Wang, Tsinghua University; Yuan Zu, University of Science and Technology of China; Ting Zhang, Tsinghua University; Kunyang Peng and Qunfeng Dong, University of Science and Technology of China; Bin Liu, Wei Meng, and Huicheng Dai, Tsinghua University; Xin Tian and Zhonghu Xu, University of Science and Technology of China; Hao Wu, Tsinghua University; Di Yang, University of Science and Technology of China

Abstract: 

This paper studies the name lookup issue with longest prefix matching, which is widely used in URL filtering, content routing/switching, etc. Recently Content-Centric Networking (CCN) has been proposed as a clean slate future Internet architecture to naturally fit the content centric property of today’s Internet usage: instead of addressing end hosts, the Internet should operate based on the identity/name of contents. A core challenge and enabling technique in implementing CCN is exactly to perform name lookup for packet forwarding at wirespeed. In CCN, routing tables can be orders of magnitude larger than current IP routing tables, and content names are much longer and more complex than IP addresses. In pursuit of conquering this challenge, we conduct an implementation-based case study on wire speed name lookup, exploiting GPU’s massive parallel processing power. Extensive experiments demonstrate that our GPU-based name lookup engine can achieve 63.52M searches per second lookup throughput on large-scale name tables containing millions of name entries with a strict constraint of no more than the telecommunication level 100μs per-packet lookup latency. Our solution can be applied to contexts beyond CCN, such as search engines, content filtering, and intrusion prevention/detection.

Yi Wang, Tsinghua University

Yuan Zu, University of Science and Technology of China

Ting Zhang, Tsinghua University

Kunyang Peng, University of Science and Technology of China

Qunfeng Dong, University of Science and Technology of China

Bin Liu, Tsinghua University

Wei Meng, Tsinghua University

Huicheng Dai, Tsinghua University

Xin Tian, University of Science and Technology of China

Zhonghu Xu, University of Science and Technology of China

Hao Wu, Tsinghua University

Di Yang, University of Science and Technology of China

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {180305,
author = {Yi Wang and Yuan Zu and Ting Zhang and Kunyang Peng and Qunfeng Dong and Bin Liu and Wei Meng and Huicheng Dai and Xin Tian and Zhonghu Xu and Hao Wu and Di Yang},
title = {Wire Speed Name Lookup: A {GPU-based} Approach},
booktitle = {10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13)},
year = {2013},
isbn = {978-1-931971-00-3},
address = {Lombard, IL},
pages = {199--212},
url = {https://www.usenix.org/conference/nsdi13/technical-sessions/presentation/wang_yi},
publisher = {USENIX Association},
month = apr
}
Download
Wang PDF
View the slides

Presentation Video 

Presentation Audio

MP3 Download

Download Audio

Public Summary: 

by Michael Walfish

Using GPU hardware, the authors of this paper implement longest prefix matching (LPM) of arbitrary and variable-length strings. Their key technique is a new data structure for compressing a trie, and they couple this with sophisticated GPU engineering, yielding impressively high throughput (hundreds of Gbps in the core engine) for a workload consisting of lookups. However, insertions can be costly, as they cause the system to rebuild the data structure in the worst case.

A question about the paper concerns its stated motivation of Content Centric Networking (CCN), also known as Named Data Networking (NDN); the authors observe that for CCN or NDN to succeed, there need to be routers that can perform wire-speed longest prefix matches of flat names. However, as observed by the program committee (PC), the authors' evaluation did not necessarily demonstrate the suitability of the system for an NDN world: the authors evaluated on a data set consisting of DNS names. In an NDN world, meanwhile, there could be orders of magnitude more names; thus, each router would likely need very large tables and even then, each router would experience high rates of insertions and deletions (given a heavy-tailed workload, a sizeable fraction of requests will be "new").

However, the PC felt that the authors' work could be relevant to contexts other than NDN. In other words, the PC viewed its role not as making side bets on NDN but as promoting technology that is promising and novel; on that basis, this paper surely qualifies!

  • Log in or    Register to post comments

Silver Sponsors

Bronze Sponsors

General Sponsors

Media Sponsors & Industry Partners

© USENIX

  • Privacy Policy
  • Contact Us