کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
450848 694180 2013 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
GPU-accelerated name lookup with component encoding
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
GPU-accelerated name lookup with component encoding
چکیده انگلیسی

Named Data Networking (NDN) aims at redesigning the current Internet: using names to identify the wanted contents instead of using IP addresses to locate the end hosts, with the goal of substantially improving the data retrieval efficiency. Different from IP routers, NDN routers forward packets by names. An NDN name is composed of a number of length-variable components, causing the name to be tens or even hundreds of characters in length. Meanwhile, NDN routing tables could be several orders of magnitude larger than the current IP routing tables. This kind of complex name constitution plus the huge-sized name table makes wire speed name lookup an extremely challenging task.In pursuit of overcoming this challenge, we propose a Name Component Encoding (NCE) solution that assigns codes (integers) to name components. Along with an elaborate one-dimensional transition array and a local code allocation algorithm, NCE performs every node transition by a single memory access to boost lookup speed besides greatly compressing storage space. Moreover, we implement the name lookup engine on a GPU platform to exploit GPU’s massive parallel processing power; furthermore, pipeline and CUDA multi-stream techniques are applied to GPU to increase lookup throughout while reducing lookup latency. Experimental results demonstrate that, under the constraint of 100 μs latency, our GPU-based name lookup engine can achieve 51.78 million searches per second on a name table containing 10 million prefixes. NCE also saves 59.57% memory cost comparing with the character trie and supports around 900K prefix insertions and 1.2 million prefix deletions per second.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Networks - Volume 57, Issue 16, 13 November 2013, Pages 3165–3177
نویسندگان
, , , , , ,