@article{ART002109876},
author={Junghwan Kim and Jinsoo Kim},
title={High Performance IP Address Lookup Using GPU},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2016},
volume={21},
number={5},
pages={49-56}
TY - JOUR
AU - Junghwan Kim
AU - Jinsoo Kim
TI - High Performance IP Address Lookup Using GPU
JO - Journal of The Korea Society of Computer and Information
PY - 2016
VL - 21
IS - 5
PB - The Korean Society Of Computer And Information
SP - 49
EP - 56
SN - 1598-849X
AB - Increasing Internet traffic and forwarding table size need high performance IP address lookup engine which is a crucial function of routers. For finding the longest matching prefix, trie-based or its variant schemes have been widely researched in software-based IP lookup. As a software router, we enhance the IP address lookup engine using GPU which is a device widely used in high performance applications. We propose a data structure for multibit trie to exploit GPU hardware efficiently. Also, we devise a novel scheme that the root subtrie is loaded on Shared Memory which is specialized for fast access in GPU. Since the root subtrie is accessed on every IP address lookup, its fast access improves the lookup performance. By means of the performance evaluation, our implemented GPU-based lookup engine shows 17~23 times better performance than CPU-based engine. Also, the fast access technique for the root subtrie gives 10% more improvement.
KW - IP address lookup;Router;GPU;Multibit trie;CUDA I. Introduction 지속적으로 증가하는 인터넷 트래픽에 대응하기 위해서는 물리적 전송선의 대역폭 증가도 필요하지만;라우터의 성능도 고도화하는 것이 요구된다. 가령;OC-3072의 경우 159.252 Gbps의 대역폭을 갖는데;이 경우 라우터에서는 최소 이더넷 프레임 (64 bytes) 기준으로 약 초당 3.1억 개 이상의 패킷 처리 성능이 요구된다. 즉;라우터에서 IP address lookup을 초당 3억 번 이상 처리할수 있는 성능을 갖춰야 한다. IP address lookup은 라우터의 주요 기능으로써;주어진 패킷의목적지 IP address에 대해 nexthop 정보를 찾아내는 작업이다[1]. CIDR(Classless Inter-Domain Routing)[2]이 도입된 이후 IP address lookup은 LMP(Longest Matching Prefix)를 찾는 과정이 되어 시간이 많이 걸리는 작업이 되었으며;라우팅 테이블의prefix의 개수 또한 지속적으로 증가하고 있는 추세이다[3]. IP address lookup에 사용되는 포워딩 테이블(forwarding table)은
DO -
UR -
ER -
Junghwan Kim and Jinsoo Kim. (2016). High Performance IP Address Lookup Using GPU. Journal of The Korea Society of Computer and Information, 21(5), 49-56.
Junghwan Kim and Jinsoo Kim. 2016, "High Performance IP Address Lookup Using GPU", Journal of The Korea Society of Computer and Information, vol.21, no.5 pp.49-56.
Junghwan Kim, Jinsoo Kim "High Performance IP Address Lookup Using GPU" Journal of The Korea Society of Computer and Information 21.5 pp.49-56 (2016) : 49.
Junghwan Kim, Jinsoo Kim. High Performance IP Address Lookup Using GPU. 2016; 21(5), 49-56.
Junghwan Kim and Jinsoo Kim. "High Performance IP Address Lookup Using GPU" Journal of The Korea Society of Computer and Information 21, no.5 (2016) : 49-56.
Junghwan Kim; Jinsoo Kim. High Performance IP Address Lookup Using GPU. Journal of The Korea Society of Computer and Information, 21(5), 49-56.
Junghwan Kim; Jinsoo Kim. High Performance IP Address Lookup Using GPU. Journal of The Korea Society of Computer and Information. 2016; 21(5) 49-56.
Junghwan Kim, Jinsoo Kim. High Performance IP Address Lookup Using GPU. 2016; 21(5), 49-56.
Junghwan Kim and Jinsoo Kim. "High Performance IP Address Lookup Using GPU" Journal of The Korea Society of Computer and Information 21, no.5 (2016) : 49-56.
