컴퓨터 네트워크 11-1일차 : Pipelined protocol (GO-BACK-N / Selective Repeat)

컴퓨터 네트워크 10일차 : transport layer rdt / 9일차 복습

드디어 10일차 돌파!!!!

11일차로 돌입합니다 ^^

이제 수업 3번만 더 지나가면 중간고사네요 ㅠㅠ

+소켓프로그래밍 과제까지 있다는 소식 흑흑

 

---

1. Pipelined protocol

rdt3.0을 거쳐 reliable한 채널을 만들었으니 이제부턴 rdt3.0에서 어떻게 빠르게 데이터를 보낼 수 있을지 성능면을 고려해보도록 하겠습니다.

 

지난번에는 하나보내고 ACK받고 하나보내고 ACK받고 원바이원으로 데이터를 보냈습니다. 하나보내고 ACK받는 것까지 1RTT가 소요되는 셈입니다. 즉, 1RTT까지 패킷 1개를 보낸 셈이죠.

 

하지만 이런 방식보단 여러개 데이터를 보내고 줄줄이 ACK을 받는 방식도 생각해볼 수 있습니다. 우리는 이런 방식은 Pipelining 이라고 합니다.

Pipelining : 아직 ACK을 받지 않은 상태에서 여러개의 패킷을 전송할 수 있는 것을 허락하는 것 입니다. 이 방식은 링크를 점유하는 비율(link utilization)이 굉장히 올라가게 됩니다.

기존 rdt3.0에서는 전달한 패킷에 대한 ACK이 들어와야 다음 패킷을 보낼 수 있던 것과는 차이가 있죠.

 

 

1-1. Pipelining을 위해 필요한 것

 

1) 시퀀스 넘버의 범위가 늘어나야 합니다.

패킷에 대한 ACK을 관리해야하는데 줄줄이 패킷을 보내고 줄줄이 보낸 패킷에 대한 ACK을 관리해야하기 때문입니다. 즉, 어떤 패킷이 손실이 났는지 알기 위함이에요.

참고로 기존 rdt3.0에서는 시퀀스넘버 0,1 총 2개만 있으면 동작시킬 수 있었습니다.

 

2) sender와 receiver 사이에서는 보낸 데이터에 대한 버퍼링을 해줘야합니다.

sender 입장에서는 줄줄이 보낸 패킷이 잘 도착하지 못할 수 있어 재전송을 해줘야할 수 있기 때문에 버퍼링을 잘 해줘야합니다.

 

 

1-2. Utilization

기존 1개 데이터보내고, 1개 ACK을 돌려받고 다음 데이터를 전송하는 방식이었다면 Pipelining 방식은 아래와 같습니다.

L/R은 트랜스미션 딜레이입니다.  패킷이 트랜스미션 되고서 ACK이 날라올 때까지 시간 동안에 하늘색이 차지하는 포지션이 곧 유틸라이제이션 입니다. 하늘색이 차지하는 포션은 3*L/R입니다.

 

이렇게 reliable한 전송에 파이프라이닝까지 적용하니 적용한 갯수만큼 유틸라이제이션이 배로 늘어나는 것을 알 수 있습니다.

 

P1. 그렇다면, 3 즉, N을 무한대까지 늘리면 성능(속도)이 무한대로 늘어날까요?

NO, 문제가 생깁니다.

적정 파이프라인은 넘어선다면, 네트워크의 congestion이 발생해 네트워크가 느려질 겁니다.

때문에 뒤에 나올 GO-BACK-N 방식을 사용할 때 N을 어떻게 적정하게 맞출지가 큰 논점이 될겁니다.(=congestion control)

 

P2. 네트워크는 빵빵한데 수신자입장에서 데이터를 받는 속도가 있습니다. 수신자가 데이터를 받고 애플리케이션 레이어로 올려보내야 하는데요. 데이터를 읽어들인 다음에 애플리케이션으로 올려보내는 속도를 말합니다. 이 때 네트워크가 빵빵하다해서 데이터를 왕창 보냈지만, 수신단에선 소화하지 못할 수 있습니다. (수신단 overflow)

 

때문에 이를 위해서도 N을 잘 컨트롤해야합니다 이것을 flow control이라고 합니다.

 

즉, 적절한 N을 제어해야한다는 사실!

 

 

1-3. Pipelined protocol : GO-BACK-N 프로토콜

sender가 N개의 패킷을 ACK을 안받은 상태에서 보낼 수 있게 하자는 겁니다. N개를 윈도우 사이즈라고 합니다.

N개의 패킷마다 패킷번호를 붙여줘야 하는데요. 때문에 Kbit의 시퀀스넘버가 필요하게 된 것입니다.

 

base : sender가 패킷을 죽죽 보내면 그에 해당하는 ACK이 들어올 겁니다. 이 때 ACK을 받은 패킷도 있고 못받은 패킷도 있을텐데, 내가 관리하고 있는 N개의 윈도우 중에서 아직 ACK을 안받은 패킷 중 제일 오래된 것을 말합니다.

위의 파란색 예시와 같이 1,2,3이 있을 때, 1,2에 대한 ACK이 들어오고 3은 안들어왔다면, 2칸을 더 수용하기 위해 N이 뒤로 슬라이딩합니다. 우리는 이런 방식을 sliding-window protocol이라고 합니다. 이때, base는 3인 것이죠. 참고로 base는 항상 앞에 있습니다.

 

위에서는 윈도우 사이즈가 4인 것을 가정했기 때문에 ACK을 안받을 상태에서 패킷을 최대 4개를 보낼 수 있습니다.

여기서 주목해야할 점은 이전 패킷에 대한 ACK이 오지 않았다면 리시버에선 다음 패킷을 받아들이지 않습니다.(discard) 그 후 어디까지 받았는지에 대한 ACK을 보냅니다.(cumulative ACK = 누적 ACK 방식)

여기서 ACK은 1)패킷 잘받았다. 2)패킷 n까지 잘 받았다라는 의미입니다.

 

0에 대한 ACK을 받은 후 base는 1이 됩니다. 1에 대한 ACK을 받은 후 base는 2가 됩니다.

 

또한 중요한 점은 base에서는 항상 타이머를 킵니다. base 기준으로 시간을 돌립니다. 위에서는 2번으로 base가 넘어가며 다시 타이머를 키고 타임아웃이 터지면 윈도우 N에 포함된 아이들을 전부 다시 재전송을 해줍니다.

파란색 애 중 가장 앞에 있는 것을 next sqeunce number라고 합니다. 윈도우 사이즈를 2^32까지 이론적으로 쓸 수 있습니다.

 

 

- GO BACK N의 리시버 입장

ACK이 내포하고 있는 의미가 2가지 있다고 했는데요. 1)패킷 잘받았다. 2)패킷 n까지 잘 받았다 (=cummulative ACK)라고 합니다.

또 n까지는 잘 받았는데 다음은 못받았다의 의미로 loss 문제가 있는데요. sender는 duplicate ACK을 받게 될겁니다. 왜냐하면, 리시버가 패킷 3,4,5를 잘받아도 2)패킷 n까지 잘 받았다 (=cummulative ACK) 을 보내기 때문이죠.

이렇게 되면 어느 순간에는 제한 시간 안에 ACK을 못받는 애들이 보이게 됩니다. 타임아웃 이벤트가 발생해 윈도우 안에있는 모든 패킷들을 재전송하게 됩니다. 즉, Single timer로 base 기준의 타이머를 운영합니다.

 

 

SENDER

위에서 base ==nextseqnum이라는 말은 가장 오래된 패킷이라는 의미입니다. 때문에 타이머를 켜주는 것이죠.

 

RECEIVER

out-of-order라는 뜻은 이전 패킷을 못받은 상태에서 다음 패킷을 받은 상태를 의미합니다. 때문에 discard합니다. ack은 in-order까지 들어온 패킷의 ack을 보낼겁니다. (어디까지 잘 받았다)

 

but GO-BACK-N 방식은 비효율적인 방식이 보이는데요.

뒤 패킷들을 모두 버리는 것이 아깝습니다.

 

 

1-4. Pipelined protocol : Selective Repeat(SR)

그래서 나온 것이 Selective Repeat(SR) 방식입니다.

앞의 패킷이 안들어왔다고 해 뒤의 패킷을 모두 버리지 않고 keep해두는 방식을 말합니다.

sender는 고백엔과 동일하게 ack을 안받은 상태에서도 다음 패킷을 보낼 수 있습니다.

receiver는 각각의 패킷에 대해서 ack을 보냅니다. 즉, cummulative ack과 같은 방식이 아닌셈이죠.(= 이 패킷만 잘 받았다 정도)

sender는 어느 패킷이 ack을 받았고 안받았는지 관리를 해줍니다.

각각의 ack을 못받은 패킷에 대해서 time을 각각 관리합니다. 왜냐하면 각각의 패킷에 대해 ack을 들어올 건데, 어떤 패킷이 ack을 받고 안받았는데 in order가 아니기 때문입니다. (순서대로가 아니여서)

앞에 고백엔은 타이머 터지면 base부터 윈도우 안에 있는 것을 전부 보내줬다면, 셀렉티브 리핏은 각각의 타이머가 터지면 터진 패킷만 다시 전송합니다.

 

때문에 out of order여도 버퍼링해두는 겁니다. 네트워크 자원이 아깝기 때문에 Keep해두고 in-order을 맞추겠다는 의미입니다.

 

 

그렇다면, SR방식이 무조건 좋을까요?

NO!, 타이머 관리한다는 것은 프로세싱을 많이 요구합니다. 윈도우 사이즈가 커져서 패킷이 천개라면 타이머 천개가 도는 겁니다. 컴퓨터 입장에선 프로세싱이 많이 필요합니다. 그래서 이론적으론 좋지만, 타이머에 오버헤드가 커서 현재 쓰이지 않습니다.

 

TCP는 GO-BACK-N + SR을 하이브리드한 형태로 만든 겁니다.