Network Layer에는 두가지 plane이 존재한다
첫번째는 버퍼의 입력부에서 출력부로 내보내는 Forwarding을 담당하는 Data Plane,
두번째로는 출발지로부터 목적지까지의 경로를 결정하는 Routing을 담당하는 Control Plane이 있다.
Control Plane
Control plane에는 두가지 접근 법이 있는데
1. Pre-router Control(전통적)
각각의 라우터에 있는 control plane이 서로 상호작용하며 독립적인 라우팅 알고리즘을 통해 라우팅 진행
각각의 라우터가 경로를 결정(S/W에 의해 정의됨)
2. Logically Centralized Control
Remote Controller가 전체 forwarding table을 계산하고 각 router에 설치
router 내부의 control agent가 remote controller와 상호작용 하여 해당과정 진행
Routing Protocol
- Link State, distance vetor
라우팅 프로토콜의 목표는 출발 호스트로부터 도착 호스트까지 좋은 경로를 결정하는 것
좋은 경로란 최소의 비용으로 빠르고 혼잡하지 않게 가는 것.
link costs
각각의 edge가 갖는 cost가 바로 Link cost, 만약 연결이 없으면 INF(infinate)로 설정.
cost는 network operator에 의해 설정되는데
1일수도, 혹은 bandwidth의 역으로도, congestion 상태의 역으로도 설정될 수 있다.
Classification
-
global: 모든 라우터가 완벅히 네트워크 전체의 topology(구성), link cost를 알고 있는 경우로, link State 알고리즘을 사용한다.
-
decentralized: 물리적으로 연결된 이웃의 cost만 알고 있으며, 이웃의 정보를 받아서 조금씩 업데이트를 진행한다, distance vector 알고리즘을 사용
=> Router가 전체 정보를 알고 있는지, 자기 정보만 알고 있는지의 차이
- static: 라우터가 느리게 변환
- dynamic: 라우터가 더 빠르게 변환 -> 일정 시간을 두고 업데이트 되거나, link cost가 주기적으로 업데이트
Link State
다익스트라 알고리즘을 사용한다.
모든 노드가 link state broadcast에 의해 전체 네트워크 구성과 link cost를 알고 있다.
- 한 노드에서 최소 비용 경로를 계산하기 위해 다른 전체 노드에 대한 경로를 계산해 forwarding table에 기록
- k iteration 후에, 최소 k 만큼 떨어진 destination들까지의 거리를 계산한다.
간단히, 시작 노드부터 모든 노드들에 대한 비용을 구하고, 이후 N' 에 포함되지 않은 모든 노드들에 대해 최소비용을 탐색한다.
이후 해당 노드 주변 노드를 다시 탐색한다.
원래 경로와, 새로 추가된 경로를 거쳐서 가는 것의 cost를 비교하여 더 작은걸로 업데이트 한다.
- u에서 모든 노드로의 cost 업데이트
- 그중작은 D(W)(3,u)선택
- w 거처 각 노드로 갈 수 있는 cost 업데이트
- 또 남은 것중 가장 작은 D(X)(5,u)선택
반복
-
시간 복잡도 : O(n^2)
가장 작은 노드 찾는 과정을 heap 이나 우선순위 큐에 넣으면 O(nlogn)으로도 가능.
각 라우터는 link state정보를 다른 n개의 router에 broadcast하는데,
이 과정에서 효율적인 broadcast 알고리즘을 사용하면 O(n)만에 link crossing이 가능하다. -
만약 각 라우터의 메시지가 O(n)개의 링크를 교차하면, 전체가 모두의 메시지를 받는데에는 O(n^^2)
또한 link cost를 traffic volume에만 의존토록 설계하면 route oscilation 발생이 가능하다.
위 사진 처럼 불필요한 반복을 통해 route가 계속 변동
(solution은 synchronization, 하나 업데이트시 모두 같이 업데이트하는 것
Distance Vector
Bellman-Ford 알고리즘 사용
이웃 노드로 가는 비용 + 이웃에서 목적지로 가는 비용을 비교해서 최소값을 선택하는 것
사진처럼 u에서 z로 가는 비용을 계산시, 인접한 라우터들 중 어떤 것을 거쳐서 가는 것이 빠를 지만 결정하는 것.
Key Point
각 노드가 자신의 distance vector 계산 값을 이웃에게 보낸다.
각 노드가 이웃으로 부터 새 계산 값을 받으면 BF방적식을 사용하여 자신의 Distance Vector를 업데이트한다.
즉, 각 노드는 자신의 link State를 모니터링 하면서, 이웃들이 notify하는 것을 받는다. 주변의 notifiy가 오면 estimate를 다시 계산하고, DV가 바뀐 경우에만 이웃에게 알린다.
t가 1씩 더해질때 마다, 전파 영역이 증가됨.
- Conclusion(link cost Change)
만약 link cost 변경을 감지하게 되면, 라우팅 정보를 업데이트 하고, local DV를 다시 계산한다.
만약 DV가 변경시 이웃에게 알린다.
good news travels fast
link cost가 감소했다는 좋은 소식은 더 빠르게 전파.
bad news travels slow
link cost가 증가했다는 나쁜 소식은 더 느리게 전파
- Count-to-Infinity 문제 발생
변경 전, Z: X -> Y, Y: X -> X(x로 이동시, 직접 x로 이동)
그런데, Y->X로 가는 길의 cost가 60으로 변경되었을때, 즉 cost가 급증하여 길이 끊겼을때,
Y -> X는 끊겼지만, Z로 부터 X->Y는 여전히 비용 2로 갈 수 있다는 정보를 얻게 된다.
결국 D(Y,X) = C(Y,Z) + D(Z,X) = 1 + 2 = 3
또 이를 Z에게 알려주면 여전히 비용 3으로 갈 수 있다는 정보를...
이를 반복하여 60까지 다다를때, 그제서야 아 우리 link가 조졌구나를 깨닫게 된다.
=> 해결법
https://www.nowwatersblog.com/cs/%EC%BB%B4%ED%93%A8%ED%84%B0%EB%A7%9D/5.%20Network%20Layer
Comparison between Link State and Distance Vector
-
message complextity
LS: n개의 라우터, O(n^2)메시지가 전송
DV: 이웃간 정보 교환, 수렴시간(Convergence Time)이 변화 -
speed of convergence
LS: O(n^2) 알고리즘, O(n^2)메시지, 변동(oscillation)존재 가능
DV: convergence Time 변화, 라우팅 loop 에 빠질 수 있으며, Count-to-infinity 문제 발생 가능
Convergence Time : Network Topology(구성) 변화 발생시 이를 반영하여 네트워크가 재구성 될때 까지 소요되는 시간
- robutness(라우터 고장)
LS: 라우터, 부정확한 Link Cost 전파, 각 라우터는 각자의 테이블만 계산
DV: 부정확한 Path Cost 전파, black-holding(다른 라우터가 사용하는 라우팅 테이블을 받아 에러가 네트워크 전체에 전파)
Intra-ISP Routing: OSFP
Making routing scalable
scalability: 확장성, 망의 규모가 커졌을 때를 대비
-
이상적(idealized)
모든 라우터들이 LS or DV로 통일 -> Network "flat"
근데 실전에선 그렇지 않다 -
실제 동작 방식(administrative Autonomy)
인터넷 = Network of Network
각각의 네트워크 관리자는 자신 고유 영역(AS, Autonomous System)의 네트워크의 라우팅을 통제하기를 원함
AS를 Domain 이라고 부르기도 함.
Autonomous System
AS로 구역을 나누어 그 안에 라우터를 포함시킨다.
1. Intra-AS(Intra-domain)
동일한 AS내에서 동작하는 라우팅 방식(same AS)
한 AS 내 모든 라우터 -> 같은 intra-domain protocol로 동작
- Gateway router : AS의 가장자리(edge)에서 다른 AS의 라우터로 연결되는 link를 갖고 있는 라우터
2. Inter-AS(Inter Domain)
여러 AS간 라우팅 방법(routing among AS'es)
gateway들이 inter-domain routing 수행
Forwarding Table -> intra-As, inter-AS Routing 알고리즘에 의해 구성
- Interconnected AS
Intra-AS: AS 내에서 목적지로 가기위한 entry들을 결정
Intra-AS, Inter-AS: 외부 목적지로 가기 위한 entry들을 결정
AS간 사용하는 라우팅 프로토콜은 Path Vector 사용
만약 AS1이 다른 AS3 나 AS2로 보내야할 데이터 그램을 받는다면,
AS1은 내부에 있는 gateway 라우터 중 어떤 것으로 보내야 되는가? 라는 질문,
따라서, AS1 inter-domain routing은 반드시 두가지 동작을 하는데,
1. AS2, AS3, 각각을 거쳐서 도달 가능한 목적지를 학습
2. 이 reachability 정보는 AS1 내부에 모든 라우터로 전송
Intra-AS routing 종류
1. RIP(Routing Information Protocol)
- class DV: 30초마다 DV 값 교환 => Count to Infinity 문제 유발
2. EIGRP
DV로 동작, Cisco 에서 독자적으로 사용하는 기술
3. OSPF(Open Shortest Path First)
-Link state routing 으로 동작 -> 현재 가장 많이 사용되는 방식
- classic link-state 방식 => 전체 topology(구성방식)을 그리고 Routing Table을 만든다.
- 다익스트라 앍리즘을 사용하여 forwarding Table을 계산
각 라우터들은 전체 AS내 모단 라우터에게 IP를 사용하여 OSPF link-state 정보를 전달
모든 OSFP 메시지들은 악의적 방해를 막기 위해 인증되어있음
여러 link cost가 존재할 수 있음
Hierarchical OSPF
- two-level hierarchy : local area, backbone
link state 전달(advertisement)는 area와 backbone에서만 진행
각각의 노드는 세부 area topology를 갖고 있으며, 오직 다른 목적지로 도달하기 위한 방향밖에 알지 못함
-
local routers
LS 전달이 이루어지는 부분, 외부로향하는 데이터 그램 받으면 Area Border Routers로 전달 -
area border routers
목적지까지의 거리를 요약해서 backbone으로 전달 -
backbone router(backbone에 연결), boundary router
두 라우터를 거쳐서 다른 area에 있는 라우터로 전달하는 과정을 거침
