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) 알고리즘 : 노드는 적절하지 못한 “경로 비용”을 알릴 수 있는데, 그럴 때 각 노드의 테이블은 이웃 노드에게 이용되어지며 에러가 네트워크 전역에 전파된다.

▶ Network Layer (네트워크 계층, 3계층)

- 송신 호스트에서 수신 호스트로 세그먼트를 전송한다.

- 송신 호스트에서 세그먼트를 데이터그램(datagram)으로 캡슐화한다.

- 수신 호스트에서 세그먼트를 전송 계층(4계층)으로 전송한다.

- 네트워크 계층이 모든 호스트와 라우터에서의 프로토콜을 지정한다.

- 라우터는 해당 라우터를 통과하는 모든 IP 데이터그램에 있는 헤더 필드를 검사한다.

▶ Network Layer Functions and Plane

- 라우팅 (Routing) : 출발지에서 목적지까지의 모든 경로를 결정한다. 라우터에서 라우팅 알고리즘으로 포워딩 테이블을 만든다. 포워딩 테이블에는 목적지 IP 주소와 해당 포트번호가 저장되어 있다.

- 포워딩 (Forwarding) : 라우터 내부에 입력 버퍼와 출력버퍼가 있다. 입력버퍼로 들어온 패킷의 헤더에 있는 IP주소와 포워딩 테이블의 IP주소를 비교하여 적절한 포트번호를 가진 출력 버퍼로 패킷들을 옮긴다.

- 라우팅이 출발지에서 목적지까지 여행을 계획하는 과정이라면, 포워딩은 여행 중간의 하나의 지점을 지나가는 과정이다.

- Control plane

• 넓은 네트워크의 논리적인 부분을 담당하는 뇌의 역할을 한다.

• 데이터그램이 종단 사이에 라우터들에 의해 어떻게 라우팅되는지 결정한다.

• 하드웨어 측면에서 라우터에 의해 구현되는 전통적인 라우팅 알고리즘 방식
• 소프트웨어 측면에서 서버에 의해 구현되는 SDN(Software-Defined Networking) 방식

• Per-Router Control plane : 각 라우터마다 있는 라우팅 알고리즘이 Control plane의 상호작용을 한다.

• Logically Centralized Control plane : 별도로 중앙에 배치된 컨트롤러가 local control agents(CAS)로 각 라우터와 상호작용한다. 중앙에서 control plane이 이루어짐.

- Data plane

• 각 라우터의 포워딩 함수들을 동작한다. 팔, 다리가 동작하는 것과 유사하다.

• 라우터 입력 버퍼에 도착한 데이터그램이 어떻게 출력 버퍼로 포워딩되는지 결정한다.

▶ Network Service Model

- 송신자에서 수신자에게 데이터그램들을 전송하는 채널에 대한 서비스 모델은 두 가지가 있다.

- 각각의 데이터그램에 대한 서비스 : 지연 시간이 40ms 보다 적은 상태로 전달된다.

- 일련의 데이터그램들에 대한 서비스 : 순서가 중요한 데이터그램을 위한 서비스로, 전송을 위해 최소한의 대역폭이 보장된다. 또한 각 패킷간의 간격에서 변화(ex : Jitter)가 제한적이다.

ex) 영상코덱(MPEG)

▶ 라우터 입력 포트의 기능 (3계층)

- 패킷의 헤더 필드 값(목적지 IP주소)을 보고, 포워딩 테이블에 있는 출력 포트 번호를 찾는다.

- 포워딩 테이블에 있는 IP주소와 패킷의 목적지IP주소를 비교하는데 시간이 오래 걸린다.

- 큐잉(Queuing) : 데이터그램이 포워딩하는 속도보다 더 빨리 입력 포트에 도착하면, 큐(입력 버퍼)에 저장된다.

- 목적지 기반의 포워딩 : 목적지 IP 주소만을 이용하여 포워딩한다. 전통적인 방식이다.

- 일반화된 포워딩 : 헤더 필드 값의 전체를 이용하여 포워딩한다.

▶ 목적지 기반의 포워딩

[ 원래는 IP 주소를 범위로 정해 포트 번호를 구분한다. ]

- IP 주소가 32비트이다보니 전체 값을 저장하면 테이블이 너무 커진다. 따라서 IP 주소에서 앞부분에 정해진 비트까지만 보여주고 범위(range)를 정하여 포트번호를 구분한다. 즉, 주소의 앞쪽만 매칭시켜서 해당 포트번호로 보낸다.

- Longest prefix matching : 패킷의 목적지 IP주소가 포워딩 테이블에서 둘 이상의 IP주소 범위에 포함될 경우, 그 중 비트가 가장 많이 공개된(가장 긴 prefix) IP 주소 범위의 포트번호로 포워딩한다.

[ 밑에 있는 예제의 정답은 위에서부터 0과 1이다. ]

- TCAMs : Ternary Content Addressable Memories 의 약자로, 실제 라우터가 포워딩 테이블에서 IP 주소를 탐색하는데 시간이 많이 걸리므로 라우팅의 속도를 빠르게 하기 위해 IP 주소 검색을 위한 포워딩 테이블이 저장되는 메모리이다.

▶ Switching fabrics

- 스위치 내부에서 각 입출력 포트를 가상의 회선으로 그물 또는 직물처럼 연결하여 구성되는 모양을 섬유(fabric)로 비유한 것이다. 즉, 스위치 내부가 직물 또는 망처럼 보이는 모양

- 입력 버퍼로부터 적절한 출력 버퍼로 패킷을 전송한다.

- Switching rate : 입력 포트에서 출력 포트로 패킷을 전송할 수 있는 속도로, 종종 다수의 입출력 라인 속도에서 측정되어진다. n개의 입력이 있을 때, 스위칭 속도는 입력 라인 속도의 N배가 요구된다.

[ 스위칭 구조 분류  ]

- Switching via Memory

• CPU의 직접적인 제어 아래에 스위칭하는 전통적인 컴퓨팅 방식으로, 첫 세대 라우터들의 스위칭 구조이다.

• 패킷이 시스템 메모리로 복사된다.

• 속도가 메모리 대역폭에 의해 제한된다.

• 메모리에 접근하는 시간도 많이 걸린다.

- Switching via a Bus

• 버스 구조는 2 이상의 신호선들을 모아놓은 것으로, 디지털 시스템에서 디지털 요소들을 상호 연결하는데 필요한 데이터 신호 통로들의 구조화된 그룹이다.

• 입력 포트 메모리로부터 출력 포트 메모리까지 하나의 공유된 버스를 통해 데이터그램을 스위칭한다.

• Bus contention : 스위칭 하는 속도는 버스의 대역폭에 의해 제한된다.

• ex)　Cisco 5600 제품이 32Gbps의 속도를 가진 버스 구조로 접근성에 있어서 충분한 속도를 가진다.

- Switching via Crossbar

• 제한적인 버스 대역폭을 해결한다.

• 다수의 프로세서들을 연결하기위해 개발된 interconnection nets, banyan networks, crossbar 망이다.

• 진보된 구성으로는, 데이터그램을 고정된 길이의 셀들로 분할하여 단편화한다.

• ex) Cisco 12000 제품이 interconnection network를 통해 60Gbps의 속도로 스위칭한다.

▶ 입력 포트 큐잉(Queuing)

- 큐잉은 입력 큐(버퍼)에서 패킷이 저장되는 것을 의미한다.

- 입력 큐(버퍼)가 꽉 차면 오버플로우(Overflow)가 발생했다고 한다.

- 큐잉 지연(Queuing delay) : 큐에서 패킷들이 대기하는 시간이다.

- 오버플로우가 발생하면 큐잉 지연(Queuing delay)이 일어나고 전송 속도가 저하된다. 또한 큐에 들어오지 못한 패킷들은 손실된다.

- HOL blocking : Head-of-the-Line blocking 의 약자로, 큐에서 저장된 패킷들 중 앞에 있는 패킷이 속도가 느려 뒤에 있는 패킷이 못가는 상황을 말한다. 즉, 둘 이상의 다른 입력 버퍼에서 같은 출력 버퍼로 이동하는 패킷들이 있을 때, 하나가 이동하면 다른 입력 버퍼의 맨 앞의 패킷은 이동할 수 없다. 그러면 대기하는 패킷의 뒤에 있는 패킷들도 덩달아 대기해야하는 상황을 말한다.

▶ 라우터 출력 포트의 기능 (3계층)

- 버퍼링(Buffering)

• 더 빠른 속도의 구조(fabric)로 인해 발생한다. 혼잡 제어나 버퍼공간의 부족으로 데이터그램(패킷들)이 손실될 수 있다.

• 스위치를 통해 도착하는 속도가 출력 라인 속도보다 크면, 버퍼링이 발생한다.

• 출력 버퍼에서 오버플로우가 발생하게 되면 큐잉 지연 및 패킷의 손실이 발생한다.

- 스케줄링(Scheduling) : 최고의 성능을 내기 위해 전송할 패킷의 우선순위를 조정하는 기능이다. 기본적으로 FIFO(First-In-First-Out)방식이다.

▶ 출력 포트 스케줄링(Scheduling)

- 스케줄링이란 링크로 보낼 다음 패킷을 결정하는 것이다.

- FIFO 스케줄링 : 기본적인 방식으로 처음 큐에 도착하는 패킷이 먼저 전송된다. 즉 순서에 맞게 전송한다.

- 오버플로우 발생 시 패킷을 버리는 방법

• tail drop : 꼬리 자르듯이 도착하는 패킷들을 버린다.

• priority : 우선순위를 기반으로 낮은 순위의 패킷들을 버린다.

• random : 무작위로 패킷을 뽑아 버린다.

- Priority Scheduling : 가장 높은 우선순위를 가진 큐에 담긴 패킷들을 먼저 링크로 보낸다. 즉 순위가 낮은 큐는 순위가 높은 큐가 비어 있어야 패킷들을 전송할 수 있다.

- Round Robin(RR) Scheduling : 다수의 큐들이 돌아가면서(Cyclically) 각각의 패킷들을 전송한다.

- Weighted Fair Queuing (WFQ) : 라운드 로빈(RR) 스케줄링과 유사하나, 각 큐마다 대기 시간이 있다는 점에서 차이가 있다. 즉, 각 큐는 돌아가면서 패킷을 전송하지만 전송되는 시간간격이 정해져 있다.