[CN] 4장: What’s inside a router (input, output, buffer 관리, 스케줄링)

What’s inside a router (input, output, buffer 관리, 스케줄링)

라우터 구조 개요

일반 라우터 구조 개요

• 입력 포트
  • 라인종단 + 링크 계층 프로토콜 + 데이터그램 큐잉
• 스위치
  • 입력포트/출력포트 연결
  • 스위칭 속도: 입력 → 출력 속도 조절
    N개 입력포트 = 속도는 N * R
  • 메모리/공유버스/상호연결네트워크 종류 3가지
• 출력 포트
  • 데이터그램 큐잉 + 링크 계층 프로토콜 + 라인종단

입력 포트

라인종단 - 물리계층

링크 계층 프로토콜 - 링크 계층 (데이터 링크 처리)

‘검색’, 전달, 큐잉 - 데이터그램이 분산되어 있음

헤더필드의 값으로 출력 포트를 조회함

입력링크에 들어온 속도로 출력 해주는 것이 목표

입력포트 큐잉: 데이터그램이 스위치 구조로 전달되는 속도보다 빨리 도착하는 경우

목적지 기반 포워딩

: 목적지 IP 주소만을 기준으로 전달

일반화된 포워딩

: 헤더 필드 값들의 집합을 기준으로 전달

목적지 기반 포워딩 & 최장 프리픽스

목적지 IP 주소만을 기준으로 전달
포워딩 테이블에 IP 주소 범위가 정해져있음

그러나 범위가 위와같이 잘 나누어지지 않았다면 ?

→ ‘최장 프리픽스 매칭’

최장 프리픽스 매칭

포워딩 테이블의 항목을 찾을 때,
대상 주소와 일치하는 가장 긴 주소 프리픽스(접두사)를 가진 항목과 매칭

문제

Q1) 11001000 00010111 00010110 10100001 = 0번 링크 인터페이스에 연결

Q2) 11001000 00010111 00011000 10101010 = 1번 프리픽스에 연결

스위치 구조

입력 포트에서 적절한 출력 링크로 패킷 전달/전송

스위칭 속도

스위칭 속도 = 입력 → 출력 속도

입력 포트가 N개라면, 스위칭 속도는 라인 속도의 N배 이상이 되어야 함

메모리를 통한 스위칭 구조

초기 라우터의 동작 방식
CPU를 직접 제어해서 입력과 출력 사이에서 패킷을 스위칭

• 메모리 대역폭에 의해 스위칭 속도가 제한됨
• 데이터그램이 시스템 버스를 2번씩 사용함
• 입력 포트에 도착한 패킷을 시스템 메모리에 복사

버스를 통한 스위칭

라우팅 프로세스의 개입 없이 공유 버스를 통해
입력포트 메모리에서 출력포트 메모리로 직접 데이터그램을 스위칭

• 버스 경쟁 - 버스 대역폭에 의해 스위칭 속도가 제한됨
• 소규모 기관 네트워크

상호연결 네트워크를 통한 스위칭

• 크로스바 스위치 - 멀티 프로세서 컴퓨터 구조에서 사용
• 
• 다단계 스위치 - 여러 단계의 소형 n*n 스위치
• 병렬 처리에 활용
  • 스위치 구조 진입 시, 데이터그램을 고정 길이의 청크들로 분해
  • 출력 포트는 원래 데이터그램으로 재조립

다중 스위치 구조를 병렬로 실행하여 라우터의 스위칭 용량을 확장

→ 속도향상, 병렬처리를 통한 확장

입력/출력 포트 큐잉

입력포트 큐잉

스위칭 속도가 입력포트보다 느리면
입력 포트의 버퍼에서 큐잉 발생
입력포트 버퍼의 오버플로우로 인해 큐잉 지연과 패킷 손실 발생가능

HOL 블로킹

: 앞에서 대기중인 패킷 때문에, 뒤에 있는 패킷이 출력포트로 스위칭될 수 없음

출력포트 큐잉

스위치 구조에서 패킷이
출력 포트의 링크 전송 속도보다 빠르다면,
버퍼링이 필요함

출력 포트 버퍼의 오버플로우로 큐잉지연/패킷손실 가능

버퍼관리 & 스케줄링 정책

버퍼관리

버퍼링이 클수록, 패킷 손실률은 감소함
그러나, 버퍼링이 너무 많다면 지연이 증가함

1. 드롭 정책
   • Tail Drop = 도착한 패킷을 드롭
   • 우선순위 = 우선순위에 따라 패킷을 드롭
   • Random = 랜덤하게 패킷을 드롭
2. 사용 가능한 버퍼가 없다면, 뭐부터 삭제 ?
3. 패킷 스케줄러
4. 우선 전송할 패킷, 삭제할 패킷을 선택
   이 때는 네트워크 중립성 문제 생각해야 함
5. 버퍼 관리
   • Drop: 새로운 패킷이 도착했지만, 버퍼가 꽉차있다면
     어떤 버퍼를 버릴 것인가 ?
   • Marking: 패킷에 혼잡 발생을 표시 (ECN)

스케줄링

FCFS

우선순위

라운드 로빈

가중 공정 큐잉

FCFS (First Come, First Served)

출력 포트에 도착한 순서대로 패킷 전송

우선순위 스케줄링 (Priority)

도착한 패킷을 분류하여, 우선순위 별로 버퍼링
-> 모든 헤더필드들이 분류에 사용될 수 있음

같은 우선순위에서는 FCFS로 동작

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

도착한 패킷을 분류하여, 클래스 별로 버퍼링
-> 모든 헤더 필드들이 분류에 사용될 수 있음 (우선순위와 동일)

주기적으로 버퍼를 검사하며 각 클래스 별로 하나씩 전송

가중 공정 큐잉 스케줄링 (WFQ, Weighted Fair Queueing)

일반화된 라운드 로빈
각 클래스 i는 가중치 Wi를 할당 받고,
각 주기에서 가중치 만큼 서비스 시간을 할당받음

트래픽 클래스 당 최소 대역폭 보장

만약 가중치가 10이 있다면,

빨강 5, 초록 3, 파랑 2

와 같이 분배해서 클래스 당 최소 대역폭 보장