신뢰적인멀티캐스트전송프로토콜을위한 Top-Down 기반의제어트리구축방안 611 신뢰적인멀티캐스트전송프로토콜을위한 Top-Down 기반의제어트리구축방안 (A Top-down based Control Tree Construction Mechanism for eliable Multicast Transport Protocols) 김은숙 고석주 강신각 최종원 (Eunsook Kim) (Seok Joo Koh) (Shin Gak Kang) (Jongwon Choe) 요약최선의전송 (Best Effort) 서비스를제공하는현재의 IP 멀티캐스트서비스의특성상신뢰전송을요구하는각종응용들의요구를만족시키기위해서는추가적인신뢰전송프로토콜이필요하다. 이러한요구에따라신뢰적인멀티캐스트전송프로토콜에대한연구가수행되고있는가운데, 계층적트리를구축하여신뢰성을보장하는노력이활발하게진행되고있다. 계층적트리기반의방식은높은확장성을보장하면서효율적으로신뢰성을보장하지만전송단계에서효율적인논리트리구축방안이제공되어야한다. 논리적인제어트리구축은수신자기반의상향식 (bottom-up) 방식이주로사용되어왔으나이방법은병렬적트리구성을통하여신속한트리구축을할수있다는장점이있지만제어트리상에루프 (loop) 가발생할수있다는단점과메시지부하가커지는단점이있다. 이에본논문은하향식 (top-down) 기반의제어트리구축방안을제안한다. 하향식방식은단계적인트리구축을통하여루프발생을방지할수있다. 또한성능평가를통하여메시지부하를줄일수있다는것을보였다. 본논문은응용의요구사항에맞추어상향식과하향식을선택적으로사용할것을제안한다. Abstract To meet the requirements of reliable service for various applications, a eliable Multicast Transport Protocol should be implemented over IP Multicast where currently best-effort service is provided. Among the current researches, hierarchical tree-based mechanism has been proposed and actively studied. This mechanism is known to provide high scalability as well as reliability, but needs an additional tree configuring mechanism for building an efficient logical tree in transport layer. Bottom-up approach has been used for creating such a tree. This method has benefits from parallel tree construction for receivers, while it has some drawbacks such that it does not guarantee a loop-free tree and brings heavy message overhead during tree creation process. Therefore, this paper proposes a top-down based mechanism for constructing a control tree, which can guarantee loop-freeness by step-wise mannered tree building. From experimental simulations, it shows that the proposed mechanism has less message overhead. It is recommended that the bottom-up and the proposed top-down will be selectively used in real networks, according to the requirements of the concerned multicast applications. 1. 서론중전송을이용하는인터넷응용이증가하면서 IP 멀티 인터넷방송, 다중화상회의, 소프트웨어분배등다 비회원 : 한국전자통신연구원표준연구센터연구원 eunah@etri.re.kr sjkoh@etri.re.kr sgkang@etri.re.kr 종신회원 : 숙명여자대학교전산학과교수 choejn@sookmyung.ac.kr 논문접수 : 2001년 2월 28일 심사완료 : 2001 년 9 월 6 일 캐스트서비스에대한요구가증가하고있다. 그러나현재의 IP 멀티캐스트 [1] 는 Best Effort 서비스를제공하기때문에원격강의, 공동문서작업등신뢰전송을요구하는각종응용들의요구를만족시키기위해서는추가적인신뢰전송프로토콜이필요하다. 이러한요구에따라신뢰전송멀티캐스트프로토콜에대한연구가수년간수행되어왔고 [2, 3] 1998년 4월부터 IETF의 MT-WG 을중심으로이분야의표준화연구가진행
612 정보과학회논문지 : 정보통신제 28 권제 4 호 (2001.12) 되고있다. IETF MT-WG에서는기존의연구들을종합하고새로운요구사항을검토하여현재신뢰전송프 식이확장성을보장할수있다는알려진사실을따라서수신자기반방식을채택한것인데, 전송계층트리는 로토콜에관한연구들을크게 LCT(Layered Coding 네트워크계층의멀티캐스트라우팅트리와달리송신 Transport)[4], NOM(Nack Oriented eliable 자와수신자간의상태정보교환이필수적인만큼송신 Multicast)[5], TACK(Tee-based ACK)[6, 7] 의 자초기화방식의트리구성이송신자에게추가적인오 세가지로분류하여다양한응용에맞는표준화프로토콜을설계하기위한노력을기울이고있다. 이중 TACK은전송단계에서계층적인제어트리를구축하여신뢰성을보장하는방법으로높은확장성을보장하면서효율적으로신뢰성을보장하는것으로잘알려져있다 [8]. 그러나이방법을사용하는프로토콜의효율성은전송단계에서구축되는논리제어트리의효율성에크게의존한다. 그러므로동적으로변화하는그룹수신자들에게확장성및신뢰성을보장하는서비스를제공하기위해서는효율적인논리제어트리구축방안을보장하는것이선행되어야한다. 제어트리를구축하는기존연구들은크게상향식 (bottom-up) 과하향식 (top-down) 으로분류할수있다. [9] 는하향식방식에대한연구를발표하였으나이방식에서는트리구조상의지역대표노드들의공지메시지 (advertisement) 가전체그룹으로멀티캐스트되는데따른메시지오버헤드가크다는단점이지적되었다. 이에따라 [10] 에서는상향식기반의제어트리구축방 버헤드를주지않는다. 본논문은이러한고려를바탕으로기존의하향식의공지메시지에제한적멀티캐스트를적용하고공지메시지의전송간격을효율적으로조정하여기존방식이갖는단점을해소하도록하였다. 실시한성능평가결과는하향식을기반으로설계된제안기법이기존의상향식기반방식과비교했을때메시지부하를줄일수있다는것을보였으며현저하게낮은레벨의트리를형성함으로써다단계의제어메시지처리에효율성을높일수있음을보였다. 그러나단계적트리구성의특성상병렬처리를하는상향식방식보다는트리구축시간이길어지는것을볼수있었다. 이에, 본논문은응용의요구사항에맞추어상향식방식과하향식방식을선택적으로사용할것을제안한다. 본논문의구성은다음과같다. 2장에서는관련연구를살펴보고, 3장에서제안된트리구축기법을소개하며, 4장에서제안기법에관한실험결과를보인다. 마지막으로 5장에서결론및향후과제를살펴본다. 안들을정리하여발표하였다. 발표되어진방법들은수신 자기반의멀티캐스트그룹운영방식을적용한것으로대표노드를찾아가는구체적인메카니즘은서로다르지만, 각수신자들이동시에자신과가까운서비스노드를 2. 관련연구 2장에서는신뢰적인멀티캐스트전송프로토콜의효율적인설계를위한연구방향으로계층트리를이용하 찾아가는간단한트리구축방안을제공하며그룹에참 는 트리 기반 ACK 프로토콜 (Tree-based ACK 여한수신자들에게병렬적트리구성을제공한다는공통점을가지고있다. 그러나상향식기반방식또한모든수신자들이자신의대표노드를구하기위하여보내는질의메시지 (queary) 로인하여수신자수가커질수록메시지부하가커지는단점이있다. 또한제어트리상에루프가발생할수있다는단점과서비스노드수와네트워크상태변화에민감하다는단점이있다 [11]. 이러한문제를해결하기위한방안으로본논문은기존의하향식방법을개선하고이에기반을둔새로운제어트리구축방안을제안한다. 본연구에서하향식에관심을갖게된것은알려진단점을해결한다면이방법이송신자와서비스노드들로부터단계적인트리구축을통하여루프발생을방지할수있으며네트워크의환경에투명한서비스를제공할수있다는장점이있기때문이다. 또한상향식방법은하위네트워크계층의멀 Protocol) 의개념및서비스수행방법에대하여간략하게살펴보고이방법을적용하기위하여계층트리를구축하는방법에대한관련연구를살펴보겠다. 2.1 트리기반 ACK 프로토콜트리기반 ACK 프로토콜메카니즘은전송계층상에논리적제어트리를구축하고하나의멀티캐스트그룹을계층적관계를갖는여러개의지역그룹으로나누어지역그룹단위로상태정보를관리한다. 그림 1에서보는것처럼송신자 (S) 가루트가되는제어트리를형성하고중간노드들중에 H(epair Head) 라는서비스노드가있어서자신의지역그룹수신자들 () 에게오류제어및 ACK 통합등의서비스를제공한다. 이때 H 노드는종단의호스트또는서비스사업자가보유한서버들이될수있는데제어트리형성전에그역할이명시되어야한다. 이과정은 SAP[12], SD[13] 등세 티캐스트라우팅트리를구성할때수신자기반의상향 션에관한규약에따라웹등을통해멀티캐스트세션
신뢰적인멀티캐스트전송프로토콜을위한 Top-Down 기반의제어트리구축방안 613 참여시에명시되어질수있는것으로본논문에서는다루지않는다. ACK S Multicast Data Transmission H H H 그림 1 Tree-based ACK 프로토콜의제어트리 제어트리형성이완료되면멀티캐스트송신자는데이타를전송한다. 이때데이타는멀티캐스트라우팅경로를따라전송되고상태정보는제어트리경로를따라전송된다. 각수신자는데이타수신상태와흐름및혼잡제어에대한정보를실은패킷을자신의 H에게전송한다. 각 H는수신한정보를바탕으로손실패킷의재전송을수행하며, 각수신자의상태정보를통합하여자신의상위노드로전송한다. 최종적으로송신자는자신과직접연결을맺은수신자들로부터받은통합된정보를종합하여흐름및혼잡제어를수행할수있다. 이러한오류및흐름제어에관한기능들외에그룹멤버쉽관리및유지에관한기능들또한제어트리를바탕으로수행된다. MTP-II[14], TAM[15] 등이이기법을기반으로프로토콜을설계하였다. 이들은패킷손실처리나늦은참여등네트워크의트래픽을유발하는오퍼레이션이지역적으로처리되기때문에높은확장성을보인다. 각프로토콜들은오류및혼잡제어를수행하는기능에서는대체적으로공통성을지니고있으나제어트리를구축하는방법에관한이슈들에서는차이점을보이고있다. 그러므로다음절에서이들이사용하는트리구축기법을중심으로관련연구를살펴보겠다. 2.2 제어트리구성방안 제어트리의구축은멀티캐스트세션광고, H(epair Head) 탐색, 최적의 H로의바인딩 (binding) 의순서로진행된다. 세션광고는웹등을통한 out-of-band 방식으로수행되며이때그룹수신자들은멀티캐스트주소와송신자주소및제어트리를구축하는데필요한정보들을얻고, 송신자가제어트리구축을알리면자신과가까운 H 탐색을통해제어트리구축에참여하게된다. 최적의 H 를선택한수신자는해당 H 에바인딩하고 각 H 역시자신의 H 또는송신자에게바인딩함으로써제어트리를구축한다. 이때 H 탐색과정을크게상향식과하향식으로나눌수있다. 현재알려진트리구성옵션들은주로상향식트리구성방법으로모든종단수신자들이병렬적으로 H가주변에있는지멀티캐스트질의를통해부모 H를찾으면서제어트리가종단에서부터상위로확장되어최상위루트노드인송신자에게연결되는방법을사용한다. 반면에하향식에서는 H들이자신의멤버를모집하기위하여그룹으로공지메시지를보냄으로써상위루트노드부터종단노드로트리가형성되어진다. 각방식은각각의장단점이있는데, 상향식은병렬적트리구성을통하여신속한트리구성을이룰수있다는장점이있는반면네트워크에서양방향멀티캐스트가지원된다는가정이있어야한다. 또한트리구성이완료되기전에도착하는데이타에대한오류회복은보장되지않는다. 반면하향식은단계적트리구성을통하여루프방지가보장된다는장점이있으며초기오류에대한재전송을보장할수있고단방향멀티캐스트로서비스를제공할수있다. 그러나단계적트리구성으로인하여여러단계의트리구성이필요한환경에서긴트리구성시간이필요하다는단점이있다. 또한두가지방법모두메시지부하가크다는단점이있다. 알려진연구중에서 [9] 는하향식방식에대한연구를발표하였으나이방식에서는트리구조상의지역대표노드들의공지메시지 (advertisement) 가전체그룹으로멀티캐스트되는데따른메시지오버헤드가크다는단점이지적되었다. 이에따라 [10] 에서는상향식기반의제어트리구축방안들을정리하여발표하였다. 이방법들은 H 탐색메커니즘에따라 POC(Point_Of Contact), GA(Generic outer Assist), 그리고 ES (Expanding ing Search) 방식으로나눌수있다. POC는제어트리구축을위해네트워크에분포된지정서버들을말한다. 각 H 노드들은자신의도메인내의 POC에자신을등록한다. 각수신자들은 POC에게현재도메인내의 H 정보를문의하고 POC는 H 리스트를전송해준다. 그러므로이방식은 POC 서버의전개상황에따라수신자들이적절한 H를탐색할수있는여부가결정된다. GA는라우터의기능을확장하여이것의지원을받아제어트리를구축한다. 각라우터가라우팅트리정보를모으고이들을하위스트림 (downstream) 의수신자들에게전송해주며, 상태정보에대한간단한처리를통해제어트리구축에참여한다. 이방법은하위계층
614 정보과학회논문지 : 정보통신제 28 권제 4 호 (2001.12) 의멀티캐스트라우팅트리와비교적일치하는제어트리를구축할수있다는장점이있지만확장된기능을갖춘라우터의전개가우선되어야한다는문제가있다. ES는각수신자들이멀티캐스트질의메시지를주고받으면서적절한 H를탐색한다. 각수신자들은 TTLscoping' 을사용하여자신의이웃으로멀티캐스트메시지를전송해서해당범위내에 H가있는지탐색한다. 이때 TTL(Time To Live) 값을 1부터차례로증가하면서멀티캐스트메시지를전송함으로써자신과가까운 H를찾게된다. 만일이메시지범위내에 H가있다면이메시지를받고이에응답한다. 이과정은 H를포함한모든수신자들이동시에수행하며질의에대한응답메시지를받거나 TTL값이 255에도달할때까지반복된다. POC나 GA가특정서버또는라우터의전개가선행되어야하고그전개상황에성능이크게좌우된다는특성이있기때문에본논문에서는상향식트리구축방안중 ES 방식을본논문에서제안하는방식의성능평가를위한모델로선정하였다. 3. 하향식기반의제어트리구축방안 앞에서살펴본 ES[16] 방식은 IP 헤더의 TTL정보를이용하여간단한제어트리구축메카니즘을제공한다. 그러나이방식은트리구축과정에서모든수신자가멀티캐스트질의를통하여트리구축에참여함으로써메시지오버헤드가크다는단점이있다. 또한일반수신자와 H가동시에트리구축에참여함으로써루프가발생할가능성을배제하지못한다는단점이있다 [11]. 그러므로본논문은단계적트리구축을통해루프발생을방지할수있는하향식트리구축방안을기반으로한새로운제어트리구축방안을제안한다. 1) 제어트리구축을위해송신자는제어트리구축을알리는메시지를데이타채널로멀티캐스트한다. 이메시지를수신한 H 노드들이송신자에게먼저바인딩 (binding) 한뒤자신의지역그룹으로제어트리초대메시지를전송하면이초대메시지를받은각일반수신자들이 H에바인딩하여제어트리를형성해나간다. ES와제안방식의제어트리형성과정에서사용하는메시지는표 1과같다. 상향식방식에서는표에나열된모든메시지가사용되며본논문에서제한한방식에서는 QUEY 메시지를제외한 BEACON, QUEY, 1) 편의상제안한방식을 하향식 이라고칭하고, 비교대상인기존연구를 상향식 이라고통칭하여서술하겠다. 표 1 상향식과하향식에서사용하는제어트리형성을위한메시지 메시지타입 From To 전송설명상향식하향식타입 BEACON S M 트리형성알림사용사용 QUEY H M ADVETISE H M 수신자들이 H 를찾기위해그룹으로보내는질의 H 의수신자의질의에대한응답 사용 사용안함 사용사용 BIND H U 바인드요청사용사용 ACCEPT or EJECT H U 바인드요청에대한응답 S: 송신자, : 수신자, M: Multicast, U: Unicast 사용 사용 ADVETISE, BIND, ACCEPT( 또는 EJECT) 메시지가사용된다. 각메시지이름은사용성격에따라붙여진이름이며구체적인프로토콜또는메카니즘별로서로다른이름으로불려질수있다. BEACON 메시지는송신자가모든수신자에게트리형성을알리고트리형성에대한기본적인정보를전달하기위하여사용된다. 이메시지는트리형성과정동안주기적으로전송된다. QUEY 메시지는일반수신자들이자신의 H를찾기위하여그룹내로멀티캐스트하는메시지인데, 하향식의단계적제어트리과정에서는이미제어트리의멤버가된 H들이수신자들에게 ADVETISE 메시지를전송하기때문에상향식에서사용되는 QUEY 메시지가불필요하다. ADVETISE 메시지는각 H가자신의제한된범위의그룹으로전송하는메시지이다. 이것은상향식에서는수신자의 QUEY 에대한응답으로사용되며하향식에서는 H가지역그룹수신자들에게자신의정보를전달하기위하여사용된다. BIND 메시지는 H와일반수신자들이자신의제어트리에바인드하기위하여송신자또는 On-Tree 노드에게참여요청을하는메시지이다. 마지막으로 ACCEPT 또는 EJECT 메시지는 H 노드들이자신에게참여요청을한수신자들에게응답하기위한메시지이다. 그림 2는본논문에서제안하는방식의트리형성을위하여송신자와 H 노드간, H 노드와일반수신자간의메시지교환과정을나타낸것이다. 이과정에따라제어트리가형성되는과정을자세히살펴보면다음과같다. (1) 송신자가멀티캐스트세션으로트리생성을알리는 BEACON 메시지를전송한다. (2) 이메시지를수신한 H 가송신자에게 BIND 메
신뢰적인멀티캐스트전송프로토콜을위한 Top-Down 기반의제어트리구축방안 615 BEACON S S BIND ACCEPT H H H H (or EJECT) ADVETISE BIND ACCEPT or EJECT 그림 3 제안방식의트리형성과정 이러한방법에서 ADVETISE 메시지의전송간격이 메시지부하에크게영향을주게된다. 제안한기법에서 Sender epair Head eceiver 는 T(AGT: Ack Generation Time) 을정의하여이메 그림 2 제어트리형성을위한메시지교환과정 시지로부터과도한트래픽이발생하지않도록한다. T(AGT) 는다음과같이정의하였으며, ADVETISE 뿐 시지를전송하고송신자는 ACCEPT 또는EJECT여부 아니라멀티캐스트데이타의 ACK 메시지전송을위하 에대해응답한다. 이때 BIND 허락여부는 MaxNum 여동시에쓰일수있는값으로정의하였다. Children' 및 MinNumH' 의두변수에의해서결정 된다. 이두변수는세션정보로기록되어송신자의 T(AGT) = max (1 second, AdvCnt AdvSize / BEACON 메시지에실려모든수신자에게전달된다. MaxAdvBW, AdvCnt / MaxNumChildren은지역그룹의최대수신자수를나 MaxPacketate) 타내며, MinNumH는지역그룹수신자들에포함된 여기서 AdvCnt는 ADVETISE 메시지의수를나타 최소 H 수를나타낸다. 내고, AdvSize는비트단위로계산된 ADVETISE 메 (3) On-tree 노드가된 H는자신의지역그룹으로 시지의크기를나타낸다. 이것은 UDP와 IP 헤더를포함 ADVETISE 메시지를전송하여자신의이웃에위치 한크기이다. MaxAdvBW 는최대가능한 ADVETISE 한 Non-Tree 노드들을초대한다. 만일송신자의트리 대역폭을나타낸다. 이것은응용에서데이타가전송되기 형성규칙 (MaxNumChildren과 MinNumH) 에위배 전과후에서로다르게값을제어할수있다. 이런방법 되어 EJECT 메시지를 받은 H 노드는 이미 으로데이타전송이시작된이후에는 ADVETISE 메 On-Tree 노드가된다른 H들의 ADVETISE 메시 시지의전송대역폭을적게변경시킬수있다. Max 지를기다린다. Packetate는데이타패킷의최대전송률을나타낸다. (4) On-Tree 노드가된 H들의 ADVETISE 메시 ADVETISE 메시지를 수신한 수신자들은 T(TI: 지를받은이웃의 Non-tree 노드들은자신에게전송되 Tree Invite) 시간동안이메시지를모아서최적의 H 는 ADVETISE 메시지에실린정보를모아자신에게 를계산하여바인딩을하게된다. 이때 T(TI) 는 가장가까운 H를선정한다. ADVETISE 메시지를 T(AGT) 를이용하여다음과같이정의한다. 통하여자신의부모 H 정보를얻은수신자들은해당 H로 BIND 메시지를전송한다. 이때부모노드선정 T(TI) = min(3 T(AGT), C seconds) 은구현시정해질수있으며, ES와같이 Hop Count 이때 C는상수로서최적의 H를평가하기위한최 또는 IP 주소를기준으로삼을수있다. 소시간을반영할수있도록정하는데, 멀티캐스트그룹 (5) 각 H는 MaxNumChildren' 과 MinNumH' 를 의규모에따라세션시작시값을부여할수있다. 기본 기준으로 ACCEPT 또는 EJECT를결정하여응답한다. 값은 60초로부여하여최소 60초내에 H 평가가종료 이과정은현재그룹에참여해있는모든노드가 되는것을보장한다. On-Tree 노드가되거나정해진타이머가만료될때까 설명한과정에서보이는바와같이제안기법은단계 지계속된다. 이런방법으로제어트리는그림 3과같은 적트리구성을통하여송신자와 H 노드들간의바인 모양으로형성되어진다. 딩이먼저이루어지고, On-Tree 노드가된 H들과일
616 정보과학회논문지 : 정보통신제 28 권제 4 호 (2001.12) 반수신자들간의바인딩이차례로이루어지기때문에손쉽게루프를방지할수있음을직관적으로보여준다. 또한, 모든수신자들이제어트리를참여하기위해서그룹으로멀티캐스트되는 QUEY 메시지가불필요해짐을알수있다. 그러나 QUEY 메시지가제거되었으나 ADVETISE 메시지가상향식과같이단발성이아니고주기적으로발생하게되므로하나의제어메시지가대역폭단위하나를차지한다고가정하여메시지부하의감소여부를살펴보면다음과같다. 측정을위하여제한된하나의지역그룹영역안의평균수신자수를 이라하고, 부모 H와하나의자식수신자와의평균홉거리를 d라놓는다. 또한 T(H) 를상향식방법에서 H를탐색하는데걸리는시간이라고정의한다. 이때상향식의경우 TTL값이 1씩증가할경우하나의수신자가평균 O(d) QUEY 메시지를그룹으로전송한다. 나머지 -1 개의수신자도같은수의메시지를전송하게되므로평균 O(d) 의 QUEY 메시지가전송된다. 이러한 QUEY 메시지에대하여 H가유니캐스트응답을보내야하므로 O() 의 ADVETISE 메시지가필요하므로 O(d) + O() O(d) 만큼의메시지가교환된다. 만일 d가무시할만큼작다면이것은 O() 로, 그렇지않다면 O( 2 ) 으로표시될수있다. 초당메시지수를측정한다면, O() / T(H) 또는 O( 2 ) / T(H) 가될것이며이것은두가지경우모두이것은수신자수에비례하여메시지부하가증가한다는것을나타낸다. 하향식의경우 H 탐색은 H의 ADVETISE 메시지로이루어지며메시지부하는이메시지의전송간격에비례할것이다. 만일주어진시간안에 n 번의메시지가전송된다면이방법의메시지부하는 O(n) 에따를것이다. 여기서하향식의경우상향식과같이양방향의교환이필요하지않으므로 H탐색은 1/2 T(H) 에이루어지고이로써초당교환되는메시지수는 1/2 O(n) / T(H) 로나타낼수있다. 이것의의미는메시지부하가수신자수의증가에비례하지않는다는것인데, 제안기법은정의한 T(AGT) 를통하여비교한상향방식모델보다적은메시지부하를나타낸다는것을실험결과에서보였다. 이결과는 4장에서서술된다. 비교평가를실시한시뮬레이션결과를설명한다. 시뮬레이션은 SMPL 라이브러리 [17] 를사용한 C 코드로실시하였다. 시뮬레이션은 100, 250, 500, 1000개의노드를통하여실시되었다. 각노드들은홉거리정보를가지고있으며 TTL 값을비교하여이값을기준으로 H 노드를선정하게된다. 그룹의범위는 TTL 64로지정한다. ES 방식은 TTL 값의증가치에따라메시지오버헤드가달라질수있으므로 QUEY 메시지의 TTL값을 1, 2, 5 단위로각각증가시킨다. MinNumH는 MaxNum Children의 10% 로정한다. 하나의 H가서비스하는지역노드수는최대 50으로제한한다. 또한지역그룹내의적절한 H 수를평가하기위해서노드 1000의환경에서전체 H의수를 50, 100, 150, 200, 250으로증가시켰다. 즉, 최대 H 수를전체노드수의 30% 까지할당시켜실험한것인데, 만일 H 수가 50% 가된다면한 H가노드 1개를서비스하는모양이되기때문에이것은트리기반의서비스를사용하는의의를상실하게되므로실험에서는이를 30% 까지증가시킨다. 제안한기법의성능평가를위해서사용된메트릭스는다음과같다. -트리형성과정에서교환되는메시지수 : 메시지오버헤드를측정하기위하여 BEACON, QUEY, ADVETISE, BIND, ACCEPT/EJECT 메시지수를더한다. -트리형성시간 : 모든노드들이제어트리에연결되는데걸리는시간을측정한다 -트리레벨 : 형성된제어트리의효율성을평가하기위하여트리의레벨수를측정한다. 첫번째실험으로그림 4 는제어메시지수의측면에 Msg. Overhead 400 350 300 250 200 150 100 50 Bottom-up (ttl 1) Bottom-up (ttl 2) Bottom-up (ttl 5) Proposed Scheme 4. 성능평가 0 0 200 400 600 800 1000 Group Size 이번장에서는앞에서설명한상향식기반의 ES[16] 방법과하향식기반의본논문에서제안한기법에대한그림 4 그룹사이즈변화에따른메시지오버헤드
신뢰적인멀티캐스트전송프로토콜을위한 Top-Down 기반의제어트리구축방안 617 Msg. Overhead 550 500 450 400 350 300 250 200 150 100 50 Bottom -up (ttl 1) Bottom -up (ttl 2) Bottom -up (ttl 5) Proposed Scheme 5 10 15 20 25 30 atio of the number of H (%) Tree Creation Time 24 Proposed Mechanism Bottom-up (ES) 22 20 18 16 0 200 400 600 800 1000 Group Size 그림 5 H 비율의변화에따른메시지오버헤드 그림 6 그룹크기변화에따른트리구성시간 서제안방법인하향식과 ES로대표되는상향식의성능을평가한것이다. 서로다른그룹수신자환경에서실험한모든그룹에서하향식방법이제어메시지수를감소시키는것을볼수있다. 이것은앞서설명한대로하향식방법은 QUEY 메시지의필요성을없앰으로써간단한메시지교환으로제어트리를구축하며하향식기반의제안방법은 ES와는달리 TTL값의증가에영향을받지않는장점이있기때문에기존방법의주요한단점중의하나인메시지오버헤드를줄일수있는것으로나타났다. 그림 5에서는노드 1000개의그룹환경에서전체수신자수중 H 노드가차지하는비율을달리하여메시지오버헤드를조사하였다. 상향식방법은그룹내에서 H 수가증가함에따라성능이조금씩좋아지는것을볼수있다. 이것은전체그룹내에 H가증가하면서그룹수신자들이보다빨리 H를찾을수있으므로그만큼제어트리에참여하기위한메시지교환이적어질수있기때문이다. 그러나전체노드의 30% 가 H에참여한경우에서도여전히 Top-down 방식보다는메시지오버헤드가큰것으로나타난다. 특히이환경에서는이후에설명될트리레벨에대한실험에서지나치게깊은트리를형성하는것으로나타나서 ( 그림 9 참조 ), 전체노드에서 H 수가많아지는것이상향식방식의메시지오버헤드를줄이는데도움을주긴하지만전체적인트리효율성이향상된다고보여지기는어렵다. 이결과를통하여본논문의제안기법은메시지오버헤드측면에서그룹내 H 비율의변화에민감하지않은것을관찰할수있다. 그래프의성장곡선으로전체수신자수에대한 H의비율이 30% 를넘어서도제안기법은일정한오버헤드를보일것이라는것을짐작할수있다. 그러나전체수신자수에대한 H 노드의비 율이 30% 를넘는것은이장의앞에서밝혔듯이트리기반의장점을저해하기때문에실험에서제외되었다. 이실험결과는 H 비율에민감하지않은제안기법이어떤환경의네트워크에서도고른성능을낼수있다는장점이있다는것을알수있다. 그림 6은서로다른수의그룹수신자를보유한네트워크환경에서제어트리를구축시간측면에서성능을평가한것을보이고있다. 트리구축시간측면에서는그룹수신자수가증가할수록단계적트리구성을제공하는하향식방법보다병렬적트리구성을제공하는상향식방법에서우수한성능을보이고있다. 하향식방법은그룹수신자수 500 명미만에서는상향식보다우수한성능을보이지만그이상에서는상향식방식에비하여성능이저하되는것을볼수있다. 그러므로하향식은트리구성시간적인측면에서만본다면비교적작은크기의멀티캐스트그룹에보다적합한방식이라고하겠다. 또한그림 7 은그룹수신자수 1000 의환경에서그룹 Tree Creation Time 24 22 20 18 16 Proposed Mechanism Bottom-up (ES) 5 10 15 20 25 ation of the number of H (%) 그림 7 H 비율의변화에따른트리구성시간
618 정보과학회논문지 : 정보통신제 28 권제 4 호 (2001.12) 20 Proposed Mechanism Bottom-up (ES) 25 Proposed Mechanism Bottom-up (ES) 15 20 Tree Level 10 Tree Level 15 10 5 5 0 0 200 400 600 800 1000 Group Size 0 5 10 15 20 25 30 atio of the number of H (%) 그림 8 그룹크기변화에따른트리레벨 그림 9 H 변화에따른트리레벨 내 H 수의비율이변화될경우제어트리구축시간 (2) 트리형성시간측면에서는하향식방법은그룹을측정한것이다. 이실험에서는두가지방법모두수신자수 500 미만의작은그룹을가진네트워크환경 H 수가증가함에따라제어트리구축시간이감소하에서우수하며이보다큰그룹에서는상향식방법이는것을볼수있다. 이것은일반수신자들이가까운거우수하다는것을알수있다. 그러므로제어트리형성리내에서짧은시간안에자신의부모 H를찾아제시간에민감한큰그룹크기를가진환경에서는상향식어트리에참여할수있기때문이다. 방법을사용하는것이적합하다는것을알수있다. 그림 8과그림 9는제어트리가형성된후에트리레 (3) 형성된제어트리의깊이를평가한결과에서는벨을조사한것이다. 그림 8은서로다른그룹수신자제안한하향식기반방식이뚜렷하게우수한것을볼수아래서형성된제어트리의레벨을보이고있으며, 수있다. 특히제안한기법에서는그룹수신자수의증그림 9는그룹수신자수가 1000일경우그룹내전체가나 H 수의변화에민감하지않게안정된레벨의트수신자대비 H 수를달리해서실험한결과이다. 두가리를형성함으로써그룹수신자의분포나참여가일정지실험에서모두트리레벨측면에서는제안한하향식하게예측되지않는환경에서도안정된성능을나타낼방법이현저하게낮은레벨의트리를구축한것을볼수수있다는것을알수있다. 있다. 트리기반방식에서트리의깊이가깊어지면메시지가전달되는길이가길어지며통합메시지전달에도 5. 결론및향후연구과제비효율적이므로바람직하지않다. 실험결과로부터상향신뢰적인멀티캐스트전송프로토콜은원격강의, 원식방법은모든수신자들이 greedy manner' 를가지고격주식정보교환, 공동문서작업, 소프트웨어분배전체트리구성과관계없이자신과가까운 H를만나등다양한종류의응용을위해필요하다. 이를위해계면무조건트리에바인딩하는반면, 제안한하향식방안층적트리기반에서서비스를구축할경우신뢰성뿐만은각 H들이 ADVETISE 메시지를보내고이것으로아니라확장성을보장할수있다. 이러한제어트리기 H의정보를모은뒤수신자들이적합한 H를찾아가반의서비스를구축하기위하여네트워크계층의라우는방법을사용하기때문에궁극적으로레벨이깊지않팅트리와는별도로전송계층에서논리적제어트리를은효율적인트리를구축한다는것을알수있다. 형성하는것이필요하다. 위의실험을요약하면다음과같은다음과같은결과현재제어트리형성을위해서상향식 (bottom-up) 를얻어낼수있다. 방식이주로사용되고있는데, 이것은모든수신자들이 (1) 제어메시지수로측정한메시지오버헤드측면병렬적으로트리형성에참여함으로써수신자주도의에서는제안한하향식기반방식이보다우수한성능을간단한제어트리형성방법을제공한다. 그러나이방갖는다는것을알수있다. 이결과로부터제안한방식법은루프방지를보장할수없으며메시지오버헤드가이대역폭자원이적은네트워크환경에보다적합하다크다는단점이있다. 는것을알수있다. 그러므로본논문에서는상향식방법의단점을보완
신뢰적인멀티캐스트전송프로토콜을위한 Top-Down 기반의제어트리구축방안 619 할수있는하향식 (top-down) 기반의제어트리구축방안을제시하였다. 하향식방법은송신자와지역그룹대표자인 H들이주도하여제어트리를단계적으로형성하여제어트리가송신자로부터점진적으로성장해나가기때문에별도의메커니즘없이루프방지를보장할수있다. 또한실험결과를통하여제안방법이기존의상향식기반방식의단점인메시지오버헤드를감소시킬수있으며보다안정된깊이를갖는트리를형성하는것을알았다. 그러나제어트리형성시간의관점에서는하향식은그룹크기가커졌을때트리구축시간이길어지는단점을보였다. 이것은단계적인트리구축의특성으로인하여병렬적트리구성을하는상향식에비하여긴시간이걸리는것으로보인다. 이러한실험결과는제안한하향식제어트리구축방식이제어트리구축시간이민감하지않고네트워크대역폭자원이풍족하지않은네트워크환경에서는상향식의대안으로사용될수있을것이라는것을나타낸다. 그러므로, 본논문에서제한한방식은다양한응용의요구와네트워크환경을고려하여상향식방법과선택적으로사용할수있을것으로보인다. 향후보다다양한그룹수신자환경과다양한메트릭스를사용하여다양한관점에서상향방식과하향방식을비교평가하며효율적인제어트리구축을위한연구가지속되어야한다. 참고문헌 [1] S. Deering, "Host Extensions for IP Multicasting," FC1112, August 1989. [2] K. Obraczka, "Multicast Transport Protocols: A Survey and Taxonomy," IEEE Communication Magazine, January 1998. [3] eliable Multicast Links, http://research.ivv.nasa. gov/mp/links.html, January 2001. [4] M. Luby, J. Gemmell, L. Vicisano, L. izzo, M. Handley, and J. Crowcroft, "Layered Coding Transport: Massively scalable multicast protocol," IETF Internet Draft, draft-ietf-rmt-bb-lct-02.txt, November 2000. [5] B. Adamson, C. Bormann, S. Floyd, M. Handley, and J. Macker, "NACK-Oriented eliable Multicast Protocol (NOM), IETF Internet Draft," draft-ietf-rmt-pi-norm-00.txt, November 2000. [6] B. Whetton, D. Chiu, M. Kadansky, and G. Taskale, "eliable Multicast Transport Building Block for TACK," IETF Internet Draft, draft- ietf-rmt-bb-track-00.txt, November 2000. [7] B. Whetton, D. Chiu, S. Paul, M. Kadansky, and G. Taskale, "TACK Architecture: A Scalable eal-time eliable Multicast Protocol," IETF Internet Draft, draft-ietf-rmt-track-arch-00.txt, July 2000. [8] B. Neil Levin and J.J. Garcia-Luna-Aceves, "A Comparison of Known Classes of eliable Multicast Protocols," Proceedings of International Conference on Network Protocol(ICNP-96), 1996. [9] D. M. Chiu, S. Hurst, M. Kadansky, and J. Wesley, "TAM: A Tree-based eliable Multicast Protocol," Technical eport of SUN Microsystems, SML T-98-66, July 1998. [10] M. Kadansky, B. Levine, D. Chiu, B. Whetten, G. Taskale, B. Cain, D. Thaler, and S. Koh, "eliable Multicast Transport Building Block: Tree Auto- Configuration," IETF Internet Draft, draft-ietfrmt-bb-tree-config-01.txt, November 2000. [11] C. Maihofer and K. othermel, "A obust and Efficient mechanism for Constructing Multicast Acknowledgement Trees," T-IPV-99, July 1999. [12] M. Handley, "SAP : Session Announcement Protocol," IETF Internet Draft, November 1996. [13] M. Handley and V. Jacobson, "SDP : Session Description Protocol," FC2327, April 1998. [14] B. Whetten and G. Taskale, "The Overview of eliable Multicast Transport Protocol II," IEEE Network, January-February 2000. [15] M. Kadansky, D. Chiu, J. Wesley, and J. Provino, "Tree-based eliable Multicast (TAM)," IEEE Internet Draft, draft-kadansky-tram-01.txt, September 1999. [16]. Yavatkar, J. Griffioen and M. Sudan, A eliable Dissemination Protocol for Interactive Collaborative Applications, In Proceedings of ACM Multimedia 96. [17] M. MacDouall, "Simulating Computer Systems, Techniques and Tools," MIT Press, 1987. 김은숙 1996 년 2 월숙명여자대학교전산학과졸업 ( 학사 ). 1998 년 2 월숙명여자대학교대학원전산학과졸업 ( 이학석사 ). 2001 년 8 월숙명여자대학교대학원컴퓨터과학과졸업 ( 이학박사 ). 2001 년 3 월한국전자통신연구원표준연구센터. 관심분야는 MT, 멀티미디어그룹통신, 인터넷 QoS 등
620 정보과학회논문지 : 정보통신제 28 권제 4 호 (2001.12) 고석주 1992년 2월한국과학기술원경영과학과 ( 공학사 ). 1994년 2월한국과학기술원경영과학과 ( 공학석사 ). 1998년 8월한국과학기술원산업공학과 ( 공학박사 ). 1998년 8월 ~ 현재한국전자통신연구원표준연구센터. 2000년 6월 ~ 현재 ITU-T SG7 & ISO/IEC JTC1/SC6 Project Editor. 관심분야는인터넷멀티캐스트, 인터넷 QoS 강신각 1984년 충남대학교 전자공학과 학사. 1987년 충남대학교 전자공학과 석사. 1998년 충남대학교 전자공학과 박사. 1995년정보통신기술사. 1984년 ~ 현재 한국전자통신연구원통신프로토콜표준연 구팀장. 1997년 ~ 현재 ITU-T SG 7 Q.8 apporteur. 2000년 ~ 현재 VoIP 포럼부의장. 관심 분야는멀티미디어통신, VoIP, 정보보호 최종원 1984년서울대학교전자계산기공학과졸업 ( 학사 ). 1986년서울대학교대학원전자계산기공학과졸업 ( 공학석사 ). 1992년 Northwestern University 졸업 ( 공학박사 ). 1993년 ~ 1997년숙명여자대학교전산학과조교수. 1997년 ~ 현재숙명여자대학교전산학과부교수. 관심분야는분산라우팅알고리즘, QoS 라우팅, 멀티캐스트라우팅알고리즘, MT 등임.