4. 네트워크 계층 3

ICMP(Internet Control Message Protocol)

• 네트워크 전체 상황을 파악하기 위해 만들어진 Control Message
• Source에게 네트워크에서 벌어지는 이벤트들을 전달해줌.
• 네트워크를 진단하는데 사용됨.
• Ipv4의 헤더가 아닌 데이터 부분에 들어감.

 

IPv6

 

IPv6 데이터그램 포맷

• 확장된 주소 기능: IP 주소 크기를 32비트에서 128비트로 확장했으므로 IP 주소가 고갈되는 일은 발생하지 않음.

 

IPv4에서 IPv6로의 전환

• 터널링
  • 터널: IPv6라우터 사이에 IPv4 라우터들을 지칭
  • 터널링
    • IPv4 라우터에 전달하는 IPv6 라우터는 IPv6 패킷을 받고 IPv4 패킷의 데이터 필드에 이것을 넣고, 목적지 주소를 터널의 수신측 IPv6 노드(라우터)로 적어서 보냄.
    • IPv4 패킷을 전달받은 IPv6 라우터는 IPv4 패킷을 받고 IPv4 패킷이 실제 IPv6 패킷이라는 것을 결정한 뒤, IPv6 패킷으로 만들어 다음 노드(라우터)로 전달

 

 

5.1 네트워크 계층: 제어 평면 개요

포워딩 테이블이 만들어지는 두 가지 방법 

• 라우터별 제어
  • 라우팅 알고리즘이 모든 라우터 각각에 동작하는 방식.
  • 포워딩과 라우팅 기능이 모두 개별 라우터에 포함되어 있음.
  • 각 라우터는 다른 라우터의 라우팅 구성요소와 통신하여 자신의 포워딩 테이블의 값을 계산하는 라우팅 구성 요소를 갖고 있음.
  • OSPF와 BGP 프로토콜이 이 방식을 기반으로 함.
• 논리적으로 중앙 집중된 제어
  • 논리적으로 집중된 컨트롤러가 포워딩 테이블을 작성하고 이를 모든 개별 라우터가 사용할 수 있도록 배포하는 방식.

 

 

5.2 라우팅 알고리즘

• 라우팅 알고리즘의 목표: 송신자로부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로(최소 비용 경로)를 결정하는 것,
• 그래프가 사용됨.
  • 그래프:  G = (N,E)
  • N: 노드. 패킷 포워딩 결정이 이루어지는 지점인 라우터를 나타냄.
  • E: 엣지. 라우터들 간의 물리 링크를 나타냄.

 

라우팅 알고리즘의 두 가지 분류

1. 중앙 집중형 라우팅 알고리즘
   • 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산함.
   • 모든 노드 사이의 연결 상태와 링크 비용을 입력값으로 함.
   • 이러한 정보는 알고리즘이 실제 수행되기 전에 어떠한 방법을 통해서라도 얻어야 함.
   • 링크 상태(Link-state, LS) 알고리즘이라고도 함.
2. 분산 라우팅 알고리즘
   • 최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행됨.
   • 어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지 않음.
   • 대신 각 노드는 자신에 직접 연결된 링크에 대한 비용 정보만을 가지고 시작함.
   • 이후 반복된 계산과 이웃과의 정보 교환을 통해 노드는 점차적으로 목적지 또는 목적지 집합 까지의 최소 비용 경로를 계산함.
   • 거리 벡터(Distance-vector, DV) 알고리즘이라고도 함.

 

링크 상태 라우팅 알고리즘

• 각 노드가 자신과 연결된 링크의 식별자와 비용을 포함하는 링크 상태 패킷을 네트워크 상의 모든 다른 노드로 브로드캐스팅 하게 함으로써 모든 링크 비용을 구함.
• 링크 상태 브로드캐스트 알고리즘이라고도 불림.
• 링크 상태 알고리즘(다익스트라 알고리즘)
  • 하나의 노드(출발지, u라고 지칭)에서 네트워크 내 모든 다른 노드로의 최소 비용 경로를 계산.
  • 반복 수행, k번 반복 후에는 k개의 목적지 노드에 대해 최소 비용 경로가 알려짐.
  • D(v): 알고리즘 현재 반복 시점에서 출발지 노드로부터 목적지 v까지의 최소 비용 경로의 비용.
  • p(v): 출발지에서 v까지의 현재 최소 비용 경로에서의 v의 직전 노드(v의 이웃).
  • N': 노드의 집합. 출발지에서 v까지의 최소 비용 경로가 명확히 알려져 있따면 v는 N'에 포함됨.

 

출발지 노드 u를 위한 링크 상태 알고리즘

• STEP 0 (초기화 )
  • N' = u (u에서 u까지 가는 비용만 명확히 알려져 있는 상태)
  • u와 연결되어 있는 노드들 중 방문하지 않은 노드를 차례로 방문하며 현재 알려진 최소 비용 계산
    • D(v) = 7 / p(v) = u
    • D(w) = 3 / p(w) = u
    • D(x) = 5 / p(x) = u
    • D(y), D(z) = 무한대 (아직 u와 직접 연결되어 있지 않음)
• STEP 1
  • N'집합에 포함되지 않은 노드들 중에서 최소 비용을 가진 노드 찾기 -> w(비용 3으로 가장 작음)
  • N' = uw (u에서 w로 가는 비용만 명확히 알려져 있는 상태)
  • w와 연결되어 있는 노드들 중 방문하지 않은 노드를 차례로 방문하며 현재 알려진 최소 비용 계산
    • D(v) = 6 / p(v) = w (N'=u일 때 D(v)=7이고 N'=uw일 때 D(w)+D(v)=3+3=6 이므로 6이 더 작기 때문에 더 작은 값으로 교체)
    • D(y) = 11 / p(w) = w (N'=u일 때 D(y)=무한대이고 N'=uw일 때 D(w)+D(y)=3+8=11 이므로 11이 더 작기 때문에 더 작은 값으로 교체)
    • D(z) = 무한대 (아직 uw와 직접 연결되어 있지 않음)
• STEP 2
  • N'집합에 포함되지 않은 노드들 중에서 최소 비용을 가진 노드 찾기 -> x(비용 5로 가장 작음)
  • N' = uwx (u에서 x로 가는 비용까지 명확히 알려져 있는 상태)
  • x와 연결되어 있는 노드들 중 방문하지 않은 노드를 차례로 방문하며 현재 알려진 최소 비용 계산
    • D(z) =  14 / p(v) = x (N'=u일 때 D(z)=무한대이고 N'=ux일 때 D(x)+D(z)=5+9=14 이므로 14가 더 작기 때문에 더 작은 값으로 교체)
• ...
• 최종적으로 얻게 되는 각 노드들 까지의 최단 경로 그림 & 포워딩 테이블

목적지	링크
v	(u, w)
x	(u, x)
w	(u, w)
y	(u, w)
z	(u, w)

• 시간 복잡도
  • n(n+1)/2 -> O(n^2)

• 라우팅 경로 진동(oscilation)
  • 경로 링크 비용은 링크상에서 전송 중인 부하와 같고, 이는 패킷이 겪을 수 있는 지연시간을 반영함.
  • C가 A로 패킷을 보낸다고 했을 때
    • 처음엔 C-> B-> A 경로로 감.(시계 반대 방향)
    • 라우팅 알고리즘을 업데이트 하면 A까지 가는 비용이 1+e인 기존의 경로보다 비용이 1로 더 작은 경로인 C -> D -> A 경로로 수정. (시계 방향)
    • 라우팅 알고리즘을 업데이트 하면 A까지 가는 비용이 2+e인 기존의 경로보다 비용이 0으로 더 작은 경로인 C-> B -> A 경로로 수정. (시계 반대 방향)
  • 이러한 방식으로 링크  비용이 트래픽의 양에 의존하여 경로가 양 방향으로 진동하는 문제를 경로 진동이라고 함.