Abstract
IP lookup affects the speed of an incoming packet and the time required to determine which output port the packet should be sent to; hence, it plays an important role in the design of router-tables. In this paper, we propose a new data structure, called a multi-prefix trie, for use in designing dynamic routertables. One key feature of our data structure is that each node can store more than one prefix, which reduces the number of memory accesses. When performing lookup, the structure can search more prefixes in one node and may find the longest matching prefix in an internal node rather than on a leaf. Moreover, when updating the router-table, it does not need to reconstruct the table. As a by-product, the proposed data structure minimizes the time required for dynamic router-table operations, including lookup, insertion, and deletion, and also reduces the number of memory accesses. We report the results of experiments conducted to compare the proposed data structure with other structures using the benchmark IPv4 prefix database AS4637 with 219,581 prefixes.
| Original language | English |
|---|---|
| Title of host publication | 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings |
| DOIs | |
| Publication status | Published - 2010 Jul 14 |
| Event | 5th International Conference on Future Information Technology, FutureTech 2010 - Busan, Korea, Republic of Duration: 2010 May 20 → 2010 May 24 |
Publication series
| Name | 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings |
|---|
Other
| Other | 5th International Conference on Future Information Technology, FutureTech 2010 |
|---|---|
| Country | Korea, Republic of |
| City | Busan |
| Period | 10-05-20 → 10-05-24 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Computer Networks and Communications
- Information Systems
Cite this
}
A novel dynamic router-tables design for IP lookup and update. / Hsieh, Sun Yuan; Huang, Chao Wen; Huang, Yi Ling; Yang, Ying Chi.
2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings. 2010. 5482735 (2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - A novel dynamic router-tables design for IP lookup and update
AU - Hsieh, Sun Yuan
AU - Huang, Chao Wen
AU - Huang, Yi Ling
AU - Yang, Ying Chi
PY - 2010/7/14
Y1 - 2010/7/14
N2 - IP lookup affects the speed of an incoming packet and the time required to determine which output port the packet should be sent to; hence, it plays an important role in the design of router-tables. In this paper, we propose a new data structure, called a multi-prefix trie, for use in designing dynamic routertables. One key feature of our data structure is that each node can store more than one prefix, which reduces the number of memory accesses. When performing lookup, the structure can search more prefixes in one node and may find the longest matching prefix in an internal node rather than on a leaf. Moreover, when updating the router-table, it does not need to reconstruct the table. As a by-product, the proposed data structure minimizes the time required for dynamic router-table operations, including lookup, insertion, and deletion, and also reduces the number of memory accesses. We report the results of experiments conducted to compare the proposed data structure with other structures using the benchmark IPv4 prefix database AS4637 with 219,581 prefixes.
AB - IP lookup affects the speed of an incoming packet and the time required to determine which output port the packet should be sent to; hence, it plays an important role in the design of router-tables. In this paper, we propose a new data structure, called a multi-prefix trie, for use in designing dynamic routertables. One key feature of our data structure is that each node can store more than one prefix, which reduces the number of memory accesses. When performing lookup, the structure can search more prefixes in one node and may find the longest matching prefix in an internal node rather than on a leaf. Moreover, when updating the router-table, it does not need to reconstruct the table. As a by-product, the proposed data structure minimizes the time required for dynamic router-table operations, including lookup, insertion, and deletion, and also reduces the number of memory accesses. We report the results of experiments conducted to compare the proposed data structure with other structures using the benchmark IPv4 prefix database AS4637 with 219,581 prefixes.
UR - http://www.scopus.com/inward/record.url?scp=77954408771&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77954408771&partnerID=8YFLogxK
U2 - 10.1109/FUTURETECH.2010.5482735
DO - 10.1109/FUTURETECH.2010.5482735
M3 - Conference contribution
AN - SCOPUS:77954408771
SN - 9781424469505
T3 - 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings
BT - 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings
ER -