A new name prefix trie with path compression

Jungwon Lee; Hyesook Lim

doi:10.1109/ICCE-Asia.2016.7804781

A new name prefix trie with path compression

Jungwon Lee, Hyesook Lim

Electronic and Electrical Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

11 Scopus citations

Abstract

As one of promising future Internet architectures, named data networking (NDN) technology has been widely researched in these days. As a basic name lookup structure used in NDN routers, a name prefix trie (NPT) is an extended version of a binary trie used for IP address lookup. However, since name prefixes can have an unbounded number of components, an NPT can have many empty nodes which cause memory wastes as well as low lookup performance. In this paper, we propose a pathcompressed NPT (PC-NPT) to reduce the memory requirement and improve the search performance. Simulations using real URL data sets show that the proposed structure removes up to 97% of empty nodes and improves approximately 21% in the search performance.

Original language	English
Title of host publication	2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
Publisher	Institute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)	9781509027439
DOIs	https://doi.org/10.1109/ICCE-Asia.2016.7804781
State	Published - 3 Jan 2017
Event	2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016 - Seoul, Korea, Republic of Duration: 26 Oct 2016 → 28 Oct 2016

Publication series

Name	2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016

Conference

Conference	2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016
Country/Territory	Korea, Republic of
City	Seoul
Period	26/10/16 → 28/10/16

Bibliographical note

Publisher Copyright:
© 2016 IEEE.

Access to Document

10.1109/ICCE-Asia.2016.7804781

Cite this

@inproceedings{c3aeb879cd3042699a52673b5ca0978a,

title = "A new name prefix trie with path compression",

abstract = "As one of promising future Internet architectures, named data networking (NDN) technology has been widely researched in these days. As a basic name lookup structure used in NDN routers, a name prefix trie (NPT) is an extended version of a binary trie used for IP address lookup. However, since name prefixes can have an unbounded number of components, an NPT can have many empty nodes which cause memory wastes as well as low lookup performance. In this paper, we propose a pathcompressed NPT (PC-NPT) to reduce the memory requirement and improve the search performance. Simulations using real URL data sets show that the proposed structure removes up to 97% of empty nodes and improves approximately 21% in the search performance.",

author = "Jungwon Lee and Hyesook Lim",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016 ; Conference date: 26-10-2016 Through 28-10-2016",

year = "2017",

month = jan,

day = "3",

doi = "10.1109/ICCE-Asia.2016.7804781",

language = "English",

series = "2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

booktitle = "2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016",

}

Lee, J & Lim, H 2017, A new name prefix trie with path compression. in 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016., 7804781, 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016, Institute of Electrical and Electronics Engineers Inc., 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016, Seoul, Korea, Republic of, 26/10/16. https://doi.org/10.1109/ICCE-Asia.2016.7804781

A new name prefix trie with path compression. / Lee, Jungwon; Lim, Hyesook.
2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016. Institute of Electrical and Electronics Engineers Inc., 2017. 7804781 (2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A new name prefix trie with path compression

AU - Lee, Jungwon

AU - Lim, Hyesook

PY - 2017/1/3

Y1 - 2017/1/3

N2 - As one of promising future Internet architectures, named data networking (NDN) technology has been widely researched in these days. As a basic name lookup structure used in NDN routers, a name prefix trie (NPT) is an extended version of a binary trie used for IP address lookup. However, since name prefixes can have an unbounded number of components, an NPT can have many empty nodes which cause memory wastes as well as low lookup performance. In this paper, we propose a pathcompressed NPT (PC-NPT) to reduce the memory requirement and improve the search performance. Simulations using real URL data sets show that the proposed structure removes up to 97% of empty nodes and improves approximately 21% in the search performance.

AB - As one of promising future Internet architectures, named data networking (NDN) technology has been widely researched in these days. As a basic name lookup structure used in NDN routers, a name prefix trie (NPT) is an extended version of a binary trie used for IP address lookup. However, since name prefixes can have an unbounded number of components, an NPT can have many empty nodes which cause memory wastes as well as low lookup performance. In this paper, we propose a pathcompressed NPT (PC-NPT) to reduce the memory requirement and improve the search performance. Simulations using real URL data sets show that the proposed structure removes up to 97% of empty nodes and improves approximately 21% in the search performance.

UR - http://www.scopus.com/inward/record.url?scp=85011081856&partnerID=8YFLogxK

U2 - 10.1109/ICCE-Asia.2016.7804781

DO - 10.1109/ICCE-Asia.2016.7804781

M3 - Conference contribution

AN - SCOPUS:85011081856

T3 - 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016

BT - 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2016 IEEE International Conference on Consumer Electronics-Asia, ICCE-Asia 2016

Y2 - 26 October 2016 through 28 October 2016

ER -

A new name prefix trie with path compression

Abstract

Publication series

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this