1. 라우팅 알고리즘
라우팅 알고리즘을 분류하는 첫 번째 방식은 다음과 같다.
- 중앙 집중형 라우팅 알고리즘(centralized routing algotrithm)
- 분산 라우팅 알고리즘(decentralized routing algorithm)
라우팅 알고리즘을 분류하는 두 번째 방식은 다음과 같다.
- 정적 라우팅 알고리즘(static routing algorithm)
- 종적 라우팅 알고리즘(dynamic routing algorithm)
세 번째 방식은 부하에 민감한지 아닌지에 따른다.
1.1 링크 상태(LS) 라우팅 알고리즘
링크 상태 알고리즘에서는 네트워크 토폴로지와 모든 링크 비용이 알려져 있어서 링크 상태 알고리즘의 입력값으로 사용될 수 있다. 대표적인 알고리즘이 바로 다익스트라 알고리즘(Dijkstra's algorithm) 이다.
다익스트라 알고리즘은 k번째 반복 이후에 k개의 목적지 노드에 대해 최소 비용 경로가 알려지며 이 k개의 경로는 모든 목적지 노드로의 최소 비용 경로 중에서 가장 낮은 비용을 갖는 k개의 경로다.
1.2 거리 벡터(DV) 라우팅 알고리즘
거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다. 거리 벡터 알고리즘을 통한 최소 비용 경로의 비용은 벨만-포드(Bellman-Ford) 식에 의해 다음처럼 나타낼 수 있다.
하지만 DV 알고리즘은 경로비용이 감소하는 경우에는 전체에 빠르게 퍼지지만, 증가하는 경우에는 그렇지 않다. 경로비용이 증가하는 경우 이는 빠르게 퍼지지 않으며, 무한 계수 문제를 발생시킨다.
무한 계수 문제는 포이즌 리버스(poison reverse) 문제를 통해 해결 할 수 있다. 경로비용이 증가한 것을 아는 노드에게 다른 경로가 존재하지 않음을 알린다.(선의의 거짓말) 결국 노드는 비용이 증가한 경로를 사용하고 이에 대한 정보가 다른 노드에게 전파된다. 그리고 다른 노드들은 자신들의 거리 정보를 다시 전파해준다. 즉, 선의의 거짓말을 통해 역경로를 차단하는 것이다. 하지만 3개 이상의 노드를 포함한 루프는 포이즌 리버스로는 감지할 수 없다.
1.3 링크 상태 알고리즘과 DV 알고리즘의 비교
| LS 알고리즘 | DV 알고리즘 | |
|---|---|---|
| 메시지 복잡성 | 링크 비용이 변할 때마다 모든 노드에게 전달되어야함 | 매번 반복마다 직접 연결된 이웃끼리 메시지 교환 |
| 수렴 속도 | O(N^2) 알고리즘 | 천천히 수렴하고 라우팅 루프/무한 계수 문제 발생 가능 |
| 견고성 | 경로계산이 분산되어 어느 정도의 견고성을 제공 | 잘못된 계산을 전파할 수 있음 |
2. 인터냇 AS 내부 라우팅: OSPF
AS: autonomous system(자율 시스템)
OSPF 란 개방형 최단 경로 우선(open shortest path first) 을 의미한다. OSPF는 링크 상태 정보를 플러딩(flooding) 하고 다익스트라 최소 비용 경로 알고리즘을 사용하는 링크 상태 알고리즘이다. 각 라우터는 전체 AS에 대한 완벽한 토폴로지 지도를 얻는다.
OSPF에 구현된 개선사항들은 다음과 같이 요약된다.
- 보안: 라우터들 간의 정보 교환을 인증할 수 있다.(MD5)
- 복수 동일 비용 경로
- 유니캐스트와 멀티캐스트 라우팅의 통합지원
- 단일 AS 내에서의 계층 지원
자세한 내용은 [Huitema 1998, Moy 1998, RFC 2328] 참고.
3. ISP 간의 라우팅: BGP
실제 인터넷의 모든 AS는 경계 게이트웨이 프로토콜(Border Gateway Protocol) 이라고 불리는 동일한 AS간 라우팅 프로토콜을 사용한다. 일반적으로 BGP 라고 알려져 있다. BGP는 DV 알고리즘처럼 분산형 비동기실 프로토콜이다.
3.1 BGP의 역할
AS 간 라우팅 프로토콜로서 BGP는 각 라우터에게 다음과 같은 수단을 제공한다.
(1) 이웃 AS를 통해 도달 가능한 서브넷 프리픽스 정보를 얻는다.
(2) 서브넷 주소 프리픽스로의 가장 좋은 경로를 결정한다.
3.2 BGP 경로 정보 알리기
AS에서 각각의 라우터들은 게이트웨이 라우터 또는 내부 라우터 다.
BGP 연결은 179번 포트를 이용해 반영구적인 TCP 연결을 통해 BGP 메시지를 주고받는것이다. 이 연결은 AS 외부/내부 여부에 따라 eBGP/iBGP로 구분된다. 이를 통해 경로 정보(프리픽스 정보)를 AS간에 주고받는 것이다.
3.3 뜨거운 감자 라우팅
뜨거운 감자 라우팅(hot potato routing) 은 가장 단순한 라우팅 알고리즘이다.
라우터는 서브넷 x까지의 경로를 BGP를 통해 파악하고, 해당 경로로 연결되는 게이트 웨이 중 게이트 웨이까지의 비용이 가장 적은 것이 선택된다.(이때 AS 내부 프로토콜이 사용된다.) 즉, AS 외부의 비용은 전혀 고려하지 않는 라우팅 알고리즘이다.
3.4 IP 애니캐스트
BGP는 AS 간 라우팅 외에도 종종 DNS에서 흔히 사용되는 IP 애니캐스트 서비스를 구현하는 데도 활용된다. IP 애니캐스트 설정 단계에서 CDN 사업자는 자신의 서버 여러 대에 동일한 IP 주소를 할당하고 표준 BGP를 활용하여 이 주소를 서버 각각으로부터 알린다. BGP 라우터가 이 IP 주소에 대한 복수 개의 경로 알림 메시지를 받으면 이를 동일한 물리적 위치로의 서로 다른 경로에 대한 정보를 제공받고 있는 것으로 생각한다. 각 라우터는라우팅 테이블을 설정하면서 BGP 경로 선택 알고리즘을 수행하여 해당 IP 주소로의 최고의 경로를 골라낸다.
하지만 실제로 CDN 사업자는 일반적으로 IP 애니캐스트를 사용하지 않는다. 왜냐하면 BGP 라우팅이 변경되면 하나의 TCP 연결에 속한 패킷들이 서로 다른 복제 웹 서버로 도착될 수 있기 떄문이다.
그러나 DNS 시스템에서는 DNS 질의를 가장 가까운 루트 DNS 서버로 전달하기 위해 IP 애니캐스트가 광범위하게 사용된다.
4. SDN 제어 평면
SDN 구조의 네 가지 특징은 다음과 같이 정리된다.
(1) 플로우 기반 포워딩
(2) 데이터 평면과 제어 평면의 분리
(3) 네트워크 제어 기능이 데이터 평면 스위치 외부에 존재
(4) 프로그램이 가능한 네트워크
4.1 SDN 제어 평면
- 통신 계층: SDN 컨트롤러와 제어받는 네트워크 장치들 사이의 통신
- 네트워크 전역 상태 관리 계층: SDN 제어 평면의 궁극적인 제어 결정
- 네트워크 제어 애플리케이션 계층과의 인터페이스
4.2 OpenFlow 프로토콜
OpenFlow 프로토콜은 TCP 상에서 디폴트 포트번호 6653을 가지고 동작한다.
컨트롤러가 제어되는 스위치로 전달하는 중요한 메시지는 다음과 같다.
- 설정
- 상태 수정
- 상태 읽기
- 패킷 전송
SDN으로 제어되는 스위치에서 컨트롤러로 전다로디는 주요 메시지는 다음과 같다.
- 플로우 제거
- 포트상태
- 패킷 전달
5. 인터넷 제어 메시지 프로토콜:ICMP
ICMP는 호스트와 라우터가 서로 간에 네트워크 계층 정보를 주고받기 위해 사용된다. 전형적인 사용 형태는 오류 보고다.
ICMP는 IP 데이터그램에 담겨 전송되므로 구조적으로는 IP 바로 위에 있다. ICMP 메시지에는 타입(type)과 코드(code) 필드로 구성된다.
ping 프로그램은 타입8 코드0 인 ICMP 메시지를 특정 호스트에 보내고, 목적지 호스트는 에코 요청을 보고 타입0 코드0인 ICMP 에코 응답을 보낸다. 대부분의 TCP/IP 구현은 ping 서버를 운영체제에서 직접 지원한다. 즉 ping 서버는 별도의 프로세스가 아니다.
Traceroute 또한 ICMP를 이용한다.
