[네트워크] 4.2 라우터 내부에는 무엇이 있을까?

Router

Router

네트워크 계층에서 host와 router가 있다. 그 중 router에 대해 알아보자.

 

▶ Control plane: control message를 routing한다. (end-end-path through network)

▶ Data plane: user message를 forwarding한다. (local forwarding)'

 

Cf) Host는 router와 달리, control plane을 필요로하지 않는다.

: host --> gateway router로 바로 연결되기 때문이다.

 

Router

1. Control plane에서: routing protocol --> routing algorithm --> routing table
2. Data plane에서: forwarding table --> input port에서 switching fabric을 거쳐 output port로 forwarding된다.

 

Router Architecture Overview

Router Architecture Overview

▶ Input port

- Physical-layer 기능: input port의 맨 왼쪽 박스와 output port의 맨 오른쪽 박스는 라우터로 들어오는 입력 링크로, 물리 계층 기능을 수행한다.

- Link-layer 기능: input port는 들어오는 링크의 반대편에 있는 link-layer과 상호운용하기 위해 필요한 link-layer 기능을 수행한다.

- Input port --> Output port: input port에서는 forwarding table을 참조하여, 도착된 패킷이 switching fabric을 통해 도달할 output port를 결정한다.

• Routing processor: forwarding table을 계산하고, input port로 전달한다. (Control plane 기능)
  - traditional router: 하나의 router 내에서, control plane에서 forwarding table을 만들어서 data plane으로 내려보낸다.
  - SDN: control plane의 역할은 remote controller에서 수행하고, 계산된 forwarding table을 각각의 router들로 내려보낸다.

 

▶ Switching fabric

: Router의 input port와 output port를 연결한다.

 

▶ Output port

: Switching fabric에서 수신된 패킷을 저장하고, 필요한 link layer, physical layer 기능을 수행하여 output link로 패킷을 전송한다.

 

 

4.2.1 Input Port 처리

Input Port Functions

Input Port Functions

• Physical layer
• Link layer
• Network layer: forwarding, queueing

▶ Forwarding

: Forwarding table을 이용하여, 도착 패킷이 switching fabric을 통해 전달될 output port를 검색한다.

이때 forwarding table은 routing processor에서 계산되거나(traditional), 원격 SDN 컨트롤러에서 수신(SDN)된다.

• 전통적인 control plane: Desination-based forwarding
• SDN control plane: Generalized forwarding

Cf) "match + action"

• 전통적인 control plane: 헤더의 목적지 주소와 forwarding 엔트리(match) --> Forwarding(action)
• SDN: Generalized(match) --> Forwarding(action)

 

▶ Queueing

: Link layer에서 들어오는 속도 > Swtiching fabric에서 나가는 속도 --> Queueing

 

 

4.2.2 Switching

Switching Fabrics

Switching Fabrics

▷ Switching rate

: switching rate가 느리면, input port buffer에 패킷이 늘어난다.

• 이상적인 상태: N개의 input이 들어왔을 때, switching fabric의 switching rate가 NR (input port buffer가 필요없는 상태)

 

Switching via Interconnection Network

Switching via Interconnection Network

Switching에는 memory, bus, 그리고 3x3 corssbar 등 여러 방식이 있다. 하나하나 자세히 살펴보자.

 

▶ memory

: Input port에서 패킷이 들어오면, 운영체제 인터럽트를 통해 그 패킷이 메모리 Bus에 탑승한다. 이후, memory에서 forwarding table을 확인한 후, 다시 Bus에 탑승한다.

--> 따라서 Bus에는 2번 타게 되고, switching speed == 메모리 Bus speed/2가 된다.

 

▶ bus

: Input port에서 패킷이 들어오면, 그 패킷은 전용 Bus에 탄다. 따라서 이 때는 memory가 필요하지 않다.

--> Bus에 1번 타게 되고, switching speed는 메모리 Bus speed와 같다.

 

그러나 memory와 bus 방식 switching의 공통점은, Bus에는 1명만 탈 수 있다는 것이다.

따라서 이에 대한 해결책으로 제시된 것이 interconnection network의 (3x3 crossbar) 방식이다.

 

▶ interconnection Network (3x3 crossbar)

: 3x3 crossbar에는 Bus가 input/output port 개수만큼 존재한다. 따라서 Bus에는 여러 패킷이 탑승할 수 있게 된다.

 

하지만 이러한 3x3 crossbar에도 문제가 있는데, 문제는 바로 패킷의 output port(목적지 포트)가 같다면, 동시에 나갈 수 없다는 것이다.

그리고 이러한 3x3 crossbar의 한계를 극복하기 위해 제시된 것이 바로 multistage switch이다.

 

▶ multistage switch

multistage switch

multistage switch는 동시에 같은 output port로 나갈 수 없다는 crossbar 방식의 단점을 극복하여, 다른 input port에서 들어온 패킷이 동시에 같은 output port로 나갈 수 있도록 하였다. 

또, 병렬성을 이용하여 속도를 높이는 기능도 추가하였다. 3-stage로 구성된 하나의 plane 8개를 연결하여 basic unit을 8-switching plane으로 하여, 패킷을 plane 개수만큼 나누도록 하여 전송 속도를 8배로 증가시켰다.

 

 

Input Port Queueing & Head-of-Line (HOL) Blocking

Input Port Queueing & Head-of-Line (HOL) Blocking

앞서 살펴본 switching의 여러 가지 방법들 중, crossbar 방식의 문제점에 대해 자세히 살펴보자. 

 

Crossbar 방식의 문제는 서로 다른 input port에서 들어온 패킷이, 같은 output port로 동시에 나갈 수 없다는 것이다. 

그런데 이러한 문제로 인해 새로운 문제가 생기는데, 바로 'HOL blocking'이다.

 

▶ HOL blocking

HOL(Head of Line) blocking이란, 하나의 input port의 buffer에서, 앞에 있는 패킷때문에, 그 패킷이 없었더라면 output port로 나갈 수 있었던 패킷이 나가지 못하게 되는 현상을 말한다.

Crossbar 방식에서는 HOL blocking에 의해서만 queueing이 발생한다. 그리고 이러한 queueing이 발생하면, 패킷의 대기 시간이 길어지고, 더 나아가 drop이 발생하게 될 수 있다.

 

 

지금까지 공부한 내용 중 중요한 것은, 각 switching fabric에서 queueing이 발생하는 이유에 대해 정확히 이해하는 것이다!

• memory, bus: Bus를 통해서는 한 번에 한 개의 패킷만이 이동할 수 있기 때문에 queueing이 발생한다.
• crossbar: 한 번에 여러 개의 패킷이 이동할 수 있지만, 같은 output port로는 하나의 패킷만이 나갈 수 있기 때문에, HOL blocking이 발생한다.
• multistage switch: crossbar의 단점을 극복하여, 한 번에 여러 개의 패킷이 같은 output port로 나갈 수 있도록 하였다. 이와 더불어, 병렬성을 이용해 switching 속도를 높였다.

 

 

4.2.3 Output Port 처리

Output Port Queueing

Output Port Queueing

자, 이제 지금까지 input port와 switching fabric에 대해 살펴보았다. 이제부터 output port의 queing에 대해 생각해보자.

 

위에 제시된 그림에서와 같이, input port의 queueing은 switching fabric의 속도를 증가시킴으로서 해소될 수 있다. 즉, switching fabric에서 패킷이 빠져나가는 속도를 input port에 패킷이 도착하는 속도만큼 빠르게 하면 (이상적인 속도: NR), input port에서는 queueing이 발생하지 않게 된다.

 

하지만 output port는 다르다. Switching fabric의 corssbar 방식에서의 문제를 해결하여 하나의 서로 다른 input port에서의 패킷을 같은 output port로 전송한다면, output port에는 필연적으로 패킷이 쌓이고, 따라서 queueing이 발생하게 된다. 

즉, output port에서의 queueing을 완전히 막는 것은 불가능하다.

 

Output Port Functions

Output Port Functions

그렇다면 어떻게 해야 할까? Output port에서의 queueing을 잘 다룰 필요가 있다.

이를 위해 output port에 있는 기능은 두 가지가 있는데, 바로 Drop policy와 Scheduling disipline이다.

 

▶ Drop policy

: Drop policy란, buffer에 쌓인 패킷들 중, 어떤 패킷을 drop할 지 결정하는 방법을 말한다.

 

▶ Scheduling disipline

: Scheduling disipline이란, buffer에 쌓인 패킷들 중, 어떤 패킷을 내보낼 것인지 결정하는 방법을 말한다. 뒤에서 4가지 방법을 살펴볼 것이다.

참고로, 이러한 scheduling disipline은 망 중립성(network neutrality)에 방해가 될 수 있다.

 

How much Buffering at Routers?

Output port의 scheduling disipline에 대해 자세히 살펴보기 전에, output port의 buffer 용량을 결정하는 방법에 대해 알아보자.

 

먼저, RFC에서 가장 먼저 설정한 방식은, "typical RTT" * C(link capacity) 이다.

하지만 TCP flow 수(N)가 많을 때, 이러한 방식에 문제가 있음을 깨달은 RFC는 다른 방식을 제안하였다. 

TCP flow 수로 (RTT * C)를 나눠주는 방식이다. 즉, TCP flow 수가 많으면, 요구되는 buffering이 줄어들게 된다.

 

Output Port Buffer Management

Output Port Buffer Management

앞서 output port에서 buffer에 패킷이 꽉 찼을 때, drop이 발생한다고 설명하였다. 하지만 사실 drop 이외에 다른 방법이 하나 더 있다.

Output port의 buffer 처리 방법에 대해 조금 더 자세히 살펴보자.

 

▶ Drop

먼저, 아까도 이야기했던 drop이다. 이는 곧, queue에 쌓이 패킷 중 하나를 버리게 되는 것을 말한다. 

Drop의 방법에는 두 가지가 있다.

• Tail drop: tail drop은 buffer가 꽉 찼을 때는, 새로 들어오는 패킷을 drop하는 방식이다.
• Priority: priority 방식은, buffer가 꽉 찼을 때 packet의 우선순위를 판단하여, 우선순위가 낮은 패킷을 drop하는 방식이다.

 

▶ Marking

Marking이란, active queue management 방식을 말한다. 즉, 패킷을 drop하게 되는 최악의 상황이 되기 전에 조치를 취하는 것이다.

Marking에는 여러가지 방법이 있지만, 두 가지를 소개하도록 하겠다.

• ECN: Transport 계층과 Network 계층이 협력하여, buffer에서 drop이 발생하기 전에, 미리미리 output port로의 전송 속도를 줄이는 방법이다.
• RED(Random Early detection): 이름에서와 같이, 모든 패킷을 drop해야 하는 최악의 상황이 발생하기 전에, 미리미리 패킷을 random하게 drop하는 방식이다.

 

 

4.2.5 Packet Scheduling

자, 이제 드디어! Output port에서의 packet scheduling 방법에 대해 알아보자.

 

1) FIFO

1) FIFO

먼저 FIFO 방식이다. 이름과 같이 First In First Out, 가장 먼저 들어온 것이 가장 먼저 나가게 된다.

 

2) Priority scheduling

2) Priority scheduling

다음으로, priority scheduling 방식이다. 우선순위에 따라, 패킷을 서로 다른 queue에 넣는다.

1. 높은 우선순위 큐에 있는 패킷 먼저 내보낸다.
2. 하나의 큐 내에서는 FIFO 방식이다.

 

3) Round robin

3) Round robin

세 번째, round robin 방식이다. 큐를 여러 개로 나눈다는 점에서는 priority 방식과 동일하다.

하지만 round robin 방식에서는 각 큐끼리는 fair하게 동작한다. 즉, 1 cycle 당 각 큐별로 패킷을 하나씩 내보내는 것이다.

 

4) Weighted fair queueing (WFQ)

4) Weighted fair queueing (WFQ)

마지막으로, WFQ 방식이다. 이는 round robin 방식과 매우 유사하지만, 각 큐마다 서로 다른 weight가 할당되어 있다는 차이가 있다. 즉, 큐끼리의 약간의(?) 우선순위가 존재한다고 생각하면 되겠다.

이러한 WFQ 방식은 traffic class별로 minimum bandwidth를 보장해야 할 때 주로 사용하게 된다.

 

 

실전원리: 망 중립성 (Network Neutrality)

실전원리: 망 중립성 (Network Neutrality)

망 중립성이란, "인터넷 데이터를 차별하지 마라!" 라는 법적 제약이다.

 

 

 

 

 

출처: 이화여자대학교 이미정교수님 컴퓨터네트워크