[네트워크 5편] - Network Layer : Control Plane

네트워크 5편 Control Plane은 총 4개의 내용으로 구성됩니다.

 

1. Overview

2. Routing Protocol

3. Intra-AS Routing in the Internet : OSPF

4. Inter-AS Routing in the Internet: BGF

 

✔️ Overview

• Network-Layer Functions
  • Data Plane(HW): Forwarding
  • Control Plane(SW): Routing
    • 2가지 Approach
      • traditional per-router: 각 라우터 내에 routing algorithm 존재.
      • SDN: Centralized controller에서 계산한 내용을 각각 Router의 Control Agent에 전달.

✔️ Routing Protocol

• Routing Protocols
  • 라우터의 네트워크를 통한 source에서 destination 까지 좋은 경로를 찾는 것.
  • 경로 = sequence of routers.
• Graph Abstraction of Network
  • cost: 패킷 입장에서의 비용.
  • routing algorithm: algorithm that find the least cost path.
• Routing Algorithm Classification
  • Global vs Decentralized
    • Global = all routers have complete topology link cost info. 
      • link-state를 알고있음.
    • Decentralized = routers know physically-connected neighbors, link cost to negihbors.
      • 각 노드가 네트워크 내의 다른 노드까지의 비용 추정값을 벡터 형태로 가지고 있다.
  • Static vs Dynamic
    • Static = routes change slowly over time. (종종 사람이 개입한 결과)
    • Dynamic = routes change more quickly. (cost change 나 topology에 더 민감)
• Link State Routing Algorithm
  • 다익스트라 알고리즘
    • 네트워크 topology, link cost를 모든 노드가 가지고 있다.
      • 네트워크 전체에 broadcasting.
    • 한 노드에서 다른 노드까지 경로를 계산한 forwarding table 작성.
    • iterative 하다.
    • precedessor: 전위자가 있으므로, 전위자를 보고 따라간다.
  • Complexity
    • O(N^2)의 복잡도를 가짐.
    • 효율적으로 만들다 보면, O(nlogn) 까지도 가능.
    • oscillation problems(ping-pong) : support link cost equals amount of carried traffic.
      ( 트래픽 양에 따라 경로가 자꾸 변경됨.)
• Distance Vector Algorithm
  • Bellman Ford Equation(Dynamic Programming)
    • 노드는 각 이웃노드까지의 cost를 알고 있고, 이웃 노드가 가지고 있는 타 노드까지의 cost도 알고 있다. (= 라우팅 테이블)
    • 측정값이 바뀌면 바뀐 노드가 이웃된 노드의 vector 값을 업데이트 시킨다.
    • iterative, distributed 하다.
  • Cost Changes
    • link cost down.
      • node가 local link cost 변화 감지.
      • 자기 자신을 update하고 연결된 이웃에게 알림.
      • 이웃 노드도 확인하고 update.
    • link cost up.
      • node가 변화 감지.
      • 이미 기존에 세팅된 최소 거리로 update되어 있기 때문에 loop를 돌려서 원래의 값보다 커질 때 까지 무한 루프.
      • 해결 방법: Posioned Reverse
        • 기존의 값이 무한하다고 알리기.
• Comparison LS vs DV
  • message complexity
    • LS: O(nE) n- node, E - links
    • DV: exchange btw neighbors, 수렴 시간에 따른 문제
  • spread of convergence
    • LS: O(N^2) 시간 동안 O(nE)의 메세지.
    • DV: convergence time varies may have routing loop. count to infinity problem.
  • Robustness: 견고성 (what happens if mal-function?)
    • LS: incorrect한 cost를 가지고 있어도 각 노드들은 각자 계산한 table을 가지고 있기 때문에 propagate 되지 않음. 
      타 노드에 영향을 미치지 않는다.
    • DV: advertise incorrect path to the other nodes. - propagate 가능.

 

✔️ Intra-AS routing Protocol : OSPF(Open Shortest Path First)

• 실제 사용되는 프로토콜.
• router에는 모든 주소가 들어있는 게 아닌 longest prefix matching(subnet)으로 나뉘어 routing table 작성.
  
  
• Autonomous System: AS
  • 단순하게는 ISP 라고 생각하면 됨.
  • 라우터들의 모임.
    
    
  • Intra-AS routing
    • ISP 내에서의 네트워킹.
    • AS 내의 모든 라우터들은 같은 intra-domain routing을 사용해야함.
    • gateway router: AS 밖으로 나가는 AS의 edge. 다른 AS와 연결됨.
  • Inter-AS routing
    • ISP 간 혹은 AS 간의 라우팅.
    • Gateway Router는 Intra-AS Routing Protocol 뿐만 아니라 Inter-AS Routing Protocol도 진행.
• Interconnected ASes
  • Forwarding Table은 intra-AS 알고리즘과 inter-AS 알고리즘으로 결정.
    • intra-AS routing은 AS 내의 도착지로 가기 위한 결정.
    • inter-AS routing은 AS 바깥의 도착지로 가기위한 결정.
• Inter AS tasks
  • A의 AS에서 B의 AS로 나가려는 패킷을 보낼 때.
    • 1. 어떤 gateway 라우터가 AS B로 내보내는 지 알아내기.
    • 2. Reachability Info(Subnet, 경로 info)를 AS A에 다 알리기.
• Intra AS Routing
  • OSPF : Open Shortest Path First
  • 어떤 프로토콜을 사용할 지는 ISP가 결정함.
• OSPF: Open Shortest Path FIrst
  • open, free 프로토콜.
  • link-state algorithm 활용. (=다익스트라 알고리즘)
    • topology map이 각 노드에 저장되어 있음.
  • AS 내의 모든 라우터들에게 OSPF의 Link state를 알림(=broadcating)
    • 이 내용은 OSPF 메세지로 전달.
  • OSPF가 제공하는 고급 기능.
    • security: 인증된 OSPF 메세지
    • multiple same cost paths allowed
    • Hierarchical OSPF 제공
      • 2 Level hierarchy: local area / backbone
      • link state advertisement in area
      • each nodes has detailed area topology.
        • 다른 area의 topology는 모르지만, 가야하는 방향은 알고 있다.

 

✔️ Inter-AS routing Protocol : BGP(Border Gateway Protocol)

• BGP = Border Gateway Protocol
  • Inter-domain routing protocol
• eBGP(=external BGP) : AS로부터 reachability info를 obtain.
• IBGP(=internal BGP): AS 내의 모든 router에게 reachability info를 propagate.
  • subnet이 internet 나머지 부분에 reachability info를 advertise 하기도 함.
• gateway router는 eBGP, iBGP를 모두 돌린다.
  
  
• BGP session
  • 2개의 BGP 라우터는 서로 간의 semi-permanent 한 TCP Connection을 열어 BGP 메세지를 주고 받는다.
  • BGP is a path vector protocol.
  • ISP에 라우터 하나가 추가되었다면, reachability info를 다른 AS에게 전달.
• inter AS routing은 policy의 영향을 많이 받음.