리눅스에서 응답과 appliction의 요청이 온라인으로 일치 함 커널

Question

Netfilter의 훅을 사용하여 호스트의 모든 수신 및 송신 패킷을 검사하는 Linux 커널 모듈을 구현했습니다. 이 모듈을 사용하면 해당 호스트에서 실행중인 특정 응용 프로그램의 흐름을 모니터링 할 수 있습니다. 즉, src/dst 포트/IP를 알면 해당 패킷을 수신/전송할 때 필터링 (분류) 할 수 있습니다.

내가 수행하고자하는 작업은 들어오는 응용 프로그램의 요청에 해당하는 보내는 응답을 런타임에 일치시키는 것입니다. 각 요청/응답은 src/dst IP 및 고유 ID로 식별됩니다.

순진 구현은 흐르는 :

• 스토어 나가는 각 응답의 경우 목록의 각 들어오는 요청 (배열/연결리스트 등)
• : 스루
  • 검색 일치하는 요청을 찾기위한 목록. 요청이 발견되면 목록에서 제거하십시오.
• X 초보다 오래된 요청을 제거하려면 요청 목록을 정기적으로 정리하십시오.

문제는 모든 응답이 순진 알고리즘은 일치를 식별하기 위해 요청 목록을 통해 선형 검색을 필요로한다는 것이다. 이것은 높은 비용으로 비싸다.

복잡성을 줄일 수있는 알고리즘을 제안 해 주시겠습니까? 성능을 유지하기 위해 정밀도를 희생 (일부 일치하지 않음)해도 좋습니다.

감사합니다.

Answer 1

해시 테이블을 사용하여 조회 작업을 줄일 수 있습니다. Linux 커널 3.7 이상에서는 일반 해시 테이블 implementation을 커널 모듈에서 사용할 수 있습니다. 그것은 매우 사용하기 쉬운 기능을 가지고 있습니다.

src/dest ip & 포트 + 고유 ID를 요청하고이를 해시 테이블에서 사용하는 해시 테이블은 각 키에 대한 값을 저장해야하며 값은 실제에 대한 포인터가 될 수 있습니다 요청 페이로드. 그것의 구현을 기반으로 O (n)의 최악의 경우를 가질 수 있지만 채우기 인자가 좋은 해시 테이블은 O (1) 또는 O (logN)를 쉽게 얻을 수 있습니다.

더 많은 최적화를 위해 블룸 필터를 사용할 수 있습니다. 블룸 필터는 유효하지 않거나 삭제 된 요청을 필터링하는 데 사용할 수 있습니다. 매우 빠르고 해시 테이블과 같은 메모리 액세스 패널티가 없습니다. 그러나 해시 테이블과 달리 각 키의 값을 저장하지 않으므로 해시 테이블도 필요합니다. 리눅스 커널 블룸 필터 구현이 있습니다.