확률적 네트워크에서의 유한 시간 큐 피크 법칙: 기하학적 임계값 이후의 로그 스케일링

우리는 많은 큐(queue)가 제한된 서비스 자원을 공유하는 표준 확률적 네트워크 모델인 일반화된 스위치(generalized switches)에서의 유한 시간 큐 피크(finite-horizon queue peaks)를 연구합니다. 도착(arrivals)은 의존적이고, 시간에 따라 변하며, 과거에 적응할 수 있습니다. 부하 조건(standing load condition)은 균일한 내부 여유(uniform interior slack)로, 이는 조건부 평균 도착 벡터가 용량 영역(capacity region)의 고정된 수축(contraction) 내에 머무름을 의미합니다. 우리는 이러한 여유(slack)가 MaxWeight와 같은 드리프트 최소화 스케줄링 정책(drift-minimizing scheduling policies)의 유한 시간 피크 법칙(finite-time peak law)을 재형성함을 보여줍니다. 여유가 없을 때 날카로운(sharp) 형태를 띠는 제곱근 포락선(square-root envelope)은 기하학적 의존적 임계값(geometry-dependent threshold)까지만 지속됩니다. 해당 임계값을 넘어서면, 실행 최대값(running maximum)은 높은 확률(high probability)과 기대값(expectation) 모두에서 호라이즌(horizon)에 따라 로그 단위(logarithmically)로만 성장합니다. 그 메커니즘은 자기 정규화(self-normalization)입니다. 현재 큐 방향에서 투영된 변동 규모(projected fluctuation scale)는 안정화 드리프트 규모(stabilizing drift scale)에 의해 정규화됩니다. 이는 로그 계수(logarithmic coefficient)에서 용량 기하학(capacity geometry)을 제거하는 반면, 기하학은 임계값에는 남아있게 합니다. 일치하는 하한(Matching lower bounds)은 로그 항과 기하학적 임계값 모두 피할 수 없음을 보여줍니다. 유한 시간 상태 공간 붕괴(finite-time state-space collapse)가 가능한 경우, 국소적 병목 기하학(local bottleneck geometry)을 사용하여 임계값을 더 정교하게 다듬을 수 있습니다. 일반화된 입력 큐 스위치(generalized input-queued switches)의 경우, 우리는 타이트한 로그 계수를 가진 유한 시간 피크 경계(finite-time peak bounds)를 얻습니다. 시뮬레이션은 이론에 의해 예측된 두 단계 포락선(two-phase envelope), 국소적 기하학적 개선(local geometric refinements), 그리고 분산 민감형 개선(variance-sensitive improvements)을 보여줍니다.