Go-back-N ARQ, Selective Repeat ARQ 프로토콜 정리

Go-back-N ARQ와 Selective Repeat ARQ는 모드 전송층(Transport Layer)의 프로토콜이며 이 두가지를 혼합 및 개선하여 만든 프로토콜이 TCP(Transmission Control Protocol)이다.

이 글에서 사용된 "프레임" 이라는 용어는 전송층에서 쓰이는 "패킷" 과 같은 개념이며 데이터링크층에서 사용되는 전송단위인 프레임과는 다르다.

1. 무잡음 채널에서의 프로토콜
 - Simplest
 - Stop-and-Wait

2. 잡음이 있는 채널에서의 프로토콜
 - Stop-and-Wait ARQ (파이프 라인이 1개)
 - Go-Back-N ARQ (파이프 라인 N개)
 - Selective Repeat ARQ (파이프 라인 N개)

※ ARQ(Automatic Repeat Request : 자동 반복 요청)
 : 에러가 발생한 경우 재전송을 요구하는 방식

※ 파이프라인(pipeline)
 : ACK를 받기 전에 보낼 수 있는 프레임의 갯수

※ ACK(acknowledgment : 확인응답)
 : 에러없이 프레임을 받은 경우 송신측에 보내는 신호

※ 프레임의 종류
 - 데이터 프레임
 - 제어 프레임 : ACK 프레임

※ redundent bit
 - 프레임의 오류를 검출 또는 정정하기 위해 데이터 비트 외에 추가적으로 붙이는 bit




* Stop-and-Wait ARQ

- 손상된 프레임을 검출하여 정정하기 위해서는 데이트 프레임에 redundent bit 를 넣어야 한다. 프레임이 수신자에게 도달 한후
① 검사하여 손상된 것이 발견된 경우 프레임을 버린다.(discard) 오류 검출은 수신자가 ACK를 보내지 않고 가만히 있는 것에 의해 송신자에게 알려진다.

- 프레임의 손실, 중복, 순서바뀜을 알아내기 위해 프레임에 순서번호(sequence number)를 붙여야 한다.
② 순서번호에 의해 받은 프레임이 중복, 순서바뀜이 일어난 경우 프레임을 버리고 ACK를 보내지 않는다.
    (discard and silence)

★ 대원칙 : 잘(제대로) 프레임을 받은 경우에만 응답을 한다.(ACK를 보낸다.)
 -> 그 외의 경우엔 ACK를 보내지 않는다.

- 송신측은 프레임을 보냄과 동시에 타이머를 작동시킨다. 수신측에서 보낸 ACK를 받으면 타이머가 멈춘다.

- 송신측은 전송한 프레임의 사본을 보관하고 있다가 타이머가 만료(expired)되면 해당 프레임을 다시 보낸다.(retransmission)
-> ACK가 오지 않은 경우 프레임이 손실,중복,순서바뀜이 일어난 것으로 판단

※ 프레임 순서가 뒤바뀐 경우는 왜 생기는가?
-> 프레임의 전송경로가 매번 같지 않기 때문

※ 중복된 프레임이 오는 경우는?
-> ACK가 Timer만료 후 도착하여 재전송이 일어난 경우

※ 순서가 뒤바뀌는 경우와 중복된 프레임을 어떻게 알 수 있는가?
-> 순서번호(sequence number)로 알 수 있다.

※ UDP 프로토콜은 ACK가 없다. TCP/IP 프로토콜은 ACK가 있다.

- 데이터 프레임에 순서번호가 있듯이 ACK 프레임에도 응답 번호가 있다. 응답 번호는 항상 송신자가 다음에 받기를 기대하는 순서 번호를 보낸다. 예를 들면 0번 프레임이 도달했으면 수신자는 1번을 담은 응답 프레임을 보내 1번 프레임을 기다리는 것을 알린다. 1번 프레임이 안전하게 도달하면 수신자는 0번을 응답으로 보내어 0번 프레임을 기다린다는 것을 알린다.
(프레임0을 잘 받은 경우 ACK0을 보낼수도 있다. 약속하기 나름)





* Go-back-N ARQ

- 전송 효율을 높이기 위해서는 송신자가 응답을 기다리는 동안 여러개의 프레임을 보내어 채널의 사용량을 높여야 한다.

※ sliding window : 송신자와 수신자가 관심을 두고 있는 순서 번호의 영역을 정의하는 추상적인 개념이다. 송신자와 수신자는 가능한 순서 번호의 일부분만을 사용해야 한다는 것이다. sliding window의 크기가 파이프라인의 크기이다.
-> 응답을 기다릴 수 있는 최대 프레임의 개수 = ACK를 받기전에 보낼 수 있는 프레임의 개수

- Go-bakc-N ARQ 프로토콜은 누적응답이기 때문에 ACK 응답번호에 의해 sliding window가 한꺼번에 한 칸이상 밀려 갈 수 있다.
예) 프레임0, 1, 2 를 전송한 후 ACK3이 온 경우 프레임2까지 잘 전송된 것으로 판단하여 sliding window가 3칸 이동하여 프레임3이 sliding window의 첫 프레임이 된다. ACK3 이 오면 ACK1,2가 오지 않아도 프레임0,1이 잘 전송된것으로 판단한다.

- Go-bakc-N ARQ 프로토콜에서 Timer는 단 한개뿐이다.

- Timer 가 만료되면 ACK가 오지 않은 프레임(sliding window의 첫 프레임)부터 재전송한다.
예) 6번 프레임을 보냈는데 3번 프레임의 타이머가 만료된 경우, 송신자는 뒤로 돌아가서 3,4,5,6번 프레임을 다시 보낸다. 이것이 Go-back-N ARQ라고 하는 이유이다.

- 수신측 sliding window의 크기는 1이다. 받고자 하는(받을 차례의) 프레임의 번호만 가리키고 있는다. 수신된 프레임의 번호가 기다리는 프레임의 번호가 아닌 경우 버리고 기다린다.(discard and silence)

- Stop-and-Wait ARQ 는 송신측 sliding window의 크기가 1인 Go-back-N ARQ라고 볼 수 있다.




* Selective Repeat ARQ

- Go-back-N ARQ 프로토콜은 수신자 쪽에서의 과정을 단순화 하고 있다. 수신자는 오직 하나의 변수만 관리하며 순서가 뒤바뀌어 도달한 프레임들을 보관하는 버퍼가 없이 단순히 버려질 뿐이다. 그러나 이 프로토콜은 잡음이 많은 채널에서는 매우 비효율적이다. 잡음이 있는 채널에서는 프레임이 손상될 확률이 높아지며 이는 다수의 프레임을 다시 전송하게 되는 것을 의미한다. 이 재전송으로 인해 대역폭을 소모하게 되며 전송 속도도 저하된다. 잡음이 있는 채널에 대해서는 오직 하나의 프레임이 손상되었는데 전체 N개의 프레임을 재전송하는 대신에 오로지 손상된 프레임만 다시 전송하는 방법이 있다. 이 방법이 Selective Repeat ARQ 이다. 이 프로토콜은 잡음이 있는 채널에서 효율적이지만 수신자 쪽에서의 절차가 더욱 복잡하다.

- 선택적 응답 : (ACK3이 오면 프레임2만 잘 받았다고 판단)

- Timer는 각 프레임당 1개씩 동작한다. Timer1이 만료되면 프레임1을 다시 보낸다.

- 송신측 sliding window의 가장 빠른 번호의 프레임의 ACK를 받으면 sliding window를 이동시킨다.

- 수신측도 sliding window의 가장 빠른 번호의 프레임을 받으면 sliding window를 이동시킨다.

- 수신측에서 sliding window 범위 안에 프레임이 순서가 뒤바뀌어 온 경우, 버리지 않고 저장한다.
(sliding window가 프레임 0,1,2,3 에 걸쳐 있는 경우, 프레임0이 오기전에 프레임1이 온 경우 프레임1에 대한 ACK를 보낸다.)

- Selective Repeat ARQ는 NAK를 사용하여 개선할 수 있다. NAK를 쓰게 되면 Timer가 만료되기전에 해당 프레임을 재전송 해야한다는 것을 알 수 있으므로 빠른 재전송이 가능하다.

※ NAK(Negative Acknowledge) : 해당 프레임을 제대로 전송받지 못한 경우 송신측에 보내는 신호