자연계열 3번

인터넷에서는 불안정한 통신채널을 통해서 데이터를 안정적이고 효율적으로 전송하기 위해 TCP 프로토콜을 사용한다. TCP는 안정적인 전송을 위해서 재전송 시간, 일명 타임아웃(TO : TimeOut) 시간 내에 응답 데이터가 도착하지 않는 경우에는 데이터가 분실된 것으로 여겨 데이터를 재전송한다. 마치 편지를 보내고 TO 시간 내에 응답 편지가 도착하지 않으면 같은 편지를 재전송하는 방식과 같다.

이러한 TO 시간은 TCP 전송효율에 큰 영향을 미친다. 일례로 TO를 실제 편지의 왕복시간보다 작게 정하면 응답 편지가 오는 도중인데도 같은 편지를 두 번 전송하는 문제가 발생하며, TO를 크게 정하면 오래전에 편지가 분실되었어도 편지를 재전송하지 못하고 오랫동안 기다리는 문제가 발생한다.

인터넷에서는 트래픽량이 계속적으로 변화하고, 이에 따라 왕복시간도 변화하기 때문에 TO를 하나의 정적인 값으로 결정하는 것은 어렵다. 이 문제를 해결하기 위해 TCP는 왕복시간 변화에 따라 TO를 가변적으로 결정하는 방법을 사용한다. 종래의 TCP는 데이터를 전송할 때마다 매번 측정한 왕복시간을 평균하고 이를 기반으로 다음 데이터의 TO를 조정한다. 즉 TCP는 식 (1)을 이용하여 (n+1)번째 데이터 재전송 시간 TO(n+1)을 과거 n개 왕복시간의 평균 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(n)$에 비례하여 동적으로 결정한다.

$\displaystyle \mathrm{TO}(n+1)=C\times\mathrm{RTT}_{\mathrm{avg}}(n)$ …………………… (1)

이때 C는 자연수 상수를 나타낸다. 참고로 n이라는 특정 순서의 타임아웃 시간을 지칭해야 할 경우에는 TO(n)으로, 아닌 경우에는 그냥 TO로 표기한다. $\displaystyle \mathrm{RTT}_{\mathrm{avg}}$와 같은 변수들도 이러한 표기 방식을 따른다.

식 (1)에서 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}$를 계산할 때 일반적인 산술평균 식을 이용하지 않는다. 이는 산술평균이 왕복시간의 변화추세를 잘 나타내주지 못하기 때문이다. 일례로 두 개의 순차적으로 측정한 왕복시간 열, (1, 2, 3, 4, 5)와 (5, 4, 3, 2, 1)의 산술평균은 같으나, 확률적으로 예측된 다음 데이터의 왕복시간은 다를 것이다. 다음 왕복시간은 전자에서는 3이상, 후자에서는 3이하가 될 확률이 높다. 즉 산술평균 식으로 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}$를 계산하면 측정시각에 따른 표본값의 중요도를 고려하지 못하므로 변화추세를 알맞게 예측할 수 없다. 최근에 측정한 값이 먼 과거에 측정한 값보다는 미래의 값과 유사할 확률이 높기 때문에, 최근 표본이 과거의 표본에 비해 더 중요하게 고려되어야 한다.

이 문제를 해결하기 위해서 TCP는 EWMA로 지칭된 식 (2)를 이용하여 매 응답 데이터를 수신한 후에 평균 왕복시간 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(n)$을 계산한다. 즉 n번째 평균 왕복시간 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(n)$은 (n-1)번째 평균 왕복시간 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(n-1)$의 a배와 n번째 측정한 왕복시간 RTT(n)의 (1-a)배의 합으로 계산된다. 이때 a는 0과 1사이 실수 상수로, 중요도 또는 반영정도를 나타낸다.

$\displaystyle \mathrm{RTT}_{\mathrm{avg}}(n)=a\times\mathrm{RTT}_{\mathrm{avg}}(n-1)+(1-a)\times\mathrm{RTT}(n)$ …………………… (2)

일례로 왕복시간 열이 (4, 7, 8)일 때, 1번째 평균 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(1)$은 (1-a)×4, 2번째 평균 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(2)$는 a(1-a)×4 + (1-a)×7, 3번째 평균 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(3)$은 a{a(1-a)×4 + (1-a)×7} + (1-a)×8로 계산된다. $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(1)$을 계산할 때 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(0)$은 0으로 가정한다. 3번째 평균을 계산할 때는 측정된 순서에 따라서 왕복시간이 평균에 반영된 비율이 a×a×(1-a), a×(1-a), (1-a)로 감소된다. 즉 식 (2)를 이용하면 왕복시간이 오래전에 측정되었을수록 평균 왕복시간에 작게 반영된다.Correction. 반영 비율을 $\displaystyle a^2(1-a),a(1-a),1-a$ 순서로 나열한 문장에서 “감소된다”는 “증가한다”의 오기이다. 그러나 원칙에 따라 원문 표기를 그대로 실었다.

그러나 식 (1)에서 TO는 평균 왕복시간에만 의존하기 때문에 왕복시간 분포도를 정확하게 반영할 수 없는 문제가 있다. 일례로 a가 0.125일 때 두 개의 왕복시간 열, (8, 8, 8, 8, 8)과 (8, 10, 6, 15, 7)의 EWMA 평균은 8로 같으나, 두 개의 열에서 예측되는 다음 왕복시간은 다를 것이다. 다음 데이터의 TO가 전자에서는 8, 후자에서는 15 정도를 갖는 것이 데이터의 손실 여부를 정확하게 예측할 수 있을 것이다. 즉 평균이 같더라도 측정한 왕복시간의 변화가 크면 TO는 큰 값을 가져야 할 것이다.

이 문제를 해결하기 위해서 현재 TCP에서는 식 (3)을 이용하여 왕복시간 분포도의 차이를 TO에 반영한다. 즉 TO(n+1)은 $\displaystyle \mathrm{RTT}_{\mathrm{avg}}(n)$과 왕복시간의 분포 정도를 나타내는 왕복시간 표준편차 $\displaystyle \mathrm{RTT}_{\mathrm{dev}}(n)$에 C를 곱한 값의 합으로 결정된다.

$\displaystyle \mathrm{TO}(n+1)=\mathrm{RTT}_{\mathrm{avg}}(n)+C\times\mathrm{RTT}_{\mathrm{dev}}(n)$ …………………… (3)