ipv6에 가장 긴 프리픽스 일치를 구현하는 가장 좋은 방법은 무엇입니까?

Question

ipv6 라우터는 주소의 첫 번째 n 비트로 여러 경로를 저장합니다. 2000 년 연구자들은 1500 개의 ipv6 경로에서 14 개의 고유 한 접두어 길이를 발견했습니다. 들어오는 패킷은 가장 긴 접두사 일치에 따라 다른 발신 포트로 라우팅되므로 패킷 x의 처음 8 비트가 8 비트 경로와 일치하지만 동일한 패킷의 처음 48 비트가 48 비트 경로와 일치하면 라우터는 48 비트 경로.

라우터가 너무 많은 패킷을 처리하므로 라우팅 테이블에 대한 메모리 검색 속도가 제한적입니다. 내 라우팅 테이블에서 가장 긴 일치하는 접두사를 찾는 좋은 알고리즘은 무엇입니까?

Answer 1

"표준"접두사를 저장하려면 trie 또는 radix-tree을 사용하십시오. 접미어 트리/배열은 불필요한 오버 킬입니다. 중 하나 인 사이의 일치 항목을 찾는 데 사용됩니다 (어떤 접미사도 접미어의 접두어이며 여러 문자열 간의 일치를 찾으려면 접두사 사이뿐만 아니라 여러 문자열을 서로 연결해야 함).

Answer 2

내가 일반적으로 가장 긴 일반적인 접두사를 계산하는 가장 효율적인 방법을 믿는 suffix tree 또는 suffix array (런타임 전처리 후 접두사의 길이 선형)입니다.

Answer 3

일부 여분의 메모리가 있습니까?

이 구조 다음과 같이하십시오 :

typedef struct node { 
    struct node* table[256]; 
    Port_type port; 
} Node; 
Node* root[256]; 

지금 당신과 같이 검색을 수행 할 수 있습니다

Node* table = root; 
for (i=0; table != NULL; i++) 
{ 
    node = table[address_byte[i]]; 
    table = node->table; 
} 
destination = node->port; 

Answer 4

나는이 주제에 cool paper을 발견 Longest Prefix Matching using Bloom Filters을했다.

초록 : 우리는 가장 긴 접두사 매칭 (LPM)을 위해 블룸 필터를 사용하는 것을 알고있는 첫 번째 알고리즘을 소개합니다. 이 알고리즘은 접두사 길이별로 정렬 된 접두사 집합에서 주소 접두사 구성원을 결정하기 위해 구성원 쿼리에 대한 효율적인 데이터 구조 인 Bloom 필터에 대한 병렬 쿼리를 수행합니다. 인터넷 프로토콜 (IP) 라우팅 조회에이 알고리즘을 사용하면 검색 엔진이 TCAM 기반 접근 방식보다 우수한 성능과 확장 성을 제공한다는 것을 알 수 있습니다.

기본적인 생각은 프로세서의 내장 SRAM (빠른)에 저장된 블룸 필터를 사용하여 더 느리지 만 풍부한 메모리에서 접두사 해시 테이블 조회를 유도하는 것입니다. IPv4의 경우 라우팅 테이블 접두어의 대부분이 24 비트라는 사실을 설명하기 위해 알고리즘을 조정합니다. IPv6의 경우 1550 BGP 항목에서 14 개의 고유 한 프리픽스 길이 만 발견되었습니다.