Routing Algorithms

네트워크 계층: 제어 플레인

네트워크 계층에서 제어 플레인은 라우팅 알고리즘을 통해 네트워크의 각 노드가 패킷을 어디로 보내야 할지 결정하는 역할을 한다. 전통적인 라우팅 알고리즘과 소프트웨어 정의 네트워킹(SDN)으로 나눌 수 있다.

라우팅 알고리즘

라우팅 알고리즘의 목표는 출발지에서 목적지로 데이터를 전달할 때 최적의 경로(최소 비용 경로)를 결정하는 것이다. 이 과정에서 "좋은" 경로는 최소 비용, 가장 빠른 경로, 또는 혼잡이 가장 적은 경로를 의미한다.

그래프 추상화

네트워크는 그래프로 추상화할 수 있다. 각 라우터는 그래프의 노드로, 라우터 간의 링크는 그래프의 간선으로 표현된다. 간선의 비용은 대역폭, 혼잡도, 또는 고정된 값에 따라 결정된다.

라우팅 알고리즘의 분류

1. 링크 상태 알고리즘: 모든 라우터가 네트워크 전체의 링크 비용을 알고 있으며, 이 정보를 바탕으로 경로를 계산한다.
2. 거리 벡터 알고리즘: 각 라우터는 이웃 라우터와 비용 정보를 교환하며, 점진적으로 경로를 계산한다.

정적 또는 동적

• 정적 라우팅: 경로가 잘 변경되지 않는 경우.
• 동적 라우팅: 네트워크 상태 변화에 따라 경로가 자주 변경되는 경우.

---

링크 상태 라우팅 알고리즘 (Dijkstra 알고리즘)

• Dijkstra 알고리즘은 네트워크의 모든 노드와 링크 비용을 알고 있는 상태에서 동작한다.
• 각 노드는 최단 경로를 계산해 자신에게 필요한 포워딩 테이블을 생성한다.
• 알고리즘 동작 방식:
  • 초기 상태에서 출발 노드를 선택하고, 그 노드와 인접한 노드들의 경로 비용을 계산한다.
  • 경로 비용이 가장 작은 노드를 선택해 해당 노드를 확정하고, 이를 반복해 모든 노드의 최단 경로를 구한다.

Dijkstra 알고리즘 예시 및 풀이법

Dijkstra 알고리즘 예시

• 노드 u에서 시작해 그래프의 모든 노드로의 최단 경로를 계산한다.
• 각 노드에 대해 경로 비용을 계산하고, 갱신된 경로 정보를 바탕으로 최단 경로를 확정한다.

---

거리 벡터 라우팅 알고리즘 (Bellman-Ford 알고리즘)

• 각 라우터는 자신과 직접 연결된 이웃 라우터와 거리 정보를 주기적으로 교환하며, 최적 경로를 계산한다.
• Bellman-Ford 방정식: Dx(y) = min {c(x,v) + Dv(y)}, 여기서 c(x,v)는 x에서 v로 가는 링크의 비용, Dv(y)는 v에서 y로 가는 경로 비용이다.

 

Bellman-Ford 알고리즘 예제 및 풀이법

거리 벡터 알고리즘의 동작 방식

• 각 노드는 이웃 노드로부터 거리 벡터 정보를 받아 자신의 경로를 업데이트한다.
• 주기적인 업데이트와 네트워크 상태 변화에 따라 경로가 지속적으로 갱신된다.

---

LS와 DV 알고리즘 비교

1. 메시지 복잡도:
   • 링크 상태 알고리즘은 모든 노드가 네트워크 전체의 링크 상태를 알아야 하므로 메시지 복잡도가 높다.
   • 거리 벡터 알고리즘은 이웃 간의 정보만 교환하므로 메시지 복잡도가 상대적으로 낮다.
2. 수렴 속도:
   • 링크 상태 알고리즘은 O(n^2)의 계산 복잡도를 가지며, 수렴 속도가 빠르다.
   • 거리 벡터 알고리즘은 수렴 속도가 느릴 수 있으며, 특히 count-to-infinity 문제(무한루프)가 발생할 수 있다.
3. 견고성:
   • 링크 상태 알고리즘은 한 노드가 잘못된 정보를 광고하더라도 다른 노드에는 영향을 미치지 않는다.
   • 거리 벡터 알고리즘에서는 잘못된 정보가 네트워크 전체에 전파될 수 있다.

---

BGP (Border Gateway Protocol)

BGP는 자율 시스템(AS) 간의 라우팅을 관리하는 프로토콜이다. BGP는 각 자율 시스템이 인터넷의 다른 자율 시스템과 경로 정보를 교환할 수 있도록 한다.

BGP의 주요 기능

• AS-PATH: 경로를 광고한 자율 시스템의 목록을 포함한다.
• NEXT-HOP: 특정 목적지로 가기 위한 다음 홉 라우터의 IP 주소를 포함한다.
• 정책 기반 라우팅: 각 자율 시스템은 자신이 허용하는 경로를 선택하거나 거부할 수 있다.

eBGP와 iBGP

• eBGP: 외부 자율 시스템 간의 경로 정보 교환을 담당한다.
• iBGP: 내부 자율 시스템 내에서 경로 정보를 전파한다.

---

OSPF (Open Shortest Path First)

OSPF는 링크 상태 알고리즘을 사용하는 내부 게이트웨이 프로토콜이다. 자율 시스템 내에서 가장 널리 사용되는 라우팅 프로토콜 중 하나이다.

OSPF의 주요 특징

• 각 라우터는 네트워크의 전체 링크 상태 정보를 바탕으로 최단 경로를 계산한다.
• Dijkstra 알고리즘을 사용해 경로를 계산하며, 링크 상태 광고(LSA)를 통해 모든 라우터에 링크 상태 정보를 전파한다.
• OSPF는 계층적 구조를 지원해 대규모 네트워크에서도 효율적으로 동작할 수 있다.

---

계층적 OSPF

OSPF는 두 개의 계층으로 나뉜다:

1. 지역(Local Area): 각 지역 내에서 링크 상태 정보가 공유된다.
2. 백본(Backbone Area): 각 지역 간의 라우팅 정보를 공유하며, 백본 라우터가 다른 지역으로의 경로를 요약해 광고한다.

---

라우팅 정책과 성능

1. 정책: 자율 시스템 간 라우팅에서는 각 AS 관리자가 자신의 네트워크를 경유하는 경로를 제어하려 한다.
2. 성능: 내부 라우팅에서는 성능이 중요하게 고려되며, 외부 라우팅에서는 성능보다는 정책이 우선시된다.

---

라우팅 확장성

인터넷은 수십억 개의 목적지가 존재하므로, 모든 목적지를 라우팅 테이블에 저장할 수 없다. 이를 해결하기 위해 자율 시스템(AS)을 사용해 네트워크를 계층화하고, 각 자율 시스템 내에서 경로를 요약해 저장한다.