Ⅰ. 서 론

통신 및 정보처리 기술의 발달로 인해 인터넷을 통한 영상 정보의 교환양이 급증하고 있다. 영상 정 보는 영상 서버에서 다수의 시청자에게 전송되는 통신 형태를 보이기 때문에 효율적인 정보 전송을 위해 과거 IP 멀티케스트 기법이 제안되었다. 그러 나 인터넷에서 IP 멀티케스트 서비스를 지원하기 위해서는 망 내 모든 라우터 소프트웨어의 변경이 요구되므로 현재까지 인터넷에서 IP 멀티케스트는 보편적으로 지원되고 있지 않다. 이에 따라 영상 정 보 전송을 위한 또 다른 방안으로 인터넷을 하나의 가상적인 통신 선로로 생각하고 그 위에 영상 정보 수신자들로 구성된 오버레이 네트워크를 구성하는 어플리케이션 멀티케스트 기법이 제안되었다 [1]. 이와 같은 기법은 네트워크로부터 특정 서비스를 요청하지 않으며, 특정 미디어 서버가 모든 참여자 들을 지원하지 않고 각 세션 참여자가 미디어의 수 신자이자 송신자의 역할을 담당함으로써 매우 많은 사용자들이 동시에 서비스를 받을 수 있다는 장점 을 가지고 있다. 이로 인해 P2P 오버레이 멀티케스 트 네트워크를 통한 IPTV와 같은 P2P 스트리밍 서 비스는 급속하게 확산되고 있다 [2][3][4].

그러나 참여 피어의 용량이 상이하고 참여 피어 의 수가 많은 P2P 오버레이 멀티케스트 서비스 환 경은 효율적인 오버레이 네트워크 구성을 어렵게 만든다. 오버레이 네트워크는 참여 노드의 능력 측 면에서 매우 이질적이다. 즉, 피어들의 억세스 대역 폭은 수십 Kbps에서 수백 Mbps로 다양하며 CPU와 RAM, 하드 디스크와 같은 처리 능력과 저장 능력 이 매우 상이하며 참여 피어의 수가 증가할수록 이 와 같은 이질성은 증가한다. 또한 각 피어의 수신율 은 각 피어가 선택한 상위 노드 (부모 피어)의 전송 율에 의해 제한되기 때문에 스트리밍 세션 피어들 의 전체 수신율 증가를 위해서는 각 참여 피어들이 멀터케스트 소스를 루트로 하여 피어의 용량에 따 라 정렬되어야 한다. 그러나 일반적으로 P2P 네트 워크에는 상태 관리를 위한 단일 서버 (central agent)가 존재하지 않으므로 참여 노드들은 P2P 오 버레이 네트워크의 전체 토폴로지를 알 수 없다. 이 와 같은 문제 해결을 위해 [5]와 같이 오버레이 네 트워크 상태 관리를 위한 에이전트를 두는 방안이 제안되었으나 이와 같은 방법은 확장성과 실용성 문제를 야기시킨다. 따라서 다수의 참여 노드를 지 원할 수 있는 P2P 오버레이 네트워크 구성을 위해 서는 시그널링 부하가 적은 분산 기법이 요구된다.

오버레이 멀티케스트 트리 구성을 위한 분산 기 법들이 [6][7]에서 제안되었다. Chi 등은 max-min 공 정성을 보장하는 최적의 트리 구성 문제를 데이터 제약조건과 네트워크 제약조건을 고려한 최적화 문 제로 정의하였다 [6]. 또한 이와 같은 최적화 문제 는 NP-hard임을 증명한 후 트리 구성을 위한 휴리 스틱 (heuristic) 기법을 제안하고 있다. 그러나 이들 의 기법은 피어가 새롭게 오버레이 네트워크에 참 여하는 경우 기존 피어들의 송신율 변경으로 인해 트리를 재구성해야 하는 문제를 가진다. Kwang 등 은 피어의 용량을 통신 대역폭뿐만 아니라 저장 능 력 및 처리 능력까지 포함하는 포괄적인 개념을 제 시하였다 [7]. 이들은 피어 용량을 노드 용량 분포 ρ(n)으로 모델링한 후 피어의 용량과 피어가 지원 하는 자식 피어의 수를 고려하여 멀티케스트 트리 를 구성하는 프로토콜을 제안하였다. 그러나 이들 의 기법은 다수의 랜덤워크 (random walk)를 통해 트리를 구성하여 시그널링 부하가 크며 참여 피어 와 멀티케스트 소스와의 홉 수를 고려하지 않으므 로 오버레이 네트워크의 반지름이 커질 수 있다는 문제를 가진다.

이에 따라 본 논문에서는 다수의 이질적인 피어 들이 참여하는 P2P 오버레이 멀티케스트 네트워크 의 효율적 구성을 위한 프로토콜을 제안한다. 제안 프로토콜은 피어의 용량뿐만 아니라 참여 피어와 멀터케스트 소스 사이의 홉 수를 명시적으로 고려 한다. 또한 제안 기법은 지능적 계산 기법의 하나인 개미-군집 이론에 바탕을 두고 있어서 각 노드의 로컬 정보만을 이용하여 분산적으로 동작하며 동작 에 필요한 오버헤드도 작다.

본 논문은 다음과 같이 구성된다. 2장에서는 개 미-군집 이론을 소개하고 P2P 오버레이 네트워크 구성 기법에 관한 관련 연구를 분석한다. 3장에서 는 P2P 오버레이 멀티케스트 네트워크 구성을 위한 제안 기법을 기술한다. 4장에서는 모의실험을 통해 제안 기법의 타당성을 검증하고 5장에서 결론을 맺 는다.

Ⅱ. 관련연구

개미-군집 이론은 개미 집단이 먹이를 찾는 방식 에 착안하여 계산적 최적화 문제 (combinatorial optimization problem)의 해를 구하기 확률적 방법으 로 제안되었으며 [8] 유사 기법들과 함께 지능적 계 산법으로 분류된다 [9]. 개미들은 자신들이 지나온 경로에 페르몬을 남기고 먹이까지의 경로를 선택 할 때 경로에 남아있는 페르몬의 양을 이용한다. 이 와 같은 특성을 이용하여 개미-군집 이론은 최적화 문제를 가상의 개미들이 최적화 문제의 해를 찾아 가는 과정으로 모델링하여 인자가 많거나 비선형적 인 최적화 문제의 해를 빠르게 찾을 수 있는 방안 을 제시한다. (이론에 대한 자세한 사항은 [10]과 [11]를 참조하기 바란다.) 이와 같은 개미-군집 이론 은 다양한 곳에 응용되어 왔으며 최근에는 통신 네 트워크 설계 문제에도 적용되고 있다 [12]. 이들 연 구는 개미의 경로 탐색 과정과 통신 네트워크의 라 우팅 문제의 유사성을 이용했다. 그러나 본 논문에 서는 개미-군집 이론의 핵심 아이디어를 오버레이 네트워크 구성 문제에 적용한다.

초기 파일 공유에 주로 이용되던 P2P 오버레이 네트워크는 참여 노드들이 임의로 상대 노드를 선 택하여 구성되어져 왔으며 확장성을 위해 노드 용 량에 따라 슈퍼 노드가 대부분의 참여 관련 시그널 링을 담당하는 2 계층 구조로 발전되었다. P2P 트 래픽의 급증으로 인해 효율적인 P2P 네트워크 구성 방안은 망 사업자들 사이의 불필요한 P2P 트래픽 전달을 방지하기 위한 방향으로 제안되었다. 이들 은 하부 망 정보와 피어의 상태 정보를 특정 서버 에서 관리하고 이와 같은 정보를 이용하여 각 피어 의 부모 피어를 결정한다 [13]. 이들 기법들은 망 사업자들 사이의 불필요한 트래픽 교환을 방지할 수 있다. 그러나 망 정보 등은 망 사업자의 기밀 정 보이므로 타 사업자들과 공유되기 어렵고 단일 서 버가 모든 상태 정보를 관리하는 것은 대역폭과 처 리능력 측면에서 확장성이 결여되기 때문에 이들 기법을 실제로 적용하는 것은 실용적이지 못하다. 오버레이 네트워크 구축을 위한 분산 방법들이 [14][15][6][7]에서 제안되었다. 그러나 이들 기법들 은 실제 네트워크 환경과는 다르게 P2P 참여 노드 의 용량이 같다고 가정하거나, 새로운 피어가 참여 할 때 마다 트리 구성 목적 달성을 위해 트리를 재 구성해야 하는 문제를 발생시키며, 참여 피어의 일 부 특성만을 고려하기 때문에 구성된 오버레이 네 트워크의 효율이 낮아진다.

Ⅲ. 제안 기법

본 절에서는 개미-군집 이론에 기반을 둔 P2P 오 버레이 네트워크 구성 기법을 기술한다. 제안 기법 은 각 피어들이 피어의 용량과 피어와 멀터케스트 소스 사이의 거리를 이용하여 부모 피어를 확률적 으로 선택함으로써 효율적인 오버레이 네트워크 구 성을 목적으로 한다. 즉, 제안 기법은 참여 피어들 의 분산적 동작을 통해 용량이 높은 피어들이 멀터 케스트 소스에 보다 근접하게 되어 보다 용량이 작 은 피어들을 보다 많이 서비스함으로써 전체적인 오버레이 네트워크의 반지름을 줄이게 된다.

1. 오버레이 네트워크 모델

피어의 이질성은 [7]에서와 같이 노드 용량 분포 로 모델링 한다. 즉, 피어 i 의 용량 n_i는 피어의 억 세스 링크 대역폭과 기타 가용 자원들을 포함하며 노드 용량 확률 밀도 함수 ρ(n)를 따른다고 가정 한다. ρ(n)은 연속적일수도 있으며 불연속적일수 도 있다. [16]에서는 오버레이 네트워크에 참여하는 노드들의 분포는 소수의 대용량 노드들과 다수의 소용량 노드들로 구성된다는 P2P 네트워크의 측정 연구 결과에 따라 다음과 같은 불연속적인 ρ(n)을 제안하였다.

[7]에서는 식 (1)과 같은 불연속적인 ρ(n)이외에 연속 확률 밀도 함수로서 지수법칙을 따르는 ρ(n) 을 다음과 같이 제안하였다.

식 (2)의 d는 정규화 상수를 나타낸다. 식 (2)에 비해 식 (1)에 따라 발생되는 대용량 피어의 수는 작 지만 소용량 피어에 비해 대용량 피어의 용량은 상 대적으로 크게 된다. 따라서 본 논문의 모의실험에서 는 식 (1), 식 (2) 두가지 분포를 모두 이용하며 향후 식 (1)의 ρ(n)이 적용된 경우를 D_ρ 로 d = 1000인 식 (2)의 ρ(n)이 적용된 경우를 C_ρ 로 표기한다.

현재 인터넷 백본 링크는 대부분 오버프로비져 닝 (overprovision) 되어 있으므로 [15][17] 본 논문에 서는 혼잡은 각 피어의 억세스 링크에서만 발생 가 능하다고 가정한다 [7][15]. 또한 본 논문에서는 기 존 연구들과 마찬가지로 인터넷의 종단간 경로에 해당되는 P2P 논리 링크 사이의 상관관계 (correlation)을 고려하지 않는다 [18][19].

2. 오버레이 네트워크 구성 기법

오버레이 네트워크에 새롭게 참여하는 노드는 현재 가용 용량이 최고이고 멀터케스트 소스로부터 거리가 가장 짧은 노드를 선택하고자 한다. 즉, 시 간 t에서 오버레이 네트워크에 참여하고 있는 노드 의 집합을 N(t), 노드 i 의 용량을 n_i, 노드 i 가 지 원중인 자식 피어의 수를 k_i, 멀터케스트 소스와 노 드 i와의 거리를 h_i 홉으로 표기하면 새롭게 참여 하는 피어의 부모 노드는 다음과 같이 결정된다.

그러나 식 (3)의 해를 구하기 위해서는 트래커 (tracker)와 같은 부트스트랩 (bootstrap) 서버가 각 노드의 상태 정보{n_i,k_i,h_i} 관리해야한다. 하지 만 P2P 오버레이 네트워크와 같이 피어의 용량이나 지원하는 자식 피어 수가 가변적인 환경에서 부트 스트랩 서버가 다수의 피어 상태를 관리해야하는 중앙집중적 네트워크 구성 방식은 매우 많은 시그 널링 오버헤드가 야기되고 P2P 네트워크의 기본 설 계 원칙에도 부합하지 않으므로 식 (3)의 구현은 확 장성이 결여되어 실용적이지 않다.

이에 따라 본 논문에서는 다음과 같은 분산 오버 레이 네트워크 구성 기법을 제안한다. 오버레이 네 트워크에 새롭게 참여하는 노드 j 는 부트 스트랩 서버를 통해 N(t) 중에서 임의로 선택된 m개의 참여 노드 식별자를 전달 받는다. 새롭게 참여하는 노드 j 는 이들의 상태 정보를 알지 못하므로 노드 j 가 네트워크 참여 의사를 전달할 수 있는 방법은 다음 두 가지가 있을 수 있다. 첫 번째 방법은 m개 의 노드 중 임의로 한 노드를 선택하여 JOIN 요청 메시지를 송신하고 이 후부터 참여 노드들의 상태 정보에 따라 확률적으로 부모 노드를 선택하는 것 이다. 두 번째 방법은 노드 j 가 m개 노드에게 상 태 정보를 요청한 후 이에따라 JOIN 요청 메시지를 전송할 노드를 확률적으로 선택하는 것이다. 상태 정보 요청 메시지에 의해 시그널링 오버헤드가 증 가되지만 상태정보 요청 과정은 오버레이 네트워크 참여 노드들 사이에 이루어지므로 부트스트랩 서버 의 부하를 증가시키지 않는다. 또한 m의 수가 작 을 경우 상태 요청 과정을 위해 각 피어가 추가적 으로 처리하는 오버헤드는 수용 가능하므로 본 논 문에서는 두 번째 과정을 채택한다.

즉, τ_i = n_i/k_i, η_i = 1/h_i로 표기하고 N_m 을 수 신 받은 m개 피어의 집합으로 표기하면 개미-군집 이론에 따라 노드 j 가 노드 i 에게 JOIN 요청 메시 지를 전송할 확률은 다음과 같이 결정된다.

α 와 β 는 각각 피어의 페르몬 양 τ_i와 노드 i 의 링크 비용 η_i에 대한 가중치 파라메터로 피어를 선 택할 때 노드의 용량에 가중치를 부여할 것인지 멀 티케스트 소스와 노드 사이의 거리에 가중치를 부 여할 것인지를 결정한다.

P2P 시스템에서 N(t)에 속한 각 노드들은 m개 의 이웃 노드와 주기적 메시지 교환을 통해 이들의 상태 정보를 유지하고 있다. 따라서 새로이 참여하 는 노드 j 로부터 JOIN 요청 메시지를 수신한 노드 i 는 자신의 이웃 노드들의 상태정보와 식 (4)를 이 용하여 자신이 JOIN 요청 메시지를 전달할 노드를 확률적으로 결정하며 이와 같은 과정이 반복된다. 위와 같은 과정의 반복 횟수를 제한하기 위해 새롭 게 참여하는 노드 j 는 JOIN 요청 메시지에 TTL 값 을 설정하며 이 후의 노드들은 JOIN 요청 메시지를 전달할 때 마다 TTL 값을 하나씩 감소시킨다. 노드 k에서 TTL=0이 되면 노드 k는 더 이상 JOIN 요청 을 전달하지 않고 자신이 새롭게 부모 노드로 선택 되었다는 것을 노드 j 에게 통보한다. 즉, JOIN 요 청 메시지는 개미-군집 이론에서 가상 개미의 역할 을 수행하며 동적으로 변화하는 노드의 용량은 링 크의 페르몬 양을 나타낸다. 오버레이 네트워크에 참여중인 노드가 멀티케스트 세션을 이탈하는 경우 이탈 노드의 자식 피어들은 위와 동일한 참여 과정 을 통해 새로운 부모 피어를 선택한다.

Ⅳ. 실험 결과 및 분석

본 절에서는 모의실험을 통해 본 논문에서 제안 한 P2P 오버레이 네트워크 구성 방안의 타당성을 검증한다. 모의실험 초기에 한 개의 멀터케스트 소 스 노드와 m=10개의 피어 노드로 오버레이 네트 워크를 임의로 구성한다. 이후 노드들은 ρ(n)에 따 라 용량을 할당받고 제안 기법에 따라 오버레이 네 N 으로 안정 화 된 후 오버레이 네트워크에 참여 중인 피어 노 드를 대상으로 제안 기법의 성능을 평가하였다. 제 안 기법의 성능 검증을 위해 환경 변수인 참여 노 드의 수와 참여 노드의 ρ(n) 및 TTL을 변경 하면 서 제안 기법의 성능을 평가하였다. 특히, 실시간 P2P 비디오 세션과 같이 다수의 참여자가 동시에 참여하는 환경을 고려하여 참여 노드의 수를 1,000 에서 20,000 사이에 변화시키면서 제안 기법의 확 장성을 평가하였다. (이를 위해 모든 결과 그림의 x 축을 참여 노드의 수로 표기하여 도시하였다.) P2P 오버레이 멀티케스트 방식은 참여 피어들의 데이터 릴레이를 통해 멀터케스트 소스로부터 다수의 피어 에게 동일 정보를 전송한다. 따라서 멀터케스트 소 스와 피어 사이의 홉 수가 작아질수록 멀터케스트 소스에서 전송된 데이터가 피어에게 도달하는 종단 간 지연 시간과 지터가 줄어든다. 또한 P2P 오버레 이 네트워크가 특정 인센티브 메커니즘이 없어도 많은 피어들을 수용하기 위해서는 피어의 용량이 커질수록 이들이 지원하는 자식 피어들의 수가 많 아져야 한다 [20]. 따라서 성능 평가 인자로 멀티케 스트 서버와 피어 노드 사이의 홉 수 및 각 피어 노 드가 지원하는 자식 피어 노드의 수를 선정하였다.

그림 1과 그림 2에 제안 기법에 의해 구성된 오 버레이 네트워크의 홉 수를 도시하였다. 그림에서 멀터케스트 소스 노드와 참여 노드 사이의 최대 홉 수를 max로 95%의 홉 수를 95% 로 표기하였다. 멀터케스트 소스 노드와 참여 노드 사이의 95%의 홉 수가 a라는 것은 N 개의 참여 노드 중 멀터케스 트 소스와의 거리가 a 홉 이하인 노드의 수가 95% 가 된다는 것을 의미한다. 그림에서 보는 바와 같이 참여노드의 수에 따라 홉 수는 증가하며, TTL이 커 질수록 멀터케스트 소스와 피어 노드 사이의 홉 수 는 감소한다. TTL=1인 경우 새롭게 오버레이 네트 워크에 참여하는 노드는 현재 참여 중인 N 개의 노 드 중 m개 노드의 상태 정보에 따라 부모 피어를 선택한다. 반면에 TT=5인 경우 새롭게 참여하는 노 드는 최대 m⁵ 개의 노드들 중에서 홉 수와 용량이 최적인 노드를 확률적으로 선택하게 된다. 따라서 TTL이 증가할수록 멀터케스트 소스 노드와의 홉 수가 작은 노드를 부모 노드로 선택할 확률이 높아 지고 이로 인해 오버레이 네트워크의 크기가 줄어 든다.

<그림 3>과 <그림 4>는 각 피어가 지원하는 자 식 노드의 수의 최대값과 95%값을 보여준다. 자식 노드 수의 95%의 값이 b라는 의미는 N 개의 피어 중 b개 이하의 자식 노드를 지원하는 피어들의 수 가 95%라는 것을 의미한다. 오버레이 네트워크에 참여하는 노드의 수가 증가할수록 각 노드가 지원 하는 자식 노드의 수는 증가한다. TTL이 증가할수 록 참여 노드들은 제안 기법에 의해 용량이 크고 멀터케스트 소스와 홉 수가 작은 노드를 선택할 확 률이 커지므로 자식 노드의 수는 TTL에 따라 증가 한다. 멀티케스트 소스와 피어 사이의 홉 수에서와 는 달리 지원하는 자식 노드의 수는 동일 조건에서 ρ(n)이 연속적인 경우보다 불연속적인 경우 많다. ρ(n)이 연속적인 경우 지수법칙에 의해 용량이 1 에서 1,000인 노드들이 비슷하게 발생되는 반면 ρ(n)이 불연속적인 경우 식 (1)에 의해 노드 용량 에 따른 노드의 수가 매우 다르게 발생된다. 따라서 0.1%에 해당하는 용량 10,000인 노드가 다수의 저 용량 노드들을 지원하기 때문에 노드 당 지원하는 피어의 수가 증가하게 된다.

<그림 5>와 <그림 6>은 TTL=3인 경우 참여 노 드 수와 제안기법의 파라메터인 α , β 에 따른 95% 홉 수와 95% 자식 노드 수의 변화를 보여준다. α > β 인 경우 부모 노드 선택 과정에서 홉 수 보 다는 노드의 용량에 보다 높은 가중치가 부여되므 로 ρ(n)의 종류와 무관하게 β/α 가 증가할수록 멀 티케스트 소스와 피어 사이의 홉 수가 증가한다. 반 면에 α > β 일수록 식 (4)에서 p_ji는 α 에 의해 영 향을 많이 받기 때문에 α = 2, β = 1인 경우가 그 이외의 경우에 비해 각 피어 노드가 지원하는 자식 노드의 수가 가장 많다. 그러나 개미-군집 이론의 다른 연구들 [10]처럼 β/α 값이 결과에 미치는 영 향은 크지 않았다.

Ⅴ. 결 론

본 논문에서는 개미-군집 이론을 이용하여 용량이 상이한 피어들이 P2P 오버레이 네트워크를 구성할 때 오버레이 네트워크의 크기와 서비스 용량 측면에 서 효율적인 오버레이 네트워크 구축 기법을 제안하 고 모의실험을 통해 그 타당성을 검증하였다. P2P 오 버레이 네트워크에 참여하는 노드는 대역폭, 처리 능 력 및 저장 용량 등이 상이하다. 따라서 오버레이 네 트워크는 참여 노드의 용량에 따라 지원하는 자식 노드의 수가 비례하게 구성되어야 한다. 또한 멀터케 스트 소스와의 홉 수가 증가 할수록 종단간 전송 지 연과 지터가 증가하므로 참여 노드와 멀터케스트 서 버 사이의 홉 수가 적게 설정되어야 한다. 또한 단일 서버가 오버레이 참여 노드의 상태 정보를 관리하여 새로운 참여 노드의 부모 노드를 설정하는 것은 확 장성 문제로 인해 실용적이지 않다. 이에 따라 제안 기법에서는 개미-군집 이론을 이용하여 참여 노드의 용량과 참여 노드와 멀터케스트 서버 사이의 홉 수 를 모두 고려한 오버레이 네트워크 구축 방안을 제 안하였다. 제안 기법은 각 노드의 로컬 정보만을 이 용하여 분산적으로 참여 노드가 부모 노드를 선택하 므로 확장성이 우수하다. 오버레이 네트워크 구성 노 드가 수천개에서 수만개인 환경에서의 모의실험을 통해 제안 기법은 다수의 노드가 참여하더라도 소수 의 용량이 큰 노드가 다수의 용량이 작은 노드를 지 원함으로써 멀터케스트 소스와 참여 피어 사이의 거 리가 작게 오버레이 네트워크를 구축할 수 있다는 것을 정량적으로 검증하였다.