주소 원거리 하나 이상의 ACL 범위에 대한 기준?인덱스는 IP에 대한 검색 알고리즘은 100 억의 IPv4와의 ACL 목록을 감안할 때 CIDR의 notiation의 범위 또는 두 개의 IP를 사이에
대부분의 ACL 범위 정의가 많은 수의 클래스 C 블록에 걸쳐 있다고 가정합니다.
해시 테이블을 통한 인덱싱 지점은 쉽지만 많은 포인트가 "행"목록에 포함되어 있는지를 감지 할 수있는 적절한 방법을 찾지 못했을 수 있습니다.
일정 수준의 세부 사항에 대한 색인 힌트와 같은 일부 생각이 들었습니다. 예를 들어 클래스 C 레벨에서 사전 계산을하면 그 지점을 덮고 있지만 테이블이 너무 큽니다. 또는 일종의 KD 트리를 동적으로 세부 수준을 설정합니다.
또한이 문제를 해결할 수있는 충돌 감지 알고리즘이있을 수 있다는 생각이 들었습니다.
올바른 방향의 힌트 또는 포인터가 있습니까?
Interval tree에서 특정 간격 또는 지점과 겹치는 모든 간격을 찾을 수 있습니다.
겹치지 않는 ip 범위의 경우 인덱싱 및 검색을 위해 b 트리 또는 컴팩트 시도 (Judy arrays (64-bits))를 사용할 수 있습니다 (시작 IP를 키로 저장하고 끝 IP를 값으로 저장).
인터넷 경로 조회에 사용 된 단순한 Radix Tree은 다른 작은 것들과 겹치는 더 큰 CIDR 서브넷을 나타내는 노드를 보유하도록 확장 될 수 있습니다. 가장 긴 일치 검색은 IP 주소와 일치하는 전체 CIDR 서브넷 집합을 가져 오기 위해 선택된 노드를 탐색합니다.
이제 동일한 트리에서 IP 범위를 유지하기 위해 convert each range into a set of CIDR subnets을 사용할 수 있습니다. 이 세트에는 많은 서브넷이있을 수 있지만 (심지어 일부 호스트 IP - 즉 IP/32 종류의 CIDR 주소) 항상 수행 할 수 있습니다.
40 억 개의 가능한 주소와 일치하는 100 억 개의 규칙이 있습니까?
40 억 개의 주소 테이블을 만듭니다. 100 억 개의 규칙 각각에 대해 적용되는 주소를 '페인트'하여 두 개 이상의 규칙이 같은 주소에 적용될 때 합리적인 조치를 취하십시오.