라우터의 구조에 대해 자세히 알아보자

그림에서 가장 작은 박스들은 Router의 입력 링크로, 물리 계층 기능을 수행한다.

• Input port

  • Middle box: 들어오는 링크의 반대편에 있는 링크 계층과 상호 작용하기 위해 필요한 Link layer 기능을 수행한다.
  • 가장 오른쪽의 박스: Forwarding table을 참조하여 도착한 패킷이 스위치 구조를 통해 Router Output port를 결정한다.

• Switch structure: Router의 Input port와 Output port를 연결한다.

• Output port: Switch structure에서 수신한 패킷을 저장하고 필요한 링크 계층 및 물리 계층 기능을 수행하여 출력 링크로 패킷을 전송한다.

  • 링크가 양방향인 경우, 출력 포트는 일반적으로 동일한 링크의 입력 포트와 한 쌍을 이룬다.

• Routing processor: Control Plane의 기능을 수행한다.

Forwarding

1. 목적지 기반 포워딩 (Destination-Based Forwarding)

• 패킷의 목적지 주소를 기반으로 경로를 결정하여 해당 목적지로 전송하는 방식.

2. 일반화된 포워딩 (Generalized Forwarding)

• 패킷의 다양한 헤더 필드(예: 소스, 목적지, 프로토콜 등)를 분석하여 포워딩 규칙에 따라 전송하는 유연한 방식.

A) Input port process & Destination-Based Transmission

• "검색"에서는 Forwarding table을 사용하여 도착 패킷이 Switch structure를 통해 전달되는 Output port를 검색한다.
• Forwarding table은 Routing processor에서 계산되거나 Remote SDN Control에서 수신된다.

Forwarding 처리

가장 간단한 예시로 출력 포트가 각 패킷의 Destination address를 기반으로 하는 경우를 생각해보자

모든 주소에 대해 하나의 Entry를 설정하는 것은 무리이다.

방법 1: 범위 사용

방법 2: Prefix 사용

• 여러 개의 Prefix에 매칭 되는 경우에는 Longest prefix matching rule을 사용하여 가장 긴 match entry로 패킷을 전송한다.

Forwarding 처리 이후, 패킷은 Switch structure로 보내져야한다.

• 이때, Switch structure가 다른 패킷에 의해 사용 중이라면, 패킷이 Switch structure에 들어가는 것을 일시적으로 차단할 수 있다.

Input port에서 검색과 (match) Output port로 전송(action)하는 것은 Network 장치들에서 흔히 수행되는 match plus action의 한 예시이다.

B) Switching

Switch structure는 패킷이 Input port에서 Output port로 실제로 Switching 되는 구조를 가진다.

아래 그림과 같이 여러 가지 Switching 방법이 존재한다.

1. Memory를 통한 교환

a. 패킷이 도착하면 Input port는 Routing processor에게 interrupt를 보내 패킷을 Processor memory에 복사한다.

b. Routing processor는 Header에서 목적지 주소를 추출하고 Forwarding table에서 적절한 Output port를 찾은 다음 패킷을 Output port의 buffer에 복사한다.

• Memory가 읽고, 쓰는 작업은 서로 다른 작업이기 때문에 동시에 할 수 없다. 따라서 Memory의 최대 대역폭이 B라면, 전체 전달 처리량은 B/2보다 작아야한다.

2. Bus를 통한 교환

Routing processor의 개입 없이 Public bus를 통해 직접 Output port로 패킷을 전송한다.

a. 입력 포트는 라우팅 프로세서의 개입 없이 직접 출력 포트로 패킷을 전송하며, 내부 레이블은 출력 포트를 나타내는 데 사용된다.

b. 모든 출력 포트에서 패킷을 수신하지만, 레이블에 맞는 포트만 패킷을 유지하고, 레이블은 출력 포트에서 제거된다.

한계점: 동시에 여러 패킷이 도착하면, 버스를 통해 한 번에 하나의 패킷만 전달되므로 다른 패킷은 대기해야 한다. 라우터의 교환 속도는 버스 속도에 의해 제한된다.

3. 상호연결 네트워크를 통한 교환

Crossbar switch: N개의 입력 포트를 N개의 출력 포트에 연결하는 2N 버스로 구성된 상호연결 네트워크다.

• 각 수직 버스는 교차점에서 각 수평 버스와 교차하며 스위치 구조 컨트롤러에 의해 언제든지 열거나 닫을 수 있다.

• 이를 통해 앞의 두가지 방식과 달리 크로스바 스위치는 여러 패킷을 병렬로 전달할 수 있다.

• 그러나 두개의 서로 다른 입력 포트에서 나오는 2개의 패킷이 동일한 출력 포트로 보내지는 경우 한번에 하나의 패킷만 특정 버스에서 전송될 수 있기 때문에 입력을 기다려야한다.

• 좀 더 정교한 상호연결 네트워크는 다단계 스위치 구조를 통해 각기 다른 입력 포트의 패킷이 동일한 출력 포트를 향해 동시에 전달할 수 있도록 여러 단계의 스위칭 요소를 사용한다.

C) Output port 처리

Output port의 memory에 저장된 패킷을 가져와서 출력 링크를 통해 전송한다.

• 이때, Scheduling, 큐 제거, 필요한 링크 / 물리 계층 전송 기능을 수행하는 것이포함된다.

D) Queueing이 발생하는 위치

Queue는 Input port와 Output port 모두에서 형성될 수 있다.

• Queue가 커지면 Router memory가 전부 다 소모되어 도착하는 패킷을 저장할 메모리가 남지 않았을 때, packet loss가 발생한다.

Router에서의 packet loss 과정

모든 패킷의 고정 길이가 같고 동기식으로 도착한다고 가정하자.
각각 N개의 입력 및 출력 라인의 전송률은: $R_{line}$ 패킷/s 이다.
$R_{switch}$: Switch structure의 전송률

1. $R_{switch} = N \cdot R_{line}$

   • Input port에서 발생하는 queuing은 무시한다.

Input Queueing

Switch structure가 충분히 빠르지 못한 경우에 해당된다.

• Input port에서 가장 위와 아래에 위치한 packet이 같은 Output port로 이동하고자 한다.
• 둘 중 하나의 Packet만 우선적으로 처리되고 나머지 하나는 대기한다.
• 중간에 위치한 packet의 경우도 이미 Switch structure가 하나의 packet에 대해 작동 중이기 때문에 대기해야한다.
• 이것을 HOL(Head-Of-the-Line) Blocking이라고 한다.

Output Queueing

$R_{switch} = N \cdot R_{line}$ 경우를 가정하자.

• N개의 Packet은 Switch structure을 거쳐 Output port로 도착한다.
• N개의 Packet이 출력 링크를 통한 Transfer queue에서 대기하는 동안, 다른 N개의 packet이 도착할 수 있다.
• 이러한 경우, $R_{switch} = N \cdot R_{line}$ 이더라도 Packet queuing이 Output port에서 발생한다.
• drop-tail: Memory가 충분하지 않을 때, 도착한 패킷을 삭제하는 정책

Q) 얼마나 많은 Buffer가 요구되는가?

packet loss를 줄이기 위해서는 각 Port에 얼마만큼의 Buffer가 요구되는가?

$B = RTT \cdot C / √N$

• Buffer가 클수록 Queuing delay도 커진다.

E) Packet scheduling

Queue에 존재하는 packet이 출력 링크를 통하여 전송되는 순서를 결정하는데 사용한다.

• 일반적으로는 FCFS (First-Come-First-Served, FIFO라고도 함) 방식이 사용된다.

FIFO (First-In-First-Out)

• 링크가 현재 다른 패킷을 전송 중이라면, queue에 도착한 패킷은 전송을 기다린다.
• Buffer 공간이 충분하지 않은 경우 Queue의 packet 폐기 정책은 패킷 손실 여부 또는 큐에서 제거할 것인지 여부를 결정한다.

FIFO Scheduling rule

• Output queue에 도착한 순서와 동일한 순서로 출력 링크에서 전송할 패킷을 선택한다.

Priority Queuing

• Packet이 도착하면 높은 우선순위와 낮은 우선순위로 분류된다.
• 높은 우선순위 클래스가 비었을 때만 낮은 우선순위 패킷이 전송된다.
• 높은 우선순위 클래스 내에서는 FIFO 방식으로 전송된다.

Priority Queuing

• Packet 1, 3, 4: 높은 우선순위
• Packet 2, 5: 낮은 우선순위

Round Robin Queuing rule

• Packet을 클래스로 분류한다.
• 클래스 간에는 엄격한 서비스 우선순위가 존재하지 않으며, Round Robin Scheduler가 클래스 간에 서비스를 번갈아서 제공한다.
• Work-Conserving Queuing: 전송 대기 중인 패킷이 있다면 다른 class로 넘어가는 것을 허용하지 않는다.

Round Robin Queuing schedule

• Class 1: 1, 2, 4
• Class 2: 3, 5
• Round Robin에 의해 Class 1과 Class 2를 번갈아가며 출력한다.

WFQ (Weighted Fair Queuing) rule

Round Robin Queuing rule의 일반화되 형태이다.

• 각 class마다 weight $w_i$ 에 따른 다른 Service time을 보장받는다.
• Service time = $w_i$ / $\displaystyle\sum w_j$
  • 여기서 분모는 모든 Weight의 합이다.
• 링크의 전송률이 R이라면 class $i$는 $R \cdot w_i$ / $\displaystyle\sum w_j$의 처리율을 가진다.