단일 링크 모델
다중 서비스 클래스를 지원하는 단일 링크를 고려한 기본 모델은 네트워크 경로의 근사치로, 다른 교차 경로의 트래픽 변화를 무시합니다.
- 사용자 및 트래픽 구성: 유한한 사용자 집합 I = {1, 2, ..., I}가 서비스 클래스 집합 A = {1, 2, ..., A}를 제공하는 링크를 공유합니다. 각 사용자 i는 각 서비스 클래스 a에서 흐름 f_i^a ≥ 0을 선택할 수 있습니다. 사용자 i의 총 요구량은 f_i = ∑_{a ∈ A} f_i^a입니다. 클래스 a의 총 흐름은 f_a = ∑_{i ∈ I} f_i^a입니다. 사용자 흐름 구성 f_i는 벡터 (f_i^1, ..., f_i^A)로, 모든 사용자의 흐름 구성 벡터는 f = (f_1, ..., f_I)입니다. 타당한 사용자 흐름 구성은 비음성 제약 조건을 만족해야 합니다.
- 용량 분배: 네트워크 관리자는 일정한 용량 C를 서비스 클래스 간에 분배해야 합니다. 고객 수와 선호도를 사전에 예측할 수 없기 때문에 정적 분배는 불가능합니다. 관리자는 주기적으로 클래스 성능을 측정한 후, 사용자 라우팅 결정보다 느린 시간 척도로 현재 용량 분배를 수정합니다. 클래스 a에 할당된 용량은 c_a이며, 관리자의 용량 분배 벡터는 c = (c_1, ..., c_A)입니다. 타당한 분배는 비음성 제약 조건과 총 용량 제약 조건(∑_{a ∈ A} c_a = C)을 만족해야 합니다.
- 가격 설정: 각 서비스 클래스 a에는 일정한 단위 흐름 가격 p_a가 있습니다. 사용자 i의 네트워크 사용 비용은 ∑_{a ∈ A} f_i^a p_a입니다. 가격은 간접적인 접근 제어 수단으로, 더 나은 서비스 클래스가 빠져나가는 것을 방지합니다. 본문에서는 가격이 정적(또는 시간 척도가 느림)이라고 가정하며, 가격 설정 문제는 향후 연구로 남깁니다.
사용자 및 관리자 비용 함수
사용자의 성능 측정은 자체 비용 함수로 지정되며, 모두 이 비용 함수를 최소화하려 합니다.
- 사용자 비용 함수: 사용자의 유용성 함수 U_i(f_i)는 총 흐름 f_i의 유용성을 측정합니다. U_i는 증가, 유계, 오목, 연속 미분 가능이라고 가정합니다. 사용자 i의 총 비용 J_i(f, c)는 지연 비용, 네트워크 사용 가격에서 유용성을 뺀 값으로, 다음 식으로 정의됩니다: $$J_i(f, c) = \beta_i \sum_{a = 1}^{A} f_i^a D_a(f_a, c_a) + \sum_{a = 1}^{A} f_i^a p_a - U_i(f_i)$$ 여기서 β_i > 0은 사용자 i의 지연 민감도, D_a(f_a, c_a)는 M/M/1 지연 함수입니다: $$D_a(f_a, c_a) = \begin{cases} \frac{1}{c_a - f_a} & f_a < c_a \\ \infty & \text{기타} \end{cases}$$
- 관리자 비용 함수: 관리자는 서비스 클래스의 평균 지연 간 특정 비율을 적용하려 합니다. 클래스 1의 지연을 기준으로, 비율은 벡터 ρ = (ρ_2, ..., ρ_A)로 설명되며, ρ_1 = 1입니다. 관리자는 지연 D_1, ..., D_A가 다음 관계를 만족하도록 합니다: $$D_a(f_a, c_a) = \rho_a D_1(f_1, c_1)$$ 이 관계는 고정 비율 목표로 불립니다. 관리자의 비용 함수는 다음과 같이 정의됩니다: $$J_M(f, c) = \begin{cases} 0 & \text{고정 비율 목표 충족 시} \\ \infty & \text{기타} \end{cases}$$ 다른 고려 사항으로는 지연 함수의 가중 합 최소화가 있습니다: $$\overline{J}_M(f, c) = \sum_{a \in A} w_a D_a(f_a, c_a)$$ 여기서 w_a > 0입니다.
사용자와 관리자의 상호작용은 사용자-관리자 게임으로 불립니다. 이 게임의 나시 균형점(NEP)은 타당한 시스템 구성 (f̃, c̃)으로, 다음 조건을 만족합니다: $$J_M(f̃, c̃) = \min_{c \in \Gamma} J_M(f̃, c)$$ $$J_i(f̃_i, f̃_{-i}, c̃) = \min_{f_i \in F_i} J_i(f_i, f̃_{-i}, c̃) \quad \forall i \in I$$ 여기서 f̃_{-i}는 제i 사용자를 제외한 모든 사용자의 흐름 구성입니다.
다음은 단일 링크 모델의 프로세스 다이어그램입니다:
graph TD;
A[사용자] --> B[흐름 구성 f_i 선택];
B --> C[총 요구량 f_i 계산];
D[관리자] --> E[용량 c 분배];
F[흐름 f_a = f_i^a 합] --> G[지연 D_a 계산];
G --> H[사용자 비용 J_i 계산];
G --> I[관리자 비용 J_M 계산];
H --> J{NEP 도달?};
I --> J;
J -- 예 --> K[균형 도달];
J -- 아니오 --> B;용량 분배 및 균형 분석
이 섹션에서는 균형점을 분석하고 비율 목표를 달성하는 용량 분배 전략을 제시합니다.
- 최적 반응 용량 분배: 어떤 고정된 흐름 구성 (f_1, ..., f_A)과 기대 비율 벡터 ρ가 주어졌을 때, ∑_{a ∈ A} f_a < C이면 고정 비율 목표를 만족하는 유일한 용량 분배 c ∈ Γ가 존재합니다. 이 분배는 다음 식으로 주어집니다: $$c_a - f_a = (C - \sum_{\alpha ∈ A} f_\alpha) \frac{\rho^{-1}_a}{\sum_{\alpha ∈ A} \rho^{-1}_\alpha}$$ 이 결과는 관리자가 현재 네트워크 트래픽을 측정하여 고정 비율 목표를 충족하는 최적 반응 분배를 명확히 계산할 수 있음을 보여줍니다.
- 균형점 존재성 및 유일성: 각 지연 비율 벡터 ρ에 대해 유일한 나시 균형점이 존재합니다. 이 NEP는 관리자와 사용자 모두에게 유한한 비용을 가지며, 관리자의 비율 목표를 충족합니다. 증명은 다음 4개의 보조 정리를 기반으로 합니다:
- 보조 정리 1: 각 지연 비율 벡터 ρ에 대해 NEP가 존재합니다. 각 NEP에서 사용자와 관리자의 비용은 유한하며, 비율 목표가 충족됩니다.
- 보조 정리 2: NEP에서 클래스 지연 D_1, ..., D_A가 주어졌을 때, 균형 시 각 사용자 i와 서비스 클래스 a에 대해 다음 방정식이 성립합니다: $$\beta_i (D_a + f_i^a D_a^2) + p_a = U_i’(f_i) \quad \text{if } f_i^a > 0$$ $$\beta_i D_a + p_a \geq U_i’(f_i) \quad \text{if } f_i^a = 0$$
- 보조 정리 3: 주어진 클래스 지연 D_1, ..., D_A를 가진 NEP에 대해, 해당 균형 흐름 f_i^a는 유일하게 결정됩니다.
- 보조 정리 4: 두 나시 균형점 (f, c)과 (f̃, c̃)을 고려합니다. 각 a ∈ A에 대해 D_a(f_a) = D_a(f̃_a)입니다.
- 고정 비율 목표와 가중 합 목표의 동등성: 사용자-관리자 게임에서 J_M을 J̄_M으로 대체하는 유사한 게임을 고려합니다. 매개변수 w_a = 1/ρ_a² (a ∈ A)가 만족되면, 두 게임은 동등하며, (유일한) 균형점이 겹칩니다.
용량 분배 및 균형 분석의 단계는 다음과 같습니다:
- 정리 1을 사용하여 흐름 구성과 비율 벡터에 대한 최적 반응 용량 분배 계산.
- 보조 정리 1-4 조건을 확인하여 균형점 존재성 및 유일성 확인.
- 조건을 만족하면 나시 균형 도달; 아니면 흐름 구성과 용량 분배 조정 후 단계 1과 2 반복.
이 방법을 통해 차등 서비스 네트워크에서 비율 QoS를 실현하고, 다양한 서비스 클래스의 상대적 혼잡도를 효과적으로 제어할 수 있습니다. 이 방법은 유연성, 반응성, 이질적 사용자 환경에서 실행 가능하며, 나시 균형 계산을 위한 효과적인 알고리즘을 제공합니다. 그러나 관리자 시점에서, 사용자의 선호도를 완전히 알고 있어야 하므로, 이는 항상 가능하지 않습니다. 따라서 최적 반응 매핑을 활용한 적응형 용량 분배 방식이 더 실제적일 수 있으며, 이는 향후 연구의 중요한 방향입니다.
고정 비율 목표와 가중 합 목표의 연관성 및 알고리즘 의미
앞서 언급했듯이, 고정 비율 목표와 가중 합 목표는 특정 매개변수 조건에서 동등합니다. 매개변수 w_a = 1/ρ_a² (a ∈ A)가 만족되면, J_M을 비용 함수로 사용하는 사용자-관리자 게임과 J̄_M을 비용 함수로 사용하는 게임의 유일한 균형점이 겹칩니다. 이 결론은 알고리즘적 의미가 크며, J̄_M은 볼록하고 연속적인 함수입니다. 이를 기반으로, 관리자는 기울기 기반 알고리즘과 같은 반복 알고리즘을 사용하여 이 비용 함수를 최소화하고, 최종적으로 원하는 고정 비율 균형에 도달할 수 있습니다. 반복 알고리즘의 대략적인 단계는 다음과 같습니다:
- 용량 분배 c와 흐름 구성 f 초기화.
- 현재 J̄_M(f, c) 및 기울기 계산.
- 기울기 정보를 기반으로 용량 분배 c 업데이트.
- 사용자가 새로운 용량 분배에 따라 흐름 구성 f 조정.
- 단계 2-4 반복, J̄_M(f, c)가 최소값에 수렴할 때까지.
구체적인 알고리즘 설계 및 구현은 본문 범위를 벗어납니다.
나시 균형점 계산
나시 균형점(NEP) 계산은 비율 QoS 실현의 핵심입니다. 앞서 사용자 흐름의 유일성은 엄격한 볼록 최적화 문제로 결정됨을 증명했습니다. NEP 계산 시 유일한 미지수는 D_1입니다. D_1 값은 반복 검색을 통해 계산할 수 있으며, 다음 단계로 수행됩니다:
- D_1의 초기 추정값 설정.
- 최적 반응 공식 $c_a - f_a = (C - \sum_{\alpha ∈ A} f_\alpha) \frac{\rho^{-1}_a}{\sum_{\alpha ∈ A} \rho^{-1}_\alpha}$을 사용하여 용량 분배 c 계산.
- 최적화 문제 $\begin{cases} \min \sum_{a = 1}^{A} \frac{1}{2\beta_i D_a^2} f_i^a + f_i^a(\beta_i D_a + p_a) - U_i(\sum_{a} f_i^a) \\ \text{s.t. } f_i^a \geq 0 \end{cases}$ 해결하여 사용자 흐름 구성 f 얻기.
- 총 흐름 $\sum_{a} f_a$ 계산.
- 최적 반응 공식과 최적화 문제 해로 얻은 총 흐름 비교. 두 값이 허용 범위 내에 있으면 적절한 D_1 값 찾음; 아니면 D_1 값 조정 후 단계 2-4 반복.
더 세부적인 검색 방법은 관련 자료 참조.
일반 네트워크 확장
위 결과를 일반 네트워크 토포로 확장하는 것은 유의미합니다. 최신 연구에서 고정(유연) 사용자 수요 모델을 확장했습니다. 주요 특징은 다음과 같습니다:
- 사용자 경로: 각 사용자는 원천에서 목적지까지의 유일한 고정 경로를 가집니다.
- QoS 비율 목표 유지: QoS 비율 목표는 링크 레벨에서 유지되며, 분산 관리 방법을 사용하여 링크 레벨에서 용량 조정을 수행합니다. 위 두 특징이 충족되면, 각 사용자의 엔드-투-엔드 QoS 비율이 보장됩니다. 이 경우, 게임 프레임워크에서 각 링크에 네트워크 관리자가 있습니다. 용량 관리의 지역성으로 인해, 최적 반응 매핑 공식(정리 1)과 J_M 대체(정리 3)는 일반 네트워크 상황으로 쉽게 확장 가능하며, 균형점 존재성 증명도 동일합니다. 그러나 일반 네트워크 상황에서 균형점 유일성 문제는 더 복잡하며, 현재 열린 문제입니다.
일반 네트워크 확장의 프로세스 다이어그램은 다음과 같습니다:
graph TD;
A[초기 네트워크 상태] --> B[사용자 경로 결정];
B --> C[링크 레벨에서 QoS 비율 목표 설정];
C --> D[각 링크 관리자 용량 조정];
D --> E[링크 흐름 및 지연 계산];
E --> F[사용자 흐름 구성 조정];
F --> G{균형 도달?};
G -- 예 --> H[균형 도달];
G -- 아니오 --> D;결론 및 전망
본문에서 제시한 차등 서비스 네트워크의 QoS 공급 방법은 다양한 서비스 클래스의 상대적 혼잡도 유지에 초점을 맞춥니다. 분석 결과, 이 방법은 실행 가능하며, 특히 유연성, 반응성, 이질적 사용자 환경에서 QoS 목표 작업점의 존재성 및 유일성을 확보합니다. 또한 나시 균형 계산을 위한 효과적인 알고리즘을 제공합니다.
그러나 관리자 시점에서, 사용자의 선호도를 완전히 알고 있어야 하므로, 이는 실현하기 어렵습니다. 따라서 최적 반응 매핑을 활용한 적응형 용량 분배 방식이 더 실제적입니다. 이 방식은 각 서비스 클래스의 총 흐름을 측정하기만 하면 되므로, 운영이 용이하며, 분석은 향후 연구의 중요한 방향입니다.
또한 가격 설정 문제, 다른 비용 함수 및 QoS 측정 비율 QoS, 용량 분배 알고리즘 균형 역학 등 기타 연구 주제들도 있습니다. 이러한 연구는 차등 서비스 네트워크의 QoS 공급 방법을 더욱 완성하고, 네트워크 서비스 품질과 성능을 향상시키는 데 기여할 것입니다.
향후 연구 주제 목록은 다음과 같습니다:
- 적절한 서비스 클래스 가격 설정 문제, 더 나은 접근 제어 및 자원 분배를 위한 결정.
- 다른 비용 함수 및 QoS 측정 하에서 비율 QoS 실현 방법 탐구.
- 용량 분배 알고리즘 균형 역학 연구, 시스템이 균형 도달 과정에서의 행동 변화 이해.
지속적인 연구와 개선을 통해 차등 서비스 네트워크에서 더 효율적이고 공정한 QoS 공급을 실현할 수 있을 것입니다.