Post

[네트워크] 네트워크 계층(Network) - 라우팅(Routing)

Posted
By Ennik 15 min read

OSI 7계층에서 Network Layer은 IP 프로토콜, 라우팅 알고리즘, ICMP 프로토콜을 다룬다

Data plane

  • Forwarding - 주어진 테이블로 데이터 단순 송신
  • 어떤 리소스에서 들어온 데이터 그램을 어떤 인터페이스로 내보낼 지 결정하는 것
  • 테이블이 있어서 테이블에 따름 (ex. IP주소를 보고 163.219…이면 2번 인터페이스로 보냄)

포워딩 테이블을 누가 작성하는가? → 전체 네트워크에 대해 알아야 함

특정 네트워크의 위치를 알고 가장 좋은 방법인 인터페이스를 결정

Control plane

  • 라우팅 결정 레벨 – routing
  • Routing(라우팅): 출발지(source)부터 목적지까지 네트워크 상황에 따라 테이블(경로)을 만들어내는 작업
  • 라우팅 - 테이블 결정 → 테이블에 따라 포워딩을 함.
  • 네트워크 control plane을 구성하는 두가지 접근
    • per-router control(traditional)
      • 전통적인 방식, 분산형
      • 각 라우터가 알아서 경로 파악 후 결정하고 서로 연락을 주고받으며 스스로 경로 작성
      • 라우터들끼리 정보 교환은 control plane에서 이루어짐
      • 장점
        • 특정한 중앙 노드가 필요하지 않음
        • 네트워크는 중앙 노드 하나가 없어지더라도 쉽게 복구가 됨
      • 단점
        • 네트워크를 비효율적으로 지나가는 경우가 생김, 트래픽이 일부에 집중될 수 있음
        • 실시간성 제공이 어려움. 트래픽의 양을 예측할 수 없고 트래픽 제어 불가
    • logically centralized control
      • 중앙집중형, software defined networking을 포함
      • 초월적, 전체적인 위치에서 모든 라우터들에게 지시를 내림
      • 중앙에 있는 하나의 remote controller에서 명령을 내리고 그 명령에 따라 각 라우터는 포워딩 테이블을 만듦
      • 장점
        • 트래픽 엔지니어링(완전한 제어)가 가능, 트래픽 집중을 방지할 수 있음
      • 단점
        • 모든 라우터들이 중앙 노드와 서로 커뮤니케이션 해야함
        • 아무데서나 사용할 수 없고 라우터들을 다 지배할 수 있는 특정 영역에서만 사용 가능
  • False Aggregation
    • Routing에서 Black hole이 생기는 원인
    • 인터넷 경로와 라우팅에서 발생할 수 있는 문제
  • Longest (prefix) matching routing rule
    • 라우팅 테이블에서 입력된 목적지 IP 주소를 기반으로 최적의 라우팅 경로를 선택하는 데 사용되는 방법 중 하나
    • 라우팅 테이블에는 목적지 IP 주소 범위 또는 프리픽스와 각 프리픽스에 해당하는 라우팅 정보 기록
    • 빠르게 구현할 수 있는 메모리 종류 - CAM(Content Addressable Memory) 또는 TCAM
  • Priority Queueing
    • 특정 패킷 또는 트래픽 클래스에 대한 우선순위를 부여하여 특정 유형의 트래픽이 높은 우선순위를 가지고 처리되도록 하는 것
    • Starvation - 특정 트래픽 클래스 또는 우선순위 높은 트래픽이 다른 트래픽 클래스나 우선순위 낮은 트래픽을 완전히 배제하는 상황 → 낮은 우선순위 트래픽이 대기열에서 무기한 대기하거나 처리가 지연될 수 있음

IP

라우팅 프로토콜

  • 소스에서 데스티네이션까지 최선의 경로를 결정하는 것
  • 크게 link state와 distance vector 두가지 카테고리
  • 경로**(path)**: 주어진 소스에서 파이널 목적지까지 가는 동안 가는 동안 거치는 일련의 라우터들
  • 비용이 적고, 빠르고, 가장 덜 붐비는 것, 좋은 것은 정의하기 나름
  • 라우팅은 굉장히 어렵다.
  • 라우터들 간의 연결을 그래프로 표현 가능
    • N은 노드(라우터의 집합), E는 엣지(링크의 집합)
    • N, E를 합쳐서 그래프라고 할 수 있음
    • 간선(Edge)에 weight(Cost)가 있어 최단경로가 무엇인지 정하는 문제
    • Cost는 정의하기 나름, 대역폭의 역수(B/W), 레이턴시, 금액 여러가지가 될 수 있음
    • 하나의 edge도 TCP Layer에서는 여러 개의 라우터를 거친것일 수 있음
  • 어떤 경로의 Cost: 각각의 링크들의 cost의 합
  • 라우팅 알고리즘 : 최소한의 비용을 지불하게 되는 경로는 무엇인지 찾는 것

라우팅 알고리즘 분류

  • Global
    • 전체적인 view를 가지고 라우팅을 하는 것
    • Link State 알고리즘

  • Decentralized

    • 로컬에서 옆에 있는 노드들의 정보만 보고 라우팅을 하는 것
    • Distance Vector 알고리즘
    • Routing by Rumor (소문에 의한 라우팅)
  • Static - 한번 라우팅을 정해서 잘 바꾸지 않음. 바꾸려면 세팅해야 함
  • Dynamic - 다양한 상황에 따라 그때그때 라우팅을 바꿔 줌. 실시간으로 네트워크 구성이나 cost같은 주변 정보 확인

  • Dijkstra’s algorithm

    • 그래프의 모든 링크의 cost를 다 알고 있어야 함
    • 모든 노드가 전체 그래프에 대한 정보를 가지고 있음
    • 각자가 최소 cost 경로를 계산하고 이를 바탕으로 forwarding 테이블을 만들고 목표 노드에 대한 경로 계산
    • C(x, y) - x에서 y로 연결되는 링크의 cost. 바로 이웃이 아니라면 ∞
    • D(v) - souce로부터 노드 v까지 현재까지 알려진 최선의 경로
    • P(v) - souce 로부터 v까지 최소경로 상에서 앞선 노드
    • N’ - 현재까지 최소경로가 확인된 노드들의 집합. 모든 노드가 여기 포함되면 알고리즘이 끝남
    • Cost가 낮은 노드부터 넣고 거쳐갔을 때 개선되는지 확인 후 경로의 cost 와 직전 노드 표기
    • Predecessor 통해서 최단경로를 알 수 있음
    • 안 쓰는 경로가 생기므로 트래픽이 몰릴 수 있어 트래픽을 조정할 수 있는 SDN(software defined routing)이 존재
    • 다익스트라는 모두가 같은 라우팅을 공유. 모두가 동의함. convergence
    • 걸리는 시간은 n개의 노드가 있을 때 loop n번 반복, 업데이트가 최악의 경우 n-1, 대략 O(n^2)

    dk

Distance vector 알고리즘

  • Bellman- Ford equation(Dynamic Programming)

    • 이웃한 노드간의 간격으로 source부터 목적지까지 얼마나 걸리는지 알아냄
    • 인접한 노드들에서 목적지까지의 거리와 자신과 인접한 노드들까지의 cost를 더한 값에 최소값인 노드를 선택
    • 이웃한 노드들이 이미 가지고 있는 정보를 이용해서 최단경로를 알아낸다.
    • 특정한 노드 v의 distance vector는 v가 그 그래프 상에 있는 모든 노드들에 대한 거리를 벡터로 표시한 것
    • Routing Convergence - 모두가 동의하지 않으면 데이터가 왔다갔다 하면서 트래픽을 늘려서 network congestion으로 이어짐. 네트워크 다운
    • 네트워크에 큰 변화가 일어났을 때(cost 변화) 새로운 convergence를 이뤄야 하고 그 전에는 혼란이 있을 수 있음
    • 노드들은 자기가 가지고 있는 distance vector의 추정치를 대략 30초에 한번씩 계속 주변에 줌. 이웃으로부터 distance vector를 받으면 Bellman- Ford equation을 가지고 업데이트

    BF

    BF

    BF

  • Bad news travels slow - 어떤 간선의 cost가 크게 커지더라도 이전의 정보때문에 빨리 반영되지 않음
  • Poisoned reverse
    • 간선의 cost가 증가했을 때  늦게 반영되는 것의 해결책
    • 자신이 알려준 경로를 바탕으로 다시 자신에게 경로를 제시하는 것을 방지
    • Poisoned reverse를 하더라도 loop가 있다면 distance vector는 쓸 수 없다. Loop prevention 필요

Autonomous system(AS)

  • 네트워크 관리와 라우팅을 위해 정의된 독립적인 네트워크 도메인

  • AS 번호 (AS Number) - 각 AS에는 고유한 AS 번호, 이 번호를 사용하여 AS 식별, 다른 AS와의 통신 관리

  • Intra-AS 라우팅 (Interior Gateway Routing Protocol, IGP)
    • 동일한 자율 시스템(AS) 내에서 라우팅을 관리하는 데 사용되는 라우팅 프로토콜
    • RIP, EIGRP, OSPF 등이 Intra-AS 라우팅 프로토콜의 예시
      • RIP(Routing Information Protocol) - 거리 벡터(distance vector) 라우팅 프로토콜
      • EIGRP(Enhanced Interior Gateway Routing Protocol) - DV, Cisco가 개발한 고급 거리 벡터 라우팅 프로토콜
      • OSPF(Open Shortest Path First) - 링크 상태(link-state) 라우팅 프로토콜
  • Inter-AS 라우팅 (Exterior Gateway Routing Protocol, EGP)
    • 서로 다른 자율 시스템(AS) 간에 라우팅 정보를 교환하는 데 사용되는 라우팅 프로토콜
    • BGP(또는 eBGP)가 가장 일반적인 Inter-AS 라우팅 프로토콜
      • BGP (Border Gateway Protocol)
        • AS 간 라우팅 트래픽을 관리하고 다른 AS에 대한 네트워크 전송 정보를 교환하는 데 사용되는 프로토콜
        • 1순위: Local Preference - 가장 높은 쪽으로 내보냄
        • 2순위: AS PATH Attribute - 지나는 AS의 수를 최대한 짧게 함
        • 3순위: MED(Multi - Exit Discriminator Attribute) - MED 값이 낮을수록 해당 경로의 우선순위가 높음

BGP는 기본적으로 Distance Vector와 Link State 중 어느 방식을 따르며, 또 해당 방식의 약점을 극복하기 위한 해결책

Distance Vector, AS-PATH(경로상의 모든 AS를 기록)

BGP 라우팅에서 Tdown 즉 링크가 끊어 진 후 Convergence를 다시 이루는 시간이 Tree 구조의 네트워크에서 짧은 이유

링크가 끊어질 탐색해 볼 대체 경로를 찾는데 경우의 수가 없으므로(작으므로) 수렴 시간이 짧다.

AS 내부의 routing 불안을 외부에 전파 시킬 attribute는 무엇이며 그 이유

MED, 내부의 Routing 불안(라우팅 변 화)을 따라 MED 값이 달라지고 이 변화가 AS간의 라우팅 경로를 바꾸게 되므로 (Local_Pref, AS-PATH가 같은 값은 같은 경우)

SDN

Distance Vector Routing에서 Traffic Engineering을 구현하기 어려운 이유

Source와 Destination이 같은 데이터그램은 같은 경로를 지나가게 Routing Algorithm이 만들어져서 이 트래픽을 효율적으로 나누어 네트워크 자원을 충분히 활용하기 어렵다.

TCP/IP에서 정의하는 flow와 SDN에서 정의하는 flow의 차이점

TCP/IP에서 정의하는 flow는 4-tuple(Src IP, Src Port, Dst IP, Dst Port)으로 정의되지만, SDN에서는 flow를 LINK, IP, TCP, APP 계층의 요소를 다양한 방식으로 결합하여 정의할 수 있다.

Controller가 스위치의 configuration을 query 하거나 set할 수 있게 하는 프로토콜

Openflow

Computer Networking: A Top-Down Approach 8 th edition Jim Kurose, Keith Ross Pearson, 2020

0.2 네트워크
Network Network Layer
This post is licensed under CC BY 4.0 by the author.