[Network] Network Layer:The Control Plane

network control plane 을 설계하는 방법에는 두 가지가 있다. 

 

Per-router control

전통적인 방법으로, 각각의 모든 router 의 routing algorithm 이 control plane 내의 다른 router 들과 forwarding tables 를 계산하기 위해 상호작용한다. OSPF 와 BGP 이  per-router 기반의 프로토콜이다.

 

Logically centeralized control 

logically centralized controller 가 각각의 모든 router 에 사용되는 forwarding tables 를 계산하고 분배한다. controller 는 각각의 router 에 있는 CA (control agent) 와 상호작용한다. 보통 CA 는 controller 와 소통하고 controller command 에 따라 행동하는 최소한의 기능만 가진다. 또한, CA 는 서로 상호작용하지도 forwarding table 을 계산하기 위해 작동하지도 않는다. SDN 이 logically centralized controller 의 개념을 채택했다. 

 

Routing Protocols

routing algorithm 은 network topology 정보를 입력 받아 routing table 을 출력하는 algorithm 이다. routing algorithm 의 목표는 network 의 routers 를 통해, sender 에서 receiver 까지 가지는 good paths (routes) 를 결정하는 것이다. 이때, good path 란 least cost, fastest, least congested 한 path 를 의미한다. routing algorithm 은 입력되는 topology 의 특정에 따라, 두 가지 종류로 분류할 수 있다.

• Centralized routing algorithm : 모든 router 들이 complete, global topology 를 가진다. 즉, 계산 전에 알고리즘은 모든 node 들과 모든 link costs 사이의 connectivity 를 가진다. 대표적으로 link-state (LS) algorithm 이 있다. 
• Decentralized routing algorithm : router 는 physically-connected neighbors 와 neighbors 의 link costs 만 알고 있다. neighbors 와 정보를 교환하고 계산의  iterative process 를 통해, node 는 점진적으로  leaset-cost path 를 계산한다. 대표적으로 distance vector (DV) algorithm 이 있다. 

routing algorithm 다음과 같이 분류할 수도 있다.

• Static routing algorithm : routing 관리자에 의해 routing table 이 유지/관리된다.  routes 가 시간에 따라 매우 느리게 변한다.
• Dynamic routing algorithm : routing protocol 의해 routing table 이 유지/관리된다. network traffic 이나 topoloy 의 변화에 따라 routes 가 보다 빠르게 변화한다. periodic update 나 link cost changes 의 응답으로 실행된다. 

 

Link State Routing Algorithm

network topology 와 모든 link costs 를 모든 node 가 알고있으며, 한 node 로 부터 모든 다른 node 까지의 least cost paths 를 계산한다. OSPF routing protocol 이 LS algorithm 을 사용한다.

LS routing algorithm 은 Dijkstra's algorithm 을 사용한다. 

위의 그림들은 LS algorithm 과 algorithm 에 사용되는 notation 이다. 간단히 요약하면, N 에 없는 w 중 D(w) 가 최소인 w 를 찾아 N 에 추가하고 갱신된 N 에 대하여 D(v) 를 갱신한다. 이러한 수행을 모든 node 가 N 에 포함될 때 까지 반복한다. 

LS algorithm 은 모든 node 들의 least cost paths 를 찾기 위해 최대 n(n+1)/2 번 반복이 필요하므로, worst-case complexity 는 O(n^2) 이다.

위 그림은 routerA 를 기준으로 모든 router 에 대한 least cost paths 를 구한 예제이다. 

 

Distance Vector Routing Algorithm

Bellman-Ford Algorithm 이라고도 불린다. DV algorithm 은 iterative 하고 asynchronous 하며 distributed 한 특징을 가진다.

• iterative : neighbors 사이에 교환할 정보가 없을 때까지 process 가 계속된다. 또한, 정지를 위한 signal 없이 멈추기 때문에 self-terminating 이다.
• asynchronous : node 들은 lockstep 에서 information 을 교환하거나 반복을 할 필요가 없다.
• distributed : 각각의 node 는 반드시 directly-attached neighbors 끼리 통신한다.

 BGP routing protocol 이 LS algorithm 을 사용한다.

DV algorithm 은 Distance Table 을 통해 routing table 을 계산한다. 재귀적인 방법으로 Distance Talbe 이 생성되면, Distance Table 은 한 destination 에 대해 가장 적은 cost 를 가지는 경유 node 를 선택하여 routing table 을 만든다. 

 

위의 그림들은 DV algorithm 과 DV algorithm 의 작동 예시이다. 각각의 router 는 초기 Distance Table 을 설정 후, 시간이 지남에 따라 neghbors router 과 통신하며 재귀적으로 Distance Table 을 완성하게 된다. router 는 완성된 Distance Table 을 사용하여 routing table 을 만들 수 있다.

 

LS algorithm 은 routing table 계산 전에 complete topology 가 필요하므로 DV algorithm 보다 전처리 시간이 길다. DV algorithm 은 routing table 을 계산하면서 information 을 교환하므로, routing table 이 convergence 될 때까지의 시간이 LS algorithm 보다 길다. 추가로, topology 가 수정될 때 convergence 가 빠른, 즉 변화에 빠른 algorithm 은 LS algorithm 이다. battle field 처럼 무선이고 자주 변화하는 환경이라면, 전처리에 시간이 덜 걸리는 DV algorithm 이 더 적합하다.

참고로, routing table 이 완성되어 더 이상 변화가 없는 상태를 table 이 convergence 되었다고 한다. 

 

OSPF & BGP

routing protocol 의 대표적인 예들인 OSPF 와 BGP 를 살펴보기전, Autonomous System 이 무엇인지 살펴보아야 한다. AS (Autonomous System) 는 단일 routing policy 에 따라 연결된 하나 이상의 Internet Protocol prefixes 의  group 이다. 

AS 내에서 실행되는 routing algorithm 을 intra-autonomous system routing protocol 이라고 하고, 다른 AS 사이에서 실행되는 routing algorithm 을 inter-authonomous system routing protocol 이라고 한다. 다른 AS 와 연결되는 router 는 gateway router 라고 한다. 

 

OSPF (Open Shortest Path First)

OSPF 는  intra-autonomous system routing protocol 로, AS 내부 routing 경로를 설정한다. ink-state algorithm 을 사용한다. 

 

BGP (Border Gateway Protocol)

BGP 는 inter-authonomous system routing protocol 로, 여러 개의 AS 를 연결하며 몇 천개의 ISP 를 internet 으로 연결한다. distance-vector algorithm 을 사용한다. 

 

 

ICMP (Internet Control Message Protocol)

ICMP 는 network-level information 을 communicate 하기 위해 hosts 와 routers 에 의해 사용된다. unreachable host, network, port, protocol 에 의한 error reporting 과 ping program 에 의한 echo request/reply 에 많이 사용된다. ICMP 는 IP 위에 올려져 있으며, TCP/UDP segment 처럼 ICMP messages 는 IP datagram 안에 담겨있다. ICMP message 는 type 와 code field 를 가지며, ICMP message 를 처음 생성한 IP datagram 의 header 와 처음 8 byte 를 가진다. 

 

Traceroute Program

Traceroute program 은 ICMP message 로 구현된다. source 는 destination 으로 일련의 UDP segemnts 를 보낸다. 첫 번째는 TTL = 1, 두 번째는 TTL = 2, ... n 번째는 TTL = n 으로 설정된다. n 번째 datagram 이 n 번째 router 로 도착하면, router 는 TTL = 0 이 되어 만료되고 datagram 을 무시한 후 source 로 ICMP message 를 보낸다. ICMP message 에는 router 의 IP address 와 이름이 담겨 있다. source 로 ICMP message 가 도착하면, source 는 RTT 와 n 번째 router 의 IP address 와 이름을 얻는다. 

 

 

 

 

참조
Computer Networking _ A Top Down Approach, 7th, converted