[Review] PCC: Re-architecting Congestion Control for Consistent High Performance.

* [NSDI' 2015] "PCC: Re-architecting Congestion Control for Consistent High Performance" 논문을 한국어로 정리한 포스트입니다.

PCC: Re-architecting Congestion Control for Consistent High Performance (2015)

Mo Dong and Qingxi Li, University of Illinois at Urbana-Champaign; Doron Zarchy, Hebrew University of Jerusalem; P. Brighten Godfrey, University of Illinois at Urbana-Champaign; Michael Schapira, Hebrew University of Jerusalem

paper ( link )  / presentation ( link )  / Github ( link )

modong/pcc

Abstract 

• TCP와 다양한 변종들 ( CUBIC, Reno 등 ) 은 high performance를 달성하는데 근본적인 구조적 결함을 가지고 있다. 응답을 제어하기 위한 내장된 packet수준의 이벤트들 ( hardwiring packet-level events to control responses ) 이 바로 그것이다.
• 성능 지향 혼잡 제어 ( Performance-orented Congestion Control, PCC ) 는 sender가 지속적으로 action과 경험적으로 얻어진 성능을 관측하여, 높은 성능을 내는 action을 채택하는 방식을 사용한다. PCC는 안정되고 공정한 균형으로 수렴하며, TCP와 비교하여 지속적이고 때로는 종종 10배가 넘는 성능을, 더 나은 fairness와 안정성을 가진 채로 보여준다.
• PCC는 또한 router의 하드웨어 supprot가 필요하지 않으며, 새로운 packet format 또한 필요하지 않다. ( 구현이 쉽다 )

TCP와 PCC의 의사 결정 ( rate control ) 구조 비교

1. Introduction

•  TCP는 lossy links 에서 나쁜 성능을 보이고, high-RTT flow를 penalize 하며, high bandwidth-delay prodcut ( BDP ) 연결을 효율적으로 사용하지 못하며, 빠르게 변하는 network를 잘 다루지 못한다. 또한 bufferbloat 상황에서 매우 높은 latency를 유발한다.
•  심각한 성능 문제로 인해, 특정한 network 환경 ( high BDP links, 위성 links, 데이터 센터, wireless and lossy links 등 )에 맞춘 protocol 등이 등장했지만, 이러한 많은 변종들은 단지 특정 네트워크에서만 잘 작동할 뿐이다. 심지어 이러한 TCP 변종들은 그들이 적용되기 위해 만들어진 환경 내에서도 최적의 성능에 한창 떨어지는 모습을 보여준다. 따라서 핵심 문제는 해결되지 않은 채로 남아있다.
• 복잡한 현실 세계 network 환경에서 지속적으로 높은 성능을 달성하는 것. 이는 TCP의 전송률 조절 구조로는 힘든 것으로 보이는데, 이는 특정한 미리 정의된 packet 수준 event와 특정한 미리 정의된 응답 제어 반응 ( control responses ) 간의 내장된 mapping 때문이다.
• TCP는 한 번의 packet loss ( New Reno) 나 하나의 packet loss 및 RTT 증가 ( TCP Illinois ) 와 같은 단순한 이벤트에 대해서 반응하며, 반응 또한 단순히 전송률을 절반으로 줄이기 ( New Reno ) 나 windowsize $w$ 를 $f(\Delta RTT)w$로 줄이기 뿐이다. action을 제어하는 것은 단순히 packet 수준 event들에 대한 함수인 것이다.
• 이러한 내장된 mapping은 network에 대한 가정을 전제로 한다. TCP 는 패킷 손실이 congestion의 신호라고 가정한다. 이러한 가정이 틀렸을 때, TCP의 반응 ( window size 반으로 줄이기 ) 은 성능을 심각하게 해친다. ( 손실이 단순히 random일 때, 전송률은 유지되거나 더 높아져야 한다. ) 따라서 근본적으로 "항상 최적화된" mapping을 만들어 내는 것은 복잡한 현실 세계 network에서 거의 불가능하다. 
• 또한 현대의 network는 환경의 다양성이 더욱 커졌다. : 랜덤 손실과 zero 손실, 좁은 queue와 넓은 queue (bufferbloat), 경쟁하는 flow 간의 RTT 차이, mobile 환경에서의 역동성, Kbps ~ Gbps 사이의 다양한 링크, AQM ( Active Queue Management ), software 라우터, gateway 에서의 전송률 조절, virtualization 계층 및, firewall와 같은 middlebox, packet inspector 및 load balancers 등등. 이러한 요소들은 내장된 mapping에 포함된 단순한 가정으로 요약되기에는 너무 많은 복잡성을 가지고 있다. 이러한 많은 가정이 엇나갔을 때에도, TCP는 완고하게 rate 조절을 수행할 뿐이다.
• PCC의 목적은 실험적인 증거 ( live experimental evidence )를 바탕으로 어떤 전송률 조절 action이 성능을 향상시키는지 이해하고, TCP의 network에 대한 가정을 피하는 것이다. PCC는 짧은 시간 동안 전송률 $r$로 패킷을 보내고 결과 ( 전송, 손실, 각 패킷의 지연율을 나타내는 selective ACKs ) 를 관측한다. 그리고 이런 packet 수준 events들을 높은 throughput과 낮은 loss rate와 같은 목적들을 포함하는 unitility function에 모아 single numerical performance utility $u$로 나타낸다. 이 부분에서 PCC는 rate $r$ 이 utility $u$를 생성하는 실험을 진행한다고 할 수 있다.
• 전송률 조절에 대한 결정을 위해 PCC는 여러번의 실험을 진행한다. PCC는 두 개의 다른 전송률을 시도하여 실험적으로 더 나은 성능을 보이는  전송률을 선택한다. 경험적으로 최적의 전송률을 추적하는 online-learning algorithm을 기반으로한 이러한 실험을 특정한 상황에서가 아닌 연속적으로 시행한다. 즉 복잡한 network에 대한 가정을 하는 대신에 경험적으로 높은 성능을 내는 action을 선택하는 것이다.
• PCC의 전송률 조절은 자기중심적이지만 ( selfish ), 폭넓게 적용 가능한 utility 함수를 통해, 경쟁하는 PCC senders 들은 single bottleneck link에서 공정한 균형을 유지하도록 수렴한다. 또한 실험 결과는 PCC가 TCP와 비슷한 수렴시간 ( Convergence time ) 을 가지며 variance는 훨씬 더 적음을 보여준다. 게다가 다양한 목적을 나타내도록 utility 함수를 선택함으로써 TCP 구조보다 더 나은 flexibility를 제공한다.
• large-scale 및 현실 network에서 진행된 실험에서, control 알고리즘을 수정하지 않고도, PCC는 특별하게 설계된 TCP들 보다 오히려 더 나은 성능을 보여준다. 또한 PCC는 단순히 sender 측에서 TCP의 전송률 조절 방식을 바꾸는 것만으로도 쉽게 구현이 가능하다.

2. PCC Arcitecture

2.1 The Key Idea  

• flow $f$ 가 data를 보내는 과정에서 패킷이 손실되었을 때, $f$ 는 어떻게 반응해야 하는가? 하나의 손실은 많은 가능한 network 시나리오의 결과일 수 있다.
  1. Congestion으로 인한 경우 : 전송률을 낮춰야 한다.
  2. High-BDP 링크의 좁은 버퍼 ( Shallow buffer ) 를 통과할 때, 손실이 link utilization을 위해서가 아닌 statistical multiplexing의 불운으로 인해 발생하는 경우 : 전송률을 조금 낮추는 것만으로도 충분하다
  3. 더 높은 전송률을 가진 flow와 경쟁하는 경우 : 전송률을 유지하고 다른 flow가 낮아지도록 해야한다.
  4. random 한 경로상 어딘가에서의 non-congestion 원인의 loss로 인한 경우 : $f는 유지되거나 더 높아져야 한다.

• 전통적으로 TCP는 패킷 손실이 무시할 수 없는 혼잡을 나타내며, 전송률을 절반으로 낮추는 것이 network 상황을 개선할 것이라 가정해 왔지만, 이러한 가정은 틀렸으며, 위 네 가지 상황에서 3가지의 경우 이러한 가정은 성능을 낮추는 요인이 된다. 근본적으로 최적의 미리 정의되고 내장된 (hardwired) 전송률 조절 반응을 고르는 것은 어렵다. 왜냐면 같은 손실이라도 조금이라도 다른 상황에서는 같은 반응이 성능을 낮추는 결과를 야기하기 때문이다. 많은 TCP 변종에서는 더 정교한 event에 대한 분석과 이에 대한 대응 ( 전송률 조절 ) 을 사용하였지만, 근본적으로 events와 그에 대한 반응을 설정하는 것은 필연적으로 네트워크에 대한 신뢰할 수 없는 가정을 전제로 하기 때문에 근본적인 해결책이 되지 못하였다. 이러한 신뢰할 수 없는 가정이 깨지는 순간 네트워크의 성능을 심각하게 해하게 된다.
• 네트워크에 대한 가정에 더해 전송률 조절 action 또한 성능을 낮춘다. TCP는 아직도 "jump off the cliff" ( 눈 딱 감고 절벽에서 뛰어내리기 ) 방식을 사용한다. action이 성능에 미칠 영향에 대해 알지 모사기 때문이다. PCC는 action이 performance에 미치는 영향을 직접적으로 이해하는 제어 동작 알고리즘을 설계하였다.
• 개념적으로, 네트워크가 얼마나 복잡하던지, sender가 전송률 $r_1$ 이 $r_2$보다 더 나은 성능을 보인다는 걸 측정한다면, $r_1$이 $r_2$보다 낫다는 사실을 알 수 있다. ( 적어도 이 한 sender의 입장에서 ) 이 예시가 Performance-oriented Congestion Control의 핵심 아이디어이다. : PCC는 action과 그로 인해 직접적으로 관측된 성능을 결합하여 얻어진 경험적 증거를 토대로 제어 작용을 결정한다. ( PCC makes control decisions based on empirical evidence pairing actions with directly observed performance results )
• PCC의 제어 동작은 전송률의 선택이다. PCC 연속된 시간을 monitor intervals ( MIs, 감시 간격 ) 으로 나누며, 각 MI의 길이는 보통 1~2 RTTs이다. 각 MI 마다 PCC는 action을 test 한다. 전송률 $r$로 data를 전송 후, 약 한 RTT 이후, sender는 SACK를 받게 된다. TCP와 다른 점은 이 SACK가 어떠한 미리 지정된 제어 반응도 일으키기 않고 대신에 이러한 SACK을 의미 있는 성능 분석 ( throughput, loss rate, latency ) 이 되도록 종합하여 이러한 분석을 utility function을 통해 unitility value $u$ 로 치환한다. 결과적으로 PCC는 전송률 $r$ 에 utility $u$ 를 얻는다는 사실을 알게 된다.
• 위는 한 번의 소규모 실험을 나타내며, PCC는 이러한 소규모 실험을 연속적으로 시행해 다른 전송률에 따른 utility 값을 비교할 수 있게 되고, 최적의 action을 추적할 수 있게 된다. 구체적으로 PCC는 gradient ascent와 비슷한 online-learning algorithm을 수행하는데, 전송률 $r$에서 시작해서 $(1+\epsilon)r$ 과 $(1-\epsilon)r$을 시험하여 더 높은 utility를 나타내는 방향으로 이동한다. 그리고 utility가 증가하는 동안 계속 같은 방향으로 이동하고, utility가 더 이상 높아지지 않을 때는 decision-making state로 돌아와 다시 높거나 낮은 전송률을 시험한다.
• PCC는 비정기적인 관측을 보내지도, 측정을 위해 불필요한 데이터를 보내지도 않으며, 실제 데이터를 통해 실제 제어 결정의 결과를 관측하며 결과를 기다리기 위해 전송을 멈추지도 않는다는 점이 중요하다.
• 다시 초반의 예시로 돌아와 전송률 100 Mbps에서 105 Mbps를 시험했을 때, 패킷 손실이 발생한 상황을 가정해보자. PCC는 어떠한 MI 내에서 특정 사건에 대해 반응하여 전송률을 바꾸지 않으며, 단지 utility value를 측정하여 더 높은 값을 가지는 방향으로 전송률을 바꾼다
  1. 만약 네트워크가 flow의 결과로 혼잡한 경우, 100 Mbps로 전송 시 비슷한 throughput과 더 낮은 loss rate를 가질 것이고, 더 높은 utility를 보일 것이다. 따라서 PCC 는 전송률을 낮출 것이다.
  2. 네트워크가 random loss를 경험한 경우, 105 Mbps 전송률이 비슷한 loss rate에 조금더 높은 throughput을 가질 것이고, 더 높은 utility를 보일 것이다. 따라서 PCC 는 packet loss 에도 불구하고 전송률을 높일 것이다. 

= PCC 는 네트워크 상황에 대한 어떠한 가정도 하지 않으며, 대신 어떤 action이 경험적으로 더 높은 utility를 만드는 지를 관측한다. 그러므로 지속적으로 더 높은 성능을 얻는 것이다.

Decisions with Noisy measurements.

• 위와 같은 실제 상황에서의 PCC의 실험은 전송률을 utility 를 증가시키는 방향으로 바꾸지만, 이 과정에서 틀린 결정을 내릴 수도 있다. 위의 예시에서 loss가 random 한 경우, 우연히 105 Mbps에서 loss가 크게 증가하여, 더 낮은 rate를 선택할 수 있다. 반대로 loss가 혼잡으로 인해 발생한 상황에서, 예측하지 못한 외부의 사건 ( 100 Mbps 실험 중 높은 initial rate를 가진 sender의 도착 ) 은 105 Mbps 실험에서 더 나은 throughput과 더 낮은 loss rate를 야기할 수 있다. 
• 일반적으로 network는 sender의 액션과 무관한 원인으로 인해 변할 수 있다. 이는 decision 과정에서 noise를 추가한다. 
• 이를 보완하기 위해 multiple randomized controlled trials ( 다수의 무작위 조절 시도, RCTs ) 를 도입하는데, 100, 105로 2번의 실험을 하는 대신, random한 순서로 4번의 비교 실험을 시행한다. ( 100, 105, 105, 100) PCC는 두 번의 비교에서 모두 높은 rate를 선택하며, 각 비교에서 서로 다른 rate가 이겼을 경우, 현재의 rate를 유지한다. 이를 통해 local optimum에 도달한다.
• RCT는 variance를 줄여주며, 수렴하는데 걸리는 시간을 두 배 늦출 것 같지만, 실제로는 더 나은 선택을 하도록 돕기 때문에 두 배 정도로 늦춰지지 않고, 안정성 / 수렴 시간 tradeoff를 개선하는 효과를 보인다.

2.2 Fairness and Convergence

• 각 PCC sender는 utility function value를 최적화 하지만, 이러한 local selfishness 가 global 안정성, 수렴, 공정성을 나타내는 것은 아니다. 만약 이기적인 sender 특정 'safe' utility function과 단순한 control algorithm을 사용한다면, 공정한 전송률 균형으로 수렴한다.
• PCC의 기본적인 utility function은 다음과 같다

$u_i ( x_i ) = T_i * {Sigmoid}_{\alpha}(L_i - 0.05)- x_i * L_i$

• $x_i$ 는 sender $i$의 전송률, $L_i$는 관측된 손실률 ( loss rate ), $T_i = x_i(1-L_i)$는 throughput, ${Sigmoid}_{\alpha} = \frac{1}{1+e^{\alpha y}}$, $\alpha > 0$
• $Sigmoid$는 "cut-off" 함수로 $\alpha$가 충분히 클 때,  ${Sigmoid}_{\alpha}(L_i - 0.05)$는 $L_i$가 커짐에 따라 0에 수렴하고 utility function 은 작아진다. 따라서 모든 loss rate는 최악의 경우 5%이다. ( 이 또한 loss rate 가 0.05 이하가 될 수 있다는 가정을 포함하고 있으며, 만약 이 가정이 틀린 환경에서는, PCC의 성능 또한 낮아진다. )
• Theorem 1 : $\alpha \geq max\{2.2(n-1), 100\}$ 일 경우 unique 한 stable state가 존재하며, 각 sender의 전송률은 이 state에서  $x^{*}$로 동일하다.
• Theorem 2: : 모든 sender가 위와 같은 algorithm을 사용한다면, $x_j$ 는 $(x^{*}(1-{\epsilon})^2 , x^{*}(1+{\epsilon})^2)$ 사이의 값으로 수렴하며, $x^{*}$ stable state에서의 전송률이다. 이는 PCC가 multiplicative increase mulitpicative decrease ( MIMD )를 사용한다는 점을 봤을 때 놀라운 일이다. 100 Mps에서 A가 90 Mpbs , B가 10 Mbps로 전송 중인 상황을 가정해보자. A 가 전송률을 높일 경우, loss rate로 인한 utility 값의 하락이 더 크기 때문에 전송률을 낮추게 되고, B가 전송률을 높일 경우 loss rate로 인한 값의 하락보다 throughput의 증가가 더 크기 때문에 전송률을 높이게 된다. 이러한 수렴성은 전송률 변동 방식 ( AIMD, AIAD 등 ) 이 원인이 아닌, utility 함수의 선택에 의존한다. ( 다른 알고리즘과 경쟁 시의 공정성 문제에 대해 논의가 필요 )

2.3 Utility Function: Source of Flexibility 

• PCC는 다른 utility function을 사용함으로써 서로 다른 application으로 하여금 다른 목적 ( latency vs Throughput ) 을 추구할 수 있도록 할 수 있다. TCP 구조에서, latency 기반 protocol 은 loss-based protocol 과는 다른 조절 알고리즘을 포함하기 때문에, applciation 간의 다른 목적을 위해서 active queue management ( AQM ) 에 의존하여야 했다. TCP는 목적을 알 수 없기 때문에. 하지만 utility function을 나타내는 코드 한 줄을 바꿈으로써 PCC는  loss-based에서 latency-based로 변할 수 있다. 즉 다양한 utility 함수는 PCC의 미지의 영역이라고 할 수 있다.

2.4 Deployment

• PCC는 router support 도 새로운 protocol ( 새로운 packet format ) 도, receiver의 change 도 필요하지 않다. 남은 문제는 PCC가 어떻게 안전하게 TCP를 대체하거나, 상호작용하느냐의 문제이다. 다음과 같은 scenario에서 PCC 는 안전하게 구현되고 TCP를 대체할 수 있다.
  1. 네트워크 자원이 single entity에 의해 소유되거나 예약되어 있을 때.
  2. per-user ( Satellite Internet Providers ) , per-tenant ( Data center ) 자원 분리 ( resource isolation ) 가 시행될 때.
• 사실, PCC는 어떤 종류의 자원 분리에도 의존하지 않는다. 실제 인터넷에서 중요한 이슈는 TCP friendliness이다. 위에서 언급한 utility function은 TCP friendly 하지 않으며, 다음과 같은 utility function을 대신 사용한다.

$u_i (x) = (T_i * {Sigmoid}_{\alpha}(L_i - 0.05) * {Sigmoid}_{\beta}({\frac{RTT_{n-1}}{RTT_n}}-1) - x_i * L_i)/RTT_n$

• $RTT_n$은 현재 MI의 평균 RTT이다. 위 utility 함수를 통해 PCC는 TCP friendliness를 달성할 수 있다. PCC는 도전적인 상황에서 TCP friendly 하면서도 높은 성능을 낼 수 있으며 이는 잠재력 있는 연구 방향이다.
• 물론 각 사용자가 PCC의 default utility function을 좋은 성능을 위해 사용하는 것 또한 가능하다. 하지만 이러한 default utility function의 unfriendliness 또한 오늘날 web browser들이 사용하는 parallel TCP 연결로 인한 손해와 비교할 만한 수준으로, TCP를 사용하는 데에 있어 심각하게 ecosystem에 문제를 야기하는 것은 아니다.

3. Prototype Design

• PCC prototype은 UDT의 udp기반의 TCP 코드를 사용하였다.

3.1 Performance Monitoring

• time-line은 $Monitor Interval$ ( MI ) 이라 불리는 지속시간 ( duration ) $T_m$ 의 chunk로 나뉜다. 특정한 sending rate로 패킷을 보낸 후 PCC 모듈은 MI 동안 보내진 패킷을 기억하고, SACK가 도착하면 각 패킷에게 어떤 일( 전송 성공, 손실 여부, RTT )이 발생했는지 알 수 있게 된다.
• Fig. 3의 예시에서, Monitor는 MI1 ( $T_0$ to $T_0 + T_m$ ) 동안 어떤 패킷이 보내졌는지를 안다. 시간 $T_1$ ( 보통 $T_0 +T_m$이후 1 RTT 지난 후 )에 monitor는 MI1 에서 보내진 모든 패킷에 대한 SACK를 받는다. Monitor는 각 SACK들을 종합해  thorughput, loss rate, average RTT를 포함한 의미 있는 Performance metrics을 계산한다. 그 후 perfromance metric은 utility function에 의해 결합된다. 이 결과가 각 MI의 제어 action (sending rate)과 성능 결과 (utility)를 연관짓는다. 이 쌍은 micro-experiment를 형성하며, 성능 지향 제어 모듈에 의해 사용된다.
• 한 Monitro Interval 동안 충분한 패킷이 있도록 하기 위해, $T_m$은 1) 패킷 10개를 보내는 시간의 최댓값과 2) [1.7, 2.2] RTT 사이의 균일한 랜덤값으로 설정하였다. 
• 한 MI의 측정결과는 다음 MI가 시작된 후에 계산되며, control module은 sending rate를 결과가 처리된 후에 바꾼다. 최적화로써, PCC는 즉시 전송률을 바꾸고 현재 MI의 시작 시간을 전송률이 바뀐 시간으로 "재조정"함으로써 다음 MI를 기다리지 않아도 되게 된다.

3.2 Control Algorithm

• Starting State : PCC는 $2*MSS/RTT$ ( MSS = Maximum Segment Size, 여기서는 1.5KB ) 의 전송률로 시작한 후 전송률을 계속 2배로 늘린다. PCC는 이 와 같은 2배 적용의 결과 (utility)를 monitor한 후, utility가 감소하기 시작할 때만, starting state에서 빠져나온 후, Decision Making State 로 들어간다. 
• Decision Making State : PCC의 현재 rate가 $r$일 때, multiple randomized controlled trials (RCTs)를 진행한다. PCC는 연속하는 4번의 MIs를 두 쌍의 pair로 나눈 후 ( 각 2 MIs ), 각 쌍에서 random한 순서로, 각 MI에서 살짝 높은 전송률 $r(1+\epsilon)$과 낮은 전송률 $r(1-\epsilon)$을 시도한다. 그 후 두 쌍 모두에서 더 높은 utility를 보이는 방향으로 전송률을 조정한다.
• 만약 두 쌍에서 서로 다른 결과가 나올 경우, PCC는 현재 전송률 $r$을 유지한채 다시 Decision Making State로 들어간 후, $\epsilon = \epsilon + \epsilon_{min}$ 로 experiment granularity를 조정한다. granularity는 $\epsilon_{min}$에서 시작하며 $\epsilon_{max}$까지 증가한다.
• Rate Adjusting State: Decision Making 후 새 전송률이 $r_0$이고 $dir \pm 1$이 선택된 방향일 때, 각 MI에서 PCC는 새로운 전송률 $r_n$ 을 $r_n = r_{n-1}*(1+n \cdot \epsilon_{min} \cdot dir)$로 설정하여 그 방향으로 점점 더 빠른 속도로 rate를 조절한다. utility가 감소하게 되면, PCC는 전송률을 $r_{n-1}$로 되돌이고 다시 Decision making State로 돌아간다.

4. Evaluation

• PCC를 개선한 PCC vivace 가 제안되었기 때문에 이후 내용 ( 성능 결과를 포함한 ) 은 PCC Vivace 논문 정리 후 필요에 따라 추가할 예정이다.