전송 제어 프로토콜(transmission control protocol, 이하 TCP)은 현대의 네트워크를 구성하는 가장 핵심적인 규약으로, 패킷이 전송된 후 전송이 성공적으로 완료되었음을 알려주는 확인응답(acknowledgement, 이하 ACK)을 다시 보내는 방식으로 전송의 신뢰성을 보장합니다.
그런데 만약 패킷이 전송될 때마다 ACK를 보내게 된다면, 가뜩이나 복잡한 네트워크에 큰 부하를 추가로 줄 것이 뻔합니다. 이를 회피하기 위해서 TCP에는 패킷이 전송되었을 때 바로 ACK를 보내지 않고 다른 패킷이 전송되는 것을 기다렸다가 적절한 때에 지금껏 들어온 패킷들에 대한 ACK를 한 번에 처리하는 기술이 있습니다. 이를 지연된 확인응답(delayed acknowledgement)이라고 부릅니다. 그런데 여기서 또 다른 문제가 발생하는데요. TCP에 따르면 패킷을 전송한 쪽은 해당 패킷에 대한 ACK를 받아야 다음 작업을 진행할 수 있기 때문에, 각 패킷의 ACK가 너무 늦은 때에 도달한다면 네트워크 서비스의 품질이 매우 저하가 될 터입니다.
여기서 우리는 흥미로운 온라인 최적화 문제를 맞닥뜨리게 됩니다. 패킷 은 시간이 흐름에 따라 주어집니다. 즉, 어느 시점에 미래에 패킷이 어떻게 들어올지는 정확히 알 수 없습니다. 이 와중에 우리는 들어온 모든 패킷에 대해 ACK를 보내주어야 합니다. 이 상황에서 우리는 다음 두 가지 목표를 동시에 달성해야 합니다. 네트워크에 가해지는 부하를 줄이기 위해서는 여러 패킷을 묶어서 한 번에 ACK를 보내야겠지만, 서비스의 품질을 위해서는 각 패킷의 ACK가 너무 늦은 때에 전송되어서는 안 됩니다. 어떻게 하면 미래에 대한 정확한 정보 없이 두 마리 토끼를 적절하게 잡을 수 있을까요?
문제 정의
문제를 엄밀히 정의해 보겠습니다. 입력으로는 패킷들이 주어집니다. 각 패킷은 도착 시각이 정해져 있으며, 해당 시각에 도달하기 전에는 해당 패킷에 대한 정보는 알 수 없습니다. 매 시각 우리는 ACK를 할지 말지를 결정합니다. 만약 ACK를 하겠다고 결정하면 현재까지 도착한 패킷 중에서 직전까지의 ACK로 처리되지 않은 패킷에 대한 ACK를 한 번에 진행하게 됩니다.
이러한 상황에서 우리는 최소의 "비용"으로 도착하는 모든 패킷에 대해 ACK를 보내야 합니다. 여기서 우리가 고려하는 비용은 크게 두 가지로 구분됩니다. 첫 번째는 실제로 ACK를 수행한 횟수입니다. 두 번째는 각 패킷마다 ACK를 보내기까지 지연된 시간입니다. 두 마리 토끼를 모두 잡기 위해서 본문에서는 이 비용들을 모두 합한 것을 최소화하는 것을 목표로 삼습니다.
기호를 사용하여 문제를 좀더 간결히 표현하도록 하겠습니다. 입력되는 모든 패킷의 집합을 \(P\)라고 부르고, 각 패킷 \(p \in P\)는 \(t(p) > 0\) 시각에 도착한다고 하겠습니다. 우리의 출력은 \(|A| \geq 1\)이면서 \(\max A \geq \max_{p \in P} \{t(p)\}\)를 만족하는 시각의 집합 \(A\)입니다. \(A\)의 크기를 \(k\), 여기에 포함된 시각을 오름차순으로 \(a_1 \leq \ldots \leq a_k\)라고 하겠습니다. 그러면 매 \(i = 1, \ldots, k\)에 대해, \( (a_{i-1}, a_i] \) 사이에 도착한 패킷들 \( P_i := \{ p \in P \mid t(p) \in (a_{i-1}, a_i] \} \)는 모두 \(a_i\) 시각에 수행되는 ACK에 의해 처리됩니다.(단, \( a_0 := 0 \)이라고 하겠습니다.) 즉, 각 패킷 \(p \in P_i\)는 \( a_i - t(p) \)만큼 지연됩니다. 그러므로 우리의 목표는 \[ k + \sum_{i = 1}^k \sum_{p \in P_i} (a_i - t(p)) \]를 최소화하는 \(A\)를 찾는 것으로 다시 표현할 수 있습니다.
2-경쟁 알고리즘
이제 이 문제를 경쟁적으로 해결하는 알고리즘을 생각해 봅시다. 어떤 패킷이 도착했을 때 우리는 이 패킷에 대한 ACK를 바로 처리하여 줄지, 아니면 미룰지를 결정해야 합니다. 미래에 대한 정보를 알고 있다면 그 선택이 수월할 것입니다. 만약 미래에 다른 패킷이 곧장 도착한다면 이 패킷까지 기다린 후 한 번에 ACK를 하는 것이 비용적으로 이득일 것입니다. 하지만 만약 이후에 패킷이 도착하지 않거나 아주 늦은 때에 도착한다면, 해당 패킷에 대한 ACK를 즉시 하는 것이 이득입니다.
문제는 미래에 대한 정보를 알 수 없다는 데에 있죠. 따라서 우리는 이후에 패킷이 바로 도착하는 상황과 늦게 도착하는 상황 모두에 경쟁적인 답안을 출력해야 합니다. 이를 해결하는 가장 자연스러운 방법은 처음에는 약간 기다리다가 지연 시간이 어떤 역치를 넘어가면 그때 ACK를 처리하는 것입니다. 이러한 전략은 이전에 다루었던 스키 대여 문제(ski rental problem)에서도 확인할 수 있을만큼 온라인 최적화 문제를 해결하는 대표적인 방법입니다.
[스키 대여 문제 / Ski Rental Problem] 문제 정의 & Break-Even Algorithm
이번 포스트에서는 기초적인 온라인 문제 중 하나인 스키 대여 문제(ski rental problem)를 다루어 보도록 하겠습니다. 온라인 문제 및 온라인 알고리즘이 무엇인지는 이전 글을 참조해 주시기 바랍
gazelle-and-cs.tistory.com
결국 중요한 것은 역치를 어떻게 설정하느냐에 달려 있습니다. 위 글에서 소개된 스키 대여 문제 알고리즘은 어떻게 설정하였는지 잠깐 살펴봅시다. 스키를 구매하는 가격이 \(B\)라고 할 때, 알고리즘은 \(B\) 번째 날에 스키를 구매하고, 그 전까지는 스키를 대여하기만 합니다. 이를 통해 스키장이 \(B\) 번째 날 이후에도 여는 상황에서도 최적해의 최대 두 배의 비용만 지불합니다. 같은 이치를 이 문제에 적용해 보자면 다음과 같을 것입니다. 어떤 패킷이 도착했을 때 바로 ACK를 보내는 것은 1의 비용을 발생시키므로, 도착한 시각으로부터 1의 시간만큼 기다린 후에 ACK를 보낸다면 최적해 대비 최대 두 배의 비용만 지불할 것임을 유추할 수 있습니다.
하지만 이 문제는 여기서 한 가지 더 복잡한 부분이 있습니다. 다음의 상황을 생각해 봅시다(그림 1). 두 패킷 \(p_1\), \(p_2\)가 각각 \(t(p_1) = 0.5\), \(t(p_2) = 0.6\)의 시각에 도착한다고 해 보겠습니다. 이후에 패킷이 더 들어오지 않는다면, 최적해는 \(t(p_2) = 0.6 \) 시각에 ACK를 보내는 것이 고 그 비용은 총 1.1입니다. 이제 알고리즘의 입장에서 생각해 보겠습니다. \(t(p_2) = 0.6\) 시각에 도달하기 전에 알고리즘은 \(t(p_1) + 1 = 1.5\) 시각에 ACK를 보낼 생각을 하고 있을 것입니다. 하지만 \(p_2\)가 도착한 후에도 1.5 시각에 ACK를 보내는 것을 고수한다면, 알고리즘은 최종적으로 2.9의 비용을 내게 됩니다. 최적해 비용의 두 배를 넘기는 이유는 \(p_2\)의 지연 시간이 비용에 추가되기 때문입니다.
그러면 이 상황에서 알고리즘은 ACK를 보내는 시각은 언제로 수정하면 좋을까요? 여전히 총 지연 시간이 ACK를 보내는 비용인 1과 동일해 지는 때로 설정하는 것이 자연스럽겠죠. 하지만 여기서 우리는 한 가지 절약할 수 있는 부분이 있습니다. 바로 최적해에서도 \( p_1 \)은 \(t(p_2) - t(p_1) = 0.1\) 만큼 지연되었다는 것이죠. 따라서 우리는 입력된 두 패킷 \( p_1 \), \( p_2\)가 \(t(p_2)\) 이후에 지연된 총 시간만 따져도 괜찮습니다. 이를 종합하면 \( t(p_2) + 0.5 = 1.1 \) 시각에 ACK를 보내는 것으로 결론을 내릴 수 있습니다. 그 비용은 2.1로 최적해 비용의 두 배 이내에 들어온다는 것을 확인하시기 바랍니다.
앞에서 논의한 아이디어를 구체화하면 다음과 같은 알고리즘을 얻을 수 있습니다.
알고리즘 1. 지연된 TCP 확인응답 2-경쟁 알고리즘
- \(a \gets \infty\), \(b \gets \infty\), \(c \gets 0\)
- 매 \(t\) 시각에 다음의 경우 중 하나라도 발생하면 각각 수행한다. 두 경우가 동시에 발생하면 첫 번째 경우를 먼저 처리한 후 두 번째 경우를 처리한다.
- \(t\) 시각에 도착하는 패킷이 존재하는 경우
- 이 때 도착한 패킷의 개수를 \(x\)라고 하자.
- \(c \gets c + x\)
- 만약 \( t + \frac{1}{c} < a \)라면, \(a \gets t + \frac{1}{c}\), \(b \gets t\)
- \(t = a\)인 경우
- 현재까지 도착한 패킷 중 아직 ACK를 보내지 않은 패킷들에 대한 ACK를 한 번에 전송한다.
- \(a \gets \infty\), \(b \gets \infty\), \(c \gets 0\)
- \(t\) 시각에 도착하는 패킷이 존재하는 경우
알고리즘의 기술에서 빨간색 글씨로 처리된 \(b\)에 관한 부분은 분석을 위한 것으로, 해당 부분이 없어도 알고리즘은 잘 동작합니다. 알고리즘이 올바른 출력을 준다는 것은 어렵지 않게 확인할 수 있습니다.
이제 이 알고리즘의 성능을 분석해 보도록 하겠습니다. 알고리즘이 ACK를 보낸 때를 순서대로 \(a_1, \ldots, a_k\)라고 부르겠습니다. 편의를 위해 \(a_0 := 0\)으로 정하겠습니다. 마지막으로, 각 \(i = 1, \ldots, k\)에 대해, \(a_i\) 시각에 ACK를 보낼 때의 \(b\) 값, 다시 말해, 단계 2-ii-b를 수행하기 직전의 \(b\) 값을 \(b_i\)라고 부르겠습니다. 먼저 살펴볼 사실은 최적해가 일반성을 잃지 않고 가질 수 있는 성질입니다.
정리 1. 최적해의 특징
일반성을 잃지 않고 최적해는 각 \(i = 1, \ldots, k\)에 대해 \( (a_{i-1}, a_i ] \) 중 적어도 한 번 ACK를 전송한다.
[증명] 만약 최적해가 어떤 \(i\)에 대해 \( (a_{i-1}, a_i] \) 사이에 ACK를 한 번도 보내지 않았다고 해 보겠습니다. 그러면 그 사이에 도착하는 패킷들은 전부 \(a_i\) 시각 이후에 ACK 될 것입니다. 그중에서도 특히 \( (a_i, b_i] \) 사이에 도착한 패킷들을 생각해 보겠습니다. 그 개수는 \(t = b_i\)일 때, 단계 2-ii-b를 수행한 후의 \(c\) 값일 것이며, \(a_i\)와 \(b_i\)의 정의에 의해 \( a_i = b_i + \frac{1}{c} \)를 만족합니다. 다시 말해, 이 패킷들이 \(b_i\) 시각부터 ACK 되기까지 지연된 총 시간이 1보다 크거나 같다는 것을 알 수 있습니다. 따라서 기존 최적해에다가 \(b_i\) 시각에 추가로 ACK를 해 준다면, 그 비용은 기존 최적해보다 낮아지기만 합니다. ■
이제 \(i \in \{ 1, \ldots, k \} \) 를 하나 고정하고, \( (a_{i - 1}, a_i] \) 사이에 도착한 패킷들 \(P_i\)만 고려해 보겠습니다. 정리 1에 의해 이 시간 동안 최적해가 총 \( \ell \) 번의 ACK를 수행했다고 해 보고, 그 시각을 각각 오름차순으로 \(a^*_1 < \ldots < a^*_\ell \)이라고 부르겠습니다. 즉, \( a_{i - 1} < a^*_1 \)과 \( a^*_\ell \leq a_i \)가 성립합니다. 편의를 위해 \( a^*_0 := a_{i-1} \)로 정의하겠습니다. 각 \(j = 1, \ldots, \ell \)에 대해, \(P^*_j\)를 \( (a^*_{j-1}, a^*_j] \) 사이에 도착한 패킷의 집합이라고 하겠습니다. 나아가 \( P^*_{\ell+1} \)은 \( (a^*_\ell, a_i] \) 사이에 도착한 패킷의 집합으로 정의하겠습니다. 마지막으로 각 \(j = 1, \ldots, \ell \)에 대해, \(a^*_j\) 시각에 알고리즘이 단계 2-i-b를 수행한 후의 \(c\) 값을 \( c_j \)라고 부르겠습니다. 이 값은 \[ c_j = \sum_{j' = 1}^j |P^*_{j'}| \geq |P^*_j| \tag{1} \]를 만족한다는 것을 확인하시기 바랍니다. 또한 알고리즘의 단계 2-i-c에 의해, 우리는 \[ a_i \leq a^*_j + \frac{1}{c_j} \tag{2} \]임을 알 수 있습니다.
이제 최적해가 이 구간에서 적어도 얼마만큼의 비용을 발생시키는지 구하여 보겠습니다. 각 \( j=1, \ldots, \ell \)에 대해, \( P^*_j \)의 패킷들은 모두 \( a^*_j \) 시각에 ACK가 됩니다. 따라서, 최적해는 적어도 \( \sum_{p \in P^*_j} (a^*_j - t(p)) + 1 \)의 비용을 발생시킵니다. 이를 정리하면, \[ \begin{array}{rl} \displaystyle \sum_{p \in P^*_j} (a^*_j - t(p)) + 1 & =\displaystyle \sum_{p \in P^*_j} (a^*_j - t(p)) + |P^*_j| \left( (a^*_j + \frac{1}{|P^*_j|}) - a^*_j \right) \\ & \displaystyle \geq \sum_{p \in P^*_j} (a^*_j - t(p)) + |P^*_j| \left( (a^*_j + \frac{1}{c_j}) - a^*_j \right) \\ & \displaystyle \geq \sum_{p \in P^*_j} (a^*_j - t(p)) + |P^*_j| (a_i - a^*_j) \\ & \displaystyle = \sum_{p \in P^*_j} (a_i - t(p)) \end{array} \tag{3} \]를 이끌어 낼 수 있습니다. 여기서 첫 번째 부등식은 식 (1)에 의해서 유도할 수 있으며, 두 번째 부등식은 식 (2)에 의해 보장됩니다. 마지막으로 최적해는 \(P^*_{\ell + 1}\)의 패킷들에 대한 ACK를 이 구간에서 보내지 않으므로, 적어도 \[ \sum_{p \in P^*_{\ell + 1}} (a_i - t(p)) \tag{4} \]의 지연 시간을 발생시킨다는 것을 알 수 있습니다.
위에서 얻은 식 (3)과 식 (4)를 종합하면, 최적해는 \( (a_{i - 1}, a_i] \) 구간에서 적어도 \[ \sum_{j = 1}^{\ell + 1} \sum_{p \in P^*_j} (a_i - t(p)) = \sum_{j \in P_i} (a_i - t(p))\]만큼의 비용을 발생시킵니다. 이 값은 곧 알고리즘이 이 구간에서 발생시키는 총 지연 시간과 같습니다. 알고리즘은 추가로 \(a_i\) 시각에 1의 비용으로 ACK를 보냅니다. 하지만, 이 비용은 \[ \sum_{p \in P_i} (a_i - t(p)) \geq c_i (a_i - b_i) = 1 \]이므로 이 구간에서 발생된 총 지연 시간을 넘지 않습니다. 따라서 각 구간에서 알고리즘이 발생시키는 비용은 최적해가 발생시키는 비용의 두 배를 넘지 않는다는 것을 이끌어 내게 됩니다. 이는 아래 정리의 증명이 됩니다.
정리 2. 알고리즘의 경쟁성
알고리즘 1은 지연된 TCP 확인응답 문제를 해결하는 결정론적 2-경쟁 알고리즘이다.
결정론적 알고리즘 경쟁비 하한
이전 절에서 우리는 지연된 TCP 확인응답 문제를 2의 경쟁비로 해결하는 결정론적 알고리즘을 공부했습니다. 이제 남은 질문은 과연 더 잘할 수 있는지겠죠. 눈치를 채신 분이 계실 수 있을 것 같은데, 결정론적 알고리즘의 경우에는 2보다 좋은 경쟁비를 갖는 것은 어렵습니다. 이번 절에서는 아래의 정리를 증명해 보도록 하겠습니다.
정리 3. 결정론적 알고리즘의 경쟁비 하한
임의의 상수 \(\varepsilon > 0\)에 대해, 지연된 TCP 확인응답 문제를 해결하는 어떠한 결정론적 알고리즘도 \( 2 - \varepsilon \) 보다 좋은 경쟁비를 가질 수 없다.
임의의 결정론적 알고리즘을 하나 생각해 보겠습니다. 우리는 결정론적 알고리즘의 경쟁비 하한에 관심이 있으므로 이 알고리즘의 경쟁비를 항상 \(2-\varepsilon\) 이상이 되도록 만드는 적응형 상대방(adaptive adversary)을 만드는 것이 증명의 목표입니다.
\(n\)을 \( n > \frac{2}{\varepsilon} - 1 \)을 만족하는 충분히 큰 홀수라고 하겠습니다. 또, \(\tau\)는 \( 0 < \tau < \frac{n+1}{2n} \varepsilon - \frac{1}{n} \)을 만족하는 충분히 작은 양수라고 정의하겠습니다. \(n\)이 충분히 크기 때문에 그러한 \(\tau\)를 반드시 설정할 수 있습니다. 이제 다음과 같이 동작하는 적응형 상대방을 생각해 보겠습니다. 그림 2를 참고하세요.
- 알고리즘에게 \(\tau\) 시각에 도착하는 패킷을 입력한다. 알고리즘이 이 패킷에 대한 ACK를 전송한 시각을 \(d_1\)이라고 하자. 만약 \(d_1 \geq 1\)이라면 \(n\)을 1로 두고 종료한다. 만약 \(d_1 < 1\)이라면, 다음으로 진행한다.
- 알고리즘에게 \(d_1 + \tau\) 시각에 도착하는 패킷을 입력한다. 알고리즘이 이 패킷에 대한 ACK를 직전에 보낸 ACK로부터 \(d_2\) 시간 후에 전송했다고 하자. 즉, 이 ACK는 \(d_1 + d_2\) 시각에 전송된다. 만약 \(d_2 \geq 1\)이라면 \(n\)을 2로 두고 종료한다. 만약 \(d_2 < 1\)이라면, 다음으로 진행한다.
- 같은 패턴으로, 각 \( i = 1, \ldots, n-1 \)에 대해, 적응형 상대방은 \(\sum_{j = 1}^{i-1} d_j + \tau \) 시각에 패킷을 하나 도착시킨다. 알고리즘은 이 패킷에 대한 ACK를 직전 ACK로부터 \(d_i\) 이후의 시각에, 즉, \(\sum_{j = 1}^i d_j\) 시각에 전송한다고 하자. 만약 \( d_i \geq 1 \)이라면, \(n\)을 \(i\)로 두고 종료한다. 만약 \(d_i < 1\)이라면, 다음으로 진행한다.
- 마지막에 적응형 상대방은 \(\sum_{j = 1}^{n-1} d_j + \tau\) 시각에 패킷을 하나 도착시키고 종료한다. 알고리즘은 이 패킷에 대한 ACK를 직전 ACK로부터 \(d_n\) 이후의 시각에 전송한다고 하자.
이제 이 적응형 상대방을 상대로 알고리즘이 얼마큼의 경쟁비를 가지는지 구해 보겠습니다. 적응형 상대방이 입력을 끝내는 조건은 \(d_n \geq 1\)이거나 처음에 설정한 \(n\) 만큼의 패킷을 알고리즘에 입력하였을 때입니다. 먼저 \(d_n \geq 1\)인 경우를 살펴 보겠습니다. 이 경우에는 \(n\)이 다시 설정되므로 짝수일 수 있으나, 편의 상 \(n = 2k+1\)인 홀수라고 하겠습니다. \(n\)이 짝수일 경우에 대한 증명은 거의 동일한 방식으로 보일 수 있습니다.
먼저 알고리즘이 이 적응형 상대방을 발생시킨 비용을 계산해 보겠습니다. 각 \(i = 1, \ldots, n\)에 대해, \(i\) 번째 패킷은 정확히 \(\sum_{j = 1}^{i - 1} d_j + \tau\) 시각에 입력되며, 알고리즘은 이를 \( \sum_{j = 1}^i d_j \) 시각에 처리합니다. 따라서 이 패킷의 지연 시간은 \(d_i - \tau\)입니다. 알고리즘은 총 \(n\) 개의 ACK를 전송하므로, 이를 종합하면 알고리즘이 발생시킨 비용이 \[ \mathsf{ALG} = \sum_{i = 1}^n (d_i - \tau) + n \geq \sum_{i = 1}^{n - 1} d_i + (n+1) - n \varepsilon \tag{5} \]가 된다는 것을 알 수 있습니다. 여기서 부등식은 \(d_n \geq 1\)이라는 가정에서 얻을 수 있습니다.
이제 최적해 비용의 상한을 구해 보겠습니다. 이를 위해서 두 개의 답안을 제시할 것입니다. 두 답안의 비용 중 더 작은 값은 두 답안의 비용의 평균보다는 작거나 같을 것이므로, 두 답안의 비용의 평균을 최적해 비용의 상한으로 사용할 예정입니다. 이제 다음의 두 답안을 생각해 봅시다. \(n = 2k+1\)이 홀수라는 사실을 다시 한 번 확인하시기 바랍니다.
- 매 홀수 번째 패킷이 도착했을 때 ACK를 전송하는 답안
- 매 짝수 번째 패킷이 도착했을 때 ACK를 전송하고, 마지막 패킷이 도착했을 때 ACK를 전송하는 답안
답안 1을 먼저 고려해 봅시다. \(n\)이 \(2k+1\)의 값을 갖는 홀수라고 하였으므로, 답안 1은 총 \(k+1\) 번의 ACK를 전송합니다. 또한, 매 짝수 번째의 패킷은 다음 홀수 번째 패킷이 도착했을 때 ACK가 되므로, 각 \(i = 2, 4, \ldots, 2k \)에 대해, \(i\) 번째 패킷의 지연 시간은 \(d_i\)가 됩니다. 이를 종합하면, 답안 1의 비용은 \[ (d_2 + d_4 + \ldots + d_{2k}) + (k + 1) \]과 같습니다. 다음으로 답안 2를 살펴 보겠습니다. 답안 2도 매 짝수 번째 패킷이 도착했을 때와 마지막 패킷이 도착했을 때 ACK를 보내므로 총 \(k+1\) 번 ACK를 전송합니다. 마지막 패킷을 제외한 모든 홀수 번째 패킷은 다음 짝수 번째 패킷이 도착했을 때 처리되므로, 각 \( i = 1, 3, \ldots, 2k-1 \)에 대해, \(i\) 번째 패킷의 지연 시간은 \(d_i\)입니다. 따라서 답안 2의 비용은 \[ (d_1 + d_3 + \ldots + d_{2k-1}) + (k+1) \]이 됩니다.
최적해 비용은 위 두 비용의 평균을 넘지 않을 것이므로, 우리는 다음과 같은 최적해 비용의 상한을 구할 수 있습니다. \[ \mathsf{OPT} \leq \frac{1}{2} \left( \sum_{i = 1}^{2k} d_i + 2(k+1) \right) = \frac{1}{2} \left( \sum_{i = 1}^{n-1} d_i + (n+1) \right) \tag{6} \] 여기서 등식은 \(n = 2k + 1\)이라는 사실에서 얻었습니다. 식 (5)와 식 (6)을 통해 우리는 경쟁비의 하한이 \[ \frac{\mathsf{ALG}}{\mathsf{OPT}} \geq \frac{\sum_{i = 1}^{n - 1} d_i + (n+1) - n\tau}{(1/2)(\sum_{i = 1}^{n-1} d_i + (n+1))} \geq 2 - \frac{2n\tau}{n+1} > 2 - \varepsilon \]이 된다는 것을 확인할 수 있습니다. 여기서 마지막 부등식은 \( \tau < \frac{n+1}{2n} \varepsilon \)이라서 성립합니다.
마지막으로 처음에 정해진 \(n\) 만큼의 패킷을 알고리즘에 입력시킨 후에 종료한 경우를 생각해 보겠습니다. 이때는 식 (5)의 우변을 사용할 수는 없지만, 등식으로 얻어지는 식은 그대로 사용할 수 있습니다. 이를 식 (6)의 최적해 비용 상한과 엮으면, 다음과 같이 \[ \frac{\mathsf{ALG}}{\mathsf{OPT}} \geq \frac{\sum_{i = 1}^{n} d_i + n - n\tau}{(1/2)(\sum_{i = 1}^{n-1} d_i + (n+1))} \geq 2 - \frac{2(n\tau + 1)}{n+1} > 2 - \varepsilon \]이 됨을 알 수 있습니다. 여기서 마지막 부등식은 \( \tau < \frac{n+1}{2n} \varepsilon - \frac{1}{n} \)이기 때문에 만족합니다. 이것으로 정리 3에 대한 증명을 마칩니다.
마치며
오랜만에 글을 적습니다. 그동안 저는 무사히 박사를 받고, 현재는 폴란드에서 포닥을 하고 있는 중입니다. 박사까지 모두 한국에서 공부한지라 해외에서 연구를 한다는 것이 처음에는 낯설었는데, 수 달이 지난 지금은 그래도 좀 적응이 된 것 같습니다.
폴란드에 온 후, 이런저런 새로운 문제들에 대해 공부할 기회가 많이 있었습니다. 이 글의 주제인 지연된 TCP 확인응답 문제도 그중 하나입니다. 이전에는 어렴풋이만 알고 있던 문제였는데, 공부해 보니 생각했던 것보다 더 복잡하고 흥미로운 문제임을 깨달았습니다. 여기에 온 후 이렇게 새로 발견한 문제들이 몇 개 더 있습니다. 이것들에 대해서도 언젠간 포스팅할 수 있었으면 합니다.
본문에서도 슬쩍 언급하였지만, 이 문제는 본질적으로 스키 대여 문제와 비슷한 철학을 공유합니다. 그 때문인지는 모르겠지만, 이 문제 또한 랜덤 알고리즘으로는 \(\frac{e}{e-1}\)의 경쟁비를 얻을 수 있으며, 이 경쟁비는 랜덤 알고리즘으로 얻을 수 있는 최선의 성능입니다. 다음에는 이에 대해서도 다루어 보도록 하겠습니다.
읽어 주셔서 고맙습니다.
참고 자료
[1] Daniel R. Dooly, Sally A. Goldman, and Stephen D. Scott. "TCP dynamic acknowledgment delay: theory and practice." Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998.
[2] Anna R. Karlin, Claire Kenyon, and Dana Randall. "Dynamic TCP acknowledgement and other stories about e/(e-1)." Proceedings of the thirty-third annual ACM symposium on Theory of computing. 2001.