TY - GEN
T1 - Disjoint superposition for reduction of conjoined prefixes in IP lookup for actual IPv6 forwarding tables
AU - Rojas-Cessa, Roberto
AU - Kijkanjanarat, Taweesak
AU - Wangchai, Wara
AU - Patil, Krutika
AU - Thirapittayatakul, Narathip
PY - 2016/1/1
Y1 - 2016/1/1
N2 - Helix is a recently-proposed scheme that performs IP lookup in a single memory access. Helix uses parallel prefix matching at the different prefix lengths and the position of prefixes in a binary tree for reducing the amount of memory used. The scheme enables fast table updates as prefixes are kept in their original form. In Helix, a large number of prefixes is stored in a very small amount of memory and route updates, as the lookup process, is performed in a single memory access. Most IPv6 testings of IP lookup schemes are performed on forwarding tables generated synthetically from IPv4 tables as IPv6 tables have a small prefix count. However, the prefix distribution of address blocks in actual tables may be correlated and that may result in using large amounts of memory to represent them. Here, we proposed the application of disjoint superpositions in Helix to further reduce the amount of memory used to represent these forwarding tables. We show that under IPv6 forwarding tables, Helix prevails in performing lookup operations in a single memory access time.
AB - Helix is a recently-proposed scheme that performs IP lookup in a single memory access. Helix uses parallel prefix matching at the different prefix lengths and the position of prefixes in a binary tree for reducing the amount of memory used. The scheme enables fast table updates as prefixes are kept in their original form. In Helix, a large number of prefixes is stored in a very small amount of memory and route updates, as the lookup process, is performed in a single memory access. Most IPv6 testings of IP lookup schemes are performed on forwarding tables generated synthetically from IPv4 tables as IPv6 tables have a small prefix count. However, the prefix distribution of address blocks in actual tables may be correlated and that may result in using large amounts of memory to represent them. Here, we proposed the application of disjoint superpositions in Helix to further reduce the amount of memory used to represent these forwarding tables. We show that under IPv6 forwarding tables, Helix prevails in performing lookup operations in a single memory access time.
KW - Address lookup
KW - Helicoidal properties
KW - Parallel matching
KW - Parallel search
KW - Single memory access
UR - http://www.scopus.com/inward/record.url?scp=85015395102&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85015395102&partnerID=8YFLogxK
U2 - 10.1109/GLOCOM.2016.7841736
DO - 10.1109/GLOCOM.2016.7841736
M3 - Conference contribution
AN - SCOPUS:85015395102
T3 - 2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings
BT - 2016 IEEE Global Communications Conference, GLOBECOM 2016 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 59th IEEE Global Communications Conference, GLOBECOM 2016
Y2 - 4 December 2016 through 8 December 2016
ER -