[네트워크] 09. 네트워크 계층 1 (L3: 라우팅, 혼잡제어, 패킷 분할, IP 프로토콜, 다익스트라)

1. 네트워크 계층의 역할

네트워크 계층(L3)의 핵심 목표는 (1) 라우팅, (2) 혼잡제어 두가지 이다.

• 라우팅: 송수신 호스트 사이에서 end to end 레벨에서 최적의 패킷 전달 경로를 선택하는 과정
• 혼잡제어: 혼잡을 (1)예방 또는 (2)해소하는 기능
  • 혼잡(Congestion): 라우터 큐에서 패킷이 들어오고 나가는데까지 걸리는 시간이 일정 threshold를 넘어서는 것.
  • 네트워크 특정 영역에서 혼잡이 발생하면 주변으로 빠르게 확산된다.

[서비스 유형]

• 비연결형 서비스(데이터그램): 경로를 미리 정하지 않고 패킷마다 독립적으로 전송, 도착 순서가 일정하지 않고 중간에 패킷 분실 가능성이 있어 상위계층(TCP 등)에서 순서 재조정 및 오류 복구를 해야한다.
• 연결형 서비스(가상회선): 전송 전 가상회선(경로)을 설정하고 모든 패킷이 그 길로만 간다. 신뢰성이 높고 도착 순서가 일정하지만, 패킷 분실 시 재전송으로 인해 순서가 어긋날 수 있다.

 

[패킷의 분할과 병합]

: 상위 계층의 데이터가 너무 클 경우 물리 계층 전송을 위해 여러 패킷으로 패킷 분할을 하고, 목적지에서 다시 패킷 병합을 한다.

---

2. 라우팅

(1) 라우팅 세부 개념

고려사항: 라우팅을 할 때는 공평성(특정 패킷 차별금지), 효율성(지연시간 최소화, 처리량 극대화)를 고려한다.

* 처리량(초당 전송가능한 비트수 bps)는 end to end의 처리량 중 가장 낮은 성능의 처리량 병목 구간에 의존한다.

 

[정적 vs 동적 라우팅]

: 네트워크 상황(혼잡), 토폴로지 변화 등에 동적으로 대처할 수 있는지 여부에 따라 구분

• 정적 라우팅: 관리자가 수동으로 경로를 입력, 보안도 좋고 오버헤드가 적지만, 네트워크 변화에 대처하기 어렵다.
• 동적 라우팅: 네트워크 상황에 따라 경로가 동적으로 변함. 최적 경로 선택이 가능하지만, 라우터간 정보 교환으로 오버헤드가 발생.

[HELLO & ECHO 패킷]

• HELLO: 주변 라우터에 HELLO 패킷을 보내어 주변 경로 정보를 획득함. 주기적으로 주변 라우터와 주고 받음.
• ECHO: 라우터 사이의 전송 지연시간 측정을 위한 용도의 패킷

---

(2) 라우팅 기법 분류

• 소스 라우팅: Sender가 전체 경로를 결정한 후, 전송 패킷에 기록하는 방식
• 중앙 라우팅: RCC(Routing Control Center)라는 특별한 호스트가 전송 경로에 관한 모든 정보를 중앙에서 관리하는 방식
• 분산 라우팅: 패킷의 전송 경로에 위치한 각 라우터가 직접 경로 선택에 참여하는 방식
• 계층 라우팅: 분산 라우팅(대규모 네트워크) + 중앙 라우팅(소규모 네트워크) 조합 방식

---

3. 혼잡 제어 (Congestion Control)

원인: 버퍼 부족으로 패킷 손실 -> 송신 호스트가 timeout 이후 재전송 -> 혼잡 심화의 악순환이 반복됨

 

[여러가지 해결 방법]

• Timeout 시간이 짧으면 혼잡도가 증가하므로 혼잡 징후가 보이면 timeout 시간을 늘린다.
• 패킷 생존 시간(TTL, Time To Live): 패킷이 무한히 떠도는 것을 막기 위해 라우터를 지날 때 마다 값을 1씩 줄여 0이 되면 폐기한다. 
• 트래픽 성형: Leaky Bucket 알고리즘을 사용해 불규칙한 트래픽 유입을 일정한 속도로 네트워크에 흘려 보낸다.
  • 네트워크 혼잡은 burst가 많은데 leaky bucket은 물이 세는 양동이 처럼 일정한 속도로 패킷을 내보낸다.
• ECN(Explicit Congestion Control): 라우터가 혼잡 징후를 감지하면 송신 호스트에 ECN 패킷을 전송해서 송신자가 전송량을 줄이도록 유도한다.

---

3. 라우팅 프로토콜

: 최적의 경로를 결정하는 것(minimize distance)

*네트워크에서 distance란?: 지나가는 라우터의 개수(= 홉의 수, # of hops)가 기준이다. 물리적 거리가 아님!!

 

[기본 라우팅 원리]

• 최단 경로 라우팅: 홉(Hop) 수가 가장 적은 경로를 선택한다.
• 플러딩(Flooding): 들어온 패킷을 모든 포트로 내보낸다. 비효율적이지만, 중요 데이터를 모든 호스트에 전달할 때 사용함.
  (재난 상황 프로토콜)

---

[거리 벡터 라우팅]

• 개념: 라우터가 자신과 연결된 이웃 라우터와 주기적으로 라우팅 정보를 교환하는 방식. '거리(Distance)'와 '방향(Vector)' 정보만 관리함.
• 구성 요소:
  • 링크 벡터(이웃 연결 정보)
  • 거리 벡터(개별 네트워크까지의 거리)
  • 다음 홉 벡터(개별 네트워크로 가기위한 다음 홉 정보)
• RIP (Routing Information Protocol):
  • 거리 벡터 방식의 대표적 프로토콜로 구현이 간단해 소규모 네트워크에 적합하고 내부 라우팅 프로토콜에 사용됨
  • 업데이트 규칙: 새로운 목적지 정보가 오면 추가하고, 기존 정보보다 더 짧은 경로가 발견되거나, 기존 경로의 라우터가 정보를 갱신하면 업데이트.

---

[링크 상태 라우팅]

• 개념: 라우터가 네트워크 전체의 연결 상태(Topology)를 파악하여 최단 경로를 계산한다(다익스트라 알고리즘 사용).
• 특징: 정보 변화가 있을 때만 전파하며, OSPF가 대표적이다. 내부 라우팅 프로토콜에 사용된다.

---

[자율 시스템]

• 자율 시스템(AS: Autonomous System): 단일 관리기관 내의 라우터와 네트워크 그룹 (KT, LG U+, 부산대 등) 독립적인 라우팅 로직을 가질 수 있다.
• 내부 라우팅: 자율시스템 내에서의 라우팅, RIP, OSPF를 쓴다.
• 외부 라우팅: 자율시스템 간의 라우팅, BGP(Border Gateway Protocol)를 쓴다.

---

4. IP 프로토콜 (end to end의 연결)

IP 프로토콜: 인터넷에서 네트워크 계층의 데이터 전송 프로토콜

 

[특징]

• 비연결형 서비스(데이터그램)를 제공
• 패킷 분할, 병합 기능 수행
• BE(Best Effort) 원칙에 따른 전송기능 제공(전송을 100% 보장하지 않으므로 상위 layer에서 전송 오류 문제를 고려해라)

[헤더 구조]

• DS/ECN (Service Type): 우선순위 및 혼잡 알림(QoS)용 필드49.
• Identification, DF, MF, Fragment Offset: 패킷 분할 및 재조립에 사용.
• TTL: 패킷 생존 시간.
• Protocol: 상위 계층 프로토콜(TCP: 6, UDP: 17, ICMP: 1) 표시.
• Header Checksum: 헤더 오류 검출.
• Source/Destination Address: 출발지/목적지 IP 주소 (Class A~E).

---

5. 패킷 분할 (Fragmentation)

필요성: 네트워크마다 전송 가능한 최대 크기(MTU)가 다르므로, 라우터가 이를 통과시키기 위해 패킷을 분할해야한다.

 

• 라우터 좌우에 연결된 LAN이 서로 다를 경우, 데이터 링크 계층에서 프레임의 크기가 서로 다를 수 있다.
• 따라서 데이터를 수신한 후에 다음으로 중개하는 방향에 위치한 LAN에 맞도록 프레임을 분할해야한다.

 

[예시: ID, PL, MF, FO 채우기]

 

---

6. DHCP (Dynamic Host Configuration Protocol: 동적 호스트 구성 프로토콜)

: 동적으로 IP 자동 할당, 관리, 회수하여 자원효율을 높이는 프로토콜.

• IP를 Pool 형태로 관리해서 네트워크를 사용하는 PC에만 자동 할당하고 사용하지 않으면 회수하여 관리함
• Timeout 기반으로 IP 주소를 일정 주기로 회수하는 방법을 사용

[DHCP 4-way handshake]

 

• DHCP_DISCOVER: 클라이언트가 서버를 찾음 (Broadcast). (클라이언트: IP 찾아요!)
• DHCP_OFFER: 서버가 IP 주소를 제안함. (서버: 이 IP 어때요?)
• DHCP_REQUEST: 클라이언트가 제안된 IP 사용을 요청함. (클라이언트: 이거 쓸게요!)
• DHCP_ACK: 서버가 최종 승인함. (서버: 그거 쓰세요~)

---

7. 다익스트라 알고리즘

: 링크 상태 라우팅에서 네트워크 토폴로지 전체 정보를 수집한 후 하나의 소스에서 다른 모든 노드까지의 최소 비용 경로를 계산하는데 사용된다.

 

[다익스트라 알고리즘]

1. 초기화: 출발지 노드(SRC)만 방문 집합(N') 에 넣고, 이웃 노드 거리값 초기화 (이웃하지 않으면 무한대).
2. Loop:
   1. 아직 방문하지 않은 노드 중 비용 D(w)이 가장 작은 노드 (w) 를 선택해 N'에 추가한다.
   2. 새로 추가된 노드(w)를 거쳐가는 경로가 기존 경로보다 짧으면 비용 정보를 갱신한다.
      D(v) [cite_{start}]= min(D(v), D(w) + c(w,v)).
   3. 모든 노드가 N'에 들어올 때까지 반복한다.

 

[예제: 다익스트라 알고리즘 테이블 채우기]

 

라우팅 테이블은 다익스트라 테이블의 p() 정보를 역추적해서 만든다.

 

• 목적지(Destination): 패킷이 최종적으로 가야 할 곳.
• 링크(Link): 출발지(u)가 해당 목적지로 가기 위해 가장 먼저 거쳐야 하는 직접 연결된 경로.

[예시: 목적지가 y인 경우]

• 다익스트라 Table의 D(y), p(y)를 본다. 값은 (2, x)이다. (Step 1에서 갱신됨)
• 의미: y의 직전 노드는 x ( ... → x → y)
• 판단: u 입장에서 x는 직접 연결된 이웃이므로 x에게 보내면 x가 알아서 y로 보낼 것이다.
• 결과: 링크는 (u, x)가 된다.

 

[예시: 목적지가 w인 경우]

• 다익스트라 Table의 D(w), p(w)를 본다. 값은 (3, y)이다.
• 의미: w의 직전 노드는 y (... → y → w)
• 역추적:
  • w 전에는 y가 있음.
  • y 전에는 누가 있지? →  x가 있음.
  • x 전에는 누가 있지? →  u가 있음.
• 경로: u → x → y → w
• 판단: u가 가장 먼저 보내야 할 곳은 x
• 결과: 링크는 (u, x)가 된다.