라우팅 알고리즘
IT 위키
Routing Algorithm
패킷을 목적지까지 보낼 경로를 정하는 방법
망의 상태 변화에 반응하는지에 따라 비적응 라우팅과 적응 라우팅으로 나눈다.
- Non-adaptive Routing; 정적 라우팅
망의 상태 변화를 고려하지 않는다. 트래픽이나 회선 장애와 무관하게 미리 정해 둔 규칙대로 경로를 정한다. 구현이 단순하지만 혼잡이나 장애에 대응하지 못한다.
- Fixed Routing
- 모든 근원지-목적지 쌍에 대해 한 경로씩을 미리 결정해 표로 갖고 있다.
- 경로가 바뀌지 않으므로 관리가 쉽다.
- 중간 노드가 고장 나면 통신이 끊긴다.
- Flooding
- 들어온 패킷을 도착한 링크를 제외한 나머지 모든 링크로 복사해 내보낸다.
- 목적지까지 가는 경로가 하나라도 존재하면 반드시 도달한다. 지연도 최소가 된다.
- 대신 같은 패킷이 망 전체에 퍼져 트래픽 부하가 매우 크다. 홉 카운트나 일련번호로
중복을 걸러 내야 한다.
- 라우팅 정보를 전파하거나 브로드캐스트를 구현할 때 쓴다.
- Random Routing
- 들어온 패킷을 내보낼 경로를 무작위로 하나만 골라 전송한다.
- 플러딩의 단순성과 견고함은 유지하면서 트래픽 부하를 훨씬 줄인 방식이다.
- 경로가 최적이라는 보장이 없어 지연이 커질 수 있다.
- Adaptive Routing; 동적 라우팅
망의 변화하는 상태에 반응해 경로를 결정한다. 회선 상태, 지연, 혼잡도 등의 정보를 주고받으며 라우팅 테이블을 갱신한다.
- 고립 적응 : 자기 노드가 가진 정보만으로 판단한다 (예: 핫 포테이토)
- 분산 적응 : 이웃 노드와 정보를 교환한다. 거리 벡터 라우팅이 여기에 속한다.
- 중앙 집중 적응 : 라우팅 제어 센터가 전체 경로를 계산해 배포한다.
실제 망에서는 RIP, OSPF 같은 라우팅 프로토콜이 적응 라우팅을 구현한다.
| 방식 | 경로 결정 | 부하 | 망 변화 대응 |
|---|---|---|---|
| 고정 경로 배정 | 미리 정한 하나 | 낮다 | 못 한다 |
| 플러딩 | 모든 링크 | 매우 높다 | 필요 없다 |
| 랜덤 라우팅 | 무작위 하나 | 낮다 | 못 한다 |
| 적응 라우팅 | 상태를 보고 계산 | 중간 | 한다 |
