Abstract
: 결합된 wireless link가 있는 network를 통해 TCP application progarm에 대한 congestion control을 재설계한다. congestion measure로 queueing delay를 사용하여, network utility maximization problem에 대한 window-control oriented implicit primal-dual solver를 개발하여 optimal TCP congestion control를 달성한다. 이를 QUIC-TCP congestion control algorithm이라 부른다.
Introduction
: 인터넷을 통한 대부분의 트래픽은 network configuration information이 필요하지 않아 extsntibility와 scalability에 적합한 TCP(Transmission Control Protocol)-based protocol(HTTP, SMTP, FTP, ...)에 의해 전달된다. 그러나 lossy wireless links와 large bandwidth-delay product 환경에서 성능이 좋지 않았다.
Lagrange duality based network fluid model
: Optimization 도구를 활용하여 NUM(Network Utility Maximazation) paradigm이 cross-layer shemes와 network protocol을 분석하고 설계하기 위해 제시되었다. 이러한 framework에서 congestion control은 source rate controller로 모델링되고 link의 queue length는 Largrange multiplier로 사용된다. 이러한 approach를 기반으로 많은 gradient 유형의 NUM solution이 개발되었다. 직접적인 source rate control은 TCP window-control manner로의 작동이 어렵고, rate controller는 network router가 queue length message를 전달하도록 요구하므로 TCP의 scalability가 손상된다.
→ 위 구현 및 scalabiltiy issues로 인해 TCP application에 대해 NUM scheme를 적용하는 것은 불가능하다.
Kleinrock congestion model called TCP BBRv2
: BBRv2 algorithm은 End-to-end bandwidth를 추정하기 위해 packet loss에 의존하지 않기 때문에 packet loss rate에 민감하지 않다. 그러나 TCP BBRv2가 많은 bandwitdh를 점유하는 경우에는 잘 작동하지 않고 공정성이 상대적으로 낮다는 문제가 있다.
- 최근에는 인공지능과 머신 러닝 접근 방식이 TCP congestion method 개발을 위해 채택되었으나 체계적인 설계 방법론과 이론적인 성능 보장이 다소 부족하다. 추가로 Lagrange multiplier뿐만 아니라, congestion measure로 사용되는 queueing delay로 Mo-Walrand scheme과 FAST-TCP algorithm이 체계적인 방식으로 개발되었다.
- NUM solutions와 enhanced TCP schemes가 모두 관련 NUM problem에 대한 (explicit or implicit) primal-dual solver로 간주될 수 있음을 관찰할 수 있다. optimization theory에서 Lagrange multiplier는 constrained problem을 해결하는데 도움이 되는 auxiliary dual variables로 도입된다. NUM solution에서 queueing delay는 Largrange dual variable 역할을 한다. queueing delay는 또한 flow source에 대한 congestion measure 역할을 한다.
→ network router의 참여 없이 packet의 왕복 지연(즉, total queueing delay)는 source node에서 직접 계산 가능하다. 따라서 queueing delay가 congestion measure로 더 나은 선택이 될 수 있다.
- primal source rate와 dual queueing delay가 window size의 function이 되면서, end-to-end window adjustment이 implicit primal-dual update로 동등하게 바뀐다. optimal TCP congestion은 optimization problem에 대한 window-control oriented implicit primal-dual solver에 해당한다.
- 이 아이디어를 활용하여 mobile TCP application을 위한 optimal congestion solution의 존재를 증명한다. 이를 위해 TCP congestion control(at transport layer)와 wireless-link scheduling(at link layer)의 공동 설계 필요성을 나타낸다. 특히 wireless accesss point에서는 queueing delay 기반의 'MaxWeight' 방식의 scheduling이 작동되어야 한다.
- 이러한 scheduler를 사용하며 wireless link capacity가 결합될 경우 좋은 방식으로 결합될 수 있으므로 optimal congestion control이 가능하다. 게다가 우리는 QUIC(QueueIng-Control) TCP congestion contrl algorithm class를 개발하기 위해 Mo-Walrand method를 일반화한다. queueing delay 기반 MaxWeight-scheduler와 함께 제안된 QUIC-TCP algorithm이 의도한 network optimization problem에 대한 window-control oriented implicit primal-dual solver에 해당함을 보여준다. Lyapunov method을 활용하여 proposed scheme의 전역 수렴을 network fluid model에서 optimal equilibrium으로 엄격하게 설정합니다.
Preliminaries
: Wired backbone과 mobie deivce 용 wireless access point (AP)를 고려한다.
: set of data links
: wired link set
: wireless link set
: constant capacity of wired link l ∈ L_f; link capacity = bottleneck
: capacity of wireless link l ∈ L_w
- Wireless standards에서는 안정적인 데이터 전송을 보장하기 위해 일반적으로 link layer에서 error correction coding, rate and power adaptation, and hybrid ARQ를 사용한다. 결과적으로 wireless link capacity r_l은 wireless 매체의 random fading과 broadcast 특성으로 인해 결합되고 동적이게 된다.
: 각 wireless link의 fading realization h에 대한 achievable rate region
: expectation over fading distribution
: average of r_l
- network traffic은 source s ∈ S에서 오는 set of unicast flow로 구성된다. 대상을 향해 각 flow s는 여러 wired or wireless link를 통해 이동할 수 있다.
: set of links which flow s goes through
: set of flows carried by link l
: transmission rate of source s
: weight vector p, used in weighted proportionally-fair utility function
: utility maximization in (1)은 solution이 large propagation delay로 flow에 불이익을 주지 않는 공정하고 효율적인 평형으로 이어질 수 있기 때문에 중요하다. problem (1)은 NUM paradigm으로 쉽게 해결 가능하다.
NUM schemes
: (1)의 경우, primal optimization varivale에는 source rate vector x와 wireless-link capacitiy vector r이 포함된다. problem (1)이 convex하므로, globally optimal {x*, r*}, λ*는 다음의 Karush-Kunn-Tucker(KKT) 조건을 따라야만 한다.
: source rate vector
: Lagrange multipliers for the link capacity constraints
: 기존의 NUM scheme에서 queue length of links는 scaled Lagrange multiplier Q_l ≡ V λ_l의 역할을 수행하는데 사용된다. source controller, wireless link controller, queue evolution은 문제를 해결하기 위한 sub-gradient type primal-dual iteration의 분해로 연결된다. 특히, rate control x_s(t)와 scheduling policy r(t), queue evolution Q_l(t+1)는 step size 1/V로 (1)을 풀기 위해 λ_l에 대한 stochastic sub-gradient descent iteration을 수반한다. stochastic optimization tools로부터 optimal {x* , r* , λ* }에 대한 점근적 수렴을 얻을 수 있다.
Window-based TCP enhancement
: TCP congestion control에서 flow source는 own local congestion을 기반으로 transmisstion window size를 조정한다. ACK packet을 수신하면 source는 window size가 변경되지 않은 경우 새 packet을 전송한다. 또는 window size가 변경될 때, 대량traffic을 전송하여 이동 중인 packet 수가 current window size와 동일하도록 유지한다. 이 window-based operation은 implementability의 핵심이며, feedback delay가 있는 경우 비동기 방식으로 TCP reliability를 제공한다.
- 표준 TCP에서는 packet loss에 기반한 AIMD(additive-increase-multiplicative-reduction) window 조정 방식을 채택한다. 이 방식에서는 packet loss의 유일한 원인이 network congestion이라고 고려한다. 이는 wireless를 통한 TCP 성능 저하로 이어진다. 이에 대한 해결책으로 window size를 적절하게 늘리거나 줄이기 위해 heuristic window 조정 방식이 제안되었으나 optimization problem 해결이 보장되지 않았다.
- congestion으로 packet loss에 의존하는 TCP는 wireless에서 효과적이지 않다는 사실이 입증되었다. 이는 congestion control measure로 queueing delay을 사용하는 방식에 동기를 부여한다. 원하는 optimization을 달성하기 위해, queueing delay를 Lagrange multiplier로 사용하여 Mo-walrand scheme와 FAST-TCP algorithm이 제안되었다. 이러한 algorithm은 wireless network에 대한 network fluid model(즉, L_w = ∅ in (1))에서 분석되었다.
The GAP
: 기존의 NUM optimization solution과 enhanced TCP schemes는 모두 NUM problem에 대한 primal-dual solvers로 간주될 수 있다. 그러나 queue length는 전자에서 (scaled) Lagrange multipliers로 작동하는 반면, 후자에서 그러한 역할을 하게 된다. queue length와 queueing delay의 dynamic 관계는 link capacity에 맞게 조정된다. 그러나 이들은 결코 equivalent 조치가 아니다. 또한 NUM의 기본 update는 source rate controller에 의해 직접 수행되는 반면, TCP design의 window controller는 암시적으로 영향을 받는다.
- 그러나 NUM scheme에서 제안하는 source rate contrllersms TCP congestion control의 design space에 국한되지 않는다. 이러한 controller는 network router에서 총 queue length이 명시적 message 전달이 필요하므로 protocol scalability를 손상시킨다. 또한 TCP window size w_s에서 source rate x_s로의 매핑이 복잡할 수 있으므로, 제안된 rate control scheme는 TCP에서의 수행이 어렵다. 결과적으로 이러한 문제는 TCP application에 대한 관련 NUM scheme 작동이 불가능하다.
- Queue length와 달리 aggregate queueing delay는 network로부터 명시적 피드백 없이 flow source에서 local로 추정이 가능하므로 TCP scalability를 보존할 수 있다. 이러한 congestion measure를 기반으로 wired network용으로 Mo-Walrand scheme의 window-based congestion controller와 FAST-TCP가 개발되었다.
- Otimization theory에서 Lagrange multiplier는 constrained problem 해결에 도움이 되는 보조 dual variable로 도입된다. queueing delay는 queue length보다 Lagrange multiplier에 대한 더 나은 매핑 선택이 될 수 있다. 이 매핑에 의존하여 TCP congestion control에서 end-to-end 조정을 수행하는 non- standard and implicit primal-dual solvers를 개발할 수 있다. 이를 위해 다음으로 Mo-Walrand scheme를 일반화하여 mobile application을 위한 TCP window control oriented network optimization scheme를 개발한다.
Algorithm development
: Flow source에서 congestion measure로 queuing delay를 선택하여 다음과 같은 TCP congestion control 및 wireless scheduling scheme를 개발한다.
Congestion control
: FAST-TCP와 같이 동작한다. in-order ACK packet을 수신하면 flow source s의 estimation omponent는 current RTT를 계산하고 AvgRTT 및 BaseRTT local value를 update한다. 여기서 BaseRTT는 propagetion delay를 근사화하기 위해 지금까지 관찰된 최소 RTT로 제공되며 AvgRTT는 current RTT에 따라 다음과 같이 update된다.
- AvgRTT 및 BaseRTT를 기반으로 window control component는 다음과 같이 transmission window size를 조정한다. 이 때, k는 positive stepsize, ρ ∈ [0, 1]는 a constant parameter이다.
- 그런 다음, burstiness control component는 전송 시기를 결정하고, data control component는 전송할 packet을 결정한다. ACK packet이 손실되거나 순서대로 수신되지 않으면, 현재 TCP의 slow start 또는 fast recovery algorithm을 사용하여 time-out or duplicate ACK를 처리한다.
Wireless-Link Scheduling
: AP는 wireless link를 통한 slot transmission을 조정한다. slot n에서 queue length QueLen_l[n]을 읽고, wireless link l당 (8)과 유사한 low-pass filter를 사용하여 average rate AveR_l[n]을 계산한다. 그 다음 scheduler는 다음 policy를 수행한다.
- 특히, time-division downlinke or uplink의 경우, R_l[n]는 ∀ l ∈ L_w에서 link l이 slot n에서 달성할 수 있는 최대 속도이다. 그런 다음 strategy (10)은 slot 당 전송에 대해 가장 높은 (QueLen_l[n] / AveR_l[n]) * R_l[n]을 갖는 링크를 선택한다. 이 scheduler는 실제로 modified largest-weighted- delay-first (M-LWDF) strategy를 수행한다.
A. Fluid model network
: Data packet이 무한정 분할될 수 있는 w := {w_s,∀ s} and d := {d_s,∀ s}를 만족하는network model을 가정한다. source rates x_s에 대한 다음 관계들이 만족된다.
: window size
: fixed round-trip propagation delay for flow s ∈ S
: q collect the round-trip queueing delays ql for links, ∀ l ∈ L
: aggregate queueing delay along the routes for flow s
- (11)은 flow rate x_s가 window size w_s를 RTT d_s + q^s of flow s로 나눈 값과 같기 때문이다.
- (13) and (15)는 link capacity constraints 때문이다.
- (12) and (14)는 data pacekt은 무한정 분할 가능하기 때문에(즉, 무한히 작음) link l을 통한 total rate가 capacity c_l or r_l보다 작을 때, 이 link의 queue size and queueing delay는 0이다.
AP가 wireless link당 average rate AveR_l[n]을 정확하게 유지할 수 있다고 가정한다. 리틀에 법칙에 따르면 average queueing delay는 average queue length를 average rate로 나눈 값과 같다. scheduling policy (10)에서 current queue length QueLen_l[n]과 average rate AveR_l[n]의 비율에 의해 주어진 'instantaneous' delay이 user rate r_l에 대한 가중치로 사용된다.
적절한 time-scheduling을 사용하여 fluid limit argument를 적용하여 'stochastic' delay QueLEN_l[n]/AveRl [n]이 fluid model에서 average delcy q_l을 대신할 수 있다.
그러면 scheduling policy (10)은 average queueing delay based policy에 해당하게 된다. 즉, h당 모든 link가 있는 delay-capacity product의 합을 최대화한다.
- scheduler에 따르면 다음을 가지게 된다.
- BaseRTT_s, AvgRTT_s는 propagation delay d_s와 total RTT d_s := d_s + q^s를 정확하게 근사할수 있다고 가정한다. 그러면 window update (9)는 다음과 같다.
- x_s = w_s/d_s from (11)이고, v_s := w_s −x_s*d_s −p_s, v := {v_s, ∀ s}로 정의한다. window 조정은 실제로 fluid model flow s당 ordinary differential equation에 해당한다.
- 우리의 congestion control은 (18)을 사용하여 window size w_s를 조정하는 것과 같으며, 이는 차례로 (11)-(17)을 통해 source rate vector x, wireless-link capacity vector r, queueing delay vector q를 제어한다. window update (18)은 실제로 flow의 queueing을 제어한다. 따라서 0 ≤ ρ ≤ 1을 사용하여 QUIC-TCP으로 명명하고, ρ = 1일 때 algorithm은 Mo-Walrand의 방식이 된다.
- ρ = 1/2, d/dt(w_s(t))는 FAST-TCP와 유사하게 아래와 같다.
- 제안된 scheduler (17)은 실제로 MaxWeight type scheduler이다. 그러다 queue length 대신 queueing delay가 link를 통한 transmission rate에 대한 가중치로 사용된다. 이러한 queueing delay based scheduling은 queueing delay가 제안된 방식에서 Lagrange multiplier 역할을 사실 때문에 KKT condition에 쉽게 암시된다.
댓글