최근 연구실에서 띵가 띵가 거리고 있던 도중, 교수님이 갑작스레 "자네, 학회에서 발표 한번 해보지 않겠나?" 라고 하셔서, 발표 논문을 보고 있다. 내가 쓴논문도 아니고, 이 연구실에서 영어로 쓴 논문이었는데, 내가 거의 관심을 두지 않고 있던, 네트워크 쪽이다. 완전 관심이 없는 건 아니고, 공부를 거의 해본적이 없는 분야이기 때문에 사전지식이 조금 부족한 관계로 이것저것 공부하면서 열심히 파던 도중. 한국어로 제대로 된 자료가 없어서 이렇게 포스팅을 한다. 우선 소개할 내용은 애드훅(Ad Hoc) 무선 네트워크상에서 사용하는 DART(Dynamic Address RouTing) 프로토콜에 대해서 소개를 하겠다.
우선 이 DART 프로토콜은 캘리포니아 대학의 Jakob Eriksson, Michalis Faloutsos, Srikanth Krishnamurty에 의해 개발 되었다.
이것을 개발하게 된 배경은 애드훅 네트워크는 어느정도 크게 만들수 있을까? 라는 물음에서 시작되었다. 현재의 애드훅 라우팅 구조는 100개 이상의 노드가 있을때 크기를 더 늘리거나 효율적으로 작동할 수 없다. 이러한 라우팅 프로토콜들은 모바일(무선) 환경에서 노드가 증가함에 따라 그 오버헤드가 기하급수적으로 늘어나는 정적 Addressing을 사용한다. 이 DART의 주된 개념은 노드의 주소와 아이덴티티를 분리하는 것이다. 따라서, DART는 아래의 특성들을 만족시킨다.
- 오버헤드의 지역화
- 경량, 분산 프로토콜
- 제로-설정
- 하드웨어 제약을 최소화
원리.
- 아이덴티티와 주소.
피어의 아이덴티티는 전역적으로 유일하고 노드의 라이프타임과 동일한 시간동안 유지되는 정적인 숫자이다. 노드의 주소는 k-bit 숫자로 표현된다. 이것은 노드의 움직임에 따라 동적으로 변화한다. 더욱이, 주소는 이것의 현재 값이 노드의 위치에 반영되기 때문에 topological한 의미를 갖는다. "주소-상이-아이덴티티" 페러다임은 전통적인 네트워크 프로토콜인 IP와는 전혀 다르다.
- 주소 공간
주소 트리는 주소공간의 관점으로부터의 추상 시각화를 한 것이다. 이것의 잎들은 그들의 주소들에 의해 네트워크 주소안에 있는 피어들을 표현한다. 이것의 안에 있는 노드들은 주소 서브트리를 표현한다. 주소 서브트리는 같은 앞자리 고정 주소 를 갖고 있는 노드들로 구성된다. 점선으로 되어 있는 것은 노드들에 관계된 것들 사이의 물리적인 링크(무선 혹은 유선)들을 가르킨다. 같은 서브트리의 노드들은 물리적으로 연결되어 있다. 서브트리의 구분자는 서브 트리로부터의 주소를 갖고있는 모든 노드의 최소한의 구분자(identifier)이다. 점선으로 된 잎들은 현재 사용되지 않고 있는 주소들이다.
네트워크 토폴로지의 관점은 노드들 사이의 연결성을 표현한다. 중대한 제약(Prefix Subgraph Constraint)은 네트워크 토폴로지에서 연결된 서브그래프로부터 주어진 주소 앞자리 고정자(address prefix)를 공유하는 모든 노드이다. 주소 트리에서 서브 그래프의 앞자리 고정 주소가 길어질수록, 이 앞자리 고정자(prefix)를 공유하는 노드들 사이의 예상 거리는 줄어든다.
주소공간에서 또 다른 중요한 추상적 관점은 형제(Sibling)를 보는 관점이다. I-bit로 구성되 있는 서브 트리는 2 레벨-(I-1)-서브트리와 4 레벨-(I-2)-서브트리 그리고 몇몇개의 서브트리들로 구성된다. 잎들은 레벨-0-서브트리들이다. 각각의 I-bit 주소는 I 레벨-k-형제들을 갖고 있다.
라우팅
여기에서는 선조치 거리 백터 라우팅 형식이 사용되지만, 그러나 다른 라우팅 방법들(예를들어 link-state Routing) 또한 동적 주소할당에 적합할수 있다. 노드의 라우팅 테이블은 그 노드의 각각의 레벨-K-형제의 엔트리로 구성된다. 만약 노드가 자신의 주소와 같은 앞자리 고정자를 공유하고 있는 피어의 주소에 패킷을 보내고 싶다면, 패킷은 레벨-((주소길이-1)-Prefix길이)-형제의 대표에게 패킷을 보낸다. 예를들어 노드 100이 노드 101에게 패킷을 보내고 싶다. 이것은 그 피어와 2-bit 주소 앞자리 고정자를 공유하기 때문에, 노드 100은 패킷을 그의 Level-0형제의 대표에게 보낸다(이 경우 노드 101 자신). The Prefix Subgraph Constraint는 같은 주소 앞자리 고정자를 공유하기 때문에 레벨-k-형제의 대표가 목적 피어와 연결되는 것을 보증한다. 절차는 패킷이 이것의 목적지까지 도달할때 까지 노드를 받는것으로 계속해서 반복된다.
균형잡힌 주소 트리를 가정해 보면, 평균적인 라우팅 테이블은 O(log n)엔트리들(n은 노드의 수)로 구성된다. 피어는 이것의 주기적인 업데이트에 의해 이것의 이웃들에게 이것의 라우팅 엔트리를 전파한다.
노드 찾기.
중요한 질문은 어떻게 노드의 현재의 주소를 찾느냐 이다. 하나의 약속된 접근은 모든 노드들이 <구분자(identifier),주소>쌍의 공유된 분산 노드 찾기표를 사용하는것이다. 노드 Y의 주소를 저장하는 노드는 Y의 앵커(정박) 노드로 불린다. 전역적으로, 이전부터 알고 있던 해시함수 h(x)는 x의 구분자를 곶고 있는 피어를 위해 앵커 노드의 주소를 계산한다. 이 해시 함수 h(x)에 따라 새로운 노드들은 그들의 주소들을 그들의 앵커 노드들에게 요구하는 피어들에게 교대로 전파한다. 만약 주소가 h(x)에 의해 비어있다고 반환된다면, 그때 가장 적게 수정된 거리의 주소가 선택되고, 이것의 해당하는 피어가 앵커노드가 된다.
동적 주소 할당
노드가 네트워크에 가입 할 때, 이것은 적당한 주소를 얻을 필요가 있다. 이것의 이웃들로부터 주기적인 라우팅 업데이트를 들으면서, 새로운 노드들은 가장 크게 비어 있는 주소 단위를 찾고, 그 단위로부터 주소를 고른다. 확실히, 이 the Prefix Subgraph Constraint는 만족스럽다. 그러나, 서로 보이지 않는 노드들이 네트워크에 가입하고 같은 앞자리 고정자를 고르게 된다면 어떤 일이 벌어질까? 이런 경우에, the Prefix Subgraph Constraint는 훼손당하게 된다. 주기적인 라우팅 업데이트를 통해, 그들의 조소들은 네트워크에 전파된다. 그 주소 서브트리로부터 모순되는 정보를 받는 가장 첫 노드는, 서브트리의 인식자(Identifier)와 비교하고, 더 높은 ID를 갖고 서브 트리를 떨어뜨린다. 큰 주소 공간은 주소 혼잡에 의한 새로운 노드의 요청의 거절을 방지하기 위해 사용된다. 더욱이, 주소트리의 균형은 the Prefix Subgraph Constraint의 위반없이 매우 혼잡한 주소공간에서 노드를 이동시키는 것 입니다. 결국, 높은 정도의 혼잡은 주소 공간 확장으로 이끌어 갈 수 있습니다.
(출처 SarWiki -http://sarwiki.informatik.hu-berlin.de/DART_-_Dynamic_Address_Routing)
조금 쉽게 요약을 해보자면.
IP주소를 이용하여, 상대 노드(단말)을 찾는 것이 아니라, 노드 별로 라우팅 테이블을 세팅하고 주기적으로 그 라우팅 테이블을 업데이트 하는 것이 핵심이다. 위의 내용은, 그것을 실현하는 개념적인 방법과, 그것의 이점을 정리해 놓은 것이다.
이전에 사용하던 애드훅 라우팅 구조는, 정적인 주소 체계를 사용함으로써, 애드훅 네트워크 상에 있는 노드들이 많아지면 많아질수록, 헤더가 커지게 되고, 노드가 100개가 넘어가면 효율이 급격하게 떨어진다. 하지만 DART의 경우, 라우팅 테이블이 <Identifier, 주소>의 쌍으로 되어 있고, 이것을 기반으로 목적 노드를 찾아간다. 그리고 이것이 정적이 아닌, 동적으로 되어 있고 라우팅 테이블이 분산 되어 있어 광범위한 애드훅 구조라고 해도 효율적으로 관리가 가능하다는 장점이 있다.
하지만, 만약 이 <Identifier, 주소>의 prefix가 겹치는 경우, 문제가 발생할 수 있다. 물론, 이것을 해결이 가능하지만, 이경우 End-to-End Delay가 발생하게 된다.