Wrap-around된 수열을 정렬하는 방법

어떤 수의 값이 지정된 범위를 넘어갈 때 가장 작은 값으로 되돌아오는 것을 wrap-around라고 합니다. 예를 들어서, 어떤 자료형이 0부터 9의 범위를 가지고 wrap-around할 때, 이 자료형에 1씩 계속 더하면

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, ...

이와 같이 9 다음에 0의 값을 가지게 될 것입니다.

 

위성 데이터에 관한 표준 권고안인 CCSDS Blue Book에서는 위성 데이터가 여러 개의 패킷으로 분할되어 지상으로 전송되며, 각 패킷은 연속적으로 증가하는 Packet Sequence Count라는 값을 갖도록 되어 있습니다. 그러나 이 값은 무한히 증가할 수 없기 때문에, 최댓값 16383의 다음 패킷은 0의 sequence count를 갖게 됩니다. 즉, 16384에서 wrap-around합니다. 문서에서는 다음과 같이 설명하고 있습니다.

 

패킷이 위성에서 지상으로 전송될 때, 패킷 간의 순서는 보장되지 않습니다. 따라서, 지상에서는 수신한 패킷을 packet sequence count 값에 따라서 정렬해서 사용해야 합니다. 하지만 패킷에 기록된 sequence counter 값은 16384로 나눈 나머지이기 때문에, 단순한 정렬로는 제대로 정렬을 수행할 수 없습니다.

Packet	P0	P1	P2	P3	P4	P5	P6	P7
실제 counter	16380	16381	16382	16383	16384	16385	16386	16387
Packet Sequence Count 필드 값	16380	16381	16382	16383	0	1	2	3

이렇게 여덟 개의 패킷이 전송된 경우, Packet Sequence Count 필드 값을 기준으로 정렬을 수행하면

P4, P5, P6, P7, P0, P1, P2, P3

의 이상한 순서가 되어 버릴 것입니다.

 

이러한 경우에 제대로 정렬을 수행하기 위해서는 먼저 한 가지 가정이 필요합니다. 패킷의 순서가 완전히 뒤죽박죽이 되어서는 안 된다는 것입니다. 조금 더 formal하게 기술해 보면, n번째에 생산된 패킷이 m번째로 수신되었을 때, 어떤 양의 정수 K에 대해서 |n - m| < K여야 한다는 것입니다. 이런 조건이 만족된다고 할 때, 패킷은 두 가지 중요한 정보를 갖게 됩니다. 바로 수신 순서와 Packet Sequence Count 값입니다. 즉, 수신 순서라는 부가적인 정보를 통해 Packet Sequence Count가 갖고 있는 불완전한 정보를 보완할 수 있습니다.

 

패킷의 실제 순서를 복원하기 위해서는 K 값에 일정한 조건이 필요합니다. (N은 wrap-around가 일어나는 최댓값입니다. 위의 예에서는 N = 16384입니다.)

• 같은 Packet Sequence Count 값을 갖는 패킷들 사이의 순서는 실제 패킷 순서와 같아야 합니다. 그렇지 않으면 패킷의 실제 순서를 복원할 수 없습니다. 이를 만족하기 위해서는, K < N / 2여야 합니다.
• 어떤 패킷을 기준으로 앞뒤 2t개의 패킷 중 같은 Packet Sequence Count 값을 갖는 패킷은 한 개만 존재할 수 있어야 합니다. 이렇게 되면 t 크기의 window 내에서는 Packet Sequence Count를 이용해서 비교하고, 그 밖에서는 수신 순서를 가지고 비교할 수 있습니다. 이를 만족하기 위해서는 K < (N - 2t) / 4이어야 합니다.

이러한 조건을 만족하는 패킷들의 리스트가 있을 때, 이를 정렬하기 위해서 다음과 같은 비교 함수를 작성할 수 있습니다. (reception_index는 수신 순서를, sequence_count는 Packet Sequence Count 필드의 값을 의미합니다.)

 

bool compare(const Packet& a, const Packet& b) {
    if (a.reception_index + t < b.reception_index) {
        return true;
    } else if (b.reception_index + t < a.reception_index) {
        return false;
    } else if (a.sequence_count < b.sequence_count) {
        return a.sequence_count + N / 2 > b.sequence_count;
    } else {
        return a.sequence_count - N / 2 > b.sequence_count;
    }
}

 

비교 대상인 두 패킷 a와 b의 수신 index가 t 이상 떨어져 있으면, 두 패킷의 순서는 수신 순서를 통해 알 수 있습니다. 만약 수신 순서가 t 이내로 인접해 있다면, 두 패킷의 원래 counter 값은 N / 2 이상 차이나지 않을 것입니다. 따라서, N / 2 이상 차이나는 경우는 wrap-around가 일어난 경우로 간주할 수 있습니다.