검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

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

IP Lookup Using the Novel Idea of Scalar Prefix Search with Fast Table Updates 빠른 테이블 업데이트를 통해 스칼라 접두사 검색이라는 새로운 아이디어를 사용한 IP 조회

Mohammad BEHDADFAR, Hossein SAIDI, Masoud-Reza HASHEMI, Ali GHIASIAN, Hamid ALAEI

  • 조회수

    0

  • 이것을 인용

요약 :

최근에 우리는 접두사를 스칼라 숫자로 사용하는 새로운 접두사 조회 알고리즘을 제안했습니다. 이 알고리즘은 이진 검색 트리와 같은 다른 트리 구조와 RB-트리, AVL-트리 및 B-트리와 같은 다른 균형 트리에 적용할 수 있으며 검색, 삽입 및/또는 삭제 절차를 약간 수정하여 찾을 수 있습니다. 들어오는 문자열의 접두사(예: IP 주소). 결과적으로 검색 절차가 복잡해집니다. O (로그 n) 어디에 n 트리에 저장된 접두사의 수입니다. 더 중요한 것은 검색 복잡성이 주소 길이에 좌우되지 않는다는 것입니다. w 즉, IPv32의 경우 4이고 IPv128의 경우 6입니다. 여기서는 메모리에 대한 인터페이스가 접두사에 액세스할 수 있을 만큼 충분히 넓으며 비교와 같은 일부 간단한 작업이 다음에서 수행될 수 있다고 가정합니다. O (1) 단어 길이에도 불구하고 w. 또한, 이 알고리즘의 삽입 및 삭제 절차는 경쟁사에 비해 훨씬 간단하고 빠릅니다. 다음에서는 이 알고리즘의 소프트웨어 구현 결과를 보고하고 이를 IPv4 및 IPv6에 대한 다른 솔루션과 비교합니다. 또한 IPv4용 알고리즘의 간단한 하드웨어 구현에 대해서도 보고합니다. 비교 결과는 평균 및 최악의 경우 모두에서 스칼라 접두사 검색에 대한 더 나은 조회 및 업데이트 성능 또는 우수한 스토리지 요구 사항을 보여줍니다.

발행
IEICE TRANSACTIONS on Information Vol.E93-D No.11 pp.2932-2943
발행일
2010/11/01
공개일
온라인 ISSN
1745-1361
DOI
10.1587/transinf.E93.D.2932
원고의 종류
Special Section PAPER (Special Section on Architectures, Protocols, and Applications for the Future Internet)
범주

작성자

키워드