CH3 : Transport Layer (2)

* 이 글에 관련된 모든 내용은 Computer Networking A Top-Down Approach 7th에서 가져온 내용이다. *

 

Reliable data transfer

---

데이터전송을 reliable하게 하는 방식에는 두가지가 있다.

 

1. Forward Error Correction (FEC)

 - 반복되는 bit를 더해 리시버가 에러를 체크하게끔 한다.

 - 예를들어 센더는 1을 보낼때 111을 보내고, 2를 보낼때 222를 보낸다. 만약 111이 가는중에 에러가 발생하여 101이 도착했다면 리시버는 많이나왔던 1을 실제로 온 데이터로 받아들여 1이라고 인식한다. 

 

 

2. Retransmission

 - 에러가 나면 재전송하는 기능이다. 

 - ARQ(Automatic Reapeat Request)라고도 하며 크게 세가지 방법이 있다.

 

이번 내용에서는 ARQ에서 쓰이는 세가지 방법에 대해서 알아보겠다.

1. Stop and Wait

2. go-Back-N

3. Selective repeat

 

Stop and Wait

---

 

 

- 가장 기본적인 방법이다.

- 패킷하나를 보내면 그에대한 옹답이 올때까지 다음 패킷을 보내지 않는다. 

 

- 패킷마다 ack을 기다려야 하므로 반복되는 propagation delay에 의해 효율이 너무 낮다.

 

 

 

 

위 그림과 같이 sender쪽에서 패킷을 보내면 reciever는 그에 대한 응답으로 ACK를 보낸다.

하지만 만약 sender쪽에서 가는 packet이나 receiver가 보내는 ACK가 로스가 나면 어떻게 할까?

재전송을 한다.

패킷을 보낸 후에 일정시간동안 (TIME-OUT)응답이 돌아오지 않으면 패킷이나 ACK쪽에서 로스가 났다고 생각하고 재전송을 한다. 그런데 또 문제가 있다.

 

만약 진짜 패킷쪽에서 로스가 나서 재전송을 하면 괜찮지만 reciever가 패킷을 제대로 받았는데 ACK가 로스가 나면 receiver가 패킷을 제대로 받았음에도 불구하고 똑같은 패킷을 또 받는 현상이 벌어진다.(Duplication)

 

때문에 패킷에 sequence number를 붙이게 되었다. 이 sequence number는 1bit이므로 1 or 0만 나타낸다.

이렇게 되면 같은 sequence number가 붙은 패킷이 오면 discard해버리면 된다.

 

그런데 또! 문제가 있다..

만약 time-out시간이 ACK이 오는 시간보다 짧다면 0의 ACK는 제대로 갔지만 sender쪽에서 time-out이 발생해 재전송하는 생황이 생긴다.

그리고 늦게온 ACK에 대해서 sender가 보낸 초록색1패킷이 loss가 되면 sender는 잘못 재전송된 0의 ACK를 1의 ACK로 인식하고 다음패킷을 sequence number 0으로 전송한다. 그러나 reciever는 sequence number가 1인 패킷을 받지 못했기 때문에 주황색 0과 노란색 0은 서로 다름에도 불구하고 노란색 0패킷을 삭제해버린다.

 

이에 대한 해결책으로 ACK에 번호를 붙여서 보내자는 아이디어가 등장했다.

 

이렇게 패킷 0에 대한 응답으로 ACK(0)처럼 ACK에 sequecne number를 붙여서 주게 되면 문제를 해결할 수 있다.

 

이러한 과정을 통해 최종적으로 완성된 Stop and Wait ARQ의 과정은 다음과 같다.

위 과정에서는 패킷0에 대한 응답으로 ACK(0)이 아닌 ACK(1)을 보낸다. (패킷 1을 보내달라는 의미로)

이 차이는 버전마다 다르다.

Performance

 

패킷하나를 보내기 위해 걸리는 시간은 다음과 같다. 

또한 효율도 구할 수 있다. 효율은 (패킷만을 보낼때 걸리는시간) / 전체시간으로 나타낼 수 있고, 이를 수식으로 표현하면 다음과 같다.

패킷만을 보낼때 걸리는 시간 : L/R

전체 시간 : (L+A)/R + 2Tp

 

 

Sliding Window Protocols : Pipelining

---

go-back-N과 Selective repeat을 배우기 전에 우선 sliding window개념에 대해서 알아야 한다.

간단하게 말하면 파이프라인이다. 

보낸 패킷에 대한 ACK가 오기전에 특정 범위만큼의 패킷들을 모두 보내는 것이다. 

이때 이 범위(사이즈)를 WS(Window Size)라고 한다.

 

파이프라인을 사용하지 않았을때와 사용했을 때의 소요시간과 효율을 비교해보면 다음과 같다.

 

Go-Back-N

---

Sender

 

Go-Back-N에서 sender의 SWS(Sender Window Size)는 N이다.

만약 timeout이 발생하면 sender는 현재 window안에 있는 모든 패킷을 재전송한다.

 

Receiver

receiver의 RWS(Receiver Window Size)는 1이다.

만약 reciever가 기다리는 sequence number의 패킷이 도착하면 가장 높은 order에있는 sequence number의 ACK를 보낸다.

그러나 만약 원하는 sequence number가 아닌 다른 number의 패킷이 온다면 삭제하고 내가 원하는 패킷의 sequence number를 ACK로 보낸다.

 

예시를 들자면 다음과 같다. 천천히 따라가보며 이해해보자.

 

또한 Go-Back-N에서 SWS는 2^m-1보다 작거나 같아야 한다. (m은 seq number의 비트수)

이에 대한 증명은 다루지 않겠당!

 

Selective-Repeat

---

Sender

ACK가 오지 않은 패킷에 대해서만 재전송을 한다.

SWS는 GBN과 마찬가지로 N이다.

 

Receiver

GBN과 달리 RWS가 N이다.

순서가 달라도 window안에 있으면 packet을 받을 수 있다.

성공적으로 도차한 패킷에 대해서 개별적으로 ACK를 보낸다.

 

SR방식에서 reciever의 RWS는 N이므로 다음과 같은 경우의 수를 생각해볼 수 있다.

1. 윈도우안에 들어있는 seq number의 패킷이 올 경우

 - ACK를 보내고, buffer를 채우고, 윈도우를 sliding하거나 하지 않는다.

2. 현재 윈도우 이전의 seq number의 패킷이 올 경우

 - ACK(n)을 보낸다.

3. 그 외

 - error이므로 무시한다.

 

 

 

예시는 다음과 같다. 천천히 따라가보며 이해해보자.

 

GBN과 달리 SR에서 SWS와 RWS는 모두 2^(m-1)보다 작거나 같아야 한다. 이에 대한 증명은 역시 하지 않겠당!

그러나 좋은 자료가 있으므로 첨부만 하겠당

 

seq number의 bit수가 2이므로 WS는 2이하여야 한다.