논문 07-32-3-09 한국통신학회논문지 07-3 Vol. 32 No. 3 이동애드혹네트워크를위한인터넷프로토콜주소자동설정기법 학생회원최낙중 *, 준회원정어진 **, 정회원김동균 ***, 최양희 **** IP Address Auto-configuration for Mobile Ad Hoc Networks Nakjung Choi* Student Member, Uhjin Joung** Associate Member, Dongkyun Kim***, Yanghee Choi**** Regular Members 요 약 우리는이동애드혹네트워크에서인터넷프로토콜을위한세가지의주소자동설정기법을소개한다. RADA (Random ADdress Allocation) 는무작위로 IP 주소를선택하는방법이고, LiA (Linear Address Allocation) 는최대 IP 주소를사용하여순서대로새로운주소를할당하는방법이다. LiACR (Linear Address Allocation with Collision Resolution) 이라고칭하는 LiA의확장된방법은제어메시지의오버헤드를줄이는방법을사용하였다. 짧은시간동안다수의노드들이네트워크에들어오게되면 RADA는 LiA나 LiACR 보다훨씬빠르게주소를할당할수있다. 하지만 RADA는주소공간을비효율적으로사용하게된다. 즉, RADA 는특히전장이나위급상황에서긴급한주소설정이필요할경우유용하다. 반면에 LiA나 LiACR은네트워크크기가크고, 닫힌형태이며, 관리제어의형태로종속되는이를테면, 무선서비스제공자에의해조정되는애드혹네트워크에더적합하다. Key Words : IP Address Auto-Configuration, Ad Hoc Address Acquisition, Address Conflicts, Resolution Schemes ABSTRACT We introduce two distributed IP address auto-configuration mechanisms for mobile ad hoc networks. RADA (Random ADdress Allocation) is based on random IP address selection, while LiA (Linear Address Allocation) assigns new addresses sequentially, using the current maximum IP address. An improved version of LiA, known as LiACR (Linear Address Allocation with Collision Resolution) further reduces the control overhead. Simulation results show that, when many nodes join a network during a short period, RADA assigns addresses more quickly than LiA and LiACR. However, RADA uses the address space less efficiently, due to its random allocation of IP addresses. Hence, RADA is particularly useful in battlefield scenarios or rescue operations where fast setup is needed, while LiA and LiACR are more suitable for ad hoc networks that are moderate, confined and subject to some form of governance control, such as that orchestrated by a wireless service provider. 이논문또는저서는 2005 년정부 ( 교육인적자원부 ) 의재원으로한국학술진흥재단의지원을받아수행된연구임 (KRF-2005-003-D00295). 또한, 본연구는 2006 년두뇌한국 21 프로젝트지원을받아서수행되었음. * 서울대학교컴퓨터공학부 (fomula@mmlab.snu.ac.kr), ** 경북대학교컴퓨터공학과 (ujjoung@monet.knu.ac.kr) *** 경북대학교컴퓨터공학과 (dongkyun@knu.ac.kr), **** 서울대학교컴퓨터공학부 (yhchoi@mmlab.snu.ac.kr) 논문번호 :KICS2006-05-248, 접수일자 :2006 년 5 월 30 일, 최종논문접수일자 :2007 년 3 월 12 일 297
한국통신학회논문지 07-3 Vol. 32 No. 3 Ⅰ. 서론이동애드혹네트워크 (MANET) [1] 에서는제한된전송범위를지닌일련의무선노드들이미리구축된기반구조없이동적으로네트워크를구성한다. 전송범위를벗어나직접적인통신이불가능한노드와는멀티홉전송을통하여통신이가능하다. 따라서이동애드혹네트워크분야의연구는대부분효율적인멀티홉전송을지원하기위해라우팅문제를해결하고자하였다. 그예로, DSR (Dynamic Source Routing), ABR (Associativity Based Routing), AODV (Ad-hoc On-demand Distance Vector), TORA (Temporally Ordered Routing Algorithm) 등의특화된멀티홉경로설정프로토콜들이제안되었다. 그러나이런라우팅프로토콜들은기본적으로모든노드에게이미유일한 IP 주소가할당되어있다는것을가정하고있다. 따라서본논문은자동화된네트워크구성이라는측면에서이동애드혹네트워크에서의 IP 주소자동설정문제를해결하고자한다. 오늘날인터넷에서사용되고있는 IP 주소는일반적으로 (a) 전역적 IP 주소와 (b) 지역적 IP 주소, 두가지로나눌수있다. 전자는인터넷의모든노드들에대해유일한 IP 주소이고, 후자는서브네트워크내의 `고립 ' 된지역에서만유일한 IP 주소이다. 지역적 IP 주소가할당된노드가인터넷에서동작하기위해서는전역적 IP 주소와매핑하는과정이필요하다. 표 1은이동애드혹네트워크에서전역적 IP 주소와지역적 IP 주소의장단점을비교한다. 일반적으로새로운노드의 IP 주소는 (a) 미리설정되거나, (b) DHCP (Dynamic Host Configuration Protocol) 를사용하여동적으로할당되거나, (c) 자동설정기법을사용하여할당된다. 미리설정하는방법과 DHCP를사용한동적할당방법은노드가이동하는이동애드혹네트워크에서비현실적이다. 따라서최근에이동애드혹네트워크에서주소자동설정에대한중요성이인식되고있다. 이동애드혹네트워크의완벽한구현과실제배치가이루어지기위해서는효율적인동적경로설정방법과동시에주소자동설정기법이필요하다. 본논문에서는이동애드혹서브네트워크에서 IP 주소자동설정을위한두가지새로운기법을소개한다. 본논문은다음과같은순서로구성된다. 2장에서는주소설정관련연구를요약하고, 3장에서는 RADA, LiA, LiACR 기법들을제안한다. 4장에서는제안된기법들에대한정성적, 정량적인분석을 표 1. 전역적 / 지역적 IP 주소의장 / 단점. Table 1. Global/Local IP Address Assignments Pros/Cons 전역적 IP 주소 지역적 IP 주소 장점 단점 용이한구현 IP 주소재사용불가 ( 확장성 ) 주소충돌이거의없음 확장성 서브네트워크간 IP 주소할당조정자필요없음 서브네트워크간주소재사용가능 서브네트워크간 IP 주소할당조정자필요 복잡한구현 게이트웨이의전역 / 지역주소간매핑필요 (NAT 기능 ) 수행하고, NS-2 모의실험을통한성능평가결과가 5장에서논의된다. 마지막으로, 6장에서결론을맺는다. Ⅱ. 관련연구 최근들어, 이동애드혹네트워크연구분야에서주소자동설정기법은큰주목을받고있다. 본장에서는국제표준화기구인 IETF에서현재표준화진행중인주소자동설정과관련된기법들에대해살펴보고, 기존관련연구에서제안된대표적인주소자동설정기법에대해간략히언급한다. 2.1 표준화진행동향 IETF의 MANET 워킹그룹에서주소자동설정관련이슈들을해결하기위한기법 [2][3][4] 들이제안되었으며, 중복주소감지 (DAD) 를위해간단한플러딩방법 [2] 이제안되었다. 또한, 네트워크분리나병합을효율적으로지원하기위한 DAD 기법들 [5][6] 도제안되었다. 상태비보존 (stateless) IPv6 주소자동설정방법 [6] 은 IPv6 워킹그룹에서논의되었으며, 링크-지역적주소를생성하는과정을정의한다. 먼저노드는널리알려진링크- 지역적프리픽스와해당네트워크인터페이스의 MAC 주소를사용하여링크- 지역적주소를생성한다. 그러나생성된링크 -지역적주소가다른노드에의해서이미사용중일수도있기때문에이웃탐지프로토콜 (NDP) 을사용하여확인과정을거쳐야한다. 생성된주소가링크내에서유일하다는것이보장되면, 노드는실제그링크- 지역적주소를사용하여통신이가능하다. 만약유일하다는것이보장되지않는다면, 자동설정을멈추고해당네트워크인터페이스의수동설정을요구한다. 이러한접근방식은한홉통신으로제한되어있고, 298
논문 / 이동애드혹네트워크를위한인터넷프로토콜주소자동설정기법 멀티홉통신을필요로하는이동애드혹네트워크에는적합하지않다. 이동애드혹네트워크에이기법을적용하기위해서는멀티홉동작이가능하도록 DAD 동작과정의확장이필요하다. 또한, 최근조직된 AUTOCONF [7] 워킹그룹은 MANET 워킹그룹으로부터주소자동설정과관련된이슈를넘겨받아더욱활발히논의를진행하고있다. Ⅲ. 자동주소설정기법 본논문은이동애드혹네트워크의 IP 주소자동설정을위한두기법을제안한다. 두기법의주요한차이는후보 IP 주소의선택과유일성확인방법이다. 이동애드혹네트워크에서전역적인정보를교환하기위해브로드캐스팅이나플러딩의사용은피할수없다. 3.1 임의주소할당기법 (RADA) RADA 기법은새로운노드가네트워크관리자에의해설정된서브네트워크범위 (First_PERM_ ADDR ~ 65,355) 내에서임의로주소를선택하여반영구적인지역적 IP 주소 (permanent IP address) 로사용하는프로토콜이다. 새로운노드는선택한지역적 IP 주소의중복확인을위해사용할임시 IP 주소 (temporary IP address) 를나머지범위 (1 ~ First_PERM_ADDR) 내에서추가적으로선택한다. 임시 IP 주소는주소설정과정동안만해당노드의 IP 주소로사용되며, 지역적 IP 주소의중복확인이끝나면더이상사용하지않는다. 지역적 IP 주소의중복확인을위해새로운노드는먼저주소질의 (AQ) 패킷을서브네트워크에브로드캐스트한다. AQ 패킷포맷은그림 1과같다. 이때, 해당노드는 AGE 필드를 0으로설정한다. AQ 패킷전송후, AQ 타이머를시작하고주소응답 (AR) 패킷을기다린다. 노드가 AQ 패킷을받으면, 먼저그패킷이이미처리되었는지를알기위하여자신의 AQ 수신테이블을확인한다. 만약이미처리된패킷이었다면, 해당 AQ 패킷을버린다. 그렇지않다면, 해당 AQ 패킷에대한정보를 AQ 수신테이블에추가하고, AQ 그림 1. AQ 패킷포맷. Fig 1. AQ Pacekt Format 패킷내의요청된 IP 주소 (requested IP address) 를자신의 IP 주소와비교한다. 노드의지역적 IP 주소가 AQ 패킷내의요청된 IP 주소와동일하지않다면단순히해당 AQ 패킷을다른노드들에게포워딩하고, 동일하다면 AQ 패킷내의 AGE 값과자신의 IP 주소타이머를비교하여아래와같이처리한다. 1) 노드의 IP 주소타이머가 AQ 패킷내의 AGE 값보다큰값을가지면, 자신의 IP 주소를유지하고, AQ 패킷을보낸노드가해당지역적 IP 주소에대한요청을취소할수있도록주소응답 (AR) 패킷을보낸다. 2) 노드의 IP 주소타이머가 AQ 패킷내의 AGE 값보다작은값을가지면, 해당지역적 IP 주소의사용을포기하고, 새로운지역적 IP 주소획득을위한주소할당과정을시작한다. 3) 노드의 IP 주소타이머와 AQ 패킷내의 AGE 값이모두 0이면, 양쪽모두요청한 IP 주소를사용하지않는다. 해당노드는 AR 패킷을 AQ 패킷을보낸노드에게보내어지역적 IP 주소의충돌을알린다. 또한, 해당노드도지역적 IP 주소를버리고, 새로운지역적 IP 주소획득을위한주소할당과정을시작한다. 주소할당과정에서 AQ 패킷을보낼때시작한 AQ 타이머가만료할때까지 AR 패킷을받지못하면, AQ 패킷을다시브로드캐스트한다. 이과정는미리설정된값인 AQ_RETRIES 만큼반복되거나, AR 패킷을받을때까지반복된다. 만약 AQ_RETRIES 횟수만큼반복하여도 AR 패킷을수신하지못하였다면, 새로운노드는요청된지역적 IP 주소를자신의주소로설정한다. 그리고 AGE 카운터를증가시키기위해자신의 IP 주소타이머를시작한다. AGE 필드는 4,660까지의값을표현할수있다. RADA 기법은주소충돌해결프로토콜 (ACRP) 을사용하지않으면신뢰성없는무선환경에서주소의유일성을보장할수없다. 각노드는주기적으로 AQ 패킷을브로드캐스트하여사용중인지역적 IP 주소의충돌을확인한다. 지역적 IP 주소를획득한후, ACRP 타이머가시작되고, 각노드는 ACRP 주기마다해당노드의지역적 IP 주소와 IP 주소타이머값을포함하는 AQ 패킷을브로드캐스트한다. 이러한값들은주소충돌을확인하는데사용된다. 노드가자신이사용하고있는지역적 IP 주소와동일한요청된 IP 주소를가진 AQ 패킷을받으면, 299
한국통신학회논문지 07-3 Vol. 32 No. 3 AQ 패킷을보낸노드에서주소충돌을알리기위해현재 IP 주소타이머값을 AGE 필드에포함한 AR 패킷을보낸다. AR 패킷포맷은그림 2와같다. 는즉시주소할당과정을시작해야한다. 그림 3은 RADA 기법에서의동작에대한간략한흐름도를나타낸다. 그림 2. AR 패킷포맷. Fig 2. AR Packet Format. (a) RADA 주소요청. (a) RADA Address Request 3.2 선형주소할당기법 (LiA) LiA 기법에서는새로운노드가이동애드혹네트워크에참여하려면먼저네트워크로부터비콘메시지를기다리게된다. 특정시간동안비콘메시지를받지못하면, 자신을네트워크의초기노드로인식하고가능한지역적 IP 주소공간내에서첫번째주소를자신의주소로사용한다. 만약네트워크에이미다른노드들이존재한다면, 새로운노드는네트워크에서사용되고있는 `최대 IP 주소 (Max.IP)' 정보가포함된비콘메시지를듣게되고, Max.IP + 1을자신의후보 IP 주소로선택한다. LiA 기법은 RADA 기법과는다르게후보 IP 주소선택과주소충돌해결을위하여 AQ 패킷이나 AR 패킷을사용하지않고, 그림 4의공통포맷을가진세가지제어메시지들을사용한다. 그림 4. LiA 기법에서사용하는제어메시지의공통포맷 Fig 4. The common format of control messages in LiA (b) RADA 주소충돌해결. (b) RADA Address Collision Resolution 그림 3. RADA 기법. Fig 3. Random Address Allocation (RADA). AQ 패킷을보낸노드가 AR 패킷을받았을때주소충돌을나타내는세가지경우에따라아래와같이처리한다. 1) AR 패킷의 AGE 값이노드의 IP 주소타이머보다큰값을가지면, 노드는해당지역적 IP 주소가이미사용되고있다는것을알고, 주소할당과정을다시시작한다. 2) AR 패킷의 AGE 값이노드의 IP 주소타이머와동일한값을가지면, 이웃노드들로부터자신이보낸 AR 패킷을되돌려받을경우이기떄문에해당 AR 패킷을버린다. 3) AR 패킷의 AGE 값이노드의 IP 주소타이머보다작은값을가지면, ACRP 과정에서주소충돌의발견을의미하기때문에해당노드 LiA 기법의제어메시지는 2-비트 TYPE 필드의값에따라 BEACON, ANNOUNCE, WINNER 메시지로구분된다. AGE 필드의역할은 RADA 기법과유사하고, 식별자필드는각노드의유일한식별자를나타내는것으로 MAC 주소등을사용할수있다. 세가지제어메시지의역할은아래와같다. 1) BEACON TYPE 필드가 0으로설정되면, 해당제어메시지는 BEACON 메시지이다. 네트워크에서사용중인가장큰 IP 주소를가진노드는주기적으로자신의 IP 주소를포함한 BEACON 메시지를브로드캐스트한다. 따라서새로운노드는현재네트워크에서사용중인 IP 주소에대한정보를얻을수있다. 2) ANNOUNCE TYPE 필드가 1로설정되면, 해당제어메시지는 ANNOUNCE 메시지이다. 새로운노드가후보 IP주소를선택한후, 요청된 IP 주소필드에자신의후보 IP 주소를넣어 ANNOUNCE 메시지를브로드캐스트한다. ANNOUNCE 메시지를통해다른노드가동 300
논문 / 이동애드혹네트워크를위한인터넷프로토콜주소자동설정기법 일한 IP 주소를후보 IP 주소로선택하였다는것을알수있다. 3) WINNER TYPE 필드가 2로설정되면, 해당제어메시지는 WINNER 메시지이다. 둘이상의노드들이동일한 IP 주소를사용하려한다면, 해당주소를얻기위한경쟁이필요하다. 주소충돌해결과정을통해승리한노드는분쟁한 IP 주소를자신이사용한다는것을알리기위해 WINNER 메시지를브로드캐스트한다. 나머지노드들은다시주소할당과정을거치게된다. BEACON 메시지를기다린다. 자신의후보 IP 주소와동일한요청된 IP 주소값을가지는 WINNER 메시지를수신하면, ANNOUNCE 메시지처리과정과동일하게식별자비교를통해주소할당과정을재시도한다. LiA 기법에서는새로운노드가주소할당을위해 (a) 후보 IP 주소, (b) 할당된 IP 주소, (c) 최대 IP (Max.IP) 주소의세가지변수들을유지한다. 노드는후보 IP 주소변수에지역적 IP 주소후보를저장하고, 해당지역적 IP 주소의유일성이보장되면할당된 IP 주소변수에저장하고, 실제통신을시작한다. 네트워크에서사용주인최대 IP 주소는최대 IP 주소변수에저장한다. 그림 5는 LiA 기법의동작과정을간략히보여준다. 새로운노드는먼저주소할당타이머를전송지연시간의 5배정도로설정한다. 만일그주소할당타이머가만료될때까지 BEACON 메시지를받지못한다면, 네트워크의초기노드가되어사용가능한 IP 주소공간에서첫번째 IP 주소를자신의 IP 주소로설정하고, 다른새로운노드들을위해주기적으로비콘메시지를브로드캐스트한다. 그러나주소할당타이머가만료되기전에비콘메시지를받으면, 자신의후보 IP 주소를비콘메시지에포함된 Max.IP 값보다 1이큰값으로설정한다. 그리고자신의후보 IP 주소를포함한 ANNOUNCE 메시지를브로드캐스트한다. 특정시간동안다른제어메시지를받지못한다면, 후보 IP 주소를자신의 IP 주소로사용하게되고, BEACON 메시지를주기적으로브로드캐스트한다. 새로운노드가다른노드로부터 ANNOUNCE 메시지를들었을경우, 먼저자신의후보 IP 주소와 ANNOUNCE 메시지의요청된 IP 주소를비교한다. 만약동일하다면, 자신의식별자와 ANNOUNCE 메시지의식별자를비교한다. 만약자신의식별자의우선순위가높으면, WINNER 메시지를보내고, 주소할당타이머가만료될때까지다른제어메시지를기다린다. 만약자신의식별자우선순위가낮다면, 자신의후보 IP 주소를취소하고, 다시 (a) LiA 주소요청 (a) LiA Address Request (b) LiA 주소충돌해결 (b) LiA Address Collision Resolution 그림 5. LiA 기법 Fig 5. Linear Address Allocation (LiA). 301
한국통신학회논문지 07-3 Vol. 32 No. 3 새로운노드는주소할당과정이성공적으로종료되면, 자신의지역적 IP주소 ( 새로운최대 IP 주소 ) 를다른노드들에게알리기위한 BEACON 메시지를주기적으로브로드캐스트한다. 이전에 BEACON 메시지를보내던노드는자신의지역적 IP 주소보다 BEACON 메시지의요청된 IP 주소가더큰값을가지고있기때문에더이상네트워크의최대 IP 주소를사용하는노드가아니라는것을알수있다. 따라서기존의 Max.IP에해당하는주소를사용하던노드는자신의 Max.IP 정보를수정하고, BEACON 메시지를브로드캐스트하는것을멈춘다. LiA 기법에서 ACRP 과정은주소중복발견과해결의두과정으로구성되어있다. 새로운노드는자신의 IP 주소후보를선택하고, 그주소를사용하기위하여 ANNOUNCE 메시지를브로드캐스트한다. 그리고주소할당타이머를시작하여주소중복발견과정으로들어가게된다. 만약설정한주소할당타이머가만료되기전에동일한 IP 주소를포함한다른제어메시지 (ANNOUNCE 메시지나 WINNER 메시지 ) 를받는다면, 주소충돌이명백해지고해당노드는주소충돌감지단계에서주소충돌해결단계로자신의상태를변경한다. 이때, 승리한노드와나머지노드들은노드들의식별자를기반으로구별된다. 3.3 효율적충돌해결을위한선형주소할당기법 (LiACR) LiA 기법에서다수의새로운노드들이자신들의 ANNOUNCE 메시지들을보낼때, 요청된 IP 주소가동일하고자신들보다우선순위가높은식별자를가진제어메시지를받으면, 해당노드들은즉시주소할당과정을재시작해야한다. 그러나이경우, 그들모두가새로운 MAX.IP+1 주소에대해경쟁하게되고, 하나의노드만이승리하는과정을반복하게된다. 이런문제점을해결하기위해 LiACR 기법에서는 ANNOUNCE 메시지를보내고미리정의된기간 (S) 동안다른 ANNOUNCE 메시지를기다리게된다. 이기간동안수집한모든 ANNOUNCE 메시지정보를종합하여식별자가가최소인노드가승리자가되어 WINNER 메시지를브로드캐스트하고, 후보 IP 주소를자신의 IP 주소로사용하게된다. 반면에, 경쟁에서패배한노드들은자신의후보 IP 주소를 1 만큼증가시키는것이아니라, 수집된 ANNOUNCE 메시지중에서자신의식별자우선순위만큼증가시킨다. 그후, 모든패배자들은자신의 IP 주소를결정하기위해 ANNOUNCE 메시지를브로드캐스트하고, 주소할당타이머를재설정한다. 주소할당타이머가만료될때까지더이상다른주소충돌이발생하지않으면, 해당후보 IP 주소를자신의 IP 주소로사용하게된다. 그러나추가적인주소충돌이발생하게되면, 위과정을반복한다. 예를들어, 노드 A, B, C가동시에네트워크에들어왔고, 노드 A가가장높은우선순위를가지고, 노드 C가가장낮은우선순위를가진다고가정한다. 모든노드들은비콘메시지를받고, 자신의 ANNOUNCE 메시지를거의동시에보낸다. 제어메시지수집기간인 S 시간후, 각노드는같은 IP 주소를요청한다른노드들의정보를알게된다. 우선순위에따라노드 A가승리하게되고, WINNER 메시지를보낸다. 다음제어메시지수집기간 S 동안주소충돌이발생하지않고, 노드 A는후보 IP 주소를자신의 IP 주소로사용한다. 반면에노드 B는후보주소를 1만큼, 노드 C는후보주소를 2 만큼증가시켜새로운 ANNOUNCE 메시지를보낸다. 따라서 LiACR 기법은노드 A, B, C가최소한의제어메시지만을사용하여 IP 주소를할당할수있다. 3.4 네트워크분리와결합이동애드혹네트워크시나리오에서는네트워크분리와병합이빈번하게발생한다. 네트워크분리는다수의노드들이이탈할때일어날수있다. 따라서네트워크분리에대한정보가정상적으로알려지지않는상황에서는 IP 주소자동설정방법이분리된하나의네트워크내에서유일한주소들을최대한보장하면서도사용되지않는주소를재사용할수있어야한다. 또한네트워크가병합될때에는주소의충돌이일어날수있다. 이것은잘못된라우팅경로설정등의문제를발생시키게된다. 그러므로네트워크병합은빨리감지되고해결되어야한다. RADA 기법에서는 ACRP 동작이네트워크가결합할때의주소충돌을해결하기위해사용된다. ACRP 동작은네트워크분리나병합등의특정이벤트를인식할수는없지만, 주소충돌을해결할수있다. 분리된두네트워크가병합되면, 주기적으로보내는 AQ 패킷의 AGE 필드값을통해 ACRP 주기내에중복주소가발견되고해결된다 ( 그림 3). LiA 기법이나 LiACR 기법에서는네트워크분리 302
논문 / 이동애드혹네트워크를위한인터넷프로토콜주소자동설정기법 와병합시나리오를지원하기위해기본알고리즘을아래와같이조금수정한다. 1) 네트워크의초기노드는 IP 주소공간의첫번째 IP 주소가아닌임의의시작 IP 주소를선택한다. 해당시작 IP 주소로부터새로운노드들은순차적으로 IP 주소를할당받는다. 2) 시작노드에의해네트워크식별자가임의로생성되어 BEACON 메시지에포함되거나헬로우 (hello) 메시지에포함된다. 새로운노드는해당메시지의네트워크식별자를통해네트워크를구분할수있다. 3) 현재 Max.IP 주소가할당된노드는이전의 Max.IP 주소, 즉현재 Max.IP - 1 주소를가진노드와의통신으로해당네트워크의시작 IP 주소를알수있다. 4) 주소쉬프트오프셋필드를포함하는새로운 SHIFT 제어메시지를정의한다. 노드가 SHIFT 제어메시지를받을때, 자신의현재의 IP 주소를주소쉬프트오프셋만큼증가시켜새로운자신의 IP 주소로사용한다. 두네트워크가접근하게되면가장자리에위치한노드들은다른네트워크식별자를포함하는 BEACON 메시지를듣게된다. 두네트워크의가장자리에위한노드들은서로협상을통해각네트워크의시작 IP 주소와 Max.IP 주소정보를교환하고, 중복되는 IP 주소범위를계산하게된다. 중복되는구간이없다면, 두네트워크의 Max.IP 주소중큰값을 Max.IP 주소로사용하게된다. 중복되는구간이존재한다면, 낮은우선순위를가진네트워크에중복되는구간정보를포함한 SHIFT 메시지를보내어새로운 IP 주소를설정하도록한다. 낮은우선순위를가진네트워크내의모든노드는새로운 Max.IP 주소를가진노드의 BEACON 메시지를통해새로운네트워크식별자를부여받게된다. 그림 6은 LiA 기법과 LiACR 기법의간략한병합과정이단계별로나타내고있다. 다른네트워크로부터받은패킷들은모든주소충돌이해결될때까지전달되지않아야한다. 즉, 중복된주소가완전히해결되기전에다른네트워크의경로설정에참여하지않는다. 또한네트워크병합시더욱효율적인주소충돌해결을위해현재적은수의통신이진행중인네트워크에 SHIFT 메시지를브로드캐스트할수도있다. 그림 6. LiA 기법과 LiACR 기법의네트워크병합. Fig 6. Network Merge in LiA and LiACR. Ⅳ. RADA 와 LiA 의분석 4.1 정성적비교 RADA 기법과 LiA 기법의주요한차이점은노드가자신의후보 IP 주소를선택하는방법이다. RADA 기법에서새로운노드는자신의후보 IP 주소를임의로선택한다. 192.254/16 프리픽스를가진 IP 주소공간의이동애드혹네트워크가약 1,300 개노드들로구성되어있다면, 새로운노드가이미사용되고있는 IP 주소를선택할확률은 0.02이다. 즉, 98% 의확률로새로운노드가주소충돌없이 IP 주소를획득할수있다. LiA 기법에서는네트워크에서가장큰 IP 주소를사용하는노드가주기적으로 BEACON 메시지를브로드캐스트한다. 새로운노드는이메시지를듣고, 사용중인가장큰 IP 주소보다하나큰주소를자신의 IP 주소로사용하려고시도한다. IP 주소는노드식별자의우선순위에따라순차적으로할당된다. 그러나여러노드들이동시에네트워크에들어오는경우에는모든노드가 BEACON 메시지를받고, 거의동시에 ANNOUNCE 메시지를브로드캐스트하기때문에문제가발생하게된다. 이문제는 LiACR 기법에서미리정의한기간 (S) 동안에제어메시지들을수집하여후보 IP 주소를선택시다른노드의정보를활용함으로써해결할수있다. 경쟁에서승리한노드는하나뿐이고, 나머지노드들은충돌없이자신의 IP 주소를얻을때까지이과정을반복하게된다. 303
한국통신학회논문지 07-3 Vol. 32 No. 3 표 2. 특성비교 Table 2. Comparison of Characteristics 특성 RADA LiA LiACR 메시지오버헤드 적당낮음낮음 ( 적당 ) ( 높음 ) ( 적당 ) 주소공간활용비율 적당 높음 높음 동작복잡도 낮음 적당 적당 메모리요구치 낮음 적당 적당 표 2는 RADA, LiA, LiACR 기법의대표적특성의상대적인비교를보여준다. RADA 기법이 4 번의 AQ 패킷을브로드캐스트하는데비해 LiA와 LiACR 기법은 BEACON 메시지를받은후에 ANNOUNCE 메시지를한번브로드캐스트한다. 그러나충분히큰가용주소공간을가진상황에서는다수의노드들이동시에도착하면 RADA 기법이훨씬적은제어메시지오버헤드를가진다. LiA 기법에서는동시에도착한노드들이동일한주소를요청하게되어, 일정시간동안제어메시지를기다리는 LiACR 기법에비해훨씬많은주소충돌이발생한다. 주소공간활용비율의관점에서는 LiA 와 LiACR 기법은 RADA 기법보다나은성능을보인다. 즉, RADA 기법은사용중인 IP 주소의수가늘어날수록새로운노드들이선택하는주소의충돌확률이높아진다. 그외의특성들은 RADA, LiA, LiACR 기법이비슷한성능을보인다. RADA 기법은모든가용 IP 주소를사용할수없다는문제가있다. 네트워크관리자는 First_ PERM_ADDR 인자를작은값으로설정하여임시 IP 주소의수를줄일수는있지만, 이것은임시 IP 주소의충돌가능성을높이고주소할당시간을길어지게한다. 만일 IP 주소공간이작으면, IP 주소를순차적으로할당하기때문에 LiA와 LiACR 기법의성능이좋다. 4.2 정량적비교 4.2.1 RADA 분석 가 AQ 타임아웃시간내에 AR 패킷을받지못한다면, 그과정을 3번반복한다. (AQ 재전송회수는 3번으로설정한다.) 이때 RADA 기법의평균주소할당시간 (AAT) 은아래와같이계산할수있다. AAT=(2.0 PropDelay) 4.0 네트워크에할당가능한충분한 IP 주소가있다면, 네트워크관리자는두네트워크가동일한프리픽스를사용하는것을피할수있다. 그러나동일한프리픽스를사용하더라도두네트워크가전송범위안에있다면, ACRP 동작이주소충돌문제를해결할수있다. 4.2.2 LiA 분석 그림 8. LiA 기법에서 IP 주소할당. Fig 8. IP Address Assignment in LiA. 그림 8과같은노드도착시나리오에서시간단위는전파지연 (PropDelay) 이고, 비콘간격은전파지연시간의 5배로설정되어있다고가정하자. 첫번째전파지연동안최고 IP 주소를사용하는노드는비콘메시지를브로드캐스트한다. 새로운노드는비콘메시지를기다려야하는데, 최악의경우, 4 시간유닛동안기다려야만한다. 시간 t1과 t2 사이의노드도착확률을 P(t1,t2) 라하면, LiA 의평균주소할당시간은다음과같이계산되어질수있다. AAT = (4.5 PropDelay) P(0, PropDelay) +(7.0 PropDelay) P( PropDelay, BeaconInterval) 각비콘주기동안노드도착과 IP 주소요청이균일하게이루어진다면, 평균주소할당시간은전파지연시간의 6.5배정도의값을보인다. 그림 7. RADA 기법에서 IP 주소할당. Fig 7. IP Address Assignment in RADA. 그림 7은충돌없이시도된 IP 주소할당의과정을보여준다. 새로운노드는첫번째 AQ 를보낸후에 AQ 타임아웃시간동안기다린다. 만일노드 Ⅴ. 성능평가 5.1 모의실험환경 NS-2 시뮬레이터 [9] 를사용하여 RADA, LiA, LiACR 기법들을구현하고, 그성능을 (a) 평균주소충돌수, (b) 주소할당시간 (AAT, address al- 304
논문 / 이동애드혹네트워크를위한인터넷프로토콜주소자동설정기법 location time), (c) 제어오버헤드 (CO, control overhead) 발생의관점에서비교한다. AAT는주소요청시작부터 IP 주소할당과정이종료될때까지의시간으로정의하였다. 추가적으로주소할당율 (AAR, address allocation ratio) 을사용중인 IP 주소들의개수를가용주소공간의크기로나눈값으로정의한다. 모의실험에서사용된네트워크는 670m X 670m 크기이며, 노드는 250m 전송범위를가지고, 전파모델은 two ray ground를사용하였다. 전송지연은 200ms로가정하고, (a) 일정주기동안한노드만이진입하는패턴 (one-in-b) 과 (b) 일정주기안에여러노드들이도착하는패턴 (some-in-b) 의노드도착시나리오에대한성능평가를수행하였다. 5.2 one-in-b 시나리오에서의성능평가그림 10(a) 는 RADA와 LiA 기법의평균적인주소충돌수를보여준다. 예상한바와같이 RADA 기법의주소충돌수는 AAR이증가할수록늘어난다. 이것은새로운노드가이미사용되고있지않은남은 IP 주소를선택할확률이줄어들기때문이다. 더욱이주소충돌로인해 IP 주소를획득하지못하면, 다른새로운노드와다시경쟁하게된다. 그러나 LiA 기법에서는최대 IP 주소등의네트워크정보를사용하기때문에 AAR의영향을받지않는다. 그러므로모든새로운노드들이 BEACON 메시지를정상적으로수신한다면, IP 주소는충돌없이할당된다. AAR이높을때는 LiA 기법에서도가끔주소충돌이일어날수있는데, 이것은 IEEE 802.11 MAC 계층의신뢰성없는브로드캐스팅으 그림 9. 비콘주기동안노드가도착하는패턴. Fig 9. The Pattern of a Node Arrival per a Beacon Interval 그림 9는 one-in-b 시나리오를나타낸다. 각비콘주기 (1초) 에도착하는노드의수가하나인경우이며, IP 주소범위는주소할당율을계산하기위해사용되었다. IP 주소공간의크기는 65,536이며, 모의실험은주소할당율이 0.95 값이되었을때종료한다. some-in-b 시나리오에서는 IP 주소를요청하는새로운노드의도착은지수적 ON/OFF 분포를따르며, 초당 0.5번의요청비율을가진다. 일정시간 ( 전송지연시간의 10배 ) 동안도착하는요청의수를하나씩늘린다. 20,000 이상의 IP 주소공간을설정하여두노드가동일한 IP 주소를선택할가능성은무시할수있을정도로작다. 네트워크병합시나리오는 IP 주소공간크기가 20,000이며, 동일한개수의노드들로구성된네트워크가결합되는시나리오이다. LiA 기법을사용하면각네트워크에서시작노드는 0 에서 10,000 범위의시작 IP 주소를선택한다. 다른네트워크식별자를포함하는비콘메시지를받게되면, 가장자리에위치한노드들은자신들이속한네트워크에대한정보를교환하게된다. RADA 기법에서 ACRP 주기와비콘주기는 2초로설정하였다. (a) 평균주소충돌수. (a) Average Number of Address Conflicts. (b) 평균주소할당시간. (b) Average Address Allocation Time. 그림 10. one-in-b 시나리오. Fig 10. one-in-b Scenario. (c) 평균제어오버헤드. (c) Average Control Overhead. 305
한국통신학회논문지 07-3 Vol. 32 No. 3 로인한제어메시지의손실로주소충돌및복구가감지되지않았기때문이다. 만약다수의노드들이동시에 BEACON 메시지를다시브로드캐스트하면, 패킷충돌이일어나 MAC 계층에서의재전송이실패할수도있다. 최악의경우에는새로운노드가 BEACON 메시지를전혀수신하지못할수도있다. 그림 10(b) 는새로운노드의 AAR에따른 AAT 변화를보여준다. RADA 기법을사용하고충분한임시주소들이있다면, 새로운노드가 IP 주소할당에걸리는시간은평균 1.6초이다. 주소사용량 (AAR) 이증가하면, AAT 역시빈번한주소충돌로인하여증가하게된다. LiA 기법에서는새로운노드가자신의 IP 주소를획득하는데평균 1.3초정도의시간이소모된다. 이러한결과들은이전 AAT 정량적분석을통해검증할수있다. RADA 기법의 AAT는 2 0.2 4.0으로계산되어 1.6초이고, LiA 기법의 AAT는 6.5 0.2 로계산되어 1.3초로모의실험결과와일치한다는것을알수있다. 그림 10(b) 에서 AAT를변화시킬때 RADA 기법이 LiA 기법에비해큰값을가진다. RADA 기법에서새로운노드는 3번의 AQ 패킷을브로드캐스트하고일정시간을기다려야하지만, LiA 기법에서는 BEACON 메시지를수신할때까지한번의일정시간동안만기다리면된다. 그림 10(c) 는새로운노드의 AAR에따른제어메시지오버헤드를보여준다. RADA 기법은대부분의 IP 주소가사용중일경우에많은제어메시지들이필요하다. 반면에 LiA 기법에서는주소충돌이없어주소할당재시도가필요하지않기때문에제어메시지오버헤드가고정적이다. 따라서 LiA 기법은 RADA 기법에비해적은메시지와에너지만을사용한다. LiA 기법에서는비콘주기마다하나의노드만도착할경우, AAR 변화는주소충돌과관계가없다. LiACR 기법도유사한경향을보인다. 5.3 some-in-b 시나리오에서의성능평가 그림 11(a) 는짧은시간동안다수의노드가주소요청을할경우의 AAT 변화를보여준다. 충분한가용 IP 주소가있는경우, RADA 기법을사용하면비콘주기내에다수의노드들이주소요청을한다고해도주소충돌이거의발생하지않는다. 그러나 LiA 기법은비콘주기내에서 IP 주소를순차적으로할당하기때문에만일짧은시간동안다수의노드가주소를요청하면, 주소충돌이발생하게 되어 AAT가증가하게된다. 그림 11(b) 는 LiA와 LiACR 기법에서의 AAT 차이가크지않다는것을보여준다. 그림 11(c) 는제어메시지오버헤드를나타낸다. RADA 기법은일정제어메시지오버헤드를가지고, LiACR 기법은 LiA 기법보다적은제어메시지오버헤드를가진다. LiA 기법을사용할때, N개의주소요청이한비콘주기내에발생하면, 하나의노드만이해당 IP 주소를획득할수있고, N-1개의노드들은다음비콘주기에다시경쟁을해야한다. 그러나 LiACR 기법에서는각노드가다른 N-1개노드들로부터 ANNOUNCE 메시지들을수집하여하나의노드만이 WINNER 메시지를브로드캐스트하고, 나머지노드들은자신의우선순위에맞게후보 IP 주소를선택하여다시 ANNOUNCE 메세지를보낸다. 그림 11(c) 는 LiACR 기법의주소충돌 (a) 평균주소충돌수. (a) Average Number of Address Conflicts. (b) 평균주소할당시간. (b) Average Address Allocation Time. (c) 평균제어오버헤드. (c) Average Control Overhead. 그림 11. some-in-b 시나리오. Fig 11. some-in-b Scenario. 306
논문 / 이동애드혹네트워크를위한인터넷프로토콜주소자동설정기법 해결방식이두번째비콘주기에, 동일한 IP 주소에대한경쟁노드의수를 N-1에서 1로낮추어제어메세지오버헤드를줄일수있음을보여준다. 5.4 네트워크병합시나리오그림 12(a) 는두네트워크가병합될때평균주소충돌수를보여준다. LiA 기법은각네트워크의초기노드가자신의 IP 주소를사용가능한주소공간의앞쪽 1/2 공간에서선택하기때문에, 전체사용가능한주소공간에서자신의 IP 주소를선택하는 RADA 기법에비해두네트워크가병합될때더많은중복된주소공간이발생한다. 또한각네트워크를구성하는노드의수가많을수록주소충돌은 AAR에비례하여증가한다. 그림 12(b) 는각네트워크에서 AAR에따른네트워크수렴시간 (NCT) 을보여준다. NCT는두네트 워크가만난시점부터모든주소충돌이해결될때까지의시간을의미한다. RADA 기법에서는네트워크병합을위한특별한동작과정이없지만, ACRP 동작이주소충돌을해결할수있다. 몇번의 ACRP 기간내에동일한 IP 주소를가진노드들은주소중복을인식하고, 가장높은우선순위의한노드만이해당 IP 주소를사용하고다른노드들은새로운노드와마찬가지로주소할당과정을다시수행한다. 따라서 RADA 기법의 NCT는 AAR 증가에따라비례적으로증가한다. 그러나 LiA 기법에서는 SHIFT 메시지를사용하기때문에한번에모든중복주소를변경할수있다. 비록네트워크병합을감지하는시간에차이가있을수는있지만, 한두번의비콘주기에이루어진다. 그림 12(c) 는두네트워크병합할때발생하는전체제어메시지들개수를보여준다. RADA 기법에서는동일한주소를사용하던각노드가유일한주소를할당받기위해추가적인제어메시지들을필요로한다. AAR 증가에따라더많은주소충돌이발생하게되어이러한오버헤드는더욱증가한다. 반면에 LiA 기법에서는하나의 SHIFT 메시지로동시에거의모든주소충돌을해결할수있기때문에제어메시지수가거의일정한수준을유지한다. (a) 중복된주소의수. (a) Average Number of Address Conflicts. (b) 네트웍수렴시간. (b) Network Convergence Time. (c) 평균제어메시지오버헤드. (c) Average Control Message Overhead. 그림 12. 네트워크병합시나리오. Fig 12. Network Merge Scenario. Ⅵ. 결론본논문은이동애드혹네트워크에서 IP 주소자동설정을위한 RADA, LiA, LiACR 기법을제안하였다. 기본적으로후보 IP 주소를선택하여해당애드혹네트워크에서후보 IP 주소의유일성을확인하는과정을거치는기법들이다. LiA 기법이순차적으로 IP 주소를할당하는방식임에반해, RADA 기법은임의주소선택을기반으로동작한다. IP 주소공간이충분하다면, RADA 기법은주소출동이없이빠르게주소를할당할수있다. LiA 기법은 IP 주소의낭비없이거의모든가용 IP 주소의할당이가능하다. 그러나다수의노드들이동시에네트워크에도착하게되면, LiA 기법은주소충돌을해결하기위하여주소할당시간을길어지게되고, RADA 기법에비해큰제어메시지오버헤드를발생시킨다. LiACR 기법은 LiA 기법을확장한것으로거의동일한주소할당시간을유지하면서제어메시지의수도줄일수있다. NS-2 시뮬레이터상에서 RADA, LiA, LiACR 기법을구현하고, 다양한주소할당비율과노드도 307
한국통신학회논문지 07-3 Vol. 32 No. 3 착시나리오를사용하여성능평가를수행하였다. 실험결과는짧은시간내에다수의노드들이네트워크에참여하게되면, RADA 기법은 LiA나 LiACR 기법보다빠르게주소를할당할수있고, 가용주소공간이작은경우에는 LiA나 LiACR 기법이주소공간을더효율적으로사용할수있다는것을보여준다. 다수의노드들이동시에도착하는시나리오에서는 IEEE 802.11 MAC 표준의브로드캐스팅방법이충돌감지와복구기능을가지고있지않기때문에모든주소자동설정기법들의신뢰성이저하되었다. 추후주소자동설정기법의신뢰성향상을위한추가기법과재사용가능한 IP 주소를활용하여주소할당시간을줄이는기법에대한연구를진행할것이다. 참고문헌 [1] IETF Mobile Ad-hoc Networks (manet) Working Group, http://www.ietf.org/html.charters/ manet-charter.html. [2] Perkins, C., Malinen, J., Wakikawa, R. and E. Belding-Royer, IP Address Autoconfiguration for Ad Hoc Networks, I-D draft-perkinsmanet-autoconf-01.txt,november 2001. [3] Jeong, J., Park, J., Kim, H. and D. Kim, Ad Hoc IP Address Autoconfiguration, I-D draft-jeong-adhoc-ip-addrautoconf-02.txt, February 2004. [4] S. Ruffino, P. Stupar, T. Clausen and S. Singh, Connectivity Scenarios for MANET, I-D draft-ruffino-connscenarios-00.txt, February 2005. [5] N. H. Vaidya, Weak Duplicate Address Detection in Mobile Ad Hoc Networks, In Proceedings of the ACM Mobihoc 2002, Lausanne, Switzerland, June 2002, pp. 206-16. [6] Thomson, S. and Narten, T., IPv6 Stateless Address Autoconfiguration, RFC 2462, December 1998. [7] IETF Ad-hoc Network Autoconfiguration (autoconf) Working Group, http://www.ietf.org/ html.charters/autoconfcharter.html. [8] S. Mesargi and R. Prakash, MANETconf: Configuration of Hosts in a Mobile Ad Hoc Network, in Proceedings of the IEEE Conference on Computer Communications (INFOCOM), New York, NY, 2002. [9] VINT Group, UCB/LBNL/VINT Network Simulator ns (version 2), http://www.isi.edu/nsnam/ns. 최낙중 (Nakjung Choi) 학생회원 2002년 2월 : 서울대학교전기컴퓨터공학부졸업 2004년 2월 : 서울대학교전기컴퓨터공학부석사 2004년 3월~현재 : 서울대학교전기컴퓨터공학부박사과정 < 관심분야 > 멀티홉무선네트워크, 무선랜 MAC 프로토콜개선. 이기종망의연동, 트래픽엔지니어링정어진 (Uhjin Joung) 준회원 2005년 2월 : 한밭대학교정보통신컴퓨터공학부졸업 2007년 2월 : 경북대학교컴퓨터공학과졸업 2007년 2월~현재 : 모비루스에근무중 < 관심분야 > 이동애드혹네트워크에서의주소자동설정및 MAC 프로토콜김동균 (Dongkyun Kim) 정회원 1994년 2월 : 경북대학교컴퓨터공학과 ( 학사 ) 1996년 2월 : 서울대학교컴퓨터공학과 ( 공학석사 ) 2001년 2월 : 서울대학교전기컴퓨터공학부 ( 공학박사 ) 1999년 : 미국 Georgia Institute of Technology, 방문연구원 2002년 : 미국 University of California at Santa Cruz, Post-Doc. 연구원 2003년 3월~현재 : 경북대학교컴퓨터공학과조교수 < 관심분야 > 이동인터넷, 초고속인터넷, Mobile Ad Hoc Network, 무선 LAN 등 308
논문 / 이동애드혹네트워크를위한인터넷프로토콜주소자동설정기법 최양희 (Yanghee Choi) 정회원 1975년 2월 : 서울대학교전자공학과공학사 1977년 2월 : 국립과학기술원전자공학과석사 1984년 : 프랑스국립전기통신대학컴퓨터공학박사 1991년 ~ 현재 : 서울대학교컴퓨터공학과교수 2005년 ~ 현재 : 한국과학기술한림원회원 < 관심분야 > 무선모바일네트워크, 미래인터넷, IP기반멀티미디어트래픽 309