Transport Layer - 4. Reliable data transfer Design (3)

1. 성능을 높여보자!

지난 시간에 마지막으로 설계한 신뢰성 있는 전송 방식은 stop&wait protocol 이다. 아무리 대역폭이 커지더라도 한 패킷씩 보내고 기다리기 때문에 성능이 좋지 않다. 따라서 이번에는 지난 설계 모델을 수정해서 성능을 높여보자.

성능을 높이기 위해 새로운 테크닉 몇가지가 더 필요하다.

1. cack(cumulative acknowledge)

sender가 cack(x) 를 받으면 수신자가 x번까지의 패킷은 잘 수신했다고 인지한다. 위의 예시의 경우 수신자는 6번을 받지 못하고 7, 10을 이어서 받았으므로 ack5를 보낸다.

2. pipelined protocols

stop&wait protocol 방식이 매우 느리다는 것을 지난 시간에 확인했다. stop&wait 방식에서는 outstanding packet이 오직 한개이다.
(link utilization을 높이기 위해) pipelining은 ack를 받기 전에 한 번에 여러개의 패킷을 연달아 보내는 것이다. 이를 구현하기 위해서는 sequence number의 범위가 커져야 한다.

아직 ack가 오지 않아서 수신 여부가 확정되지 않은 패킷들을 outstanding, in flight packet이라고 한다.
sender와 receiver 모두 outstanding packets를 보관하는 buffer가 필요하다.
sender는 ack#에 따라서 버퍼에 보관하던 패킷들을 다시 전송할때 쓰고, receiver는 버퍼에서 순서가 알맞게 잘 도착한 패킷들만 application layer에게 올려보내고 나머지 outstanding packets들은 버퍼에 보관한다. (ex. recevier는 ack5를 보내고 6번 패킷이 오기를 기다린다면 그동안 수신했던 5번까지의 패킷들을 저장할 공간이 필요하다. 6이 오면 어플리케이션 계층에게 0-6까지 패킷을 올려보낸다.)

지난 시간 계산한 링크 사용율에 거의 3배 가까이 성능이 좋아졌다. 하지만 이렇게 여러개의 패킷을 연달아 보낼수록 그에 맞는 sequence#를 부여하고 그 크기에 맞는 버퍼를 구비해두어야 한다.
연결한 connection마다 만들어지는 socket마다 해당하는 크기의 버퍼를 할당해주어야 한다.

파이프라인 프로토콜의 종류로 go-Back-N, selective repeat 가 있다.
위 두 종류는 실제 구현이라기 보다는 concept이다. 자세히 공부하면서 위에 모호한 설명을 완벽히 이해해보자.

2. Go-back-N

송신자는 N개의 unacked 패킷을 파이프라인으로 보낸다.
수신자는 cack만 보낸다.

-> 0,1,2,3번 패킷을 보내고 0번 패킷 전송 시간 기준으로 타임아웃을 설정한다.
-> cack(0)도착
-> cack(1)도착
-> cack(1)도착 (중복, 무시함)
-> cack(1)도착 (중복, 무시함)
-> 2번 패킷 기준 타임아웃 초과 2번부터 4개 재전송

cack(0)를 받으면 윈도우를 한칸 옮기고 다음 pkt4를 보낸다.
cack(1)을 받으면 윈도우를 한칸 옮기고 다음 pkt5를 보낸다. 지금 이 순간에 outstanding packet은 2,3,4,5 4개이다.

수신자는 오로지 expecting seq#만을 기다리며 out of order 패킷의 경우 받자마자 버린다.(pkt4, pkt5는 그냥 버림 그리고 계속 cack(1)만 반복해서 보낸다)

수신한 패킷중에 gap이 한 곳이라도 발생하면 전부 다시 보내고 받아야 하므로 비효율적이다. 하지만 구현이 훨씬 간단하다.

참고) https://jsdysw.tistory.com/196?category=1009390

컴퓨터 통신 - 12. 오류복구2

참고) https://jsdysw.tistory.com/203?category=1009390

컴퓨터통신 - 13. Sliding Window 프로토콜 구현 1

sliding window protocol이라고도 부른다.
k bit sequence number를 사용한다면 윈도우 크기 N은 2^k > 2N을 만족하면 된다. 만약 N=5라면 4bit의 sequence number를 사용하면 적절하다.
위의 예시에서 N은 14이다. k는 최소한 5는 되어야 한다.

초록색은 이미 수신 완료가 보장된 패킷들이다. 노란색은 보내긴 했는데 수신완료가 아직 되지 않은 패킷들이다. 파란색은 아직 보내지 않은 패킷들이다.
노란색 패킷들은 상황에 따라 재전송될 수도 있기 때문에 버퍼에 반드시 저장해두어야 한다. 최대 N개의 패킷이 버퍼에 저장될 수 있다.

노란색 패킷중 가장 왼쪽이 보낸지 오래된 oldest sent packet이다. 이 패킷을 기준으로 하나의 timeout이 설정된다.

윈도우 크기 안에서 패킷을 연달아 보낼 수 있다.

3. Selective Repeat

송신자는 N개의 unacked 패킷을 파이프라인으로 보낸다.
수신자는 받은 패킷마다 ack를 보낸다.

제일 마지막에 ack2가 송신자에게 도달하면 송신자는 윈도우를 전진 시켜서 2, 3, 4, 5를 acked packet 처리한다. 윈도우는 6,7,8,9를 담게 된다.

selective repeat이 못 받은 번호의 패킷만 골라서 다시 요청할 수 있기 때문에 더 효율적이다. 하지만 모든 패킷마다 timeout을 설정,관리하고 buffer를 유지하는 일은 훨씬 더 복잡하고 운영체제 에게 부담을 준다.

sender는 가장 왼쪽에 oldest한 노란색 패킷이 아직 있기 때문에 윈도우가 sliding할 수 없는 상태이다.
ack가 도달하면 초록색으로 표시해서 기억해둔다.
왼쪽 두개 노랑 패킷에 대해 ack가 도달하면 다음 노랑 패킷 위치 까지 윈도우가 이동한다.

receiver는 순서가 올바르게 수신된 패킷들 다음 순서인 expecting 패킷에서 window가 시작한다.
out of order 패킷 수신 후 버퍼에 저장해둔다. 그리고 ack를 보내준다.
가장 왼쪽 회색 패킷이 수신되면 그 다음 번 회색 패킷까지 윈도우가 이동한다.
순서대로 잘 도착한 패킷 들은 application layer로 올려보낸다.
만약 수신자가 윈도우를 벗어난 좌측 패킷을 수신하면 ack(n)을 보내주고 윈도우를 벗어난 우측 패킷을 수신하면 그냥 무시한다.

참고) https://jsdysw.tistory.com/196?category=1009390

컴퓨터 통신 - 12. 오류복구2

k bit sequence number를 사용한다면 윈도우 크기 N은 2^k > 2N을 만족하면 된다고 했다.
예를들어 window 크기가 3일 때, sequence #를 2bit sign으로 잡았다고 해보자.

(a), (b) 상황은 전혀 다른데 receiver는 동일한 상황으로 인식한다. 즉 (b)에서 옛날 0번인데 receiver는 다음 0번을 받았다고 생각한다. 그래서 2^k에서 k는 2N보다도 꽤 크게 잡는다.