네트워크 레이어는 Data Plane과 Control Plane으로 나눌 수 있다.
이 글에서 라우터~Middleboxes는 주로 데이터 플레인에 대한 내용이다.
그 이후는 주로 컨트롤 플레인에 대한 내용이다.

네트워크 레이어 개요

네트워크 레이어는 세그먼트(segment)를 송신호스트에서 수신호스트로 전달하는 역할을 담당한다. 두 호스트의 행동을 자세히 기술하면 다음과 같다.

• 송신 호스트(sender) : 세그먼트를 데이터그램으로 encapsulate해 링크 레이어(link layer)로 전달
• 수신 호스트(receiver) : 세그먼트를 트랜스포트 레이어 프로토콜에 전달

네트워크 레이어 프로토콜은 모든 인터넷 장치(호스트, 라우터)에 존재한다. 특히 라우터는 네트워크 레이어를 동작시키는 핵심 요소이다. 라우터가 하는 일을 개략적으로 살펴보면

• IP 데이터그램의 모든 헤더 필드를 확인해 적절한 곳으로 전달
• 전달경로를 따라 데이터그램을 인풋 포트에서 아웃풋 포트로 전달한다.

네트워크 레이어의 구분

• Data Plane : 라우터 단위의 동작이다. 라우터에 들어온 패킷이 어디로 나갈지 결정한다.
• Control Plane : 네트워크 단위의 동작이다. 데이터그램의 경로를 결정한다.
  • Per-router routing : (대체로) 각 라우터가 개별 알고리즘을 돌려 경로를 결정하고 포워딩테이블에 내용 기록.
  • SDN(Software Defined Networking) : 중앙의 remote controller가 경로를 계산해 라우터의 CA(Control Agent)로 내려줌. 라우터는 내려받은 내용을 포워딩 테이블에 기록.

즉, 전통적인 라우터는 데이터플레인과 컨트롤플레인을 모두 내장하고 있다. 새로운 라우터는 이와 다르게 데이터플레인만 가질 수도 있다. (컨트롤플레인의 역할은 원격지의 컴퓨터가 담당하므로)

네트워크 레이어 역할

네트워크 레이어는 대표적으로 두 개 역할을 수행한다.

• forwarding : 데이터 플레인이 하는 일. 라우터의 인풋포트로 들어온 패킷을 적절한 아웃풋포트로 내보내는 것
• routing : 컨트롤 플레인이 하는 일. 라우팅 알고리즘을 돌려 패킷의 출발지-목적지 경로를 결정하는 것

여기서 컨트롤 플레인이 라우팅 알고리즘을 돌려 경로를 결정하고 나면(라우팅) 그 내용은 forwarding table에 기록된다. 데이터 플레인은 포워딩 테이블 내용을 살펴보고 가장 적절한 포트로 패킷을 내보낸다(포워딩).

네트워크 서비스 모델

인터넷 서비스 모델로 세 가지가 있다.

• best-effort : 대역폭, 손실, 순서, 타이밍 보장 못함
• Intserv Guaranteed : 대역폭, 손실, 순서, 타이밍 보장
• Diffserv : 트래픽별로 차별화된 서비스 제공 (타이밍은 보장 못하고, 나머지는 상황봐서 해줌)

이 중 Intserv Guaranteed는 IP로는 실현이 어렵다. 로컬에서는 가능할 수 있겠으나 글로벌에서는 지원이 어렵다.

best-effort가 일반적인데 아래 특징이 있어 좋다/나쁘다를 쉽게 판단할 수 없다.

• 동작원리가 단순하다
• 대역폭 프로비저닝 하면 보통은 리얼타임 애플리케이션에서도 쓸만하다.
• 복사본이 클라이언트 주변에 이미 있다.
• 탄력적 서비스를 지원하는 혼잡 제어 기능이 있다.

라우터

라우터는 input port -- fabric -- output port / routing processor로 나누어 살펴볼 수 있다. (패브릭은 데이터가 옮겨다니는 라우터 내부로 생각하면 된다. 이름이 저런건 특별한 이유가 없다. 그냥 레거시이다.)

input port

인풋포트의 구조를 살펴보면 아래와 같다.

+------------+       +-------+       +-------+
|    line    | ----> | link  | ----> | queue | ---> (fabric)
| termination|       | layer |       |       |
+------------+       +-------+       +-------+

• line termination(physical layer) : 들어온 아날로그 신호를 디지털로 변환한다.
• link layer protocol : 일반적으로 이더넷이다.
• buffer
  • 큐잉 : 스위칭 속도보다 들어오는 속도가 빠르면 버퍼링해서 좀 늦게 받는다.
  • 포워딩 (decentralized switching)
    • destination-based forwarding : IP주소만 보고 나갈 포트 결정
    • generalized forwarding : 몇층이든 있는 헤더 다 까서 나갈 포트 결정

output port

인풋포트랑 반대로 생겼다.

+--------+       +-------+       +-------------+
| queue  | ----> | link  | ----> | line        | ---> 바깥
|        |       | layer |       | termination |
+--------+       +-------+       +-------------+

스위칭 패브릭이 내보내는 속도가 link transmittion rate보다 빠르면 큐잉한다.
링크 레이어는 일반적으로 이더넷이다.
라인 터미네이션은 디지털신호를 아날로그로 바꾼다.

switching fabric

스위칭 패브릭은 인풋으로 들어온 패킷을 실제로 아웃풋으로 보내는 동작을 한다.

• 성능지표 Switching Rate : (I/O 포트 라인 개수) * (패브릭으로 들어오는 속도)
  • e.g.) 인풋포트 N개, 아웃풋포트 N개, 패브릭으로 들어오는 속도 R bps이면 --> 이상적인 경우 값은 NR

패브릭은 대표적으로 아래 세 가지 종류가 있다. 아래로 갈 수록 빠르다.

• memory : 그냥 컴퓨터다. 인풋포트로 들어온 패킷 내용 메모리에 복사한다. 내보낼 때는 메모리에 있는 내용 빼서 아웃풋포트로 보낸다.
• bus : 인풋/아웃풋 포트들이 하나의 버스를 공유한다. 자연히 스위칭 속도는 버스 대역폭에 의해 제한된다. (bus contention)
• interconnection network : 이거 빠르고 좋다. (예시 : Crossbar, Clos network)
  • multiple switch : 입력포트에서 데이터그램 분할하고 아웃풋포트에서 다시 조립

(interconnection network - cross bar)

인풋포트 1 --------+-------+-------+
                  |       |       |
인풋포트 2 --------+-------+-------+
                  |       |       |
인풋포트 3 --------+-------+-------+
                  |       |       |
               아웃풋1  아웃풋2  아웃풋3
                 포트    포트     포트

queueing

인풋포트 큐잉과 아웃풋포트 큐잉이 발생할 수 있다.
큐잉을 하면 자연히 큐잉딜레이와 버퍼오버플로우에 따른 손실이 발생할 수 있다.

• 인풋 큐잉
  • 패브릭 처리속도가 인풋포트 속도보다 느리면 발생
  • HOL Blocking : 큐의 맨 앞 데이터그램이 뒤 데이터그램의 처리를 지연시키는 것(HOL : Head of the line)
• 아웃풋 큐잉
  • 아웃풋 포트가 내보내는 속도보다 패브릭 처리속도가 빠르면 발생
  • 어떤 패킷을 먼저 내보낼지 결정하는 것은 망 중립성과 관련됨 (Drop policy, scheduling discipline)

버퍼 크기를 정하는 일도 중요하다. 너무 많은 버퍼링은 지연을 증가시키기 때문이다. (예 : 긴 RTT가 주어지는 경우 리얼타임 앱의 응답성이 떨어진다) 아래와 같은 크기 결정 방법이 있다.

• RFC 3439 전통적 : ( 전형적 RTT인 250msec ) * ( link capacity )
• 최근 : $\frac{RTT \times C}{\sqrt{N}}$ (C:link capacity, N:The number of flows)

버퍼 공간은 유한하기 때문에 관리가 필요하다. 관리한다는 것은 아래 두 가지를 포함한다.

• drop : 버퍼가 가득찼을 때 어떤 패킷을 큐에 넣을지, 혹은 뺄지 결정
  • tail drop : 마지막에 온 패킷 버림
  • priority : 우선순위에 따라 패킷 버림
• marking : 혼잡 신호를 주기 위해 특정 패킷에 마킹(ECN, RED)

Packet scheduling

어떤 패킷을 먼저 제공할지 결정하는 것을 스케쥴링 한다고 표현한다.

• FCFS (First Come First Serve)
  • 먼저 왔으면 먼저 내보낸다.
• Priority
  • 큐를 두 개 만든다 : high pq, low pq
  • 높은 우선순위의 패킷은 high pq로 보낸다. 낮은 우선순위의 패킷은 low pq로 보낸다.
  • 각 실재하는 큐안에서는 별도의 스케쥴링 기법을 적용할 수 있다. (예시 : FCFS)
• RR (Round Robin)
  • 패킷의 종류(class)를 나눈다. 종류 개수만큼 큐를 만든다. (우선순위 아님)
  • 들어온 패킷은 종류에 따라 그에 맞는 큐로 넣는다.
  • 각 큐별로 골고루 서빙한다.
• WFQ (Weighted fair queueing)
  • 큐를 여러 개 만들고 각각 가중치를 부여한다.
  • RR과 유사하게 동작하는데, 가중치가 좀 더 클수록 많이 서빙한다.

IP : Internet Protocol

IP Datagram Format

각 줄은 4바이트이다.
IP 데이터그램의 필수 항목은 5줄이므로 헤더로 20바이트를 잡아먹는다.

이 단계에서 오버헤드는 다음과 같이 계산된다.
( TCP의 20바이트 ) + ( IP의 20바이트 ) + ( APP의 오버헤드 )

아래 포맷에서 header length와 데이터그램의 length는 바이트 단위이다.

<---------------------   32 bits ------------------------->
<------------ 16 bits ---------->
+---------------------------------------------------------+
| ver | head len | service type |         length          |
+---------------------------------------------------------+
| idenfier                      | flags | fragment offset |
+---------------------------------------------------------+
| TTL    | Upper layer protocol | header checksum         |
+---------------------------------------------------------+
| source IP address                                       |
+---------------------------------------------------------+
| destination IP address                                  |
+---------------------------------------------------------+
| option                                                  |
+---------------------------------------------------------+
| payload                                                 |
+---------------------------------------------------------+

IP Addressing

IP주소는 호스트나 라우터 인터페이스의 (일반적으로) 32-bit 식별자이다.
여기서 인터페이스란 호스트/라우더/피지컬링크 사이의 연결부를 뜻한다.

컴퓨터로 예를 들면 유선랜카드, 무선랜카드가 각각 인터페이스이다.
각 인터페이스는 각각 IP주소를 부여받는다.

Subnet

서브넷은 전체 망의 부분망이다. 라우터 없이 통신 가능한 섬과같은 단위를 서브넷이라 할 수 있다. 각 서브넷은 네트워크의 IP주소를 갖는다. 이를 알기 위해서는 IP주소의 구조를 살펴보아야 한다.

1. 가정
   → 어떤 서브넷에 있는 호스트의 IP주소가 223.1.1.1/24라 하자. (CIDR)
2. 비트의 의미
   → 뒤에 붙은 /24는 앞에서 24개 비트는 서브넷을 나타내는 비트(=subnet part)임을 의미한다. 마지막 8비트는 서브넷 내의 호스트를 나타내는 비트(=host part)이다.
3. 사용가능한 IP 주소 구간
   → 즉, 이 서브넷은 223.1.1.0~223.1.1.255 구간의 256개 IP주소를 사용할 수 있다.
4. 최대 호스트 개수
   → 이 때 첫 번째 주소인 223.1.1.0은 어떤 서브넷을 나타내는 네트워크 IP, 마지막 주소 223.1.1.255는 브로드캐스트 IP이다(예약 주소). 실질적으로 호스트들에 부여할 수 있는 IP주소는 1~224 구간의 224개이다.

IP 체계 : Class

이런 IP주소를 표현하는 체계가 두 가지 있다.

• Class
• CIDR (Classless Inter Domain Routing)

먼저 클래스 체계를 살펴보면 다음과 같다.

• 32-bit IP는 5개 클래스로 분류할 수 있다.

  • A : 1바이트 네트워크부, 3바이트 호스트부, 첫 옥텟 0~127
  • B : 2바이트 네트워크부, 2바이트 호스트부, 첫 옥텟 128~191
  • C : 3바이트 네트워크부, 1바이트 호스트부, 첫 옥텟 192~223
  • D : 0바이트 네트워크부, 4바이트 호스트부, 첫 옥텟 224~239 (멀티캐스트용)
  • E : 0바이트 네트워크부, 4바이트 호스트부, 첫 옥텟 240~255 (연구용)

• 외부와 분리된 서브넷을 사설망이라고 부른다. 이 안의 호스트에는 사설(Private) IP를 부여할 수 있다. 정해진 그 구간을 나열하면 다음과 같다.

  • A : 1.0.0.0 ~ 10.255.255.255
  • B : 172.16.0.0 ~ 171.31.255.255
  • C : 192.168.0.0 ~ 192.168.255.255

CIDR는 클래스에 구애받지 않고 네트워크부와 호스트부를 분할해 사용하는 기법이다. 예를 들면 아래와 같다.

• 22.22.22.5/24 라는 IP는 앞의 24비트는 네트워크부, 뒤 8비트는 호스트부

DHCP

Dynamic Host Configuration Protocol

호스트가 어떤 네트워크에 참여하면 그 안의 DCHP서버로부터 동적으로 IP주소를 할당받는다. 그 과정을 살펴보면 아래와 같다.

1. 호스트→DHCP : DHCP discover (DHCP있냐? 있으면 IP주소좀 주셈)
2. DHCP→호스트 : DHCP offer (ㅇㅇ있음. 주소 이거 어떰?)
3. 호스트→DHCP : DHCP request (ㅇㅋ 좋음 주셈)
4. DHCP→호스트 : DHCP ack (ㅇㅇ 쓰셈)

자신의 IP주소 외에도 호스트가 DHCP 서버로부터 얻을 수 있는 정보가 있다.

• 첫 번째 hop 라우터의 IP주소
• DNS서버의 이름, IP주소
• 네트워크 마스크 (서브넷 마스크)

Hierarchical Addressing

IP주소 구간(블록)의 할당은 ICANN 아래의 IANA가 담당한다.
5개의 RR(Regional registries)에게 IP블록을 주면, RR은 다시 지역 Registry에게 할당한다. 이 주소는 다시 그 아래의 고객들에게로 할당된다.

네트워크가 자신의 IP를 부여받으려면 ISP로부터 주소 공간을 할당 받아야 한다. 망 자체가 계층적으로 구성되어 있기 때문이다. 그림으로 나타내보면 각 기관 네트워크는 사실상 ISP의 부분망이다.

• route aggregation : ISP는 인터넷에게 "이 숫자로 시작하는 IP주소로 가는 패킷은 다 나한테 보내셈"과 같이 경로를 알려야 한다. 이후 ISP에서 각 네트워크로 패킷을 전달하게 된다.

기관이 ISP를 다른 회사로 바꾸는 경우가 발생할 수 있는데, 이 때 네트워크 IP주소는 일반적으로 그대로 들고 간다. 이 경우 옮겨온 ISP가 인터넷에 advertising하는 내용이 바뀐다.

• 이전에 있던 ISP : 변화없음
• 새로 옮겨온 ISP :
  • (원래)이 숫자로 시작하는 IP주소 패킷 다 나한테 주셈
  • 또는!! (그 기관의 IP주소)로 가는 패킷도 나한테 주셈

NAT

Network Address Translation

공인IP주소(인터넷)와 사설IP주소(내부망)를 서로 변환시켜주는 기능이다.

예를 들어 사설망 내에 100억개 컴퓨터가 있다고 하면, 이 100억개의 컴퓨터 각각에 공인 IP주소를 주는 대신 하나의 공인IP만 주고 외부망과 통신을 시켜버리는 것이다. 이것이 가능하도록 하기 위해 NAT를 둔다. 이러면 IP주소도 아끼고 보안상 이점도 얻을 수 있다.

NAT는 구체적으로 아래와 같이 동작한다.

• 나가는 데이터그램에 대해
  • Src IP주소를 NAT의 IP주소로 바꾼다.
  • Src port를 NAT가 송신호스트와 1:1대응되는 임의의 port로 바꾼다. * NAT translation table에 이 내용을 기록한다.
• 들어오는 데이터그램에 대해
  • NAT translation table을 확인해 해당하는 내부 호스트로 전달한다.

그러나 NAT은 IP주소 고갈에 대한 근본적인 해결책이 아니다. NAT는 3층에서 동작한다. 그런데도 4층의 할 일인 포트 지정을 뺏어와 자기가 해버린다. 또, NAT없이는 외부에서 내부망 호스트에 접근할 방법도 없다. 그렇지만 이미 많이 쓰이고 있어서 어쩔 수가 없다. 아직까진 쓸만하니까 쓴다.

IPv6와 Tunneling

32-bit IPv4의 주소는 이미 고갈되었다. 표현상 없다는게 아니고 정말로 없다. 텍스트 그대로 다 할당해버렸다.
그래서 표현 가능한 주소의 범위를 넓히면서 네트워크 성능을 개선하기 위한 목적으로 IPv6가 연구되고 사용되고 있다.

IPv4의 데이터그램 포멧과 비교해보면 checksum, fragmentation/reassembly 정보, option항목이 없다.

|<------------- 32 bits ------------>|
+------------------------------------+
| ver | priority | flow label        |
+------------------------------------+
| payload len | next hdr | hop limit |
+------------------------------------+
| source address  (128-bit)          |
|                                    |
+------------------------------------+
| destination address (128-bit)      |
|                                    |
+------------------------------------+
| payload                            |
+------------------------------------+

IPv6으로 언젠가 넘어가기는 해야하는데 당장 IPv4의 사용을 중단할 수다. IP는 수많은 네트워크 요소를 떠받치는 인프라와 같은 존재이기 때문이다. 그래서 전이 과정의 대응책으로 Tunneling을 사용한다. 터널링은 IPv4패킷의 페이로드에 IPv6패킷을 통째로 박아 전송하는 것이라 요약할 수 있다.

라우터는 크게 세 가지로 나누어볼 수 있다.

• IPv4만 이해하는 라우터
• IPv6만 이해하는 라우터
• 둘 다 이해하는 라우터

아래와 같이 라우터와 IPv4네트워크가 배치되어 있다고 하자.
라우터 1에서 4로 어떤 정보를 전달하고 싶다면 터널링이 필요하다.

• 1에서 2로는 IPv6 패킷 그대로 넘긴다.
• 2에서 IPv4 네트워크로 IPv4 포맷에 담아 넘긴다. (Src는 2, Dest는 3)
• IPv4 네트워크에서 3으로 IPv4 패킷을 넘긴다.
• 3은 이게 v6이라는걸 알고 있다. 페이로드에 있는 v6패킷을 꺼내서 4로 넘긴다.

   1        2                           3        4
IPv6만 -- 둘 다 ---( IPv4 네트워크 )--- 둘 다 -- IPv6만
 ㄱㄴ      ㄱㄴ                         ㄱㄴ      ㄱㄴ

Forwarding

앞서 라우터의 input port 부분에서 두 가지 포워딩 방식이 있음을 살펴보았다.

• destination-based forwarding : 비교적 전통적
• generalized forwarding : flow

destination-based forwarding

포워딩 방식 중 destination-based forwarding의 경우 Longest prefix matching이라는 방법으로 IP주소를 이용해 나갈 포트(링크 인터페이스)를 결정한다.

포워딩 테이블은 아래와 같이 주소 범위에 대해 내보낼 포트 번호가 기록되어있다. (편의를 위해 8-bit IP를 쓴다고 가정하자)

도착지 주소 범위	아웃풋포트 번호
0000 0000 ~ 0000 1111	0
1100 0000 ~ 1100 1111	1
1101 0000 ~ 1111 1111	2

위 테이블은 아래와 같이 주소 범위를 prefix로 다시 나타낼 수 있다.
*이 아닌 숫자 부분이 prefix이고, 이 부분을 도착지 IP주소와 비교한다.

도착지 주소 프리픽스	아웃풋포트 번호
0000 ****	0
1100 ****	1
11** ****	2

• 만약 패킷을 보낼 주소가 0000 1010이라면 프리픽스 0000와 비교되어 0번 포트로 나간다.
• 주소가 1100 1111이면 적용 가능한 프리픽스가 1100과 11두 개이다. 하지만 더 긴(Longest) 1100을 적용해 1번 포트로 나간다.
• 주소가 1111 1111이면 고민 없이 2번 포트로 나간다.

longest prefix matching은 TCAMs(ternary content addressable memories) 를 사용해 수행되는데, 이 기술은 테이블 사이즈가 몇이든 1클럭사이클에 아웃풋 포트를 결정한다. TCAMs을 쓰는 시스코 제품으로 Cisco Catalyst가 있다.

Generalized Forwarding

match + action : 들어오는 패킷의 비트와 그에 대한 액션을 매칭시켜놓은 것. 프로그래밍 가능한 네트워크의 간단한 형태이다.

앞서 살펴본 forwarding table은 flow table이라고도 부른다.

• flow : 헤더의 필드 값에 의해 정의된 요소

일반화된 포워딩을 구성하는 packet-handling 규칙은 다음과 같다.

• match : 패킷 헤더의 값과 어떤 값이 일치하는지 확인
• action : match된 패킷에 대해 할 일 (drop, forward, modify, send to controller)
• priority
• counters

일반화된 포워딩의 대표적인 예시가 OpenFlow이다. 오픈플로우에서 flow table의 엔트리는 다음과 같이 구성되어있다.

• match (Ingress 포트번호, link/network/transport 헤더의 필드들)
• action
• stats

여기서 OpenFlow는 match, action에 다른 값을 줌으로써 아래의 네 가지 역할을 모두 수행할 수 있다. match+action의 개념 자체가 추상적이기 때문이다.

• 라우터
• 스위치
• 방화벽
• NAT

Middleboxes

RFC 3234 : any intermediary box performing functions apart from normal, standard functions of an IP router on the data path between a source host and destination host

NAT, 방화면, IDS, 로드 밸런서, 캐시서버 등은 모두 미들박스이다.

• 미들박스는 초기에는 black box 하드웨어 솔루션이었다가, open API구현에 따라 white box 하드웨어로 전환된다.
• 미들박스 관리를 위한 SDN, NFV (** NFV는 SDN의 구현사례로 볼 수 있음)

End-End argument, The IP hourglass

네트워크의 지능부는 중간보다는 끝단에 구현되는 것이 좋다고 말한다.
링크

The function in question can completely and correctly be implemented only with the knowledge and help of the application standing at the end points of the communication system. Therefore, providing that questioned function as a feature of the communication system itself is not possible. (Sometimes an incomplete version of the function provided by the communication system may be useful as a performance enhancement.)

링크

3층 IP는 어느 곳에나 있으므로 간단하게 구현되어야 하지만 현대 네트워크는 3층에 많은 기능을 추가했다. (NAT, 방화벽, NFV, 캐싱, ...)
근본적으로는 모두 SDN으로 해결되어야 할 문제이다.

네트워크의 지능

과거 전화만 있던 시절에는 네트워크의 지능이 중앙(전화국)에만 있엇다.
그러나 현재는 네트워크 그 자체도, 끝단도 지능을 가지고 있는 상황이다.

---

여기부터 Control Plane에 대한 내용을 주로 적는다.

---

Routing Protocols

라우팅 프로토콜의 목표는 라우터를 통해 송신 호스트에서 수신 호스트로 이르는 좋은 경로를 찾는 것이다. 좋은 경로는 판단 기준에 따라 달라진다. 어느 조직에서는 가장 비용이 적은 것이 좋을 수 있고, 어느 조직에서는 돈이 얼마가 들든 빠른 것이 좋은 경로일 수 있다. 이런 경로는 송신-수신 호스트 사이 라우터의 나열로 표현할 수 있다.

라우팅 알고리즘의 분류 기준

• 경로의 변화 주기 : static / dynamic
• 적용 범위 : decentralized(local) / global

LS (Link State)

LS는 global, centralized 알고리즘이다. (Dijkstra)

• 특징 : 한 노드로부터 다른 모든 노드로 가는 경로를 계산한 포워딩 테이블을 모든 노드 각각이 들고 있다. (같은 정보를 들고 있는 셈)
• 한계 : 다익스트라 알고리즘을 돌리는데, k번 돌리면 k개 목적지로의 비용을 알 수 있다. 때문에 라우터의 개수가 유한한 네트워크에서 사용할 수 있는 방법이다.
  • 알고리즘 복잡도 : O(n^2) ~ O(nlogn)
  • 메시지 복잡도 : O(n^2)
• 표기
  • $C_{x,y}$ : 노드 x에서 y로의 비용 (인접노드가 아니면 INFINITE)
  • D(V) : 출발지부터 도착지V까지 현재 계산된 최소비용
  • p(V) : 최단경로의 도착지 바로 직전 노드
  • N' : 최단경로 내의 노드 집합

DV (Distance Vector)

DV는 local, decentralized 알고리즘이다. (Bellman-Ford)
벨만포드 방정식 $D_{x}(y) = min_{v} \{C_{x,v} + D_{v}(y)\}$에 기초한다.

• distance vector : 대충 나와 인접 노드 사이의 비용이다.
• 동작 방식
  • 인접 노드로부터 DV나 메시지를 받기까지 대기
  • 인접 노드로부터 DV를 받으면 자신의 DV(비용)를 다시 계산
  • 비용 변화가 있으면 인접 노드로 DV 전파
• 특징
  • iterative, asynchronous
  • distributed, self-stopping
• routing loops : DV알고리즘이 다른 노드의 DV를 그대로 받는 특징에서 기인하는 문제. 잘못된 경로정보를 토대로 갔다가 되돌아오는 일을 반복하는 현상이다.

Scalable Routing

• AS (Autonomous system, Domain) : 한 주체가 관리하는 라우터와 서브 네트워크의 집합
• 게이트웨이 라우터 : 다른 AS과 연결되는 라우터
• AS 라우팅 기법의 분류
  • Intra-AS : AS 내부에서의 라우팅.
  • Inter-AS : AS 간 라우팅

라우터의 포워딩 테이블은 상기 두 분류의 라우팅 알고리즘에 의해 결정된다.

• Intra-AS 알고리즘 : AS 내 도착지에 대한 엔트리 결정
• Intra-AS + Inter-AS 알고리즘 : AS 바깥 도착지에 대한 엔트리 결정

Intra-AS Routing

• RIP : classic DV (30초마다 DV 교환)
  • RIP v1 : 최대 15개 라우터
  • RIP v2 : 최대 255개 라우터
• EIGRP : DV Based
• OSPF : classic link-state routing
  • 특징
    • 각 라우터는 IP프로토콜 단에서 같은 AS내 모든 라우터에게 OSPF LS advertisement를 전달
    • 각 라우터는 완전한 토폴로지를 갖고 있음. 다익스트라로 라우터 별 포워딩 테이블 계산.
  • Hierarchical OSPF : 링크스테이트 계산을 area안에서만 한다.
    • backbone area : Boundary Router,
    • local area : Area Border Router, Local Router, Internal Router
• IS-IS Protocol : OSPF와 거의 비슷 (IS : Intermediate System)

Inter-AS Routing

BGP(Border Gateway Protocol)는 사실상 Inter-domain routing의 표준 프로토콜이다.

BGP는 eBGP와 iBGP로 구성된다.

• eBGP : 인접 AS들로부터 서브넷 도달가능성 정보 획득.
  • 피어 : eBGP로 연결된 두 라우터는 peer라고 한다.
  • 교환 : 피어의 두 BGP라우터는 semi-permanent TCP 연결 위에서 BGP 메시지를 교환
• iBGP : AS 내부 라우터에게 eBGP로 얻은 정보를 전파

BGP 메시지의 종류는 아래와 같다.

• OPEN : BGP Peer간 TCP연결 체결
• UPDATE : 새로운 경로정보 전달
• KEEPALIVE : 메시지 교환 없어도 연결 살려두기
• NOTIFICATION : 에러 알림 또는 연결 닫기

BGP advertised routes는 아래 항목으로 구성된다.

• prefix : 목적지
• attribute :
  • AS-PATH(목적지로 가기 위해 지나는 AS 목록)
  • NEXT-HOP Router : 다음 AS로 가기 위한 특정 라우터

BGP상의 라우터는 Policy-based routing을 한다.

• 도달가능성 정보를 받는 게이트웨이 라우터는 import policy에 따라 이 경로를 사용할지 말지(즉, iBGP로 AS내부에 전파할지) 여부를 결정한다.

AS의 내부 라우터는 Hot potato routing을 사용할 수 있다. 이는 전체 경로 거리에 관계없이 Domain내 비용이 가장 작은 로컬 게이트웨이를 선택하는 방법이다.

SDN (Software Defined Networking)

사용이유

• 네트워크 관리 쉬움 : 유연한 트래픽 흐름(NAT, ACL), 네트워크 관리자 숙련도에 따른 설정의 적합도 차이 감소(avoid misconfiguration)
• centralized table-based 포워딩은 라우터를 프로그래밍 가능하게 한다.
• 공개된 구현 : 서드파티 개발사가 표준에 입각한 제품을 개발하면 혁신 속도가 빠름

구성요소

• Data-plane switches : 라우터들. 컨트롤러 입장에서는 관리되는 장치들이다. southbound API로 SDN컨트롤러와 연결.
• SDN Controller(Network OS) : 네트워크 상태정보 유지. 논리적으로는 하나지만 물리적으로는 분산된 시스템으로 구현됨(성능, 확장성, 결삼내성, 강건함을 위해)
  • Interface layer to network control apps (abstraction API)
  • network-wide state management (distributed database)
  • communication
• Network-control apps : 컨트롤러가 제공하는 서비스와 API로 컨트롤 기능 구현. northbound API로 SDN컨트롤러와 연결

OpenFlow protocol

컨트롤러와 스위치 사이에서 동작하는 프로토콜. TCP로 메시지 교환.

OpenFlow메시지는 세 가지 종류가 있음

• controller-to-switch
  • packet-out
  • feature
  • configure
  • modify-state
• switch-to-controller(asynchronous)
  • packet-in
  • flow-removed
  • port status
• symmetric

SDN Controller 예시

• ODL (OpenDayLight)
• ONOS (Open Network OS)

ICMP

Internet Control Message Protocol

네트워크 레벨 정보를 주고받기 위해 호스트, 라우터가 사용.
3층이긴 한데 IP보다 위에 있다.

traceroute

udp 세그먼트 셋을 전송한다.
1번째 셋은 TTL=1, 2번째 셋은 TTL=2, n번째 셋은 TTL=n

라우터는 TTL Expired이면 데이터그램을 버리고 source로 ICMP 메시지를 전송. 메시지를 받은 source는 RTT 기록.

TTL이 도착지까지 가기 충분해져서 도달 하면 동작을 멈춤.

Network Management

Autonomous System(Network)는 수많은 장비의 집합.
네트워크를 관리한다는 것은 아래 내용을 포함

• 서버 관리 (앱+사람)
• 네트워크 관리 프로토콜 (e.g., SNMP)
• 관리되는 장치
• 데이터 (관리받는 데이터, 통계)

네트워크 관리자가 각 장비를 관리할 수 있는 접근법은 아래와 같음

• CLI
• SNMP/MIB : 좀 옛날
  • 1:1관리(모니터링)에 적합. massive한 관리 어려움.
• NETCONF/YANG : 2010년대
  • 다중관리에 적합.

SNMP / MIB / SMI

SNMP는 프로토콜. MIB는 관리용 데이터베이스. SMI는 데이터 정의어.

• SNMP Protocol mode
  • request/response mode ( agent <--> controller )
  • trap mode ( agent -> controller )
• SNMP msg type
  • "manager-to-agent" function
    • GetRequest
    • GetNextRequest
    • GetBulkRequest
    • SetRequest
  • "agent-to-manager" function
    • Response
    • Trap
• SNMP msg format
  • Trap메시지와 그 외 메시지 포맷 다름.
  • 헤더 뒤에 { name, value } pair가 온다.
• MIB : Management Information Base
  • 동작할 때 발생하거나 설정된 값

NETCONF/YANG

NETCONF : SNMP의 단점 보완. NETCONF의 문법은 YANG이 정의

• actions : retrieve, set, modify, activate conf
• operations
  • <get-config> : 설정값
  • <get> : 설정값, 데이터
  • <edit-config>
  • <lock>, <unlock>
  • <create-subcription>
  • <notification> : SNMP의 TRAP과 유사
• atomic-actions
• RPC

YANG : NETCONF와 함께 쓰이는 데이터 모델링 언어

• NETCONF의 구조, 문법, 의미 정의.