Network layer - introduction

Transport layer에서는 sending process에서 receiving process로 data를 전달하는 기능을 제공하는데

Network layer에서는 Segment를 sending host에서 receiving host로 전달하는 기능을 제공한다.

 

sending side에서는 transport layer에서 보내준 segment를 받아서 datagram으로 만든다.

참고로 segment 앞에 network layer의 header를 붙여주면 datagram이 된다.

이후 receiving side에서는 이 datagram을 받아서 segment를 꺼내고 transport layer로 전달해주게 된다.

 

transport layer나 application layer에서는 보내는 쪽과 받는 쪽에만 구현이 돼 있으면 되지만

network layer의 기능은 모든 host와 모든 router에 다 구현이 되어 있어야 한다.

이 때 router는 datagram의 header를 조사해서 datagram을 어디로 보낼지 정하게 된다.

 

이렇게 network layer에서 이러한 기능(sending host -> receiving host (datagram))을 제공해주기 위해서

각각의 router들은 어떤 기능을 해야할까?  -> 2가지 Key Function이 있는데

그것은 Forwarding과 Routing이다.

 

▶ Forwarding: Router의 input으로 들어오는 packet을 적절한 router의 output으로 보내주는 기능

▶ Routing: 보내는 쪽에서 받는 쪽 까지 packet이 거쳐가야할 경로를 결정해주는 기능

여행으로 비교한다면 forwarding은 하나의 interchange를 거쳐서 가는 기능을 말하고

routing은 목적지부터 도착지까지의 여행 경로를 계획하는 과정을 말한다.

 

이 기능들을 담당하는 부분이 있을텐데, 이들을 각각 Data plane과 Control plane으로 구분한다.

여기서 plane은 sub layer라고 생각하면 되는데, 한 계층에 두 가지 서로 다른 일에 대한 구분을 위한 용어이다.

 

▶ Data Plane: datagram이 router의 input port로 도착하면, output port로 보내주는 기능을 한다.

대표적으로 forwarding 기능을 수행하게 되고 router 안에서, router별로 개별적인 작업이 이루어지게 된다.

 

▶ Control Plane: 네트워크 전반에 걸친 logic을 만들어내는 기능을 한다.

Data Plane은 하나의 네트워크 안에서 동작하는 기능이라고 보면, Control Plane은 네트워크 전체를 살펴봐야한다.

즉 Control plane에서는 datagram이 source에서 destination까지 어떤 router들을 거쳐서 가야하는지 결정해준다.

이러한 Control Plane을 구현하는 방식은 2가지가 있는데

Traditional routing algorithms과 SDN(Software-Defined Networking) 방식이다.

Per-router control plane (Traditional Routing Algorithms)

router별로 control plane이 다 구현이 되어있고, 그 안에서 routing algorithm이 수행된다.

이 때 router들은 서로 간에 메세지를 주고 받으면서 interaction을 하는데,

이 내용을 바탕으로 해서 경로를 설정하게 되고, 그 결과는 local forwarding table이라는 곳에 저장을 한다.

이 forwarding table은 data plane에서 packet이 들어왔을 때 header 정보를 보고 forwarding table에 검색을 할 때

사용되고 그 결과를 토대로 output interface를 찾아서 내보내는 forwarding 기능을 하게 된다.

 

즉 정리하면 Control plane의 결과로 forwarding table이 만들어지고, 이 table을 이용해서 forwarding을 수행한다.

따라서 Control plane과 Data plane은 동 떨어져 있는 것이 아닌 서로 협업을 해야하는 대상이다.

 

각각의 node가 다 data plane과 control plane을 구현하고 있다. -> Per router control plane (각각의 router에 존재한다)

Logically centralized control plane(SDN 방식)

반면에 Logically centralized control plane을 살펴보면, 우선 control plane을 중앙집중화 시켰다.

각각의 router에 control plane이 있는 것이 아닌, 독립적인 원격의 controller가 존재한다.

이 controller는 각 router에 마련된 control agent라고 하는 간단한 software와 메세지를 주고 받는다.

그렇게 주고 받은 정보를 통해 각 router에서 사용할 forwarding table을 계산 및 작성하고 보관한다.

그 table 내용을 control agent에게 보내고 control agent는 각 router의 forwarding table에 쓰게 된다.

이 경우 각각의 router에는 control plane 기능이 없다. -> 대신 control agent가 존재한다.

 

이렇게 한 곳에 모아놨을 때 생기는 장점은 일관성이 생긴다는 것이다.

그 이유는 router의 동일한 상태를 가지고 forwarding table을 만들기 때문이다.

각각의 router가 forwarding table을 만들게 되면, router들이 수집한 정보가 서로 정확하게 일치하지 않을 수 있다.

메세지를 보내는 시간의 차이가 있기 때문인데, 어떤 router 사이의 링크가 끊어지는 사건이 일어났을 때

거리가 멀어서 해당 정보를 못받았을 때 만든 forwarding table과 링크가 끊어진 것을 알고 있는 상태에서 만든

forwarding table은 당연히 정보가 다를 수 있고 따라서 일관성이 없게 된다.

정리하면 router 간에 서로 일치 하지 않는 정보를 갖게 될 확률이 있다는 것이다.

 

그렇게 일치하지 않은 정보를 가지고 routing을 하게 될 경우 loop가 발생할 수 있다.
한 쪽에서 뒤 쪽 router 사이에 링크가 끊어진 것을 알고, datagram이 오면 다시 앞으로 전달할 수 있는데

다시 전달 받은 쪽에서 링크가 끊어진 것을 모르고 있다면 계속 다시 앞으로 전달하게 되기 때문이다.

 

하지만 Remote Controller를 사용할 경우 특정한 시점에 정보를 Controller가 수집하기 때문에

loop가 발생하는 등의 안좋은 문제는 발생하지는 않는다.

단점으로는 중앙집중형이기 때문에 당연히 Controller가 죽어버릴 경우 forwarding table을 계산할 수 없다는 것이다.

이러한 방식이 Software-Defined Networking이라고 하며 주로 데이터센터 네트워크에서 많이 사용한다.

Network Layer에서 제공해주는 Service

각 datagram에 대해서 제공해줄 수 있는 서비스들의 예: delivery에 대한 보증, 40 msec 이내의 delivery 보장

 

datagram의 흐름(여러 개의 datagram에 대한 Connection)에 대한 서비스

1. in-order datagram delivery (순서에 맞게 보내주는 서비스)

2. minimum bandwidth에 대한 보증

3. flow안에 packet들이 있고 특정한 간격으로 이 packet들을 받는다고 했을 때

받는 쪽에서는 그 간격이 일정하지 않고 서로 다를 수 있다.

packet들 별로 중간에 거치는 경로가 달라질 수 있고, Congestion이 발생할 수 도 있기 때문이다.

이러한 간격들의 변화가 크지 않도록 일정 범위를 제한한 서비스를 제공해줄 수 있다.

 

Network layer의 service model은 Network Architecture에 따라서 달라진다. (Internet, ATM 등..)

Internet Architecture의 경우 best effort 라는 이름의 service model을 사용하는데

Bandwidth, Loss, Order, Timing에 대한 보증은 다 해주질 않는다.

Router의 내부 구조

하나의 router는 4개의 conponent로 구성이 되어있다.

input ports, output ports, (hight-speed) switching fabric, routing processor 이렇게 4개이다.

일반적으로 forwarding 기능은 hardware로 많이 구현을 한다.

굉장히 빠른 속도로 packet을 옮겨야 하기 때문이다.

최근에는 software로 구현하려는 시도가 있었지만 속도가 hardware만큼 나오지 않는 경우가 많다.

routing algorithm의 결과로 나온 forwarding table는 input ports 모두가 가지고 있다.

 

이제부터 이 구성요소들을 하나씩 살펴보자. (routing processor는 control plane에 속하기 때문에 나중에 본다)

 

1. Input ports

총 3가지로 나눠서 볼 수 있다. line termination, link layer protocol, lookup(forwarding, queueing)

우선 아날로그 signal을 받아서 bit로 만들어내는데 이 bit를 link layer로 보내주는게 line termination이다.

link layer에서는 header들을 검사하는 역할을 하는데 뒤에서 자세히 살펴볼 예정이다.

그리고 input port에서 가장 중요한 forwarding table을 lookup(찾아서) 적절한 output port로 넘겨주는 기능이다.

때때로 switching fabric에 속도가 느려질 수도 있는데 이 때는 queueing을 사용하기도 한다.

이 forwarding 기능은 굉장히 빠르게 수행되어야한다. (목표는 line speed로 처리하는 것)

 

여기서 table을 lookup 하는데 2가지 방식이 존재한다.

 

▶ Destination-based forwarding

destionation address만 보고 어디로 보내야할지 정하는 방법이다. (전통적인 방법)

여러 Range가 forwarding Table에 적히는데,

Destination Address Range	Link Interface
11001000 00010111 00010000 00000000 ~ 11001000 00010111 00010111 11111111	0
11001000 00010111 00011000 00000000 ~ 11001000 00010111 00011000 11111111	1
...	...

이런식으로 대략 30만개가 적힌다.그리고 보통은 Range 간의 영역은 겹치는 구간 없이 이어져있다.

 

하지만 그렇지 않을 경우가 발생할 수도 있는데 그럴 때는 어떻게 ? -> Longest prefix matching 방식의 등장

Longest prefix matching은 가장 긴 prefix에게 matching을 시켜준다는 뜻이다.

만약에 어떤 Address가 여러 군데에 Range에 matching이 된다면 Longest Address prefix에 matching을 시킨다.

이 방식의 경우 가장 긴 prefix와 matching을 하기 때문에 겹치는 경우가 생겨도 상관없다.

 

또한 와일드 카드를 사용하는데, 와일드 카드 내용에는 0이든 1이든 상관없다.

단, 그 앞에 나오는 숫자는 반드시 같아야 한다.

Destination Address Range	Link Interface
11001000 00010111 00010*** *********	0
11001000 00010111 00011000 *********	1
11001000 00010111 00011*** *********	2
otherwise	3

예시:

11001000 00010111 00010110 10100001 -> 0에 matching

11001000 00010111 00011000 10101010 -> 1에도 matching, 2에도 matching이 가능하다.

이 때 Longest prefix matching을 사용한다.

prefix는 와일드 카드 없이 정의된 숫자를 말하기 때문에 가장 긴 prefix는 Link interface 1에 해당된다.

 

앞에서 Range들이 30만개 이상 나온다고 했는데,

이들을 일일이 matching 여부를 확인하는데 시간이 오래걸리면 곤란하다.

따라서 TCAMs(Ternary Content Addressable Memories)라고 불리는 하드웨어를 이용해서 빠르게 lookup이 진행된다.

Destination Address를 TCAM에 주게 되면 TCAM이 1 clock cycle만에 output link를 return 시켜준다.

ex: Cisco Catalyst의 경우 백 만개의 entry까지 들어갈 수 있고, 백 만개 이내의 entry는 한 번에 찾아낼 수 있다.

 

좋은 라우터의 경우 이처럼 비싼 TCAM을 이용해서 Link Interface를 빠르게 찾아낼 수 있도록 하고 있다.

 

▶ generalized forwarding

header에 있는 다양한 field들을 참조해서 어디로 보낼지 정하는 방법이다.

destination-based 방식은 generalized forwarding의 방식 중 하나라고 볼 수 있다.

 

Input port queuing

앞에서 언급한 것처럼 input port에도 queue가 있다는 얘긴데, queue가 필요한 이유는

만약 fabric이 input port에 들어오는 속도를 다 합친 것 보다 속도가 조금 느릴 경우 보낼 수가 없기 때문이다.

따라서 이럴 경우 delay나 loss가 발생할 수 있고, input port에서 queue를 만들어놓고 안에 packet을 넣어놨기 때문에

Head-of-the-Line blocking(HOL) 라고 하는 새로운 문제가 생겼다.

 

▶ Head-of-the-Line blocking(HOL)

밑에서 설명하겠지만 Switching Fabric의 가장 좋은 방식인 interconnection network를 사용했다고 가정해보면,

이 경우에도 동시에 전송할 수 없을 때가 있다. (동시에 보내지 못하는 문제를 개선한 방식이었다.)

어떤 경우일까?

각각 다른 output port로 보내려고 할 때는 동시에 전송이 가능하지만,

서로 다른 input port가 같은 output port로 packet을 전송할 때는 둘 중에 하나만 보내야한다.

그러면 보내지 못한 쪽은 기다려야 하는데,

그동안 해당 input port line에서 기다리고 있는 모든 패킷들은 blocked 상태가 된다.

심지어 기다리고 있는 패킷들 중에서는 output port가 아무런 packet을 받고 있지 않아서 놀고 있을 때도 있다.

하지만 그래도 자신의 앞에 있는 패킷의 output port가 현재 다른 packet을 처리하고 있기 때문에 기다려야 한다.

이 현상을 Head-of-the-Line blocking(HOL) 이라고 한다.

짧게 요약하자면 Line의 맨 앞에 있는 녀석이 길을 막고 있는 것이다.

 

Input port에서 queue를 사용할 때 생기는 문제 중 하나가 바로 이 HOL Blocking이다.

 

2. Switching Fabrics

input port에서 들어온 packet을 어디로 보낼지 결정을 했다면 Switching Fabric에게 요청을 하게 된다.

Switching Fabric은 input buffer로 부터 들어온 packet을 적절한 output buffer로 보내주는 역할을 한다.

 

그런데 이 자체도 processing 이기 때문에 시간이 소요된다.

switching rate이라고 하는 성능 표시 단위가 있는데, packet들이 input에서 output port로 전달되는 rate을 의미한다.

(ex: 1초에 패킷 n개 or 100kb 만큼 전달할 수 있다.)

 

switching rate은 N개의 input이 있을 때 line rate보다 N배 정도 커야 정상적으로 돌아갈 수 있다.

만약 link는 1Gbps인데 switching rate이 1Gbps라고 하면, 3개의 link가 1Gbps씩 들어올 때 처리가 불가능하다.

 

그렇다면 Switching Fabric은 어떻게 만들어질까?

크게 3가지가 있다. -> Memory 기반, Bus 기반, CrossBar 기반

 

▶ Switching via memory (1세대 라우터에서 사용)

일반적으로 컴퓨터라고 생각하면 된다.

우선 CPU가 input port에 있는 packet을 memory로 읽는다.

forwarding table도 memory 내에 있기 때문에 어디로 내보낼지 결정한 후 memory에서 output port로 보내준다.

memory bandwidth와 bus를 이용할 때의 속도에 의해서 얼마나 빠른 속도로 switching 하는지가 결정된다.

memory를 거쳐서 data가 전달되기 때문에 속도가 빠른 편은 아니다.

게다가 input port -> memory, memory -> output port 이므로 총 2번 bus를 거쳐야한다.

 

이 방법 보다 조금 더 발전한 방법이 Bus를 이용한 방법이다.

 

▶ Switching via a bus

datagram이 input port에서 bus를 거쳐서 output port로 간다.

bus은 shared 방식이기 때문에 순서에 따라서 bus를 통해 packet을 통해 보내게 된다.

이 경우 bus를 한 번만 사용하기 때문에 bus를 두 번 사용하는 memory 방식 보다는 속도가 빨라진다.

 

다만 문제는 3개의 input port가 있을 때 이들이 동시에 packet을 보내는 것이 불가능하다.

그래서 등장한 것이 crossbar switching 방식이다.

 

▶ Switching via interconnection network (성능이 제일 좋다.)

crossbar 같은 interconnection network를 이용한 방식을 말한다. (banyan networks, crossbar 등이 있다.)

input port와 output port 사이에 어떤 network를 만드는 것이다.

이 방식을 사용하면 input port에서 output port로 동시에 보낼 수가 있어서 더 빨리 Switching이 가능하다.

여기에 좀 더 속도를 빨리하기 위해서 datagram을 똑같은 size의 cell로 분할해서 보내는 등의 방법을 사용하기도 한다.

 

3. Output Ports (가장 중요하다 !!)

 

switching fabric을 통해서 packet이 output port로 넘어오게 되면

bit를 아날로그 신호로 바꾸고 line을 통해서 전달을 해줘야하는데

이 때 나가는 Speed는 정해져있다.

그리고 queue를 사용하기 때문에 queue가 가득 차게 되면 packet이 손실 날 수 있고 delay도 발생할 수 있다.

 

Switching Fabric로부터 packet이 들어오는 속도가 line에서 처리할 수 있는 속도(transmission rate)를 넘어간다면

일단 queue에다가 넣어놓는 buffering이 필요하다.

기본적인 처리 과정은 buffer 맨 앞에 있는 packet을 꺼내고 link layer 관련 처리를 한 후 bit들을 내보내면 된다.

방금 맨 앞에 있는 packet을 꺼낸다고 했지만, 사실 buffer에서 packet을 꺼내는 순서(방식)에 대한 이슈가 존재한다.

그리고 이를 scheduling discipline 이라고 한다. (밑에서 좀 더 자세히 다룰 것이다.)

따라서 스케쥴링 방식에 따라서 queue의 맨 앞 부터 또는 중요도 순서 등으로 보내는 작업이 이루어진다.

 

그렇다면 output port에 있는 buffer의 size는 어느정도 해줘야할까?

RFC 3439의 정의에 따르면 RTT가 있으면 Link의 Capcity(C)를 곱한 값을 사용한다. (recommend)

만약 RTT가 250mesc(= 0.25 sec), C = 10Gbps link 라면 2.5Gbit buffer가 된다.

최근에는 flow(N)가 여러 개가 있을 경우 RTT * C를 루트 N으로 나눈 값을 추천한다. (2.5Gbit 보다 작은 값이 나온다.)

하지만 사실 RTT가 flow마다 다르기 때문에 특정 RTT를 찾는 것이 쉬운 일은 아니다.

그래서 라우터를 만들 때 Queue Size가 이미 정해져있기 때문에 그냥 그대로 사용한다.

최근 경향은 buffer를 작게 해서 조금만 넘어가도 drop을 시키고 sender 쪽에서 retransmission을 빨리 하도록 한다.

 

Scheduling mechanisms

해당 링크에서 다음에 보낼 packet을 선정하는 방식

가장 대표적인 방식은 FIFO scheduling, 도착한 순서대로 보낸다.

 

discard policy(버리는 정책): queue가 꽉 찼을 때 packet이 도달하면 어떤 것을 버릴지에 대한 정책

- tail drop: 들어오려고 하는 packet을 버린다.

- priority: 우선순위 기반으로 drop을 한다. (우선순위가 높은 패킷이 들어오면 우선순위가 제일 낮은 패킷을 버림)

- random: 랜덤으로 하나를 골라서 drop 시킨다.

 

▶ Priority 기반 Scheduling

priority가 높은 packet을 먼저 보내려고 하는 방식

따라서 우선순위 별로 class를 만들었다. (ex: high priority queue, low priority queue -> 2개의 우선순위 class)

packet이 도달하면 header를 보고 어느 priority에 속하는지 결정을 해준다.

그리고 link로 보낼 때에는 high priority queue에 packet이 있으면 무조건 이 packet부터 보낸다.

high queue에 packet이 없을 때 low priority queue에서 packet을 보낸다.

참고로 low priority queue에서 packet을 꺼내서 보내고 있을 때 high priority packet이 들어오더라도

보내고 있는 중간에 멈추지 않고 high priority packet이 기다려야한다.

 

▶ Round Robin Scheduling

기본적으로 class들이 여러 개 존재하고, 순환하면서 보내는 방식

class를 쭉 스캔하면서 1번 class 확인 -> 있으면 보내고, 그 다음 2번 class, 3번 class 이런 식으로 나간다.

즉 돌아가면서 스캐닝을 하고 한 class당 하나씩 보낸다.

우선순위는 모두 동일하게 갖고 단지 class를 구분해주었다.

각각의 class에 대해서 비슷한 정도의 bandwidth를 제공하겠다는 장점이 있다.

 

▶ Weighted Fair Queueing

Round Robin을 조금 일반화 시킨 방식이다.

각각의 class는 한 cycle 별로 가중치가 붙은 양만큼 service를 받는다.

한 번 scan 했을 때 보내는 양이 Weight로 정해져있고 Weight가 크면 클수록 더 많이 보낼 수 있다.

Round Robin의 경우 Weight 모두 1로 같은 방식이라고 볼 수 있다.