wireless ad hoc network - 2 (DSDV,AODV)

기존의 라우팅 프로토콜

Distance - Vector 프로토콜 또는 벨만 포드 알고리즘 이라고도 불린다.

라우팅 테이블을 주변 노드와만 교환한다.

여기서 Metric은 각 링크 비용의 합이다. 다른 경우엔 홉수로 메트릭을 판단하기도 한다.

주기적으로 각 노드들은 자신의 테이블을 주변 노드와 교환한다.

라우팅 테이블의 변화가 없는 상태를 stable한 상태라고 한다. 상태 변화가 일어났을때 변화에 대한 대응을 하기 위해서 주기적으로 테이블을 주변 노드와 교환 해야한다. 예를 들어 B와 C사이의 링크 코스트가 1로 바뀐 경우 업데이트가 일어난다. 

각 라우팅 테이블을 교환할때는 넥스트홉에 대한 정보는 제외한 테이블 정보만을 주고 받는다. (목적지,코스트)

B->C에게 라우팅 테이블 전송

A 1 이라는 정보 포함 되어있고,  C는 자기가 가지고 있는 A까지 가는 경로에 대한 코스트값과 비교하게 된다. C는 B가 A로 가는데 1이라는 코스트가 발생한다고 알려줬으니까 자기가 B를 통해서 보낼때는 +1된 값인 2의 코스트로 A까지 데이터를 전송할수 있을것이다. 따라서 A 2로 C는 라우팅 테이블을 업데이트 할 것이다.

새로운 D라는 노드가 네트워크에 참여한경우, 각 주기마다 라우팅 테이블이 업데이트 된다. 

B의 라우팅 테이블의 경우 C로 부터 D까지 1이 걸린다는 정보를 받았으므로 D 2로 라우팅 테이블에 새롭게 엔트리를 추가 하게 된다.

이 상황에서 C와 D사이의 경로가 끊어졌다고 해보자. 이때 C는 D까지 경로가 끊긴걸 인지하고 바로 D로가는 경로의 메트릭을 무한대로 설정한다.

그런데 이때, C가 B로 라우팅 테이블을 전송하기 전에 B가 먼저 C에게 라우팅 테이블을 전송한 경우 C는 D로가는 cost 3의 경로가 있다고 생각해서 라우팅 테이블을 업데이트 하게 된다.(C의 테이블이 망가지게 된다.)

C는 또 연쇄적으로 B에게 다시 잘못된 정보를 알려주게 된다.(D 3이라는 정보를 넘겨준다)

D 3이라는 정보를 수신한 B는 코스트가 더 높음에도 불구하고 목적지까지 가는 넥스트홉으로 부터 받은 라우팅 테이블이므로 코스트에 상관없이 무조건 테이블을 업데이트 하게 된다.

C를 기준으로 보면 B또는 D가 보낸 라우팅 테이블 정보중에 목적지가 같은 엔트리를 보고 같으면, B또는 D가 넥스트홉인지 확인하면 된다.

맞는 경우, 코스트를 보지 않고 바로 업데이트 하면 된다.

그럼 B는 C를 거치면 코스트 3인 경로가 있다고 잘못 생각하여 자신의 라우팅 테이블에서 D 4로 업데이트를 하게 된다.

코스트가 더 나은 경로의 정보를 수신할때만 라우팅 테이블을 업데이트하는게 아니다.

next hop이 destination 까지 가는 경로를 보내주는 경우 코스트에 상관없이 무조건 업데이트한다.

만약에 infinity를 distance vector 프로토콜에서 8이라고 정해놓았으면 

저런식으로 cost가 계속 증가되면서 8이 될때까지 경로가 끊겼다는것을 알수가 없게 된다.(아는데 오래걸린다.)

패킷이 B와 C사이에서 계속 왔다갔다하는 루프가 생기게 된다. 네트워크의 전체적인 성능에 급격한 저하가 생길수 있다.

count to infinity problem을 해결하기 위해서 유선에서는

split horizon , reverse poisning등의 해결책들이 있었다.

DSDV

무선에서 사용하는 Distance Vector 알고리즘인 DSDV에서는 이런 루프를 해결하기 위해서 시퀀스 넘버를 사용한다.

즉 라우팅 정보를 주변 노드들에게 전송할때 목적지,코스트,시퀀스 넘버를 전송한다.

시퀀스 넘버는 패킷의 최신성을 나타내기 위해서 사용하는것이다.

ON DEMAND VS PROACTIVE

proactive : 미리 모든 라우팅 경로를 조사해서 테이블에 저장해놓는것.(테이블을 주기적으로 교환한다고 해서 Table Driven이라고도 한다.)

on demand : 필요할때 필요한 경로만 그때그때 조사 하는것.

애드 혹 네트워크에 노드 수가 많은 경우 proactive방식에서는 오버헤드가 상당히 클 수도 있다.

기존 Distance Vector의 문제점을 개선해서 ad hoc network에 알맞게 만들어진 프로토콜이 DSDV이다.

특징

LOOP FREE (Count to infinity problem을 시퀀스 넘버를 이용해서 해결함)

네트워크에 어떤 변화가 생겼을때 즉시 route advertisement를 하도록 함으로써 노드 간의 topology 불일치 성을 해결한다.

새롭게 추가된 DSDV에서 사용되는 라우팅 테이블이다. (시퀀스 넘버가 추가됬다는것만 알면 된다.)

DSDV에서는 기존의 Distance vector 프로토콜의 라우팅 테이블 업데이트 룰이 조금 바뀌었다.

시퀀스 넘버는 어떻게 설정?

advertisement할때마다 2씩 업데이트 한다.

B가 라우팅 테이블을 전송할 주기가 되었을때, B는 자신의 시퀀스 번호를 2증가 시켜서 주변 노드에게 전송한다.

그것을 수신한 A,C는 B,0에 대한 정보를 시퀀스 넘버 100으로 알고있었는데 더 높은 시퀀스 번호인 102를 받았으므로

B,0에 대한 정보를 업데이트 하게 된다.

새로운 D라는 노드가 네트워크에 참여한 경우 C는 D로부터 D,0,D-000을 받자마자 즉시 브로드 캐스팅 한다.

C는 라우팅 테이블을 주변 노드에게 전송하기 전에 자신의 시퀀스 넘버를 2 증가시켜서 보내게 된다 그래서 C-592를 전송하게 된다.

B의 입장에서 보면 A,B에 대한 정보는 그대로 냅두고 C에 대한 정보는 원래 590이라는 시퀀스 번호로 알고있었는데 더높은 시퀀스 번호가 수신 됬으므로 C에대한 정보를 업데이트 하게 된다. 또한 D-000라는 시퀀스 번호를 갖는 엔트리가 없었으므로 D에 대한 정보도 새롭게 추가한다.

D는 C가 보내준 그대로 업데이트를 하게 된다.

만약 C와 D의 링크가 끊어진걸 C가 알게 된경우 메트릭을 무한대로 업데이트하고 D에 대한 시퀀스 번호를 1증가 시켜서 브로큰 링크라는것을 의미하게끔 한다.

그럼 C가 B에게 제대로된 링크 정보를 보내기 전에 B가 C에게 잘못된 정보를 먼저 전달한다고 해도 시퀀스 번호가 낮으므로 C는 그 정보를 업데이트 하지 않을것이므로 count to infinity problem문제가 해결 되었다. C자신이 가진 정보가 더 최신이라고 판단하는것이다.

그 후에 C의 라우팅 테이블 전송 주기가 되어서 주변 노드들에게 브로드 캐스팅 한다.

그럼 C는 C에 대한 엔트리만 seq번호를 2업데이트해서 보내게 되므로 D에 대한 정보는 여전히 D-101로 되어 있을 것이고, 그럼 A나 B는 D에대한 시퀀스 번호를 100으로 알고 있으므로 라우팅 테이블이 업데이트 될것이다. 이런식으로 브로큰 링크에 대한 정보가 바로바로 네트워크에서 전달된다.

DSDV의 가장 큰 장점 : 누구나 이해할수있는 심플한 알고리즘

또한, latency가 발생하지 않는 장점이 존재한다.

기존의 distance vector방식에서도 latency는 발생하지 않았다. (on demand는 필요할때 경로를 찾게 되므로 latency존재)

대신에, 대부분의 라우팅 정보가 사용되지 않음에도 불구하고 모든 라우팅 정보를 다 찾아내야 되는것이 큰 오버헤드로 작용한다는 단점이 존재함.(preactive 또는 table driven방식)

센서 네트워크와 같이 언제나 모든 노드들이 동작하지 않는 네트워크에서는 preactive방식이 비효율적일수 있다.

DSDV의 ondemand버전이 AODV이다.

AODV

on demand 방식의 대표적인 예가 DSR이다. DSR의 경우 모든 경로가 패킷 헤더에 포함되어 있으므로 헤더가 커질수 있다는 문제가 있다.

만약에 노드의 주소가 128BIT라고 했을때 모든 경로를 헤더에 기록한다는것은 문제가 있을수 있다.

AODV - Ad hoc on-demand distance vector routing

DSR과 동작방식이 아주 비슷하나 중간 노드에서 처리 방법이 약간 다르다.

DSR과 마찬가지로 on demand 프로토콜들은 다 이런 방식으로 작동한다.

1. RREQ를 플러딩한다.(route discovery를 위해서)

2. 중간 노드들이 Re-broadcasting을 한다. 

-> 기존의 DSR과 이부분이 다르다.

패킷에 무엇을 기록하는것이 아니라 S까지 가는 경로에서 넥스트홉이 누구다 라는 정보만 헤더에 포함시킨다.

S까지 가려면 넥스트홉이 누구다.

B,C,E는 S까지 가는데 넥스트홉이 S다 라는 패킷을 받고 리 브로드 캐스팅을 한다.

F,G,H,A는 넥스트홉도 변경해서 다시 리 브로드 캐스팅한다.(S까지 가는데 B이다 , S까지 가는데 C이다.)

이게 모두 플러딩이 완료 될 경우 모든 노드들이 데스티 네이션 까지 가는데 넥스트홉이 뭔지 알게 된다.

DSR에서는 소스 라우팅을 통해서 소스에게 RREP를 보냈는데

AODV에서는 reverse path를 따라서 간다.

D는 RREP를 J에게 보낸다. J는 RREQ를 받았을때 Destination까지 가는데 넥스트홉이 F라는 정보를 알고 있으므로 그대로 F에게 다시 RREP를 되돌려 준다.

결국에 S까지 전달되어서 경로찾기 문제가 끝나게 된다.

각 노드들이 RREP를 받았을때 라우팅 테이블이 만들어 진다.

J는 RREP를 D에게 받는다. D까지 가는데 넥스트홉이 D이다 라고 업데이트

F는 J에게 RREP를 수신. F의 라우팅 테이블에서 D까지 가는데, 넥스트홉이 J라고 기록한다.

E는 RREP를 F에게 수신, D까지 가는데 넥스트홉이 F라고 기록한다.

이런 과정을 거치면 S는 D까지 가는데 넥스트홉이 E라고 기록하고 경로 찾기 문제가 끝나게 된다.

경로 찾는데 지연시간을 줄이기 위해서 중간 노드가 목적지 까지의 경로를 알고 있을때 그 중간노드가 RREP를 발생 시킨다.

중간에 경로가 끊어진 경우 그 걸 알게된 노드가 RERR(route error)메세지를 되돌려 주며 소스가 그것을 수신하면 다시 route discovery를 시작한다.

AODV가 DSR보다 좋은점

패킷 헤더에 루트가 기록될 필요가 없으므로 헤더 길이가 더 작다.

AODV,DSDV,DSR의 장점

시퀀스 넘버를 이용해서 최신성, 중복성을 판별한다.

AODV,DSDV -> 두개가 distance vector라는 공통점

DSR,AODV -> ON - DEMAND이다 라는 공통점

DSDV와 DSR의 공통점은 단지 ad hoc network에서 사용되는 라우팅 프로토콜이라는 것 밖에 없다.