工工碩士工士士士 PIM-SM 에서오버헤드감소를위한 Group-Bootstrap Router 선정기법 Group-Bootstrap Router Selection Scheme to Reduce an Overhead in PIM-SM 2004 年 2 月 仁仁仁工仁仁工大 電電電電工工電 廉陳虎
工工碩士工士士士 PIM-SM 에서오버헤드감소를위한 Group-Bootstrap Router 선정기법 Group-Bootstrap Router Selection Scheme to Reduce an Overhead in PIM-SM 2004 年 2 月 指指指指李均夏 이士士을工工碩士工士士士으로提提함 仁仁仁工仁仁工大 電電電電工工電 廉陳虎
이士士을廉陳虎의碩士工士士士으로認認함 2004 年 2 月 主主 ( 印 )_ 副主 ( 印 )_ 委委 ( 印 )_
요 약 하나이상의송신자가특정사용자그룹에게만정보를전송하는그룹통신인멀티케스트는유니캐스트에비해송신자가하나의패킷으로원하는그룹에게정보를전송할수있다는장점을가지고있다. 멀티캐스트를지원하는라우팅프로토콜은소스기반트리방식과공유트리방식으로구분되며, 이중 RPT(Randevous Pointer-Tree) 를이용한공유트리방식으로확장성이우수한 PIM-SM(Protocol Independence Multicast-Sparse Mode) 프로토콜은 RP(Randevous Pointer) 를선정하기위해서 Bootstrap 작동방식에따라초기하나의 BSR(Bootstrap Router) 을선출한다. 그리고각각의 C-RP(Candidate-RP) 들은 BSM(Bootstrap Message) 의생성을위해서비스가능한그룹의정보가담긴 C-RP- Adv(Candidate-RP Advertisement) 메시지를 BSR 로전송하게한다. 이로 인해그룹과 C-RP 의수에비례하여 BSM 의크기가커지게되며, 전체네트워크에 BSM 으로인한오버헤드를증가시키는문제점을가진다. 본논문에서는그룹당하나의 G-BSR(Group-Bootstrap Router) 을선정함으로써, G-BSM(Group-Bootstrap Message) 의크기를줄이고, 전체네트워크의 BSM 으로인한오버헤드를줄이는방식을제안한다. 이제안방식은기존 PIM-SM 라우팅프로토콜의작동방식에서의컨트롤메시지들을그대로사용함으로써, 별도의수정과정없이적용할수있도록고안되었다. 모의실험을통해기존방식과의비교에서그룹의수와 C-RP 의 i
수의변화에안정적인증가치를보였고, 전체노드의수와각노드간 연결정도의변화에도기존방식에비해우수한결과를입증하였다. ii
ABSTRACT A multicast communication, which is a group communication to the specific user group, has a strong point that one more senders can communicate with a receiver group through only one packet compared with a unicast. Routing protocols to support the multicast are categorized into a sourcebased tree scheme and shared tree scheme. The PIM-SM(Protocol Independence Multicast-Sparse Mode),which has a good extensibility and is based on a shared tree scheme using RPT(Randevous Pointer-Tree), elects an initial BSR(Bootstrap Router) to select an optimal conditioned RP(Randevous Pointer) according to the Bootstrap operation mechanism. Moreover, in order to generate a BSM(Bootstrap Message), each C-RP(Candidate-RP)s send BSR C-RP-Advertisement Message including the information of the possible service group. This causes the problem that the number of a group increases in proportion to C-RP and hence an overhead grows at the whole network due to the BSM. This paper proposes group per G-BSR(Group-Bootstrap Router) selection scheme and reduced size of results G-BSM(Group-Bootstrap Router) and proposes a method to reduce overhead by BSM of a total network. G-BSR selection scheme uses control messages of PIM-SM as it is, adjustment and to be different does not have a need. Compared with the existing scheme by a simulation, our scheme shows stable increase by the variation of the number of the groups and C-RPs, prove that it shows more excellent result than the existing scheme by the variation of the number of all nodes and the node degree. iii
목 차 요약...i ABSTRACT...iii 목차...iv 제 1 장서론...1 제 2 장 PIM-SM 프로토콜...3 2.1 PIM-SM 의개요... 3 2.2 관련프로토콜연구... 4 2.2.1 DVMRP...4 2.2.2 MOSPF...5 2.2.3 PIM-DM...6 2.2.4 CBT...6 2.3 PIM-SM 의동작절차... 9 2.4 Bootstrap 작동방식... 15 2.5 기존방식의문제점... 18 제 3 장제안한 Group-Bootstrap Router 선정기법...19 3.1 Group-Bootstrap Router 의동작... 20 3.2 그룹생성과 Group-Bootstrap Router 재선정... 23 제 4 장모의실험및성능분석...25 4.1 모의실험환경... 25 4.2 오버헤드비교분석... 26 4.3 실험결과... 28 제 5 장결론...31 참고문헌...32 iv
제 1 장서론 초기의인터넷환경은유니캐스트를이용한데이터의전송이주를이루었으나, 현재에는인터넷의발달과함께영상회의, 원격강의등과같은음성및영상정보중심의실시간멀티미디어서비스를제공하기위한멀티캐스트서비스의연구가폭넓게이루어지고있다. 멀티캐스트서비스는하나의송신자로부터다수의수신자에게데이터를전송함으로써유니캐스트에비해실시간서비스를필요로하는사용자에게더욱많은데이터를전송할수있다. 현재멀티캐스트라우팅프로토콜은트리구성방식에따라 DVMRP(Distance-Vector Multicast Routing Protocol), MOSPF(Multicast Extension to OSPF), PIM-DM(Protocol-Independence Multicast-Dense Mode), PIM-SM (Protocol Independence Multicast-Sparse Mode), CBT(Core-Based Trees) 등이있다 [1]. 이중에서 PIM-SM 라우팅프로토콜은공유트리방식으로확장성측면에서우수하다 [2]. PIM-SM 라우팅프로토콜은 RP(Randevous Pointer) 를선정하여공유트리의루트로사용한다. 모든소스호스트는자신의멀티캐스트트래픽을 RP 로보내고, RP 는다시공유트리를통해그룹의모든구성원들에게패킷을전달한다. 이러한과정으로멀티캐스트서비스가수행되기위해서초기 PIM-SM 라우터들중하나가 BSR(Bootstrap Router) 로선정되며, 이 BSR 은 RP 선정시필요한정보들을도메인내의모든라우터들에게제공하고유지되어야한다. 1
BSR 은 BSM(Bootstrap Message) 이라는컨트롤메시지를생성하여전체네트워크에포워딩하게된다. 이메시지는그룹과각그룹에서비스가능한 C-RP(Candidate-RP) 의정보를포함하기때문에그룹과 C- RP 의수에비례하여컨트롤메시지가커지는문제점을가진다 [3]. 이는 Bootstrap 작동방식으로인한전체네트워크의오버헤드를발생시키게된다 [6]. 본논문에서는각각의멀티캐스트그룹당하나의 BSR 을선정하는 G-BSR(Group-Bootstrap Router) 선정기법을제안하였다. 이제안방식은각그룹에해당하는정보만을포함한 G-BSM(Group-Bootstrap Message) 를생성한다. 전체네트워크를대상으로전송되던컨트롤메시지를그룹단위로관리함으로써, 컨트롤메세지로인한전체네트워크에서의오버헤드를줄이게되었으며, 기존방식의문제점을개선하였다. 본논문의구성은다음과같다. 2 장에서는 PIM-SM 라우팅프로토콜에대한전반적인설명과관련된멀티캐스트라우팅프로토콜에대해서설명한다. 또한 PIM- SM 의동작절차, 그리고 Bootstrap 작동방식에대한고찰을통해기존방식의문제점을제시한다. 3 장에서는기존방식의문제점해결을위한 G-BSR 선정기법을제안하고설명한다. 4 장에서는제안방식을모의실험하여기존방식과비교평가하며, 5 장에서는본논문의결론을낸다. 2
제 2 장 PIM-SM 프로토콜 본장에서는 PIM-SM 라우팅프로토콜의개요및관련된멀티캐스트라우팅프로토콜에대해서살펴본다. 또한 PIM-SM 의동작절차에대해서설명하며, 기존의 Bootstrap 작동방식에대한고찰을통해기존방식의문제점을제시한다. 2.1 PIM-SM 의개요 PIM-SM 프로토콜은현재 IDMR(Inter-Domain Multicast Routing) 워킹그룹에의해서개발중이며, 특정한유니캐스트라우팅프로토콜에서제공되는방식과무관하게멀티캐스팅을지원한다 [3]. 또한특정한라우팅테이블의계산을필요로하지않기때문에 DVMRP 보다 단순하다. 그러나 PIM 을기반으로하는시스템의구현은네트워크 토폴로지 (Topology) 변화에효과적으로적응하는유니캐스트라우팅프로토콜을필요로한다. 기존의멀티캐스트라우팅방식에서는멀티캐스트서비스에참여하는몇몇호스트가전체네트워크를대상으로주기적인멀티캐스트트래픽을전송하게되는경우, 심각한과부하문제가발생하게된다. 이러한부하문제를해결하기위하여 PIM-SM 프로토콜은단지트래픽수신에관심있는라우터에대해서만멀티캐스트트래픽을전송하는방식을이용한다 [9]. 3
PIM 라우팅프로토콜에는 Dense 모드와 Sparse 모드가있으며, 네트워크의환경에따라각각 PIM-DM 과 PIM-SM 으로구분하여 사용한다. Sparse 모드의정의는다음과같다 [4]. 첫째, 그룹구성원이있는현재네트워크나도메인의수가인터넷의네트워크나도메인의수보다현저하게적을경우. 둘째, 그룹구성원들이너무큰지역이나광범위한지역에분산되어있어홉의수나멀티캐스트패킷전달범위를제한하는기타형식에의존할수없는경우. 셋째, 현재 Dense Mode 의오버헤드구성을무시할만큼충분한자원이네트워크에없는경우. 2.2 관련프로토콜연구 멀티캐스트라우팅프로토콜은크게소스기반트리와공유트리의방식으로나뉜다. 소스기반트리는 DVMRP, MOSPF 그리고 PIM-DM 이속하며, 공유트리방식은 CBT 와 PIM-SM 이속한다. 2.2.1 DVMRP DVMRP 는 RPM(Reverse Path Multicasting) 알고리즘을구현한다. 이는소스-그룹에대한첫번째데이터그램이기준치에허용되는 TTL 과라우터인터페이스범위에따라포워딩된다. 일단초기데이터그램은 4
모든라우터들에게전송되며, 수신라우터와직접연결되어있는서브네트워크에그룹멤버가존재하지않을경우, 해당라우터는소스를향하여 Prune 메시지를전송한다. [ 그림 2-1] 은 DVMRP 의작동방식을나타낸다. Sender Data Packet Prune Message R1 R2 R3 Receiver R6 R4 R5 [ 그림 2-1] DVMRP 의동작 Prune 과정을통하여모든그룹멤버를연결시켜주는하나의소스기반 (Source specific) 최단경로트리가구성된다. 일정기간동안이러한 Prune 메시지전달과정이반복되며, 새로운그룹멤버를포함하는새로운트리가구성될수있다 [11]. 2.2.2 MOSPF MOSPF 는네트워크토폴로지정보를구축하고이를통해서 트리를구성하는방법을사용하고있다. MOSPF 프로토콜은 OSPF 를 5
멀티캐스트에적용하기위해확장한프로토콜이며 RFC-1584 에정의되어있다. MOSPF 라우터는그룹의멤버쉽을포함한링크 (link) 의상태를주고받음으로써네트워크토폴로지를알아낸다. 이때문에 MOSPF 에서는 OSPF 에서사용하는광고메시지타입외에그룹의멤버쉽정보에관한메시지가추가된다. 라우터사이에교환된토폴로지정보는 link-state 데이터베이스에저장된다. MOSPF 는이렇게축적된데이터베이스를기반으로 Dijkstra 알고리즘을사용해서트리를생성한다. 생성된트리는그룹멤버쉽 link-states 광고메시지에의해그룹멤버를가지고있지않은트리의가지를잘라내게되어송신자와그룹멤버들간의최단경로트리를생성한다. 이트리에위치한라우터들은수신된데이터그램이모든그룹의멤버에게도착할때까지한홉씩포워딩계산을한다 [12]. 2.2.3 PIM-DM PIM-DM 은그룹의멤버가상대적으로밀집되어있고대역폭이풍부한환경에서작동되는프로토콜이다. 모든다운스트림인터페이스에멀티캐스트데이터를포워딩하며, 명백한절단메시지가수신될때까지포워딩을계속하게된다 [9]. 2.2.4 CBT 공유트리방식인 CBT 는송신자에관계없이양방향성의유일한 트리를구성하는확장성있는방법을사용한다. CBT 는송신자와 그룹의쌍으로이루어진소스기반트리와는달리송신자와관계없이 그룹의멤버가공유하는하나의트리를만든다. 따라서각각의 그룹으로보내진멀티캐스트트래픽은같은경로를통하여수신된다. 6
공유트리는코어 (Core) 라우터를중심으로연결되어있으며, 코어라우터는멀티캐스트주소와코어라우터를매핑시키는 Hash 함수에의해서선택된다. 각라우터는똑같은 Hash 함수를가지기때문에그룹당동일한코어가선택된다. 공유된하나의트리를구성하기위해서, 우선호스트는 IGMP 그룹멤버쉽메시지를통하여 Join 하고자하는그룹을로컬라우터에알린다. 따라서로컬라우터는 Join Request 메시지를전송하며, 선정된코어를통한공유트리로의멀티캐스트데이터패킷을전송받을수있게된다 [13]. PIM-SM 이구성하는공유트리는방향성이존재한다는점에서 CBT 트리와다르다. 또한공유트리와송신자기반의최단경로트리를이용할수있기때문에송신자와멤버간의전송지연을최소화한다는장점을가진다. PIM-SM 은기존의소스기반트리의멀티캐스트알고리즘과다음두가지측면에서차이점이존재한다 [7]. 첫째, PIM-SM 에서직접멤버가접속되어있는라우터는멀티캐스트트리에참여하기위해 Join 메시지를전송한다. 만약이미해당라우터가멀티캐스트트리에참여하고있었다면, 추가적인멀티캐스트트래픽수신은이루어지지않을것이다. 소스기반트리방식에서는기본적으로트래픽을포워딩한다. 반면에 PIM- SM 방식에서는멤버의요구가있는경우에만트래픽을포워딩하게된다. 또한멀티캐스트데이터전송량이커지게될경우, SPT(Shortest Path Tree) 로변환하여트리를재구축하게된다. 7
둘째, 각멀티캐스트그룹은초기 RP 를선택하고대안 RP 들의목록을유지하고있다. 각멀티캐스트그룹에대해서단하나의 RP 만이가동된다. 멀티캐스트그룹에참여를원하는각수신라우터는 RP 에 Join 메세지를전송한다. 각소스는 RP 를사용하여각멤버들에게데이터를전송한다. 이러한모형은각라우터가 RP 들의목록과같은일종의상태정보를유지하도록요구한다. 이에반해소스기반트리에서는첫번째데이터패킷이도착한후에멀티캐스트트리가구성되므로이러한상태정보가요구되지않는다. 8
2.3 PIM-SM 의동작절차 각주요절차에따른세부사항은다음과같다 [3]. (1) 그룹으로참가 특정멀티케스트그룹에 Join 하고자하는호스트는 IGMP(Internet Group Membership Protocol) 를이용하여멤버쉽정보를전달한다. LAN 에연결되어있는 PIM 라우터가하나이상존재하는경우에는, [ 그림 2-2] 와같이가장높은 IP 주소를가지는라우터가해당 LAN 에대한 DR (Designated Router) 로사용된다 [4][9]. 새로운그룹에대한멤버쉽을얻은 DR 은관련된 RP 를검색한다. 여기서 RP 의선정방식에대한알고리즘에대한기술은생략하겠다. DR 은 (*,G) 엔트리를생성하고 RP 의주소를이루트엔트리 (Route Entry) 의특별필드에포함한다. 206.80.51.1 PIM-SM Router Ethernet Hello Message Hello Message DR(Dignated Router) 206.80.51.2 PIM-SM Router [ 그림 2-2] DR 의선정 9
(2) RP 를루트로하는공유트리확립 수신자의 DR 은 (*,G) 엔트리를가진 Join 메시지를자신의그룹의 RP 를향하여전송한다. 각상위라우터들은 Join 메시지를전송받았을때, 자신의 (*,G) 엔트리를생성하거나갱신한다. Join 메시지가도착한인터페이스는출력인터페이스로설정되며, 이러한과정으로 [ 그림 2-3] 과같은공유트리가확립된다. Source RP (*,G) Join Join Message Shared Tree Receiver [ 그림 2-3] RP 로의연결및공유트리확립 10
(3) 그룹으로데이터전송 소스가그룹으로멀티캐스트데이터패킷의전송을시작할때소스의 DR 은 [ 그림 2-4] 에서와같이 Register 메시지안에각데이터패킷을캡슐화하여그그룹에해당하는 RP 로유니캐스트한다. RP 는각레지스터메시지를비캡슐화하여데이터패킷을공유트리상의하위멤버들에게전달한다. unicast Source Capsulation (S,G) Join RP Decapsulation Register Message Shared Tree Shortest Path Tree Receiver [ 그림 2-4] Register 메시지전송 11
RP 가그룹또는특정소스에대한하위수신자를가지고있지않거나이미 SPT 로전환하여캡슐화되지않은데이터패킷을받고있는상태라면, RP 는 [ 그림 2-5] 와같이 Register 메세지에대한응답으로 Register Stop 메시지를소스의 DR 에게보낸다. unicast Source RP Shared Tree Shortest Path Tree Register-Stop Message Receiver [ 그림 2-5] Register Stop 메시지전송 (4) RPT 에서 SPT 로의전환 직접연결된멤버를가지고있는라우터는처음에 RPT(RP-Tree) 에 Join 한다. 그러나한그룹에대한임계값이초과되었을경우 SPT 로 전환하게된다 [4]. 완전한 SPT 가확립되기전까지멤버는이전의 (*,G) 12
엔트리가가리키는입력인터페이스를통해소스로부터전송되어지는 데이터패킷을받을수있다. (S,G) 엔트리생성시출력인터페이스 리스트는 (*,G) 로부터복사된다. SPT 를이용한데이터수신시라우터는 RP 를향하여 Prune 메시지를전송하게된다. [ 그림 2-6] 은이러한 과정을나타낸다. Source RP (S,G) Joins Shared Tree Shortest Path Tree (S,G) Prune Receiver [ 그림 2-6] RP-Tree 에서 Shortest Path Tree 로전환 (5) 안정된상태의유지 이러한과정들을통해서그룹의멤버들은멀티캐스트데이터 패킷을전송받는다. 안정된상태에서라우터들은활성화된각루트 엔트리에대하여주기적으로 [ 그림 2-7] 과같은 Join/Prune 메시지를 13
전송한다. 이메시지는네트워크의상태, 토폴로지, 그리고멤버쉽 변화를파악하기위한것이며, 어떤새로운소스에대한새로운루트 엔트리가구성될때마다 Event-Trigger 방식으로전송된다. 0 3 4 7 8 15 16 31 Version Type Reserved Checksum Encoded Unicast Upstream Neighbor Address Reserved Number of Groups Holdtime Encoded Multicast Group Address = 1 Number of Joined Sources = n Number of Pruned Sources = m Encoded Join Source = 1 Encoded Join Source n Encoded Prune Source 1 Encoded Prune Source n Encoded Multicast Group Address = Number of Joined Source =s Number of Pruned Sources = t Encoded Join Source = 1 Encoded Join Source s Encoded Prune Source 1 Encoded Prune Source t [ 그림 2-7] Join/Prune 메시지 14
2.4 Bootstrap 작동방식 RP 를선정하기위해서각각의그룹멤버의 DR 은 BSR(Bootstrap Router) 이생성하는 BSM 을수신한다. PIM-SM 을지원하는라우터는현재활성화되어있는그룹에대한주소와각그룹마다존재하는멤버들에게동일한 RP 가선정되도록한다. PIM-SM 의 Bootstrap 작동방식은다음의순서를따른다 [3]. (1) Bootstrap Router 의선출 PIM 도메인내의라우터들중일부는 C-BSR(Candidate-Bootstrap Router) 로선출되며, 각각은 Priority 를가진다. C-BSR 들은 Hop by Hop 으로각각의 Priority 를비교하며, 이들중가장높은 Priority 를가지는 C-BSR 은도메인내의 BSR 로선정된다 [4]. 선출된현재의 BSR 이정상적인동작을못할경우, 다른 C- BSR 중에서가장높은 Priority 를가진라우터가네트워크의새로운 BSR 로자동선출된다 [5]. (2) C-RP Advertisement 메시지의전달 C-BSR 들로구성되었던라우터들은 C-RP 로재구성된다. C- RP 들은선출된 BSR 에게주기적으로 [ 그림 2-8] 의필드들로구성된 C- RP Adv(Candidate-RP Advertisement Message) 메시지를유니캐스트한다. C- RP Adv 메시지는서비스가능한그룹의주소와 C-RP 자신의유니캐스트주소를포함한다. C-RP Adv 메시지를전송받은 BSR 은 [ 그림 2-9] 과같은각각의 15
그룹마다서비스가능한 C-RP 들의정보를담은 BSM 을생성하게된다. 0 3 4 7 8 15 16 31 Version Type Prefix Count Reserved Priority Encoded Unicast RP Address Encoded Group Address = 1 Encoded Group Address = n Checksum Holdtime [ 그림 2-8] Candidate-RP Advertisement 메시지 (3) Bootstrap 메세지의분배 생성된 BSM 은해당라우터의직접접속된모든인터페이스로전송되어진다 [3]. 이전송은 Bootstrap 타이머의만료시간보다작은주기로이루어진다. 모든라우터들은 BSM 수신시다음과정을수행한다 [4][6]. Step 1. RPF(Reverse Path Forwarding) 검사를수행하여소스로부터정확한인터페이스로도달되었는지를체크한다. 이러한 RPF 검사를통해 BSM 의루프의문제점을해결한다. Step 2. RPF 검사결과이상이없으면, 수신된 BSM 이포함하는 BSR 의 Priority 와주소정보를저장된이전정보와비교한다. 16
0 3 4 7 8 15 16 31 Version Type Fragment Tag Reserved Hash Mask Length Encoded Unicast BSR Address Encoded Group Address = 1 Checksum BSR Priority RP Count 1 Fragment RP Count 1 Reserved Encoded Unicast RP Address = 1 RP1 Holdtime RP1 Priority Reserved Encoded Unicast RP Address = 2 RP2 Holdtime RP2 Priority Reserved Encoded Unicast RP Address = m RP Holdtime RPm Priority Encoded Group Address = 2 Reserved RP Count n Encoded Group Address = n Fragment RP Count n Encoded Unicast RP Address = 1 Reserved RP1 Holdtime RP1 Priority Encoded Unicast RP Address = 2 Reserved RP2 Holdtime RP2 Priority Reserved Encoded Unicast RP Address = m RPm Holdtime RPm Priority Reserved [ 그림 2-9] Bootstrap 메시지 BSR 을수신한각라우터들은저장된이전의 BSM 으로부터의 C- RP 들의정보를업데이트하며, Bootstrap 타이머를재시작한다. 그리고자신의인접라우터를향하여 BSM 을전송받은인터페이스를제외한모든인터페이스로전송을계속한다. 17
BSM 이도착되지않거나전송이중단되었을때각각의라우터는새로운정보가도착되기전까지이전의 BSR 과 C-RP 들의정보를계속유지한다. 이런경우, 멀티캐스트데이터패킷의전송은각그룹당선정되어서비스하고있는 RP 가도달가능할때까지만계속된다 [6]. (4) RP 의목록처리 BSM 에는각그룹으로서비스가능한 C-RP 들의목록을포함한다. BSR 은 RP 타이머를설정하며, 타이머의만료시간동안 C-RP Adv 메시지가도착하지않는다면해당 C-RP 를도달이불가능한것으로 판단한다. 따라서유지되고있는 C-RP 의목록에서제외하며, 새로운 BSM 의생성시해당 C-RP 를제외시킨다 [6]. 2.5 기존방식의문제점 BSM 은수신을원하는그룹멤버의 DR 이 RP 를선정하여 공유트리를구성하기위한필수적인컨트롤메시지다. C-RP 들은 C-RP Adv 메시지를주기적으로전송하며, BSR 은그룹과그룹에서비스 가능한 C-RP 들의목록과자신의주소등을포함한 BSM 을생성하여네트워크전체로전송하게된다. 여기서도메인내의 C-RP 들의수는 BSM 의크기와직접적인관련이있다 [6]. C-RP 의수가많을경우, 생성되는 BSM 의크기는그룹과해당그룹에서비스가능한 C-RP 의수에비례하여커진다 [3]. 이는 Bootstrap 작동방식으로인한전체네트워크의오버헤드를증가시키는문제점을발생시킨다 [6]. 18
제 3 장제안한 Group-Bootstrap Router 선정기법 본장에서는그룹마다 G-BSR 을선정하는방식을제안한다. PIM- SM 라우팅프로토콜을이용한멀티캐스트서비스시, 생성되는컨트롤메시지인 BSM 이그룹과 C-RP 의수에비례하여점진적으로커지게되는문제점을개선함으로써, BSM 으로인한전체네트워크의오버헤드를감소시키는방법을제안한다. 제안방식은기존 PIM-SM 의메시지필드를변형없이그대로사용하였다. 또한오버헤드를줄이기위해 BSR 작동방식에다음의몇가지절차를추가함으로써, G-BSR 방식을이용한멀티캐스트서비스가가능하게된다. 여기서각그룹의네트워크상태는동일하며, 그룹당서비스가능한 C-RP 의중복은발생하지않는다고가정한다. 기존방식에서 C- BSR 은 C-RP 로재구성된다 [3]. 따라서 C-RP 는 C-BSR 로재구성될수있다. 또한기존방식에서전송받은 C-RP Adv 메시지에포함된각각의 [C-RP: 그룹 ] 의정보를바탕으로 n 개의 [ 그룹 :C-RP] 들의전체네트워크의정보를포함한 BSM 을생성하기때문에 n 개의 G-BSM 수신시하나의 A-BSM 을생성할수있다고가정한다. 19
3.1 Group-Bootstrap Router 의동작 본논문에서제안한 G-BSR 선정기법의작동순서는다음과같다. Step 1. 기존방식과동일하게네트워크전체에서비스가능한 BSR 을 선정한다. 여기서의 BSR 은전체네트워크로서비스가능한 것이므로 A-BSR(All-Bootstrap Router) 이라고하겠다. Step 2. C-RP 들은 A-BSR 의유니캐스트주소를이용하여 C-RP Adv 메세지를전송한다. Step 3. 전송받은 C-RP Adv 메시지의정보를바탕으로 A-BSR 은기존 PIM-SM 의 Bootstrap 작동방식과같이그룹과서비스가능한 C-RP 들의정보를가진 A-BSM(All-Bootstrap Message) 을생성하여 [ 그림 3-2] 과같이전체네트워크로전송하게된다. 여기서각각의라우터들은 RPF 검사를수행하면서허용된인터페이스로만 A-BSM 을수신하게된다. Step 4. A-BSM 을전송받은 C-RP 들은 A-BSM 이포함한정보를이용하여자신의그룹에서비스가능한 C-RP 의유니캐스트주소로동일그룹에속한 C-RP 들간의 Priority 비교를통해각그룹당하나의 G-BSR 을선출한다. 20
Step 5. 선출되어진 G-BSR 들은 G-BSM 을생성하여해당그룹으로 전송함으로써, 해당 C-RP 들에게자신의유니캐스트주소와 해당그룹의 G-BSR 이라는사실을알린다. 이알림은 G- BSM 에서 [ 그림 3-1] 의필드정보를사용한다. 0 3 4 7 8 15 16 31 Encoded Unicast BSR Address RP Count n Encoded Group Address = Group address Fragment RP Count n Reserved [ 그림 3-1] Group-Bootstrap 메시지의일부 Step 6. G-BSM 을전송받은 C-RP 들은 C-RP Adv 메시지를 [ 그림 3-3] 과 같이해당 G-BSR 에게전송한다. 이는수신된 G-BSM 내의 유니캐스트주소필드를이용하며, G-BSM 을생성하기위한 정보를제공하게된다. 21
C-RP C-RP C-RP C-RP A-BSR C-RP C-RP C-RP C-RP Adv Message All-Bootstrap Message C-RP [ 그림 3-2] C-RP Adv 메시지와 A-BSM 의전송 Step 7. G-BSR 은 G-BSM 을생성하여자신의그룹내의라우터들에게 전송한다. 따라서각그룹의 DR 은자신의 G-BSR 이전송한 G- BSM 수신으로그룹을위한 RP 의선정이가능하게된다. 또한 G-BSR 로주기적인 Join/Prune 메시지를전송함으로멤버의 가입및탈퇴에따른변화에대한정보를유지시킬수있다. Step 8. 새로운그룹의생성에대비하여각 G-BSR 은초기선정된 A- BSR 에게도 G-BSM 을유니캐스트한다. 따라서 A-BSR 은각각의 G-BSR Bootstrap 주기마다 G-BSM 을전송받음으로써, 전체네트워크에존재하는모든 G-BSR 의정보와 C-RP 들의정보를유지하며업데이트가능하게된다. 22
Group 1 Group 2 C-RP C-RP C-RP G-BSR A-BSR G-BSR C-RP C-RP C-RP C-RP Adv Message Group-Bootstrap Message [ 그림 3-3] G-BSR 의선정과 G-BSM 의전송 기존방식으로생성된 BSM 은 m개의 C-RP 의목록을 n개의그룹수만큼포함하였다. 이에반해, G-BSR 선정기법으로생성된 G-BSM 은각각의그룹당해당 C-RP 에해당하는 m 개의목록만을포함한다. 또한 G-BSM 을전송받은그룹멤버의 DR 은해당 C-RP 들중하나의 RP 를선정하여 Join 함으로써기존의방식에서와동일한서비스를 제공할수있게된다. 3.2 그룹생성과 Group-Bootstrap Router 재선정 전체네트워크를대상으로하나의 BSR 을선정하는기존 PIM- SM 과는달리제안한 G-BSR 선정기법은그룹단위의 G-BSR 과 C- RP 들로그룹단위마다컨트롤메시지가구분된다. 따라서그룹간의 23
데이터를송수신하고자할경우, 통신하고자하는그룹들의현재 RP 는새로운그룹의서비스를위해서 RP 의재선정이필요하다 [10]. Group 1 Group 2 C-RP C-RP C-RP G-BSR A-BSR G-BSR C-RP C-RP C-RP All-Bootstrap Message [ 그림 3-4] A-BSM 의분배 멀티캐스트서비스제공시그룹과그룹이 Join 하고자하는경우, 새로운그룹주소를할당받게된다. 이때 [ 그림 3-4] 와같이해당그룹의 G-BSR 들은 A-BSR 로부터 A-BSM 를전송받음으로써, 전체네트워크에존재하는모든그룹과해당 C-RP 들의관련정보를수신하게된다. 새롭게전송된 A-BSM 으로써, 새로운그룹으로가입하고자하는각그룹은기존의 PIM-SM 의 Bootstrap 작동방식과 RP 의선정으로멀티캐스트서비스가가능하게된다. 24
제 4 장모의실험및성능분석 4.1 모의실험환경 본장에서는 PIM-SM 작동방식에 G-BSR 방식을적용한모델을설정하여모의실험을실시하였다. 성능평가를위해네트워크에존재하는그룹수의증가와 C-RP 수의변화에따라생성되어지는 BSM 의총오버헤드를측정하였다. 또한 BSM 은전체네트워크를대상으로전송되기때문에, 전체노드의수와각노드간연결정도의변화에따라네트워크내에전송되어지는오버헤드를기존 PIM-SM 의 BSR 선정기법과비교평가하였다. 네트워크모델은기존방식의성능비교평가를위해 [8] 의실험환경으로구성하였으며실험파라미터는 [ 표 4-1] 과같다. [ 표 4-1] 모의실험파라미터 종류 변수범위 전체라우터의수 50 ~ 200( 개 ) 존재하는그룹의수 5 ~ 20( 개 ) 노드간의연결정도 2 ~ 8 각그룹마다서비스가능한 C-RP 의수 전체의라우터의 10% 이내의수 25
4.2 오버헤드비교분석 BSM 은 PIM-SM 도메인내의 C-RP-Adv 메시지를전송받아생성되는데, 이는그룹과 C-RP 들의쌍으로구성된다. 기존 PIM-SM 의생성되는하나의 BSM 크기 (Bs) 는다음과같다 [6]. 아래수식에서의 PIM- SM_Header 는 [ 그림 2-9] 에서생성되는하나의 BSM 이포함하는 PIM- SM 의패킷헤더를나타내며, 32bits 의크기를가진다. 또한 BSR_Fields 는 Fragment Tag, Hash Mask Length, BSR Priority 필드를 나타내며, 32bits 의크기를가진다. 또한각각의 BSM 은 32bits 의 Encoded Unicast BSR Address 를포함하여전체네트워크내에존재하는 모든라우터들에게정보를제공한다. Bs = PIM SM _ Header + BSR _ Fields + ( Gp + Gp Crp) Gp : 그룹의수 ( 개 ) Crp : 그룹당 C-RP 의수 ( 개 ) x 개의노드가존재하는네트워크내에 y 개의그룹이존재한다면, 네트워크내에존재하는 C-RP 의수는 x/10 이된다 [8]. 생성된 BSM 은전체네트워크로전송되며, 이때전체네트워크를대상으로전송되어지는 BSM 의총수 (Nb) 는다음과같은수식으로표현된다 [6]. 26
BSM 은 Hop by Hop 으로각노드간의연결정도만큼씩 전송되어진다. 본논문의실험에서는 BSR 과각노드들의노드간 연결정도는동일한정도를가진다고가정하였다. i bsr Nb = Dbsr + ( Dnode 1) = Dnode ( N 1) N : 전체노드의수 ( 개 ) Dbsr : BSR 의노드간연결정도 Dnode : 각노드간의연결정도 제안한 G-BSR 선정기법을이용한전체네트워크에서의 BSM 으로인한총오버헤드 (Go) 는다음과같은수식으로표현된다. 기존의방식과달리그룹단위로 G-BSM 이생성되므로, 각각의 1 개의그룹에대한 n 개의 C-RP 의목록정보가전체노드 N 을대상으로노드간의연결정도만큼씩전송된다. Go = ( Gm _ size Gm _ number) + Gm _ As Gm_size : G-BSM 의크기 (Kbytes) Gm_number : 그룹내의 G-BSM 의총수 ( 개 ) Gm_As : A-BSR 로전송되는 G-BSM 의크기 (Kbytes) 27
4.3 실험결과 전체네트워크의 BSM 오버헤드 (Kbytes) 500 450 400 350 300 250 200 150 100 50 0 2 4 6 8 10 그룹당 C-RP 수 ( 개 ) 기존 BSR 방식 G-BSR 방식 [ 그림 4-1] 그룹당서비스가능한 C-RP 수의변화량에따른비교 [ 그림 4-1] 은전체노드의수를 125, 각노드의연결정도는 5, 그룹의수는 12.5 의평균값으로설정하였다. 또한 C-RP 의수는 2 에서 10 의범위로증가시키면서실험결과를측정하였다. 기존 BSR 방식이그룹당존재하는 C-RP 의수의증가에민감하게증가되는오버헤드가제안한 G-BSR 선정기법에서는안정적인결과치를보인다. [ 그림 4-2] 는전체네트워크에존재하는그룹의수의변화에따른 결과이다. 그룹의수는 5 개에서 20 개까지증가시켰으며, 제안방식은 그룹에따라 G-BSR 이생성된다. 각각의그룹내의 C-RP Adv 메시지는 그룹단위로분배되며, 이를바탕으로 G-BSM 이생성되기때문에 그룹의수가증가됨에따른전체네트워크의 BSM 오버헤드는 기존방식에비해감소됨을보였다. 28
전체네트워크의 BSM 오버헤드 (Kbytes) 1000 900 800 700 600 500 400 300 200 100 0 5 10 15 20 그룹수 ( 개 ) 기존 BSR 방식 G-BSR 방식 [ 그림 4-2] 전체네트워크에존재하는그룹수의증가량에따른비교 전체네트워크의 BSM 오버헤드 (Kbytes) 5000 4500 4000 3500 3000 2500 2000 1500 1000 500 0 50 100 150 200 전체노드수 ( 개 ) 기존 BSR 방식 G-BSR 방식 [ 그림 4-3] 전체네트워크에존재하는노드수의변화량에따른비교 29
전체네트워크의 BSM 오버헤드 (Kbytes) 1000 900 800 700 600 500 400 300 200 100 0 2 4 6 8 노드간연결정도 기존 BSR 방식 G-BSR 방식 [ 그림 4-4] 각노드간연결정도의변화량에따른비교 [ 그림 4-3] 은전체노드수를 50 에서 200 까지의범위에서순차적으로노드의수를 50 개의단위로추가하면서실험한결과이다. 또한 [ 그림 4-4] 는노드간의연결정도를 2 에서 8 까지변경시키면서실험한결과이다. 전송되어지는전체네트워크의 BSM 총수는전체노드의수와노드간연결정도의변화에직접적인관련이있다 [6]. 이는 RPF 검사를수행하여수신되어진 BSM 은해당라우터의수신인터페이스를제외한모든인터페이스로각노드들간의연결정도만큼전송되어지기때문이다. 또한이러한수행은네트워크에존재하는전체노드들의수만큼반복되어진다. 네트워크내에적은수의노드가존재할경우기존의방식과제안한 G-BSR 선정방식은큰차이가없다. 하지만, 노드의수가많아질수록제안방식의오버헤드감소는 30
뚜렷하게나타난다. 제 5 장결론 기존의멀티캐스트라우팅방식은트리구성방식에따라소스기반트리와공유트리로나뉜다. 공유트리방식으로확장성측면에서우수한 PIM-SM 은화상회의등의협동형서비스에적합하며, RP 를선정함으로써하나의트리를공유하여데이터를송수신한다. 또한 Bootstrap 작동방식에따라 C-RP 의정보를수집하며, RP 선정을위해컨트롤메시지인 BSM 을생성및전송한다. 이는그룹과 C-RP 의수에비례하여해당도메인내에오버헤드를증가시키는문제점을발생시킨다. 본논문에서는기존의 PIM-SM 라우팅프로토콜을이용하는 멀티캐스트서비스모델을가정하고, 그룹마다하나의 G-BSR 을 선정하는방식을적용하였다. 제안방식은 G-BSM 의전송범위를해당그룹내부로제한함으로써, 컨트롤메시지로인한오버헤드량을줄인다. 이는기존의방식에별도의수정없이사용가능하였으며, DR 의 C- RP 목록처리시 RP 선정에용이성을제공한다. 또한그룹의생성및탈퇴에따른동적인서비스가가능하였다. 모의실험을통한기존방식과의비교측정결과, 제안방식이 그룹과 C-RP 수의변화에비례하여발생되어지는오버헤드의증가 문제를크게개선하였으며, 비교적안정적인증가치를나타냄을보였다. 또한전체네트워크를대상으로전송되어지는 BSM 은전체노드의 수와노드간연결정도와밀접한관련이있다. 이에대한각각의요소에 31
따른결과도제안방식이비교적낮은오버헤드를보였으며, 회선의 효율성을높일수있음을입증하였다. 참고문헌 [1] Maufer, T. A., Deploying IP Multicast in the Enterprise, 1st Ed., Prentice- Hall Inc., New Jersey, 1998. [2] Billhartz, T., Cain, J. B., Farrey-Goudreau, E., Fieg, D., and Batsell, S. G., "Performance and Resource Cost Comparisons for the CBT and PIM Multicast Routing Protocols," IEEE Journal on Selected Areas in Communications, Vol.15, No.3, pp.304-315, Apr 1997. [3] D. Estrin, D. Farinacci, "Protocol Independent Multicast-Sparse Mode (PIM-SM): Protocol Specification," RFC 2362. [4] Microsoft Windows 2000 server, PIM-SM Multicast Routing Protocol, Microsoft, White Paper. [5] Bill Fener, Mark Handley, Roger Kermode, David Thaler, "Bootstrap Router (BSR) Mechanism for PIM Sparse Mode," Internet-Draft, Feb 2003. [6] Deborah Estin, Mark Handley, Ahmed Helmy, Polly Huang, "A Dynamic Bootstrap Mechanism for Rendezvous-based Multicast Routing," Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings, Vol.3, pp.1090-1098, Mar 1999. [7] Seiji Ueno, Toshihiko Kato, Kenji Suzuki, "Analysis of Internet multicast traffic performance considering multicast routing protocol," 2000 32
International Conference on Network Protocols, pp.95-104, Nov 2000. [8] Hwa-Chun Lin, Zhe-Hong Lin, Selection of Candidate Core for Core- Based Multicast Roution Architectures, IEEE International Conference on, Vol.4, pp.2662-2666, 2002. [9] S.J. Koh, J.S. Park, G.S. Kim, Y.J. Kim, Analysis of Internet Multicast Routing Protocols, 전자통신동향분석제 14 권제 5 호, pp 99-110, Oct 1999. [10] Dong-Lim Lee, Chan-Hyun Youn, Sang-Jin Jeong, RP Reselection Scheme for Real-Time Applications in Delay-Constrained Multicast Networks, IEEE ICC2002, New York, April 2002. [11] D. Waitzman, C. Partridge, "Distance Vector Multicast Routing Protocol," RFC1075, Nov 1988. [12] J. Moy, "Multicast Extensions to OSPF," RFC1584, Mar 1994. [13] A. Ballardie, "Core Based Trees (CBT version 2) Multicast Routing: Protocol Specification," RFC2189, Sep 1997. 33
34
감사의글 해가바뀜을거듭하여 2003 년의마지막계절인겨울이왔습니다. 2 년이라는시간동안연구실에서지내며많은일들이있었지만, 선배님, 후배, 그리고동기들과함께지낸시간들이저에겐너무나도소중하고기억에남는추억이될것입니다. 이글을빌어무사히논문을작성하고졸업할수있도록도와주신모든분들에게감사드립니다. 특히저를나아주시고길러주신소중한부모님, 힘든순간저에게많은힘이되어준동기들인영조, 제원, 민경, 제논문에많은관심과격려를하여주셨던교철이형과재우형, 그리고항상굳건하게제자리를지킬수있도록따뜻한격려를아끼지않았던저의예쁜여자친구지영이에게많은고마움을느낍니다. 또 2 년간올바른지도와격려를아끼지않으신이균하교수님께도무한한감사의인사를드립니다. 그리고동고동락을항상함께하였던연구실의맏형인인구형, 정민, 승찬, 주성씨에게도감사의맘을전하며, 앞으로 2 년간의연구실생활을시작하게될호선, 익래, 왕봉이도모두좋은논문으로높은학업의성과를거두기를바랍니다. 또졸업후에도간접적으로나마많은격려를해주었던영호와경호에게도감사의마음을전합니다. 오는 2004 년에는더더욱활기찬모습으로우리연구실가족모두에게 즐겁고따뜻한일들만가득한최고의한해가되기를기원합니다. 다시한번 감사의맘을전하며이글을마치고자합니다. 2003 년 12 월 29 일 염진호