5장 네트워크 계층(1)

(본 글은 “컴퓨터 네트워킹 하향식 접근” 도서 및 네트워크 프로그래밍 수업 내용을 정리한 글 입니다.)

5. 네트워크 제어부분

5.1 라우팅 프로토콜

5.1.1 라우팅 프로토콜의 개요

[목적]

• 출발지에서 목적지 까지 최적의 경로를 결정 하는 것
• 경로란 패킷이 거쳐지나가는 라우터의 순차

[종류]

• 글로벌 vs 분산
  • 글로벌 : 모든 라우터가 서로의 대한 정보를 완전히 알고 있음 [링크 상태 알고리즘]
  • 분산 : 각 라우터는 이웃과의 정보를 교환하며 반복적인 계산작업 수행 [거리 벡터 알고리즘]
• 정적 vs 동적
  • 정적 : 경로가 느리게 변함[링크 상태 알고리즘]
  • 동적 : 경로가 자주 변함 (주기적 갱신)[거리 벡터 알고리즘]

5.1.2 링크 상태 라우팅 알고리즘

• 대표적 사례 : 다익스트라 알고리즘
• 링크 비용이 모든 노드에게 알려짐
  • 모든 노드가 같은 정보를 가진다 (브로드 캐스팅 사용)

• 하나의 노드에서 다른 모든 노드에 대한 최소 비용 경로를 계산한다

• 다익스트라 알고리즘

  1. 자기 노드로부터 인접한 링크에 대한 값들을 넣어줌
  2. D(w)값 (= 최소 경로)가 가장 적은 노드를 찾아 N에 넣는다 (큐)
  3. D(v) = min (D(v), D(w) + c(w,v)) 즉 새롭게 추가된 애를 거쳐서 갔을 때 더 작은경로가 있는지 체크
  4. 이를 반복한다
  • 알고리즘의 복잡도는 n(n+1)/2 = O(n^2)
  • 효율적으로 구현한다면 O(nlg n)
• 문제점
  • 때로는 분산시킬 때 더 효과적일 수 있는데 항상 최단경로로만 몰린다
  • 진동문제가 발생할 수 있다.

5.1.3 거리 벡터 알고리즘

• 대표적 사례 : 벨만포트 알고리즘

• 자기 자신의 인접한 노드의 거리 + 해당 노드에서 목적지 까지의 거리의 최소값을 계산

• Dx(y) = x에서 y까지의 추정치

  • 초기에는 다 모르니까 무한값
  • 각 노드끼리 정보를 교환하다보면 점차 최소경로값에 근사하게된다
    • 비동기 , 반복형
    • 이웃벡터로부터 갱신메세지를 받으면 재계산 후 변경된다면 다시 이웃에게 알린다
• 특징1) 비용 감소에 대한 좋은 소식은 빨리 전파된다

• 특징2) 비용증가에 대한 나쁜 소식은 무한카운트 문제 발생

  • 포이즌 리버스를 통해 해결하자
    • A가 B를 통해 목적지로 가는 경로를 설정했다면 A는 B에게 나로부터 목적지까지 거리가 무한이라 설정
    • 그러나 3개 이상의 노드를 포함한 루프는 포이즌 리버스로 감지할 수 없다.

5.1.4 LS,DV 비교

• 메세지 복잡성
  • LS : O(ne)
  • DV : 수렴시간은 다양
• 수렴 속도
  • LS : O(n^2) , 진동문제 발생 가능
  • DV : 수렴시간 다양 , 무한카운트 발생 가능
• 강건성 (라우팅에 문제 발생)
  • LS : 각 노드는 잘못된 링크비용을 전파 가능 (자신의 테이블만 계산해서 특정 링크만 오류가짐)
  • DV : 특정 잘못된 링크정보가 다 전파되므로 오류가 누적되서 커질 수 있다

5.2 계층적 라우팅

5.2.1 계층적 라우팅 개요

• 모든 목적지를 라우팅테이블에 저장하는건 비현실적
• 영역별 관리가능한 만큼 라우터 영역을 나눈다
• 구분되는 하나의 영역을 AS라고 한다
• 계층적 라우팅은 테이블크기를 줄이고 갱신을 위한 트래픽을 줄인다.

[Intra-AS라우팅]

• 같은 AS안에서 이루어지는 라우팅
• 같은 라우팅 프로토콜을 사용한다 (다른 AS라면 달라도 괜찮다)
• 내부 목적지에 대한 엔트리를 설정 (어디로 가야 가장 빠른가?)

[Inter-AS라우팅]

• AS간의 라우팅
• 외부 목적지에 대한 엔트리를 설정

[게이트웨이 라우터]

• AS에서 외부 AS에 패킷을 전달하는 라우터

• inter , intra라우팅을 모두 수행한다

  • inter라우팅을 통해 외부로부터 받은 정보를 intra로 내부로 알린다

• AS와 AS사이에서 서로 정보를 넘겨주는 작업을 위해 양쪽에서 BGP프로토콜을 돌린다.

• 모든 라우터는 Inter + Intra라우팅을 수행해야한다

  1. 게이트웨이가 가져다주는 정보를 받기 위해 inter를 돌려야함

  2. 게이트웨이로 보내는 경로를 확인하기 위해 intra또한 돌려야 한다.

     (정리 : 외부[inter+intra] // 내부[intra] )

5.2.2 Intra-AS 라우팅

RIP(DV), OSPF, IGRP(DV)와 같은 종류가 있다. - open shortest path first

[OSPF]

• 개방되어있어 공용 사용이 가능
• 링크 상태 알고리즘 사용
  • 다익스트라 알고리즘을 사용
• OSPF 링크상태 정보는 AS전체로 플러딩(다뿌린다)
• OSPF메세지는 IP에 의해 직접적으로 운반된다 (TCP, UDP X)

OSPF의 개선된 기능들

• 보안 : 모든 OSPF은 인증을 받아야 한다
• 여러개의 동일 비용경로가 가능 -멀티경로 (RIP는 1개)
• 유니캐스트, 멀티캐스트 통합 지원
• 계층적 OSPF를 통해 큰 영역에서 사용가능 (AS영역이 크더라도 관리가능)

5.2.2.1 계층적 OSPF

• AS도 커지게 된다면 이를 더 쪼갤수 있도록 OSPF는 구현되어있다
• 쪼개지는 단위를 Area라고 한다

• 용어

  • 경계 라우터 : AS와 AS를 연결하는 라우터
  • backbone : area와 area를 연결해주는 영역 (area border router가 내부에 존재)
  • backbone 라우터 : backbone내부의 라우터, 백본라우터들에 대해 OSPF라우팅 실행
  • area border routers : area와 area를 연결하는 라우터
• 로컬영역과 백본 2개의 계층구조를 가진다

5.2.3 Inter-AS 라우팅(BGP)

• 서브넷으로 하여금 자신의 존재를 광고한다

• inter domain라우팅 프로토콜의 종류

  • eBGP : 이웃에서 AS사이에서 정보를 얻음

  • iBGP: AS내부의 모든 라우터들에게 도달 가능 정보를 전파

(게이트웨이는 당연히 eBGP, iBGP모두 사용)

• BGP 세션
  • BGP라우터쌍은 TCP연결을 통해 메세지를 교환

• 프리픽스

  • 프리픽스(서브넷주소) + 속성 = 경로
  • 210.3.4.5/24 일때 210.3.4부분이 프리픽스 (네트워크를 나타낸다)
  • 2가지 속성
    • AS-Path : 프리픽스 광고가 거쳐가는 AS리스트
    • Next-Hop : 인접 AS연결이 있는 내부 AS라우터의 인터페이스
  • 자신의 라우터정책에 따라 경로 광고 수신여부를 결정한다 ex)
• 다중 경로가 나타나면 정해진 정책에 따라 선택

5.2.3.1 BGP 메세지

• BGP 메세지는 TCP를 통해 교환

• 종류

  • OPEN : tcp설정 및 송신자 인증
  • UPDATE : 새로운 경로 광고 및 옛날 경로 제거
  • KEEPALIVE : 연결 유지 및 OPEN의 ACK
  • notification : 오류 보고 및 연결 닫을 때

왜 Inter-AS와 IntraAS의 라우팅 프로토콜이 다른가?

Inter : 정책에 초점(관리자는 누가 자신의 네트워크를 통하는지 제어하기 원한다)

Intra : 성능에 초점(내부적으로 돌아가므로)

5.2.3.2 BGP경로 선택

• 다중 경로에 대한 삭제
  • 지역 선호 값 속성 (AS관리자 정책)
  • 최단 경로
  • 가장 가까운 Next-Hop 라우터 [Hot Popato라우팅]
  • BGP식별자 이용

[뜨거운 감자 라우팅]

• intra-domain경로가 짧은 게이트웨이 라우터를 선택 (홉수가 더 긴것을 선택할 수 도 있다.)
• inter-domain은 고려하지 않는다
  • 말 그대로 계산이 오래걸릴 수 있는 바깥은 고려하지 않고 내부만 신경