일련번호 산술
Serial number arithmetic많은 프로토콜과 알고리즘은 관련 실체의 일련화 또는 열거가 필요하다.예를 들어, 통신 프로토콜은 어떤 패킷이 어떤 다른 패킷에 "이전"으로 오는지 또는 "이후"로 오는지 반드시 알아야 한다.IETF(인터넷 엔지니어링 태스크포스) RFC1982는 이러한 시퀀스 번호를 조작하고 비교할 목적으로 "시리얼 번호 산술"을 정의하려고 시도한다.
대부분의 알고리즘은 시퀀스 번호에 고정 크기(이진수) 표현을 사용하기 때문에 이 작업은 처음에 나타날 수 있는 것보다 다소 복잡하다.알고리즘은 숫자가 너무 커져서 마지막으로 한 번 더 증가되고 최대 숫자 범위를 중심으로 "파열"되지 않는 것이 중요하다(큰 양수에서 0 또는 큰 음수로 즉시 이동).일부 프로토콜은 문제가 발생하기 전에 프로그램이 교체(또는 폐기)되기를 바라면서(Y2K 참조) 이러한 문제를 무시하고 카운터에 매우 큰 정수를 사용하기로 선택한다.
많은 통신 프로토콜은 슬라이딩 윈도우 프로토콜의 구현에서 패킷 시퀀스 번호에 일련번호 산술을 적용한다.TCP의 일부 버전에서는 래핑된 시퀀스 번호(PAWS)에 대한 보호를 사용한다. PAWS는 시퀀스 번호의 고차 비트의 확장으로 타임스탬프를 사용하여 패킷 타임스탬프에 동일한 일련 번호 산술을 적용한다.[1]
시퀀스 번호에 대한 작업
시퀀스 번호에 작은 양의 정수만 추가하고 두 시퀀스 번호를 비교하는 것이 논의된다.RFC(이하 "SERIAL_BITS") 전체에서 비트 단위로 임의의 크기를 기록하면서 서명되지 않은 바이너리 구현만 논의된다.
덧셈
시퀀스 번호에 정수를 추가하는 것은 단순한 부호 없는 정수 추가에 이어 결과를 범위(대개 대부분의 아키텍처에서 부호 없는 추가에 함축적임)로 되돌리기 위한 부호 없는 모듈로 작업이 뒤따른다.
- s' = (s + n) 모듈로SERIAL_BITS 2
0보다 작거나SERIAL_BITS−1 2 - 1보다 큰 값의 추가는 정의되지 않았다.기본적으로 이 범위를 초과하는 값을 추가하면 결과 시퀀스 번호가 "wrap"이 되고 (종종) 원래 시퀀스 번호 "보다 작다"고 간주되는 숫자가 발생한다.
비교
두 시퀀스 번호 i와1 i2(서열 번호 s와1 s의2 부호 없는 정수 표현)를 비교하는 수단이 제시된다.
평등은 단순한 수적 평등으로 정의된다.
비교를 위해 제시된 알고리즘은 복잡하며, 첫 번째 시퀀스 번호가 값 범위의 "끝"에 가까운지 여부를 고려해야 하며, 따라서 더 작은 "포장" 번호는 실제로 첫 번째 시퀀스 번호보다 "더 큰" 것으로 간주될 수 있다.따라서 나는1 단지 나보다2 더 적은 것으로 간주된다.
- (i1 < i와2 i2 - i < 21SERIAL_BITS−1) 또는
- (i1 > i와2 i1 - i > 22SERIAL_BITS−1)
부족액
RFC에 의해 제시된 알고리즘에는 적어도 하나의 중요한 단점이 있다: 비교가 정의되지 않은 시퀀스 번호가 있다.다수의 독립적인 협력 당사자들에 의해 많은 알고리즘이 독립적으로 구현되기 때문에, 그러한 모든 상황이 발생하는 것을 막는 것은 종종 불가능하다.
RFC 1982의 저자들은 일반적인 해결책을 제시하지 않고 다음과 같이 인정한다.
모든 값 쌍에 대해 정의되는 동안 불평등이 이 놀라운 속성을 갖지 않도록 시험을 정의할 수는 있겠지만, 그러한 정의는 구현하는 데 불필요하게 부담이 되고 이해하기 어려울 것이며, 여전히 다음과 같은 경우를 허용할 수 있을 것이다.
s1 < s2 및 (s1 + 1) > (s2 + 1)그건 그냥 비흡연일 뿐이지
따라서 문제 사례는 정의되지 않은 채 방치되며, 구현은 결과를 반환하거나 오류를 표시할 수 있으며, 사용자는 특정 결과에 의존하지 않도록 주의해야 한다.보통 이것은 그러한 특정한 한 쌍의 숫자들이 공존하는 것을 허용하지 않는다는 것을 의미할 것이다.
따라서 시퀀스 번호의 모든 "정의되지 않은" 비교를 피하는 것은 종종 어렵거나 불가능하다.그러나 비교적 간단한 해결책이 있다.서명되지 않은 시퀀스 번호를 서명된 두 개의 보완 산술 연산에 매핑함으로써, 모든 시퀀스 번호의 모든 비교를 정의하고, 비교 연산 자체를 극적으로 단순화한다.RFC에 의해 명시된 모든 비교는 원래 진리 값을 유지하며, 이전에 "정의되지 않은" 비교만 영향을 받는다.
일반용액
RFC 1982 알고리즘은 N-비트 시퀀스 번호에 대해 "보다 큼"으로 간주되는 2N−1 - 1 값과 "보다 작음"으로 간주되는 2N−1 - 1 값이 있음을 명시한다.나머지 값(정확히 2-distantN−1)과의 비교는 "정의되지 않은" 것으로 간주된다.
대부분의 현대 하드웨어는 서명된 두 개의 보완적인 이진 산술 연산을 구현한다.이러한 연산은 주어진 피연산자에 대한 값의 전체 범위에 대해 완전히 정의된다. N-비트 이진수에는 2개의N 구별되는 값이 포함될 수 있고, 그 중 하나가 값 0에 의해 차지되기 때문에 0이 아닌 모든 양수와 음수에 대해 홀수 수가 남아 있기 때문이다.단지 긍정적인 숫자보다 부정적인 숫자가 더 많을 뿐이다.예를 들어 16비트 2의 보완 값은 -32768 ~ +32767 범위의 숫자를 포함할 수 있다.
따라서 단순히 시퀀스 번호를 2의 보완 정수로 재캐스팅하고 "보다 작음"으로 간주되는 시퀀스 번호가 "보다 큼"으로 간주되는 것보다 한 개 더 많도록 허용한다면, 우리는 RFC가 제안한 논리적으로 불완전한 공식 대신 간단한 서명된 산술 비교를 사용할 수 있어야 한다.
다음은 일부 무작위 시퀀스 번호와 숫자 0을 비교한 몇 가지 예(16비트, 다시 한 번)이다.
서명되지 않은 이진 서명 시퀀스 값 거리 ---------------------------------------------------------------------- 32767 = 0x7FF == 32767 1 == 0x0001 == 1 0 = 0x00 = 0 65535 == 0xFFFF == -1 65534 == 0xFFE == -2 32768 == 0x8000 == -32768
시퀀스 번호에 대한 서명된 해석의 순서가 올바른지 쉽게 알 수 있으며, 문제의 시퀀스 번호를 "회전"하여 0이 우리가 비교하는 시퀀스 번호와 일치하도록 하는 한, 쉽게 알 수 있다.이것은 단순히 서명되지 않은 뺄셈을 사용하고 그 결과를 단순히 서명된 두 개의 보완 숫자로 해석하는 것으로 밝혀졌다.결과는 두 시퀀스 번호 사이에 서명된 "거리"이다.다시 한 번 말하지만i1그리고i2시퀀스 번호 s와1 s의2 서명되지 않은 이항 표현, s에서1 s까지의2 거리는
거리를 두다 = (서명된)(i1 - i2) 거리가 0이면 숫자는 같다.만약 그것이 < 0이라면, s는1 "보다 작다" 또는 "이전" s2. 단순하고 깨끗하고 효율적이며 완전히 정의된다.하지만, 놀라운 일이 없는 것은 아니다.
모든 시퀀스 번호 산술은 시퀀스 번호의 "포장"을 다루어야 한다. 숫자 2는N−1 RFC 1982 시퀀스 번호 항에서 양방향으로 동일하다.우리의 수학에서, 그들은 둘 다 서로 "낮은" 것으로 간주된다.
거리1 = (서명된)(0x8000 - 0x0) == (서명된)0x8000 == -32768 < 0 거리2 = (서명된)(0x0 - 0x8000) == (서명된)0x8000 == -32768 < 0 이는 두 시퀀스 번호 사이의 거리가 0x8000인 경우 모두 해당된다.
더욱이, 두 개의 보완 산수를 사용하여 일련 번호 산술을 구현하는 것은 일반적으로 16비트, 32비트, 64비트 등 기계 정수 크기와 일치하는 비트 길이의 일련 번호를 의미한다.20비트 일련 번호 구현 시 교대(32비트 인트로 가정):
거리를 두다 = (서명된)((i1 << 12) - (i2 << 12)) 
