The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
최근에 우리는 접두사를 스칼라 숫자로 사용하는 새로운 접두사 조회 알고리즘을 제안했습니다. 이 알고리즘은 이진 검색 트리와 같은 다른 트리 구조와 RB-트리, AVL-트리 및 B-트리와 같은 다른 균형 트리에 적용할 수 있으며 검색, 삽입 및/또는 삭제 절차를 약간 수정하여 찾을 수 있습니다. 들어오는 문자열의 접두사(예: IP 주소). 결과적으로 검색 절차가 복잡해집니다. O (로그 n) 어디에 n 트리에 저장된 접두사의 수입니다. 더 중요한 것은 검색 복잡성이 주소 길이에 좌우되지 않는다는 것입니다. w 즉, IPv32의 경우 4이고 IPv128의 경우 6입니다. 여기서는 메모리에 대한 인터페이스가 접두사에 액세스할 수 있을 만큼 충분히 넓으며 비교와 같은 일부 간단한 작업이 다음에서 수행될 수 있다고 가정합니다. O (1) 단어 길이에도 불구하고 w. 또한, 이 알고리즘의 삽입 및 삭제 절차는 경쟁사에 비해 훨씬 간단하고 빠릅니다. 다음에서는 이 알고리즘의 소프트웨어 구현 결과를 보고하고 이를 IPv4 및 IPv6에 대한 다른 솔루션과 비교합니다. 또한 IPv4용 알고리즘의 간단한 하드웨어 구현에 대해서도 보고합니다. 비교 결과는 평균 및 최악의 경우 모두에서 스칼라 접두사 검색에 대한 더 나은 조회 및 업데이트 성능 또는 우수한 스토리지 요구 사항을 보여줍니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Mohammad BEHDADFAR, Hossein SAIDI, Masoud-Reza HASHEMI, Ali GHIASIAN, Hamid ALAEI, "IP Lookup Using the Novel Idea of Scalar Prefix Search with Fast Table Updates" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 11, pp. 2932-2943, November 2010, doi: 10.1587/transinf.E93.D.2932.
Abstract: Recently, we have proposed a new prefix lookup algorithm which would use the prefixes as scalar numbers. This algorithm could be applied to different tree structures such as Binary Search Tree and some other balanced trees like RB-tree, AVL-tree and B-tree with minor modifications in the search, insert and/or delete procedures to make them capable of finding the prefixes of an incoming string e.g. an IP address. As a result, the search procedure complexity would be O(log n) where n is the number of prefixes stored in the tree. More important, the search complexity would not depend on the address length w i.e. 32 for IPv4 and 128 for IPv6. Here, it is assumed that interface to memory is wide enough to access the prefix and some simple operations like comparison can be done in O(1) even for the word length w. Moreover, insertion and deletion procedures of this algorithm are much simpler and faster than its competitors. In what follows, we report the software implementation results of this algorithm and compare it with other solutions for both IPv4 and IPv6. It also reports on a simple hardware implementation of the algorithm for IPv4. Comparison results show better lookup and update performances or superior storage requirements for Scalar Prefix Search in both average and worst cases.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.2932/_p
부
@ARTICLE{e93-d_11_2932,
author={Mohammad BEHDADFAR, Hossein SAIDI, Masoud-Reza HASHEMI, Ali GHIASIAN, Hamid ALAEI, },
journal={IEICE TRANSACTIONS on Information},
title={IP Lookup Using the Novel Idea of Scalar Prefix Search with Fast Table Updates},
year={2010},
volume={E93-D},
number={11},
pages={2932-2943},
abstract={Recently, we have proposed a new prefix lookup algorithm which would use the prefixes as scalar numbers. This algorithm could be applied to different tree structures such as Binary Search Tree and some other balanced trees like RB-tree, AVL-tree and B-tree with minor modifications in the search, insert and/or delete procedures to make them capable of finding the prefixes of an incoming string e.g. an IP address. As a result, the search procedure complexity would be O(log n) where n is the number of prefixes stored in the tree. More important, the search complexity would not depend on the address length w i.e. 32 for IPv4 and 128 for IPv6. Here, it is assumed that interface to memory is wide enough to access the prefix and some simple operations like comparison can be done in O(1) even for the word length w. Moreover, insertion and deletion procedures of this algorithm are much simpler and faster than its competitors. In what follows, we report the software implementation results of this algorithm and compare it with other solutions for both IPv4 and IPv6. It also reports on a simple hardware implementation of the algorithm for IPv4. Comparison results show better lookup and update performances or superior storage requirements for Scalar Prefix Search in both average and worst cases.},
keywords={},
doi={10.1587/transinf.E93.D.2932},
ISSN={1745-1361},
month={November},}
부
TY - JOUR
TI - IP Lookup Using the Novel Idea of Scalar Prefix Search with Fast Table Updates
T2 - IEICE TRANSACTIONS on Information
SP - 2932
EP - 2943
AU - Mohammad BEHDADFAR
AU - Hossein SAIDI
AU - Masoud-Reza HASHEMI
AU - Ali GHIASIAN
AU - Hamid ALAEI
PY - 2010
DO - 10.1587/transinf.E93.D.2932
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 11
JA - IEICE TRANSACTIONS on Information
Y1 - November 2010
AB - Recently, we have proposed a new prefix lookup algorithm which would use the prefixes as scalar numbers. This algorithm could be applied to different tree structures such as Binary Search Tree and some other balanced trees like RB-tree, AVL-tree and B-tree with minor modifications in the search, insert and/or delete procedures to make them capable of finding the prefixes of an incoming string e.g. an IP address. As a result, the search procedure complexity would be O(log n) where n is the number of prefixes stored in the tree. More important, the search complexity would not depend on the address length w i.e. 32 for IPv4 and 128 for IPv6. Here, it is assumed that interface to memory is wide enough to access the prefix and some simple operations like comparison can be done in O(1) even for the word length w. Moreover, insertion and deletion procedures of this algorithm are much simpler and faster than its competitors. In what follows, we report the software implementation results of this algorithm and compare it with other solutions for both IPv4 and IPv6. It also reports on a simple hardware implementation of the algorithm for IPv4. Comparison results show better lookup and update performances or superior storage requirements for Scalar Prefix Search in both average and worst cases.
ER -