네트워크 계층(4) _ ICMP, Routing Algorithm, Link-State Routing Algorithm

 ICMP (Internet Control Message Protocol) 

• 네트워크 상에서 증상을 알리기 위한 컨트롤 메시지를 전송하는 프로토콜
• IP 패킷을 처리할 때 발생하는 에러를 알려주며 보통 네트워크 진단을 위해 많이 사용됨
• IP는 오직 패킷이 목적지에 도달했는지만 확인하기 때문에, 어떤 이유로 에러가 발생했는지는 알려주지 못함 ⇒ 이러한 단점을 보완하기 위해 나온게 ICMP
• 목적지의 호스트가 없거나 목적지 port에 서버 프로그램이 없는 등의 에러 상황이 발생하면, IP header에 기록되어 있는 출발지 호스트에게 해당 에러를 알려주는 기능을 함

 

• ICMP 패킷 Type

 

 

• code 0: Network 도달불가
• code 1: Host 도달불가
• code 2: protocol 도달불가
• code 3: port 도달불가
• code 4: fregment(단편화)가 필요하지만 DF(dont fregment)가 설정되어 있음

 

 

 

 

 

 

 

 

 

---

 IPv6 

• IPv6은 고정된 40byte 헤더를 갖는다.
• 단편화(fragmentation)를 허용하지 않는다.
• Priority: flow 안에서 데이터그램 간의 우선순위 식별
• flow label: 같은 flow 안에 있는 데이터그램들 식별 (flow라는 개념 아직 명확하게 규정되지 않음)
• next header: 상위 계층 프로토콜 식별

IPv4와 IPv6의 과도기가 왔을 때 혼용하는 방식 Tunnerling

 

 Tunnerling 

• IPv4 라우터를 거쳐갈 때 IPv6 데이터그램을 IPv4의 데이터 필드(payload)에 포함해서 전송한다
• IPv4와 IPv6은 버전이 달라서 서로를 인식하지 못하기 때문에 IPv6을 IPv4 패킷 안에 넣어서 전달한다.

---

 Routing Algorithm 

• 송신자로부터 수신자까지 데이터를 전송할 때 어떤 라우터들을 통과해서 가야할지 경로를 선택하는 알고리즘
• 이 라우팅 알고리즘에 의해 fowarding table이 구성됨

 

⛳ Global vs Decentralized information

• Global
  • 모든 라우터들은 완벽한 topology와 link cost 정보를 가진다
  • link state algorithm
  • link state: 모든 노드가 자신의 링크 정보를 브로드캐스트로 전체에게 알려준다.
• Decentralized information
  • 라우터는 물리적으로 연결된 이웃을 알고있고, 그 이웃까지 이동하는 비용을 알고있다.
  • 이웃과 정보를 교환하는 반복 계산 과정을 거친다.
  • distance vector algorithm

 

⛳ Static vs Dynamic

• Static
  • forwarding table을 직접 만드는 방법
  • 경로가 아주 느리게 변하는 경우이다. 종종 사람이 개입(직접 링크 비용 수정)한 결과로 그렇게 된다.
• Dynamic
  • forwarding table을 네트워크 상태에 따라 업데이트 하는 방법
  • Link State(LS), Distance Vector(DV), Hierarchical
  • 네트워크 그래픽 부하나 위상 변화에 따라 라우팅 경로를 바꾼다. 동적 알고리즘은 주기적으로, 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다.

 

우리가 배우는 것

1️⃣ link state

• 모든 간선의 정보를 알고 있을 때 사용되는 알고리즘

2️⃣ distance vector

• 이웃한 라우터의 간선 정보만 알고 있을 때 사용되는 알고리즘

---

 Link-State Routing Algorithm 

• 각 라우터들이 자신이 보유한 간선의 정보들을 모든 네트워크에 있는 라우터들에게 브로드캐스트를 통해 알리고, 모든 라우터들은 네트워크 상 모든 간선에 대한 비용 정보를 저장할 수 있도록 한다.
• 모든 라우터들은 모든 네트워크 상의 모든 간선 정보를 알고 있기 때문에 특정 라우터 u 에서 z 라우터로 패킷을 보낼 때 다익스트라 알고리즘을 이용하여 최단 경로를 취득할 수 있다.

❗그러나❗

• 하나의 라우터가 전 세계 라우터 지도를 저장할 수는 없다.
• 따라서 현실적으로 Link State Algorithm은 일정 크기의 같은 네트워크에 위치하는 라우터들의 지도만을 저장하고 있다.
• 예) 한양대 네트워크, 성균관대 네트워크 이런 식으로 네트워크 관리 책임 주체가 동일한 네트워크에 대해서만 Link State Algorithm을 수행한다. 이는 네트워크 관리 주체가 결정하는 것으로, 타 기관이 Link State Algorithm을 사용하는지 안 하는지 알 수 없기도 하다. (자세한 내용은 이후 강의에서 다루기로함)

 

✨ Link State 알고리즘은 다익스트라 알고리즘을 사용한다.

1️⃣ step0

시작점 U와 연결된 라우터만 살펴보고 해당 라우터까지의 최소 비용을 갱신해준다.

직접적으로 갈 수 없는 경우에는 INF 값으로 설정한다.

 

2️⃣ step1

3,u가 제일 비용이 작기 때문에 w가 선택되어 N'에 들어간다.

w와 이웃한 노드를 토대로 비용 업데이트.

p(v)에서 7,u 와 6,w 중 6,w이 더 작기 때문에 6,w로 업데이트!

 

3️⃣ step2

5,u가 제일 비용이 작기 때문에 x가 N'에 들어간다.

x와 이웃한 노드를 토대로 비용 업데이트. 없음

 

4️⃣ step3

6,w가 제일 비용이 작기 때문에 v가 N'에 들어간다.

v와 이웃한 노드를 토대로 비용 업데이트.

p(y)에서 11,w 와 10,v 중 10,v이 더 작기 때문에 10,v로 업데이트!

 

5️⃣ step4

10,w가 제일 비용이 작기 때문에 y가 N'에 들어간다.

y와 이웃한 노드를 토대로 비용 업데이트.

p(z)에서 14,x 와 12,y 중 12,y이 더 작기 때문에 12,y로 업데이트!

 

6️⃣ step5

모든 노드들이 N'에 포함되었으므로 반복을 종료한다.

 

 진동 문제 (ocillations possbile) 

비용이 네트워크 트래픽인 경우

• 노드 B는 1, C는 e, D는 1 만큼의 트래픽을 갖는다.
• 초기 상태에서 D → A는 1만큼의 비용이 발생하고, B → A로 갈 때는 e + 1만큼의 비용이 발생한다.
• C의 라우터는 시계방향으로 가는 것이 비용이 더 적게 드는 것을 감지하고, 시계방향으로 경로를 정한다.
• 일정 시간 이후, D → A 가는 비용이 2+e 이고 B → A 가는 비용이 0 이라는 것을 라우터가 다시 감지하고 다시 경로를 반시계방향으로 바꾼다.
• 매번 더 나은 상황을 위해 움직이다보니, 트래픽 상황 비용을 갱신할 때마다 시계방향과 반시계방향의 경로를 진동하듯 계속 방황하게 된다.

 

 해결방법 

• 1️⃣ 해당 링크가 전달하는 트래픽의 양에 의존하지 않도록 한다.
• 2️⃣ 모든 라우터가 동시에 링크 상태 알고리즘을 실행하지 못하도록 동기화하지 않는다.

→ 하지만 라우터들은 스스로 자기들끼리 점진적으로 동기화 된다. 이러한 자기 동기화는 각 노드가 링크 상태 정보를 송신하는 시각을 임의로 결정하게 함으로써 회피할 수 있다.

---

 Distance Vector Algorithm 

• 인접한 라우터들에 대해서만 거리를 아는 경우
• 라우터 x와 라우터 y간의 최단경로는 라우터 x와 인접한 모든 라우터 중 최소 라우터 v간의 거리와 해당 점 v와 y간의 최단 거리의 합으로 정의 할 수 있음

 

---

참고자료

 

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

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

[알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현

[알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현

네트워크 계층 4

네트워크 계층 4

📡 [Network] 링크 상태(Link State) 라우팅 알고리즘과 진동 문제 (Ocillations possbile)

📡 [Network] 링크 상태(Link State) 라우팅 알고리즘과 진동 문제 (Ocillations possbile)