요약

프레임의 끝을 알리는 방법은 세 가지다. 끝에 정해 둔 글자를 두는 보초 방법, 앞에 길이를 적는 바이트 수 방법, 비트 모양 깃발을 쓰는 비트 채우기다. 셋의 차이는 “데이터를 무엇으로 보느냐”(글자인가, 임의의 비트인가)와 “끝 표시가 깨졌을 때 무슨 일이 생기느냐”다.

어느 쪽일까

1. 보낼 데이터가 바이트로 딱 나뉘지 않는 임의의 비트열이다.

비트 채우기(HDLC). 깃발과 채우기가 비트 단위라 데이터 길이가 8의 배수일 필요가 없다. 보초 방법과 바이트 수 방법은 바이트(글자) 단위다.

2. 받는 쪽이 본문을 다 받기 전에 프레임 길이를 알아 버퍼를 미리 잡고 싶다.

바이트 수 방법(DDCMP). 헤더의 Count로 길이를 먼저 안다. 보초 방법과 비트 채우기는 끝 표시를 만날 때까지 길이를 모른다.

3. 본문이 거의 모두 ETX·DLE 글자로 된 이상한 데이터다. 오버헤드가 가장 걱정이다.

바이트 수 방법. 보초 방법은 그런 글자마다 DLE를 붙여 본문이 두 배까지 는다. 바이트 수 방법은 데이터와 상관없이 Count 칸 하나만 더한다.

결정적 차이

세 방법을 다섯 가지 기준으로 나란히 놓으면 다음과 같다1.

  보초 방법 (BISYNC) 바이트 수 방법 (DDCMP) 비트 채우기 (HDLC)
데이터를 보는 단위 글자(바이트) 글자(바이트) 비트
끝을 아는 방법 ETX 글자 앞의 Count 깃발 01111110
본문과 끝 표시가 겹치는 문제 DLE를 붙여 피함 없음 1 다섯 개 뒤 0을 끼워 피함
최악의 오버헤드 본문 2배 Count 칸 하나 본문의 20%
끝 표시가 깨지면 다음 ETX까지 이어 읽음 엉뚱한 곳에서 자름(CRC로 검출) 다음 깃발까지 이어 읽음

아래 다섯 소절은 표의 줄을 하나씩 숫자 예로 푼 것이다. 예는 바이트 중심 프레이밍과 비트 채우기에 나온 것과 같다2.

데이터를 보는 단위

보초 방법과 바이트 수 방법에서 받는 쪽은 비트를 8개씩 끊어 바이트로 읽는다. 끝 표시 ETX와 확장 글자 DLE는 바이트 하나짜리 글자이고, Count는 본문이 몇 바이트인지 센다. 그래서 본문 길이가 8의 배수여야 한다.

13비트 본문 0111111111110을 예로 들자. 8비트씩 끊으면 1바이트와 5비트가 남는다. 바이트 수 방법의 Count에는 “1바이트와 5비트”를 적을 방법이 없다. 남은 5비트 뒤에 0을 3개 채워 2바이트로 보낼 수는 있다. 그러면 받는 쪽은 마지막 3비트가 채운 것이라는 사실을 따로 전해 들어야 한다.

비트 채우기는 깃발도 채우기도 비트 단위다. 그래서 13비트를 그대로 받아, 0 두 개를 끼운 15비트로 만들고, 깃발까지 붙여 31비트로 보낸다.

끝을 아는 방법

보초 방법은 본문의 바이트마다 “ETX인가”를 묻는다. ETX는 16진수 03, 비트로 00000011이다. 비트 채우기는 비트마다 카운터를 올리며 깃발 01111110이 나오기를 기다린다. 두 방법 모두 끝 표시를 만나야 비로소 그 프레임이 몇 바이트(몇 비트)였는지 안다.

바이트 수 방법만 본문을 받기 전에 길이를 안다. Count가 5면 받는 쪽은 “앞으로 5바이트가 본문”임을 미리 안다. 그래서 받은 본문을 담아 둘 메모리 자리(버퍼)를 처음부터 정확히 5바이트만 잡을 수 있다. 앞의 “어느 쪽일까” 2번 상황이 이 차이에서 나온다.

본문과 끝 표시가 겹치는 문제

가운데 바이트 03이 ETX와 같은 값인 본문 41 03 42를 세 방법으로 보내면 차이가 드러난다.

  • 보초 방법: 03 앞에 DLE를 붙여 41 DLE 03 42 ETX를 보낸다. 받는 쪽은 DLE 다음의 03을 끝이 아니라 데이터로 받는다.
  • 바이트 수 방법: Count에 3을 적고 41 03 42를 그대로 보낸다. 받는 쪽은 세 바이트를 세기만 하고 값은 보지 않으니, 03이 무엇과 같든 상관없다.
  • 비트 채우기: 41 03 42를 비트로 쓰면 01000001 00000011 01000010이다. 1이 많아야 두 개 이어지니 끼울 0이 하나도 없다. 비트 채우기가 0을 끼우는 것은 0111111111110처럼 1이 다섯 개 넘게 이어지는 본문이다.

바이트 수 방법에도 겹치는 값이 하나 숨어 있다. 프레임의 시작을 알리는 SYN(16)이다. 본문에 16이 있어도 평소에는 아무 일이 없다. 받는 쪽이 Count를 믿고 세기만 하기 때문이다. 하지만 Count가 깨져 받는 쪽이 다음 프레임의 시작을 찾아 SYN을 뒤질 때는, 본문 속 16에 속을 수 있다. 이 일은 아래 “끝 표시가 깨지면”에서 다시 나온다.

최악의 오버헤드

오버헤드는 본문 말고 더 보내야 하는 양이다.

  • 보초 방법: 본문의 ETX·DLE마다 DLE 1바이트가 붙는다. 본문이 DLE 10개면 20바이트에 끝 ETX까지 21바이트를 보내니, 본문 길이의 두 배가 넘는다. 무작위 바이트라면 한 바이트가 ETX나 DLE일 확률이 \(\frac{2}{256}\)라 평균 약 0.8%만 는다.
  • 바이트 수 방법: 본문 내용과 상관없이 Count 14비트가 늘 붙는다. 본문이 10바이트든 1만 바이트든 같다.
  • 비트 채우기: 1 다섯 개마다 0 한 비트가 붙는다. 1만 40개인 본문은 0이 8개 붙어 48비트(20%)가 된다. 무작위 비트라면 평균 약 1.6%다.

두 채우기 방법은 최악의 입력이 서로 다르다. 바이트 FF(비트 11111111) 10개는 보초 방법에게 평범한 데이터라 한 바이트도 늘지 않는다. 비트 채우기에게는 1이 80개 이어진 것이라 0이 16개(20%) 끼어든다. 반대로 DLE(10, 비트 00010000) 10개는 보초 방법에서 10바이트를 늘리지만, 1이 이어지지 않으니 비트 채우기에서는 한 비트도 늘지 않는다.

끝 표시가 깨지면

프레임 네 개를 이어 보내는데, 첫 프레임의 끝 표시(바이트 수 방법은 Count)가 전송 중에 깨졌다고 하자. 받는 쪽이 각 방법의 규칙대로 자르면 결과는 아래와 같다.

그림

네 줄이 네 가지 경우다. 줄마다 막대가 보낸 프레임 네 개이고, 주황 칸이 깨진 자리다. 막대 아래 괄호는 받는 쪽이 한 덩어리로 자른 구간이다. 초록 “정상”은 CRC 검사를 통과한 덩어리, 주황 “버림”은 CRC가 맞지 않아 버린 덩어리, 회색 점선 “건너뜀”은 다음 프레임의 시작을 찾느라 버린 바이트다. 오른쪽 끝의 숫자가 잃은 프레임 수다. 첫째 줄은 2개, 둘째 줄은 1개, 셋째 줄은 3개, 넷째 줄은 1개다3.

첫째 줄, 보초 방법. 첫 프레임의 ETX 03(00000011)이 한 비트 뒤집혀 07(00000111)이 되었다.

  1. 받는 쪽은 07을 ETX로 알아보지 못하고 데이터로 받는다.
  2. 프레임 1의 CRC 두 바이트, 프레임 2의 SYN·SOH·헤더·STX도 DLE나 ETX가 아니니 모두 데이터로 받는다. 본문을 읽는 동안 받는 쪽은 “DLE인가, ETX인가”만 묻기 때문이다.
  3. 프레임 2의 본문 끝 ETX에서 드디어 끝을 찾는다. 그 뒤 두 바이트(프레임 2의 CRC)를 CRC로 읽는다.
  4. 길게 이어 붙은 본문으로 다시 계산한 CRC는 프레임 2의 CRC와 맞지 않는다. 받는 쪽은 프레임 1과 2를 한 덩어리로 버린다.
  5. 3번 차례에서 찾은 ETX는 프레임 2의 진짜 끝이었다. 그래서 바로 뒤는 프레임 3의 SYN이고, 받는 쪽은 정확한 자리에서 다시 시작한다. 프레임 3과 4는 정상이다.

보초 방법의 손해는 “깨진 프레임과 바로 다음 프레임” 두 개로 늘 정해져 있다.

둘째 줄, 바이트 수 방법에서 Count가 작아질 때. Count 5가 3이 된 경우로, 바이트 중심 프레이밍의 예와 같다. 받는 쪽은 본문 세 바이트와 가짜 CRC 두 바이트를 읽고 버린다. 그 뒤의 진짜 CRC 두 바이트는 SYN이 아니니 건너뛰고(회색 점선), 프레임 2의 SYN에서 다시 시작한다. 이번에는 프레임 1 하나만 잃는다.

셋째 줄, 바이트 수 방법에서 Count가 커질 때. Count 5(00000000000101)의 오른쪽에서 다섯 번째 비트가 뒤집혀 21(00000000010101)이 되면 이야기가 다르다.

  1. 받는 쪽은 21바이트를 본문으로 받는다. 프레임 1의 본문 5바이트와 CRC 2바이트, 프레임 2 전체 10바이트, 프레임 3의 앞 4바이트(SYN, SYN, Class, Count)다. \(5 + 2 + 10 + 4 = 21\)이다.
  2. 다음 두 바이트(프레임 3의 헤더와 본문 첫 바이트)를 CRC로 읽는다. 맞지 않으니 버린다.
  3. 이제 받는 쪽은 프레임 3의 한가운데에 서 있다. SYN 두 개가 나올 때까지 바이트를 버리며 기다리다, 프레임 4에서 다시 시작한다.

프레임 1, 2, 3을 잃었다. Count가 클수록 더 많이 삼킨다. Count 14비트의 맨 앞 비트가 뒤집히면 5가 \(5 + 2^{13} = 8{,}197\)이 된다. 프레임이 100바이트쯤이면 뒤따르는 프레임 80개 남짓을 한꺼번에 잃는 셈이다. 게다가 3번 차례에서 받는 쪽이 찾는 SYN(16)은 본문에서 막아 두지 않은 값이다. 프레임 3의 본문에 16 16이 우연히 있었다면, 받는 쪽은 거기서 가짜 프레임을 시작해 또 한 번 엉뚱하게 자른다.

넷째 줄, 비트 채우기. 프레임 1의 끝 깃발 01111110의 네 번째 비트가 뒤집혀 01101110이 되었다.

  1. 이 8비트에는 1이 많아야 세 개 이어지니, 받는 쪽은 보통 데이터로 받는다.
  2. 바로 뒤에 프레임 2의 앞 깃발 01111110이 온다. 카운터가 5에 닿고 다음 두 비트가 10이니, 받는 쪽은 여기서 끝을 찾는다.
  3. 프레임 1의 내용 뒤에 깨진 깃발 8비트가 붙은 덩어리는 CRC가 맞지 않아 버린다.
  4. 방금 찾은 깃발은 프레임 2의 진짜 앞 깃발이다. HDLC 받는 쪽은 깃발 하나를 앞 덩어리의 끝이자 다음 덩어리의 시작으로 본다. 그래서 프레임 2부터는 정상이다.

이번에는 프레임 1 하나만 잃는다. HDLC는 시작과 끝을 같은 모양(깃발)으로 표시하니, 다음 프레임의 앞 깃발이 깨진 끝을 대신 맡아 준다. 보초 방법은 시작(SYN·SOH)과 끝(ETX)이 서로 다른 글자라, 다음 프레임의 시작을 보고도 끝으로 쓰지 못한다. 그래서 첫째 줄은 다음 프레임까지 잃었다.

두 가지를 덧붙인다. 프레임 사이에 깃발을 하나만 두고 앞 프레임의 끝과 다음 프레임의 시작으로 같이 쓰면, 그 깃발 하나가 깨질 때 두 프레임이 한 덩어리가 되어 둘 다 잃는다. 깃발의 마지막 0이 1로 뒤집혀 1이 일곱 개가 되면, 받는 쪽은 “다음이 11” 갈래에서 곧바로 오류로 안다.

정리하면 이렇다. 보초 방법은 깨진 프레임과 바로 다음 프레임, 두 개를 잃지만, 그 뒤로는 정확한 자리에서 다시 시작한다. 비트 채우기는 보통 한 프레임만 잃는다. 바이트 수 방법은 Count가 작아지면 하나만 잃지만, 커지면 Count만큼 뒤 프레임들을 삼키고, 다시 시작할 자리도 본문 속 SYN에 속아 틀릴 수 있다. 손해가 어디까지 번질지 정해져 있지 않다는 점에서 바이트 수 방법이 가장 위험하다.

둘 다 아닐 때

  • 물리 신호로 표시: 4B/5B처럼 데이터에 쓰지 않는 부호가 남으면, 그 부호로 프레임의 처음과 끝을 표시할 수 있다. 데이터와 겹칠 일이 없다1.
  • 두 방법을 함께: 길이를 적으면서 깃발도 두면, 길이가 깨져도 다음 깃발에서 다시 동기를 맞춘다.

확인 문제

C1 보초 방법과 바이트 수 방법 중, Count나 ETX가 전송 중 깨졌을 때 잃는 프레임이 몇 개까지 번질지 알 수 없는 쪽은? 다른 쪽은 몇 개를 잃고, 그 뒤로는 왜 괜찮은가?

답: 바이트 수 방법. Count가 작아지면 한 프레임만 잃지만, 커지면 받는 쪽이 Count만큼 뒤 프레임들을 본문으로 삼킨다. 다시 시작할 자리를 찾을 때도 본문 속 SYN 값에 속을 수 있다. 보초 방법은 깨진 프레임과 바로 다음 프레임, 늘 두 개를 잃는다. 다음 프레임의 진짜 ETX에서 끝을 찾으므로, 그 바로 뒤의 SYN부터는 정확한 자리에서 다시 시작한다.
흔한 오답: “보초 방법은 다음 프레임을 잃지 않는다.” ETX가 깨지면 받는 쪽은 다음 프레임의 ETX까지 이어 읽어 두 프레임을 한 덩어리로 버린다.

C2 보초 방법과 비트 채우기가 모두 “채우기”를 하는 이유를 하나의 문장으로 설명하라.

답: 둘 다 끝 표시를 데이터 안에서 찾기 때문에, 데이터가 우연히 끝 표시와 같은 모양일 때를 막으려고 데이터 쪽을 살짝 바꿔(DLE 붙이기, 0 끼우기) 그 모양이 생기지 않게 한다.

  1. 44·45 구현 코드로 확인했다. 쓰지 않는 부호로 프레임을 표시하는 방법은 Peterson & Davie 2.3절(FDDI의 4B/5B 제어 부호)에 있다. ↩ ↩2

  2. 숫자는 46_framing-compared_plot.py, 44_byte-framing_plot.py, 45_bit-stuffing_plot.py로 확인했다. ↩

  3. 46_framing-compared_plot.py로 그렸다. 본문 41 42 43 44 45, 46 47 48, 49 4A 4B 4C, 4D 4E로 프레임 네 개를 만들어 이어 보내고, 받는 쪽 규칙대로 잘라 잃은 프레임 수(BISYNC 2, DDCMP Count 3이면 1, Count 21이면 3, HDLC 1)를 같은 코드로 확인했다. 깨지지 않으면 네 경우 모두 네 프레임을 정상으로 받는 것도 확인했다. CRC 두 바이트는 CRC-16/ARC로 본문만 넣어 계산했고, 계산을 짧게 하려고 DDCMP의 Header는 1바이트로, Count는 1바이트 값으로 줄였다. HDLC 받는 쪽이 깃발 하나를 앞 프레임의 끝이자 다음 프레임의 시작으로 보는 것은 HDLC의 일반적인 동작이다. ↩