[컴퓨터망] - Network Layer(Routing & Forwarding & Switching Fabric && Buffer Management)

이번 글은 Network Layer에 대해서 설명해 보겠습니다.

우선 Network Layer는 Transport Layer 아래에 위치합니다.

---

Network layer의 핵심 기능

1. Forwarding
   1. data plane이 담당
   2. 패킷이 들어왔을 때, 보내주는 기능
2. Routing
   1. control plane이 담당.
   2. 들어온 패킷을 어디로 보낼지 판단하는 기능
   3. 판단하는 과정을 Routing table을 보고 판단함.

간단하게 두 기능을 여행에 비유해 설명해 보자면,

forwarding은 여행을 하는데 고속도로를 통과하는 것처럼 그저 나아가는 작업입니다.
routing은 여행에서 출발지에서 목적지까지의 경로를 계획하는 과정입니다.

자 그러면 이러한 기능들을 해주는 Data plane과 Control plane은 무엇일까요

---

Data plane & Control plane

Data plane

• 적용범위가 local이며, 각각의 라우터마다 동작함.
• input port로 도착한 datagram이 어떻게 output port로 가야 하는지 결정한다.

Control plane

• 적용범위는 네트워크 전체
• 출발지에서 도착지까지 라우팅 되는 방법(경로)을 결정한다.
  • 2가지 방법이 있다.
    1. 라우팅 알고리즘
       • 포워딩 테이블을 이용해서 어디로 갈지 경로를 정함.
    2. SDN(software-defined networking)
       • 원격의 서버를 이용함.

---

Routing 알고리즘

Per-router control plane

같은 machine안에 control plane과 data plane이 모두 있는 그림.

control plane은 모든 라우터에 들어 있어서, 라우팅을 해준다.

위는 forwarding table을 이용한 Routing Algorithm을 control plane에서 맡아서 경로를 정함.

user data가 도착하면 data plane에서 다음 경로로 forwarding 함.

forwarding은 destination ip address만 보고 forwarding 한다.

SDN(Software-Defined Networking) control plane

중앙에서 네트워크를 제어하고 관리하는 방법. 각 라우터마다 중앙서버(control plane)에서 다음 경로를 제어하고 관리해 줌.

control plane과 data plane이 분리되어 있다.

---

Network Service Model

네트워크 레이어에서 제공하는 서비스들은 뭐가 있을까요

• individual datagram
  1. delivery를 보장
  2. 일정 delay 이내로 패킷을 보내는 것을 보장
• flow of datagrams
  1. 순서대로 패킷을 보내주는 것을 보장
  2. 최소 대역폭을 보장

라우터의 구조

• 입력포트
• 출력포트
• Routing을 담당하고 관리하는 소프트웨어 형태의 Routing processor
• Forwarding을 담당하는 하드웨어 형태의 high speed switching fabric

Router input functions

line termination

• physical layer에서 처리함.

link layer protocol

• data link layer에서 처리함.

lookup forwarding queueing

• 하나씩 꺼내서, 헤더를 보고 어디로 보낼지 판단하여 switch fabric으로 보냄.
• 어디로 보낼지 정하는 것은 forwarding table을 보고 판단함.

인풋 포트에서 fabric으로 포워딩해 주는 속도가 datagram이 도착하는 속도보다 느리면 buffering이 발생한다.
이를 입력 큐잉이라고 한다.

이에 대해서는 밑에서 더 자세히 설명하겠습니다.

---

forwarding table

control plane에서 Routing을 진행할 때 이용하는 테이블이다.
각각의 라우터마다 모두 보유하고 있으며, 목적지를 보고 경로를 설정해 주는 역할을 한다.

forwarding table은 목적지의 주소에 해당하는 Link interface로 보내준다.

forwarding table을 일반화한 식은 위의 식이 된다.

위의 Destination Address는 어디로 보내야 할까요?

1번과 2번 Link inter face 접두사와 일치합니다.

여기서 더욱 분명하게 결정짓기 위해서

forwarding table은 Logest prefix matching알고리즘을 사용합니다.

즉 가장 길게 일치하는 Link interface에 보내준다는 뜻이다.

Destination Address를 끝까지 검사해 보면 1번 접두사와 가장 길게 일치하는 것을 알 수 있고, 라우터는 1번으로 보내게 됩니다.

---

Switching fabrics

패킷이 입력포트에서 적절한 출력포트로 보내주는 라우터의 핵심 기술입니다.

switching rate

• 패킷이 input에서 output으로 전송될 수 있는 속도
• input/output line rate로 측정가능하다.

스위칭 페브릭은 아래와 같은 구조입니다.

1. 메모리를 통한 스위칭
2. 버스를 통한 스위칭
3. 상호연결 네트워크를 통한 스위칭

메모리를 통한 스위칭

초기의 라우터 방식이었다.

위 그림처럼 가운데 memory를 두어 작업을 처리하는 중앙화 방식입니다.

따라서 모든 입력포트들은 하나의 메로리를 공유하게 되는 방식이고, 속도가 느립니다.

그리고 이 방식은 메모리에 패킷을 복사합니다.

이렇게 메모리에 패킷을 복사하는 것에는 단점이 존재합니다.

• 패킷을 메모리에 복사하기에
  • 지연이 발생한다.
  • 메모리 자원을 소비하기에, 메모리 부하가 올 수 있다.
  • 전력소비
  • 스케일링문제

이러한 방식은 입력과 출력이 공유 시스템 버스를 통해 한 번에 하나의 메모리 읽기 쓰기 작업이 가능하다.

그리고 한 패킷을 복사해서 사용하기에, 최대 출력은 기존 메모리 대역폭의 절반이다.

버스를 통한 스위칭

버스란?

네트워크에서 데이터와 제어신호를 전송하기 위한 물리적인 통신 매체입니다.
즉 데이터가 이동하는 통신경로입니다.

입력 포트에 패킷은 공유 버스를 통해서 출력포트로 이동합니다.

공유버스라는 하나의 통로를 통해 패킷이 이동하기 때문에,

전송속도는 버스의 대역폭이나 데이터 전송속도에 영향을 받습니다.

단점

• 하나의 버스만을 사용하기 때문에 충돌을 피하기 위해 한 사이클 당 하나의 패킷만 처리할 수 있다.
• 여러 장비가 동시에 데이터를 전송하려고 할 때 버스 충돌이 발생할 수 있어 데이터 전송의 신뢰성이 저해됨.
• 병렬로 여러 개의 데이터를 전송하기 때문에 병렬 전송선의 수가 많아지면 비용이 증가한다.
• 버스는 단일 통신 매체로 사용되기 때문에 전송 속도에 한계가 있다.
  • 모든 장비가 단일버스를 공유-> 해당 버스에 장애가 생기면 시스템에 영향을 줌.

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

다양한 스위치나 라우터들이 병렬로 상호 연결된 구조입니다.

n개의 입력포트와 n개의 출력포트가 연결된 구조.

동시에 여러 개의 패킷을 병렬적으로 보낼 수 있습니다.

multistage switch를 두어서 병렬 처리를 가능하게 합니다.

• 전체 패킷 처리를 분산시켜서 이동시킴.
  • 데이터 전체를 이동시키는 것보단 데이터를 잘게 쪼개서 이동시키는 것이 더 효율적이고 빠르다.

전체 패킷을 잘게 쪼개서 이동시킨 뒤 종료하고 데이터그램을 재 재조립하는 병렬처리 방식을 이용한다.

---

Input port queuing

만약 스위칭 페브릭의 속도가 input port에서 내보내는 속도보다 느리면

input queue에서 큐잉 딜레이가 생긴 것입니다.

이러한 큐잉 딜레이와 loss는 input buffer에 오버플로우가 나서 생깁니다.

즉 인풋 큐잉은 모든 패킷을 전송하기에 스위칭 페브릭이 입력 속도에 비해 빠르지 않기에 발생합니다.

HOL(Head-of-the-Line) blocking

위 그림은 HOL(Head-of-the-Line) block의 예시 상황입니다.

그림을 설명하자면, 초록 패킷은 빨간 패킷에 의해 대기하고 있는 것을 볼 수 있습니다.

1번의 빨간 패킷과 3번의 빨간 패킷이 빨간 출력포트로 이동하는데, 두 패킷의 경쟁사황 때문에 죄 없는 초록패킷은 기다리고 있습니다.

이렇게 나와 연관 없는 패킷 때문에 대기하는 상황을 HOL Blocking이라고 합니다.

---

Output port queuing

입력포트와 마찬가지로, 출력포트에서도 큐잉이 발생할 수 있습니다.

어떤 상황에서 출력 큐잉이 발생할까요?

여러 개의 패킷이 동시에 도착하여 같은 출력포트로 전송될 때 발생합니다.

즉 출력포트로 전송하는 속도보다 페브릭에 도착하는 속도가 더 빠를 때 버퍼링이 발생합니다.

여기서 만약 출력 버퍼가 가득 차게 되면, 뒤에 도착하는 패킷들은 drop 될 수 있기 때문에, 적절한 스케쥴링을 통해서

버퍼가 넘치지 않게 패킷을 내보내주는 작업이 필요합니다.

여기서 버버페 있는 패킷 중에 누구를 먼저 보낼 거냐~~ 하고 정하는 기준을 패킷 스케쥴링이라고 합니다.

Buffer Management

버퍼가 가득 찬 상황에서 패킷이 들어온다면 버퍼 매니지먼트에서 패킷을 drop 합니다.

그럼 어떤 패킷을 drop 하느냐?

2가지 방식이 있습니다.

1. tail drop
   • 말 그대로 꼬리를 내보낸다는 소린데, full 된 시점에서 가장 먼저 도착한 패킷을 내보냅니다.
2. priority
   1. 패킷마다 우선순위를 부여해서, 가장 낮은 우선순위에 해당하는 패킷을 drop 하거나 제거합니다.

Buffer가 가득 찬 상황이면 패킷의 손실이나 지연이 생깁니다.

이러면 우리는 혼잡 제어 알고리즘을 통해서 이러한 상황을 해결해야 합니다.

Marking은 혼잡 제어에서 사용되는 버퍼 관리 기술 중 하나입니다.

혼잡이 발생한 경우 송신 측에게 보낼 패킷에 표시를 하여 지금 혼잡하니, 다른 경로로 전송을 유도하는 등 혼잡을 완화할 수 있습니다.

FCFS(First Come First Send)

스케쥴링하면 대표적으로 나오는 방법 중의 하나입니다.

말 그대로 선입선출, 들어온 순서대로 나갑니다.

하지만 이러한 방식은 효율적이라고는 할 수 없습니다.

예를 들어서 나는 1분이면 작업이 끝나는데, 앞에 사람은 1시간 동안 작업을 해야 끝나는 상황이면

나는 앞사람이 끝날 때까지 기다려야 합니다. 나는 1분만 하면 끝나는데!

굉장히 효율적이지는 않습니다.

하지만 가장 단순한 방법이고, 직관적인 방법이 또 FCFS방법입니다.

Priority scheduling

작업마다 우선순위를 부여해서 큐를 분류합니다.

우선순위가 높은 작업을 우선적으로 끝냅니다.

이러한 방식에도 단점이 존재합니다.

"아니 중요한 일을 먼저 끝내는 것이 당연한 거 아냐? 좋은 거 아냐?"라고 생각하실 수도 있지만,

낮은 우선순위 큐에 있는 친구들이, 계속 우선순위 큐에 있는 작업을 기다리고, 기다리고, 기다리다가,

낮은 우선순위 큐에 있는 패킷이 전송되지 못하는 starvation(기아)가 발생할 수 있습니다.

즉 낮은 우선순위 큐에 있는 패킷들은 무작정 기다려야 하는 단점이 있습니다.

RR(Round-Robin) 라운도 로빈

라운드로빈도 여러 클래스로 패킷을 분류합니다.

여러 클래스로 분류된 패킷들을 번갈아 가면서 전송하는 방식입니다.

각 클래스들은 자신의 차례가 오면 패킷을 전송합니다.

이 방식의 단점은 평등한 할당이기에, 중요도가 높은 작업과 중요도가 낮은 작업이 동일한 패킷량을 전송하기에,

중요도가 높은 작업이 불필요하게 대기하는 시간이 생길 수도 있습니다.

이러한 단점을 해결하기 위해서 WFQ라는 방식이 도입되었습니다.

WFQ(Weighted Fair Queuing)

RR방식에서 분류된 클래스에 우선순위를 부여하는 방식입니다.

Round-Robin 방식처럼 순환형식으로 동작하지만, 각자 자신의 차례에 가중치에 맞는 시간을 할당받습니다.

즉 가중치가 높은 클래스는 더 많은 시간을 부여받아서 패킷을 많이 전달하게 되고,

가중치가 낮은 클래스는 비교적 적은 시간을 부여받아서 패킷을 적게 전달합니다.

각 서비스 시간은 자신의 가중치/가중치의 합으로 부여받습니다.

 

---

요약

• Network의 핵심기능은 Forwarding과 Routing이 있다.
  • Forwarding
    • 패킷이 들어왔을 때, 보내주는 작업을 함.
  • Routing
    • 들어온 패킷을 어느 경로로 보낼지 판단하는 작업.
• Switching fabrics는 패킷이 입력포트에서 출력포트로 전달해 주는 과정이다.
  
  • 메모리, 버스, 상호연결 네트워크 구조가 있다.
• 입력 큐잉
  • 스위칭 페브릭의 속도가 input port에서 내보내는 속도보다 느리면 발생.
    • 버퍼에 오버플로우가 나서 생긴 현상이다.
  • HOL blocking
    • 입력포트에서 생기는 현상으로, 앞에 있는 연관 없는 패킷 때문에 다른 패킷이 대기하는 상황
• 출력 큐잉
  • 출력포트에서 전송하는 속도보다 페브릭에 도착하는 속도가 더 빠를 때 발생.
    • 여기서는 버퍼가 가득 찬 경우, 뒤에 도착하는 패킷들이 drop 될 수 있기 때문에 적절한 스케쥴링이 필요함.
      • 이러한 스케쥴링은 Buffer Management에서 관리함.
• 스케쥴링 알고리즘은 FCFS, Priority, RR, WFQ가 있다.