Overview
Two approaches to structuring network control plane
1) per-router control (traditional routing algorithms)
- Routing algorithm classification
- Link State routing algorithm: Dijkstra's algorithm
- Distance Vector algorithm: Bellman-Ford algorithm
- Hierarchical routing
- Routing protocols
- RIP, OSPF (IGP; interior gateway) / BGP (EGP; exterior gateway)
2) logically centralized control SDN controllers
- OpenFlow controllers
Traditional Routing Algorithm (Destination-based forwarding)
- Data plane: Forwarding
- FIB: move pkts from router's input to appropriate router's output based on destination IP address
- Control plane: Routing
- RIB: determine route taken by pkts from source to destination
- Per-router control plane
- Individual routing algorithm components in each and every router interact with each other in control plane to compute forwarding tables
라우터의 control plane은 라우터들끼리 주고받는 routing protocol msg를 포함한 패킷을 처리하고, 라우터의 data plane은 end host에서 출발한 유저의 msg를 포함한 패킷을 처리한다.
Routing Algorithms
Routing Protocol은 라우터들간에 주고받는 message의 format과 order를 정의하고 있으며, Path selection algorithm을 포함하고 있다.
👉 Routing Protocol = Path selection + message format & action
Routing Protocol goal
Routing Protocol
- Routing Protocol은 라우터들간에 주고받는 message의 format과 order를 정의하고 있으며, Path selection algorithm을 포함하고 있다.
- Routing Protocol = Path selection + message format & action
- Goal: determine good paths(routes) from sending hosts to receiving host, through network of routers
- path: sequence of routers
- good == least cost, fatest, least congested : typically means least cost path or shortest path
Graph Abstraction of the Network: Graph: G = (N, E)
- N = set of routers (nodes)
- E = set of links (edges)
- c(x1, x2) = cost of link (x1, x2)
- cost of path(x1, x2, ... xp) = c(x1, x2) + c(x2, c3) + ... + c(xp-1, xp)
- 전통적인 라우터의 forwarding table에는 특정 subnet으로 가는 1개의 best path만 사용되며, 해당 best path에 해당하는 output port 정보만 있다.
- 전통적인 라우터에서 사용되는 path selection algorithms 중 경로에 포함된 각 링크의 대역폭, 에러율, output buffer의 혼잡도 등의 성능을 비용으로 표현하여 최소 비용 path를 선택하는 알고리즘도 있는데, 이때 링크 혼잡도는 시간에 따라 변동하여 의도치 않은 비효율적인 패킷 전송이 일어날 수 있어 실제 인터넷에서는 사용되지 않는다.
Routing Algorithm Classification
Global vs. Decentralized
- Global: every router has complete topology(connectivity, link cost)
- ex. Link State(LS) algorithm (OSPF)
- Decentralized: router knows physically-connected neighbors, link costs to neghbors (estimates of costs to all other nodes in the network); interactive process of computation, exchange of info with neighbors
- ex. Distance Vector(DV) algorithm (RIP, BGP)
Static vs. Dynamic
- Static: routes change slowly over time
- Dynamic: routes change more quickly; responsive to NW changes
- RIP, BGP, OSPF 모두 네트워크 내부의 오류 발생 시, 상황을 실시간으로 감지하고 이를 path selection에 반영하여 새로운 경로를 계산할 수 있는 dynamic routing algorithm을 사용하는 라우팅 프로토콜이다.
Load-sensitive vs. Load-insensitive
- Load-sensitive: link cost reflects the current level of congestion
- 오류 방지를 위한 추가 기능 필요
- Load-insensitive: link cost doesn't explicitly reflect the current level of congestion;
- Today's Internet routing algorithms: RIP, OSFP, BGP
Routing Algorithm Classification
Link State(LS) Routing Algorithm
Link-State(LS) Routing Algorithm = Dijkstra's Algorithm
- Global, Dynamic routing
- net topology & link costs known to all nodes via link state broadcast (all nodes have same info)
- compute least cost paths from one node (source) to all other nodes: gives routing table for that source node
- interative: after k iterations, know least cost path to k destination's
- Notation
- c(x, y): link cost from node x to y;
- D(v): current value of cost of path rom source to destination v (계속 변하는 값)
- p(v): predecessor node along path from source to v
- N: set of nodes whose least cost path definitively known
- N개의 라우터들로 구성된 네트워크를 가진 ISP의 라우터가 Dijsktra를 사용해 경로를 계산한다면 해당 ISP의 모든 라우터들은 각각 자신의 local network topology 정보를 나머지 (N-1) 개의 라우터들에게 전송한다.
- LS routing algorithm은 각 라우터들이 속한 ISP의 전체 network topology를 모두 알고 path selection 계산을 시작하므로 라우터들은 각자의 local network topology 정보를 교환하기 위해 OSPF 같은 라우팅 프로토콜이 필요하다.
Dijkstra's Algorithm
- Complexity: O(n^2) -> using heap: O(nlogn)
Problem of Dijkstra's algorithm
- oscillations possible: 네트워크의 특정한 상황에서 경로가 반복적으로 변하는 현상
- 경로가 계속해서 변하면서 데이터가 원래 목적지로 도달하지 못하거나, 반복적인 경로 변경으로 인해 네트워크의 성능이 저하될 수 있음
- everyone goes with least loaded, making them most loaded for next time, so everyone switches 👉 Herding effect
- can happen with any routing protocol that uses dynamic load info
- load-sensitive cost를 이용할 때 발생
Distance Vector(DV) Algorithm
RIP, BGP는 DV를 사용하는 라우팅 프로토콜이며, Decentralized routing 정보를 사용하므로 각 라우터가 path selection을 게산할 때 전체 network topology는 모른다.
Bellman-Ford equation
- dx(y) = min_v{c(x, v) + dv(y)}
- dx(y) := cost of least-cost path from x to y
- min_v: min taken over all neighbors v of x
- c(x, v): cost to neighbor v (real value)
- dv(y): cost from neighbor v to destination y (estimated value)
- node achieving minimum is a next hop in shortest path, used in forwarding table
DV 알고리즘을 사용할 때 라우터가 정확하게 알고 있는 network topology는 자신과 직접 연결된 링크 뿐이다.
Distance Vector(DV) Algorithm
- from time-to-time, each node sends its own distance vector estimate to neighbors: slowly converge final routing table
- when x receives new DV estimate from neighbor, it updates its own DV using B-F equation
- under minor(small NW in ISP), natural conditions, the estimate Dx(y) converge to the actual elast cost dx(y)
- iterative, asynchronous algorithm
- each local iteration caused by: local link cost change, DV update msg from neighbor
- distributed
- each node notifies neighbors only when its DV changes (프로토콜 마다 다름)
- each node:
- wait for change in local link cost or msg from neighbor
- recompute estimates (updates local DV)
- if DV to any dest has changed, notify neighbors
- DV 알고리즘으로 경로를 계산하는 RIP 프로토콜을 사용하는 라우터는 해당 ISP 안의 이웃한 라우터들에게만 자신의 라우팅 테이블을 메시지로 전달한다.
- BGP는 EGP이며 상당한 양의 라우팅 정보를 교환하므로, 라우팅테이블에 변동이 있을 때 update된 정보만 이웃에게 알려준다.
DV: link cost changes
- node detects local cost change -> update routing info, recalculates DV -> if DV changes, notify neighbors
- good news travles fast: link cost가 좋아지면 반영이 빠름
- count to infinity: bad news travels slowly; cost가 나빠지는 경우 특정 라우터 사이에 routing loop 발생
A와 B 노드 사이의 연결이 끊어졌을 때, A는 B를 통해 다른 노드로 가는 최단 거리가 무한대로 설정됩니다. 이 정보는 A의 이웃 노드에게 전달되고, 그 노드들은 또 다른 무한대의 거리를 기록하게 됩니다. 이런 정보 전파가 반복되면서 각 노드는 점차적으로 무한대로 수렴하게 되는데, 이것이 count to infinity 문제
Count to Infinity
- Split horizon: don't send the path info whose next-hop is B back to B
- 상대 라우터에게 얻은 정보로 update한 라우팅 엔트리는 다시 그 라우터에게 주지 않는 것
- Split horizon with poisoned reverse: Node A advertises its route for C as unreachable(infinite) back to B
- 위의 상황에서 infinite 값을 전달하는 것
- These solutions don't work for routing loops involves 3 or more nodes
- RIP: 물리적으로 topology를 loop free하게(loop가 없도록) 구성
- BGP: 경로 router를 확인해서 loop가 생기면 drop
LS vs. DV
Link-State(LS) routing algorithm
- each router(node) talks with all other nodes via boradcast
- it provides them with only the costs of its directly connected links
Distance-Vector(DV) routing algorithm
- each node talks to only its directly connected neighbors
- it provides its neighbors with least-cost estimates from itself to all the nodes
| LS | DV |
| message complexity: with n nodes, E links, O(n*E) msg sent 👉 More, smaller messages |
message complexity: exchange btw neighbors only n-1 👉 Fewer, larger messages |
| speed of convergence: O(n^2) - may have oscillations - path selection: O(nlogn) |
speed of convergence: varies depending on topology - may be routing loops - network topology에 따라 모든 라우터들이 안정적인 라우팅 테이블 정보를 얻기까지 소요되는 시간(convergence time)이 다양할 수 있다. |
| robustness: if router malfunctions - node can advertise incorrect link cost - each node computes only its own table 👉 provide a degree of robustness |
robustness: if router malfunctions - DV node can advertise incorrect least-cost path cost - incorrect table is used by neighbors 👉 error propagates thru network |
- LS에서 각 라우터가 전송하는 정보는 local link 정보이므로 msg에 오류가 발생해도 다른 라우터들이 결과적으로 계산하는 e2e path의 일부분에 해당해 영향력이 작으나, DV는 각 라우터가 전송하는 msg가 e2e path 정보에 해당하므로 오류가 있는 msg를 받은 라우터들의 경로 계산에 미치는 영향력이 더 크다.
- RIP는 multicast로 msg를 전송하므로 L4 프로토콜로 UDP를 사용하고, BGP는 unicast로 msg를 전송하므로 TCP를 사용한다.
Message 크기: DV > LS
Message 갯수: DV < LS
👉 LS의 라우터들은 자신의 local link 정보를, DV 라우터들은 자신이 알고 있는 라우팅 정보(라우팅 테이블)을 전송하기 때문
'CS > 컴퓨터네트워크' 카테고리의 다른 글
| [Ch5] ICMP, SDN, SNMP (0) | 2024.01.01 |
|---|---|
| [Ch5] Hierarchical routing, RIP, OSPF, BGP (1) | 2023.12.31 |
| [Ch4] IPv6, SDN (0) | 2023.12.19 |
| [Ch4] IPv4, Network Address Translation(NAT) (1) | 2023.12.03 |
| [Ch4 Network Layer] Network Layer, Router (0) | 2023.12.02 |
