라우팅 알고리즘

2024.03.13 15:17

라우팅 알고리즘

Dynamic Routing을 구현하는 알고리즘들에 대해 자세히 알아보자
Distance-Vector Routing Argorithm
- 인접 라우터와 정보 공유하여 목적지까지의 거리와 방향을 결정하는 라우팅 프로토콜 알고리즘
- 벨만-포드(Bellman-Ford) 알고리즘 사용
- https://ko.wikipedia.org/wiki/거리_벡터_라우팅_프로토콜
  Terminal window
```
dist[v]<=dist[u]+w(u,v)
```
- Count to Infinity 문제가 일어날 수 있음
  - 수평 분할: C가 A에 도달하는 최소 경로에서 B를 거쳤다는 것을 안다면, 이 정보를 다시 B에게 광고할 필요가 없다. 경로 정보를 받아온 노드에는 다시 정보를 보내지 않도록 하는 것이 수평 분할 방식이다.
    
    만약 타이머를 써서 테이블의 오래된 정보를 삭제한다면, 타이머 때문에 경로가 사라진 건지(이 경우 갱신 필요) 수평 분할 정책으로 인해 소식이 안 오는건지 구분이 불가능
  - 포이즌 리버스: 포이즌 리버스는 수평분할에서 일어나는 문제를 해결할 수 있다. C가 A에 대한 정보를 광고하되, 만약 송신자가 노드 A인 경우 거리값을 무한대로 설정해서 값이 사용되지 않도록 한다.
- 장점
  - 구현이 간단하고 쉽다.
  - 작은 네트워크에서 잘 작동한다.
  - 라우터가 자신의 이웃에 대한 정보만 알면 되므로 라우팅 테이블이 비교적 작다.
- 단점
  - 컨버전스 시간(모든 라우터가 전체 네트워크 경로를 합의하는 데 걸리는 시간)이 길 수 있다.
  - 확장성이 제한적이다.
  - 큰 네트워크에서는 잘 동작하지 않을 수 있다.
- 대표 프로토콜: RIP, IGRP
Link-State Routing Argorithm
- 링크 상태 정보를 모든 라우터에 전달하여 최단 경로 트리를 구성하는 라우팅 프로토콜 알고리즘
- 다익스트라(Dijkstra) 알고리즘 사용
- 동작과정
  1. 이웃을 파악하기 위해 hello 패킷을 보낸다. 응답이 오면 이웃이 있는 것이고 없으면 존재하지 않는 것이다.
  2. 각 라우터마다의 cost를 측정하기 위해서 ping 메세지를 보낸다.
  3. cost 정보를 뿌리기 위한 link state 패킷을 만든다.
    Terminal window
    distance[a][c]>distance[a][b]+distance[b][c]가 성립한다면 distance[a][c]=distance[a][b]+distance[b][c];
  4. 만든 패킷을 도메인 내의 다른 라우터들에게 브로드캐스트 한다.(Flooding)
  5. 다른 노드들도 모두 브로드캐스트하므로 받은 정보를 통해 다익스트라 알고리즘을 돌려 shortest path를 구성한다.
- 대표 프로토콜: OSPF(Open Shortest Path First)
Path-Vector Routing Argorithm
- 자신의 패킷이 통과하는 것을 어떤 라우터를 지나는 것을 금지하고 싶은 경우가 있을 수 있다.
  - (라우터가 충분한 보안을 제공하지 못하거나, 정책때문에 특정 지역을 피해야 하는 경우)
  - 그러나 위에서 얘기한 Distance-Vector와 Link-State 라우팅은 최소비용을 목표로 하기 때문에 이런 정책을 설정할 수 없다.
- ISP 사이에 패킷의 경로를 사용하기 위해 설계되었다.
- 발신자가 경로에 적용한 규칙을 사용하여 경로를 결정한다.
- 스패닝 트리를 사용하여 경로를 결정한다. (최소비용 X, 지정한 규칙에 따라)
- 동작 과정
  - 노드가 부팅될 때 이웃으로부터 얻는 정보 기반으로 경로 벡터를 작성한다.
  - greeting 메시지를 근접 라우터에 전송하여 이웃에 대한 정보를 수집한다.
  - 이웃으로부터 경로 벡터를 전달받아 벨만-포드 방정식과 비슷한 방정식을 사용하여 갱신된다. 최소비용을 찾는 대신 규칙에 맞는 최선의 경로를 선택하도록 한다.
- 장점
  - 전체 네트워크에 대한 정확한 정보를 가지고 있으므로 최적의 경로를 결정하는데 더 효과적이다.
  - 컨버전스 시간이 짧다.
  - 복잡하고 큰 네트워크에서도 잘 동작한다.
- 단점
  - 각 라우터가 전체 네트워크에 대한 정보를 유지해야 하므로 메모리 사용량과 CPU 사용량이 많다.
  - 구현 및 관리가 복잡할 수 있으며, 초기 설정 비용이 비쌀 수 있다.
라우팅에서는 대부분 IGP로 OSPF(Link-State Routing)와 BGP가 많이 사용된다. EGP로는 대부분 BGP(Distance-Vector)가 사용된다.

참고

l1networkaccesslayer아날로그, 디지털 신호와 전송 라우터ECMP 라우터라우터 라우터멀티캐스트 라우팅 l2internetlayerCIDR l2internetlayerICMP