A Learning-Based Superposition Operator for Non-Renewal Arrival Processes in Queueing Networks

이 논문은 다양한 비재생 도착 프로세스의 합성을 정확하게 모델링하기 위해 합성 마코프 도착 프로세스 (MAP) 로 학습된 심층 학습 기반의 확장 가능한 초위치 연산자를 제안하여, 기존 재생 근사법보다 정밀한 분산 성능 분석을 가능하게 합니다.

핵심

이 논문은 **"대기 행렬 (Queueing Networks) 에서 여러 줄이 하나로 합쳐질 때, 그 흐름을 어떻게 정확하게 예측할 것인가?"**라는 아주 실용적인 문제를 해결하기 위해 **인공지능 (딥러닝)**을 활용한 새로운 방법을 제안합니다.

기존의 수학적 방법들은 너무 복잡하거나, 중요한 정보를 잃어버려서 정확하지 않았습니다. 이 논문은 그 문제를 **"데이터를 학습한 스마트한 번역기"**로 해결했습니다.

다음은 이 논문의 핵심 내용을 일상적인 비유로 설명한 것입니다.

---

1. 문제 상황: "혼잡한 고속도로의 합류 지점"

생각해 보세요. 두 개의 다른 고속도로 (A 도로와 B 도로) 가 하나로 합쳐지는 지점이 있다고 가정해 봅시다.

• A 도로: 차들이 규칙적으로, 천천히 들어옵니다.
• B 도로: 차들이 갑자기 몰려오기도 하고, 한참 비어 있기도 합니다 (불규칙함).

이 두 도로가 합쳐지면 (Superposition), 새로운 하나의 도로가 생깁니다. 문제는 이 새로운 도로의 흐름이 어떤지 예측하는 것입니다.

• 기존의 문제점:
  • 수학자 A (전통적 방법): "차들의 평균 속도와 간격만 보면 돼!"라고 말합니다. 하지만 이 방법은 차들이 갑자기 몰려오는 '뭉침 (Burstiness)'이나 '불규칙한 패턴'을 무시합니다. 그래서 실제 교통 체증이 얼마나 심할지 잘못 예측합니다.
  • 수학자 B (정확한 방법): "모든 차의 움직임을 하나하나 추적하자!"라고 말합니다. 하지만 차가 너무 많으면 (데이터가 방대해지면) 계산하는 데 시간이 너무 오래 걸려서 현실적으로 불가능합니다.

2. 해결책: "스마트한 흐름 번역기 (신경망)"

저자는 이 문제를 해결하기 위해 **딥러닝 (Neural Network)**을 사용했습니다. 이 모델을 **"흐름 번역기"**라고 상상해 보세요.

• 학습 과정 (훈련):
  이 번역기는 먼저 가상의 데이터로 엄청나게 많은 연습을 했습니다.

  1. 컴퓨터로 수천 가지의 다양한 '가상의 차 흐름 (MAPs)'을 만들어냈습니다.
  2. 이 흐름들을 수학적으로 정확하게 합쳐서 (정답) 어떤 결과가 나오는지 계산했습니다.
  3. 입력: "A 도로는 평균 5 분, B 도로는 평균 10 분, 그리고 A 도로는 2 분마다 한 번씩 몰려와요." 같은 간단한 통계 정보 (평균, 분산, 상관관계 등).
  4. 출력: "합쳐진 도로는 이렇게 움직일 거예요."라는 정답 데이터.
  5. 이 '간단한 정보'와 '정답'을 수백만 번 반복해서 학습시켰습니다.

• 실전 (추론):
  이제 실제 상황에 적용할 때는 더 이상 복잡한 수학적 계산을 할 필요가 없습니다.

  • 두 도로의 간단한 통계 정보만 입력하면, 학습된 AI 가 합쳐진 도로의 복잡한 흐름 패턴을 순식간에 예측해 줍니다.
  • 마치 "이 두 가지 재료를 섞으면 어떤 맛이 날지"를 요리사가 경험으로 바로 알아내는 것과 같습니다.

3. 왜 이 방법이 특별한가요? (핵심 장점)

이 번역기는 기존 방법들보다 훨씬 더 똑똑하고 빠릅니다.

1. 정보를 잃지 않아요: 기존 방법들은 "평균"만 보고 예측해서 중요한 '뭉침'이나 '불규칙성'을 놓쳤습니다. 하지만 이 AI 는 **평균뿐만 아니라, 차들이 얼마나 불규칙하게 몰려오는지 (고차 모멘트)**까지 기억하고 있습니다.
2. 정확도가 압도적이에요: 실험 결과, 기존 수학적 방법들은 예측 오차가 30%~3000% 에 달하는 반면, 이 AI 는 오차 2% 미만으로 매우 정확하게 예측했습니다. 특히 교통이 막히고 차들이 불규칙하게 몰릴 때 (고부하 상황) 그 차이가 극명했습니다.
3. 순간적입니다: 복잡한 계산을 하는 대신, 학습된 AI 가 순식간에 답을 내놓습니다. 수천 개의 시나리오를 동시에 계산해도 몇 초면 끝납니다.

4. 실제 적용: "공장 라인 분석"

이 기술은 단순히 도로만 분석하는 게 아닙니다.

• 공장: 여러 공장에서 나온 부품이 하나의 조립 라인으로 들어올 때, 어떤 부품이 얼마나 불규칙하게 들어오는지 예측합니다.
• 데이터 센터: 여러 서버에서 데이터가 하나의 라우터로 몰릴 때, 네트워크가 얼마나 버거워질지 예측합니다.

이 논문에서는 이 '흐름 번역기'를 세 개의 다른 AI 모듈 (흐름 합치기, 흐름 분리하기, 대기 줄 길이 예측하기) 과 연결했습니다. 그 결과, 복잡한 공장이나 통신 네트워크 전체의 정확한 혼잡도를 예측할 수 있게 되었습니다.

5. 결론: "복잡한 세상을 단순하게 만드는 마법"

이 논문의 핵심 메시지는 다음과 같습니다.

"우리는 더 이상 복잡한 수학적 공식을 외워서 모든 상황을 계산할 필요가 없습니다. 대신, 데이터를 통해 '흐름의 법칙'을 학습한 AI에게 맡기면, 훨씬 빠르고 정확하게 복잡한 시스템 (대기 행렬, 교통, 공장 등) 의 미래를 예측할 수 있습니다."

이 방법은 불규칙하고 복잡한 현실 세계를, 간단한 통계 정보로 요약하면서도 정확한 결과를 내는 새로운 패러다임을 제시합니다. 마치 복잡한 악보를 보지 않고도, 몇 마디만 듣고 다음 소리가 무엇인지 알아맞히는 천재 음악가와 같습니다.

기술 요약

1. 문제 정의 (Problem Definition)

• 배경: 실제 시스템 (제조, 통신, 서비스 등) 에서는 여러 개의 독립적인 트래픽 스트림이 하나의 서비스 노드로 합쳐지는 현상이 빈번하게 발생합니다.
• 핵심 난제:
  • 포아송 과정의 중첩은 여전히 포아송 과정이지만, 일반적인 비재생 (Non-Renewal) 또는 비마르코프 (Non-Markovian) 과정의 중첩은 재생 과정이나 마르코프 과정으로 닫히지 않습니다.
  • 기존 방법론은 중첩된 흐름을 단순한 재생 과정 (Renewal Surrogate) 으로 근사하거나, 정확한 표현을 위해 마르코프 도착 과정 (MAP) 의 크로네커 합 (Kronecker construction) 을 사용하지만, 이는 계산 비용이 너무 많이 들거나 고차 모멘트와 시계열 의존성 정보를 잃어버립니다.
  • 결과적으로, 평균 대기 시간 등 1 차 성능 지표는 예측 가능하지만, 큐 길이 분포나 대기 시간의 꼬리 (Tail) 와 같은 분포 기반 성능 분석은 신뢰할 수 없게 됩니다.
• 목표: 다양한 변동성 (Variability) 과 상관관계 (Correlation) 구조를 가진 비재생 도착 스트림들을 합칠 때, 고차 모멘트와 단기 의존성 구조를 보존하면서 확장 가능한 (Scalable) 중첩 연산자를 개발하는 것입니다.

2. 방법론 (Methodology)

저자는 신경망 (NN) 을 기반으로 한 데이터 기반 중첩 연산자를 제안하며, 다음과 같은 단계를 거칩니다.

A. 데이터 생성 및 학습 (Data Generation & Training)

• 데이터 소스: 정확한 중첩 계산이 가능한 **마르코프 도착 과정 (MAP)**을 사용하여 학습 데이터를 생성합니다. MAP 은 비음수 분포 클래스에서 밀집되어 있어 다양한 비재생 과정을 근사할 수 있습니다.
• 생성 전략: 학습 데이터의 다양성을 확보하기 위해 세 가지 다른 알고리즘을 사용하여 MAP 을 생성합니다.
  1. 강한 음의 상관관계: 빠른/느린 상태가 교대로 발생하여 짧은 간격과 긴 간격이 번갈아 나타나는 구조.
  2. 강한 양의 상관관계: 같은 상태에 머무는 확률이 높아 짧은 간격이나 긴 간격이 군집 (Clustering) 되는 구조.
  3. 약한 상관관계: 다양한 변동성 (SCV, 왜도, 첨도) 을 가지면서도 조절된 상관관계를 갖는 구조.
• 입력/출력:
  • 입력: 각 입력 스트림의 첫 $n$개 모멘트 (평균, 분산, 왜도 등) 와 선택된 지연 (Lag) 에 대한 자기상관 계수.
  • 출력: 중첩된 과정의 첫 5 개 모멘트와 단기 의존성 구조 (자기상관 계수).
• 학습 목표: 입력 스트림의 통계적 기술자 (Descriptors) 를 중첩된 스트림의 통계적 기술자로 매핑하는 함수를 학습합니다.

B. 신경망 아키텍처

• 모델: 완전 연결 피드포워드 신경망 (Fully Connected Feed-forward NN) 을 사용합니다.
• 손실 함수: 모멘트 예측 오차와 자기상관 계수 예측 오차의 가중 합 (Weighted Sum) 을 최소화하도록 설계되었습니다. 모멘트의 동적 범위를 줄이기 위해 로그 변환을 적용했습니다.
• 특징: 추론 (Inference) 시에는 MAP 의 상태 공간이 필요 없으며, 오직 도착 과정의 모멘트와 자기상관 계수만 입력받습니다.

C. 대기행렬 네트워크 분석 프레임워크

제안된 중첩 연산자는 Sherzer (2025) 의 기존 연구와 결합되어 전체 네트워크 분석을 가능하게 합니다.

1. 중첩 (Superposition): 외부 스트림들이 합쳐질 때 NN 1 을 사용하여 중첩된 도착 과정의 기술자를 생성.
2. 이탈 과정 (Departure Process): 서비스 노드를 통과한 후의 이탈 과정을 NN 2 로 근사.
3. 정상 상태 분포 (Steady-State): 최종 노드의 고객 수 분포를 NN 3 으로 예측.
   이러한 모듈화된 접근 방식은 피드포워드 (Feed-forward) 네트워크의 분해 기반 분석을 가능하게 합니다.

3. 주요 기여 (Key Contributions)

1. 신경망 기반 중첩 연산자 개발: 비재생 스트림의 중첩을 위해 고차 모멘트와 의존성 기술자를 직접 근사하는 최초의 데이터 기반 연산자입니다.
2. 확장성 및 정확성: 기존 재생 근사 (Whitt, Albin 등) 나 MAP 기반 정확한 계산보다 훨씬 정확하면서도 계산 비용이 적게 듭니다.
3. 오픈 소스 구현: 학습된 모델과 데이터 생성 코드를 오픈 소스로 공개하여 재현성을 보장합니다.
4. 비마르코프 네트워크 분석의 확장: 기존의 연쇄 (Tandem) 시스템 제한을 넘어, 합류 (Merging) 가 있는 일반적인 피드포워드 네트워크에 대한 분해 기반 분석을 가능하게 했습니다.

4. 실험 결과 (Results)

저자는 다양한 변동성 (SCV) 과 상관관계 (Autocorrelation) regimes 에서 실험을 수행했습니다.

• 모멘트 및 자기상관 예측 정확도:
  • 제안된 NN 은 2 차부터 5 차까지의 모멘트에서 평균 절대 백분율 오차 (MAPE) 가 0.5% ~ 3.5% 수준으로 매우 정확했습니다.
  • 자기상관 계수 예측 오차 (MAE) 는 0.002 ~ 0.03 사이로 매우 낮았습니다.
  • 비교: 기존 방법 (Whitt, Albin) 은 변동성이 높거나 상관관계가 강한 경우 오차가 30% 에서 3000% 까지 치솟았으나, NN 은 모든 regime 에서 3% 미만의 오차를 유지했습니다.
• 대기행렬 네트워크 성능:
  • System 1 (단일 노드): 제안된 분해 방식은 평균 상대 오차 (REM) 가 **2.86%**였으며, 기존 Whitt 근사 (9.20%) 보다 약 69% 정확도가 향상되었습니다.
  • System 2 (3 노드 네트워크): 여러 노드를 거치며 오차가 전파되더라도 NN 기반 방식은 평균 REM **4.17%**를 기록하여, 기존 방법 (10.73%) 보다 훨씬 우수한 성능을 보였습니다.
  • 특히 고변동성과 양의 상관관계가 공존하는 복잡한 환경에서 NN 의 우월성이 두드러졌습니다.
• 계산 효율성:
  • 5,000 개의 인스턴스에 대한 추론 시간이 0.004 초로, 실시간 분석 및 대규모 설계 공간 탐색에 적합합니다.

5. 의의 및 결론 (Significance & Conclusion)

• 이론적 기여: 대기행렬 이론에서 오랫동안 해결되지 않았던 "비재생 과정의 중첩" 문제를 데이터 기반 학습을 통해 해결했습니다. 이는 고차 모멘트와 의존성 정보를 보존하면서 분해 기반 분석을 가능하게 하는 획기적인 접근입니다.
• 실용적 가치:
  • 상태 공간 폭발 (State-space explosion) 회피: MAP 의 정확한 중첩은 상태 수가 곱셈적으로 증가하여 계산이 불가능해지는 문제를 피합니다.
  • 정확한 분포 예측: 평균값뿐만 아니라 큐 길이 분포 전체를 예측할 수 있어, 시스템의 안정성과 서비스 품질 (QoS) 분석에 필수적입니다.
  • 확장성: 이 프레임워크는 향후 분할 (Splitting/Thinning) 연산자를 추가하여 더 복잡한 피드포워드 네트워크나 피드백 루프가 있는 네트워크로 확장될 수 있는 기초를 마련했습니다.

결론적으로, 이 연구는 복잡한 비마르코프 대기행렬 네트워크를 분석하기 위한 모듈화되고 데이터 기반의 새로운 패러다임을 제시하며, 기존 분석적 방법론의 한계를 극복하고 정확한 분포 기반 성능 평가를 가능하게 합니다.