AncomWiki

Scheduling in a Random Environment: Stability and Asymptotic Optimality

Properties1
description이 논문은 무선 채널 환경에서 여러 사용자가 공유 자원을 사용할 때의 스케줄링 문제를 다룹니다. 유체 스케일(fluid-scaled) 시스템을 분석하여 시스템의 안정성 조건과 최대 안정 정책(maximum stable policies)을 규명했습니다. 주요 발견으로는, Score-Based나 Proportionally Best 같은 기회의 스케줄링 정책은 최대 안정 조건 하에서 안정적이지만, Relative-Best나 cmu…

11 min read

Scheduling in a Random Environment: Stability and Asymptotic Optimality

Source

  • Evernote/Papers/Scheduling in a Random Environment Stability and Asymptotic Optimality.md

Summary

이 논문은 무선 채널 환경에서 여러 사용자가 공유 자원을 사용할 때의 스케줄링 문제를 다룹니다. 유체 스케일(fluid-scaled) 시스템을 분석하여 시스템의 안정성 조건과 최대 안정 정책(maximum stable policies)을 규명했습니다. 주요 발견으로는, Score-Based나 Proportionally Best 같은 기회의 스케줄링 정책은 최대 안정 조건 하에서 안정적이지만, Relative-Best나 cmu-rule은 그렇지 않다는 점입니다. 또한, 평균 지연 성능을 위해 ‘myopic’이라고 불리는 tie-breaking 규칙(이탈 확률이 가장 높은 사용자에게 우선순위 부여)이 중요하며, 이를 적용한 단순 우선순위 인덱스 정책이 안정적이고 점근적으로 최적임을 증명했습니다.

Key Points

  • 무선 채널 변동 환경에서의 자원 스케줄링 안정성 및 평균 지연 분석
  • 유체 스케일 시스템을 통한 최대 안정 정책(maximum stable policies) 도출
  • Score-Based, Proportionally Best 등은 안정적이지만, Relative-Best, cmu-rule은 불안정
  • 평균 지연 성능 향상을 위해 이탈 확률이 높은 사용자를 우선하는 ‘myopic’ tie-breaking 규칙의 중요성
  • Myopic tie-breaking 규칙을 적용한 단순 우선순위 인덱스 정책이 안정적이고 점근적으로 최적임

그래프 뷰

백링크