Ⅰ. 서 론

과거와는 달리 현재의 네트워크는 다수의 서비스 를 동일 네트워크를 통해 제공하는 멀티서비스 네 트워크로 진화하고 있다. 단일 네트워크에서 멀티 서비스를 제공하기 위해서는 우선 응용 서비스의 품질 요구 사항에 따라 요구 사항이 비슷한 응용 서비스들을 모아 서비스 클래스로 구분하고 네트워 크 내에서는 각 서비스 클래스가 요구하는 품질 보 장을 위해 클래스 별 차등 처리가 필요하다. 모든 클래스는 노드의 자원인 대역폭을 공유하며 클래스 의 서비스 품질은 클래스의 트래픽 입력율과 클래 스에 할당되는 대역폭에 의해 결정된다. 각 클래스 는 품질 요구 사항이 다르고 각 클래스의 트래픽 양은 시간에 따라 동적으로 변하기 때문에 클래스 사이에 공유 자원인 대역폭을 효과적이며 공정하게 할당하는 것은 대역폭 이용율 증대와 클래스별 서 비스 품질 보호를 위해 필요하다.

네트워크 노드의 대역폭 할당 문제를 해결하기 위해 최대-최소 공정성 (min-max fairness) 기법과 [1]와 비례적 공정성 (proportional fairness) [2] 기법 이 제안되어 왔다. 그러나 최대-최소 공정성 기법은 대역폭 이용측면에서 효율성이 떨어지고 비례적 공 정성 기법은 특정 커넥션에 보다 많은 자원을 할당 하며 기법 개발을 위해 사용한 커넥션의 유용성 (utility)에 대한 정량적인 정의가 어렵다는 문제를 가지고 있다.

따라서 대역폭 관리를 위해서는 효율성과 공정성 모두를 보장할 수 있는 자원 관리 기법이 필요하며 이를 위해 본 논문에서는 Nash 협상 게임 이론을 이용한다. Nash 협상 게임의 해 (NBS: Nash Bargaining Solution)는 자원의 효율적이며 공정한 할당을 위한 수학적 근거를 제공한다. 따라서 본 논문에서는 품 질 요구 사항이 다른 서비스 클래스들 사이의 대역 폭 할당 문제를 Nash 협상 게임으로 모델링 하고 이를 통해 서비스 클래스의 트래픽 입력율과 평균 시스템 대기 시간 측면에서의 서비스 품질 요구 사 항 및 클래스의 가중치를 고려한 효율적이며 공정 한 대역폭 관리 기법을 제안한다.

본 논문은 다음과 같이 구성된다. 2장에서는 Nash 협상 게임 이론을 소개하고 대역폭 할당 관련 연구를 분석한다. 3장에서는 NBS를 이용한 대역폭 할당 기법을 제안한다. 4장에서는 수치적 분석을 통해 제안 기법의 타당성을 검증하고 5장에서 결론 과 추후 연구 방향을 제시한다.

Ⅱ. 관련연구

1. 협상 게임 이론과 Nash 협상 해

Nash 는 협상 참여자들이 가능한 모든 협상 결과 들 중에서 공정한 협상 결과를 선택하는 문제를 연 구하였다. 협상의 결과에 따라 참여자들의 유용성 이 결정되며 유용성 값이 클수록 게임 결과에 대한 해당 참여자의 만족도가 크다는 것을 의미한다. 모 든 가능한 협상 결과의 집합을 협상 도메인 (Bargaining Domain) U, 참여자 i 가 협상에 참여하 기 위해 필요한 최소한의 유용성 값을 s_i, n명의 참여자 각각의 최소 유용성 값의 집합을 백터 s = { s 1 , ⋯ , s n } 로 표기하면 Nash 협상 게임의 목 적은 (s, U) 로 정의되는 게임에서 공정한 해를 찾 는 것으로 이와 같은 해를 NBS라고 한다.

NBS는 전략적 협상 방법 혹은 공리적 방법으로 구할 수 있다[3]. 전략적 협상 방법은 게임 참여자 들이 일련의 제안(offer)과 대안(counteroffer)을 반복 적으로 제시하여 평형 상태를 얻어내는 방법이다. 그러나 이와 같은 일련의 협상 과정에 많은 시간이 소요되기 때문에 전략적 협상 방법을 실시간 자원 할당 기법에 적용하기에는 적합하지 않다. 공리적 방법은 참여자들 사이의 협상과정을 고려하지 않고 모든 참여자들이 수용 가능한 공정성 특징을 가지 는 일단의 공리들에 의해 결정되는 해를 찾는 방법 이다[4]. 공리적 방법은 분쟁을 조절하는 중재자 (arbitrator)의 역할과 유사하기 때문에 중재 기법 (arbitration scheme)이라고 불린다. 대역폭 할당 문제 에서는 다수의 클래스를 지원하는 노드가 중재자의 역할을 하기 때문에 본 논문에서는 공리적 기법에 의한 NBS를 이용한다.

2. 자원 할당 관련 연구

일반적으로 대역폭 할당은 요구되는 대역폭보다 충분히 큰 양을 할당하는 방식(over- provisioning) 방식을 사용하고 있다. 이를 위해 최번시 (peak time) 때 요구되는 트래픽 클래스별 요구량을 통계 내어 이를 기반으로 대역폭을 할당한다. 하지만, 이 방식은 대역폭의 낭비가 심하고 트래픽 요구량이 통계치와 다르게 되면 손실이 발생하게 된다. [5]은 트래픽 예측을 통해 사용할 대역폭을 할당하는 기 술을 제안하였다. 이들이 제안한 방안은 트래픽 예 측의 정확성은 높지만 클래스별 분류를 하지 않고 전체 트래픽 양을 예측하여 대역폭을 할당하기 때 문에 클래스별 QoS 는 보장되지 않는다는 단점이 있다. [6]의 방안은 광대역 무선 네트워크 환경에서 다양한 트래픽 클래스를 고려한 방법으로 일정한 주기마다 동적으로 대역폭을 할당한다. 이때 할당 하는 양은 이전 시점의 트래픽양에 기초하므로 대 역폭의 부족 및 낭비가 커지는 단점을 지닌다. [7] 에서는 사업자 사이에 네트워크 자원을 공유하는 경우 무선 호의 특성을 이용하여 사업자 사이에 대 역폭을 할당하는 방안을 연구하였다. [8]에서는 트 래픽 클래스의 요구 양에 따라 클래스의 서비스 품 질 제공과 효율적인 대역폭 이용을 위한 호 수락 제어 기법을 제안하였다. 그러나 이들 방식은 호 단 위 혹은 응용 서비스 단위로 대역폭을 관리하기 때 문에 대용량 데이터 서비스 위주의 환경에는 적합 하지 않다는 단점을 갖는다. NBS를 이용한 대역폭 할당 기법이 [9]에서 제안되었다. 이들은 오목함수 로 정의되는 일반적인 유용성 함수가 대역폭 할당 에 미치는 영향을 고찰하였다. 그러나 멀티서비스 네트워크 환경에서 각 클래스 별 중요도에 따라 대 역폭 할당이 차별적으로 이루어져야 하지만 이들의 연구에서는 이와 같은 비대칭적 특성을 고려하지 않고 있다.

Ⅲ. 대역폭 할당 기법

본 논문에서는 대역폭 C 인 네트워크 노드가 n 개의 서비스 클래스 (player)를 제공하는 환경을 고 려한다. 대역폭 할당 측면에서 유용성은 할당된 대 역폭이 서비스 품질에 미치는 영향을 나타내며 할 당되는 대역폭이 클수록 유용성은 커진다. 3GPP나 ITU-T, IETF와 같은 표준화 기구에서는 서비스 클 래스를 데이터 손실율과 전송 지연을 이용하여 구 분하고 있으며 특히 음성, 영상과 같은 실시간 서비 스를 위해서는 각 노드별 지연 시간은 엄격하게 지 켜져야 한다 [10, 11]. 따라서 본 논문에서는 평균 시스템 대기 시간을 이용하여 클래스의 유용성을 나타낸다.

몇 가지 특별한 경우를 제외하고는 시스템 대기 시간 분포에 대한 일반적인 분석 모델은 존재하지 않는다는 것은 알려져 있는 사실이다. 그러나 본 논 문에서는 플로우별 대역폭 할당이 아닌 클래스별 대역폭 할당에 초점을 맞추고 있으며 자원의 효율 적 이용을 위해 NBS를 이용하여 시스템에서 지원 하는 각 클래스의 유용성의 곱을 최대화 하는 것을 목적으로 한다. 따라서 본 논문에서는 각 클래스별 로 동일 조건에서 동일한 유용성 함수를 사용하여 동일 자원양에 따른 각 클래스별 유용성의 차이를 정량적으로 나타낼 수 있는 유용성 함수를 선정한 다. 이에 따라 본 논문에서는 타 연구에서와 마찬가 지로 분석 모델을 얻기 위해 각 클래스의 트래픽 입력율을 평균 r_i인 포아손 분포를 따른다고 가정 한다[12]. 또한 각 클래스는 특성이 비슷한 응용 서 비스를 수용하므로 분석의 편의를 위해 각 클래스 별 패킷 크기는 동일하다고 가정한다 (예를 들어 음성 서비스를 제공하는 서비스 클래스의 경우 음 성 패킷의 크기는 하위 프로토콜들의 헤더 정보를 포함하더라도 64~100 Bytes이내 이다.). 이와 같은 조건에서 클래스 i 에 할당되는 대역폭을 x_i라고 하 면 클래스 i 의 시스템 대기 시간은 입력율 r_i 서비 스율 x_i인 M/D/1 모델로 근사화 가능하며 평균 시 스템 대기 시간은 다음과 같이 주어진다.

분석적 모델이 존재하지 않는 경우 실제 구현에서 는 시스템 대기 시간을 실측함으로써 동일한 방법으 로 제안 기법을 적용할 수 있다. 클래스 i 에 할당되 는 대역폭 x_i에 대한 유용성을 u_i로 표기하며 게임 이론의 적용을 위해 u_i는 x_i에 대해 증가 함수 이어 야 하므로 u_i는 다음과 같이 정의 할 수 있다.

또한 클래스는 최소한 보장 받고자하는 서비스 품질 요구 사항을 가지고 있다. 클래스 i 의 최대 평 균 시스템 대기 시간을 w_i,m 으로 표기하고 이때의 유용성을 s_i로 나타내며 r_i가 주어진 경우 w_i,m 을 만족하기 위해 필요한 최소 대역폭을 x_i,m 으로 표 기하면 주어진 대역폭 할당 문제는 Nash 협상 게임 에 의해 다음과 같이 정의 된다 [3].

멀티서비스 네트워크에서 각 노드는 클래스별로 가중치를 달리 두어 자원을 할당함으로써 클래스별 로 제공 서비스 품질을 조절한다. 즉, 각 노드는 클 래스들의 트래픽 입력율이 동일하더라도 가중치가 낮은 클래스보다 가중치가 높은 클래스에게 보다 많은 대역폭을 할당할 수 있어야 한다. 이를 위해 식 (3)의 NBS를 비대칭 (asymmetric) 환경으로 확장 하는 것이 필요하다. NBS에서 각 클래스가 가중치 (a_i) 만큼 복제 (clone) 클래스를 가진다고 생각하면 클래스별 가중치를 고려할 수 있으며 이를 이용한 대역폭 할당은 다음과 같이 이루어진다.

위와 같은 최적화 결과 각 클래스의 트래픽 입력 율과 보장해야 하는 평균 시스템 대기 시간 및 클 래스의 가중치에 따라 각 클래스에 할당되는 대역 폭은 다음과 같이 결정된다.

Ⅳ. 실험 결과 및 분석

본 절에서는 모의 실험을 통해 본 논문에서 제안 한 대역폭 공유 방안의 정확성과 타당성을 검증한 다. 실험을 위해 대기 시간을 50msec(w_i,m) 이하로 요구하는 클래스와 (class1) 대기 시간에 대한 특별 한 보장을 요구하지 않는 최선형 서비스 클래스를 (class2) 설정하였고 이들의 트래픽 입력율을 변화시 켜 가면서 링크 대역폭 100Mbps가 각 클래스에 할 당되는 양과 이로 인한 각 클래스별 대기 시간 변 화를 측정하였다. <그림 1>과 <그림 2>는 두 트래 픽 클래스의 가중치가 동일한 경우 (a₁ = a₂ = 1) class2의 트래픽 입력율이 증가될때 각 클래스에 할 당되는 대역폭과 이로 인한 시스템 대기 시간을 보 여준다. 그림에서 보는 바와 같이 수학적인 분석 결 과는 모의실험 결과와 부합한다.

제안 기법은 NBS를 이용하기 때문에 각 클래스 의 트래픽 입력율에 따라 공정하게 대역폭을 할당 한다 (<그림 1>). 따라서 두 클래스의 입력율이 동 일한 경우 (r₁ = r₂ ) 제안 기법은 링크 대역폭을 두 클래스 모두에게 동일하게 (C/2) 할당한다. class1 의 트래픽 입력율이 낮은 경우 적은 양의 대역폭을 class1에 할당하더라도 class1에 요구하는 평균 시스 템 대기 시간 50msec를 만족할 수 있다. 따라서 class2의 트래픽 입력율이 증가할수록 링크 대역폭 은 class2에 보다 많이 할당되며 이로 인해 동일한 시스템 대기 시간에 대해 수용 가능한 class2의 트 래픽 양은 증가된다. 예를 들어 링크 대역폭을 각 클래스에 1:1로 정적 분할한 경우 r₁ =10Mbps이면 class2의 트래픽 입력율이 44.5Mbps일때 class2의 평 균 대기 시간은 100msec가 된다. 그러나 제안 기법 을 적용한 경우 class2의 트래픽 입력율이 68.3Mbps 로 증가해도 평균 대기 시간은 100msec로 유지된 다. 즉, 제안 기법은 class1이 사용하지 않는 자원을 이용하여 동일한 성능에 대해 보다 많은 class2의 트래픽을 수용할 수 있다.

또한 제안 기법은 class2의 트래픽 입력율이 과도 하게 증가하는 경우에도 class1의 QoS 요구 사항을 보장한다. 즉, 제안 기법은 class1의 입력율에 따라 class1의 QoS 요구 사항을 만족할 수 있는 최소 대 역폭을 class1에 할당하기 때문에 (<그림 1>) class2 의 입력율이 매우 높은 경우 class2의 대기 시간은 급증하지만 class1의 평균 시스템 대기 시간은 요구 사항인 50msec로 보장된다 (<그림 2>).

동일 조건에서 class1의 가중치가 (a₁ ) class2의 가중치의 (a₂) 두배인 경우 클래스의 입력 부하와 서비스 품질 요구 사항에 따른 대역폭 할당 결과와 이로 인한 클래스의 시스템 대기 시간을 <그림 3> 과 <그림 4>에 도시하였다. 그림에서 보는 바와 같 이 두 클래스의 가중치를 달리 하는 경우에도 제안 기법은 노드의 대역폭을 두 클래스에게 공정하게 할당하여 class2의 과도한 입력율 증가에도 class1의 QoS를 보장한다. 또한 가중치가 증가된 class1의 경 우 가중치가 1인 경우보다 동일 조건에서 보다 많 은 양의 대역폭이 할당된다 (<그림 1>, <그림3>). 이로 인해 class2의 트래픽 입력율이 동일한 경우 class1이 주어진 QoS 조건인 최대 대기 시간 50msec 를 만족하면서 수용 가능한 트래픽 양이 증가한다 (<그림 4>). 예를 들어 class2의 트래픽 입력율이 (r₂ ) 30Mbps이고 a₁ =1인 경우 r₁ < 47Mbps가 되어 야만 class1의 평균 시스템 대기 시간이 50msec 이 하가 된다. 그러나 class1의 가중치가 class2의 가중 치의 2배가 되면 (a₁ =2) r₁ 이 47Mbps~53Mbps 사이 인 경우에도 평균 대기 시간을 50msec 이하로 보장 할 수 있다. 즉 동일 환경에서 class1의 가중치를 증 가시킴으로써 class1에 할당되는 대역폭이 증가되며 이로 인해 동일 QoS 조건을 만족하면서 class1에 수 용할 수 있는 트래픽 양이 증가된다.

Ⅴ. 결 론

본 논문에서는 Nash의 협상 게임 이론을 이용하 여 서비스 품질 요구 사항이 다른 트래픽 클래스 사이에 링크 대역폭을 공정하고 효율적으로 할당하 는 대역폭 관리 기법을 제안하였으며 정량적 분석 과 모의 실험을 통해 그 타당성을 검증하였다. 제안 기법은 각 트래픽 클래스의 트래픽 입력율과 평균 시스템 대기 시간을 고려하여 특정 서비스 품질을 요구하는 클래스의 서비스 품질 보장을 위한 대역 폭 이외의 유휴 대역폭을 타 클래스에 동적으로 할 당한다. 제안 기법은 이처럼 대역폭을 효율적으로 이용함으로써 링크가 수용할 수 있는 트래픽 양을 증가시킨다. 이와 동시에 제안 기법은 서비스 품질 을 요구하지 않는 트래픽 클래스의 입력율이 과도 하게 증가하더라도 특정 서비스 품질을 요구하는 트래픽 클래스에게 요청된 품질 만족을 위한 최소 한의 대역폭을 할당함으로써 타 클래스의 대역폭 독점을 방지하여 품질 요청이 있는 클래스의 서비 스 품질을 보장한다. 또한 제안 기법은 클래스의 가 중치에 따른 차별적인 대역폭 할당이 가능하다. 추 후 연구로는 실제 구현 측면에서 트래픽 모델이 분 석 모델의 가정을 따르지 않는 경우 시스템 대기 시간을 실측하고 그 결과를 본 논문에서 제안한 대 역폭 관리 기법에 적용하는 방안 마련이 요구된다.