control plane은 datagram이 sender host로부터 receiver host까지 경로상의 라우터들 간에 어떻게 전달되어야 하는지 뿐만 아니라 네트워크 계층 구성요소들과 서비스들을 어떻게 설정하고 관리할지도 제어 한다.

실제 user의 data가 들어왔을 때 forwarding 하는 것을 Data plane이라고 했음.

forwarding: router의 input port에 들어온 packet을 output port로 local하게 switching하는 일

forwarding 하기 위해선 control plane이 있어야 함.

input port로 들어온 패킷의 헤더 안의 destination 주소를 보고 output port를 결정할 수 있는 건 router들간에 주고 받는 메세지로 만들어진 routing table에 의해서 만들어진 forwarding table (best of best만 골라 넘겨줌).

router들은 user packet에 관계없이 자기들끼리 ctrl msg를 주고 받으며 end to end로 가는 경로를 계산.

control plane은 user data가 들어왔을 때 어떤 output port로 보낼지 결정하는 일!

5.2 장에서는 그래프에서 최소 비용 경로를 계산하기 위한 전통적인 라우팅 알고리즘을 다룬다. 이 알고리즘은 가장 널리 사용되는 두 가지 OSPF와 BGP의 기반이다. 이 두 프로토콜은 각각 5.3장과 5.4장에서 다룬다.

OSPF는 단일 ISP 네트워크 내에서 동작하는 라우팅 프로토콜인 반면 BGP는 인터넷의 모든 네트워크를 상호 연결하는 역할을 하는 라우팅 프로토콜이다.

Control plane routing protocol은 전통적으로 라우터 내에 data plane의 패킷 forwarding 기능과 한 덩어리로 뭉쳐져 구현되어 있어서 융통성이 없었지만, Software Defined Networking (SDN)은 data plane과 control plane을 분리하고 contorl plane 기능을 자신이 관리하는 라우터의 전달 기능 요소와 분리된 별도의 원격 controller 서비스에 구현한다. SDN controller는 5.5장에서 다룬다.

5.6장과 5.7장에서는 IP 네트워크 관리의 기본 요소인 ICMP(Internet Control Messeging Protocol)와 SNMP(Simple Network Management Protocol)에 대해 공부한다.

---

Chapter 5. network layer, control plane

control plane을 만드는 두 가지 방법

1. per-router control (traditional routing algorithm)
   destination IP address를 보고 forwarding하는 방식, 라우터마다 독립적인 control 보드 가짐.

• Routing algorithm classification = Path selection algorithm
  • link state routing algorithm: Dijkstra's algorithm
  • Distance vector algorithm: Bellman-Ford algorithm
  • Hierarchical routing
• Routing protocols = msg, action(Path selection algorithm을 실행), format
  • RIP, OSPF (ISP 내에서의 통신) / BGP (ISP 끼리의 통신)

2. logically centralized control SDN controllers
   logically centralized된 controller가 FIB를 작성하고, 이를 모든 개별 라우터가 사용할 수 있도록 배포한다. 라우터는 기존에 별도의 장치로 구현되었던 다양한 기능들 (load balancing, Firewall, NAT 등)까지 수행할 수 있다.
   OpenFlow controllers 중앙에서 한꺼번에 보고 결정.

Traditional Routing Algorithms (dest-based forwarding)

router에는 user의 data가 지나가는 data plane이 있고, control plane에는 user의 packet을 source로부터 destination까지 전달하기 위한 route를 결정하는 control msg(routing protocol에서 정의한)들이 돌아다님.

data plane: match(destination IP addr가 matching되는지) + action(forwarding) ⇒ dest-based fwd.

Per-router control plane

5장에서 보려는 라우팅 프로토콜은 각각의 router에 모두 탑재되어 있다. (but 다르게 구현될 수 있음)

라우팅 알고리즘들은 모든 라우터 각각에서 동작하는 경우이다. forwarding과 routing 기능이 모두 개별 라우터에 포함되어 있다. 각 라우터는 다른 라우터의 라우팅 구성요소와 통신하여 자신의 FIB를 setting 한다.

OSPF와 BGP 프로토콜이 이 라우터별 제어방식을 기반으로 한다.

5.2 Routing algorithms (path selection)

라우팅 알고리즘의 목표는 sender host로부터 receiver host까지 라우터의 네트워크를 통과하는 좋은 루트를 결정하는 것이다. 일반적으로 "좋은" 경로란 최소 비용 경로를 말한다.

routing protocol 자체는 message format & action (Path selection)

Routing protocol goal

source → destination, 어느 길로 가야 좋을까? (shortest, fastest, real time fastest)

unicast routing을 볼 것(한 source에서 한 destination으로 가는 길)

: determine "good" paths (routes) from sendign hosts(source router) to receiving host(dest router), through NW of routers.

• path: sequence of routers packets will traverse in going from given initial source host to given final destination host. 어떤 라우터들을 지나가느냐.
• good:
  “least cost(fixed: link BW, error ratio, NW admin, variable: load TI = congestion)”,
  “fastest”,
  “least congested(buffer의 TI등을 봄)”
  - typically means minimum cost path (least-cost path) or
  - shortest path (smallest number of links) if all edges have the same cost

Graph abstraction of the network

OSPF는 전체를 보고 라우팅 프로토콜 msg를 주고 받으며 N과 E를 앎.

Routing algorithm classification

Q1. global or decentralized information?

OSPF는 global information을 가지고 자신이 속한 ISP에게 broadcast하여 모두 알려줌. (Link State)

• Global: 모든 router가 완벽한 topology (connectivity, link cost)를 갖고 Link State (LS) 알고리즘
  • 네트워크 전체에 대한 완전한 정보를 가지고 source와 dest사이의 최소 비용 경로를 계산한다. 즉, 이 알고리즘은 모든 노드(라우터) 사이의 연결 상태와 link cost를 입력값으로 한다.
  • 전체 상태 정보를 가지는 이 알고리즘을 Link State algorithm이라고 한다. 이는 이 알고리즘이 네트워크 내 각 링크의 cost를 알고 있어야 하기 때문이다.
  • Link State (LS) algorithms: 모든 라우터에 대한 네트워크 전체의 정보를 완벽히 알고난 후 path selection 알고리즘을 running. → 모든 라우터가 각각의 라우터에 대한 정보를 알 수 있도록 msg를 주고 받도록 define해놓은 라우팅 프로토콜이 OSPF
• Decentralized: NW 상황에 대한 정보를 모든 router에게 X, 바로 옆 router에게만 local하게 줌.
  = physically-connected 된 neighbor에게만 정보(e2e=routing table=Distance Vector) 전달.
  바로 연결된 애들한테 가는 길만 정확하고, 한 hop을 넘어간 길은 결정은 할 수 있으나 정확하지 X.
  그 라우터 바로 다음 라우터에 붙어있는 subnet로 가는 path selection algorithm을 돌렸을 때 나온 값은 내 옆 라우터가 알려준 정보를 믿고 계산한 것 = estimate. (iterative process of computation)
  - 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다. 어떤 노드도 모든 link cost에 대한 완전한 정보를 갖고 있지 않다. 대신 각 노드는 자신에 직접 연결된 link에 대한 link cost만 가지고 시작한다. 이후 반복된 계산과 neighbor router와의 정보 교환을 통해 router는 점차적으로 dest까지의 최소 비용 경로를 계산한다.
  - 이 decentralized algorithm을 distance vector 알고리즘이라고 한다. 이는 각 router가 네트워크 내 모든 router까지 비용의 측정값을 벡터 형태로 유지하기 때문이다. 이웃한 router들끼리 반복적으로 message를 교환한다.
  - Distance Vector(DV) algorithms: 한 홉만 정확히 알고 있고 나머지는 측정 값.
  Estimates of costs (distance) to all other nodes in the network.

각각의 이 알고리즘을 쓰게 support하는 msg를 define 해놓은 것이 OSPF, RIP, BGP이다.

Q2. static or dynamic?

• Static: routes change slowly over time. 손으로. (수동 → 늦게 반영)
• Dynamic: routes change more quickly. 네트워크 변화에 빠르게 대응할 수 있다. (responsive)
  라우터들은 라우터들의 동작을 monitoring하는 protocol을 추가로 가지고 있음 (SNMP)
  어떤 라우터의 보드가 죽었으면, 라우터가 그를 감지하고 라우팅 프로토콜 msg에 그 뒤의 destination으로 갈 수 없다고 알려줌. (OSPF 같은 경우 모든 라우터에게 전송, RIP 같이 한 hop만 가는 decentralized algorithm의 경우 옆에 라우터에게 알려줌, 또 그 옆으로, 점점 퍼져나감.) detour하여 NW가 작동.
  네트워크 트래픽 부하나 topology 변화에 따라 routing 경로를 바꾼다. 주기적으로 변경에 직접 응답해 네트워크 변화에 더 빠르게 대응할 수 있으나 경로의 loop나 oscillation과 같은 문제에 더 취약하다.

Q3. load-sensitive or load-insensitive?

• load sensitive: 실시간으로 로드가 변화하는 것을 감지, 최근에 혼잡한 링크에 높은 비용을 부과, 우회
• load insensitive: 항상 고정된 값을 사용. RIP, OSPF, BGP. 최근의 혼잡을 반영하지 X

A link-State Routing Algorithm (OSPF)

Link State algorithm은 network topology와 모든 link cost가 알려져 있어서, 각 라우터가 자신과 연결된 link에 대한 정보를 네트워크 상의 모든 다른 router로 broadcast함으로써 가능하다.

broadcast를 통해 모든 router는 NW에 대한 동일하고 완벽한 view를 갖게 된다. 각 노드는 이제 LS 알고리즘을 통해 다른 노드들과 동일하게 최소 비용 경로 집합을 계산할 수 있다.

Dijkstra's algorithm

• Global Dynamic routing (global 하게 정보를 주고 + 문제가 생기면 알려주어 rerouting하는 dynamic)
• 문제가 생기면 모든 라우터에게 전송. net topology를 완벽하게 각각의 router가 가질 수 있도록 한다.
• broadcast, all nodes have same info (최종의 목표: 완벽한 net topology를 모두가 가진다.)
• computes least cost paths from one node (me) to all other nodes (n-1) → routing table
• iterative: after k iterations, know least cost path (n-1) to k dest's.

notation

• c(x,y): link cost from node x to y. ∞ if not direct neighbors.
• D(v): 현 시점에서 출발지 노드부터 목적지 v까지의 최소 비용 경로의 비용. 상황에 따라 변하는 값
• p(v): predecessor node. 출발지에서 v까지의 최소비용 경로에서 v의 직전 node
• N: set of nodes whose least cost path definitively known. 노드의 집합.

Dijkstra's Algorithm

Dijkstra's algorithm, time complexity

• using global info
• no loop in selected path
• non-negative cost only

⇒ O(n^2) to O(nlogn)

Problem of Dijkstra's algorithm

load sensitive cost를 사용할 때의 단점. Herding effect. 진동 문제가 발생

Distance vector (DV) algorithm

각 router는 직접 연결된 이웃 router로부터 정보를 받고, 계산을 수행하며, 계산된 결과를 다시 그 이웃들에게 배포한다. 이웃끼리 더 이상 정보를 교환하지 않을 때까지 프로세스가 지속된다.

Bellman-Ford equation (dynamic programming)

slowly converge find routing table

---

Keywords

• Routing protocol

  = Routing algorithm (path selection computation) + (message format/order & action)

• Link-state routing algorithm (Dijkstra's algorithm)

-- Using global link state information

-- Link cost should NOT be negative

-- All nodes (routers) share their local network information, e.g., port up/down

-- A router finds the least cost path to each of the other routers.

-- There is no loop in the found paths.

-- Finally, a router updates FIB with (destination IP network, output_port)