컴퓨터 네트워크 5: Network Layer - Control Plane

LeemHyungJun·2023년 12월 11일

컴퓨터네트워크

Computer Network

목록 보기

6/8

1. Introduction

Network-layer functions (Recap)
- forwarding: data plane / 라우터 안에서
- routing: control plane / 전체 경로상에서
Per-router control plane
- 기존에 쓰던 방식
- 각 라우터당 라우팅 알고리즘 존재
Software-Defined Networking control plane
- 중앙 집중형
- agent가 server에 존재

2. Routing Protocols

출발지에서 목적지까지 "good" "path"를 결정하기
- path
  - router packet의 sequence
  - initial source에서 destination host까지의 경로
- good : 적은 cost (빠름, 혼잡x)
Graph abstraction: link costs
- $cost = \frac{1}{bandwidth}$ or $cost = \frac{1}{congestion}$
- 각 링크 당 가중치를 cost로 생각하고 그래프 문제를 푼다.
  - 가중치가 무한대라면 직접 연결이 안된 경우
Routing Algorithm Classification

2-1. Link State

다익스트라 link-state 라우팅 알고리즘
- 특징
  - centralized
  - iterative
- notation
  - $C_{x,y}$ : x,y를 직접 연결한 link의 가중치
  - $D(v)$ : 목적지 v까지의 최소 비용
  - $p(v)$ : 목적지까지 가는길에 바로 직전의 노드
  - $N'$ : 최소비용경로가 알려진 노드
- 알고리즘
  - $N'$ 에 자기 자신(시작) 노드를 넣고 시작해서 최소 비용인 노드들을 하나씩 넣다가 모든 노드가 $N'$ 에 들어가면 반복을 종료한다.
- 목적지까지의 최소 비용 계산식
  - $D(v) = min(D(v), D(w)+C_{w,v})$
    - $D(v)$ : 기존값
    - $D(w)+C_{x,y}$ : 새로 비교하게 되는 값
- 분석
  - 알고리즘 시간 복잡도
    - n개의 노드가 있을때 $O(n^2)$
    - $O(nlgn)$ 으로도 구현 가능
  - message 복잡도
    - 각 노드가 연결된 모든 노드에 정보를 전달해야함
    - $O(n^2)$
Oscillations Possible
- 네비게이션의 경로 추천 기능 처럼..
- A경로가 빠를 때 A경로를 추천하지만, 점차 A경로가 포화상태가 되고 이후로는 B경로를 추천하게된다.

2-2. Distance Vector

Bellman-Ford equation (DP)
- $D_x(y)=min_v{c_{x,y}+D_v(y)}$
BF Example
Distance vector algorithm
- 다른 노드가 계산된 결과를 바탕으로 계속해서 업데이트하기 (다익스트라 알고리즘은 다른 노드의 정보 생각x)
- "good news travels fast" : 더 좋은 값으로 바뀐 것은 더 빨리 다른 노드들로 전파된다.
- "bad news travels slow" : count to infinity

2-3. Comparison of LS and DV

message complexity
- LS : n개의 라우터 -> $O(n^2)$
- DV : 수에 따라 달라짐
speed of convergence
- LS : global, $O(n^2)$
- DV : distributed and iterative (LS보다 오래걸림)
robustness
- LS
- DV : 잘못된 정보 한번에 모두가 잘못될 수 있다. (LS보다 보안이 취약함)

3. Intra-ISP routing: OSPF

making routing scalable
- 이전까지는 라우터가 모두 동일한 것으로 생각했지만 실생활에서는 그렇지 않다.
- 실제로는 모든 라우터들의 도착지를 테이블에 저장할 수 없으며, 각 ISP는 네트워크를 자신이 원하는 대로 운영하고 싶어한다. 이런 것들을 위해 "autonomous systems 으로 조직화 해서 운영한다!

Autonomous Systems (aka domains)

Intra-AS
- AS 내부의 동작
- AS 내부에서는 같은 프로토콜로 동작한다.
- gateway router 라는 다른 AS와 연결되는 link가 존재한다.
Inter-AS
- AS와 AS간의 동작
- 특정 AS에서 나가는 datagram이 있을때 어떤 라우터를 골라야 하는지는 연결된 AS를 보고 어디로 갈 수 있는지를 확인해 본 후 결정한다.
Intra-AS routing
- RIP(Routing Information Protocol)
  - classic DV 방식, 잘 안씀
- EIGRP(Enhanced Interior Gateway Routing Protocol)
  - DV based
- OSPF(Open Shortest Path First)
  - Link-State 라우팅
  - IS-IS protocol(OSPF와 유사)

OSPF routing

특징
- 라우팅 동작 방식이 공개되어있다.
- classic link-state 방식으로 동작함
  - 링크 상태 flooding, 인접한 것 뿐만 아니라 모든 라우터에게 정보를 broadcasting
- multiple link cost metrics : 동일한 비용을 가진 다른 링크를 이용할 수 있다. (분산시키기)
- security : 모든 메세지를 인증을 통해 참여한다.
- two-level hierarchy
  - backbone(inter AS 담당)->border(gateway 역할)->local 라우터

4. Routing Among ISPs: BGP

Inter-AS routing 방식이기 때문에 전 세계에 하나만 존재한다.
BGP(Border Gateway Protocol)
- 라우터의 forwarding table의 목적지가 AS 외부에 있는 경우 필요한 프로토콜
- eBGP(external BGP)
  - AS와 AS를 연결하는 BGP
- iBGP(internal BGP)
  - 같은 AS 내의 라우터 간 BGP 연결
  - iBGP가 필요한 이유는 바깥에서 받아온 정보를 내부에 알려주기 위해서 이다

BGP basics
- BGP session
  - 두개의 BGP 라우터끼리는 반영구적인 TCP를 통해 연결한다.
- 동작 예시
  1) 위의 그림에서 AS3에서 x라는 데이터를 AS2에게 보내면 AS3, x라고 표시한다.
  2) 이후 AS2는 AS1으로 전달하면서 x는 AS2를 거쳐 AS3로부터 왔다는 뜻으로 AS2,AS3,x 라고 표시한다.
경로 특성
- prefix(목적지) + attributes(특성)의 형태로 전달
- policy-based
  - use import policy
- 특성의 종류
  - AS-PATH : 목적지 주소에 대한 배포가 어떤 주소를 거쳐서 왔는지
  - NEXT-HOP : AS-PATH를 시작하는 라우터 인터페이스의 IP 주소
BGP advertisement
BGP message
- OPEN
- UPDATE
- KEEPALIVE
- NOTIFICATION
BGP path advertisement??
Intra vs Inter AS
- policy : inter AS의 경우 관리자가 라우팅되는 방법이나 누가 라우팅 하는지 등을 제어한다. intra AS는 단일 관리자이므로 정책이 의미 없다
- scale : 계층 라우팅을 통해 사이즈와 트래픽을 줄인다.
- performance : intra AS가 성능에 더욱 focus
Hot potato routing
- domain 내에서 비용이 가장 적은 local gateway를 선택하기
- AS 바깥의 비용은 생각하지 않고 빨리 자신의 AS내에서 밖으로 보내는 것
BGP: achieving policy via advertisements
- 다른 ISP간의 transit traffic을 전달하지 않기 (X가 B와 C간의 트래픽을 전달하는 것을 막는 것이 목적)
- X가 자신을 제외하고 다른 경로가 없다고 알려주어서 B에서 C의 경로를 막는다.
BGP route selection
1) policy 따르기!, 지역 선호도
2) 짧은 AS-PATH
3) 가까운 NEXT-HOP, 뜨거운 감자
4) 다른 기준들

5. SDN control plane

왜 control plane을 centralized 했을까
- network mangement를 쉽게 하기
- programming이 쉽다.
- open 해서 기술의 발전을 도모
Traffic engineering
- 과거의 방식
  - 가중치를 분산시키기 위해 source에서 destination 까지의 경로를 다양하게 구성하는 것이 어렵다.
  - load balancing 구현 어렵다.
  - 특정 지점을 지나서 가는 경로를 만들도록 구현하기가 어렵다.
- SDN
  - 과거의 방식에서 불가능한 것을 할 수 있게 되었다.
  - SDN은 hardware/controller/application 세가지로 분류하여 동작한다.
    - dataplane switches
      - hardware에 구현된 dataplane forwarding을 위한 switch
      - openflow를 통해 control plane과 정보를 주고받음
    - software controller(network OS)
      - network의 상태 체크하는 역할
      - sounthbound API를 통해 switch들과 상호작용하며, northbound API를 통해 application들과 상호작용한다.
    - network-control apps
      - unbundled 한 특성 (각각 하는 기능이 따로 나누어져 있다)
OpenFlow protocol
- 세가지 메세지 종류
  - controller to switch
  - asynchronous (switch to controller)
  - symmetric
- controller-to-switch message(flow table 세팅을 위한 메세지)
  - features: controller가 질문하고 switch가 응답함
  - configure
  - modify state: openflow table 수정
  - packet-out: controller가 제어하는 스위치의 지정된 포트에서 특정 패킷을 내보낸다.
- switch-to-controller message
  - packet in: packet을 controller에게 전달
  - flow-removed: flow table entry를 삭제한다.(시간 만료나 modify state 메세지 수신한 경우)
  - port status: 스위치가 port의 상태를 controller에게 알리기
다익스트라 LS가 SDN으로 동작하는 예시
SDN의 문제점
- 중앙집중형이므로.. 한번에 고장남

6. Internet Control Message Protocol

ICMP
- host와 라우터의 통신할때 사용 (3계층에서-network layer)
- error reporting 할때 많이 사용한다.
Traceroute and ICMP
- 출발지에서 도착지까지의 경로 구하기(출발지와 목적지 사이의 라우터 이름과 주소를 알아내기)
- 도착지에 도달하면 "port unreachable" 메세지를 통해 도착지에 도달한 것을 알 수 있다.