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.
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,
}
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!
connect with us