A novel dynamic router-tables design for IP lookup and update

Sun Yuan Hsieh, Chao Wen Huang, Yi Ling Huang, Ying Chi Yang

研究成果: Conference contribution

6 引文 (Scopus)

摘要

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.

原文English
主出版物標題2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings
DOIs
出版狀態Published - 2010 七月 14
事件5th International Conference on Future Information Technology, FutureTech 2010 - Busan, Korea, Republic of
持續時間: 2010 五月 202010 五月 24

出版系列

名字2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings

Other

Other5th International Conference on Future Information Technology, FutureTech 2010
國家Korea, Republic of
城市Busan
期間10-05-2010-05-24

指紋

Routers
Data structures
Data storage equipment
Byproducts
Experiments

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Information Systems

引用此文

Hsieh, S. Y., Huang, C. W., Huang, Y. L., & Yang, Y. C. (2010). A novel dynamic router-tables design for IP lookup and update. 於 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings [5482735] (2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings). https://doi.org/10.1109/FUTURETECH.2010.5482735
Hsieh, Sun Yuan ; Huang, Chao Wen ; Huang, Yi Ling ; Yang, Ying Chi. / A novel dynamic router-tables design for IP lookup and update. 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings. 2010. (2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings).
@inproceedings{7042bb951b3d481897fea99561f2a417,
title = "A novel dynamic router-tables design for IP lookup and update",
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.",
author = "Hsieh, {Sun Yuan} and Huang, {Chao Wen} and Huang, {Yi Ling} and Yang, {Ying Chi}",
year = "2010",
month = "7",
day = "14",
doi = "10.1109/FUTURETECH.2010.5482735",
language = "English",
isbn = "9781424469505",
series = "2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings",
booktitle = "2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings",

}

Hsieh, SY, Huang, CW, Huang, YL & Yang, YC 2010, A novel dynamic router-tables design for IP lookup and update. 於 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings., 5482735, 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings, 5th International Conference on Future Information Technology, FutureTech 2010, Busan, Korea, Republic of, 10-05-20. https://doi.org/10.1109/FUTURETECH.2010.5482735

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).

研究成果: 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 -

Hsieh SY, Huang CW, Huang YL, Yang YC. A novel dynamic router-tables design for IP lookup and update. 於 2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings. 2010. 5482735. (2010 5th International Conference on Future Information Technology, FutureTech 2010 - Proceedings). https://doi.org/10.1109/FUTURETECH.2010.5482735