Fairness Scheduling for Coded Caching in Multi-AP Wireless Local Area Networks

1. 연구 배경 및 문제 정의 (Problem)

• 배경: 멀티미디어 트래픽의 급증으로 인해 사용자 기기의 온디바이스 메모리 (On-device memory) 를 활용한 캐싱 (Caching) 기술이 주목받고 있습니다. 특히, **부호화 캐싱 (Coded Caching, CC)**은 사용자들의 캐시 메모리를 활용하여 유니캐스트 트래픽을 멀티캐스트 전송으로 변환함으로써 이론적으로 큰 이득을 제공함이 증명되었습니다.
• 현실적 한계: 기존 CC 연구들은 대부분 정보 이론적 최적성을 증명하는 데 초점을 맞추었으나, 물리층 (PHY) 이나 MAC 층을 변경해야 하는 경우가 많아 기존 무선 표준 (예: IEEE 802.11 WiFi) 과 호환되지 않는 문제가 있었습니다. 또한, 기존 연구들은 파일 다운로드와 같은 '최악의 경우 전송 시간 최소화'에 집중하여, 실시간 비디오 스트리밍과 같은 '지속적인 데이터 유량 (Goodput)' 요구사항을 충족하지 못했습니다.
• 핵심 문제:
  1. 호환성: 기존 WiFi 표준 (PHY/MAC) 을 변경하지 않고, IP 계층 이상에서 작동하는 CC 솔루션의 필요성.
  2. 공정성 (Fairness): 다중 AP 환경에서 여러 사용자가 동시에 스트리밍할 때, 사용자 간 공정한 데이터 전송률 (Goodput) 을 보장하는 스케줄링 문제.
  3. 동적 환경: 사용자 요청이 비동기적으로 발생하고 네트워크 토폴로지가 변화하는 환경에서의 실시간 스케줄링.

2. 제안된 방법론 (Methodology)

저자들은 다중 AP (Access Point) WLAN 환경에서의 부호화 캐싱 기반 비디오 스트리밍을 위해 다음과 같은 체계적인 접근법을 제시합니다.

가. 시스템 모델 및 캐싱 전략

• Over-IP 접근: 물리층/MAC 층을 건드리지 않고 IP 계층 이상에서 동작하는 솔루션을 제안합니다.
• 비동기적/탈중앙화 캐싱: 사용자가 언제든 네트워크에 접속할 수 있도록, 오프라인 단계에서 사용자가 무작위로 선택한 '캐시 프로파일 (Cache Profile)'에 따라 비디오 청크 (Chunk) 의 하위 패킷 (Subpacket) 을 분산 저장합니다.
• 충돌 모델: WiFi 의 CSMA/CA 방식과 유사한 충돌 모델을 가정합니다. 한 사용자가 특정 AP 의 전송 범위 내에 있으면서 다른 활성 AP 의 간섭 범위 내에 있지 않을 때만 성공적으로 데이터를 수신합니다.

나. 공정성 스케줄링 최적화 문제

• 목표: 사용자별 'Goodput' (단위 시간당 재생 버퍼에 도달한 비디오 청크 수) 을 극대화하면서 공정성을 확보합니다.
• 목적 함수:
  • 비례 공정성 (Proportional Fairness, PF): 사용자 Goodput 의 기하평균을 최대화 ($\sum \log(\bar{r}_k)$).
  • 최대 - 최소 공정성 (Hard Fairness, HF): 가장 낮은 Goodput 을 가진 사용자의 속도를 최대화 ($\max \min \bar{r}_k$).
• 문제 형태: 달성 가능한 Goodput 영역 (Convex Hull) 위에서 목적 함수를 최대화하는 볼록 최적화 문제로 정의됩니다.

다. 동적 스케줄링 알고리즘 (Dynamic Scheduling)

정적 최적화 문제의 계산 복잡도가 네트워크 크기에 따라 지수적으로 증가하는 문제를 해결하기 위해 Lyapunov Drift-Plus-Penalty (DPP) 기법을 적용합니다.

1. 가상 큐 (Virtual Queue): 각 사용자의 요청 대기열 (Backlog) 을 기반으로 가중치를 동적으로 업데이트합니다.
2. 가중 합 전송률 최대화 (WSRM): 각 슬롯에서 가중치와 전송률의 곱을 최대화하는 AP 활성화 패턴 및 부호화 코드를 선택합니다.
3. 복잡도 감소 전략:
   • 동적 솔루션 (Reduced-Complexity Dynamic Solution): 동일한 캐시 프로파일을 가진 사용자 중 가장 큰 큐 백로그를 가진 사용자만 고려하여 코딩 집합을 구성함으로써 탐색 공간을 획기적으로 줄입니다.
   • 휴리스틱 (Virtual Queue Heuristic): 대규모 네트워크를 위해, 큐 백로그가 큰 사용자부터 순차적으로 AP 에 할당하는 휴리스틱 알고리즘을 제안합니다. 이는 모든 가능한 활성화 패턴을 탐색하지 않고도 좋은 성능을 냅니다.

3. 주요 기여 (Key Contributions)

1. 실용적인 CC 프레임워크: 기존 이론적 CC 와 달리, 기존 WLAN 표준과 호환되며 IP 계층에서 동작하는 비동기적/탈중앙화 CC 솔루션을 최초로 체계화했습니다.
2. 공정성 중심 스케줄링: 비디오 스트리밍에 적합한 'Goodput'을 기준으로 한 공정성 스케줄링 문제를 정립하고, 이를 위한 최적의 동적 알고리즘을 개발했습니다.
3. 복잡도 관리: 최적 해를 구하는 데 필요한 지수적 복잡도를 줄이기 위해 사용자 동치성 (Equivalence) 과 DPP 기반의 휴리스틱을 도입하여 대규모 네트워크에서도 실용적인 성능을 달성했습니다.
4. 성능 검증: 기존 방식 (전통적 캐싱, 주파수 재사용, CSMA 기반 방식) 과의 비교를 통해 제안된 방식의 우수성을 입증했습니다.

4. 실험 결과 (Results)

시뮬레이션을 통해 다음과 같은 결과를 도출했습니다.

• 기저선 대비 성능 향상: 제안된 CC 기반 스케줄링은 전통적인 접두어 캐싱 (Prefix Caching) 및 주파수 재사용 (Spatial Reuse), CSMA 기반 방식보다 현저히 높은 Goodput을 달성했습니다. 이는 멀티캐스트 전송의 이점을 효과적으로 활용했기 때문입니다.
• 공정성 달성:
  • 최적 해 (Optimum Solution): 소규모 네트워크에서 이론적 최적 공정성 점수에 근접합니다.
  • 휴리스틱 (Heuristic): 대규모 네트워크에서도 최적 해에 매우 근접한 성능을 보이며, 계산 복잡도를 크게 낮춥니다.
• L (캐시 프로파일 수) 의 영향: 캐시 프로파일 수 ($L$) 가 증가할수록 멀티캐스트 기회가 늘어나 Goodput 이 향상되지만, 일정 수준 이상에서는 포화되는 경향을 보입니다.
• 동적 환경 적응: 사용자가 네트워크에 진입하거나 이탈하는 동적 상황에서도 DPP 알고리즘이 빠르게 적응하여 새로운 최적 Goodput 으로 수렴함을 확인했습니다.
• PF vs HF:
  • HF (Hard Fairness): 모든 사용자의 최소 전송률을 보장하지만, 전체 평균 성능은 낮아질 수 있습니다.
  • PF (Proportional Fairness): 일부 사용자의 전송률은 낮아질 수 있지만, 전체 네트워크의 효율성과 적응형 비트레이트 (Adaptive Quality) 를 통한 고품질 스트리밍 사용자 수를 극대화합니다.

5. 의의 및 결론 (Significance)

이 논문은 이론적으로 우아한 부호화 캐싱 (CC) 기술을 실제 무선 네트워크 (WLAN) 환경에 적용할 수 있는 첫 번째 엄밀한 스케줄링 프레임워크를 제공한다는 점에서 의의가 큽니다.

• 실용성: 물리층 변경 없이 IP 계층에서 구현 가능하여, 기존 WiFi 인프라 (공항, 경기장, 기차역 등) 에 즉시 적용 가능한 솔루션을 제시합니다.
• 공정성 보장: 다중 사용자 환경에서 특정 사용자의 불이익 없이 전체적인 스트리밍 품질을 극대화하는 공정성 스케줄링 기법을 정립했습니다.
• 미래 지향성: 고밀도 사용자 환경에서의 비디오 스트리밍 효율성을 획기적으로 개선하여, 향후 6G 및 차세대 무선 네트워크의 핵심 기술로 자리매김할 수 있는 가능성을 보여줍니다.

요약하자면, 이 연구는 부호화 캐싱의 이론적 이득을 실제 WLAN 환경의 공정성 요구사항과 결합하여, 복잡도를 관리 가능한 수준으로 낮추면서도 기존 방식 대비 월등한 성능을 달성하는 실용적이고 확장 가능한 스케줄링 체계를 완성했습니다.