[Review] Pcc vivace: Online-learning congestion control.

* [NSDI' 2018] "Pcc vivace: Online-learning congestion control" 논문을 한국어로 정리한 포스트입니다.

Pcc vivace: Online-learning congestion control. (2018)

Mo Dong and Tong Meng, UIUC; Doron Zarchy, The Hebrew University of Jerusalem; Engin Arslan, UIUC; Yossi Gilad, MIT; Brighten Godfrey, UIUC; Michael Schapira, The Hebrew University of Jerusalem

[ 논문 ], [ 발표 영상 ]

Abstract

• TCP 구조의 좋지 않은 성능을 개선하기 위해 machine learning의 online (convex) optimization 을 기존의 PCC framework에 도입하였다.
• 기존의 방식들에 비해 performance ( throughput, lantecy, loss ), 수렴 속도, bufferbloat 완화, 변동하는 네트워크 상황에 대한 반응성, 다양한 상황에서 기존 TCP에 대한 friendliness 측면에서 더 나은 성능을 보이며, sender만 변화시킴으로써 구현이 쉽다.

1 Introduction

• 전송률 제어는 다음과 같은 많은 도전에 직면해 있다.
  • 혼잡 제어는 다양한 네트워크 환경 ( random loss, high-RTT 대륙간 링크, 무선에서의 동적 네트워크 환경 )에서 네트워크 자원을 효율적으로 활용해야 한다. ( throughput, loss, latency 최적화 )
  • 다수의 sender 간의 안정되고 공정한 상태로 빠른 수렴을 보장해야 한다.
  • 혼잡 제어 방식은 쉽고 안전하게 적용가능해야한다. 즉 존재하는 프로토콜과 친화적으로 동작해야한다.
• 전통적 알고리즘 ( TCP Vegas, Illinois, Cubic ) 은 앞의 두 조건을 충족하지 못했으며, 최근의 제안들 ( Remy, BBR, PCC )은 새로운 접근법을 연구하였다.
  
  • Remy 는 설계를 특정 설계 공간에서 최적의 방식을 찾는 offline 최적화 방식으로 대체하였지만, 입력된 가정과 다른 환경에서 성능이 떨어진다.
  • BBR은 white-box 네트워크 모델링 방식을 사용해, 성능 측정의 패턴을 미리 상정한 네트워크 환경으로 바꾼다.
  • PCC Alegro (2015) 는 black-box 접근법을 채택해, 특정 전송률로 보낸 결과의 성능을 측정하고 이를 utility value로 전환하여 전송률을 높은 utility를 보이는 방향으로 움직인다.
• PCC Allegro와 BBR 은 낮은 latency를 달성하는데 실패하엿고, 수렴속도와 안정성의 이상적인 tradeoff로부터 먼 결과를 보여준다. BBR 은 수렴과정에서 높은 rate variance와 높은 패킷 손실을 보여주며, PCC 는 수렴 시간이 너무 길다. BBR의 네트워크에 대한 모델이 현실의 복잡함을 반영하지 못할 때, 성능이 심각하게 낮아지며, 두 방식 모두 TCP 방식에게 공격적인 모습을 보인다.
• 위와 같은 한계를 극복하기 위해, online 최적화 이론으로부터 PCC Vivace 를 만들었다. VIvace는 high-level 구조에서는 PCC를 사용했지만 다음과 같은 차이가 있다.
  • Vivace 는 learning-theory를 기반으로 하였으며, atency 최소화와 TCP 친화성을 고려하여 파생된 utility를 이용한다.
  • Vivace는 gradient ascent 기반의 optimal online optimization을 통해 네트워크 용량의 높은 활용성과 변화에 대한 신속한 대응, 빠르고 안정된 수렴을 달성한다.
• throughput 과 loss ( Allegro 처럼 ) 는 물론, latency, 안정된 global 전송률 설정을 포함하는 utility function의 적절한 선택이 언제나 존재한다는 사실을 증명하였다.
• gradient ascet 알고리즘을 활용한 전송률 제어 방식을 통해 안정성과 반응성 사이의 tradeoff를 향상 시켰다. 
• 실험을 통해 변화하는 환경에서의 높은 성능과, 빠른 수렴, 높은 안정성, 더 낮은 video 버퍼링, 향상된 TCP 친화성을 보여주었다.

2 Rate-Control Through Online Learning

• Online learning은 불확정성 속에서 의사결정을 위한 이론을 제공하며, decision maker는 가능한 strategies 중 하나를 선택하고, 선택된 startegy의 결과를 utility value를 통해 확인한다. 이를 통해 환경에 대한 불확실함 ( strategy의 선택과 야기된 utility value의 관계에 대한 어떠한 가정이나 추측없이 ) 에도 증명 가능한 "no regret"을 보장한다. 또한 게임 이론은 이러한 알고리즘이 함께도 잘 동작함을 보여주며, 다수의 sender들이 적절한 환경에서 안정된 균형으로 global하게 수렴함이 보장된다.
• traffic sender는 반복적으로 전송률을 선택하고 충분히 긴 시간 후에 결과를 utility value로 변환한 뒤 전송률을 조정한다. 종종 네트워크로부터 매우 제한된 feedback만이 sender에게 전달되, 정확하기 utility를 결정하는 것이 불가능할 때, online learning의 적용이 어려울 수 있다.
• PCC Allegro는 online-learning 기반의 혼잡 제어의 좋은 출발점이지만, 다음과 같은 점에서 잠재력을 충분히 발휘하지 못하였다.
  • Allegro는 다소 자의적인 untility function을 채택하였다. letency 기반의 함수를 사용시 공정한 수렴이 보장됨을 증명하지 못하고, parameter 설정에 따른 근본적인 tradeoff에 대한 추론이 어려우며, 서로 다른 utility 함수를 가진 Allegro sender가 어떻게 상호작용하는지에 대한 이론적인 이해가 없다.
  • 아래와 같은 utility function 에서 $r_1$, $r_2$와 같은 initial rate에서 Allegro는 임의의 $\epsilon$을 기준으로 전송률을 조정하는데, 고정된 step size는 어떤 상황에서는 너무 크고, 어떤 상황에서는 너무 작은 경우가 발생해, suboptimal한 반응성과 수렴성을 야기한다.

• utility function의 즉석 선택과 단순한 전송률 조절 방식으로 인해 PCC Allegro는 빠르게 변하는 네트워크 환경에서 좋은 성능을 보이지 못하고, bufferbloat을 완화하지 못하며, 수렴성/안정성 tradeoff에서 TCP보다는 낫지만 suboptimal하며, 수렴과정에서 높은 패킷손실, TCP에 대한 공격성을 보인다.
• VIvace는 online convex optimzation의 지식을 통해 Allegro의 두 가지 요소를 대체하였다. 1) utility function framework의 틀, 2) learning rate-제어 알고리즘.
  • Vivace는 다수의 경쟁하는 Vivace sender가 유일한 안정 상태 ( 공정하고, 최적에 가까운 )에 수렴함을 보장하도록 하는 learning-theory 기반 framework를 사용한다.
  • gradient-ascent 기반의 no-regret online 최적화를 통해 변하는 방향뿐만 아니라 변하는 정도를 고려하여 sending rates를 조절한다. 
• no-regret learning, Vivace는 전송률의 선택이 점근적으로 utility 측면에서 더 나빠지지 않음을 보장한다. 1) no-regret은 각 sender에게 모든 환경에서 성능을 보장하며, 2) 다수의 경쟁하는 ( 서로 다른 utility 함수를 사용할 때도 ) no-regret sender가 수렴함과, 수렴하는 과정에서의 손실과 혼잡이 원인이 아닌 손실사이의 tradeoff에 대해 추론하는 이론적 분석을 위한 근거를 제공한다.
• no-regret의 한계, no-regret이 성능을 best-fixed strategy와 연관지으면서, 변화하는 환경에서의 성능 보장의 quality는 프로토콜이 regret을 최소화 하는 속도에 의존한다. 만약 자의적인 시작 상태에서, T 시간안에 regret이 사라진다면, best-fixed strategy에 대한 no-reget의 보장은 매 T 시간동안 적용된다. 물론 best dynamic starategy 를 통한 성능의 보장이 훨씬 좋지만, 그러한 보장은 네트워크에 대한 가정을 수반하게 되고, vivace는 그러한 가정을 피하고자 한다. 즉 미래의 연구에서는 현실 세계 네트워크가 충분히 예측가능함을 정량화 하는 것이 중요한 연구방향이라 할 수 있을 것이다.
• Allegro vs. Vivace, 1) Vivace는 latency에 대해 자각함으로써, bufferbloat 문제와 이로 인한 패킷 손실과 latency 증가를 완화 시켰다. 2) 다른 종류의 utility function을 사용하는 sender로 하여금 융통성 있는 네트워크 자원할당을 가능하게 하였다. 3) TCP에 더 친화적으로 행동함으로써 현실세계 적용에 더 맞도록 하였다. 추가적으로 VIvace는 더 빠르고 안정적인 수렴과, 변화하는 환경에 대한 더 빠른 반응을 제공한다.

3 Vivace's Utility Framework

$u(x_i, \frac{d(RTT_i)}{dT}, L_i) = {x^t}_{i}-b{x_i}{\frac{d(RTT_i)}{dT}}-c{x_i} \times {L_i}$

• $ 0 < t < 1mb \geq 0, c > 0, $ $x_i$는 sender $i$의 전송률, $L_i$는 손실률, $\frac{d(RTT_i)}{dT}$는 RTT의 MI 동안의 gradient, 즉 MI 동안의 latency 증가량, parameter $b,c,t$는 상수이다.
• latency의 값이 아닌 RTT의 gradient를 사용하는 이유, 큰 buffer를 가진 link에서 single sender가 link 용량의 두배의 전송률로 전송하는 경우를 생각해보자, 다음 MI에서, sender는 여전히 용량보다 크지만 조금 낮은 전송률을 시도한다. 여기서 Sender는 두번째 MI에서 더 높은 latency의 값을 경험한다, rate를 낮추는게 옳은 선택임에도 불구하고. 하나의 MI 동안 전송률을 낮추는 것이 더 낫다는 사실을 학습하기 위해 sender는 latency가 증가하거나 감소하는 rate를 조사한다. -> 첫번째 MI에서 RTT가 더 크게 증가하고 두번째 MI에서 증가량이 더 적음에도 절대적인 값은 두번째 RTT가 더 크기 때문에 이를 방지하기 위해 절대값 대신 증가량을 사용한다는 뜻
• parameter b, c 그리고 t의 값은 다수의 sender가 경쟁할 때 균형값의 존재 여부와 균형상태에서 latency와 congestion loss에 중대한 영향을 미친다.

utility function에서의 parameter의 영향

3.1 Stability and Fairness

3.2 Random Loss vs. Congestion

3.3 Heterogeneous Senders

4 Vivace's Rate Control

Gradient ascent

4.1 Key Idea and Challenges

4.2 Translating Utility Gradients to Rates

4.3 Contending with Unrealiable Statics

4.4 TCP Friendliness

5 Implementation and Evaluation

5.1 Consistent High Performace

5.1.1 resilience to Random Loss

5.1.2 HighPerformance on Satellite Links

5.1.3 High Throughput without Bufferbloat

5.1.4 Swift Reaction to Changes

5.2 Convergence Properties

5.2.1 Convergence Speed and Stability

5.2.2 Lower Price for Loss Resilience

5.3 Improved Friendliness to TCP

5.4 Flexible Convergence Equilibrium

5.5 Benefits in the Real World

5.5.1 Video Streaming

5.5.2 The Wild Internet

6 Related Work

7 Conclusion