In this thesis we propose a proactive scheme using efficient preemptive route maintenance for AODV (Ad hoc On-demand Distance Vector) routing. Existing on-demand routing algorithms such as DSR (Dynamic Source Routing) and AODV do not consider maintenance of established paths. So after a link failure is detected, the path discovery operation is triggered. This causes delay and jitter to packets delivered.
To address this problem, the recovery action is triggered early in preemptive route maintenance by detecting that a link is likely to break soon and it finds an alternative path. But preemptive route maintenance by broadcasting RREQs to find alternate good path can degrade performance of total network in terms of throughput, end-to-end delay as network topology is changed frequently and traffic flows increase.
Motivated by this point, we propose a new proactive scheme (GPAODV) in which nodes in the near of destination generate GREPs (gratuitous replies) to build extended sub-paths to source and the generated GREPs are forwarded by "greedy forwarding" strategy using knowledge of position information of neighbors and source. For this, we assume all data packet convey position information of their sources and hello messages position information of their originators. Once extended sub-paths are established in this way, they are maintained by a proactive manner: explicit periodic hellos and errors. In alternative path discovery operation, we introduce the alternative path request (APREQ) message to request delayed reply (DREP) and only good route replies (RREP) in terms of hop count. We believe that by this approach, delay and overhead for establishing alternative paths can be reduced.
We implemented our scheme by extending AODV implementation in NS-2. Also, we implemented "emulated" preemptive route maintenance (PAODV) for the comparison with our scheme called GPAODV.
The simulation results prove that our idea is more efficient than PAODV in terms of number of broken links, packet delivery fraction, routing load, and average end-to-end delay.
본 논문에서 우리는 AODV에서 효율적인 선점적 경로 관리를 이용하는 능동적 기법을 제안한다. 기존 DSR (Dynamic Source Routing)과 AODV와 같은 on-demand 라우팅 알고리즘은 찾아서 사용중인 경로의 관리를 전혀 고려하지 않는다. 링크의 유실이 탐지되고서야 경로 탐색 동작 (path discovery operation) 이 구동된다. 이는 배달되는 패킷들에 지연 (delay) 과 지터 (jitter)를 유발한다.
이 문제를 해결하기 위한 선점적 경로 관리 기법에서는 링크가 곧 끊어질 것을 감지하고 미리 복구 행동 (recovery action)이 구동되어 다른 경로를 찾는다. 그러나 다른 좋은 경로를 찾기 위해 경로 요구 메시지 (RREQ)를 방송(broadcast)하는 것은 네트웍의 토폴로지가 빈번히 변화하는 이동 애드 혹 망(mobile ad hoc networks)에서는 전체 네트웍의 성능을 저하시킬 수 있다.
경로 요구 메시지로 인한 성능 저하를 개선하기 위해, 우리는 목적지에서 가까운 노드들이 기존 경로에서 출발지 (source) 노드 쪽으로 부분 경로 (sub-path)를 만들기 위해 무상 경로 응답 메시지 (gratuitous route reply)를 보내고 인접 노드들과 출발지 노드의 위치 정보를 이용하여 그리디 포워딩 (greedy forwarding) 하도록 하는 능동적 기법을 제안한다. 이를 위해 모든 데이터 패킷과 헬로우 (hello) 패킷들은 출발지 노드의 위치 정보를 포함하도록 한다. 이런 방식으로 만들어진 확장 부분경로 (extended sub-path) 는 주기적 헬로우, 에러 메시지 등을 이용하여 능등적인 (proactive) 방식으로 관리된다. 다른 경로 찾기 (path discovery) 동작에서는 늦은 응답 (DREP: delayed reply) 과 홉 수 측면에서 좋은 경로 응답 (RREP: route reply) 를 요구하도록 다른 경로 요구(APREQ) 라는 라우팅 패킷을 정의한다. 이 기법에 의해, 다른 경로 수립을 위한 지연과 오버헤드 (overhead)를 감소시킬 수 있다.
우리는 제시한 기법 (GPAODV)을 NS-2 (Network Simulator 2)의 AODV를 확장하여 구현하였다. 또한 비교를 위해 기존 선점적 경로 관리 기법과 유사한 PAODV도 구현하였다. 시뮬레이션을 통해 GPAODV가 깨진 링크 수, 패킷 전달율, 라우팅 로드, 출발지와 목적지 간(end-to-end) 평균 지연 등의 관점에서 PAODV보다 효율적이라는 것을 입증하였다. 또한 결과로부터 효율적인 경로 관리 기법을 통해서 GPAODV가 AODV보다 더 나은 성능을 보이는 것을 확인하였다.
