그래서, 흐름을 식별하기 위해 4 개의 튜플 IP와 포트를 해시하는 데 사용할 다른 해시 함수를 찾고 있습니다. 내가 건너 온src에 대한 해시 함수 dest ip + port
하나는
((size_t)(key.src.s_addr) * 59)^
((size_t)(key.dst.s_addr))^
((size_t)(key.sport) << 16)^
((size_t)(key.dport))^
((size_t)(key.proto));
지금 내 인생, 내가 사용하는 소수 (59)을 설명 할 수 있었다. 왜 31이 아니며, 2의 거듭 제곱으로 스포츠를 곱하면 어째서 엉망이됩니다. IP 주소에 사용할 더 나은 해시 함수가 있습니까?
한 소수에 소수를 곱하면 다른 유사한 연산이 그 위에 누적 될 때 더 높은 고유 확률을 보이는 경향이 있기 때문에 소수를 사용합니다. 특정 값 (59)은 임의로 선택되거나 의도적 일 수있다. 말할 수 없습니다. 가능성이 가장 높은 투입물에 근거하여보다 나은 가치 분배를 창출하는 경향이있을 수있다.
포트가 2^16 범위로 제한되어 있기 때문에 16 시프트가 발생할 수 있습니다. 이 기능은 대상 포트를 하단에두고 소스 포트를 비트 필드의 상위 부분으로 이동하는 것처럼 보입니다. 나는 이것이 다음 단락에서 더 설명 될 수 있다고 생각한다.
곱셈이 발생하는 또 다른 이유는 (또한 시프트 연산에도 해당됩니다) 해시 함수의 연관성을 파괴하기 때문입니다. IP 주소 src = 192.168.1.1과 dst = 192.168.1.254는 src = 192.168.1.254 및 dst = 192.168.1.1 (스왑 된)과 동일한 값으로 해시됩니다 (배타적 논리합).
균일 한 분포를 위해 함수의 출력을 검사하십시오. 당신이 그것을 좋아하지 않는다면, 당신이 좋아하는 배포판을 얻을 때까지 몇 가지 다른 소수를 연결하십시오. 해싱은 '옳은'대답이없는 매우 어두운 미술 일 수 있습니다.
예프. 대부분의 경우,이 특정 기능은 테스트 데이터에 대해 여러 가지 기능을 테스트하고 최상의 결과를 얻은 것을 확인한 결과 발생했습니다. –
개인적으로 4 비트의 IP 바이트를 부호없는 long으로 읽는 것이 좋을 것입니다. 그러면 대략 0 - 2^32-1 범위의 수를 얻을 수 있습니다. 그런 다음 한 번에 활성 상태로 만들려는 플로우의 수를 알아 내면 인덱스 테이블 크기가됩니다.
예를 들어 2000을 가져옵니다. 즉, 2^32 숫자를 대략 2^11의 indeces (정보를 전달하기 위해)로 매핑하려고합니다. 100 %로 채워지면 해시가 거의 작동하지 않으며 심지어 90 %가 어려울 수 있기 때문에 해킹이 제대로 작동하지 않습니다. 50 % (4000 indeces) 또는 25 % (8000)까지만 채울 수있는 인덱스 테이블을 사용하면 오늘날의 추억에 별다른 영향을 미치지 않습니다.
인덱스 테이블의 정확한 크기는 고르지 않은 위치 번호 여야하며, 소수점이 바람직합니다. 이는 충돌을 처리하기 위해 오버 플로우 처리 (인덱스 테이블의 동일한 위치에 대한 해싱 포인트 이후의 두 개 이상의 IP 번호)를 처리해야 할 가능성이 높기 때문입니다. 오버플로 처리는 인덱스 테이블 크기보다 작은 다른 소수이어야합니다. 이 모든 소수! 어쨌든 그들과 함께 무엇입니까?
I는 (C)에서 일례로 도시 한 것이다 :
idxsiz = prime(2000 * 2); // 50% loading
ovfjmp = prime(idxsiz/3);
...
처음에 (-1)로 마킹 UNUSED idxjmp 위치의 테이블을 채운다. DELETED 표시를 준비하십시오 (-2).
당신의 IP 번호는 시스템을 입력하고 (또는 존재하지 않을 수있다)의 흐름 기록을 찾습니다
stoppos = ip % idxsiz; /* modulo (division) just this once */
i = stoppos;
do
{
if (index[i] == UNUSED) return NULL;
if (index[i] != DELETED)
{
flowrecptr = &flow_record[index[i]];
if (!flowrecptr->in_use) {/* hash table is broken */}
if (flowrecptr->ip == ip) return flowrecptr;
}
i += ovfjmp;
if (i >= idxsiz) i -= idxsiz;
}
while (i != stoppos);
return NULL;
하지 않는이 인덱스가 사용 된 적이있는 마커 역할을하고 검색이 중지해야 . DELETED는이 색인이 사용되었지만 더 이상 사용되지 않았다는 표시입니다. 즉, 검색을 계속해야 함을 의미합니다.
이것은 얻으려는 시도였습니다. 당신은 UNUSED 나 DELETED가 포함 된 첫 번째 인덱스 위치를 찾음으로써 시작하는 put을 할 필요가 있으므로 get로부터 NULL을 얻을 수 있습니다. 이 값을 flow_record 테이블의 첫 번째/다음 빈 행 인덱스로 대체하십시오. 행을 in_use로 표시하십시오. 원래 IP 번호를 flow_record 행의 ip b 버에 넣으십시오.
이것은 매우 간단하지만 매우 효과적인 해싱 메커니즘을 구성하는 방법입니다. 실질적으로이 함수 나 함수가 실패한 후에 사용되는 특별한 함수 형태의 최적화는 해싱의 효율성을 향상시킵니다.
소수를 사용하면 모든 색인 위치가있는 최악의 경우에 메커니즘이 모든 단일 위치를 테스트합니다. 이를 설명하기 위해 : idxsiz가 ovfjmp로 균등하게 나눌 수 있다고 가정 해 보겠습니다. 오버 플로우 처리가 많지 않습니다. 35 및 7은 인덱스가 0으로 점프되기 전에 테스트되는 위치 0,7,14,21 및 28이되고, while 테스트는 검색을 중지하게합니다.
---------------------- OOPS!
나는 당신이 포트 번호를 원했음을 놓쳤다. ip V4는 6 바이트의 주소를 의미합니다. 이를 부호없는 64 비트 정수로 읽고 상위 16 비트/2 바이트를 지 웁니다. 그런 다음 모듈로 계산을 수행합니다.
브라이언 기드온은 거의 그것을 요약합니다. 곱셈과 시프트는 대칭 차단기로 사용됩니다. 따라서 이것은 기계 A의 가상의 경우를 기계 B의 telnetting으로, 그 반대의 경우를 포착하고, 일시적인 동일한 포트 넘버를 선택하게됩니다. 아주 흔하지는 않지만 불가능한 것은 아닙니다. 5- 튜플의 대부분은 매우 일정합니다. 프로토콜은 매우 작은 도메인에서 제공되며 {address, portnum}의 절반도 마찬가지입니다.
소문자 크기의 해시 테이블을 가정하면 마법 상수 59는 소수 IMO로 바뀔 수 있습니다. (포트 < < 16)도 비트가 없거나 (포트 * some_other_prime) 용어에 의해 다른 시프트로 대체 될 수 있습니다.
2의 2의 비중의 해시 테이블의 경우, 5-tuple의 모든 멤버 (마이너스 1)에 (소수) 소수를 곱셈 해주세요. (예전에는 비싼 비용으로 옵션이 나왔을 때)
그래서 각 ip에 소스 대신 프라임을 곱하면 어떨까요? – creatiwit
해시 함수는'(a * P)^(b * P) = (b * P)^(a * P)'이기 때문에 다시 연관성이 있습니다. 비슷한 일을하기 위해 두 개의 가상 번호가 함께 작동하는 것이 일반적이지만 –