[네트워크] 라우팅 알고리즘

라우팅 알고리즘 : 네트워크 계층에서 출발지에서 목적지까지 패킷을 전달할 때 사용하는 것

정적 라우팅 : 현재의 상태에서 어떤 곳으로 패킷을 보내야 목적지에 도달하는 지를 찾는 알고리즘 ex) 최단 경로, 플러딩

동적 라우팅 : 시시각각 라우터의 상태를 감지하여 경로를 변경하는 알고리즘 ex) 거리벡터 라우팅, 연결상태 라우팅, 계층적 라우팅

 

그래프 : 라우터들과 통신선의 연결을 표현한 것, 노드(라우터)와 선(통신선)의 집합

통신선은 양방향이기 때문에 방향성이 없는 선

선 위에 적혀있는 숫자들은 패킷을 전송하는데 걸리는 시간 혹은 거리를 의미

 

라우팅 알고리즘의 목적 : 각 라우터로 가는 가장 빠른 경로를 찾는 것, 최단 경로를 결정하면 트리(사이클이 없는 그래프) 형태

 

최단경로 알고리즘(다익스트라 알고리즘) : 새로운 라우터가 집합에 들어오면 집합에 속한 라우터들에서 보이는 경로 중 가장 짧은 경로를 찾아 집합에 넣는 방식

초기값 => 시작 노드를 집합에 넣음
모든 노드가 집합에 들어갈 때까지 다음을 반복
{
    1. 집합에 있는 모든 노드에서 바로 보이는 노드의 거리 계산
    2. 집합에 있는 노드를 제외한 가장 작은 값을 가진 노드 선택
    3. 선택된 노드를 집합에 삽입
}

 

각 노드에는 (시간, 경로정보) 형식으로 정보가 저장되며, 초기 값은 (∞, -)로 설정

1. 초기화
   • 출발 노드 A의 값은 (0, A)로 설정 (A에서 A까지는 시간이 0이므로)
   • 다른 모든 노드의 값은 (∞, -)
2. 첫 번째 반복: A에서 시작
   • 집합 {A} 생성 (A는 방문된 노드 집합에 추가)
   • A에서 직접 연결된 노드를 업데이트:
     • B의 값: (2, A) (A에서 B까지 2ms)
     • C의 값: (6, A) (A에서 C까지 6ms)
3. 두 번째 반복: 가장 짧은 값 B 추가
   • B의 값 (2, A)가 가장 작으므로 B를 집합에 추가: {A, B}
   • B에서 연결된 노드(D, E)를 업데이트:
     • D의 값: (3, B) (A → B → D, 2ms + 1ms)
     • E의 값: (5, B) (A → B → E, 2ms + 3ms)
4. 세 번째 반복: 가장 짧은 값 D 추가
   • D의 값 (3, B)가 가장 작으므로 D를 집합에 추가: {A, B, D}
   • D에서 연결된 노드(C, E)를 업데이트:
     • C의 값: (5, D) (A → B → D → C, 3ms + 2ms)
     • E의 값: (4, D) (A → B → D → E, 3ms + 1ms)
5. 네 번째 반복: 가장 짧은 값 E 추가
   • E의 값 (4, D)가 가장 작으므로 E를 집합에 추가: {A, B, D, E}
   • E에서 연결된 노드(F)를 업데이트:
     • F의 값: (6, E) (A → B → D → E → F, 4ms + 2ms)
6. 다섯 번째 반복: 가장 짧은 값 C 추가
   • C의 값 (5, D)가 가장 작으므로 C를 집합에 추가: {A, B, D, E, C}
7. 여섯 번째 반복: 가장 짧은 값 F 추가
   • F의 값 (6, E)가 가장 작으므로 F를 집합에 추가: {A, B, D, E, C, F}

노드 번호	A	B	C	D	E	F
거리	0	2	5	3	4	6

---

플러딩 : 네트워크에 홍수를 일으켜 사장 빠른 길을 찾는 정적 라우터 방식

• 라우터들은 패킷이 들어온 선을 제외한 모든 선에 패킷을 복사하여 보냄 -> 패킷에는 지나온 라우터들을 적어 놓음 -> 가장 먼저 도착한 패킷에 적혀 있는 경로가 가장 빠른 경로
• 장점 : 알고리즘이 단순하여 구현하기 쉬움
• 단점 : 많은 패킷이 폭주하여 네트워크의 정체를 유발

 

거리벡터 라우팅 : 자신만의 라우팅 테이블을 만들고, 이를 다시 주변 라우터에게 전송하는 방식

• 알파넷 개발 초기에 많이 사용하던 동적 알고리즘
• 각 라우터들은 주기적으로 라우팅 테이블을 주고 받는데, 데이블에는 자신의 기주에서 다른 라우터까지 가는데 걸리는 시간이 명시
• 라우터까지의 거리에 대한 연속적인 값(벡터)

연결상태 라우팅 : 자신에게 연결된 라우터 정보만을 보내고, 최단경로 알고리즘을 사용즘 : 네트워크 계층에서 출발지에서 목적지까지 패킷을 전달할 때 사용하는 것

• 거리벡터 라우팅의 문제를 개선한 알고리즘
• 일련번호와 나이를 추가하여 잘못된 정보가 도착하는 것을 막고, 특정 라우터가 고장나는 것을 확인할 수 있도록 함

1. 인접한 라우터(이웃 라우터)들 파악
   • 자신 이웃 라우터neighbor router(자신과 직접 연결된 라우터)가 무엇인지를 파악하는 것. 라우터가 처음 시작되면 자신의 주변에 HELLO 패킷을 보내고, HELLO 패킷을 받은 라우터는 ACK 패킷을 보냄으로서 서로 연결된 것을 확인. 또한 HELLO 패킷이 전송된 시간을 계산
2. 라우팅 테이블을 주기적으로 모든 라우터에게 보냄(플러딩)
   • 이웃 라우터들이 파악된 후 라우터들은 주기적으로 테이블을 주고 받음. 연결상태 라우팅 알고리즘 에서 주고받는 테이블에는 라우터 이름, 일련번호, 나이, 자신에게 연결된 이웃 라우터의 거리 정보 가 적혀있음
3. 최단 경로 알고리즘을 사용하여 라우팅 테이블 만듦
   • 연결상태 라우팅에서 모든 라우터들로부터의 정보가 모아지면, 각 라우터들은 최단경로 알고리즘을 사용하여 모든 노드까지 가는데 걸리는 최소의 시간을 계산하여 라우팅 테이블을 만듬
   • 관리 테이블의 일련번호는 해당 라우터로부터 가장 최근에 받은 테이블의 일련번호를 의미 ➔ 늦게 도착한 일련번호 테이블은 폐기
   • 나이는 다음 테이블의 도착예정시간 ➔ 패킷이 도착한 후에 나이가 계속 줄어들다가 0이 될 때까 지 다음 테이블이 도착하지 않으면 해당 라우터가 고장난 것으로 판단 ➔ 일련번호도 0으로 만듦
4. 라우터 구조와 라우팅 테이블 값을 지속적으로 업데이트

 

---

	거리벡터 알고리즘	연결상태 알고리즘
경로설정 방식	거리의 방향	전체 구조를 고려함
거리계산 방식	라우터 거리 합산	전체 라우터 최단 경로 계산
사용 알고리즘	벨만-포드	다익스트라 최단경로
테이블 전달 범위	인접	전체 라우터
테이블 전달 주기	일정 주기	변화 발생 시
테이블 정보	라우팅 테이블	링크 상태 테이블
테이블 전송 정보	전체 테이블	변경된 일부 테이블
장점	알고리즘 간단 구성이 단순 쉽게 구현 가능	네트워크 변화 빠르게 반영 네트워크 트래픽 정음 무한루프 발생 안함 대규모 네트워크에 적합
단점	네트워크 변화가 느리게 반영 무한루프 발생 가능 주시적으로 많은 트래픽 발생 대규모 네트워크 부적합	CPU 부하 높음 계산에 많은 시간과 메모리 소모
사용 범위	외부 라우팅 프로토콜	내부 라우팅 프로토콜
주요 프로토콜	BGP	OSPF