Pipelining _ Go Back N, Selective Repeat

Stop and Wait

 

   하나의 패킷을 전송하고 그에 대한 응답을 기다리는 방식. sequence number을 이용하여 중복 패킷을 확인하고, timer로 loss된 패킷을 파악하여 재전송한다.

 

   RDT_ stop and wait

 

Pipelining

 

   하드웨어는 우리의 처리보다 빠르고, 효율을 위해선 보다 더 하드웨어를 낭비하지 않고 사용하기 위해 노력해야한다고 컴퓨터 구조를 공부하면서 생각했다.  마찬가지로 네트웨크에서도 데이터를 병렬적으로 처리하여 낭비없는 채널(송신자)의 이용을 위해 파이프라이닝을 이용한다.     

   

   전송 시에 패킷의 첫 비트를 전송한 시점부터 처음 응답을 받을 때까지 송신자가 얼마나 분주하게 일을 하였나를 Utilization으로 한다. 아래 그림에서 왼쪽 그림처럼 한 전송에 한 패킷만을 전송하면 RTT 동안 송신부는 아무 일도 하지 않는 반면, 한 전송에 3개의 패킷을 처리하면 같은 (RTT+L/R) 동안 더 많은 처리(3*L/R)를 가능하게 한다. 

 

송신 당 1개의 패킷을 보내는 방식과 3개의 패킷을 보내는 방식의 효율률 비교.  RTT는 Round trip time (왕복 지연 시간), L은 패킷의 크기, R은 전송률을 의미한다. 

Go Back N

 

   Go_back_N 방식은 한 전송 시의 패킷의 개수를 정하여 전송한다. 버퍼에 그 개수만큼의 집합을 저장하여 누락 시 버퍼 안의 해당 집합을 시작 패킷부터 끝까지 다시 전송한다. 수신부는 받아야할 순서의 패킷만을 기다리고 해당 순서가 아닐 경우 무조건 폐기시킨다.  이때 전송할 한 집합 단위, 버퍼를 window라고 하고 가장 최근에 정상적으로 수신한 패킷의 순서 넘버를 기억하고 응답에 첨부하는 것으로 다음 패킷의 수신 여부를 결정한다. 이를 Cumalative ACK라고 한다.

 

 Go_back_N 방식, window size : 4

   ack이 들어오면 중복을 확인하고 정상적인 수신이 확인된다면 해당 패킷을 바로 바로 상위 계층으로 전달하고 window의 시작점을 한 패킷씩 뒤로 한다. 그렇지 않고 중복이 확인된다면 수신된 응답(ack)과 전송된 window 내의 이후 pkt들을 폐기하고 timer를 기다린다.

 

   timer가 작동하면 패킷의 loss를 인지하고 한 window의 모든 패킷을 재전송한다. 위 그림에서는 window 사이즈가 4 밖에 안되지만 실제 통신의 window 사이즈는 매우 크고 한 패킷의 loss로 나머지 패킷을 폐기하고 다시 재전송하는 것은 비효율적이라는 단점이 있다.

 

Selective Repeat

 

   GBN의 비효율성을 해결하기 위한 방식이다. SR은 loss된 패킷을 확인하여 따로 재전송 할 수 있다. 이를 위해 송신부 뿐만 아니라 수신부에도 버퍼를 둔다. 순서에 상관없이 수신하고 응답하여 손실된 패킷만 재전송하고, 수신부 버퍼가 가득차면, 즉 한 window가 모두 전송되면 상위 계층으로 한번에 전달한다.

   

Selective Repeat 방식, window size : 4

   수신에 문제가 없는 상황에서는 GBN 방식과 동일하게 송신부에서는 window의 패킷을 송신하고, 수신부에서는 들어오는 패킷을 상위 계층으로 전달하고 응답한다.

 

   ack에 따라 다음 순서가 아닌 패킷이 수신된다면 수신에 문제가 있음을 확인하고 수신부의 버퍼에 우선 수신되는 패킷을 저장하고 수신되는 패킷의 순서 번호만 응답한다. 손실된 패킷만을 재전송하여 수신부의 패킷이 가득차면 한번에 패킷을 상위 계층으로 전달한다.

 

window size : 4, sequence size : 5 일 때, ack0,1,2,3 이 loss된 상황

   헤더가 작을수록 오버헤드가 적기 때문에 순서 번호를 최대한 중복시켜 표현할 비트 수를 줄이는 것이 효율적이다. 위 그림처럼 sequence num를 너무 작게 설정하는 경우 수신된 패킷이 재전송된 패킷인지, 새로 전송된 패킷인지 확인할 방법이 없다. 따라서 sequence number는 적어도 이전 window와 현재의 window를 구별은 가능하도록 해야하며 최소한 window 사이즈의 2배는 되어야한다. stop and wait에서 sequence number를 0과 1만 사용한 이유와 같고, 또 같은 이유로 구별을 위한 사이즈가 window 단위로 늘어난 것으로 생각하면 된다.

 

  SR 방식은 재전송할 패킷을 선택하여 전송하기 때문에 재전송에서 GBN보다 효율적이나, 모든 패킷에 각각 타이머를 필요로 하므로 많은 비용이 발생한다는 단점이 있다.