Xeraph@NCHOVY

RFC1071 - Computing the Internet checksum

계산해야 할 바이트가 A, B, C, D, ... , Y, Z 이렇게 있다고 가정하고, [a, b] 표기를 a * 256 + b인 16비트 정수로 정의하자. 그리고 +' 기호를 1의 보수 덧셈이라고 하면, 체크썸 계산은 아래와 같이 표현할 수 있다.

[A, B] +' [C, D] +' ... +' [Y, Z] (짝수 개인 경우)
[A, B] +' [C, D] +' ... +' [Z, 0] (홀수 개인 경우)

(IP 헤더 길이는 4바이트 단위로 표현되니 실제로는 짝수 개만 쓰겠지만)

(1) 교환, 결합 가능
위의 계산을 임의로 묶거나 순서를 바꿔서 수행해도 결과는 바뀌지 않는다.
가령 ([A, B] +' [C, D] +' ... [J, 0]) +' ([0, K] +' ... +' [Y, Z])

(2) 바이트 순서 독립성
[B, A] +' [D, C] +' ... +' [Z, Y] 로 나온 결과도 바이트 순서만 바뀔 뿐 동일하게 계산된다.

(3) 병렬 연산
1의 보수 덧셈이 교환 가능하므로 원래 [A, B] +' [C, D] +' [E, F] +' [G, H] 하던 것을
[A, B, C, D] +' [E, F, G, H] 하고 절반으로 접어서 다시 +' 해도 동일하게 계산된다.
여기에 2번 특성까지 더 하면 아무 순서대로 섞어서 머신 워드 단위로 계산할 수 있게 된다.

이쯤 되면 놀랍기도 하고 머리가 아프다 -_-..
못 믿겠다 싶으면 수식을 전개해보거나 RFC1071에 있는 예제를 들여다보시라..

이제 체크썸 계산을 아래와 같은 기법으로 빠르게 할 수 있다.

(1) 캐리 미루기
기계에 따라서는 덧셈부터 모조리 끝내고 캐리를 나중에 더하는게 효율적이다. 16비트 워드를 32비트 변수에 누적시켜서 계산을 해버리면 오버플로우는 상위 16비트에 쌓인다. 32비트 단위로 계산하는 것에 비해 2배로 계산을 해야하긴 하지만 오히려 이게 빠를 수 있다.

(2) 루프 풀기
코드가 좀 너절해 보일 수 있으나 루프 오버헤드를 줄이려고 내부의 덧셈을 풀어서 쓰기도 한다. 요새는 컴파일러가 해줄 수 있으니 확인 필요하겠다.

(3) 데이터 복사 묶기
특정 메모리에서 값을 복사하는 것도 버스가 느린 경우 심각한 오버헤드가 되는데 한 번에 두 개씩 처리해서 줄일 수 있다.

(4) 부분 업데이트
TTL처럼 일부 헤더값만 바뀌는 경우 부분 업데이트가 가능하다.
자세한 내용은 RFC1624를 참고한다. (+0, -0 으로 인해 주의할 경계 조건이 있음)
----
그런고로 아래와 같은 C 코드가 나오게 된 것이니..
while( count > 1 ) {
    /* This is the inner loop */
    sum += * (unsigned short) addr++;
    count -= 2;
}
/*  Add left-over byte, if any */
if( count > 0 )
    sum += * (unsigned char *) addr;

/*  Fold 32-bit sum to 16 bits */
while (sum>>16)
    sum = (sum & 0xffff) + (sum >> 16);

checksum = ~sum;

while이 왜 들어갔나 생각할 수 있는데, 접어서 더하고 난 뒤 캐리가 나오면 다시 더해야 하기 때문에 그렇다. IP 체크썸을 검증할 때는 IP 헤더를 다 더 해서 -0 (0xFFFF)이 나오게 된다. (보수를 저장했으므로)

요새는 NIC가 체크썸 계산을 오프로딩 해주기 때문에 별 생각 없이 넘기고 있었다 (..) 왜 굳이 1의 보수로 만들었나 했는데 흠..

TCP/IP Illustrated Vol 1. 내용 요약.

IP Fragmentation은 전송 중 데이터그램이 MTU보다 큰 경우 어디에서나 발생할 수 있다. 한 번 분할된 패킷이 다시 분할되는 것도 가능하다. (인덱스가 아니라 오프셋을 기록하니까) 그리고 전송 계층(TCP, UDP 등)은 IP Fragmentation에 대해서 모른다. 이것은 분할된 부분 중 하나라도 유실된다면 전체 데이터그램이 다시 전송되어야 함을 의미한다. IP 자체는 타임아웃이나 재전송이라는 개념이 없으니 상위 계층에서 전체를 다시 보내게 되는 것.

IP 헤더의 Identification 필드는 각 데이터그램의 식별 번호를 담고 있으며, Fragmentation 되는 경우에도 이 Id값은 그대로 복사된다. Fragment Offset만 바뀔 뿐이다. Total Length는 분할된 크기에 맞춰서 조정된다. 분할하는 크기는 항상 8의 배수로 정렬된다. 물론 마지막 부분은 예외. 마지막 부분을 제외하고는 Flags 필드의 More Fragments 비트가 켜진다.

Don't-Fragment 비트를 켜놓고 ICMP Fragmentation Required 응답을 관찰하는 것으로 경로 전체의 MTU 값을 계산할 수 있다. 구형 장비가 아니라면 ICMP 에러 응답 자체에 MTU 값이 쓰여서 돌아온다.

IP 계층은 데이터그램의 분할된 조각을 받은 경우 타이머를 시작시켜야 한다. 보통 30초에서 60초 정도 시간을 두고 나머지 조각을 받는다. 만약 시간 내에 모든 조각이 도착하지 않으면 전부 버려진다. 이렇게 버려지는 경우 ICMP time exceeded during reassembly 에러가 발생할 수 있는데, 여기에도 조건이 있다. 첫번째 조각이 도착하지 않으면 어차피 전송자가 에러를 받아도 프로세스와 연관시키는데 필요한 전송 계층 헤더가 없기 때문에, 그냥 ICMP 에러 응답 없이 조용히 버린다. 조건이 맞더라도 BSD 계열은 그냥 무시하도록 구현한 경우가 많다고 한다.

RFC 815: IP Datagram Reassembly Algorithm