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

라우팅 프로토콜

라우팅(Routing)이란?

• 데이터(패킷)를 보내려면 어떤 경로로 보낼지 결정해야 한다.
• 이 경로를 결정해주는 것이 라우터(Router)이며, 이때 쓰는 규칙과 알고리즘을 라우팅 프로토콜이라고 한다.

 

“좋은 경로”의 기준

• 비용(cost): 낮을수록 좋음 (ex. 더 짧은 거리, 더 빠른 링크)
• 속도: 빠를수록 좋음
• 혼잡도: 적을수록 좋음

 

라우팅 알고리즘의 분류

기준	설명
전역 vs 분산	전체 지도를 다 아는가? or 근처 이웃만 아는가?
정적 vs 동적	길이 고정돼 있는가? 자주 바뀌는가?

 

• 전역 (Global, Link-State): 모든 정보를 가지고 계산 (ex. 다익스트라)
• 분산 (Decentralized, Distance-Vector): 이웃과 협업하며 계산 (ex. 벨만-포드)

 

Link-State 알고리즘 (Dijkstra)

핵심 특징

• 모든 라우터가 전체 지도를 알고 있음
• 각 라우터는 자기 자신을 출발점으로 모든 노드까지 최소 비용을 계산
• 계산 결과는 포워딩 테이블에 저장됨

 

절차 설명 (다익스트라 알고리즘)

1. 시작: 자기 자신을 확정된 집합(N’)에 넣음
2. 가장 가까운 이웃 선택: 아직 확정 안 된 노드 중 비용(D)이 가장 작은 노드 선택
3. 확정 집합(N’)에 추가
4. 인접 노드들의 비용 갱신: 새롭게 확정된 노드를 경유할 때 더 비용이 적다면 갱신
5. 모든 노드가 확정될 때까지 반복

 

Distance Vector 알고리즘 (Bellman-Ford)

핵심 특징

• 이웃 정보만 알고 있음
• 이웃끼리 서로 Distance Vector 정보를 교환하며 최소 경로 추정
• 시간이 지나면서 점점 실제 거리로 수렴

 

핵심 수식

d_x(y) = min { c(x,v) + d_v(y) }

 

• x가 목적지 y까지 가려면 이웃 v를 통해 가야 하니까 → 이웃까지의 거리 + 이웃에서 y까지의 거리

 

작동 방식

• 각 라우터는 자기 Distance Vector를 이웃에게 보냄
• 이웃의 정보를 이용해 자기 Distance Vector를 업데이트
• 업데이트되면 다시 이웃에게 전달 → 반복
• → 전체 네트워크에 비용 정보가 퍼지며 점점 정답에 가까워짐

 

문제점: Count-to-Infinity

무한 루프 문제

• 어떤 경로가 끊어졌다는 사실이 늦게 퍼짐
• 잘못된 정보가 계속 갱신되면서 비용이 계속 증가
• → 무한대처럼 커짐

 

해결책: Poisoned Reverse

• “저쪽으로는 가지 마!” 하고 일부 이웃에게 일부 목적지에 대해 무한대라고 알림
• 루프를 완화할 수는 있지만 완전히 해결되지는 않음

 

Link-State vs Distance Vector 비교

항목	Link-State (Dijkstra)	Distance Vector (Bellman-Ford)
데이터	전체 네트워크 정보	이웃과의 거리 정보
계산 방식	각자 계산 (중앙 집중 느낌)	이웃끼리 협업 (협동 분산)
장점	빠르고 정확, 루프 적음	구현 쉬움, 메시지 적음
단점	정보량 많음, 복잡함	느리고 루프 생김
루프 발생	거의 없음	발생 가능 (Count-to-infinity)