무선 환경의 특징
- 무선 환경에서는 한 사람에게 보내려는 것도 브로드캐스트가 된다.
- 중간에 충돌, 간섭, 노이즈가 많다.
- 전송 파워에도 한계가 있다.
- 무선 기기의 메모리가 작은 경우 라우팅 테이블을 크게 만들 수 없다는 것도 고려해야 한다.
분류
마스터 노드의 유무
인프라 기반
- 특별한 마스터 노드가 있다.
- 예를 들어 기지국
- 중앙 통제적이다.
- 라우팅이 비교적 쉽다.
애드 호크
- 특별한 노드가 없다.
- 모든 노드와 라우터가 평등하다.
- 알고리즘이 분산되어 돌아간다.
대응 관계에 따른 분류
- any to any
- one to many
- 예시로 스위치를 켜면 모든 형광등의 불이 켜지는 것
- many to one
- 예를 들어 노드들의 하나의 마스터에게 보내는 경우
트래픽 특성에 따른 분류
프로액티브
- 먼저 라우팅 테이블을 만들고 통신한다.
- 필요하지 않을 수도 있지만 일단 만든다.
리액티브
- 필요할 때만 즉 데이터를 보낼때만 라우팅 테이블을 만든다.
- 첫 메세지를 보낼때 라우팅 테이블을 만들어야 해서 시간이 좀 걸린다.
라우팅 정보에 따라
홉 바이 홉
- 다음 라우터에게 패킷을 보내면 더이상 신경 쓰지 않는다.
- 즉 한 홉 보내면 해당 패킷에는 더이상 관여하지 않는다.
- 루프가 없다는 것을 보장하지 못한다.
소스 라우팅
- 소스가 목적지로 어느 라우터로 가야하는지 다 알고 있다.
- 그래서 헤더에 경로가 다 들어있다.
- 경로를 정해주니 루프가 없다는 것을 보장할 수 있다.
- 단 패킷이 너무 길어질 수 있다.
on-demand, 애드 호크 라우팅
aodv 프로토콜이 이에 해당한다.
소스는 a 목적지는 h라고 할 때
- a가 h에게 보내고 싶다는 요청 메세지를 브로드캐스트한다.
- b와 c가 이걸 받으면 a가 h에게 보내고 싶어한다는 것을 알게 된다.
- b와 c는 메세지를 다시 브로드캐스트한다.
- b가 먼저 브로드캐스트하면 d와 e가 받고 이 둘은 a가 h에게 뭘 보내고 싶어한다는 것을 알게 된다. c도 받지만 c는 이미 받았기 때문에 메세지를 무시한다.
- c도 브로드캐스트르 하고 f가 받는다.
- d와 e중 e가 먼저 보내면 b, c, d는 무시하고 g 와 h가 받을 것이다.
- h는 자신이 받은 메세지를 보고 목적지가 자신이라는 것을 알게 된다.
- h는 답장을 하려 하는데 이때 자신에게 메세지를 준 e에게 응답 메세지를 준다.
- e는 b에게 받았으니 b에게 응답을 한다.
- b는 a에게 받았으니 a에게 응답을 한다.
- 이런 방식으로 a, b, e는 h로 가려면 어디로 보내야 하는지 알게 된다.
다대일 라우팅
슬레이브 -> 마스터
예시 네트워크는 동일하다.
a가 스페셜 노드 즉 루트 노드이다.
나머지 노드는 a에게 뭘 보내야 한다.
- a는 라우팅 비콘을 보낸다. 이 비콘은 자기가 루트인 a에게 가려면 거리가 0이라는 것을 말한다.
- 이 비콘을 받은 b와 c는 이전 홉의 노드는 a까지의 거리가 0이었으니 자신들의 a까지의 거리가 1이라는 것을 알게 된다.
- c가 거리 1 비콘을 보내면 d, e, f가 받고 자신들은 거리 2라는 것을 알게 된다. 추가로 a로 가려면 c로 가야한다는 것도 알게 된다.
- d가 먼저 보내면 g가 받고 거리 4에 루트로 가려면 d로 가야한다는 걸 알게 된다.
이런식으로 홉을 논리적인 토폴로지로 나타낼 수 있게 된다.
이를 라우팅 트리라고 한다. 이걸 만들면 라우팅시 각 노드의 라우팅 테이블의 크기는 1이다. 왜냐면 목적지는 루트 1개이고 부모만 알면 되기 때문이다.
마스터 -> 슬레이브
만약 루트인 a가 자손에게 무엇을 보내려고 한다면
예를 들어 g에게 무엇을 보내려고 하면
- 먼저 모든 노드가 루트에게 광고 메세지를 보낸다.
- b가 보낸 메세지를 통해 a는 b로 가려면 b로 보내야 한다는 것을 알게 된다.
- e가 보낸 메세지는 b와 a를 거쳐가니 b는 e로 가려면 e로 보내야 하는 것 a는 e로 가려면 b로 보내야 하는 것을 알게 된다.
이런 식으로 라우팅 테이블이 만들어지고 라우팅 테이블의 크기는 당연히 n개의 노드가 있을 때 O(n)
따라서 슬레이브 -> 마스터로 갈 때보다 비용이 더 크다.
라우팅 트리에서 일대일 라우팅
위의 라우팅 트리를 사용하는데 이제 슬레이브간 통신을 할 것이다.
예를 들어 d가 f에게 보내려면 d는 a에게 보내고 a가 f에게 보내주면 된다.
일대다 라우팅
알람처럼 한 노드가 모두에게 보내고 싶을 수도 있다.
똑같은 예시 네트워크를 사용하고 a가 소스일 때
a에게 받을 걸 b와 c가 다른 노드들에게 보내면 충돌이 일어날 수 있다. 이런 경우를 위해 trickle 알고리즘을 사용한다.
trickle 알고리즘
- a가 어떤 걸 보내면
- b와 c는 시간의 범위를 나누고 나눈 시간대 중 랜덤으로 하나를 정해서 그 시간에 보낸다.
- d와 e도 받으면 똑같은 것을 한다.
- 이때 다른 레벨의 홉에 있는 노드는 쪼개기 전의 시간대가 겹치지 않는다.
- 충돌이 나면 시간대를 2배로 늘리고 위 과정을 반복한다.
