TY - JOUR
T1 - Bitmap-based priority-NPT for packet forwarding at named data network
AU - Seo, Jihee
AU - Lim, Hyesook
N1 - Funding Information:
This research was supported by the National Research Foundation of Korea (NRF) , NRF-2017R1A2B4011254 .
Publisher Copyright:
© 2018 Elsevier B.V.
PY - 2018/10
Y1 - 2018/10
N2 - As a promising future Internet architecture, the named data networking (NDN) technology has recently been widely studied. A Forwarding Information Base (FIB) used in forwarding named packets is composed of a set of name prefixes, each of which consists of multiple variable-length name components. Achieving wire-speed name lookup on an FIB is an essential prerequisite for the successful realization of the NDN. As one of the various data structures for the FIB construction, a name prefix trie (NPT) has an extended structure of a binary trie. Since an FIB can have an excessively large number of name prefixes and the cardinality of components at each trie level is theoretically infinite, the name lookup using an NPT has critical issues in terms of memory usage and lookup performance. In this paper, we propose the use of a priority trie and an encoded bitmap structure for efficient name lookup. The simulation result shows that our proposed algorithm achieves less than 2.5 off-chip memory accesses in average for each name lookup against FIB tables with 10,000 to 600,000 name prefixes.
AB - As a promising future Internet architecture, the named data networking (NDN) technology has recently been widely studied. A Forwarding Information Base (FIB) used in forwarding named packets is composed of a set of name prefixes, each of which consists of multiple variable-length name components. Achieving wire-speed name lookup on an FIB is an essential prerequisite for the successful realization of the NDN. As one of the various data structures for the FIB construction, a name prefix trie (NPT) has an extended structure of a binary trie. Since an FIB can have an excessively large number of name prefixes and the cardinality of components at each trie level is theoretically infinite, the name lookup using an NPT has critical issues in terms of memory usage and lookup performance. In this paper, we propose the use of a priority trie and an encoded bitmap structure for efficient name lookup. The simulation result shows that our proposed algorithm achieves less than 2.5 off-chip memory accesses in average for each name lookup against FIB tables with 10,000 to 600,000 name prefixes.
KW - Bitmap
KW - Forwarding engine
KW - Memory hierarchy
KW - Name prefix trie
KW - Named data networking
UR - http://www.scopus.com/inward/record.url?scp=85059061588&partnerID=8YFLogxK
U2 - 10.1016/j.comcom.2018.09.001
DO - 10.1016/j.comcom.2018.09.001
M3 - Article
AN - SCOPUS:85059061588
SN - 0140-3664
VL - 130
SP - 101
EP - 112
JO - Computer Communications
JF - Computer Communications
ER -