지난 정리글에서는 Network Layer의 전반적인 내용을 살펴봤다. 그 중, network layer의 주요 기능인 forwarding과 routing에 대해서도 간략히 정리했는데, 이번 글에서는 그 forwarding과 routing에서 중요한 역할을 하는 router, 라우터에 대해서 정리해보려고 한다.
1. Router Architecture
먼저 라우터의 기본 architecture 부터 다음 그림을 통해 살펴보자.
라우터도 기본적인 계산을 진행하기 때문에 컴퓨터의 일종이다. 라우터 내부에는 OS도 있고, 컴퓨터에 있는 것처럼 여러 board들도 존재한다.
위 그림을 보면, Routing processor와 High-speed switching fabric이 나뉘어져 있는 것을 알 수 있다. 각각을 설명하면,
- Routing processor : router의 S/W 부분으로, routing 역할을 담당하며 control plane에 해당한다.
- High-speed switching fabric : router의 H/W 부분으로, forwarding 역할을 담당하며 data plane에 해당한다.
이전 글에서 언급했듯이 forwarding table은 routing algorithm 결과를 반영해 작성한다. 그러기 위해서는 router 내부에서 routing processor와 high-speed switching fabric이 서로 소통을 해야하는데, 이 사이에 인터페이스를 통해 소통이 진행된다. 이 인터페이스 자체가 컴퓨터라고 할 수 있으며, router가 컴퓨터로 여겨지는 이유 중 하나이다.
+) router의 성능은 forwarding을 얼마나 빨리 진행할 수 있는지에 따라 결정된다.
2. Input Port
router는 여러 link가 연결되어 있다. 따라서 input link, output link가 따로 정해져 있지는 않다. datagram이 들어오는 부분을 input port, 나가는 부분을 output port라고 부른다.
이제부터 Input port에서 어떤 일이 일어나는지 한 번 알아보려고 한다. Input port는 다음 그림과 같이 구성된다.
Input prot의 구성 요소에 대해서 설명하면,
- line termination : 1계층인 physical layer이다.
- link layer protocol : 2계층인 link layer의 프로토콜이 존재한다. 보통 Ethernet이다. 이 프로토콜은 2계층의 주소를 보고 올바른 router에 왔는지 확인하고 다음 단계로 전해주는 역할을 한다.
- lookup,forwarding,queueing : decentralized switching
- 3계층이 여기에 해당한다. IP 패킷의 헤더를 보고 목적지를 결정하고 output port로 forwarding 하는 역할을 한다.
- 목표 : line speed(패킷이 경로를 따라 들어오는 속도)에 맞춰 패킷 처리해 queue에 최대한 안쌓이게 하기
- Forwarding하는 속도에 비해 들어오는 속도가 빠를 때, queue에 패킷들이 쌓인다.
- destination-based forwarding : 오직 목적지 IP주소를 통해 fowrard하는 방식(전통적인 방식)
- generalized forwarding : 목적지 주소 뿐 아니라 다른 주소도 확인하며 forwarding하는 방식
2.1 Destination-based forwarding
이제부터, forwarding하는 방법들과 순서들에 대해서 알아볼 것이다. 먼저, 전통적인 방식인 Destination-based fowarding부터 알아보려고 한다.
이 방식에서는 각 port마다 forwarding table이 주어져 있다. 따라서 만약, 목적지 주소의 범위가 11001000 00010111 00010000 00000000 ~ 11001000 00010111 00010111 11111111 사이에 존재한다면 0번 포트로 나가야 하는 것을 input port에서 판단하는 것이다.
그런데 이때, 범위가 겹치는 경우가 생긴다. 다음 예시를 한 번 살펴보자.
후에 다룰 내용이지만, address는 크게 host 부분과 subnet 부분으로 나뉘는데, 같은 네트워크를 쓰고 있는 컴퓨터 1,2는 동일한 host 주소를 가져 위와 같이 겹치는 상황이 발생한다.
그렇다면, 이럴 때는 어떻게 해결해야 할까? 바로 longest prefix matching 방법을 이용하는 것이다. 즉 가장 길게 매치되는 주소에 해당하는 포트로 내보내는 것이다.
위의 그림에서 첫번째 주소는 0번에 해당하는 주소랑 일치한다. 그렇지만, 2번째 들어온 주소는 1번과 2번 모두와 일치한다. 이럴 때는 1번에 해당하는 주소와 가장 길게 매칭되기 때문에 1번으로 내보내게 된다.
이 longest prefix matching을 사용하는 이유는 무엇일까? 당연히 길게 매칭되는 곳이 해당 주소에 더 가까울 것이라고 판단하기 때문이다.
이 longest prefix matching 방식은 모든 라우터마다 구현되어 있고, 이 매칭하는 속도를 얼마나 빠르게 하느냐에 따라 라우터의 성능이 결정된다. 따라서 Cisco와 같은 router를 최초로 발명한 회사들은 이 속도를 줄이기 위해 여러 최적화 알고리즘을 적용하고 있다.
현재 가장 일반적인 방식 중 하나는 이진탐색(binary search) 기반 포워딩 테이블 탐색이며, 시간복잡도는 O(log N)이다.
+) 이보다 더 빠른 CAM이 등장했는데, 이는 목적지 IP address와 테이블에 저장된 모든 항목을 동시 비교한다. 이는 하드웨어에서 병렬로 수행하기 때문에, table size와 상관없이 one clock cycle 내에 다 비교가 가능하다고 한다.(고성능 라우터나 백본 라우터에서만 주로 사용)
2.2 Switching fabrics
switching fabric은 패킷을 input link에서 적절한 output link로 옮기는 역할을 한다. 라우터의 구조에서 H/W를 담당하는 부분의 중심에 있던 친구이다. 다음 그림을 살펴보자.
즉, router 내부에서 input link로부터 output link로 패킷을 옮기는 역할을 하는데 이는 switching 역할을 하는 것과 같다. 이와 같은 이유 때문에 router도 switch의 일종이라고 불리는 것이다.
여기서도 router의 성능 측정에 영향을 미치는 것이 있는데 바로, switching rate이다. switching rate는 초당 몇개의 패킷이 switching fabric을 통해 이동할 수 있는지를 나타낸다. . 즉, N개의 input port가 있고 패킷이 들어오는 비율이 R로 일정할 때, 단위시간 당 N*R만큼 처리하는 것이 가장 이상적이다.
이때, fabric을 구현하는 방법이 memory, bus, interconnection network 이렇게 3가지 존재하는데 각각 어떻게 처리되는지 알아보자.
2.2.1 Memory
먼저 memeory 방식으로 구현된 switching fabric을 살펴보자.
- 왼쪽의 초록색 패킷이 input port로 들어오고,
- input port가 어느 output port 나갈지 forwarding table을 참조하여 판단한 뒤,
- switching fabric을 통해 시스템의 memeory로 이동한다.
- 이때 메모리가 패킷을 복사하는 memcpy가 일어나고, 해당 패킷을 복사한다.
- 이 복사한 패킷이 적절한 ouput으로 이동한다.
- 이때, 복사된 패킷은 memory에 일시적으로 저장된다.
이 방식은 1세대 라우터에서 사용되었으며, 구현이 단순하다는 장점이 있지만 단점도 존재한다. 전송 속도가 메모리 대역폭에 의해 제한된다. 따라서 빠른 처리를 위해 더 빠른 fabric switching 방법이 등장했다.
2.2.2 Bus
다음은 bus 방식으로 구현된 switching fabric이다.
패킷이 input port로 들어오면 가운데에 shared bus로 구현된 switching fabric을 통해 oupt port로 이동한다. 즉, 하나의 shared bus를 여러 포트가 공유하는 방식이다.
하나의 shared bus를 여러 포트가 공유하다 보니, 동시에 여러 포트가 bus에 접근하려고 하면 bus contention(버스 경쟁)현상이 발생할 수 있다.
이를 해결하기 위한 방법이 bus arbitration인데, port마다 고정된 우선순위를 정하거나 우선순위를 번갈아가며 바꾸는 등등의 알고리즘으로 구현된다. 이와 같은 알고리즘 방식과 bus의 대역폭(bandwidth)에 따라 switching 속도도 제한을 받는다.
2.2.3 Interconnection Network
다음은 switching fabric 내에 네트워크 자체를 구현한 방식이다.
사실 Interconnection network는 multi-processor 시스템에서 여러 프로세서 간의 통신을 연결하기 위해 개발되었다. 이 구조는 고속의 병렬 처리 능력을 갖추고 있어서 고성능 라우터의 switching fabric에서도 활용되기 시작했다.
대표적 구조로 Crossbar와 Clos networks 구조가 있다. 이 구조들은 여러 개의 작은 스위치들을 조합해 nxn 크기의 switching fabric을 만든다.
위 그림은 8x8의 multistage switch를 나타낸 것이다.
- 총 8개의 입력 포트와 8개의 출력 포트를 갖고 있으며,
- 구조적으로는 2×4×2 형식으로 구성된 3단계 multistage 구조이다.
- 초록색 패킷이 입력되면, 이를 더 작은 단위인 cell로 분할하여 switching fabric에 투입된다.
- 각각의 셀은 병렬적으로 여러 경로를 통해 전송되고,
- 마지막 출력 단계에서 다시 원래의 패킷으로 재조립된다.
이 방식은 병렬성을 이용하여 다수의 input, ouput 포트가 동시에 데이터를 전송할 수 있게 만들었고, bus나 memory 방식에 비해 훨씬 높은 throughput을 제공한다.
위 그림은 라우터의 성능을 더 높이기 위해 switching fabric을 평면으로 여러 겹을 쌓아 구현하기도 한다. 이렇게 되면, 수많은 input 포트와 output 포트가 동시에 다수의 plane을 활용해 병렬로 패킷을 전송할 수 있기 때문에, 이 구조는 고성능 라우터나 백본 라우터에서 널리 사용된다.
2.3 Input port Queueing
만약, input port에서 패킷이 들어오는 속도보다 switching fabric이 처리하는 속도가 더 느리다면, 대기 공간이 필요할 것이고, 이는 router에서 queue로 구현되어 있다.
다음 상황을 살펴보자.
그림의 왼쪽 상황부터 설명하면,
- input port로 패킷들이 들어오는 상태이고, 각자 색깔에 맞는 ouput port로 이동해야 한다고 가정한다.
- 빨간색 패킷들이 2개가 들어오 상태고, 빨간색에 해당하는 ouput port는 한 개이므로, 우선순위가 필요하다.
- 위쪽의 빨간색 패킷이 먼저 이동한다고 가정한다.
그리고, 3번이 진행된 후의 그림이 오른쪽 그림이다. 오른쪽 그림에 대해 마저 설명하면,
- 위쪽의 빨간색 패킷이이동하고, 2번째 input port에서는 파란색 패킷이 이동한 상태이다.
- 그렇지만, 3번째 input port에 들어온 빨간색 패킷은 우선순위가 낮아 기다려야한다.
- 그 후에 들어온 초록색 패킷은 어쩔 수 없이 1번더 기다려야 한다.
이때, 3번째 input port에서는 HOL blocking 상황이 발생했다. 초록색이 먼저 들어왔다면 기다릴 필요 없이 바로 이동할 수 있었는데, 먼저 들어온 빨간색 패킷때문에 초록색이 어쩔 수 없이 1번 더 기다려야 하는 상황이 발생한 것이다.
3. Output port
3.1 Output port 구조
위의 문제를 해결하기 위해서는 ouput port에 대해서도 알아봐야 한다. 먼저 Output port에 대한 구조에 대해서는 Input port 구조의 반대라고 생각하면 된다. 다음 그림을 살펴보자.
- output port는 switching fabric으로부터 datagram을 전달받는 위치이다. 따라서 가장 먼저 위치하는 것은 3계층의 datagram buffer이며, 여기에 수신된 datagram이 일시적으로 저장된다.
- 이후, 2계층(link layer)에서 datagram에 2계층 헤더를 추가해 encapsulation을 진행한다.
- 마지막으로, 1계층(physical layer)인 line termination을 통해 신호로 변환되어 외부 링크로 전송된다.
3.2 Output port Queueing
위 구조에서 확인할 수 있듯, output port에도 queue(버퍼)가 존재한다. 이로 인해 output port 측에서도 queueing delay가 발생할 수 있다. 다음 그림은 시간 흐름에 따른 output port buffer 상황을 보여준다.
- 왼쪽 그림 (시간 t 시점):
- 두 개의 빨간색 패킷이 각각 위쪽 input port와 아래쪽 input port로부터 동시에 도착한다.
- 두 패킷은 동일한 output port(빨간색)에 도달해야 하므로, 우선순위 없이 순차적으로 output port buffer로 이동한다.
- 오른쪽 그림 (t + one packet time 시점):
- 두 패킷이 output port의 버퍼에 쌓인 상태이다.
- 이후에도 지속적으로 패킷이 도착하게 되면, 버퍼가 점점 가득 차게 되고, 결국 buffer overflow가 발생할 수 있다.
이런 상황이 지속되면 packet loss(패킷 손실)이 발생할 수 있다.
3.2.1 Buffer Management
위의 상황과 더불어 Buffer에서는 패킷의 우선순위가 높으면 먼저 처리하는 방법도 존재한다. 다음 그림을 살펴보자.
그림에 대해서 설명하면, Abstraction인 만큼 가정이다. 즉, queue에서 어떤 패킷을 먼저 꺼낼지 2계층인 link layer가 결정한다고 가정해본다는 것이다.
그렇다면 이때, ouput port의 queue에 패킷이 도착하는 속도가 link layer에서 패킷을 빼내는 속도보다 빠르면, queue가 가득 차게 되고, buffer는 이 가득찬 queue를 관리하기 위해 패킷들을 drop할 수 있다. 다음 두 가지 방식으로 drop한다.
- Tail Drop : 나중에 도착한 패킷을 drop시킨다.
- Priority : 우선순위에 기반해 drop시킨다.
또, 라우터는 TCP 헤더의 ECN 기능과 함께 RED 같은 혼잡 제어 매커니즘을 활용할 수 있다. 이전에 TCP ECN 방식에서는 혼잡을 감지하면 IP 헤더 또는 TCP 헤더 내의 ECN 비트를 11로 설정하여 수신 측에 혼잡 신호를 전달한다고 정리했다. RED(Random Early Detection)는 queue가 가득 차기 전에 혼잡이 예상되면, 버퍼에 여유가 있더라도 랜덤하게 패킷을 미리 drop하거나 ECN 마킹을 해 송신자에게 혼잡 신호를 전달한다.
3.3 Packet Scheduling
Tail drop은 흔히 사용하는 queue 관리 방식이지만, 패킷을 어떤 순서로 처리할지, 어떤 패킷을 먼저 내보낼지는 별개의 문제이다. 이 순서를 결정하는 것이 바로 Packet Scheduling이다.
Packet scheduling 방법에는 4가지 방법이 있다.
- FCFS(First Come, First Served) : 먼저 온 순서대로 내보내기(=FIFO), 가장 많이 사용되는 방법
- Priority : 우선순위 높은 순으로 내보내기
- RR(Round Robin) : 여러 큐를 번갈아가며 순서대로 내보내기
- Weighted Fair Queueing : Round Robin에 우선순위나 가중치를 반영하는 방법, 가장 복잡한 방법
기본적으로 FCFS 방식을 쓰지만, 아래 3가지 방법도 존재하며, priority 방식까지는 실제로 구현되며 사용하고 있지만 교수님께서 아래 두 개는 쓰이는 사례를 못보셨다고 하셨다. Priority 방식부터 차례대로 알아보자.
3.3.1 Priority
말그대로, 패킷들 간의 우선순위를 정해 우선 순위가 높은 순서로 link layer에서 빼가는 것을 말한다. 다음 그림을 한 번 살펴 보자.
그림에 대해서 간략히 설명하면, 2개의 queue를 만들어 놓는다.
- 빨간색 queue : 우선순위가 높은 패킷들을 위한 queue
- 초록색 queue : 우선순위가 낮은 패킷들을 위한 queue
패킷이 도착하면 Header fiedls 중 사용되지 않는 곳에 우선순위가 마킹된 것을 보고, 적절한 queue로 분류한다. 그 후, 다음 그림과 같이 처리된다.
그림에 대해서 설명하면, 왼쪽에서 오른쪽으로 시간이 진행되고, 각 번호는 도착한 순서를 나타낸 것이다.
- 우선순위가 높은 빨간색 패킷이 1번으로 도착했다.
- 1번이 처리되고 있는 도중에 우선순위가 낮은 초록색 패킷 2번과 빨간색 패킷 3번이 도착했다.
- 이때, 빨간색 패킷이 3번으로 도착했어도, 2번보다 우선순위가 높기 때문에 먼저 처리하고 내보낸다.
- 그 뒤, 2번이 처리되는 와중 4번이 도착하면, 2번이 다 끝난 뒤에 4번을 처리한다.(우선순위가 높더라도 처리되고 있는 패킷을 무시하며 먼저 처리되지 않는다.)
- 처리되고 있는 패킷이 없이 5번의 초록색 패킷이 들어오면 바로 처리한 후 내보낸다.
추가로, 만약 우선순위가 같으면 FCFS 방식을 따라 먼저 들어온 패킷을 먼저 처리한다.
3.3.2 Round Robin
다음은 round robin scheduling 방법으로, queue를 번갈아가며 처리해주는 방식이다. 다음 그림을 살펴보자.
위 그림에 대해 설명하면, 들어오는 패킷들을 적절한 queue에 나눠 담고, link layer에서 queue를 번갈아가며 처리하는 방식이다.
이 방법을 보면, HTTP/2가 HOL blocking을 완화시키는 방법이 떠오른다. (영상, 이미지1, 이미지2// 영상, 이미지1, 이미지2.... 반복하며 처리하는 방식처럼)
3.3.3 Weighted Fair Queueing
다음은 Round Robin 방식에 가중치를 부여한 scheduling 방식인 weighted fari queueing이다. 즉, 기본적으로는 queue를 순차적으로 순회하는 구조지만, 각 queue마다 처리량을 다르게 설정하여 트래픽의 중요도나 필요 대역폭에 따라 비율을 조정한다. 다음 그림을 살펴보자.
들어오는 패킷을 각 큐에 적절히 분류하는 것과, 번갈아가며 처리하는 기본 아이디어는 round robin 방식돠 동일하다. 그렇지만, 각 queue에 가중치를 부여한 것인데, 그림과 같이 설명하자면,
- 빨간색, 초록색, 파란색 queue에 각각 가중치 w1,w2,w3를 부여한다.
- wi(i=1,2,3)를 w1+w2+w3로 나누어, 즉, wi/w1+w2+w3의 값을 구해 각 queue에 현재 가중치를 판단한다.
- w1=1, w2=2, w3=3이라면, w1은 1/6만큼, w2는 1/3 만큼, w3=1/2 만큼의 비율로 처리된다.
위와 같은 방법으로 진행하면, 공평하게 서비스를 제공받을 수 있다는 장점이 있지만, 구현하기 많이 복잡하기 때문에 실제로 라우터에 사용되는 방법은 아니다.
'학교공부 > [컴퓨터 네트워크]' 카테고리의 다른 글
| [컴퓨터 네트워크] - Network Layer_NAT (0) | 2025.06.05 |
|---|---|
| [컴퓨터 네트워크] - Network Layer_IP (3) | 2025.06.05 |
| [컴퓨터 네트워크] - Network Layer_프롤로그 (0) | 2025.06.02 |
| [컴퓨터 네트워크] -Transport layer _ Transport layer의 진화 (0) | 2025.06.02 |
| [컴퓨터 네트워크] - Transport layer_TCP Congestion control (0) | 2025.05.31 |
