[2026-02-09] FitNets

🦥 본문

Motivation

• 트래픽 분포 정보의 중요성 : 트래픽 분포는 용량 계획, 트래픽 엔지니어링, 과금 및 결함 탐지 등 여러 작업에서 필수적
• Data plane 분석의 중요성 : data plane을 통해 Line-rate로 분석 후 대처
• 기존 연구의 문제점

  • 무작위 패킷 샘플링 방식의 모니터링

    무작위 패킷 샘플링은 네트워크 트래픽의 아주 작은 부분이기 때문에 정보 손실

  • data plane 모니터링 (Sampling-free)

    data plane에서 직접 쿼리를 처리하거나 스케치 같은 확률적 데이터 구조를 통해 모니터링함. data plane의 리소스 및 연산 제약

  • Over-provisioning : 정해진 정확도를 달성하기 위해 샘플링 비율을 높게 설정한 경우. 트래픽이 평온한 시간에는 적은 샘플링으로도 정확도 달성이 가능하지만 큰 샘플링을 유지하면서 자원 낭비
  • Manual Tuning : 샘플링 → Control plane 전송 → 통계 계산 → 운영자가 확인 → 피드백하는 루프에서 운영자 피드백과 트래픽 패턴 사이의 시차가 발생.

FitNets

OverView

1. 샘플로부터 분포 추정 (Control plane)
   • 추정 : 특징의 분포는 커널 밀도 추정(KDE)를 사용하여 샘플로부터 추정
   • 분포는 시간에 따라 변할 수 있기 때문에 추정 방식이 효율적이면서 계산 속도가 빨라야 함.
2. 모든 트래픽에 대한 추정치 점수화 (Data plane)
   • 점수화 : 추정치는 proper scoring rules를 사용하여 점수가 매겨짐
3. 현재 정확도를 신뢰성 있게 추정하기 위한 점수 정규화 (Control plane)
   • 정규화 : 분포 예측의 난이도는 다르기 때문에 점수를 정규화하는 작업. 추정치의 정확도는 점수를 정규화하여 계산.
     • 0~1 사이의 정규화를 위해 최적의 가능한 점수 (만점)을 추정

4. 운영자의 목표에 따른 샘플링 조정 (Control plane)

   운영자는 쿼리 언어를 사용하여 모니터링 작업을 지정하고 적응 목표를 설정

Kernel Density Estimation

커널 밀도 추정기(KDE)는 기저 분포의 형태를 가정하지 않는 유용하고 비모수적인 추정기이며, 고속 푸리에 변환(FFT)을 사용하여 효율적으로 계산

KDE의 평균 통합 제곱 오차(MISE)는 실제 분포를 모르더라도 주어진 훈련 샘플 크기에 대해 점진적으로 근사화.

• 비모수적 : 데이터를 분석할 때 특정한 확률 분포를 따른다는 가정(데이터의 기저 구조에 대한 가정)을 하지 않음

Density Estimation

(a) : 각 샘플에 중심을 두고 대역폭에 의해 크기가 조정된 커널들을 결합하여 분포를 추정하며, 데이터 지점들을 통과하는 매끄러운 선을 만듦

• 커널 : 각 데이터 지점에서 주변에 미치는 영향력의 모양. 주로 미분 가능성과 같은 결과 추정치의 수학적 특성을 결정

(b) : 대역폭은 bias와 매끄러움 사이의 상충 관계를 결정

• 수식

  $x_{1},…,x_{n}$을 알 수 없는 확률 밀도 f로부터 추출된 독립적이고 동일하게 분포된 샘플이라고 가정

  \[⁍\]

  $f_{n}(x)$: 우리가 최종적으로 추정하고자 하는 확률 밀도 함수

  h : 대역폭

점근적 수렴

충분한 샘플이 주어지면 평균 통합 제곱 오차(MISE)가 $n \rightarrow \infty$일 때 0으로 수렴

\[⁍\]

• 기댓값(E) : 데이터 샘플을 n개 뽑을 때마다 추정 분포가 달라질 수 있으므로 여러 번 샘플링 했을 때의 평균 오차를 구함

만약 MISE를 최소화하는 최적의 대역폭 h를 설정했다고 가정하는 경우. 다음과 같이 근사화

\[⁍\]

• c는 알 수 없는 실제 분포의 곡률에 의해 결정. 즉, 실제 곡률을 알 수 없기 때문에 최적의 대역폭을 정할 수 없음
  • 곡률이 클 수록 c가 커짐 → 복잡할 수록 c가 커지므로 오차를 줄이기 위해서는 데이터의 개수(n)이 커져야 함
• 개선된 쉬더-존스 알고리즘을 사용하여 반복된 계산을 통해 최적의 대역폭 h를 찾아감. 어려운 분포에서도 좋은 대역폭을 찾을 수 있고 (견고성), 효율적으로 계산

Proper Scoring Rules

추정된 분포의 정확한 오차를 결정하는 것은 불가능하지만 테스트 샘플을 통해 추정치에 점수를 매김. 점수가 클 수록 실제 분포와 추정 분포 사이의 거리가 최소화

Quadratic Score, QS (이차 점수)

QS를 최대화하는 것은 통합 제곱 오차(ISE)를 최소화 하는 것.

• 점수 산정 방식의 적정성 : 실제 분포와 똑같은 추정치의 점수가 가장 높을 때 ‘적정하다’라고 하고 실제와 100%일치할 때만 최고점을 받고 조금이라도 다른 경우 깎일 때 ‘엄격하게 적정하다’라고 함

• 거리 지표 : 최적 점수 (실제 분포의 점수)와 추정된 분포의 점수 차이

  \[⁍\]
• 평균 제곱 오차

\[⁍\]

평균적인 오차는 최고 점수 - 데이터 평면에서 여러 샘플로 측정한 평균 점수

데이터 평면 점수 산정

점수 계산은 테스트 샘플을 한 번 훑는 것만으로 가능함. x에 대한 보상을 찾아보고 평균 계산이 가능하도록 샘플 수와 보상 합계에 대한 카운터를 각각 증가 시킴.

• 수식

  

  • reward : 테스트 샘플에 대한 올바른 예측을 보상. 테스트 샘플 x의 확률값의 2배.
  • 정규화 : 지나치게 복잡한 추정을 방지. 확률 밀도 함수를 제곱하여 전체 면적을 구함
    • 샘플과 무관
    • 모든 부분에서 확률이 높은 것 억제

    • 그래프가 뾰족하여 특정 지점에 확률을 집중한 것을 억제함.

      → 매끄러운 분포를 만듦

Normalization

특정 점수가 어떤 분포에는 최적에 가까울 수 있지만 다른 분포에는 최적과 거리가 멀 수 있기 때문에 각 점수들을 비교하기 위해서 정규화가 필요.

0~1 사이의 값이며 1은 최적의 추정치인 경우.

정규화를 위해서는 달성 가능한 최적의 점수를 추정.

\[⁍\]

이 때 최적의 점수 역시 알 수 없기 때문에 최적 점수에 대한 근사화를 진행

\[MISE(f_{n}) = QS(f, f) - E[QS(f_{n}, f)] \approx cn^{-4/5}\]

QS(f, f)를 알아내야 하고, c를 모르기 때문에 제한된 선형 최적화를 이용

• 제한된 선형 최적화

  

  • $\vec{N}$을 서로 다른 샘플 크기의 벡터
  • $\vec{S}$를 평균 이차 점수의 벡터
  • $\vec{S}{i}$*는 $f$로부터 크기 $\vec{N}{i}$*의 샘플로 추정된 분포들의 평균 점수
  • $QS_{opt} = QS(f, f)$이고, $QS_{max}$는 해당 분포에 대한 모든 추정치에서 관찰된 가장 높은 점수

예측된 정규화된 이차 점수

\[⁍\]

위의 공식을 통해, n개에 대한 예상되는 정확도를 계산. 역함수가 존재하므로 정확도 달성을 위한 예상되는 샘플 개수가 나옴.

서브 샘플링

샘플을 뽑고 KDE를 만들고 점수를 매기는 과정을 샘플 크기를 바꿔가며 여러 번 반복해야 최적화 문제를 푸는 데, 비효율적

운영자에게 정규화된 점수를 빠르게 전송하기 위해 서브 샘플링 사용

1. 샘플링된 n에서 여러 서브 샘플($n_i$)을 추출. n에 대한 추정과 병렬적으로 서브 샘플에 대한 밀도도 추정
2. 모든 추정치에 대해 병렬적으로 점수를 매겨 최적화 문제를 해결

일반화

샘플 크기가 증가할 수록 거리가 줄어든다는 가정하에, KDE 뿐만 아니라 다른 추정기나 점수 산정 함수에도 일반화

System Design

Interface

입력

• 모니터링 작업

  

  1. 모니터링되는 위치
  2. 제약 조건 : 어떤 트래픽이 모니터링 되는 지
     • 5-tuple의 개별 또는 조합
  3. 어떤 특징이 모니터링 되는 지
     • 각 위치에 대해 여러 제약 조건과 여러 특징 모니터링
     • 단일 패킷 특징이나 패킷 간의 상태 유지가 필요한 더 복잡한 특징들을 선택 가능
     • 플로릿 : 비활성 간격으로 구분된 짧은 패킷 버스트

  플로우에 대한 statefull한 특징들은 논문에서 구현 X. 저자들은 이 부분을 데이터 전처리의 역할로 보고 범위를 벗어난다고 하고 있음.

• 적응 목표

  1. 고정된 자원에 대해 모든 작업의 정확도를 최대화
  2. 고정된 정확도에 대해 자원을 최소화

출력

데이터를 단계 별로 처리하여 각 모니터링 작업에 대한 밀도 추정치와 정확도를 출력

Control plane

1. 밀도 추정

   이전 단계 이후 수집된 샘플로부터 밀도 모델이 추정되고 점수 산정을 위해 데이터 평면으로 다시 전송

   • 작업 당 여러 개의 밀도가 필요

     메인 밀도(모든 가용 데이터 기반)와 서브 샘플 기반의 추가 밀도 (정확도 계산용). 하나의 평균 밀도만 data plane으로 보냄.

     모든 가용 데이터를 사용하지만 중복을 방지하여 밀도 추정 및 평균 점수에 편향을 방지

2. 정규화

   이전 단계 이후에서 추정된 밀도에 대한 점수를 받으면, 최적화 문제를 해결하고 정규화 진행

3. 적응

   운영자의 목표를 최적화하여 작업 당 샘플링 비율을 조정

   점수 예측을 통해 샘플링 비율을 조정

   • 두 가지 목표
     1. 정확도 달성을 위해 필요한 자원 예측. 이 최소한의 필요한 자원량을 수집하도록 샘플링 비율 조정
     2. 최소 정확도를 최대화 하기 위한 최적화. 가장 정확도가 낮은 밀도의 정확도를 극대화

대부분의 처리 단계가 독립적이므로 병렬화 가능

• 서로 다른 샘플의 밀도 추정, 점수 정규화는 샘플과 점수에만 의존하므로 병렬화 가능
• 적응의 경우. 자원 최소화 목표는 병렬화가 가능하지만 정확도 최대화는 최대 정확도가 개별 작업의 필요 자원에 의존하므로 병렬화 불가

Data plane

P4는 다단계 파이프라인을 방식이며, 각 단계는 하나 이상의 매치-액션 테이블이 적용.

P4 프로그램은 아키텍처와 configuration으로 분리

• 아키텍처 : 테이블 레이아웃이나 메모리 유형 및 크기와 같은 프로그램의 제어 흐름
  • 아키텍처 변경을 위해서는 새 아키텍처 설치를 위해 스위치를 재시작 및 컴파일
• configuration : 테이블 규칙, 메모리 내용 및 미터 속도를 포함하며 런타임에 변경

모니터링 작업을 위한 초기 설정의 메모리 크기 할당은 아키텍처 결정으로 신중히 결정해야함. 적응형 샘플링은 configuration 변경

동작 흐름

1. 전처리 : 트래픽 매칭 및 특징 추출
   • 필터링
     • 제약 조건은 패킷의 5-tuple을 매칭하고, 모든 활성 모니터링 작업의 ID를 반환하는 테이블을 사용하여 ID가 반환될 때 해당 모니터링 작업이 활성화
     • 테이블의 Ternary matches : 일반적인 스위치보다 복잡한 조건 검사 가능. 하나의 패킷이 여러 개 모니터링 작업에 해당 가능
   • Flowlet(작은 단위의 패킷 흐름) 상태 확인
     • 현재 패킷의 상태 확인
       1. 패킷이 새 플로릿의 시작
       2. 패킷이 활성 플로릿에 속함
       3. 패킷이 플로릿을 종료 (FIN)
       4. 해시 충돌로 인해 상태를 결정할 수 없는 경우
     • 충돌과 타임아웃을 모두 확인하기 위해 플로우 ID와 플로릿의 마지막 패킷 타임스탬프를 저장
   • 특징 추출
     • 매 패킷마다 모든 특징을 추출하기는 어렵고 이런 추출되지 않은 특징은 샘플링 및 점수 산정에서 제외
       • EX) 플로릿 지속 시간은 마지막 패킷만 추출 가능
2. 샘플링 : 속도 제한 meter를 통해 특징을 샘플링할 지 점수 산정에 사용할 지 결정.
   • direct meter : 특징 추출 테이블에 부착. 각 매치에 대해 개별적인 속도를 유지하고 매치될 때마다 자동으로 실행
   • meter를 통해 특정 속도 밑이면 샘플링 특정 속도 초과면 점수 산정을 함.
   • 샘플링은 새로운 패킷을 생성하여 control plane에 보냄

3. 점수 산정

   파이프라인 마지막 단계에서 샘플링되지 않은 특징 값들을 테스트 샘플로 사용하여 추정 점수를 업데이트. 테스트 샘플의 수와 보상의 합계를 카운트.

   • 여러 작업을 하는 경우에는 작업 k개의 카운터와 테스트 샘플 수에 대한 카운터 1개 → k+1개의 카운터 필요

   Ternary match를 사용하여 확률 계산. 패킷 크기는 양자화를 하고 확률을 정수로 만듦. 확률 변화가 심한 곳은 촘촘하게 완만한 곳은 넓게 잡아 테이블 수를 일정하게 유지하면서 해상도를 동적으로 조정

   1. 제어 평면에서 곡률이 높은 곳과 낮은 곳을 파악
   2. 비트 마스킹 : 2진수에서 마지막 3비트를 무시(Ignore)하면, 2^3 = 8개 숫자를 동시에 검색하는 효과
      1. 촘촘한 구간은 빈 크기를 2 or 4로 잡아서 TCAM의 마지막 1~2비트만 무시
      2. 넓은 구간은 2^5, 2^8로 잡아서 TCAM의 마지막 5~8비트를 무시
   3. 테이블 엔트리에 할당

Evaluation

방법론

Ground Truth : FitNets의 성능, 특히 점수 정규화의 정확도를 평가하기 위해서는 기준이 되는 실제 분포(Ground Truth)

• 데이터셋

  CAIDA 백본 트레이스를 분석하여 5가지 서로 다른 트래픽 특징에 대한 데이터 수집

  

  • e : 플로릿 지속 시간 분포는 더 복잡함
• 측정 기준
  1. 밀도 추정의 기대 점수
  2. 최적 점수
  3. 기대 점수를 최적 점수로 나누어 얻은 정확도/정규화 점수
  4. 추정치와 실제 분포 사이의 통합 제곱 오차(ISE)

• 구현

  1,000라인의 Python 코드를 사용. 제어 평면의 멀티코어 버전을 구현. 시뮬레이션된 스위치를 사용하여 패킷을 처리.

  P4Tofino를 사용하여 FitNets 데이터 평면의 P4 버전을 각각 약 500라인의 코드로 구현

밀도 추정

훈련 샘플 크기가 증가함에 따라 어떤 분포든 점근적으로 근사할 수 있지만, 일부 분포는 다른 분포보다 더 큰 샘플 크기를 필요

• 실험 방법 : 샘플 크기를 늘려가며 KDE를 계산하고, 실제 분포와의 오차(ISE)를 측정.

데이터 평면 점수 산정

훈련 샘플과 거의 비슷한 크기의 테스트 샘플이 있어야만 신뢰할 수 있는 점수를 얻을 수 있음

FitNets는 적은 수(1%)로 샘플링하고 나머지(99%)를 테스트할 수 있기 때문에 신뢰할 수 있는 점수를 얻게 됨.

정규화

• 실험 방법 : 서브 샘플들을 만들어 추가 모델을 생성하여 최적 점수를 추정.

5개일 때는 5% 미만으로 전체 데이터를 반복적으로 쓰는 게 아니라 서브 모델들로도 정밀하게 예측 가능

더 많은 수의 서로 다른 샘플 크기를 사용하는 것이 성능을 실질적으로 더 개선하지는 않는데, 이는 훈련 샘플이 점점 더 작은 크기의 서브 샘플로 나뉘면서 추가 추정기들의 품질이 떨어지기 때문

벤치 마크

• 실험 방법 : control plane의 시간 측정
• 밀도 추정 시간 : 최대 10만 개의 샘플에 대한 분포를 추정하는 데 약 40밀리초가 소요. 샘플 크기가 더 커지면 시간은 선형적으로 증가하며, 390만 개의 샘플에 대해서는 약 1초가 필요.
  • 다중 밀도 추정으로 확장하는 과정은 병렬화가 가능
• 최적화 & 정규화 시간
  • 최적화당 10밀리초 미만이 소요
  • 정확한 정규화를 위해 많은 수의 샘플 크기가 필요하지 않으므로 500개의 개별 작업에 대해 50ms 미만이 소요

Case Studies: Adaptive Allocation

• 자원 최소화

  모든 트래픽 특징에 대해 0.98의 정확도 목표를 지정. FitNets는 필요한 샘플 수를 최소한으로 줄이면서도, 일반적으로 $\pm 0.02$, 최악의 경우 $\pm 0.04$ 이내로 요구 정확도를 유지

• 정확도 최대화

  

  고정된 대역폭의 정적 할당과의 비교. 더 높은 정확도 달성

관련 연구

스케치

데이터 구조 자체가 네트워크 내 처리에 매력적이기 때문에, FitNets에서 상태 집약적인 특징을 추출하기 위한 빌딩 블록으로서 흥미로운 요소

적응형 스트림 처리

비디오 스트리밍 분야에서는 정확도 목표를 달성하기 위해 대역폭을 조정하는 것이 실용적이고 효과적임이 입증. 적정 점수 산정 규칙을 기반으로 구현

Conclusion

제어 평면(Control Plane)과 데이터 평면(Data Plane)을 피드백 루프 정확도 조건을 충족하거나 고정된 샘플링 예산 내에서 정확도를 최대화하는 등 다양한 모니터링 목표에 적응할 수 있음을 보여줌