[Network] Network Layer:The Data Plane - What's Inside a Router

 

router 는 Input ports, Switching fabric, Output ports, Routing processor 로 구성된다. 

 

Input port

Line termination 과 Data link processing 은 input link 에 대해 physical layer 과 link layer 를 구현한 것이다. 각각 전기신호를 받아 frame 으로 만들어 주고, frame 을 packet 으로 만드는 역할을 한다. input port 에서 수행되는 lookup 이 router 의 핵심 동작이다. router 는 forwarding table 을 사용하여 도착한 packet 이 swtiching fabric 을 통해 어떤 output port 로 나갈지 찾는다. forwarding table 은 routing processor 를 통해 계산/수정 되거나 remote SDN controller 를 통해 받는다.

fowarding 의 방법에는 destination-based forwarding 과 generalized forwarding 이 있다. destination-based forwarding 은 destionation IP address 를 통해 packet 을 forwarding 하고 generalized forwarding 은 header field values 를 통해 forwarding 한다. generalized forwarding 은 추후에 다루기로 한다.

 

모든 destionation address 를 사용해 만든 forwarding table 은 IP address 의 갯수에 비례한 크기를 가지므로 크기나 너무 커지는 문제를 가진다. prefix 를 사용한 forwarding table 을 사용하면, router 는 packet 의 destionation address 의 prefix 를 matching 하므로 forwarding table 의 크기가 너무 커지는 현상을 막을 수 있다. 만약 destionation address 가 여러 개의 prefix 와 match 한다면 router 는 longest prefix matching rule 을 사용한다. destination addres 와 match 하는 prefix 들 중 가장 긴 prefix 의 link interface 를 선택하는 것이다.

예를 들어, 32-bit IP address '11001000 00010111 00011000 10101010' 의 경우 두 번째와 세 번째 prefix 를 모두 만족한다. 세 번째 prefix 가 더 길기 때문에 해당 packet 은 interface 2 로 forward 한다. 

 

lookup 을 통해 packet 의 output port 가 정해지면, packet 은 switching fabric 을 전달된다. packet 은 때때로 switching fabric 에 들어가는 데 막히는데, 이때 packet 은 input port 에서 queue 되고 나중에 fabric 을 지나도록 schedule 된다. 

 

참고로, Input port 가 destionation IP address 를 look up 하여(match) 특정 output port 를 향해 switching fabric 으로 packet 을 전달하는 것(action) 은 networked devices 에서 수행되는 "match plus action" abstraction 의 특별한 예이다.  

 

Switching fabric

switching fabric 은 router 의 중심으로, packet 들을 input port 에서 output port 로 forward/swtich 한다. switching fabric 에는 세 가지 종류가 있다.

• Switching via memory : 초창기의 router 는 전통적인 컴퓨터로, CPU 의 직접적인 통제 아래에 switching 을 했다. packet 은 system 의 memory 로 복사되며 memory bandwidth 에 의해 속도가 제한된다.
• Switching via a bus : input port 는 single, shared bus 를 통해 output port 로 직접 packet 을 전달한다. switching speed 는 bus bandwidth 에 의해 제한된다. 
• Switching via an interconnection network : single, shared bus 의 bandwidth limitation 을 극복하기 위한 방법으로 보다 정교한 interconnection network 를 사용한다. crossbar switch 는 2N 개의 buse 들로 만들어진 interconnection switch 로, N input ports 와 N output ports 를 연결해 만든 것이다. 

 

Output port

output port 에서는 output port memory 에 저장된 packets 을 가져와 output link 로 보낸다. 

 

input port 와 output port 에서 packet queue 가 생길 수 있다. queue 가 커지면 router 의 memory 가 초과되어 도착한 packet 을 저장할 수 없는 packet loss 가 발생한다. 이전에 packet 들이 network 에서 lost 되거나 router 에서 drop 된다고 했었는데, router 내의 queue 에서 이러한 일들이 발생한다. 

 

Input Queueing

switch fabric 이 충분히 빠르지 않다면, packet 은 input port queues 에서 switching fabric 을 통해 output port 로 가는 자신의 차례를 기다려야 한다. 따라서 input port 에서 packet queuing 이 발생할 수 있다. 

예를 들어, 두 input queues 의 앞에 있는 두 packet 이 같은 ouput queue 을 선택한다고 하자. switching fabric 은 한번에 하나의 outport 로 하나의 packet 만을 전송할 수 있으므로,  다른 한 packet 은 block 되고 input queue 에서 기다려야 한다.  input queue 에 있는 queued packet 이 outport 가 비었음에도, 앞에 있는 다른 packet 에 의해 block 되었기 때문에 앞의 packet 이 fabric 을 통해 이동하는 것을 기다려야 한다. 이러한 현상을 HOL(head-of-line) blocking 이라고 한다. 

 

Output Queueing

하나의 output port 로 여러 개의 packet 이 도착할 수 있다. 이때, switch 를 통한 arrival rate 가 output port 의 처리율, output line speed, 를 초과하게 되면 output port 에서 packet queuing 이 발생할 수 있다. 이때, incoming packet 을 buffer 할 memory 가 충분하지 않다면, 도착한 packet 을 drop 하거나 새로 도착한 packet 을 위한 공간을 만들기 위해 하나 이상의 already-queued packet 을 제거한다 

output port 로 packet 들이 도착해 queue 되면, queue 에 있는 packet 중 하나는 outgoint link 로 전달된다. queue 에 있는 packet 을 고르기 위해 packet scheduler 가 사용된다. 

 

Packet Scheduling

queued packets 을 outgoing link 로 보내기 위한 순서를 정하기 위한 여러가지 방법이 존재한다.

First-in-First-Out (FIFO)

queue 에 도착한 순서대로 packet 을 보낸다. 만약 arriving pakcet 을 보관할 buffing 공간이 충분하지 않다면, 즉 queue 가 가득찬 상왛이면 discard policy 를 통해 arriving packet 위한 공간을 만들기 위해 queue 에 있는 packet 을 제거한다.

• tail drop : arriving packet 을 drop 한다. 
• priority : priority basis 를 통해 packet 을 drop/remove 한다.
• random : 랜덤하게 packet 을 drop/remove 한다.

참고로 ramdom 의 rate 변화율이 tail drop 보다 더  양호하기 때문에, random 이 tail drop 보다 우수하다.

 

Priority Queuing

packets 을 우선순위에 따라 multiple class 로 분류한 후, 높은 우선순위의 queued packet 을 먼저 보낸다. 실제로, packet 은 network management information 을 가지고 있는데, user traffic 에 따라 priority 를 부여한다. 그 예로, real-time voice-over-IP packet 은 SMTP 나 IMAP e-mail packet 같은 non-real traffic 보더 높은 우선순위를 가진다.

 

Round Robin

packet 은 priority queuing 처럼 mulitple class 로 분류되어 정렬되지만, class 를 돌아가며 packet 을 보낸다. 

 

Weighted Fair Queuing (WFQ)

WFQ 는 일반화된 형태의 round robin 이다. packet 은 적절한 class 로 분류되고 queue 된다. Round Robin 과 유사하지만, WFQ 에서는 각각의 class 가 매 cycle 마다 가중치를 받아 다른 양의 서비스 시간을 부여받는다. .

 

Routing processor

router 의 control plane functions 는 보통 software 로 구현되고 routing processor 에서 실행된다. traditional router 에서는, routing protocol 을 실행하고, routing tables 와 attached link state information 을 유지하며, router 를 위해 forwarding table 을 계산한다. SDN router 에서는, remote controller 에 의해 계산된 forwarding table entries 를 받고 entries 를 router 의 input 에 설치하기 위해 remote controller와 통신할 책임이 있다.

 

 

 

 

참조
Computer Networking _ A Top Down Approach, 7th, converted