[네트워크] network layer - control plane

이번에는 network layer의 control plane을 살펴보자. 저번에서 배웠듯 network layer은 SDN이 도입됨에 따라서 두가지 계층으로 나뉘었다.

• Data plane
• forwarding : router의 input port 에서 받은 packet의 router output  port를 결정짓는 것
• Longest Prefix Match
• Control plane
• routing : source 부터 destination까지 packet의 경로를 결정
• link state (dijkstra algorithm) , distance vector로 나뉜다. 

즉 정리하면, packet은 SDN에 의해 remote controller에서 전체 routing을 결정하고, 결정된 routing에 맞는 forwarding table이 각 router에게 뿌려짐으로써 forwarding이 결정되는 것이다. 

Routing protocol

• link state
• global 
• 각 노드는 전체 노드의 cost정보를 갖고있다.(여기서 node=host)
• dijkstra algorithm
• 한 노드로부터 전체노드로 가는 shortest path를 구할 수 있다. 
• 뻔한 내용이지만 간략히 설명하자면, 
1. 출발 노드부터 시작해서, 이웃한 노드중 가장 shortest path한 노드를 구한다.
2. 그 노드를 노드집합(set)에 추가하고, 해당 set으로부터부터 이웃한 노드중 가장 shortest path한 노드를 구한다. 
3. 이런식으로 쭉쭉 destination노드까지 확장해간다.
4. 이 과정은 그림1처럼 table에 계속 업데이트해나간다.

그림1 dikjstar algorithm in link state

• dijkstra algorithm의 복잡도는
• 계속 남은 전체노드까지의 cost를 탐색해야 하니 n+n-1+n-2+...+1 = n(n+1)/2 따라서 O(n^2)
• 더 효율적으로 고치면 O(nlogn)으로 구할 수 도 있다.
• dijkstra algorithm의 한계점
• oscilations possible(진동 가능성 문제)
• 이게 뭐냐면 link cost가 바뀌면 shortest path한 곳으로 패킷이 미친듯이 몰리는 현상이다. 
• 그림2를 보면 C -> A로 가는 shortest path가 D로 바뀌면, 패킷이 D에 몰리게 된다.
• 그렇다면 congestion이 발생하여 link cost가 올라가겠다. 따라서 C->A의 shortest path는 B로 바뀐다.
• 그러면 또 패킷이 B에 몰려 congestion이 발생한다. 같은 원리로 shortest path가 D로 바뀐다.
• 이일이 반복되며, 통과하는 packet들은 congestion의 저주에서 빠져나오지 못한다.

그림2 oscilations possible

• 우리가 사용하는 internet의 protocol이다.
• 더 정확히 말하면 intra-AS영역에서 사용하는 protocol인데, 이는 좀따가 다룬다.
• distance vector
• decentralized
• 각 노드는 이웃노드의 cost정보만을 갖고 있다.
• Bellman-Ford equation
• dynamic programming
• centrol control이 없이, network가 계속 변하므로, 그때그때 이웃노드의 변화를 보고 경로를 정하는 것이다. 
• dx(y) = min ( c(x,v) + dv(y) ) 
• dx(y) : x->y의 shortest cost
• v는 x와 이웃한 노드들
• iterative, asynchronous, distributed한 성질을 갖고 있다.
• flow는 그림3과 같다. 즉, 각 노드는 이웃노드의 cost정보가 변화하길 기다리고, 해당 메세지가 오면 cost정보를 다시 계산한다. 그리고 만일 해당 노드의 distance vector가 변화한다면 이웃노드에게 이를 broadcast하여 알려준다. 이를 iterative하게 하며, 이런 일은 asynchronous하게 발생한다. 또, 중앙 controller없이 distributed하게 이것이 처리된다.

그림3 distance vector flow

• 그림4를 통해 이해해보자. 각 노드는 전체 노드에 대한 shortest path table을 나름대로 갖고있다. 물론 이게 처음부터 옳은 것은 아니다. 이웃 노드의 정보밖에 모르기 때문이다. 하지만 그 table은 update하면서 이웃노드에게 뿌려지고, 이웃노드로부터 메세지가 오면 다시 update된다. 이런일이 반복되다보면, 마지막에 모든 node의 table이 같은 값으로 되는 convergence가 일어난다. 안정적으로 각 노드는 shortest path를 알게 되는 것이다. 

그림5 distance vector table

• distance vector의 한계점
• convergence가 일어나는데 운이 나쁘면 엄청난 시간이 소요될 수 있다. 이를 count-to-infinity problem이라 한다.

그림6 count-to-infinity problem

• 그림6을 더 설명해보자면, x-y link가 60으로 바뀌어도 Z는 바로 알아채리지 못한다. 하지만 y는 y->x로 가는 최소경로가 바뀌었음을 알아채고 y->z->x로 가는 경로를 선택한다. 그런데 이 시점에서 z->x로 가는  최단 경로는 z에 들어있는 정보인 z->y->x 값인 5이다. 따라서 y->x로 가는 최단경로가 y->z->y->x가 되고, 이는 실제와 다른 값이며, 6이다.  Z의 정보 업데이트가 안되기 때문에 이와 같이 44번의 iteration이 헛으로 돌게 된다. 

• adhoc network , sensor network 같은 곳에 사용된다. 
• adhoc은 각 peer이 노드역할을 하는데, 이들이 static한 router과 달리 dynamic하게 network에 추가되기도 하고 빠져나가기도 한다. 즉 graph에서 cost뿐 아니라, node자체가 바뀌는 dynamic 한 상황인 것이다.

• message complexity
• link state
• n개의 노드가 각 E개의 links의 정보를 가지고 있으므로 O(nE)
• distance vector
• 이웃간에만 message가 전달된다. 
• convergence를 위한 시간이 필요

• Intra AS : OSPF, Inter AS : BGP
• internet은 그림7과 같은 구조로 되어있다.
• 각 영역을 intra AS(domain)라고 부르며,
• 외부 intra AS로 연결되는 router을 gateway라고 한다.
• internet에서 Routing은 크게 intra-AS routing, inter-AS routing으로 나눌 수 있다. 

그림7 Intra AS

• OSPF
• Intra AS에서 쓰이는 protocol로
• dijkstra algorithm기반의 link state 방식을 사용하는 영역이다.
• dijkstra algorithm은 한 출발점으로부터 모든 노드까지의 shortest path를 알 수 있는데, AS 내 모든 node에서 gateway에 도달하기 위한 shortest path를 구할 수 있다는 걸 생각해보면 굿

• hierarchical OSPF(그림8)
•  AS자체에도 router이 너무 많으면, 이를 또다시 쪼갠다. 
• 여기서 각  area에서 link state 방식을 사용한다.
• boundary router가 gate way

그림8 hierarchical OSPF

• BGP
• eBGP
• 이웃하는 AS로부터 도달가능한 범위를 구한다.
• iBGP
• 도달가능한 범위정보를 intra AS내에서 모든 router에 전파한다.
• path attribute
• AS-PATH : 도달할 수 있는 AS 의 list
• NEXT-HOP : 이웃한 AS로 보내줄 수 있는 gate way router
• routing은 policy에 의해 좌우된다.
• 그림10을 보자 AS1의 1a 라우터는 지금 X에 도달하고 싶다고 가정하자.
• AS3의 3a는 eBGP를 통해 AS1에 AS3, X 정보를 보내고, AS2에 AS3, X정보를 보낸다.
• AS2는 iBGP를 통해 해당 attribute(AS-PATH,NEXT-HOP)을 모든 node에 전파하고, 2a가 이를 캐치한다.
• 2a는 eBGP를 통해 AS1에게 AS2,AS3,X정보를 보낸다.
• AS1의 1c는 X로 가기 위한 path를 두개 받는다. 여기서 policy에 의해 하나를 선택하고 이를 iBGP를 통해 전파한다.
• 1a router은 path를 전달받는다. 이를 토대로 forwarding table을 구성한다. 

그림9 BGP

그림10

• BGP Routing selection
• local preference value attribute : policy decision
• shortest AS-PATH
• 내부 AS는 신경쓰지않고, 외부 AS-PATH중 shortest한 path를 고려한다.
• closest NEXT-HOP router : hot potato routing
• 외부 AS는 신경쓰지 않고, 내부 AS에서의 shortest path만을 고려한다.

그림11 hot potato routing

그림12 advertisements policy

• 그림 12를 보자. 
• A는 Aw 경로를 B,C에 advertise
• B는 BAw경로를 C에게 advertise하지 않는다. (policy)
• B입장에서 C,A,w가 customer이 아니기 때문에 이득이 될게 없고, 해만 되기 때문이다. 
• C는 CBAw경로자체를 모르고, CAw경로를 택한다.
• 정리
• inter-AS에서는 policy, intra-AS에서는 link-state에 의해 performance가 좌우됨
• hierarchical routing은 table size를 줄이고 update traffic도 줄여준다.