마르코프 체인(Markov Chain) 모델이란

마르코프 체인(Markov Chain) 모델은 통신, 네트워크, 운영체제, 실시간 시스템등에서 자원 사용이나 사건 발생 확률을 모델링할 대 많이 쓴다. 

1. 기본 개념

정의: 마르코프 체인은 확률 과정(stochastic process)의 일종으로, "현재 상태가 주어지면 미래 상태는 과거 상태와 무관하다"는 마르코프 성질(Markov Property)을 가진다.

$$P(X_{t+1} | X_t, X_{t-1}, ..., X_0)=P(X_{t+1}|X_t)$$

• $X_t$: 시간 $t$에서의 상태
• 미래는 오직 현재 상태에만 의존

 

2. 모델 구성 요소

1. 상태 집합 (State space, S)
   • 예: ${Idle, Success, Collision}$
   • 네트워크에서는 슬롯이 Idle인지, 성공적 전송인지, 충돌인지 등으로 정의
2. 전이 확률 (Transition probabilities, P)
   • $p_{i,j}=P(X_{t+1}=j | X_t = i), \,\,\,\, i,j \in S$
   • 현재 상태 $i$에서 다음 상태 $j$ 로 이동할 확률
3. 전이 행력 (Transition matrix)
   • $P=\begin{bmatrix}
     p_{00} & p_{01} & \cdots & p_{0n} \\
     p_{10} & p_{11} & \cdots & p_{1n} \\
     \vdots  & \vdots  & \ddots  & \vdots  \\
     p_{n0} & p_{n1} & \cdots  & p_{nn} \\
     \end{bmatrix}$
   • 각 행은 상태 $i$에서 가능한 모든 전이 확률을 의미
   • 각 행의 합은 반드시 1
4. 상태 확률 벡터 (State probability vector, $\pi$)
   • $\pi_t = [P(X_t=s_0),P(X_t=s_1),...,P(X_t=s_n)]$
   • 시간 $t$에 상태가 각 $s_i$일 확률
5. 상태 전이식 (State evolution)
   • $\pi_{t+1}=\pi_t \cdot P$

 

3. Steady-State 분석

• 시간이 충분히 크면 $(t -> \inf)$ 상태 확률 벡터는 평형 상태(steady state) 에 도달:
• $\pi=\pi P$
• 이는 선형방정식으로 풀 수 있으며, 시스템이 장기적으로 어떤 상태에 머무르는지 알려준다.
• 충돌 상태 확률이 높으면 -> 시스템 성능이 나쁨
• 성공 상태 확률이 높으면 -> 시스템이 안정적임

 

4. 네트워크/실시간 시스템에서의 활용

1. 랜덤 엑세스 MAC
   • 상태: Idle, Success, Collision
   • 전이 확률: 슬롯 당 부하 $G$, 성공 확률 $Ge^{-G}$, 충돌 확률 등으로 계산
   • 결과: 충돌이 많은 Steady-State -> 성능 한계 증명
2. 우선순위 역전 모델 (Yoon et al. 2018)
   • 상태: Success, Collision, Inversion
   • 전이 확률: 백오프 단계 별로 정의 $(p_{s,i},p_{c,i},p_{i,i})$
   • 결과: 숨은 단말이 있으면 역전 확률이 steady-state에서 무시할 수 없음을 증명
3. 실시간 시스템 자원 관리
   • 상태: CPU 점유, I/O 대기, idle 등
   • 테스크가 어떤 상태에 있을 확률을 모델링 가능
   • 예: deadline miss 확률 = collision 상태 확률과 동일한 의미

 

5. 왜 중요한가?

• 수학적 증명 도구: 시뮬레이션만으로는 얻기 어려운 "이론적 성능 한계"를 분석할 수 있음
• 확률적 자원 관리: deterministic scheduling(예: EDF)과 달리 IoT, PLC 환경은 확률적 접근이므로, 마르코프 체인이 적합
• 설득력: 제안된 알고리즘이 왜 더 나은지, steady-state 분포를 비교하면 명확히 보여줄 수 있음

 

요약하면, 마르코프 체인 모델은 시스템의 상태 전이 과정을 확률적으로 정의하고, 장기적 상태 분포를 계산해 성능 지표(성공률, 충동률, 역전률 등)를 도출하는 수학적 프레임워크이다.

 

자 이번에는 마르코프 체인의 실제 적용은 어떤식으로 이루어지는지 정리해보자.

 

1. 시스템을 상태(State)로 단순화

현실에서는 수많은 복잡한 이벤트가 동시에 발생하지만, 이를 상태로 추상화한다.

예) 무선 MAC 프로토콜 (예: Wi-Fi, PLC, LTE random access)

• Idle 상태: 슬롯에 아무도 전송 안 함
• Success 상태: 정확히 하나의 노드가 성공적으로 전송
• Collision 상태: 둘 이상이 동시에 전송하여 충돌

현실의 모든 통신 결과를 이 3가지 상태로 단순화시킨다.

 

2. 전이 확률(Transition Probability)을 실제 값으로 측정, 모델링

전이 확률은 현실적인 변수(트래픽 양, 장치 수, 전송 확률 등)에 기반한다.

• 예 ALOHA 시스템에서 offered load = $G=N_a/M$ (슬롯 당 평균 요청 수)
• 그러면:
  • 성공 확률 = $P_{succ}=Ge^{-G}$
  • 충돌 확률 = $P_{coll}=1-e^{-G}-Ge^{-G}$
  • Idle 확률 = $P_{idle} = e^{-G}$

이런식으로 실제 환경의 "트래픽 부하(G)"와 "노드 수(N)"를 대입해 전이 확률을 계산한다.

 

3. 전이 행렬로 모델링

예를 들어 3가지 상태라면 전이 행렬은 다음과 같이 구성된다.

$$P=\begin{bmatrix}
p_{idle\to idle} & p_{idle \to success} & p_{idle \to collision} \\
p_{success \to idle} & p_{success \to success} & p_{success \to collision} \\
p_{collision \to idle} & p_{collision \to success}  & p_{collision \to collision} \\
\end{bmatrix}$$

현실에서는 이 값들을 "실제 관측된 통계"나 "트래픽 모델(포아송 도착, 지수 분포 서비스 시간)"로 부터 얻는다. 

 

4. State-state 해석으로 현실 성능 지표 도출

정기적으로 이 시스템이 어느 상태에 머무르는지(Steady-State 확률)를 계산하면:

• $\pi_{success}$: 성공확률 -> 처리율(Throughput)
• $\pi_{collision}$: 충돌확률 -> 재전송 비율, 지연 증가 원인
• $\pi_{idle}$: 자원이 놀고 있는 비율 -> 자원 효율성

이를 통해 현실 시스템에서 "이 MAC 프로토콜을 쓰면 장기적으로 몇 %나 충돌이 있어나는지" 같은 결과를 수학적으로 예측할 수 있다. 

 

5. 실제 적용 예시

1. Wi-Fi (802.11 DCF)
   • Bianchi 모델(1998)이 대표적: Wi-Fi의 CSMA/CA 동작을 2차원 마르코프 체인으로 모델링
   • 현실적용: 이 모델로 Wi-Fi의 스루풋, 지연, 충돌 확률을 이론적으로 예측할 수 있음
   • IEEE 802.11 표준 성능 해석의 기본 도구가 됨
2. 전력선 통신(PLC) V2G (Yoon et al. 2018)
   
   • 상태: Success, Collision, Inversion 정의
   • 현실 적용: EV 충전 통신에서 숨은 단말이 있으면 steady-state에서 역전 확률이 높아짐 -> QoS 보장 실패
   • 해결책: 감도 조정으로 전이 확률을 바꿔 역전 상태 점유율을 줄임
3. 실시간 시스템 (Task Scheduling)
   • Task 상태: Ready, Running, Waiting, Missed Deadline
   • 현실 적용: 테스크 도착률과 CPU 스케줄링 정책을 확률적으로 모델링 -> deadline miss 확률 예측 가능

 

현실은 항상 확률적 불확실성이 존재 (패킷 충돌, 무선 채널 페이딩, Sporadic task 등등),

마르코프 체인은 "확률적 사건들의 장기적 평균 동작"을 계산하는데 매우 적합,

즉, 시뮬레이션 없이도 성능 한계를 분석적으로 예측할 수 있음 -> 알고리즘 설득력 강화

 

주요 트래픽 모델에 대해 정리해보자

1. 푸아송 (Poisson) 도착 모겔

• 정의: 단위 시간 당 발생하는 이벤트(패킷 도착 수)가 푸아송 분포를 따른다고 가정
• 수식: $P(N(t)=k)= \frac{(\lambda t)^k e^{-\lambda t}}{k!} $ 여기서, $\lambda$는 평균 도착률 (packets/sec)
• 특징: 메모리리스(memoryless) -> 지금까지 몇 개 도착했는지와 무관하게, 미래 도착 확률은 동일
• 현실 적용: 음성 통화, 센서 네트워크 등 "랜덤 이벤트" 기반 트래픽에 잘 맞음

 

2. 지수 분포 (Exponential distribution) 서비스 시간

• 패킷 처리 시간(혹은 서비스 시간)이 지수 분포를 따른다고 가정
• 수식: $f(t)= \mu e^{\mu t}, \,\,\,\, t \geq  0$, $\mu$: 평균 서비스율 (packets/sec)
• 특징: 메모리리스 -> 어떤 패킷이 이미 처리 중이어도 앞으로 얼마 더 걸리지는 과거와 무관
• 현실 적용: 무선 채널의 랜덤 전송 시간, 랜덤 Backoff timer 분석 등에 활용

 

3. 버스트(Burst) 트래픽 모델

• 현실 네트워크는 푸아송보다 더 "몰림 현상(burstiness)"이 많음 
• 대표적 모델:
  • ON-OFF 모델:
    • ON 기간에는 패킷이 집중적으로 도착 (예: 비디오 스트리밍 구간)
    • OFF 기간에는 도착 없음
  • 마르코프 모수 모델 (Markov Modulated Poisson Process, MMPP):
    • 여러 상태(High rate, Low rate)를 가지며, 상태 별로 다른 푸아송 도착률을 가짐

 

4. Self-similar / Heavy-tail 모델

• 인턴넷 트래픽 연구에서 발견된 특성: 트래픽 분포가 긴 꼬리(heavy tail)를 가짐
• Pareto 분포, Weibull 분포 등을 사용
• 현실 적용: 웹 트래픽, 비디오 스트리밍처럼 장시간 동안 bursty한 특성을 보이는 경우

 

5. 실시간/ 산업용 트래픽 모델

• 주기적(Periodic) 모델:
  • 예: 센서가 100ms마다 한 번 데이터 전송
  • 실시간 제어 시스템에서 많이 사용
• 혼합 모델:
  • 기본적으로 주기적이지만, 이벤트가 발생하면 추가 burst 발생
  • 예: 자동차 CAN 통신, EV 충전 제어 신호

 

정리하면,

• 트래픽 모델이란 "패킷/태스크가 언제 도착하는지"를 확률적으로 정의하는 가정
• 가장 기본은 푸아송 도착 + 지수 분포 서비스 시간 (M/M/1 큐 모델)
• 현실에서는 bursty-self-similar 특성을 반영한 MMPP, ON-OFF 모델, heavy-tail 분포 등을 사용
• 이 모델들을 기반으로 마르코프 체인의 전이 확률이 계산되고, 결국 현실 시스템의 충돌률, 성공률, 지연율을 예측할 수 있음

 

앞에서 말한 M/M/1 큐 모델은 대기이론 (queueing theory)에서 가장 기본적이고 유명한 모델이다. 네트워크, 운영체제, 실시간 시스템, 서버 성능 분석 등에서 기본적으로 쓰인다. 

1. 이름의 의미 ("M/M/1")

• 첫 번째 M (도착 과정, Arrival process)
  • "Markovian"을 의미 -> 푸아송(Poisson) 도착 과정을 가정
  • 즉, 고객(또는 패킷, 테스크)은 평균 도착률 $\lambda$로 무작위하게 도착
• 두 번째 M (서비스 과정, Service process)
  • 서비스 시간이 지수 분포(Exponential) -> 메모리리스 특성을 가짐
  • 평균 서비스율은 $\mu$ (1초 당 처리 가능한 평균 고객 수)
• 마지막 1 (서버 수, Number of servers)
  • 서버가 하나 뿐인 시스템
  • 즉, 한 번에 하나의 고객(패킷)만 처리 가능

따라서 M/M/1 큐는 "푸아송 도착 + 지수 분포 서비스 + 단일 서버" 시스템이다.

 

2. 시스템 모델

• 큐(Queue): 무한 버퍼 가정 (손실 없음)
• 스케줄링: 보통 FCFS (First Come, First Served)
• 상태(State): 큐에 있는 고객(패킷) 수  $S={0,1,2,3,...}$

 

3. 마르코프 체인으로 표현

• 상태=현재 시스템 내 고객 수 (큐 + 서버)
• 상태 전이:
  • 고객 도착 시: $n-> n+1$ (확률 $\lambda \delta t$)
  • 서비스 완료 시: $n-> n-1$ (확률 $\mu \delta t$)

이산 시간에서 보면 출생-사망 과정(Birth-Death Process) 으로 표현 가능 

 

4. 안정 조건

• 시스템이 안정되려면 도착률이 서비스율보다 작아야 함 : $\rho = \frac {\lambda}{\mu}<1$ ($\rho$: 서버 이용률, traffic intensity)

 

5. Steady-state 해

시스템에 고객이 $n$명 있을 확률 $P_n$: $P_n=(1-\rho)\rho^n, \,\,\,\, n=0,1,2,....$

• 평균 큐 길이 (시스템 내 고객 수 기대값): $L=\frac{\rho}{1-\rho}
• 평균 대기 시간 (고객이 시스템에 머무는 평균 시간):  $W= \frac{1}{\mu-\lambda}$
• 리틀의 법칙(Little's Law): $L=\lambda W$ (시스템 내 평균 고객 수 = 도착률 x 평균 체류 시간)

 

6. 해석 (실제 의미)

• $\rho$가 0.5일 때: 서버가 절반은 놀고, 절반은 바쁨 -> 지연이 적음
• $\rho -> 1$: 도착률이 처리율에 가까워질수록 -> 지연과 큐 길이가 무한대로 발산
• 네트워크에서 혼잡 발생 원리를 설명하는 기본 모델

 

7. 실제 적용 예시

1. 네트워크 라우터
   • 패킷 도착률이 $\lambda$, 라우터의 처리율이 $\mu$
   • 라우터 지연, 큐 길이 예측 가능
2. 운영체제 프로세스 스케줄링
   • CPU에 테스크가 푸아송 프로세스로 돡
   • CPU 서비스 시간은 지수 분포로 가정
   • 평균 대기 시간/응답 시간 계산 가능
3. 실시간 시스템 분석
   • 요청이 주기적이라면 M/D/1, 이벤트 기반이라면 M/M/1이 적합
   • deadline miss 확률 예측 가능