📡 데이터통신네트워크 11 - Per-router algorithm : Link State(Dijkstra) & Distance Vector(Bellman-Ford)

라우터의 기능

forwarding : 라우터의 input link로 들어온 패킷들을 적절한 output link로 내보내는 것 - data plane에서 이루어짐

routing  : 어떤 패킷이 출발지로부터 도착지까지 이동하는 경로를 결정하는 것 - control plane에서 이루어짐

---

 

Routing protocols

: 네트워크의 라우터를 통해 전송자로부터 수신자까지 이동하는 '좋은' 경로를 결정하는 프로토콜

 

좋은 경로 : 비용이 최소거나, 가장 빠르거나, 혼잡이 덜하거나 등등...

 

 

라우팅 알고리즘 그래프 (topology) - 라우터를 노드로, 그것들을 연결하는 link들을 간선으로 

 

 

< global  /  decentralized information >

global : 모든 라우터가 전체 네트워크의 topology 와 link cost에 대한 정보를 모두 가지고 있는 형태

decentralized : 각각의 라우터가 자신과 이웃한 라우터까지 link cost 정보만을 가지고 있고,
                            라우터들간의 정보교환을 통해 점차 link cost 정보를 확장, 갱신해나가는 형태

 

---

 

Dijkstra's link-state routing algorithm

(다익스트라)

: centralized - 모든 라우터들이 network topology 와 link cost들을 모두 알고 있다

: 다익스트라 알고리즘 - 그래프의 최단거리를 찾는 알고리즘

1. 출발 노드를 정하고, 다른 모든 노드들까지의 거리 정보를 저장한다. (처음에는 직접 연결된 노드들만 거리 정보가 들어있고 나머지는 무한대이다). 그리고 최단 거리를 발견한 노드들의 집합을 만든다.

2. 모든 노드가 집합에 속할 때까지 다음을 반복한다.

 

아 야 이거 누적되는 값이네 숫자 변한게 6 w로 바뀐거는 시작이 u 니까 u-w(3) + w-v(3) = 6 인거잖아

 

다익스트라 알고리즘의 복잡도 

n개의 노드를 n번 확인하며 반복하므로 시간복잡도는 O(n^2)

-> 최적화시 O(nlogn)

 

 

Oscillations possible

Dijkstra's algorithm에서 특정 링크에 동일한 트래픽이 걸린다고 하면 트래픽을 고려한 방식은 결과적으로 경로에 반복적 탐색을 불러올 수 있다.

---

 

Distance vector algorithm (Bellman-Ford 벨만 포드)

: 각 노드는 자신에게 연결된 이웃의 링크의 비용(cost)만 알고 있기 때문에 이웃 노드들끼리 반복적으로 정보를 교환해 최적의 경로를 갱신함

 

각 노드가 인접한 노드들의 routing table을 보고 자신이 가진 routing table을 갱신하는 과정을 거침

 

다익스트라 알고리즘이 이웃들 간의 '간선 정보'만 참조한다면

벨만 포드 알고리즘은 routing table 전체를 참조한다고 할 수 있음

 

만일 내가 갖고 있는 노드간의 경로보다 나의 이웃으로 부터 새롭게 받은 경로가 더 좋은 경로라면 이를 수정함.

그리고 수정사항이 생겼으면 나의 이웃들이 내가 알고 있는 경로를 참조하고 있을 수 있으므로, 

나의 이웃들에게 또다시 수정본 routing table 정보를 보내줌.

만일 수정사항이 없으면 보내지 않음.

 

 

 

Distance Vector 알고리즘의 특징

- 반복적이고 비동기적(iterative, asychronous)

   : 각각의 로컬 반복은 로컬 링크의 cost가 바뀌거나 이웃의 DV(distance vector) 업데이트 메시지에 영향 받는다

- 분포적이고 알아서 멈춤 (distributed, self-stopping)

   : 오직 DV가 바뀐 경우에만 노드가 이웃에게 알린다

 

 

 

 

State Information Diffusion

: 정보가 점점 퍼져나가서 누적이 됨

 

 

Count - to - Infinity 문제 

: distance vector 알고리즘에서 link의 cost가 변경되었을 때 나타날 수 있는 문제임.

계속 무한대로 1 더해지는 작업이 반복되게 됨

---

 

LS vs DV algorithm

---

 

Making routing Scalable

어떤 시스템이 'scalable하다' 는 것은 확장성(Scalability)가 좋다는 것을 의미한다.

즉, 시스템의 규모를 확장하는 것이 용이한지에 대한..

 

만약 우리가 사용하는 인터넷 네트워크 내의 라우터들이 모두 동등하고, 서로 얼기설기 얽혀 있다면 어떨까? 전세계적으로 몇십 억 개의 destination들이 존재할 것이고 각각의 라우터들이 가지고 있는 routing table에 이 destination들에 대한 forwarding 정보를 기록하고 있는 것은 불가능에 가깝다.

예를 들어, 대한민국의 모든 가정에 대한 정보를 대한민국 정부가 모두 관리할 수는 없다. 그래서 시나 도를 나누어 시청, 도청을 설립한다. 시청/도청은 또다시 구청, 군청 등을 설립하여 계층화하고, 각 계층마다 관리 규모를 작게 유지한다.

라우터도 autonomous systems (자율 시스템)(이하 AS) 이라는 영역으로 통합할 수 있다.

 

 

 

[ Intra-AS, Inter-AS ]

전체 네트워크를 여러 개의 AS로 나누었으면 이들 간에, 또 각각의 AS 내부에서 통신이 이루어져야 한다. 

 

Intra-AS (intra-domain)

: AS 내부에서 이루어지는 라우팅

- AS에 속하는 모든 라우터는 같은 intra-AS 프로토콜을 사용해야 함

- gateway router : 각 AS의 edge에 있는, 즉 다른 AS와 연결된 라우터

 

Inter-AS (inter-domain)

: AS들 간의 라우팅

- gateway는 inter-AS 라우팅과 더불어, 다른 AS의 gateway 라우터와 inter-AS 라우팅을 수행함

 

 

forwarding table 을 만들 때에는 intra-AS, inter-AS 알고리즘을 모두 사용하여 만든다

 

---

 

가장 흔히 알려진 Intra-AS 라우팅 프로토콜 들

- RIP

- EIGRP

- OSFP

 

 

OSFP

- "open"  : publicly available

- 각각의 라우터는 AS 내부의 모든 다른 라우터들에게 Link state를 flood함

- 각각의 라우터는 모든 link state 정보를 가지고 있음 (full topology)

- 다익스트라(Dijkstra) 알고리즘을 통해 다른 모든 라우터들까지의 최적 경로를 탐색함

---

BGP (Border Gateway Protocol)

- inter-AS 라우팅에는 BGP (Border Gateway Protocol) 이 사용된다.

- policy - based !! (BGP 는 성능보다 정책기반으로 라우팅 된다!!!)

 

eBGP (external)  : 이웃 AS들로부터 reachability information 을 받아온다.

                                 AS의 위치, 갈 수 있는 destination의 종류와 경로 정보 등이 포함된다.

 

iBGP (internal) : 받아온 reachability information을 AS 내부의 모든 라우터들에게 전파한다. (propagate)

 

 

eBGP, iBGP 연결

파란 영역은 각각의 AS이며 파란 점선으로 표시된 연결은 '논리적인' AS 내부의 연결이며 곧 iBGP 연결을 뜻한다. 빨간 점선은 AS 간의 연결, 즉 eBGP 연결을 의미한다.

'논리적으로 연결되었다'는 것은 물리적으로 두 라우터 간의 연결이 존재한다는 뜻은 아니다. 다른 라우터를 거쳐서라도 서로 통신이 가능하면 연결된 것으로 본다.

---

 

Intra vs Inter-AS routing

 

 

 

⬇️ 참고

https://velog.io/@dltmdrl1244/네트워크-5-1.-Routing-Protocols

[네트워크] 5-1. Routing Protocols