[컴퓨터 네트워크] Chapter 4. Networks Layer Data Plane (Part 1) - (2)

일자 : 12주차 1차시

2. 라우터 내부 구성

• 입력 포트, 스위칭, 출력

• 버퍼 관리, 스케줄링

[1] 라우터 아키텍처 개요

• 일반적인 라우터 아키텍처의 고수준 개요:

  

1) 4가지 컴포넌트

1. 라우터 입력 포트: 네트워크에서 수신한 데이터를 라우터로 전달하는 역할을 한다.

2. 라우팅 프로세서: 수신된 패킷을 처리하고, 라우팅 테이블을 참조하여 최적의 경로를 결정한다.

3. 고속 스위칭 패브릭: 라우터 내부에서 패킷을 빠르게 전달하고, 출력 포트로 데이터를 전송하는 핵심적인 구조이다.

4. 라우터 출력 포트: 라우터에서 처리된 데이터를 목적지 네트워크로 전송하는 역할을 한다.

2) 특징

• 라우팅, 관리 제어 플레인(소프트웨어)은 밀리초 단위로 작동한다.

  • routing processor

• 포워딩 데이터 플레인(하드웨어)은 나노초 단위로 작동한다.

  • router input ports

  • high-speed switching fabric

  • router output ports

[2] 입력 포트 기능

1) 3가지 컴포넌트

1. 라인 종료 (Line Termination)

   • 물리 계층: 비트 단위로 데이터를 수신한다.

2. 링크 계층 프로토콜 (수신)

   • 링크 계층: 예를 들어, 이더넷(6장에서 배울 예정)

   • 데이터그램을 처리한다.

3. 조회, 포워딩, 큐잉

   • 패킷을 저장한다.

   • 분산 스위칭:

     • 헤더 필드 값을 사용하여 입력 포트 메모리 내의 포워딩 테이블을 참조하여 출력 포트를 조회한다 (“매치 플러스 액션”).

     • 목표: ‘line speed’에서 입력 포트 처리를 완료하는 것이다.

     • 입력 포트 큐잉: 데이터그램이 스위치 패브릭으로 포워딩되는 속도보다 더 빠르게 도착할 경우 큐잉이 발생한다.

   • 2가지 접근법

     • 목적지 기반 포워딩 (Destination-based forwarding): 전통적으로 목적지 IP 주소만을 기반으로 데이터를 포워딩한다.

     • 일반화된 포워딩 (Generalized forwarding): 헤더 필드 값들의 집합을 기반으로 데이터를 포워딩한다.

[3] Destination-based forwarding

: 목적지 기반 포워딩(Destination-based forwarding)에 대한 포워딩 테이블

1) 테이블 구성

• 첫 번째 범위: 11001000 00010111 00010000 00000000 부터 11001000 00010111 00010111 11111111 까지 (인터페이스 0)

• 두 번째 범위: 11001000 00010111 00011000 00000000 부터

  code복사

          11001000 00010111 00011000 11111111 까지 (인터페이스 1)

• 세 번째 범위: 11001000 00010111 00011001 00000000 부터

  code복사

          11001000 00010111 00011111 11111111 까지 (인터페이스 2)

• Otherwise (그 외): 인터페이스 3

1. 이미지 하단에는 "Q: but what happens if ranges don't divide up so nicely?"(범위가 이렇게 깔끔하게 나누어지지 않으면 어떻게 되나요?)라는 질문이 포함되어 있습니다.

이 테이블은 네트워크에서 패킷이 도착했을 때, 목적지 주소를 기반으로 어떤 인터페이스로 전송할지를 결정하는 데 사용됩니다.

[4] 가장 긴 접두어 일치 (Longest prefix matching)

1) 가장 긴 접두어 일치

: 주어진 목적지 주소에 대한 포워딩 테이블 항목을 찾을 때, 목적지 주소와 일치하는 가장 긴 주소 접두어를 사용한다.

2) 포워딩 테이블

3) 예시

(1) 목적지 주소: 11001000 00010111 00010110 10100001

: 첫 번째 범위인 11001000 00010111 00010*** ********을 확인했다. 이 범위는 11001000 00010111 000101과 일치했다. 따라서 이 주소는 인터페이스 0으로 포워딩된다.

(2) 목적지 주소: 11001000 00010111 00011000 10101010

: 두 번째 범위인 11001000 00010111 00011000 ********을 확인했다. 이 범위는 11001000 00010111 00011000과 정확히 일치했다. 따라서 이 주소는 인터페이스 1으로 포워딩된다.

4) 특징

• 가장 긴 접두어 일치가 왜 사용되는지 곧 주소 지정에 대해 공부할 때 알게 될 것이다.

• 가장 긴 접두어 일치: 종종 삼진 내용 주소 가능 메모리(TCAM)를 사용하여 수행된다.

  • 내용 주소 가능: 주소를 TCAM에 제공하면, 테이블 크기와 관계없이 한 클럭 사이클 내에 주소를 검색할 수 있다.

  • Cisco Catalyst: 약 100만 개의 라우팅 테이블 항목이 TCAM에 저장된다.

[5-1] 스위칭 패브릭

• 입력 링크에서 적절한 출력 링크로 패킷을 전송한다.

• 스위칭 속도: 입력에서 출력으로 패킷을 전송할 수 있는 속도

  • 종종 입력/출력 라인 속도의 배수로 측정된다.

  • N개의 입력이 있을 경우: 스위칭 속도는 N배의 라인 속도가 바람직하다

• 스위칭 패브릭의 세 가지 주요 유형

  

  1. 메모리

  2. 버스

  3. 상호 연결 네트워크

[5-2] 메모리를 통한 스위칭

1) 첫 번째 세대 라우터:

• 전통적인 컴퓨터로, 스위칭은 CPU의 직접적인 제어 하에 이루어진다.

• 패킷은 시스템의 메모리로 복사된다.

• 속도는 메모리 대역폭에 의해 제한된다 (각 데이터그램마다 2번의 버스 교차가 발생한다).

[5-2] 버스를 통한 스위칭

• 입력 포트 메모리에서 출력 포트 메모리로 데이터그램이 공유 버스를 통해 전송된다.

• 버스 경쟁: 스위칭 속도는 버스 대역폭에 의해 제한된다.

• 32 Gbps 버스, Cisco 6500: 액세스 라우터에 충분한 속도를 제공한다.

[5-3] 상호 연결 네트워크를 통한 스위칭

• 크로스바, 클로스 네트워크 및 기타 상호 연결 네트워크는 처음에 다중 프로세서 시스템에서 프로세서들을 연결하기 위해 개발되었다.

• 다단계 스위치: 여러 단계의 작은 스위치를 통해 n×n 스위치를 구성한다.

• 병렬성 활용:

  • 데이터그램을 고정 길이의 셀로 분할하여 입력 시 처리한다.

  • 셀을 패브릭을 통해 스위칭하고, 출력 시 데이터그램을 재조합한다.

[6] 입력 포트 큐잉

• 스위치 패브릭이 입력 포트들의 결합된 속도보다 느릴 경우-> 입력 큐에서 큐잉이 발생할 수 있다.

  • 큐잉 지연 및 입력 버퍼 오버플로우로 인한 손실이 발생할 수 있다.

• Head-of-the-Line (HOL) 블로킹: 큐의 맨 앞에 있는 대기 중인 데이터그램이 다른 데이터그램이 앞으로 나가는 것을 방해한다.

1) 예시

1. 예시 1

   

   : 출력 포트 경쟁: 빨간색 데이터그램 하나만 전송될 수 있다. 아래의 빨간색 패킷은 차단된다.

2. 예시 2

   

   : 하나의 패킷 시간이 지난 후: 초록색 패킷은 HOL 블로킹을 경험한다.

[7-1] 출력 포트 큐잉

• 데이터그램이 패브릭에서 링크 전송 속도보다 더 빨리 도착할 경우 버퍼링이 필요하다.

  • 드롭 정책: 만약 버퍼가 부족할 때 어떤 데이터그램을 삭제할지 결정한다.

  -> 데이터그램은 혼잡 또는 버퍼 부족으로 인해 손실될 수 있다.

• 스케줄링 규칙은 대기 중인 데이터그램들 중에서 전송할 데이터그램을 선택한다.

  -> 우선순위 스케줄링 – 누구에게 더 나은 성능을 제공할지, 네트워크 중립성은 어떻게 유지할지.

[7-2] 출력 포트 큐잉

• 스위치를 통한 도착 속도가 출력 라인 속도를 초과할 때 버퍼링이 발생한다.

• 출력 포트 버퍼 오버플로우로 인한 큐잉(지연)과 손실이 발생할 수 있다!

[8] 버퍼 관리

1) 버퍼 관리

• 드롭: 버퍼가 가득 찼을 때 어떤 패킷을 추가하거나 삭제할지 결정한다.

  • 테일 드롭: 도착한 패킷을 삭제한다.

  • 우선순위: 우선순위 기준으로 패킷을 삭제하거나 제거한다.

• 마킹: 어떤 패킷에 혼잡 신호를 표시할지 결정한다 (ECN, RED).

[9] 패킷 스케줄링: FCFS

1) 패킷 스케줄링

: 링크에서 다음에 전송할 패킷을 결정하는 것

• 선착순 처리 (First Come, First Served)

• 우선순위

• 라운드 로빈

• 가중치 공정 큐잉 (Weighted Fair Queueing)

2) FCFS

: 패킷은 출력 포트로의 도착 순서대로 전송된다.

• 또한 First-in, First-out (FIFO) 으로 알려져 있다.

• 실제 사례는 무엇이 있을까?

3) 실제 사례

1. 대기열 시스템: 예를 들어, 은행에서 고객이 순서대로 서비스를 받는 경우, 먼저 도착한 사람이 먼저 서비스를 받는 방식이 FCFS(선착순 처리)와 비슷하다.

2. 프린터 대기열: 여러 사람이 동일한 프린터를 사용할 때, 각 작업은 도착 순서대로 출력된다. 첫 번째 작업이 끝난 후 두 번째 작업이 처리된다.

3. CPU 스케줄링: 컴퓨터 시스템에서 여러 프로세스가 CPU를 사용하려고 할 때, 각 프로세스가 도착한 순서대로 CPU를 할당받는 방식도 FCFS로 처리될 수 있다.

4. 고속도로 톨게이트: 톨게이트에서 차들이 순서대로 통과하는 방식. 도착한 순서대로 요금을 지불하고 지나갈 수 있다.

[10-1] 스케줄링 정책: 우선순위

1) 우선순위 스케줄링:

• 도착하는 트래픽은 분류되어, 클래스별로 큐에 저장된다.

  • 분류에는 헤더 필드의 모든 값이 사용될 수 있다.

• 버퍼링된 패킷이 있는 가장 높은 우선순위 큐에서 패킷을 전송한다.

  • 우선순위 클래스 내에서는 FCFS 방식으로 처리된다.

2) 위의 예시 설명

1. arrivals (도착) 라인:

• 패킷 1, 2, 3이 거의 동시에 도착

• 그 뒤에 패킷 4가 도착

• 마지막으로 패킷 5가 도착

1. packet in service (서비스 중인 패킷) 라인:

• 패킷들이 처리되는 순서를 보여줍니다

• 1 → 3 → 2 → 4 → 5 순서로 처리됨

• 빨간색(1,3,4)은 높은 우선순위

• 초록색(2,5)은 낮은 우선순위

1. departures (출발) 라인:

• 패킷들이 시스템을 떠나는 순서를 보여줌

• 처리된 순서와 동일: 1 → 3 → 2 → 4 → 5

이 예시는 우선순위 스케줄링의 작동 방식을 보여준다.

• 높은 우선순위(빨간색) 패킷이 먼저 처리됨

• 같은 우선순위 내에서는 선입선출(FCFS) 방식 적용

• 낮은 우선순위(초록색) 패킷은 높은 우선순위 패킷이 모두 처리된 후에만 처리됨

[10-2] 스케줄링 정책: 라운드 로빈

1) 라운드 로빈(RR) 스케줄링:

• 도착하는 트래픽은 분류되어 클래스별로 큐에 저장된다.

  • 분류에는 헤더 필드의 모든 값이 사용될 수 있다.

• 서버는 주기적으로 각 클래스 큐를 반복적으로 스캔하며, 각 클래스에서 하나의 전체 패킷을 전송한다(해당 패킷이 있을 경우).

• 빨간색 큐, 초록색 큐, 파란색 큐

2) 가중치 공정 큐잉 (WFQ):

• 일반화된 라운드 로빈

• 각 클래스 ( i )는 가중치 ( w_i )를 가지며, 각 사이클에서 해당 클래스는 가중된 서비스 양을 받는다:

  • $\frac {w_i} {\Sigma_j}{w_j}$

• 최소 대역폭 보장 (트래픽 클래스별)