요약

오류를 찾은 뒤 망가진 데이터 덩어리(프레임)를 되살리는 방법은 둘이다. 받는 쪽이 덧붙은 정보로 스스로 고치는 방법(순방향 오류 수정, FEC)과, 보낸 쪽에 다시 보내 달라고 하는 방법(재전송, ARQ)이다. FEC는 기다리지 않아 실시간 통신에 맞지만, 오류를 찾기만 할 때보다 덧붙일 정보가 많고 모든 오류를 고치지는 못한다. 재전송은 정확하지만 시간이 걸리고, 답을 기다리는 시계(타이머)와 다시 보낼 사본을 담아 둘 저장 공간(버퍼)이 필요해 네트워크 카드(어댑터) 혼자 맡기 어렵다.

예시로 보기

오류 검출 코드나 CRC는 “이 프레임이 망가졌다”는 것까지만 알려 준다. 어느 비트가 틀렸는지, 원래 값이 무엇이었는지는 알려 주지 않는다. 망가진 프레임을 그냥 버리면 그 데이터는 사라진다. 그래서 망가진 프레임을 되살릴 방법이 따로 필요하다.

다시 받을 시간이 없는 경우: 전화

전화 통화에서 0.5초 전의 소리가 깨졌다고 다시 보내 달라고 하면, 다시 온 소리는 이미 때를 놓쳐 쓸모가 없다. 이런 실시간 통신에서는 받는 쪽이 스스로 고쳐야 한다.

숫자로 따라가 보면 왜 그런지 보인다. 통화 앱이 소리를 0.02초(20 ms)씩 잘라 조각마다 프레임 하나에 담아 보낸다고 하자. 받는 쪽 스피커는 0.02초마다 조각을 하나씩 쉬지 않고 튼다.

조각 하나가 망가져 다시 보내 달라고 하면, 요청이 가고 사본이 돌아오는 왕복 시간이 든다. 왕복이 0.25초인 먼 통화라면, 사본은 원래 틀어야 할 때보다 적어도 0.25초 늦게 온다. 그 사이 스피커는 다음 조각 12~13개(\(0.25 \div 0.02 = 12.5\))를 이미 틀었다. 늦게 온 조각을 끼워 넣을 자리가 없다. 재전송으로 늦게 받은 데이터는 가치가 없다.

어? 그럼 스피커가 늘 0.25초씩 늦게 틀면 되지 않나? 그러면 상대 말이 늘 0.25초 늦게 들려 대화가 엇갈린다. 다시 보낸 사본마저 망가지면 또 0.25초가 든다. 대화에서는 늦는 것 자체가 품질을 떨어뜨린다1.

가장 단순한 FEC: 2차원 패리티로 1비트 고치기

2차원 패리티가 가장 단순한 예다. 비트 하나가 뒤집히면 틀린 줄과 칸의 교차점을 다시 뒤집어 고친다. 재전송 없이 앞으로(받는 쪽에서) 고치므로 “순방향” 수정이다.

표 하나로 한 단계씩 따라간다. 데이터는 7비트짜리 줄 6개다. 줄마다 끝에 가로 패리티 비트를 붙이고, 맨 아래에 칸마다 세로 패리티 비트를 붙였다. 모두 짝수 패리티다. 그래서 오류가 없으면 어느 줄이든 어느 칸이든, 패리티 비트까지 세었을 때 1의 개수가 짝수다.

이 표가 오는 도중 첫째 줄 여섯째 비트가 1에서 0으로 뒤집혔다고 하자. 받은 표는 아래와 같다. 마지막 줄과 마지막 칸은 받는 쪽이 센 1의 개수다.

  칸 1 칸 2 칸 3 칸 4 칸 5 칸 6 칸 7 가로 패리티 1의 개수
줄 1 1 0 1 1 0 0 1 1 5 (홀수)
줄 2 1 1 0 1 0 1 1 1 6
줄 3 0 0 1 1 1 0 1 0 4
줄 4 1 1 1 1 0 0 0 0 4
줄 5 1 0 0 0 1 0 1 1 4
줄 6 0 1 0 1 1 1 1 1 6
세로 패리티 0 1 1 1 1 1 1 0 6
1의 개수 4 4 4 6 4 3 (홀수) 6 4  

받는 쪽은 다음 순서로 고친다.

  1. 줄마다 1의 개수를 센다. 첫째 줄은 1, 0, 1, 1, 0, 0, 1에 가로 패리티 1까지 더해 1이 5개다. 홀수이므로 이 줄 어딘가가 틀렸다. 나머지 줄은 모두 짝수라 멀쩡하다.
  2. 칸마다 1의 개수를 센다. 여섯째 칸은 0, 1, 0, 0, 0, 1에 세로 패리티 1까지 더해 1이 3개다. 홀수이므로 이 칸 어딘가가 틀렸다. 나머지 칸은 모두 짝수다.
  3. 첫째 줄과 여섯째 칸이 함께 지나는 비트는 하나뿐이다. 틀린 비트는 그 비트다. 지금 0인 그 비트를 다시 뒤집어 1로 만든다.
  4. 다시 센다. 첫째 줄은 1이 6개, 여섯째 칸은 1이 4개로 모두 짝수가 된다. 표가 보낸 그대로 돌아왔다.

받는 쪽은 보낸 쪽에 아무것도 묻지 않고 고쳤다. 이것이 “앞으로 고친다”는 말의 뜻이다1.

두 방법을 숫자로 비교하기

두 방법은 대가를 치르는 방식이 다르다.

FEC는 오류가 있든 없든 늘 비트를 더 보낸다. 위 표에서 데이터는 \(6 \times 7 = 42\)비트이고, 패리티 비트는 가로 6개, 세로 7개, 귀퉁이 1개로 14개다. 보내는 56비트 중 14비트, 곧 4비트에 1비트(25%)가 덧붙은 정보다.

재전송은 오류가 없을 때 검출용 비트만 더 보낸다. 예를 들어 1,500바이트(12,000비트) 프레임에 32비트 CRC를 붙이면 \(32 \div 12{,}000 \approx 0.27\%\)다. 1,000비트에 3비트가 안 된다. 대신 오류가 나면 왕복 시간을 기다리고 프레임 하나를 통째로 다시 보낸다. 프레임 1,000개 중 1개가 망가지는 링크라면, 다시 보내는 양은 전체의 약 0.1%다.

그래서 링크가 깨끗하고 기다릴 수 있으면 재전송이 비트를 훨씬 덜 쓴다. 기다릴 수 없거나 기다림이 너무 길면 이야기가 달라진다.

기다림의 길이는 거리가 정한다. 지구와 화성 사이는 가까울 때 약 5,500만 km, 멀 때 약 4억 km다. 전파는 빛의 속도(초당 약 30만 km)로 간다. 그래서 편도에 짧으면 약 3분(\(5{,}500\text{만} \div 30\text{만} \approx 183\)초), 길면 약 22분(\(4\text{억} \div 30\text{만} \approx 1{,}333\)초)이 걸린다.

재전송을 요청하고 사본을 받으려면 이 길을 한 번 오가야 한다. 짧아도 6분, 길면 44분이다. 그동안 탐사선은 다시 보내 달라고 할지 모르는 프레임의 사본을 모두 쥐고 있어야 한다1.

정의

오류로 망가진 프레임을 되살리는 방법은 둘로 나뉜다.

  • 오류 수정 코드(ECC)를 쓰는 순방향 수정(FEC): 받는 쪽이 덧붙은 정보로 직접 고친다. 재전송이 쉽지 않은 경우(전화 같은 실시간 통신)에 쓸모 있다.
  • 자동 반복 요청(ARQ), 곧 재전송: ACK와 타임아웃으로 망가진 프레임을 다시 받는다. 역방향 수정이라고도 한다. 고치는 일이 받는 쪽에서 끝나지 않고, 보낸 쪽으로 거슬러 가서 사본을 다시 받아 오기 때문이다1. 자세한 동작은 ARQ와 순서 번호.

오류 수정 코드에는 한계가 둘 있다. 완벽하게 수정할 수 없고, 검출 코드보다 더 많은 정보가 필요해 덧붙는 부담(오버헤드)이 크다.

완벽하게 고치지 못하는 예는 위 표에서 바로 만들 수 있다. 첫째 줄 여섯째 비트와 셋째 줄 둘째 비트가 함께 뒤집혔다고 하자. 그러면 틀린 줄이 둘(1, 3), 틀린 칸이 둘(2, 6)이 된다. 교차점 후보는 네 곳(줄 1-칸 2, 줄 1-칸 6, 줄 3-칸 2, 줄 3-칸 6)이다. 줄 1-칸 2와 줄 3-칸 6이 뒤집혀도 똑같은 줄과 칸이 틀리므로, 어느 두 곳이 진짜인지 정할 수 없다. 받는 쪽은 오류가 있다는 것은 알지만 고치지는 못한다1.

더 많은 정보가 필요한 이유는 답해야 할 질문이 다르기 때문이다. 검출은 “망가졌나?”라는 예·아니오 질문 하나에만 답하면 된다. 수정은 “56비트 중 어디가?”까지 답해야 한다. 질문이 많아진 만큼 덧붙일 비트도 많아진다. 앞의 비교에서 25%와 0.27%의 차이가 이것이다1.

프레이밍 오류: 받는 쪽은 모른다

오류 중에는 프레임의 처음이나 끝 표시가 깨져 프레임으로 알아볼 수조차 없는 프레이밍 오류도 있다. 이때 받는 쪽은 프레임이 왔다는 것조차 모른다. 곧 프레임 분실이다. 받는 쪽이 아무 말도 할 수 없으므로, 결국 보낸 쪽이 타임아웃으로 알아채야 한다.

프레임의 처음과 끝은 약속된 비트 무늬로 표시한다. 예를 들어 HDLC는 깃발 01111110을 프레임 앞뒤에 붙인다(비트 채우기). 받는 쪽은 선에서 비트를 읽으며 이 깃발을 찾는다. 깃발을 찾아야 “여기서 프레임이 시작한다”고 안다.

A가 B에게 프레임을 보내는 과정을 시각 순서로 따라가 보자. 링크는 ARQ와 순서 번호의 예와 같다(프레임을 싣는 데 0.8 ms, 건너는 데 5 ms, 타임아웃 15 ms).

  • 0 ms: A가 프레임을 싣기 시작하고 타이머를 15 ms로 맞춘다.
  • 5 ms: 첫 비트가 B에 닿는다. 그런데 잡음이 앞쪽 깃발의 비트 하나를 뒤집어 놓았다. B는 시작 표시를 찾지 못했으니 이 비트들을 프레임으로 모으지 않는다.
  • 5.8 ms: 마지막 비트까지 지나간다. B는 받은 프레임이 없는 상태 그대로다. 오류 검출 코드를 돌려 볼 프레임조차 없으니 “망가졌다”는 답(NAK)도 보낼 수 없다.
  • 15 ms: A의 타이머가 다 된다. ACK가 오지 않았으므로 A는 같은 프레임을 다시 보낸다.

어? 그럼 B가 “프레임이 올 때가 됐는데 안 왔다”로 알아챌 수는 없나? 없다. B는 A가 언제 보낼지 모른다. A는 보낼 데이터가 생길 때만 보낸다. 그래서 B에게는 “A가 보낼 게 없다”와 “A가 보냈는데 사라졌다”가 똑같이 조용한 선으로 보인다.

“보냈는데 답이 없다”를 아는 쪽은 보낸 A뿐이다. 그래서 프레이밍 오류는 A가 타이머로 알아챌 수밖에 없다. 한 번에 한 프레임씩 보내는 방식에서는 A가 ACK를 받기 전까지 다음 프레임도 보내지 않는다. B가 다음 프레임의 번호를 보고 빈 번호를 눈치챌 기회도 없다1.

재전송에 시계와 버퍼가 필요한 이유

재전송에는 타임아웃 시계와 다시 보낼 프레임을 담아 둘 버퍼가 필요하다. 하나씩 빼 보면 왜 필요한지 보인다.

시계가 없다고 하자. 위의 프레이밍 오류에서 A는 ACK를 기다리기만 한다. ACK는 영영 오지 않고, A에게 다른 신호도 오지 않는다. A는 다음 프레임으로도 넘어가지 못하고 전송이 그 자리에서 멈춘다. ACK가 사라진 경우도 똑같다. 시계는 “이만큼 기다렸는데 답이 없으면 다시 보낸다”를 정하는 유일한 장치다.

버퍼가 없다고 하자. 15 ms에 타이머가 다 되어 A가 같은 프레임을 다시 보내야 한다. 그런데 그 프레임의 비트는 0.8 ms에 이미 A를 떠났다. 사본을 남겨 두지 않았다면 다시 보낼 것이 없다. 위층 프로그램은 데이터를 넘긴 뒤 그 메모리를 다음 데이터에 쓰고 있을 수도 있다. 그래서 A는 ACK가 올 때까지 사본을 쥐고 있어야 한다. 위 링크에서는 아무 일이 없어도 10.8 ms, 한 번 실패하면 거기에 15 ms가 더 붙는다.

이 두 가지는 프레임을 비트로 바꿔 선에 싣고 받는 장치(어댑터)가 혼자 하기에는 한계가 있다. 그래서 재전송은 이웃한 두 노드 사이의 전송을 맡는 데이터 링크 계층(2계층)의 기능이지만, 노드 안의 소프트웨어가 맡는다.

활용

  • FEC: 휴대전화 음성, 위성·심우주 통신(왕복 시간이 길어 재전송이 늦음), QR 코드와 CD(리드-솔로몬 부호).
  • ARQ: 파일 전송처럼 늦어도 정확해야 하는 데이터. TCP의 재전송도 같은 생각이다.
  • 흔한 실수: FEC를 쓰면 재전송이 필요 없다고 믿는 것. 고칠 수 있는 오류의 수에는 한계가 있어, 넘치면 다시 받아야 한다. 실제 시스템은 둘을 섞어 쓰기도 한다.

연결

확인 문제

C1 오류 복구의 두 방법을 쓰고, 각각 어떤 경우에 알맞은지 말하라.

답: 순방향 수정(FEC, 오류 수정 코드로 받는 쪽이 고침)은 재전송이 어렵거나 늦은 데이터가 쓸모없는 실시간 통신에. 재전송(ARQ, ACK와 타임아웃)은 시간이 걸려도 정확해야 하는 데이터에.

C2 프레이밍 오류가 나면 받는 쪽이 NAK도 보낼 수 없는 이유는?

답: 프레임의 처음과 끝을 알아보지 못해 프레임이 왔다는 사실 자체를 모른다. 모르는 프레임에 대해 응답할 수 없으므로, 보낸 쪽이 ACK가 오지 않는 것을 타임아웃으로 알아채야 한다.

C3 지구와 화성 사이(편도 수 분) 탐사선 통신에는 FEC와 ARQ 중 무엇을 주로 쓰나? 다른 쪽은 왜 덜 맞는가?

답: FEC. 재전송을 요청하고 다시 받는 데 왕복 시간(십여 분 이상)이 걸려 너무 늦다. 덧붙일 정보가 늘더라도 받는 쪽에서 바로 고치는 편이 낫다.

  1. 표의 1의 개수, 2비트 오류의 증상, 비율, 화성 전파 시간(거리 ÷ 초당 30만 km)은 다시 계산해 확인했다. 시간 순서의 숫자(0.8 ms, 5 ms, 5.8 ms, 10.8 ms, 15 ms)는 53_arq-sequence-number_plot.py로 확인한 ‘걸리는 시간’ 절의 링크와 같다. ↩ ↩2 ↩3 ↩4 ↩5 ↩6 ↩7