Chapter 5: Network Layer Control Plane
1. Two approaches to structing network control plane.
- Traditional routing algorithms (per-router control)
- Routing algorithm
- Routing protocol - SDN controllers (logically centralized control)
2. Network management, configuration
Traditional Routing Algorithms
- Data plane: Forwarding
- Control plane: Routing
Per-Router Control Plane (traditional routing)
: Traditional routing에서는 하나의 router에 control plane과 data plane이 공존한다.
--> 각각의 router마다 control plane에 routing algorithm이 존재하고, 따라서 하나의 router마다 data plane의 forwarding table이 만들어진다.
Routing Algorithms
- Routing protocol: path selection + message format & action.
- Routing algorithm: path selection
Routing Protocol
▶ 목표: Sending host로부터 receiving host까지의 "좋은" 경로를 정한다. --> forwarding table
- "좋은" 경로: minmum cost path, shortest path
- Bandwidth (대역폭)↑ --> Good!
- Congestion ↑ --> Bad!
Routing Algorithm Classification
▶ Global vs. Decentralized
- Global: 모든 router들이 모든 네트워크 정보를 가지고 있다. (link state algorithms)
- Decentralized: router들은 인접 router의 정보만 가지고 있다. --> 이웃들과 소통하며 네트워크 전체 목적지 경로가 설정된다.
▶ Static vs. Dynamic
- Static: 경로 계산 cost가 변하지 않는다. --> route 계산을 자주 할 필요가 없다.
- Dynamic: 상황에 따라 경로 계산 cost가 바뀐다. --> route 계산을 자주 해야 한다. (임계치를 넘으면, route 계산을 한다.)
Routing Algorithm Classification
- Link state routing algorithm: Dijkstra's algorithm (OSPF)
- Distance vector algorithm: Bellma's Ford algorithm
- Hierarchical routing
Dijkstra's Link-State Routing Algorithm
- Global: 모든 router가 전체 네트워크 정보를 가진다.
<-- link state broadcast: 각 router는 모든 router의 broadcast를 듣는다. - Dynamic: 각 router 자신으로부터 최단 경로를 매번 계산해서 업데이트한다. --> forwarding table
--> k번째 탐색 이후에는, 목적지로부터 k번째로 가까운 경로가 선택된다.
- Cx,y: 노드 X와 노드 Y 사이의 cost
- D(v): 현재 단계에서 least-cost path
- p(v): 목적지 노드로 direct link로 연결된 노드
- N': 최소 비용 경로에 포함되는 router (iteration이 진행되면서, 점차 늘어난다.)
Dijsktra's Algorithm
▶ 초기화:
- 만약 source 노드와 인접하면, D(v)에 cost를 추가한다.
- 만약 source 노드와 인접하지 않으면, cost = ∞
▶ Loop:
- 현재 router와의 거리가 최소인 router를 추가한다.
- 모든 router가 N'에 들어올 때까지 반복한다.
Dijsktra's Algorithm: Example 1
: source node로부터 시작하여, 현재 N'에 속한 노드와 인접하면서 목적지로의 cost가 가장 작은 노드를 N'에 추가한다.
- 목적지로의 cost는 새로운 노드가 N'에 추가될 때마다 업데이트된다.
Dijsktra's Algorithm: Example 2
Dijsktra's Algorithm - discussion
▶ 알고리즘 복잡도:
- Source 제외 n개의 노드가 있다면, n번의 iteration이 필요하다. --> 복잡도: O(n^2)
- 힙(heap)으로 구현하면, O(nlogn)의 복잡도
▶ message 복잡도
: 각각의 router는 자신의 cost를 각각의 link state로 broadcast해야 한다.
- n개의 노드, E개의 edge가 있다면, O(n*E)
- 복잡도: O(n^2); 절약됨!
Problem of Dijkstra's Algorithm
: 매번 cost가 바뀜에 따라(dynamic), packet이 서로 다른 경로에 의해 전송된다. (out of order delivery)
출처: 이화여자대학교 이미정교수님 컴퓨터네트워크
'Computer Network > 컴퓨터네트워크' 카테고리의 다른 글
| [컴퓨터네트워크] 1124 (1) | 2023.11.27 |
|---|---|
| [컴퓨터네트워크] 1122 (2) | 2023.11.26 |
| [컴퓨터네트워크] 1115 (0) | 2023.11.15 |
| [컴퓨터네트워크] 1110 (0) | 2023.11.11 |
| [컴퓨터네트워크] 1108 (0) | 2023.11.10 |
