wireless ad hoc network - 1 (Dynamic Source Routing)

일반적으로 ad hoc network는 multi hop ad hoc network를 지칭한다.

wireless에서만 ad hoc network라고 부른다. 유선에서는 ad hoc이라고 하지 않는다.

인프라 존재 하지 않음. 사용자 끼리 서로 도와서 네트워크 구성

mobile ad hoc network -> ad hoc net에서 사용자들이 이동함.

ad hoc network에서는 이용자들이 계속 변해서 라우팅 문제가 어려운 문제이다.

무선으로 모든 노드를 연결하다 보니까 통신 품질이 떨어질수 있음.

지금은 무선 ad hoc net에서 라우팅 문제는 많은 연구가 이루어 져서 어려운 문제는 아니게 되었다.

기존의 유선 라우팅 프로토콜이 무선에서 적합하지 않은 이유

Distance Vector - 주변 노드와 distance vector를 교환함 (어디까지 어떤 cost로 갈수있다는 정보들의 배열,집합)

분산 계산이 이루어짐.

어떤 한 노드가 라우팅 계산을 잘못한 경우 네트워크 전체에 영향을 미친다.

Link State - 각 노드가 다른 모든 노드들에게 자신의 링크 정보를 알려준다.

N2가 1,3,4,5,7노드에게 모두 자신의 링크 정보를 알려주기 때문에 링크 오버헤드가 크지만, 보다 정확한 루트를 계산할수 있음.

Topology change가 자주 일어나기 때문에 기존의 유선 라우팅 프로토콜은 사용이 불가능하다.

(변화가 바로바로 네트워크 전체에 반영되지 않음)

유선 보다 무선이 통신 속도가 느리다. -> 유선보다 속도는 느린데, Topology변화가 심해서 유선보다 더 많은 데이터를 컨트롤 패킷에 사용함.

대부분의 대역폭을 라우팅에 소모해버린다. 라우팅은 네트워크 운용에 필요한것이지 실제 데이터 전송에 도움이 안됨.

Dynamic Source Routing

모든 경로를 기억해야 하므로 좋은 라우팅 프로토콜은 아니다.

기존의 라우팅 프로토콜은 내가 보내지 않아도 될 경로 까지 모두 미리 미리 찾아 놓는다.

무선에서는 통신 속도가 느리고, 노드들이 매우 빈번히 이동할수 있으므로, 이런식으로 

미리 찾아놓을 필요가 없으며, 이렇게 할경우 오버헤드가 굉장히 커진다.

따라서 DSR에서 처음 제시한 기법이 on demand란 기법이다. (필요한 경로만 요청에 따라 그때그때 경로를 찾겠다는 의미)

Discover a path(on demand)와 Maintaining a path 두단계로 DSR이 이루어진다.

한번 데이터를 보내면 나중에 또 그 경로를 사용할것이라고 예상하고, 그 경로를 유지한다.

주기적인 업데이트가 필요없다.(distance vector나 link state들은 주기적으로 라우팅 정보를 노드들 끼리 교환한다.)

link state > distance vector 순으로 라우팅 트래픽이 발생한다.

단점

1. 경로를 그떄그때 찾아야 하기 때문에 경로를 찾을때 까지 데이터를 전송하지 못하고 기다려야 한다. (시작 딜레이)

-> discover a path가 데이터 전송 시간에 비해 굉장히 커질수 있다.

DSR에서 노드가 ROUTE DISCOVERY 를 할때 RREQ(ROUTE REQUEST)를 FLOODING한다(브로드 캐스팅 한다).

C가 RREQ를 B,E,G에게 브로드 캐스팅 한다.

전송할때 최종 목적지와 지나쳐온 경로를 RREQ에 표시해서 전송한다.

[O,C,4711(SEQ NUM)]형식으로

시퀀스넘버는 RREQ간의 구분을 위해서 사용한다.

네트워크의 구조(토폴로지)가 바뀌면 경로를 다시 찾아야 하는데, 예전에 발생된 RREQ와 새로 발생된 RREQ를 구분할수 있어야 제대로된 경로를 찾을 수 있다.(바뀐 경로로)

G가 C에게 [O,C,4711]을 받고나서 C,E,I에게 [O,C/G,4711]을 전송하지만 C는 이패킷을 버려버린다.

또한 E도 G로부터 [O,C/G,4711]을 수신하지만 이 패킷을 버려버린다.

그 이유는 DESTINATION인 O와 시퀀스번호인 4711이 같기 때문에 같은 RREQ패킷이라고 판단하기 때문이다.

D입장에서 보면 B와 E에게 같은 RREQ패킷을 받는다.(목적지와 시퀀스넘버가 같으므로)

그래서 둘중에 먼저온 패킷을 수신하고 나중에 온 패킷은 버려버린다.

따라서 모든 노드들은 충돌을 방지하기 위해서 랜덤 BACK-OFF를 한다.(일정시간 딜레이후 패킷 전송)

D가 B와E로부터 동시에 패킷을 수신하면 충돌이 일어남.

최종적으로 O까지 RREQ가 전달되어서 O는 [O,C/G/I/K/M,4711]패킷을 받을것이다.

받고나서 O는 RREP(ROUTE REPLY)를 되돌려 준다.

ROUTE DISCOVERY를 완료 하려면 O가 받은 경로 정보를 C에게 다시 알려주어야 한다.

여기 까지 상황만 봤을때 O만 C->O의 경로를 알고있고 나머지 노드들은 알지 못한다.

RREQ는 브로드 캐스팅을 했지만 O가 보내는 RREP는 SOURCE ROUTING을 한다.(경로를 기록해서 보낸다)

O는 C에게 RREP를 되돌려 주어야 한다.

그 패킷의 내용은 [C,O/M/K/I/G,4711]으로 구성되어 있고

브로드 캐스팅 하는데, 왔던 경로로 다시 돌아가야 하므로 이 패킷을 받아줄 다음 노드를 포인팅 해서 보낸다.

그럼 브로드 캐스팅해서 수신된 노드들에서 포인터값이 자신인지 확인하고 자신인 경우 

다시 포인팅을 바꿔서 브로드 캐스팅하며, 이 과정을 반복하게 된다.

O->M일때

[C,O/M/K/I/G/C,4711]

(M을 제외한 나머지 노드가 이 패킷을 받은경우 DISCARD)

M->K일때

[C,O/M/K/I/G/C,4711]

K->I일때

[C,O/M/K/I/G/C,4711]

(L이 이 패킷을 수신한 경우 포인터 값이 자신과 일치하지 않아서 DISCARD함)

최종적으로 RREP가 C에게 도달하게 되면 C는 라우팅 테이블을 업데이트 할 수 있는데,

이때 O에대한 경로뿐만아니라

M,K,I에 대한 경로도 업데이트를 할 수 있게 된다.

[C,O/M/K/I/G/C,4711]이라는 패킷정보에 경로가 다 적혀있기 때문이다.

C의 ROUTING TABLE

O     G I K M

M        G I K

K        G    I

I            G

자신에게 전송된것이 아닌 패킷(목적지 주소가 자신이 아닌)을 처리하는것을 OVERHEARING이라고 한다.

L이 K가 브로드 캐스팅한 패킷(RREP)을 받은경우,

L은 K가 보낸 RREP를 받아서 라우팅 테이블을 업데이트하게된다

(I,G,C,M,O까지 가는 경로에 대한 정보) 이것을 overhearing이라고 한다.

C는 O에게 플러딩을 통해서 RREQ를 전송하고, O는 C에게 소스 라우팅을 통해서 RREP를 되돌려준다.

그럼 route discovery가 완료 된것이다.

그 과정에서 overhearing하는 노드들의 라우팅 테이블도 업데이트 된다.

RREP는 라우팅 테이블을 만드는데 사용된다.

요약

RREQ를 수신한 노드가 RREQ에 적힌 목적지 주소와 자신의 주소가 일치하는 경우 RREP를 리턴하며

이때 소스 라우팅을 통해서 그 송신지로 RREP를 되돌려준다.

브로드 캐스팅 과정에서 중복 수신된 RREQ는 버려 버린다.

중복 수신의 판단 => 목적지 주소와, 시퀀스 넘버

추가 개선

1

C->G->I->K->M->O 의 경로가 있을때

I가 O까지 가는 경로를 캐시에 저장해 놓았을때

C의 RREQ요청을 I가 받고나서 I가 RREP를 C에게 리턴해준다.

(잘 사용되지는 않는 방법)

2

C가 H까지만 패킷을 전달하고 싶을때 O까지 패킷이 전달되지 않게끔 하는게 네트워크에 좋다.

그래서 최대 이동할수있는 홉수를 설정해서 패킷을 전송하면 H까지만 패킷이 전달되게끔 할 수 있다.

3

RREP가 C->O로 가는 도중에 M이 사라지면 K는 C에게 오류(ROUTE ERROR패킷)가 발생했다고 알려주고 

C는 다시 ROUTE DISCOVERY를 시작한다.

또는 새로운 경로를 K가 시작할수도 있다.