- 26 -
의 버퍼에 전달해야 할 데이터들을 저장한다. 단절 지점의 상위 노드는 끊어진 경로를 복구하기 위해 처음에 경로를 탐색하던 것처럼 RREQ를 브로드캐스트 하고 응답을 기다린다. RREQ를 RREQ_RETRIES 시도 후에도 RREP를 받지 못하면 RERR 메시지를 소스 노드와 경로 상에 있는 노드들에게 전송하여 경 로를 해제한다.
지역 경로 복구를 위한 RREQ 메시지가 목적지 노드로 도달하면 목적지 노 드는 일련번호를 증가 시켜 RREP를 발송한다. 단절 지점의 상위 노드는 RREP를 수신하고 증가된 목적지의 일련번호를 확인하여 경로를 갱신하고 지 역 경로 복구를 종료한다.
만약 목적지 노드가 아닌, 목적지로의 경로를 가진 중계 노드가 RREQ를 수 신하고 RREP를 발송했다면 목적지의 일련번호가 증가하지 않았기 때문에 홉 수를 비교하게 된다. 홉 수가 이전에 알려진 경로의 홉 수보다 작다면 지역 경 로 복구를 완료하며, 그렇지 않다면 이 RREP에 대한 정보를 무시하게 되어 지 역 경로 복구가 완료되지 않는다.
- 28 -
(a) 경로 단절 시 RERR 메시지 전송
(b) 경로 단절 시 지역 경로 복구 수행
그림 9. 경로 상의 단절 처리 Fig 9. Processing for broken links
제3장 고장 허용 라우팅 프로토콜
본 연구에서는 AODV 기반 고장 허용 라우팅 프로토콜(FT-AODV:
Fault-Tolerant Routing Protocol)을 제안한다. 모바일 애드혹 네트워크에서 노 드는 배터리가 소진되었거나 기타 고장을 일으키는 경우도 일어난다. 단일 노 드의 고장이나 경로의 단절은 경로 재탐색에 따르는 전송 지연 시간과 라우팅 오버헤드의 증가를 가져왔다. 따라서 얼마나 빨리 노드의 고장이나 경로의 단 절에 효과적으로 대처하는가 하는 것이 네트워크의 성능 향상에 기여할 수 있 다. 노드의 고장 확률을 p라고 하면 두 개 노드가 동시에 고장 날 확률은 p2이 된다. 만약 노드 고장 확률이 1% (p = 0.01)라고 가정하면, 두 개 노드가 동시 에 고장 날 확률은 0.01% (p2 = 0.0001)로 현저하게 낮아진다.
본 연구는 경로 상의 노드의 고장을 허용하기 위해 단절된 지점의 상위 노드 가 단절된 지점의 하위 노드를 알고 있어야 한다. 이 정보를 이용하여 단절된 지점의 상위노드로부터 1-hop간의 거리에 있는 노드 중 단절된 지점의 하위노 드를 이웃으로 가진 노드를 탐색한다. 단절된 지점의 하위노드를 탐색하기 위 해서 모든 노드가 자신의 다음 홉뿐만 아니라 경로상의 2-hop 거리에 있는 노 드의 정보를 알아야 한다. 이를 위해 RREP 패킷을 이용해 초기경로가 설정 될 시 RREP 패킷의 수정을 통해 하위 방향으로 2-hop간의 노드를 기록하여 이 정보를 이용하여 단절된 지점의 하위노드를 찾는다. 또한, 단절된 지점의 하위 노드를 찾기 위해 RSAL (Route Salvage) 패킷을 제안하였다.
따라서 단일 노드 고장에 대한 고장 허용 라우팅을 제공하여 네트워크의 신 뢰성 및 전송 성능이 크게 향상되었다.
- 30 -
제1절 역 경로 설정
그림 10에서 RREQ가 목적지인 노드 D까지 전달이 되면 노드 D는 RREQ가 왔던 경로를 따라 RREP 메시지를 발신지로 전송하는데 이 때 RREP에는 수신 노드의 현재 일련번호와 수신노드까지의 홉 수를 기록하여 유니캐스트로 전송 을 한다. 이것은 기존의 AODV에서의 역 경로를 설정하는 과정이다. 기존의 AODV 프로토콜에서는 모든 경로를 전부 저장하고 있는 DSR 프로토콜과는 다르게 가볍게 설계되었기 때문에 패킷이 도착할 목적지 노드와 자신의 하위 방향으로의 다음 홉만 알고 있으며 또한 지역 경로 복구 시 노드 a가 RREQ를 목적지 노드로 다시 브로드캐스트하기 때문에 종단 간 전달 시간의 지연과 높 은 오버헤드를 가지고 있다.
그림 10과 같이 제안하는 방법은 표 3과 같은 경로 테이블을 생성한다. 노드 b가 배터리가 소진되었거나 다른 곳으로 이동하는 등의 모바일 환경에서 쉽게 일어날 수 있는 고장으로 인해 전체 경로 중 노드 a에서 노드 c로의 구간이 단 절되었을 경우, 역 경로가 설정될 때 노드 b가 자신의 다음 홉이 노드 c라는 사실을 RREP 패킷에 실어서 노드 a에게 보내어 노드 a가 단절된 지점인 노드 b 이후에 노드 c가 있다는 사실을 이미 알 수 있게 하여 RREQ 패킷을 목적지 노드인 D까지 브로드캐스팅을 하지 않고, 단지 1-hop 간에 있는 이웃 노드들 에게 경로 상에 있는 노드 c를 이웃으로 가진 노드가 있는지를 확인하는 메시 지를 전송한다. 이를 위해 그림 11과 같이 기존의 RREP 패킷에 32 bit Successor IP Address 필드인 Downstream IP Address를 추가하여 새로 추가 된 필드에 노드 b의 다음 홉인 노드 c를 기록하고 수정된 RREP를 수신한 경 우 갱신될 경로 테이블에도 Downstream IP Address를 기록할 필드인 Downsrc를 추가하였다.
그림 10. 경로의 단절에 따른 복구 과정 Fig 10. An example of local repair
- 32 -
표 3. 수정된 RREP에 의한 경로 테이블
Table 3. Routing table resulted from the modified RREP packet
Node Destination Nexthop Downstream
a D b c
b D c e
u D c e
그림 11은 고장 허용 라우팅 프로토콜을 위한 기존의 AODV의 RREP 패킷 을 수정한 것으로, 그림 10에서 노드 a의 다음 홉인 노드 b의 고장이나 이동으 로 인해 경로 a-b-c가 단절되었을 경우 노드 a에게 경로 상에 참여하는 노드 b의 다음 홉인 노드 c를 알게 하여 경로가 단절되었을 경우 노드 c를 이웃으로 가진 1-hop 간의 거리에 있는 노드들을 확인할 수 있도록 기존의 RREP 패킷 에 32 bit successor IP address 필드를 추가하였으며 새로 추가된 downstream IP address 필드에 노드 b의 다음 홉을 기록한다.
RREQ는 경로 탐색을 위한 패킷으로 특별한 수정이 필요하지는 않다. 경로를 최초로 탐색할 때 소스 노드는 RREQ 패킷을 브로드캐스트하고 목적지 노드, 혹은 목적지로의 경로를 가진 중계노드가 RREQ 패킷을 수신하면 RREQ 패킷 의 응답으로 RREP 패킷을 생성하여 소스노드로 전송하는데 이 때 역 경로가 생성이 된다. 각 노드들은 RREP 패킷을 수신하면 자신의 경로 테이블에서 목 적지 노드로 가는 정보들을 추가 또는 갱신한다. 이 때, 각 노드들이 RREP를 상위 방향으로 전송하기 위하여 RREP 패킷에 정보를 기록하면서 추가로 목적 지 노드로의 다음 홉을 추가된 필드인 downstream IP address에 함께 기록하 여 전송한다. 패킷을 받은 노드는 내용을 확인하여 자신의 다음 홉과 다음 홉 이 단절 되었을 경우 RSAL 패킷을 통해 요청할 downstream IP address를 자 신의 경로 테이블에 기록한다.
- 34 -
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
Type R A Reserved Prefix
Size Hop Count Destination IP Address
Destination Sequence Number Source IP Address Downstream IP address
Litetime
그림 11. 수정된 RREP 패킷의 구조 Fig 11. Modified RREP message format
제2절 우회 노드 탐색
경로가 단절 되었을 때 단절된 지점의 상위 노드 a로부터 1-hop 간의 거리에 있는 노드 a의 이웃 노드 중 경로에 참여하는 노드 c를 이웃으로 가진 노드가 있는지를 확인하는 패킷을 전송하기 위해 RSAL 패킷을 제안한다. 노드 v와 노 드 u는 노드 a의 1-hop 간의 전송 범위 이내에 있으며 이들은 경로에 참여하 고 있는 노드 c를 이웃으로 가지고 있다. 노드 v와 노드 u는 노드 a가 발신한 RSAL 패킷을 수신하고 수신한 즉시 자신의 이웃 테이블에 경로 상에 참여하 고 있는 노드 c가 있는지를 검사한다. 만약 이웃 테이블에 노드 c가 존재하지 않는다면 RSAL 패킷은 버려진다. 그러나 노드 c를 자신의 이웃으로 가지고 있 다면 노드 v와 노드 u는 받은 RSAL의 패킷 내용 중 목적지 노드를 참조하여 자신의 경로 테이블에서 목적지 노드로 가는 경로가 있는지를 확인하여, 존재 하지 않는다면 자신의 경로 테이블에 RSAL에 기록된 목적지 노드를 새로 추 가하고, 자신의 경로 테이블에 해당 목적지 노드가 있으면 경로 테이블에 새로 추가할 필요는 없다. 그 다음, 자신의 역 경로 엔트리에 upstream 방향의 다음 노드를 노드 a로 수정하고 RSAL에 포함된 목적지인 노드 D로의 다음 홉을 노 드 c로 수정한다. 그리고 RSAL에 대한 응답 메시지로 RREP 패킷을 자신의 상위 방향인 노드 a로 전송하여 끊어진 지점을 복구하게 된다.
그림 12는 고장 허용 라우팅 프로토콜의 RSAL 패킷의 구조를 나타낸 것으 로 AODV의 패킷 유형은 5로 설정하고, 목적지 노드의 주소는 데이터가 최종 적으로 도달해야 하는 목적지 노드의 IP 주소로 그림 10에서의 노드 D에 해당 하고, 발신지 노드의 IP 주소는 처음에 데이터가 생성되는 소스 노드의 주소로 노드 S에 해당하며, 단절된 지점의 상위 지점인 originator IP address는 단절 된 지점의 상위 노드인 노드 a, 그리고 단절된 지점의 하위 노드의 주소인
- 36 -
downstream IP address는 단절된 지점의 다음 홉인 노드 c가 된다.
그림 10에서와 같이 노드 b의 고장으로 인해 경로가 단절되었을 경우 노드 a 는 RSAL패킷에 다음과 같은 내용을 포함하여 자신의 주변의 1-hop 거리에 있 는 노드들에게 전송한다. RSAL을 수신한 노드 u와 노드 v는 먼저 자신의 이 웃테이블에서 RSAL에서 요청하는 downstream IP address인 노드 c가 자신의 이웃인지를 검사한다. 만약 노드 c가 자신의 이웃이 아니라면 수신된 RSAL은 폐기된다. 반대로 노드 c를 자신의 이웃으로 가지고 있으면 노드 u와 v는 그 다음단계로 RSAL 패킷에서 요청하는 목적지 노드가 자신의 경로 테이블에 존 재하는지를 확인한다. 만약 자신의 경로 테이블에 RSAL 패킷에서 요청하는 목 적지 노드가 존재하지 않는다면 자신의 경로 테이블에 새로이 RSAL 패킷에서 요청하는 목적지를 추가하고 존재한다면 경로의 유효 시간을 갱신한다. 그리고 RREP 패킷을 노드 a에게 발송하여 경로가 자연스럽게 복구되도록 한다.
그림 10에서는 노드 u와 노드 v가 함께 이웃 노드로 노드 a, b, c를 가지고 있으며 노드 a로부터의 거리 또한 같으므로 각각 RSAL 패킷을 수신하고 RSAL 패킷에 대한 응답으로 노드 a에게 RREP 패킷을 발송한다. 이 때 노드 a는 기존의 AODV에서 같은 패킷을 처리하는 방법과 같이 홉 수와 일련번호를 가지고 도착한 RREP 패킷을 처리하게 된다.