link state

다익스트라 알고리즘

• Input
– A graph with edge weights (distance) : 그래프와 엣지 그리고 distance

• Output
– Shortest paths from one node to all others : 어떤 노드에서부터 다른 노드까지 shortest path를 계산

Dijkstra algorithm

Dijkstra algorithm

• 소스가 되는 노드를 집합에 넣고 시작한다.
• N-1번 루프를 돈다.
• 각 경로에서 최단경로와 거치어서 가는 경로중 보다 더 최단 경로인것을 선택한다.

다익스트라 알고리즘의 문제점은 oscillation 문제가 있다.

distance vector

벨만 포드 알고리즘.

벨만 포드 방정식은 위의 것을 풀려고 한다.

X에서 Y로 가는 cost를 소유.

이웃이 업데이트 되면 정보를 업데이트를 하고 주변도 업데이트 해주고

각각의 노드가 이웃들에게 자기의 distance vector을 보낸다. 그럼 x는 처음에 정보가 없다가 업데이트 하게 된다.

x에서 y로 가는 호스트는 x->y->y, x->z->y 두개를 모두 계산한다.
x->z->z, x->y->z 를 모두 계산한다.

똑같이 모두 업데이트 해준다.

그러다가 링크 코스트가 바뀌었다고 하자. 한쪽이 너무 커지면 무한 iteration 하게 될 수도 있다.

결국 라우팅에 loop가 생기는 문제점이 있는 것이다.

그래서 이를 해결하기 위해 바뀐 경로에 대해 무한대로 표시해버리는 것이다. 그러면 더 이상의 반복이 일어나지 않을 것이다.

---

두개를 비교해보면
LS : O(nE)
DV : 이웃과 테이블을 교환하기 때문에 상황에 따라 달라질 수 있다.

수렴속도
LS : O(n^2)
DV : 바뀔 수 있다.

robustness
LS :
DV :

---

5.3 intra-AS routing in the Internet: OSPF

네트워크 전체를 계층적으로 본다. 네트워크들은 서브넷으로 구성되어 있다. 그래서 서브넷 안에서 라우팅하거나 서브넷 끼리 라우팅된다.

intra-AS routing : ISP 안에서 라우팅

• 하나의 AS에서는 같은 라우팅 프로토콜을 돌리어야 한다.
• 다른 AS 간에는 다른 라우팅 프로토콜 돌리어도 된다.
• 게이트웨이 라우터는 다른 AS와 연결된 edge에 있는 라우터를 게이트웨이 라우터라고 부른다.

inter-AS routing : ISP 간의 라우팅

• AS 들 간의 라우팅
• 게이트웨이가 inter 도메인간의 라우팅 주도

각각의 라우터에 forwarding table이 만들어질텐데 이건 intra-AS와 inter-AS 두개를 이용해서 결정이 되어진다.

inter-AS가 하는일

AS1에서는 1b, 1c가 누구와 연결할지를 결정한다.

intra-AS routing == IGP
RIP, OSPF, IGRP

OSPF(Open, link-state, dijkstra algorithm)

link-state는 area 안에서만, 각 노드는 area topology를 가지고 있다. 다른 area에 있는 것들은 direction만 알고 있다.
area border routers : 자기 area를 요약해서 다른 지역에 보낸다.
backbone router : 백본에서만 돌아가는 OSPF를 돌린다.
boundary routers는 다른 AS와 연결되는 것을 의미

5.4 routing among the ISPs BGP

ISP 간의 라우팅 알고리즘

BGP = inter-domain routing protocol

• eBGP = 이웃한 AS로 부터 reachability information 받기
• iBGP = AS 안에서 internal routers로 부터 reachability information을 받는다.

좋은 경로는 reachability information와 policy에 의해서 결정된다.

BGP sesstion은 TCP 연결이 열리어 있어서 reachability information을 계속 주고 받는다.

AS-PATH
NEXT-HOP

AS3,X를 먼저 보내고 이 정보들이 iBGP에 의해 뿌려지고
AS1에게는 AS2,AS3,X정보가 통과된다.

network policy에 의해서 하나만 선택해서 보낼 수 있다.

forwarding table

BGP에서 경로 선택은
1. policy
2. AS-PATH
3. NEXT-HOP router
4. 추가적인 기준

Hot Potato Routing은 가장 빨리 나를 빠져나갈 수 있는 놈으로 선택해준다.

A가 B와 C한테 Aw를 홍보했다. 즉 w는 A를 통해 forwarding 된다.
BAw를 C에게 광고한다.
C는 w로 가는 트래픽을 CAw로 forwarding 한다.

정책을 만들어서 패킷 포워딩을 막을 수도 있다.

전체 그림을 보면 계층적으로 라우팅이 되어 있다.

5.5 The SDN control plane

네트워크의 router에 구현이 되어 있는 control plane이 업데이트하기 아주 까다로운 형태. 라우터가 스위칭 하드웨어하고 internet standard인(IP, RIP, IS-IS, OSPF, BGP) 프로토콜들.

인터넷에서 아무리 좋은 알고리즘이 나와도 라우터를 업데이트하기 어려웠다.

새로운 라우팅 프로토콜을 적응하려면 이게 쉽지 않았다.

SDN에서는 logically centralized control plane이 있어서 얘가 전체를 다 계산해서 각각의 라우터들에 업데이트를 해준다. 그래서 control plane이 centralized 된 형태이다.

왜 logically centralized control plane을 선택 하는가

• nertwork management가 쉽다(avoid router misconfigurations, greater flexibility of traffic flows)
• table-based forwarding allows programming routers
• open implementation of control plane

SDN이 되면 위와같은 topology에서

traditional routing은 힘들다가 결론임

왜냐하면 그때그때 spliting이 힘들기 때문이다.

destination forwarding에서는 불가능하지만 SDN에서는 가능하다.

핵심은 generalized forwarding, programmable 이다.

그리고 control과 data plane을 완전히 분리시킨다.

data plane switch는 하드웨어라고 보면 된다. fast, simple, commodity이고 generalized data-plane을 구현한 것이다.

flow talbe은 centralized controller에 의해서 관리 반영된다.

table-based switch control을 위한 API를 제공한다.

SDN controller는 network OS이다. 하드웨어와 소프트웨어를 연결하는 네트워크 OS이다. network state information을 가지고 API와 하드웨어를 연결해주어 interaction 해준다.

performance, scalability, fault-tolerance, robustness를 통해 분산화된 시스템을 구현한다.

서드 파티에 의해서 새로운 서비스가 나올 수 있다.

SDN 컨트롤러는 위와같이 생기었다.

openflow는 data plane과 control plane을 연결해준다.

openflow는 컨트롤러와 스위치 사이에 컨트롤 정보나 스위치의 상태등을 컨트롤러로 보낼때 사용하게 된다. TCP, encryption을 사용할 수 있고

3가지로 사용가능하다.

controller과 switch간의 연결과 통신을 어떻게 하는지.

1. 스위치가 link failure를 겪고 있을때

2. s1은 openflow를 이용해서 포트의 상태를 controller에 알려준다.

3. SDN 컨트롤러가 그 정보를 받고 link-state info 업데이트

4. 다익스트라 link-state 라우팅 알고리즘에게 정보를 알려준다.

5. 다익스트라 알고리즘은 link-state info를 통해 바뀐 그래프를 받게 되고 새로운 경로를 계산해서 보내게 된다.
   

6. link state routing app이 flow-table-computation으로 경로를 계산해서 openflow를 이용해서 내려보낸다.

7. 그리고 업데이트 된다.

SDN이 얼마나 잘 구현될지는 모르지만 계속 이쪽으로 개발이 진행되고 있다.

failure에 얼마나 강인하게 반응할 것인지? logically centralized 이지만 여러개의 서버들에 컨트롤러가 구현되어 있다. robustness라던지 seculity 문제등

SDN을 통해서 real-time, ultra-reliable, ultra-secure 등의 문제를 해결하려고 한다.

5.6 ICMP : Internet control message protocol

icmp는 호스트와 라우터간의 error reporting. 호스트에 도달할 수 없다 등.

3 probes를 보내서 RTT를 측정하는 등

5.7 Network Management and SNMP

network management는 autonomous system이라면 수천 ~ 수백 네트워크/하드웨어 컴포넌트로 구성되어 있다.

network management라는 것은 하드웨어/소프트웨어가 네트워크 리소스들을 관리하기 위해 설치, 통합, 관리하는 것을 이야기 한다.

network management를 하려면 상태 정보를 모아야 한다.

관리대상이 되는 agent가 되고 managing entity가 되고 제어 정보가 될 수 있다.

MIB(Management Information Base)에 정보가 모두 모아진다.

request를 보내면 response를 전달해주고 trap msg는 request 안해도 보내주는 메시지이다.

뭐 이런게 있구나

네트워크 레이어를 데이터 플레인(하드웨어)과 컨트롤 플레인(소프트웨어)으로 나누어 볼 수 있다.