[네트워크]ARQ(Automatic Repeat reQuest)

ARQ란?

✍️신뢰성있는 데이터 전달을 위해, 재전송을 기반으로 하는, 에러제어 방식
✍️'검출후 재전송 방식' 혹은 'ARQ'기법이라고 함

✍️error 검출

• checksum : bit error 감지
• sender는 receiver로 부터 일정시간 동안 ack 도착 하지 않으면 에러 간주(타임아웃)
  ✍️ receiver feedback
• sender가 sequence number를 각 패킷에 추가
• Acknowledgement의 두가지 타입

🎈positive ack

• receiver가 pkt(packet)를 정상적으로 받으면 sender에게 ack를 보낸다.
• loss나 error가 발생하면 알려줄 방법이 없다.

🎈negative ack
receiver가 pkt를 정상적으로 받으면 아무 반응 없이 받기만하고, error나 loss가 생기면 nak을 보낸다.
중복된 패킷을 삭제하고 재전송한다.

Timeout mechanism

• sender가 일정 합리적인 시간동안 ACK를 기다린다.
• ACK가 정해진 시간안에 도착하지 않으면 packet을 다시 보낸다.

stop and wait ARQ

✍️ sender가 한 패킷을 보내고나서, receiver의 응답을 기다린다.(positive ack)

time out 되면 다시 보낸다.

✍️ basic operation

sender

• 하나의 패킷을 전달하고 timer를 잰다.
• reciever로 부터 ack를 기다린다.
• time out내에 받은 ACK가 없다면 재전송한다.

receiver

• 성공적으로 패킷을 받았을때만, positive ack를 응답한다.

• sender나 receiver에서 손상된 패킷을 받으면 패킷을 삭제해버린다.
• 두개의 시퀀스 (0,1)을 번갈아 사용한다.

  pkt0에는 ack0, pkt1에는 ack1, 다시 pkt0에 ack0......

위 그림처럼 packet loss가 있을때, timeout mechanism을 이용해서 정해진 시간동안 ack를 기다리고, 응답이 없으면 재전송한다.

위 그림처럼 만약에 RTT(Round time trip)가 timeout보다 크다면 위 그림처럼 premature timeout이 생겨 재전송이 증가한다.
(RTT: sender가 pkt를 보낸 시점부터 sender가 다시 ack를 받는 순간까지 걸리는 시간)

✍️예를들어 두 host가 있다.
전송속도(R)이 1Gbps인 channel로 연결되어 있다. (R = 1Gbps(bits/sec))
RTT는 그 channel 안에서 시간이 조금 지연된다. (RTT = 30msec)
packet size(L) = 1000 bytes이다.

✍️stop and wait ARQ가 사용될때 utilization을 계산해보면
Transmission delay($U_sender$) =packet size/chennel rates =L/R = (8000bits/packet) / ($10^9bits/sec$) = 0.000008 = 0.008msec

Utilization = $U_sender/(U_sender +RTT)$ = 0.008 / (30+0.008) = 0.00027

effective throughput = pkt size / $U_sender$+RTT = 8000 bits / (30+0.008)msec = 267kbps

✍️장점

• 간단하다.
• 소수의 큰 frame에서 보낸 메세지에 대해서는 잘 작동한다.

✍️단점

• 데이터 속도가 높거나 receiver와 sender사이에 거리가 멀면 부적합하다.
• 비효율적으로 링크를 활용하면 너무많은 리소스가 버려진다.

pipelined ARQ protocols

• Go-Back-N(GBN)
• Selective Repeat(or Selective Reject)

Go-Back-N(GBN) ARQ

receiver에서 순서대로 받지 못한 패킷이 있다면,해당 패킷부터 다시 시작한다.

• pipelined protocols

• ACK를 받지 않아도 최대 허용된 수 안에서 여러 패킷을 전송한다.

• 각 패킷은 field size k로 제한된 시퀀스 number를 가진다.

  시퀀스 넘버의 범위 : $[0,2^k-1]$
  sequence number는 modulo $2^k$을 사용해서 증가한다.
  0,1,2,....,$2^k-1$,0,1,2,...,$2^k-1$,0,1,2,...

• 최대 window size(N) = $2^k-1$

  receiver는 N길이의 buffer를 가진다.
  sender는 ACK없이 N packets까지 보낼 수 있다.

✍️재전송 되는경우

• NAK 프레임을 받았을 경우
• 전송 데이터 프레임의 분실
• 지정된 타임아웃내의 ACK 프레임 분실(lost ACK)

✍️sliding window

✍️window : 패킷을 한번에 보낼수 있는 범위를 지정해 놓은 것이다.

✍️sender

1.송신자는 패킷을 보내고 타임아웃 타이머를 킨다.
2.첫 패킷에 대한 ack가 도착하지 않아도, window 크기 만큼의 패킷을 순서대로 보낸다.
3.윈도우의 맨앞에 해당하는 ack가 도착했을때, 윈도우를 오른쪽으로 민다.
4.윈도우를 밀때,다시 타이머를 킨다.
5.윈도우 첫번째 에 해당하는 패킷이 도착하지 않아 타임아웃이 되면 윈도우 첫번째에 있는 패킷부터 다시 보낸다.

✍️receiver

1.패킷을 받으면 다음 패킷 순서 번호와 함께 ack를 보낸다.
2.만약, 마지막으로 받은 패킷 번호가 k인데 그다음으로 k+2를 받으면 이후로 오는 패킷은 모두 버린다.
3.k+1이 들어오면 다음 순서번호와 함께 ACK를 보낸다.

위 그림을 보면

sender가 pkt0을 보냄 -> receiver가 ACK0(#1) 보냄
..
sender가 pkt2 보냄 -> loss
sender가 pkt3 보냄 -> receiver는 pkt2가 들어와야 하는데 들어오지 않아서 pkt3 버림
...
sender가 pkt5 보냄 -> 버림
timeout -> sender가 pkt2 다시보냄
..
이후 정상

✍️윈도우로 패킷수를 N으로 제한하는 이유
TCP는 sender가 receiver의 버퍼를 오버플로우 시키는 것을 방지하기 위해 흐름제어(속도 일치시키기)를 한다. 보내지는 세그먼트 양을 제한하여 혼잡제어를 할 수 있다. 수신측은 사용가능한 버퍼 공간이 얼마나 되는지 알려주고, 송신자는 그에 맞게 윈도우 범위를 조절한다.

✍️단점
만약에 window size도 크고, bandwidth-delay도 커진다고 생각해보자. 하나의 packet만 오류가 나도 뒤에 packet은 모두 버려지기 때문에, 다시 보내야 되는 packet의 양이 많아질 수 있다.

Selective Repeat (SR)ARQ

receiver 측에서 받은 각각의 패킷들에 대해 ACK를 보내는 방식
소실된 패킷이 있다면, 해당 패킷에 대해서만 재전송한다.

✍️sender와 receiver 모두 window를 가진다.
✍️receiver가 받았더라도 sender가 ACK를 받지 못하면 window는 움직이지 않는다.
(반드시 윈도우 가장앞에 있는 넘버의 ACK나, packet을 받아야 한다.)
✍️buffer pkts: 폐기 방식을 사용하지않아, 순차적이지 않은 프레임은 재배열하기 위해서 버퍼가 필요함(예를 들면, 중간에 패킷이 손상되어 받지 못하고 넘어 갔을때, 다시 재수신 하는데 순서가 안맞을 수 있음.)
✍️sender는 각각의 패킷에 대해 타이머를 설정한다.
만약 timeout까지 window의 가장 앞 넘버의 ack를 받지 못한경우, 다시 재송신한다.
✍️receiver window size + sender window size < sequence size 를 항상 만족해야 한다. receiver와 sender의 window size는 같으므로
window size는 sequence size/2 해주면 된다.

왜 이런 값이 나와야 하느냐면, receiver에 순서대로 패킷이 들어오지 않았을때, 버퍼에 저장하게 되는데, 버퍼에 들어온 값이 중복인지 새로운 데이터인지 파악하기가 힘들어서 그냥 저장해버린다.

✍️전송과정

1. receiver는 ACK가 순서대로 오든 말든, 받은 패킷에 대한 ACK를 보낸다.

   예를들어, sender에서 1,2,3,4 보냈는데, receiver가 1,3,4를 받았다면
   1,3,4에 대한 ACK만 보낸다.

2. sender는 ACK를 받지 못한 모든 패킷에 대해서 타이머를 계산한다.

   만약, 타임아웃 내에 ack가 오지 않는다면, 해당 패킷에 대해서 다시 재전송한다.

3. receiver는 올바르지 않은 패킷이 와도 버퍼에 일단 저장해놓고, 나중에 부족한 부분을 채워서(재전송 받고) 정렬하고, 상위 계층으로 보낸다.

예를들어,

패킷 3이 소실된 경우이다.
각 패킷들은 전송되는 순간에 타이머가 시작된다.
소실된 패킷의 타이머가 만료되면 해당 패킷만 재전송 한다.
순서대로 올경우에는, 상위 계층으로 바로 전송하고, 순서대로 오지 않는다면 버퍼에 저장했다가 한번에 전송한다.(윈도우 크기만큼 채워지면 보낸다.)
receiver와 sender는 모두 윈도우의 가장 앞 시퀀스 넘버를 받아야 오른쪽으로 움직인다 .
위 그림을 보자.
패킷 2가 소실되었다. receiver는 패킷2를 받아야 하는데 패킷3을 받아서 패킷3을 버퍼에 넣었다. 패킷4,5도 마찬가지다. receiver는 받은 패킷에 대해서는 모두 ack를 보내주고 있다.
sender는 윈도우가 꽉차 더이상 보내지 못하고 있다. 이때,패킷2가 타임아웃되어 재전송했다. receiver는 패킷2를 받아 버퍼에 있던 3,4,5와 합쳐서 정렬한후 상위 계층으로 전달한다.
sender는 ack2를 받아 윈도우를 [6,7,8,9]로 이동한다.