상세 컨텐츠

본문 제목

네트워크 프로그래밍 - RTO, Karn's Algorithm, Options [EOP, NOP, MMS, Scale factor, Timestamp, SACK]

Computer Science/Network

by 2021. 11. 1. 06:25

본문

반응형

TCP의 타이머는 Retransmission, Persistence, Keepalive, TIME-WAIT 총 4개의 타이머를 사용하고 있다. 

Persistence Timer

  • 교착상태를 해결하기 위하여 사용
  • 영속 타이머가 만료되면, probe 세그먼트 전송

 

Persistence Timer는 deadlock이 발생하는 경우의 해결책으로 소개했었다.

rwnd가 0으로 전송되는 경우는 receiver의 빈 공간이 실제로 0이 되거나, silly window syndrome을 해결하기 위해서 일부러 0을 보내는 경우가 있을 것이다. 

 

rwnd로 0을 보내는 경우 중 deadlock이 발생하는 경우에 대해서 이전에 다뤘었다.

rwnd=0인 ACK을 보낸 후, rwnd가 0이 아닌 ACK을 보냈는데, 해당 ACK이 loss된 경우 deadlock이 발생하는 것이었다. 따라서 Persistence Timer를 통해 probe 세그먼트를 보내 ACK을 받아내는 방법으로 deadlock을 방지한다. 

 

Keepalive Timer

  • 오랜 기간 동안 idle 상태에 있는 것 방지
  • 서버가 2시간 동안 클라이언트로부터 세그먼트를 전송받지 못하면, probe 세그먼트 전송

TCP설정이 종료되면 sender 및 receiver의 sending buffer, receiving buffer가 삭제된다. 일반적으로는 FIN, FIN + ACK, ACK을 통한 3 way or 4 way를 통하여 정상적으로 종료하면서 buffer가 해제된다.

하드웨어적으로 클라이언트 컴퓨터가 다운되는 등 비정상적인 종료를 하게 되면, 서버입장에서는 클라이언트가 살아있다고 간주하여 buffer를 해제하지 않는다. 

 

따라서 오랫동안 idle 상태에 있다면 상대방이 죽었는지 혹은 데이터를 보내지 않는건지를 체크하기 위해서 Keepalive Timer를 사용한다. 

서버가 2시간 동안 클라이언트로부터 데이터를 받지 못하면, 작은 사이즈의 probe 세그먼트를 전송해보고 ACK이 온다면 클라이언트가 살아있다는 것을 서버가 알도록 하는 것이 Keepalive Timer이다. 

 

만약 RTT보다 조금 더 기다렸으나 ACK이 오지 않을 경우, 3 duplicated ACK에 의해서 pakcet loss가 발견되기는 하지만, congestion이 연속적이어서 후속 패킷들도 손실되는 경우에는 3 duplicated ACK으로 발견하지 못하고 Timeout으로 발견해야한다. 

RTO

여기서 RTO(Retransmission Time Out)에 대해서 알아보자.

RTO = RTTs + 4 * RTTd (그림으로)

RTO에 대해서 위 등식이 성립하는데, RTTs를 평균이라고 보고, RTTd를 편차라고 이해하면 된다. 

예를들어 평균적으로 200ms만큼 걸리고, 편차가 50ms이라면, 200 + 4 * 50 = 400ms을 RTO로 잡아놓는다. 

 

Smoothed RTT

그럼 평균값인 RTT는 어떻게 구하는가?

첫번째 측정 이후
그 이후의 측정 후

위 식에서 우변의 RTTs는 기존 평균값, RTTm은 측정값이다. 

새로히 RTT(평균)을 구한다고 하면, 새로운 측정값은 가중치를 1/8만큼 두고, 기존에 구한 값은 가중치를 7/8만큼 둔다. 

이러한 방식과 같이 가중치를 두어서 구하는 평균을 EWMA(Exponentially Weighted Moving Average)라고 한다. 

 

만약 α값이 더 크다면 새로 측정된 값이 평균에 더 많이 영향을 줄 것이고, 더 작다면 측정된 값이 평균에 더 적게 영향을 줄 것이다. TCP를 디자인 할 때 이 α값을 정해놓은 것이다.

 

첫번째 측정 때에는 최초 측정값을 평균으로 시작하고, 그 다음부터는 이전에 구했던 평균값을 RTTs 기존값으로 대입하고 새 측정값을 RTTm으로 하여 RTTs를 구한다.

 

RTT Deviation

이번에는 RTTd(편차)를 구한다. 

첫 번째 측정 이후
그 이후의 측정 후

RTTd도 마찬가지로 EWMA방식으로 가중치 β값을 두어 기존 평균과 새로 측정한 값에 가중치를 두어 계산한다. 

우변의 RTTd가 평균이며, |RTTs - RTTm|이 측정된 편차이다. 

|RTTs - RTTm| 통해 RTTm(측정값)과 측정한 RTTm으로 계산한 RTTs(평균)간의 차이를 계산한다. 

평균 RTTd에는 3/4을 곱하고, 측정된 편차 |RTTs - RTTm|에는 1/4을 곱한다. 

 

처음 측정 이후에는 측정된 값 RTTm의 절반을 RTTd(평균)으로 놓고 시작한다. 

RTTm을 측정하고 RTTs(Smoothed RTT)를 구하여 측정된 편차값을 구하고, 이전에 구한 RTTd(편차)값을 이용하여 새 RTTd값을 구한다. 

 

example

sender가 SYN을 보내고 나서 SYN + ACK이 RTO시간동안 돌아오지 않으면 packet loss로 간주한다.

RTO값은 system에서 정해놓은 default값이다. 

 

첫 측정 계산

첫 번째 측정의 상황이다.

SYN + ACK이 도착하였을 때, 처음 측정된 값 1.50s는 RTTm값이고, 첫 측정에서 RTTs = RTTm이므로 RTTs = 1.5, RTTd = 1/2 * RTTm = 0.75이다. 

RTO = RTTs + 4 * RTTd이므로 4.5이다. 

 

두 번째부터 그 이후의 측정의 상황이다.

첫 번째로 패킷을 보냈을 때 RTT 측정이 시작되고, 두 번째 패킷이 전달된 후 두 패킷에 대한 ACK이 돌아오게 되었을 때 RTT 측정이 완료된다. 

즉 RTT 측정을 하는 동안에는 또 다른 패킷 전송에 대해서 RTT 측정을 중복하지 않는다. ACK이 돌아오고 나서 RTT 측정이 끝났을 때가 되어서야 다음 패킷을 전송할 때 새로운 RTT 측정을 시작한다. 

 

새로운 패킷을 보내서 RTT 측정한 값 RTTm이 2.5s라고 하자.

먼저 RTTs(평균)을 구해야한다. RTTs는 기존 평균값 1.5 * 7/8과 새로 측정한 값 2.5 * 1.8의 합. 즉 1.625가 된다.

그 다음 RTTd(편차)를 구해야한다. 기존 편차값 0.75 * 3/4와 새로 측정한 편차값 |1.625 - 2.5| * 1/4의 합. 즉 0.78이 된다.

최종적으로 RTO = RTTs(평균) + 4 * RTTd(편차)이므로 4.74이다.

 

앞에서 계산한 첫 번째, 두 번째 측정값으로 인한 RTO 계산식으로 위 그림에 해당되는 값들을 구한 것이다. 

첫 측정은 3way handshake과정에서 SYN+ACK이 도착했을 때 측정된 값으로 구한 RTO값이고,

두 번째 측정은 두 패킷을 보낸 것에 대한 ACK이 돌아왔을 때 측정된 값으로 구한 RTO값이다.

이렇게 구한 RTO값으로 패킷을 보낼때 설정하므로, RTO값만큼 시간이 지나도 ACK이 오지 않으면 timeout으로 packet loss로 간주된다. 

 

Karn's Algorithm

a와 같은 상황에서 처음 보낸 패킷이 손실에 대한 ACK이 TimeOut될 때까지 돌아오지 않아 다시 retransmission을 보냈고, 그에 대한 ACK이 돌아왔다면,

RTT 측정값으로는 Retransmission을 보낸 시점부터 ACK이 돌아온 시점까지의 시간으로 RTO를 계산해야한다. 

 

그런에 만약 b와 같은 상황이라고 해보자. 

b의 상황은 정해놓은 RTO가 지나서 Retransmission을 보냈는데, 그 후 짧은 시간 안에 ACK이 돌아오는 상황이다. 이 상황에서 Retransmission에 대한 ACK은 오지 않았다고 하자. 그렇게 되면 Retransmission으로부터 ACK이 돌아온 시점까지의 시간은 b의 그림과 같이 측정될 것이다.

 

이러한 상황이 생기면 sender입장에서는 a와 b를 구분하지 못한다. 

따라서 b의 경우에도 이 측정값이 RTO계산에 반영되는 현상이 생기는데, 이에 대한 해결책인 Karn's Algorithm이 Retransimission에 대한 RTT측정값은 반영하지 않는다는 방법이다. 

정상적인 패킷에 대한 ACK이 올 때만 RTT측정값을 반영하고, 재전송한 Retransmission에 대한 ACK이 올 때는 반영하지 않는 방법이다. 

 

example

첫 번째 패킷을 전송한 것이 lost되고,

Time-Out으로 인하여 Retransmission을 보낼 때는 RTO를 2배로 설정해서 보내는데, 이를 Exponential Backoff of RTO라고 한다. 

그 후 Retransmission의 ACK이 올때는 RTT측정값을 반영하지 않는 것이 Karn's algorithm이다. 

 

example RTT estimation

위 그래프는 실질적으로 측정한 RTT그래프이다. 

 

Options

TCP header는 최소 20byte에서 option을 추가하면 추가로 40byte를 사용하여 최대 60byte까지 담을 수 있다.

Options에는 single byte와 multiple byte 두 종류가 존재한다.

 

End-of-option option

b 그림에서 한 줄에 4byte인데, 3byte까지 option으로 사용하고 남은 1byte를 채우는 것이 EOP option이다. 

 

No-operation option

NOP option은 앞부분을 채우기 위해서 사용되는 single-byte option이다. 

 

Maximum-segment-size option

이전에 다루었던 cwnd 및 window size에서 언급되었던 MSS에 대한 option이다. (multiple-byte)

MSS option을 통해서 default로 정해진 MSS를 변경할 수 있다. 이는 sender와 receiver가 서로 연결 setup을 하는 과정에 합의가 이루어져야 한다. 

 

참고로 option에서 kind는 option의 고유 인덱스이고, length는 option을 포함한 byte길이이다.

Window-scale-factor option

scale factor option은 추가적으로 2의 몇 승으로 window size를 늘릴 것인지에 대한 정보를 담고 있다.

 

header는 한 줄당 4byte이고, rwnd는 2byte = 16bit를 이용하여 receiver window size의 값을 전송한다. 

rwnd가 최대라면 window size는 16bit 즉 2^16 = 64 Kbyte만큼의 데이터를 전송할 수 있다.

 

RTT가 1초라고 가정하자. 

64K Byte/s = 64K * 8bit/s = 512 Kbps = 0.5 Mbps 만큼을 보낼 수 있다. 

RTT가 100ms이라면, 64KB / 0.1s = 5Mbps, 10ms라면 50Mbps이다. 

이정도의 크기로는 빠른 전송을 하기에는 무리가 있어 더 키울 방법으로 Scale factor option을 통해 늘리는 것이다. 

 

2^n만큼을 키워야한다면 n을 scale factor에 담는다.

즉 scale factor값이 3이라면, rwnd값 k에 2^3만큼을 곱한 값으로 window size를 설정하는 것이다. 

 

scale factor option 또한 연결 setup과정에서만 설정이 가능하고, 연결 이후에는 변경할 수 없다. 

 

Timestamp option

 

ACK이 도착한 시간으로 RTT를 구하기 위해서는 출발한 시간을 빼는 것이 가장 쉬운 방법이다. 따라서 sender가 패킷을 보낼 때 출발한 시간을 Timestamp option에 담아서 보낸다.

receiver는 이 출발시간을 가지고 있다가 ACK을 보낼 때 sender에게 출발 시간을 전달하면 RTT를 쉽게 구할 수 있는 것이다. 

 

Timestamp option은 또한 PAWS(Protection Against Wrapped Sequence number)를 위해 사용한다. 

sequence number는 대략 2^32 거의 40억 가량이 되는데, 파일이 매우 클 경우 40억을 넘어 sequence number가 다시 처음부터 순환하게 된다. 이 상황에서 만약 이전에 보낸 sequence와 다시 순환하여 돌아온 sequence number가 중첩되게 될 경우도 있으므로, sequence number가 같은데 Timestamp가 적혀있다면 패킷을 구분하기 더 쉬워진다. 

 

SACK

cumulative의 단점 중 하나가 패킷이 손실되면 해당 패킷부터 그 다음 패킷들의 상태를 한 번에 알 수 없으므로 이후 패킷들을 전부 한번에 보내는 것이다. SACK option은 이러한 상황에서 사용한다. 

 

 

example

위 상황은 2001:3000, 3001:4000, 6001:7000, 7001:8000 패킷을 받지 못한 상황이다. 

receiver는 못받은 패킷 이후의 패킷들 중 받은 패킷에 대한 시작 sequence number와 끝 sequence number + 1을 SACK에 저장한다. 위 그림의 경우 4001~6000까지 받았으므로 4001,6001이 SACK에 기록되고, 8001~9000패킷을 받았으므로, 8001, 9001이 기록된다. 

SACK option의 정보를 통해 이미 받은 패킷을 구분하여 보낼 수 있다.

반응형

관련글 더보기