Move Fast

▶ 인터넷에서의 라우팅

- 이전까지 알아본 라우팅 기법은 모두 이상적인 환경을 가정하고 있었는데, 이상적인 환경이란 “모든 라우터가 동일”하며, “하나의 네트워크”임을 의미한다.

- 현실에서는 아래와 같은 문제점을 가지게 된다.

• 규모의 확장(Scale) : 억 단위의 목적지(호스트)로 인해 모든 목적지를 라우팅 테이블에 저장할 수 없다는 것과 라우팅 테이블 정보의 교환은 링크의 대역폭을 고갈시킨다는 문제가 발생한다.

• 관리 자치권(Administrative autonomy) : 인터넷은 여러 네트워크의 집합으로 거대한 하나의 네트워크인데, 각 네트워크 관리자는 자신의 네트워크에서 라우팅을 제어하길 원한다는 문제가 발생한다.

▶ 자치 시스템(Autonomous System, AS)

- 라우터들을 영역으로 그룹화한 것으로 확장성(Scale) 문제를 해결한다.

(자치 시스템 외에 도메인으로도 확장성 문제를 해결 할 수 있다.)

- 인트라 AS 라우팅(intra-AS routing)

• 같은 자치 시스템(AS) 내부에 호스트와 라우터들 간의 라우팅 방식이다.

• AS 내의 모든 라우터들은 같은 인트라 도메인 프로토콜(intra domain protocol)을 수행한다.

• 다른 AS의 라우터들은 다른 인트라 도메인 프로토콜을 수행한다.

• 게이트웨이 라우터(Gateway Router) : 자신의 AS 내에서 가장자리에 있는 라우터로, 다른 AS의 라우터와 연결한다.

• ex) OSPE, RIP

- 인터 AS 라우팅(inter-AS routing)

• 서로 다른 자치 시스템(AS) 간의 라우팅 방식이다.

• 게이트웨이 라우터가 인트라 도메인 라우팅뿐만 아니라 인터 도메인 라우팅(inter domain routing)도 수행한다.

• ex) BGP

▶ Interconnected AS

- 포워딩 테이블은 인트라 AS & 인터 AS 라우팅 알고리즘에 의해 설정된다.

- 인트라 AS 라우팅은 해당 AS 내부에 목적지들에 대한 포워딩 테이블의 명부(Entry)를 설정한다.

- 인터 AS와 인트라 AS 라우팅 둘다 외부 목적지에 대한 포워딩 테이블의 명부(Entry)를 설정한다.

- 인터 AS의 작업 : AS1 안의 임의의 라우터가 AS1 밖으로 나가려는 데이터그램을 수신한다면, 해당 라우터는 게이트웨이 라우터로 패킷을 전달한다. 이 때, 여러 게이트웨이 라우터들 중 하나의 게이트웨이 라우터를 선택하는 방식이 필요한데 이는 “인터-AS 라우팅의 핵심 역할“이라고 볼 수 있다.

• 다른 AS를 경유하여 도달할 수 있는 목적지들을 학습한다.

• 이 도달 정보(라우팅 정보)를 AS1 내부의 모든 라우터들에게 전파한다.

- 인트라 AS 라우팅(Intra-AS Routing)

• 내부 게이트웨이 프로토콜(Interior Gateway Protocol, IGP)이라고도 한다.

• 대부분 흔히 인트라 AS 라우팅 프로토콜을 사용한다.

• 라우팅 정보 프로토콜(Routing Information Protocol, RIP) : 거리벡터 알고리즘이 구현되어 매 30초마다 거리벡터 값(DV)을 알린다.

• 개방형 최단경로 우선 프로토콜(Open Shortest Path First, OSPF) : IS-IS 라우팅 프로토콜과 본질적으로 유사하다.

• 내부 게이트웨이 라우팅 프로토콜(Interior Gateway Routing Protocol, IGRP) : 시스코(Cisco) 독점 프로토콜

▶ 개방형 최단경로 우선 프로토콜(OSPF)

- 개방형으로 라우팅 프로토콜이 공용으로 이용할 수 있다.

- RIP는 주로 하위 계층 ISP나 기업 네트워크 구축에 사용되는 반면, OSPF는 상위 계층 ISP들이 사용한다.

- 링크 상태 알고리즘(Link State Algorithm)을 사용한다.

• 다익스트라 알고리즘을 이용하여 최소 비용 경로를 계산한다.

• 링크 상태 패킷 정보를 전파한다.

• 각 노드에게 전체 AS의 토폴로지 맵이 주어진다.

- 라우터는 AS의 모든 라우터에게 OSPF 링크 상태 알림(라우팅 정보)을 브로드캐스트한다.

• 링크 상태 정보를 Flooding

• TCP, UDP가 아닌 IP를 통해 OSPF 메시지를 직접 전달한다. IP 데이터그램에 OSPF 메시지가 헤더가 아닌 data(페이로드)에 들어 있다.

- 보안(Security) : 모든 OSPF 메시지는 인증되어야 하므로, 아무나 라우팅 정보를 보낼 수 없다.

- 다수의 동일 비용 경로 허용 : 한 목적지까지 동일한 비용의 여러 경로가 존재할 때, 여러 경로를 사용할 수 있다. 

(RIP에서는 한 경로만 존재한다.)

- 각 링크에 다른 서비스 유형(Type Of Service, TOS)에 대해 동일 비용의 여러 경로(Equal Cost Multi Path, ECMP)의 측정값을 매긴다. 예를 들어 위성 링크의 비용을 최선(best-effort)의 경우 낮게 측정하고, 실시간(real-time)인 경우는 높게 측정한다. 즉, 위성 링크는 상황에 따라 비용(cost)이 바뀔 수 있다.

- 유니캐스트(Unicast)와 멀티캐스트(Multicast)를 통합 지원한다.

(Multicast OSPF(MOSPF)는 OSPF와 같은 토폴로지 데이터베이스를 사용한다.)

- 넓은 도메인 영역에서는 “계층적 OSPF”를 지원한다.

[ 파란색은 backbone area(백본 영역)이고, 점선 영역은 local area(지역 영역)이다. ]

- AS가 크면, Flooding 할 때 오버헤드가 증가한다. 이에 따라 제어 메시지(control message)가 증가하는데 이를 방지하기 위해 계층적으로 영역을 나눈다.

- 2계층 구조 : 지역 영역(local area)와 백본 영역(backbone area)

• 한 영역 내에서만 링크 상태를 광고하며, 바깥 노드는 축약된 정보만 받는다.

• 각 노드들은 상세한 영역 토폴로지를 가진다.

• 다른 영역의 네트워크에 대해서는 최단 경로의 방향만 알고 있다.

• AS(자치 시스템, 하나의 네트워크 관리자)에서 하나의 OSPF 영역만을 백본 영역으로 설정한다.

• boundary router : 트래픽 양을 줄이기 위해 계속해서 축약된 정보를 backbone 영역의 라우터들에게 전파한다. 다른 AS에 속한 라우터들과 연결한다.

• backbone router : 백본 내에서 OSPF 라우팅을 수행하는 비경계 라우터이다.

• area border router : 하나의 영역에서 네트워크에 거리를 요악하여 다른 영역 경계 라우터(area border router)들에게 알린다. 즉, 외부 영역으로 패킷 라우팅을 책임진다.

▶ 경계 게이트웨이 프로토콜(BGP)

- 사실상 “인터 AS 라우팅 프로토콜“을 의미한다.

- exterior BGP(eBGP) : 이웃 AS로부터 목적지 도달하기 위해 필요한 정보(서브넷 도달성 정보)를 얻는다. 라우터 간의 TCP기반의 통신이다.

- interior BGP(iBGP) : 모든 AS 내부의 라우터에게 도달성 정보를 전파한다. 즉 AS 내부에서 라우팅 정보를 주고받는다.

- 도달성 정보와 AS 정책을 기반으로 다른 네트워크에 “좋은 경로"를 결정한다.

- 서브넷이 자신의 존재를 외부 네트워크에게 알리도록 한다. 광고를 통해 그쪽으로 정보 전달이 가능하다.

[ 번개 모양의 꺾은 부분이 있는 선은 eBGP 연결이며, 구름 영역 내부의 직선은 모두 iBGP 연결이다. ]

- BGP 세션(session) : 두 개의 BGP 라우터(peer)가 반영구적 TCP 연결을 통해 BGP 메시지(라우팅 정보)를 교환한다.

- 다른 목적지 네트워크 프리픽스(prefixes)의 경로를 광고한다.  → 경로 벡터 알고리즘(Path Vector Algorithm)

- AS3의 게이트웨이 라우터가 경로 (AS3, X)를 AS2 게이트웨이 라우터에게 광고한다고 하면, AS3는 AS2에게 X로 향하는 데이터그램을 전달하겠다고 약속한다.

• (AS3, X) : X는 AS3를 거쳐옴을 의미한다.

- 경로 속성과 BGP route

• 광고된 네트워크 프리픽스(prefix)는 BGP 속성을 포함한다.

• 프리픽스(prefix) + 속성(attribute) = 루트(route)

• AS-PATH : 프리픽스 광고가 거쳐간 AS를 포함하는 리스트로 어딜 거쳐왔는지에 대한 라우팅 정보가 포함된다.

• NEXT_HOP : 다음 hop의 AS로 가기 위해 거쳐야하는 특정 내부 AS 라우터를 표시한다.

- 루트 광고를 수신하는 게이트웨이 라우터는 중요한 정책(important policy)을 통해 해당 광고의 수락 및 거절을 결정한다.

- 중요한 정책이란 여러 정보 중 우선순위를 결정하거나 정보의 수락 및 거절, 다른 이웃 AS들에게 경로를 알릴지 등을 결정하는 정책을 말한다.

- 경로 벡터(path verctor)의 전달 과정

1. AS2의 라우터 2c가 경로 광고(AS3, X)를 eBGP를 통해서 AS3의 라우터 3a로부터 수신한다.

2. AS2 정책을 기반으로, AS2 라우터 2c는 경로 정보(AS3, X)를 받아들이고, iBGP를 통해서 모든 AS2 내부 라우터들에게 전파한다.

3. AS2 정책을 기반으로, AS2 라우터 2a가 eBGP를 통해서 경로 정보 (AS2, AS3, X)를 AS1 라우터 1c에게 알린다.

- 게이트웨이 라우터는 목적지까지 다수의 경로에 대해 알 수 있다.

예를 들어, 위의 과정에서 AS3 라우터 3a가 바로 AS1 라우터 1c에게 경로정보 (AS3, X)를 전파할 수도 있다. 그 때는 AS1 라우터 1c가 AS2로부터 온 정보와 AS3로부터 온 정보 중 하나를 선택할 수 있다. 이후 iBGP를 통해 AS1 내부의 모든 라우터들에게 경로 정보를 알린다.

- BGP 메시지 : TCP 연결 상의 peer들 사이에서 교환되는 메시지로 아래와 같은 네 가지가 있다.

• OPEN : 다른 BGP 피어와의 연결, TCP 연결을 시작하고, 송신측 BGP 피어의 인증을 거친다.

• UPDATE : 새로운 경로정보를 광고하고, 오래된 정보는 철회한다.

• KEEPALIVE : 업데이트가 없어도 연결을 유지하며, OPEN 요청에 대한 ACK를 한다.

• NOTIFICATION : 이전의 메시지에 대한 에러를 보고하며, 연결 종료에도 사용된다.

▶ 포워딩 테이블 엔트리

- 라우터의 포워딩 테이블 엔트리에 프리픽스를 저장하는 방법 : AS 내에 특정 라우터가 수신하면 내부에 모든 다른 라우터들에게 경로 정보를 알린다.

예를 들어 라우터 a, b, c, d가 있다고 가정하자. c가 eBGP를 통해 경로 정보를 수신했다면, a, b, d에게 해당 정보를 알리고, a, b, d는 iBGP를 통해 c로부터 전달받은 목적지 X까지의 경로를 학습한다. 라우터 a는 OSPF 인트라 도메인 라우팅을 사용하여 c에 도달하는 출력 로컬 인터페이스 중 하나로 포워딩한다. 나머지 라우터 b와 d도 같은 행동을 수행한다. 그 때 목적지 X와 인터페이스 정보를 포워딩 테이블의 하나의 엔트리로 저장한다.

▶ BGP 경로 설정

- 라우터는 목적지 AS로 가는 다수의 라우팅 정보에 대해 배울 수 있고, 아래의 속성을 통해 하나의 정보를 선택한다.

- 지역 선호 값 속성(local preference value attribute)이 제일 높은 선호도 값의 루트를 선택, 이 속성은 정책에 의해 결정된다.

- 최단 AS-PATH : 똑같은 정보 중 최단 경로를 선택한다.

- 가장 가까운 NEXT-HOP 라우터를 갖는 경로를 선택한다. 즉, 경로의 비용이 최소인 라우터를 선택하는 방식으로 다음에 설명할 “핫 포테이토 라우팅” 방식이다.

- 위 세 개를 적용했음에도 여러 경로가 남아있다면 추가적인 기준을 사용한다.

▶ 핫 포테이토 라우팅(Hot Potato Routing)

- 언어적 의미는 뜨거운 감자를 만졌을 때 사람들이 뜨겁다며 빠르게 던지는 모습에서 따온 의미이다.

- 경로 정보를 가진 패킷이 왔을 때 큐가 짧은 쪽으로 빨리 보내는 라우팅 방식이다. 즉, AS 중에서는 짧은 경로의 AS로 빨리 내보낸다.

- 가장 작은 인트라 도메인 비용을 가진 로컬 게이트웨이 라우터를 선택한다.

예를 들어, 어떤 AS 내부에 라우터 a, b, c, d가 있다고 하고, d의 출력 인터페이스가 모든 라우터(a, b, c)와 연결되어 있다면 최저 비용을 가진 인터페이스로 패킷(경로 정보)을 전달한다. 이 때, 인터 도메인 비용은 고려하지 않는다.

▶ BGP 라우팅 정책

- ISP는 자신을 사용하는 네트워크(customer network)를 통해서만 트래픽(traffic)을 라우팅하기를 원한다. 다른 ISP 간의 트래픽이 전송되는 것을 방지하기 위함이다.

- A는 B와 C에게 경로 정보 Aw를 알린다. (Aw : A를 통해서 w로 정보 전달 가능하다라는 의미이다.)

- B는 C에게 경로 정보 BAw를 알릴지 말지 선택할 수 있다.

• B가 전송하지 않는다면, C는 w로 데이터를 전송할 때 절대로 B를 거치지 못한다. 대신 Aw를 받았기 때문에 A를 거쳐서 w로 데이터를 전송할 수 있다.

• B가 전송한다면 C는 B를 거쳐서 w로 데이터를 전송할 수 있다.

- C, A, w는 B의 customer network가 아니므로 CBAw 라우팅은 어떤 동작도 하지 않는다.

- C는 CBAw 경로를 학습하지 못한다.

- x는 두 provider network에 연결된 듀얼 홈 네트워크(dual-homed network)로, 두 ISP의 서비스를 받을 수 있다.

- x는 자신을 경유하여 B에서 C로 라우팅을 원하지 않는다. 따라서 X는 B에게 C로의 경로를 광고하지 않는다.

▶ 인터-AS & 인트라-AS 라우팅의 차이

- 정책(policy)

• 인트라-AS(내부AS) : 하나의 관리자가 제어하므로 정책 결정이 필요 없다.

• 인터-AS(외부AS) : 각 네트워크 관리자는 어떻게 트래픽이 라우팅되고, 누가 자신의 네트워크를 경유할 것인지를 제어한다.

- 확장성(scale) : 계층적 라우팅으로 인해 테이블 크기를 절약하고 업데이트 트래픽도 감소시킨다.

- 성능(performance)

• 인트라-AS : 성능에 초점을 맞춘다.

• 인터-AS : 성능보다 정책에 초점을 맞춘다. 최소 비용이 더 중요하기 때문이다.

▶ 인터넷 제어 메시지 프로토콜(ICMP)

- 네트워크 계층 정보를 통신하기 위해 호스트와 라우터들에 의해 이용되어진다.

- 오류 보고(error reporting)

목표 : 도달할 수 없는 호스트, 네트워크, 포트, 프로토콜 등을 보고하며, IP 데이터그램 전달 오류를 출발지 호스트에게 알리기

방법 : ping을 통해(like ping test) 에코 요청이나 응답을 한다.

- ICMP 메시지는 IP 데이터그램의 헤더가 아닌 데이터 영역(페이로드)에 저장되어 전송된다.

- ICMP 메시지 : 타입(type), 코드(code), 설명(description)으로 이루어진다. 에러 설명 부분은 8바이트이다.

- 아래는 ICMP 메시지 중 몇몇 설명에 대한 동작이다.

• source quench (congestion control – not used) -> 혼잡 상황을 라우터가 출발지에게 빨리 알려줌

• route advertisement -> 어떤 서브넷에 들어가면 ICMP 메시지를 통해 주기적으로 자신(라우터)을 광고한다.

• router discovery -> 내가 속한 서브넷의 라우터 정보를 받아온다.

• bad IP header -> 체크섬계산 오류시 전송되는 메시지 설명이다.

▶ Traceroute

- Traceroute 진단 프로그램 : 출발지와 목적지 사이의 라우터 이름과 주소를 추적하는 프로그램이다.

- ICMP 메시지를 이용한다.

- 지정된 목적지 경로에 따라 출발지에서 라우터까지 지연시간을 측정한다.

- 경로 상 모든 라우터의 동작 : 경로 상의 어떤 라우터 x에 대해 3개의 패킷을 송신한다면, 라우터 x는 송신자에게 패킷을 리턴한다. 그 다음, 송신자는 패킷 송신과 응답 사이 시간을 측정한다.

- Traceroute 원리

• 출발지는 목적지에 일련의 UDP 세그먼트를 보내고, 첫 번째 데이터그램의 TTL=1, 다음 hop을 거듭할수록 TTL=2, 3, 4, ... ,n 으로 계속 1씩 증가한다. UDP는 포트번호가 없다. (TTL 설정 방법)

• n번째 데이터그램이 n번째 라우터에 도착하면, 라우터는 데이터그램을 폐기한다.

• 출발지에 ICMP 메시지를 보낸다.(type:11, code:0)

• 메시지에 라우터의 이름과 IP주소가 포함된다.

• ICMP 메시지가 도착하면 출발지는 RTT를 계산한다.

- 표준 Traceroute 프로그램은 같은 TTL 값을 갖는 패킷을 3번 보낸다.

- 중단 조건(stopping criterion)

• UDP 세그먼트가 최종 목적지에 도착하고, 목적지가 ICMP port unreachable 패킷(type:3, code:3)을 반환하는데 여기서 UDP는 포트번호가 없으므로 오류를 반환한다.

• 그 다음 출발지가 이 ICMP 메시지를 받으면 traceroute를 중단한다.

▶ 네트워크 계층의 기능

- 포워딩(Forwarding) : 데이터 영역(Data Plane)의 기능으로, 포워딩 테이블을 탐색(look up)하여 라우터 입력 버퍼에서 출력 버퍼로 패킷을 전달한다.

-포워딩은 크게 (1)목적지 기반의 포워딩-전통적인 방식, (2)일반화된 포워딩-SDN 방식으로 두 가지가 있다.

- 라우팅(Routing) : 제어 영역(Control Plane)의 기능으로, 출발지에서 목적지까지 패킷의 헤더를 보고 전체 경로를 설정한다.

- 아래는 앞서 기술한 데이터 영역에 대한 정보(원리)가 포함되어 있다.

http://movefast.tistory.com/40

http://movefast.tistory.com/52

http://movefast.tistory.com/53

http://movefast.tistory.com/54

- 여기서는 제어 영역을 구성하는 정보를 알아볼 것이며, 우선 제어 영역의 구조에는 (1)라우터당 제어(분산적, 전통적 방식), (2)논리적으로 중앙 집중화된 제어(중앙 관리 방식, SDN) 방식으로 접근할 수 있다.

- 아래는 두 구조를 기반으로 포워딩 테이블을 계산하는 원리이다.

▶ 라우팅 프로토콜(Routing Protocol)

- 인터넷(Internet)은 Hop-by-Hop 라우팅 방식이라 하여 각 라우터는 다음 목적지까지만 안내한다.

- 이 때, 각 라우터마다 수신 호스트(최종 목적지)로 안내해주기 위해 각 라우터의 다음 목적지까지의 경로를 라우팅 프로토콜이 모두 결정한다.

- 송신 호스트(source host)에서 수신 호스트(destination host)로 네트워크의 라우터를 지나가는데 있어 “좋은 경로”를 결정하는 것을 목표로 한다.

- “좋은”은 “Good“을 직역한 것으로, 가장 빠르고 혼잡이 최소화되는 경로, 저렴한 비용 등 다른 일반적인 요소도 포함한다.

- “경로”는 “Path”를 직역한 것으로, 송신 호스트에서 수신 호스트로 가기 위해 지나갈 “라우터들의 순서”를 의미한다.

- Source Routing : 처음에 최종 목적지를 가기 위해 꼭 거쳐야 할 목적지(라우터)를 정해주는 기능이다.

- 아래는 네트워크의 경로를 그래프로 나타낸 것이다. 그래프 추상화는 네트워크 문맥 파악에 유용하게 사용된다.

[ 노란색은 라우터, 이어지는 선들은 경로이며, 숫자는 경로 비용(cost)이다. ]

• graph : G = (N, E) -> G는 그래프를 나타낸다.

• N : 라우터의 집합으로, 위의 그림은 N = { A, B, C, D, E, F, G } 이다.

• E : 링크의 집합으로, 위의 그림은 E = { (A, B), (A, D), (B, C), (B, E), (B, F), (D, F), (D, G), (E, F), (F, G) } 이다.

• c(x, y) : 라우터 x에서 라우터 y까지의 링크의 최소 비용으로, 비용이 적을수록 자료 전송율(bps)이 좋다. 혼잡이 많을수록 비용이 증가하며 이는 좋지 않다. 위의 그림에서 c(A, C) = 5 이다.

• Cost of Path (a, b, c, ... , z) = c(a, b) + c(b, c) + c(c, d) + ... + c(y, z) : 경로 비용이란 링크 비용의 합이다.

- 라우팅 알고리즘은 최소 비용의 경로를 찾는다. 추가로, 라우팅 경로 설정 시 정보 수집이 미리 이루어져야 하는데 위의 경우는 미리 정보가 주어진 경우이다. 소프트웨어적인 구현에 있어서 최단 경로를 찾는 자료구조가 활용된다.

▶ 라우팅 프로토콜의 분류(Classification)

- 포워딩 테이블을 계산하는 것은 “라우팅 알고리즘”의 일이다. 이 라우팅 알고리즘은 어떤 정보를 가지느냐에 따라 두 가지로 나뉜다.

- 링크 상태(Link State, LS) 알고리즘 : 모든 라우터들이 완벽한 토폴로지, 링크 비용 정보 등 각 라우터의 모든 정보(Global Info)를 가진다.

- 거리 벡터(Distance Vector, DV) 알고리즘 : 모든 라우터는 물리적으로 연결된 이웃 라우터의 링크 비용 정보만 가진다. 반복적인 계산과정과 이웃간의 정보 교환이 이루어진다.

- 처음에 송신 호스트와 수신 호스트가 정해지더라도, 라우터 간의 경로가 혼잡해지게 되어 비용이 증가하면, 최소 비용의 경로를 찾기 위해 “경로가 바뀌는“ 상황이 생긴다.

- 경로가 시간이 지남에 따라 느리게 변하거나 거의 일정한 것을 “Static”하다고 표현하며, 노드(링크)가 고정되어 있음을 의미한다. 링크 상태 알고리즘(LS)은 정적인 상태에서 경로를 설정한다.

- 경로가 빠르게, 많이 변하는 것을 “Dynamic”하다고 표현하며, 주기적으로 라우터끼리 정보를 주고받으며 링크 비용 변화에 대응한다. 거리 벡터 알고리즘(DV)은 동적인 상태에서 경로를 설정한다.

▶ 링크 상태(Link State, LS) 알고리즘

- 1단계, 정보수집 : Flooding 방식으로 망(net) 토폴로지, 링크 비용이 모든 노드에게 알려진다. 즉, 모든 노드들이 같은 정보를 가지게 된다.

- 2단계, 경로계산 : 출발지 노드에서 모든 다른 노드까지의 최소 경로 비용을 계산한다. 여기서 "다익스트라 알고리즘"(Dijkstra’s algorithm)이 사용된다.

- 3단계, 포워딩 테이블 생성 : 모든 라우터는 최단 경로 알고리즘(다익스트라)을 통해 생성된 “다음 hop에 대한 테이블”을 얻는다.

- Flooding 방식이란 “링크 상태 브로드캐스트”를 통해 홍수가 일어나듯 다른 라우터에서 받은 정보를 또 다른 라우터에게 알리는 방식이다. 중복된 정보가 수신되면 알아서 버린다.

- “링크 상태 브로드캐스트”는 라우터마다 자신의 로컬 링크 비용(link cost) 정보를 가지는데 다른 라우터와 이 정보를 주고받으면서 다른 라우팅 정보를 수집하는 것을 의미한다. Flooding 방식과 유사한 의미이다.

- 다익스트라 알고리즘에 사용되는 표기법

• c(x, y) : x에서 y까지의 링크 비용, 이웃 노드가 아닐 경우 무한대(∞)로 표시된다.

• D(v) : 출발지에서 목적지 v까지 경로의 현재 비용, 최소 비용을 발견하기까지의 비용을 현재 비용이라 한다. 현재 비용 중에 최소 비용을 찾는다.

• p(v) : 출발지에서 목적지 v까지의 경로에서 v 이전 노드(목적지, 라우터)

• N’ : 최소 비용 경로라고 명확하게 알려진 노드(목적지, 라우터)들의 집합

- 다익스트라 알고리즘의 코드

- 위의 이미지를 바탕으로, 출발지를 C라고 하고 목적지를 G라고 하였을 때의 C의 다익스트라 알고리즘 구현하기 

(실제로 위의 이미지 같은 자료는 라우팅 알고리즘에 제공되지 않습니다.)

• STEP 0 : C에서의 이웃 노드는 B밖에 없으므로, 나머지는 ∞로 표기합니다. B까지의 현재 비용은 그림과 같이 3입니다.

• STEP 1 : [step 0]에서 최소 비용이 되는 경로가 노드 B이므로 N’에 B가 추가도비니다. 이제 알고 있는 노드들(N‘의 원소)로 갈 수 있는 노드는 A, E, F로 세 경로가 있습니다. B는 이미 있으므로 계산하지 않아도 되고, D와 G는 지금까지 알고 있는 노드들과 이웃이 아니므로 ∞로 표기합니다.

C->B

• STEP 2 : [step 1]에서 현재 경로 중 최소 비용이 되는 경로는 노드 F이므로 N’에 F가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 A, D, E, G로 네 경로가 있습니다. B와 F는 이미 추가한 노드이므로 표기하지 않습니다.

C->B

C->B->F

• STEP 3 : [step 2]에서 현재 경로 중 최소 비용이 되는 경로는 노드 A와 E가 있으므로 N’에 A와 E가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 D, G로 두 경로가 있습니다. 나머지 노드는 이미 추가한 노드이므로 표기하지 않습니다.

C->B

C->B->F

C->B->A

C->B->E

• STEP 4 : [step 3]에서 현재 경로 중 최소 비용이 되는 경로는 노드 D가 있으므로 N’에 D가 추가됩니다. 이제 알고 있는 노드들(N’의 원소)로 갈 수 있는 노드는 G 하나만 있습니다. 나머지 노드는 이미 추가한 노드이므로 표기하지 않습니다.

C->B

C->B->F

C->B->A

C->B->E

C->B->F->D

• STEP 5 : [step 4]에서 현재 경로 중 최소 비용이 되는 경로는 노드 G가 있으므로 N’에 G가 추가됩니다. 모든 노드에 대하여 최소 비용 탐색이 끝났으므로 확장된 경로는 아래와 같습니다.

C->B

C->B->F

C->B->A

C->B->E

C->B->F->D

C->B->F->D->G

• 여기서 C에서 G까지의 최소 비용은 9가 되고, 아래는 C의 포워딩 테이블입니다.

• 어떤 목적지든 C에서는 다음 목적지가 B임을 알 수 있습니다.

- 다익스트라 알고리즘의 복잡도 : N‘에 없는 모든 노드들을 확인할 필요가 있으며, n개의 노드가 순서대로 살펴지기 때문에 n(n+1)/2 번의 비교횟수를 가진다. ->

- 더욱 효율적인 자료구조를 사용하여 복잡성을 감소할 수 있다. 위의 알고리즘 코드의 9번째 줄에서 w를 찾는데 "힙 자료구조"를 사용하는 것이다. 그 때의 복잡도는 O(nlogn) 가 된다.

▶ 거리 벡터(Distance Vector, DV) 알고리즘

- 벨만 포드 항등식(동적 프로그래밍에 자주 쓰임) : = min{c(x, v) +  }

• : x에서 y까지의 최소 비용 경로의 값

• c(x, v) : v는 x의 이웃노드이고, x와 v간의 경로 비용을 의미한다.

• : 모든 이웃 v에 대한 y까지의 거리

• min{ } : 괄호 안에 계산되어진 값들 중 최소값

• (이 때,  값은 v가 x에게 알려줌)

- 초기 상태에서 노드는 각 이웃들 간의 최소 거리 비용만 알고 있다.

-위의 그림에서 B에서 G까지의 거리를 벨만 포드 항등식을 사용하여 거리 벡터 알고리즘을 구현해보기

- B의 이웃노드는 A, E, F이므로(C는 G로 갈수 없으므로 제외한다.) 각 노드에서 G까지의 최소 비용 경로는 

 임을 노드 A, E, F는 알고 있다. 이 정보를 B에게 전달하면, B는 벨만 포드 항등식으로 계산한다.

node B :

-: x에서 네트워크 노드 중 임의의 노드 y까지의 최소 비용

- 거리벡터 값 (N : 네트워크 노드의 집합)

- 반복적, 비동기적 특성 : 로컬 링크 비용(c(x, v))이 변화가 생길 때마다 거리 벡터 값()이 갱신되며, 갱신된 노드는 이웃 노드에게 알리게 되고 따라서 다른 노드들도 거리 벡터 값을 갱신한다.(로컬 링크란 자신과 이웃간의 링크를 의미한다.)

- 분산적 특성 : 각 노드는 자신의 거리 벡터 값()의 변화가 있을 때만 이웃들에게 통지한다. 또는 이웃이 자신의 거리 벡터 값을 필요로 한다면 통지한다.

- 링크 비용 변화의 3단계

• 1단계 : 각 노드는 로컬 링크 비용의 변화(c(x, v))나 이웃(v)들로부터 통지( )를 받을 때까지 기다린다.

• 2단계 : 통지를 받으면 거리 벡터 값()을 다시 계산한다.

• 3단계 : 어떤 목적지에 대한 거리 벡터 값()이 변경되었다면 이웃에게 알린다. (단, 어디를 경유했는지는 없고, 비용에 대한 정보만 준다.)

- 링크 비용이 감소한 경우 해당 정보는 네트워크 전역에 빠르게 전파된다.

- 링크 비용이 증가한 경우 해당 정보는 네트워크 전역에 느리게 전파된다. 따라서 기존의 정보(이웃노드의 변화 전 거리벡터 값)를 유지한 채 다른 목적지까지의 거리벡터 값이 변경되면 기존의 정보가 적용되는 상황이 발생하고, 해당 노드는 이웃노드의 변화를 알 때까지 자신의 거리 벡터 값을 잘못 계산할 수 있다. 보통 정보 전달이 느리면 서로 잘못된 정보를 전달하게 되어 “무한 카운트 문제”가 발생한다.

- 무한 카운트 문제 예시) 노드 A와 노드 B간에 다른 노드로 보내야하는데 최소 경로로 서로가 지정되어 A->B,  B->A로 정보를 전달하게 되면 라우팅 루프가 발생한다.

- 포이즌 리버스(Poison Reverse) : 어떤 노드가 이웃노드에게 임의의 노드까지 가짜 거리벡터 값으로 ∞를 알려주는 것이다. 즉, 임의의 노드까지 가는데 자신을 거치지 말라는 의미이다. 이 방법은 무한 카운트 문제를 해결하기 위해 사용되나 세 개 이상의 이웃 노드를 포함한 루프인 경우 감지하지 못한다.

▶ 오동작 하는 경우(Robustness)

- 링크 상태(Link State, LS) 알고리즘 : 노드는 적절하지 못한 “링크 비용”을 알릴 수 있는데, 그럴 때 각 노드는 자신의 포워딩 테이블만 다시 계산한다.

- 거리 벡터(Distance Vector, DV) 알고리즘 : 노드는 적절하지 못한 “경로 비용”을 알릴 수 있는데, 그럴 때 각 노드의 테이블은 이웃 노드에게 이용되어지며 에러가 네트워크 전역에 전파된다.

▶ 일반화된 포워딩

- 앞전에 “목적지 기반의 포워딩”(http://movefast.tistory.com/40)에 대해 알아보았는데, 이 포워딩 방법은 목적지 IP 주소만을 가지고 포워딩하는 방식으로, 제어 영역(Control Plane)에 의해 생성된 “포워딩 테이블(Forwarding Table)”을 참고하여 패킷(데이터)이 전달되어진다.

- 지금부터 살펴볼 “일반화된 포워딩”기법은 제어 영역에 의해 생성되는 “플로우 테이블(Flow Table)”을 참고하여 패킷(데이터)를 전달한다. 아래는 해당 포워딩 기법을 이해하기 위해 필요한 개념을 소개한다.

- 각각의 라우터는 중앙에 집중된 라우팅 컨트롤러(중앙 관리 방식)에 의해 계산되고 배포된 Flow Table을 포함한다.

▶ 소프트웨어 정의 네트워킹(Software Defined Network, SDN)

- 등장 배경

• 네트워크 환경의 변화

• 트래픽 패턴(방식) 변화 : 트래픽이 데이터 센터를 중심으로 전환되고 있다.

• 가상화(VM)의 보편화로 호스트의 빈번한 이동
• 네트워크 관리의 필요성

- 소프트웨어로 네트워크 경로를 설정 및 제어 그리고 운용 관리를 처리할 수 있다.

- 즉, 하나의 물리 네트워크 환경에서 다수의 가상 네트워크 환경을 구축할 수 있다.

- 원리 : 라우터의 제어 부분과 데이터 전송 부분을 분리하고 개방형 인터페이스를 외부에 제공한다.

- “분리”라는 것은, 네트워크 장비가 포함된 인프라 계층은 “단순히 패킷을 전달”만 하는 역할을 하고, 소프트웨어 제어기(Controller)를 프로그래밍하여 “데이터의 흐름을 제어”하는 상황을 의미한다.

- 즉, 컨트롤러에서 데이터의 흐름을 제어하게 되면, 패킷이 발생했을 때 네트워크 장비는 패킷을 어디로 전달할지 컨트롤러에게 물어보고 결과를 반영한다.

▶ OpenFlow

- SDN을 구현하기 위해 처음으로 제정된 표준 인터페이스이다.

- OpenFlow 스위치, OpenFlow 컨트롤러로 구성되며, 흐름(flow) 정보를 제어하여 패킷의 전달 경로 및 방식을 결정한다.

- “흐름”이란 패킷의 출발지와 목적지 정보를 가진 데이터라고 볼 수 있다.

- OpenFlow 스위치 내부에는 "패킷 전달 경로와 방식에 대한 정보"를 가지고 있는 "Flow Table"이 존재한다.

- 기본 동작

1. 패킷 발생 시 Flow Table이 해당 패킷의 정보가 있는지 확인

-> 정보가 존재하면 패킷 바로 처리

-> 정보가 존재하지 않으면 OpenFlow 컨트롤러에게 해당 패킷에 대한 제어 정보를 요청

2. 스위치로부터 제어정보를 요청받은 컨트롤러는 내부에 존재하는 패킷 제어 정보를 확인하고, 해당 결과를 스위치에게 전달

3. 스위치는 받은 데이터를 Flow Table에 저장하고, 이후 동일 패킷 발생 시 Flow Table의 정보를 활용하여 패킷을 전달한다.

* FlowTable에 등록된 제어 정보는 영구적으로 저장하거나 정해진 시간 동안만 유지할 수 있다.

▶ OpenFlow 데이터 영역

- 흐름(flow) : 헤더 필드에 의해 정의되어지는데, 프레임의 2~5계층 헤더 필드값이 동일한 경우 같은 flow로 본다. IPv6에서는 흐름 라벨(flow label)로 빠르게 판단가능하다.

- 기존의 목적지 기반의 포워딩은 앞서 언급했듯이 단순히 목적지 IP주소만 보고 포워딩을 했으나 일반화된 포워딩은 몇 가지 간단한 패킷 처리 규칙이 있다.

• 패턴(Pattern) : 패킷의 헤더 필드값과 일치 여부를 결정

• 패턴이 일치한 패킷의 처리(Actions) : 해당 패킷을 삭제(drop), 전달(forward), 수정(modify), 또는 컨트롤러에게 전송한다.

• 우선순위(Priority) : 중첩되는 패턴을 구분한다.

• 통계(Counters) : 트래픽 양을 패킷 수와 바이트 수로 표시한다.

- 제어기가 계산하고 배포한 라우터의 Flow Table에는 라우터의 “match+action rules“이 정의되어 있다.

▶ match+action rules

- OpenFlow의 조건+처리 규칙(match+action rules)은 다양한 종류의 네트워크 장비에 통합적용된다.

- 조건처리 규칙은 match(해당 조건)를 만족한다면, action(처리) 할 것을 약속한 것이다.

- 라우터(Router)

• match : 가장 긴 목적지 IP 주소의 접두사(prefix)

• action : 링크로 전달

- 스위치(Switch)

• match : 목적지 MAC 주소 (2계층 주소)

• action : 포워딩(forwarding) 또는 브로드캐스팅(flooding, broadcasting) 한다.

* flood는 모든 네트워크 장비에게 알리는 것이다.

- 방화벽(Firewall)

• match : IP주소와 TCP/UDP 포트 번호
• action : 접근 허용 및 거부

- 네트워크 주소 변환(NAT)

• match : IP주소와 포트 번호

• action : 주소와 포트 번호를 재구성한다.

▶ Flow Table Entry

- Action은 어디 포트로 포워딩을 할지 등을 결정한다.

- Data Link Layer(2계층) : VLAN ID, MAC src, MAC dst, Eth type

- Network Layer(3계층) : IP src, IP dst, IP port

- Transport Layer(4계층) : TCP src port, UDP dst port

▶ IPv6

- 32비트 주소 체계인 IPv4의 고갈문제를 해결하고자 128비트 주소 체계의 IPv6가 나오게 되었다.

- IPv4의 고정 헤더 크기가 20bytes인 반면, IPv6의 고정 헤더크기는 40bytes이다. 헤더 크기는 커졌으나 기능을 간략화하였다.

- 단편화가 허용되지 않는다.

- version : IP 버전을 저장하는 필드이다. IPv6는 6이므로 “0110”이 저장된다.

- priority : 데이터그램이 전달되는 동안 우선순위를 식별한다.

- Flow label : 동일한 어플리케이션에서 만들어진 일련의 번호로, 빠른 처리를 위한 별도의 데이터그램 식별자이다.

- payload length : data의 길이를 저장하는 필드이다.

- Next header : IPv4의 프로토콜 타입을 저장하는 필드와 유사한데, 고정헤더 다음의 헤더가 무엇인지 알려준다.

- Hop limit : TTL(Time To Live)를 의미한다. 최대 값은 255이며, 최종 목적지에 달했을 경우 0의 값을 가진다. 하나의 Hop을 지날 때마다 1씩 감소한다. 최종 목적지가 아닌 곳에서 0의 값을 가질 경우 오류로 보고, 오류발생지에서 출발지로 오류메시지를 보낸다.

- source IP address : IPv6 주소 체계의 128비트의 출발지 IP주소를 저장한다.

- destination IP address : IPv6 주소 체계의 128비트의 목적지 IP주소를 저장한다.

- Data : 위에 까지가 헤더 영역이며, 이 부분은 IP 데이터그램의 데이터 부분을 저장하는 필드이다.

▶ IPv4 VS IPv6

- IPv4 헤더에 있던 체크섬 필드가 제거되었다. error을 검출하지 않는 이유는 매번 라우터마다 체크섬 계산을 비효율적이라 판단했기 때문이다. 따라서 각 hop에서 프로세싱 시간이 전체적으로 줄어든다.

- 헤더 내부에서 Option 필드가 사라지고 Extension Header가 추가되었다. 즉, 헤더 외부에 있으며 Next header 필드에 의해 나타내어진다.

- 단편화가 되지 않는 것은 오버헤드가 커지는 것을 방지하기 위함이다.

- ICMP의 새로운 버전인 ICMPv6가 등장하는데, 기존의 ICMP보다 ARP, IGMP 등 기능을 확장하였다. IGMP는 멀티캐스트 그룹을 관리하는 기능으로 보면 된다.

▶ Tunneling

- 모든 라우터가 동시에 업그레이드되어질 수 없어서 실제로 IPv6가 보편화되기에는 시간이 좀 걸린다고 한다.

- 그래서 터널링(tunneling) 기법을 통해 IPv4와 IPv6를 혼용하여 사용한다.

- Tunneling : IPv4를 사용하는 라우터들 사이에서 IPv6 데이터그램이 IPv4 데이터그램 안에 payload로써 이동되어지도록 IPv6를 IPv4로 캡슐화하는 기법이다.

- IPv4와 IPv6 모두 허용하는 라우터마다 IPv6를 IPv4로 캡슐화하고, 도착지에서 받은 데이터는 헤드가 벗겨지면서 IPv6로 받는다.

- 듀얼 스택 라우터(Dual-stack router)는 IPv6와 IPv4를 혼용하여 사용하는 라우터로, IPv4 터널을 다른 듀얼 스택 라우터와 연결하여 데이터를 전송한다. 이때 받는 측의 라우터는 헤더 버전 필드를 보고 IPv6가 올 경우 해당 데이터그램을 버린다. IPv6를 캡슐화한 IPv4만 받기 때문이다. 듀얼 스택 라우터는 Tunnel End Point(TEP)로 불린다.

- 듀얼 스택 라우터 전까지는 IPv6가 전송되다가 듀얼 스택라우터에 도착하면 IPv4로 캡슐화되어 다음 듀얼 스택라우터로 전송된다. 이 때 IPv4 데이터그램 헤더의 프로토콜 타입 필드에는 IPv6가 들어있다는 정보가 저장되어있다.

▶ IPv6 사용 여부

- 구글은 클라이언트의 8%가 IPv6를 사용하여 서비스에 접근한다.

- NIST는 미국의 국가 도메인인 US의 3분의 1을 IPv6가 가능하도록 한다.

- 보편화되기까지 20년 정도가 예상된다고 한다. 현재는 IPv4 주소 체계가 부족한 자원임이 틀림없으나 NAT로 버티고 있다.