Routing

Intro

Routing은 우리가 주고 받고자 하는 데이터를 전달하기 위해서 목적지를 찾아나가는 과정이다. 어떻게 해서 IP를 통해서 목적지를 찾아 데이터가 이동할 수 있는지를 알아볼 것이다.

Routing Vs Switching Vs Forwarding

매우 유사한 개념이지만 이에 대해서 알아두고 가는 것이 중요하다.

• Switching : Inbound Interface에서 Outbound Interface로 packet들을 전송 시키는 것을 의미한다. 즉, 하나의 기기 내부에서 발생하는 일을 의미하는 경우가 많다.
• Forwarding : 한 장치가 목적지로 가는 경로에 있는 다음 장치로 packet을 전송하는 것을 의미한다. 하지만, Switching과 동일한 뜻으로도 많이 사용된다.
• Routing : 논리적으로 Network Topology를 학습하여, 이를 기반으로 최적의 경로를 찾아 이동하는 것을 의미한다. 따라서, 전체적인 길을 찾는 것과 이를 따라가는 과정을 의미한다.

Switch

Switch를 부르는 명칭 역시 다양하고, 상황에 따라 역할도 어느정도 다르기 때문에 정리를 한다. 대게 OSI 7계층에 기반하여 분류를 하는 것이 일반적이다.

• L2 Switch : Ethernet Switch를 대게 의미하며, 일반적으로 Switch라고 부르는 장치가 이를 의미한다. MAC 주소에 기반한 Forwarding을 수행하는 장치이다.
• L3 Switch : Router라고도 불리는 장치로, IP 주소에 기반하여 최적의 경로를 학습하는 알고리즘을 포함한 Switch이다.
• L4 Switch : Port 번호를 기반으로 Switching을 수행하는 장치로 대게 Machine 내부에서 Software적으로 구현하는 Switch일 가능성이 높다.
• L7 Switch : Application Level에서 모든 Traffic을 관리 및 URL, Cookie 기반으로 자유롭게 Switching을 수행할 수 있다. 일반적으로 생각하는 Load Balancing과 같은 작업도 쉽게 구현이 가능하다. 마찬가지로 Software적으로 구현되어진다.

Routing 영역

우리가 Routing을 수행하는 경우에 case는 크게 두 가지로 나뉘어진다. AS 내부인가? 외부인가? 이다. AS란 Autonomous System의 약자로 하나의 기관에서 관리하는 IP subnet들과 Router들의 집합을 의미한다. 각 AS는 고유 식별값인 ASN(AS Number)에 의해서 식별되며 각 기업, 통신 사업자, 대학, 언론 기관 등이 이를 갖고 있다. 이렇게 같은 AS 내부에 존재하는 기기 간의 Protocol을 Interior Gateway Protocol(IGP)이라고 하고, 그렇지 않은 경우 Exterior Gateway Protocol(EGP)라고 한다.

Base

각 Routing Protocol에 대해서 자세히 살펴보기에 앞 서 기본적인 Network 환경에 대한 이해가 필요하다. 그러기 위해서 아래 개념에 대한 숙지 여부를 확인하자.

1. MAC/IP
   MAC은 특정 Network 연결 단자(Network Interface Card, NIC)에게 주어지는 고유값으로 볼 수 있다. 그렇기에 하나의 기기는 하나 이상의 NIC를 가진다면, 하나 이상의 MAC address를 갖게 되고, 이에 따라 특정 기기를 정확하게 가르키기 위해서 IPv4 주소를 사용한다. 그러나, IP 부족 현상으로 인해 현재에는 내부 네트워크에서는 private IP라는 별도의 영역으로 표기를 하고, 네트워크의 대표 IP를 내세우는 방식으로 변화하였다. 아직까지는 큰 문제가 발생하고 있지 않지만, 후에는 IPv6로 넘어가야할 수도 있다.
2. Broadcast Address
   Network에서 Traffic을 Network에 연결된 모든 Node에게 보내야할 경우가 있다. 이때, 만약 모든 IP address를 1로 표기한다면, 이는 모든 Network를 향한 Broadcast Request로 받아들여진다. 초기에 Network에서는 모든 요청이 Broadcast되고 이를 받은 사용자가 취사 선택하는 구조를 가졌었지만, Broadcast 요청이 loop가 생기면서, Network 전체를 마비시키거나 보안상/성능상의 문제로 인해 Broadcast되는 영역을 줄이고자 한다.
3. Subnet
   Broadcast Traffic이 많아진다는 것은 Network의 혼란을야기할 수 있다. 따라서, 이러한 Broadcast의 영역을 최소한으로 표현하고자 Subnet을 정의하였다. 즉, Network를 더 작은 Subnetwork로 나누자는 것이다. 이를 표시하기 위해서 Subnet Mask라는 것을 활용하며, Network prefix를 이용하여, 영역을 명확하게 구분한다. 그리고 이를 통해서 나뉘어진 Network 끼리는 다른 Broadcast 영역을 가지게 되고, 서로 Broadcast message가 전파되지 않는다. 이에 따라 나뉘어진 Network의 가장 끝(All One Address)는 Broadcast address가 되고, 가장 처음(All Zero Address)는 Network의 주소를 가르키는 값으로 사용된다.
   현대에는 이러한 Subnet을 표기할 때, 별도의 Public IP를 사용하지 않고, Private IP를 사용하는 것이 일반적이다. 이를 통해서 더욱 IP address를 절약할 수 있다. 이를 위해서는, 송신 시 Router IP로 Private IP를 바꾸고, 응답이 돌아왔을 때 원래 Node로 돌려주기 위한 번역 과정이 필요한데 이때 NAT(Network Address Translation) 기술이 사용된다.
4. CIDR
   Subnet을 나눌 때, 위에서 IP를 구분할 때 사용하는 A(8bits prefix), B(16bits prefix), C(24bits prefix) class로 나누어 사용했었는데, 이러한 범위가 Subnet에게는 너무 컸기 때문에 이를 임의의 bit 단위로 구분할 수 있도록 하는 방법이다. 이를 통해서, Subnet 범위를 더 세분화할 수 있다.
5. Loopback Address
   자기 자신을 가르키는 addrsss로 대게 127.0.0.1을 사용하는데, 필요에 따라 특정 IP를 별도로 자기 자신을 가르키도록 설정하는 것도 가능하다. 이는 Network Testing을 수행할 때 사용되는데, Router의 Loopback Address와 외부 장치 IP Address에 ping을 보내며 통신 상태를 확인할 수 있다.
6. Default Gateway
   Node에 가장 근접한 Router의 주소를 의미하며, 이를 통해서 Internet에 연결된다.
7. Collision Domain / VLAN
   하나의 hub(Switch 이전에 널리 쓰이던 L2 장치, Switch Hub라고도 부름)로 연결된 장치는 전달되는 모든 packet을 해당 hub의 모든 port로 flooding(forwarding)하는데, 이는 Broadcasting과 같다고 볼 수 있다. 이러한 Broadcasting은 성능상으로도 보안상으로도 치명적이기 때문에, 이를 방지하기 위해서 나온 것이 VLAN이다. 기존의 Subnet의 L3에서의 Broadcasting을 막았다면, VLAN은 L2에서 이를 막기 위한 시도이다. Virtual LAN의 약자로 하나의 Switch가 각 Port마다 Collision Domain(L2 Broadcasting이 수행되는 영역)을 분리시킬 수 있는 방법이다. 이를 통해서, Broadcast의 범위를 더 잘게 조갤 수 있다.
8. ARP
   Address Resolution Protocol의 약어로, 하나의 Subnet 내에서 Broadcast를 이용해, 기기의 IP 주소를 통해서 해당 기기의 MAC address를 알아내는 Protocol이다. 예시로, Default Gateway의 IP 주소를 통해서 해당 Router의 MAC address를 찾을 때 사용할 수 있다. 또한, 일반 Node에서 Server로 Request를 보낼 때에도 MAC address는 모르기 때문에, 이를 통해서 MAC address를 찾는다. 이러한 Traffic은 최소화하는 것이 좋기 때문에 이를 위한 응용 기술도 존재한다.
   • ARP Cache : 데이터를 전송할 때마다 ARP를 수행하는 것은 비효율적이기 때문에, IP와 대응하는 MAC 주소를 저장한 Mapping table을 저장해두는 것을 의미한다. PC 환경에서는 Network의 변경이 적기 때문에 20분 단위로 재실행하지만, mobile 장치에서는 30초 단위로 단축되었다.
   • Proxy ARP : Router가 수신 Host까지의 경로를 이미 알고 있는 경우에, 송신 Host에게 수신 Host에 대한 MAC address가 아닌 Router의 MAC address를 전송하는 방식으로 Router에게 전적인 대리 작업을 맡기는 것이기에 보안상에서는 좋지 않을 수 있다.

Routing Protocol

가장 기본적으로 모든 Routing 장비에서 기본적으로 적용되는 Protocol(STP)를 적용하여 Topology에서 Loop를 제거하는 과정을 거친다. 이후에는 Routing Table(RIB)와 Forwarding Table(FIB)을 구축하는 것이 가장 큰 목표가 된다. Routing Table은 특정 Router 와 연결된 Router의 정보를 Protocol마다 정의하여 보관하는 것이다. Router에서 Routing Table은 사용하는 Routing Protocol의 수 만큼, 즉 여러 개 존재할 수 있다. 이러한 Routing Table들에 기록된 정보를 통해서, 단 하나의 Forwarding Table을 각 Router에서 구성하게 된다. (이때에 각 Protocol의 우선순위에 따라서 Forwarding Table이 구성된다.) 이는 실제로 어떤 Port로 어떤 packet이 들어왔을 때, 어떤 Port로 Forwarding 할 것인지를 기록해둔다. Routing의 종류는 위에서 보았던 IGP/EGP 뿐만 아니라 언제 설정 방법에 따라서 2 가지로 나뉘어진다. Traffic이 전달되기 이전에 관리자에 의해서 사전에 직접 Routing을 정의(Static Routing Protocol)하는 방법과 스스로 규칙에 따라 학습을 통해 최적 경로를 찾는 방법(Dynamic Routing Protocol)이 있다.

각 Routing Protocol을 알아보기 이전에 기본적으로는 다음과 같은 원칙을 따라야 한다.

1. Longest match Rule : Subnet mask가 긴 Protocol을 우선시한다.
2. AD(Administrative Distance) : Protocol간의 우선 순위에 따라서 우선 적용한다. 대게 Static Routing이 Dynamic Routing보다 우선시되어진다.
3. *Spanning Tree Protocol에 기반하여 먼저, Topology 내에 Loop를 제거해야 한다.

STP(Spanning Tree Protocol)

2계층 Protocol로 Collision Domain 내부에서 Broadcast Storm을 방지하기 위해서 Loop를 막는 것을 목표로 한다.

Graph 형태로 구성된 Network 장비 간의 연결을 Tree 형태로 재구성 해주면, Loop를 해결할 수 있으므로, 특정 Port를 Block하거나 Traffic이 오가는 것을 막는 등의 작업을 수행한다.

설명하기 앞서 기본적인 용어를 먼저 정의해야 한다.

1. Root Switch
   Tree를 구성할 때, 어떤 Switch를 root로 할 것인지에 대한 결정
2. Root / Designated / Alternated Port
   Root Switch로 선택되지 못한 모든 장비들은 Root Switch로 연결되는 port를 선정해야 한다. 이를 Root Port라고 하고, 그 반대 방향에 해당하는 Designated Port를 선정한다. 그리고, 이 둘에 포함되지 않는 Port는 Alternated Port로 분류되어서 일반 통신 시에는 Block되어 사용이 차단된다. 여기서 Root Port가 된다는 것은 해당 Port로 내보내면 결국에는 데이터를 성공적으로 보낼 수 있다는 확신을 가질 수 있다.

이제 Root Switch와 각 Port를 분류하기 위한 BPDU(Bridge Protocol Data Unit)을 알아야 한다. 이는 Spanning Tree를 구성하기 위해서 실제로 각 Switch가 주고 받는 Frame으로, Switch에 연결된 모든 Port에서 전송 또는 수신된다. 초기 Configuration을 수행하거나 Network 상태가 바뀌었을 때, 재합의 과정을 수행할 때 이 Data Unit을 각 Switch 간에 전송한다. 이때 포함되는 가장 중요한 정보가 Bridge ID이다. 이는 해당 Switch의 VLAN 번호, MAC address, 임의의 값에 의해서 결정된다. 여기서 Bridge ID가 가장 낮은 Switch가 Root Switch가 된다. 이것이 완료되면 이제 각 Switch의 각 Port를 식별하는 과정을 거쳐야 한다. 과정은 다음과 같다.

1. Bridge ID가 작은 Switch부터 Root Switch까지의 거리가 가장 짧은 Port는 Root Port가 된다. 만약 동일하다면 Bridge ID, Port ID를 비교하여 선택한다.
2. 하나의 Segment(Switch간의 연결)에 반드시 하나의 Designated Port가 존재하도록 한다. 즉, 두 개의 Switch가 연결되었고, 한 Switch에서 특정 Port를 Root Port로 정했다면, 다른 Switch에서는 이와 연결된 Port를 Designated로 지정해야 한다.
3. 어떠한 Port도 존재하지 않는다면, 남는 Port를 Designated Port로 지정하고, 이 반대 Port는 Alternated Port로 지정한다.

이 과정이 끝나면, 이제 각 Port는 5가지 상태로 분류되어진다.

1. Listening State(청취)
   Switch가 최초에 전원이 켜지면, 모든 Port는 Listening 상태에 들어간다. 그리고, 해당 Port가 만약 Alternated Port로 지정된다면, 이는 Block State로 변경된다. 그렇지 않고 Root/Designated Port로 지정된다면, 15초 정도의 여유를 두고 Learning State로 변경된다.
2. Learning State(학습)
   전송을 수행하기 이전에, 연결된 Switch들의 MAC address를 학습하는 단계이다. 해당 단계가 15초 지속된 뒤에, Forwarding State로 넘어간다. 이 과정에서 갑자기 Port가 Alternated Port로 변경된다면, 이 또한 Block State로 바로 넘어간다.
3. Forwarding State(전송)
   실제로 Data를 전송하는 단계이다. 이때에는 실제로 각 장치 간에 데이터가 이동할 수 있다.
4. Blocking State(차단)
   이 상태에서도 해당 Port가 Root/Designated Port가 될 수 있다. 그럴 경우 Listening State로 변경되고, 통신 준비를 한다.
5. Disable State(비활성)
   해당 Port가 고장 또는 비연결 등으로 비활성화되어 있는 상태이다.

이렇게 결국은 Forwarding State에 도달하게 되었을 때 실제로 데이터를 주고 받는 것이 가능해지게 된다. 중간에 연결이 끊기더라도 유기적으로 계속해서 BPDU를 주고 받으면서 Root/Designated/Alternated Port로 역할이 계속해서 바뀌면서, 지속적인 연결을 추구한다. 하지만, 이 합의 과정이 생각보다 길기 때문에(Block -> Forwarding 45초 소요) 이를 해결하기 위한 RSTP, MSTP, SPB 와 같은 방법론도 있다.

Static Routing Protocol

data의 Route를 사전에 관리자가 직접 정의하는 방법이다. 이는 인터넷 가입자 구간에서 설정 시에 사용하며, 대표적인 예시가 Default Gateway 등을 지정하는 과정이다. 장애가 발생하더라도 계속해서 동일한 곳으로 요청을 보내기 때문에 장애에 대한 책임은 온전히 설정을 수행한 관리자에게 달려있다. AS에 상관없이 각 Router에서 직접적으로 다음 Link를 선택하기 때문에 AS에 상관없이 동일하게 설정한다.

Dynamic Routing Protocol

Router가 실행 중에 계속해서 장애에 대응하면서, 가용성 높은 Routing을 제공하기 위해서 경로를 최적화하는 방식이다. 이는 AS에 따라서 설정 방법이 상이하기 때문에 이에 따라서 분류한다.

• Interior(IGP) : AS 내부에서의 Routing Protocol이며, Link의 상태를 기반으로 하는지 hop 수(중간 Router의 수)를 기반으로 하는지에 따라서 두 가지 종류로 나누어진다.
  • Distance Vector
    Distance(Router 간의 Hop 수)와 Vector(방향)만을 고려하여 Routing Table을 구성한다. 인근 Router에 의해서 받은 정보를 통해서 구성하게 되며, Link의 Bandwidth, 현재 상태를 알지 못하기 때문에 최적화와는 거리가 멀다. 심지어는 반대 방향으로 돌아가는 현상도 발생할 수 있다. 종류는 대표적으로 아래 두 가지가 있다.
    1. RIP(Routing Information Protocol)
       최초의 Dynamic Routing Protocol로 각 Router간의 Hop 수를 기반으로 Distance를 추정한다. 소규모 네트워크를 구축할 때는 매우 간단하게 설정이 가능하지만, Hop 수 만을 활용하기 때문에 복잡한 네트워크 구성에는 적절치 않다. 또한, 30초 단위로 업데이트가 발생하기 때문에, 빠른 장애 회복이 되지 않는다. 또한, 최대 Hop 수를 15로 제한하였고, 그 이상은 Network가 연결되지 않았다고 인식한다. version은 1,2가 존재하고, 2 역시 1과 대동소이 한다.
    2. IGRP(Interior Gateway Routing Protocol)
       RIP와 유사하고, 기존 90초 단위로 Routing Table을 갱신하며, Hop 수를 255까지 확장하였다.
  • Link State
    Link(통신선) 상태 역시 고려하는 Protocol이다. 단순한 기기 간의 거리 뿐만 아니라 bandwidth 등과 같은 정보도 활용한다. 또한 Network 전체의 정보를 포함하고 있다. 즉, Routing Table의 크기가 굉장히 커질 수 있다. 이는 Router의 Memory 소모와 CPU 소모를 급격하게 늘린다. 또한, Routing Table을 동일하게 유지해주는 Convergence(이것이 제대로 수행되지 않으면 통신 실패가 발생할 수도 있다.)를 수행하기 위해 소모되는 시간인 Convergence Time이 과도하게 커질 수도 있다. 이러한 문제를 해결하는 것이 해당 Link State 방식의 주요 목표이다.
    1. OSPF(Open Shortest Path First)
       Network를 Area라는 단위로 나누고, 각 Area에서는 해당 Area에 해당하는 Routing Table을 보관하게 하여 전체 Routing Table의 크기를 줄인 방식이다. 같은 Area 내에서는 모든 Router가 동일한 Routing Table을 소지한다. 만약, 두 개 이상의 Area에 속한다면, 해당 Router는 두 개의 Routing Table을 소지하게 된다. Area가 하나일 경우에는 임의의 Area No을 사용해도 상관이 없지만, Area가 여러 개일 경우에는 Area 0이 반드시 존재해야 하며, 해당 Area 0를 중심으로 Topology가 구성되기 때문이다. 가장 대중적으로 많이 사용되는 Routing Protocol로 IGP 내에서는 Conversionce Time이 짧고 효율적이다. 최단 거리를 찾을 때에는 Dijkstra Algorithm을 활용하여 최단거리를 탐색한다.
    2. ISIS(Intermediate System - Intermediate System)
       Intermediate System은 Router를 의미하며, 같은 Area에 속하는 Router간의 Routing Table을 공유하는 개념으로 Router를 총 두 가지로 나눈다. 하나는 여러 Area에 걸쳐 있는 Level 2, 하나의 Area에 속하는 Level 1이다. 대게 모든 Router가 Level 2에 속하기 때문에 굉장히 큰 Routing Table을 가지게 된다. Routing Table이 커질 수 있지만 Conversionce Time이 줄어들고, Backborn을 Area 0으로 제한하지 않기 때문에 OSPF보다 더 유연한 네트워크 구조를 구축할 수 있다.
  • Hybrid
    • EIGRP(Enhanced Interior Gateway Routing Protocol)
      Hop 수를 256개로 늘리고, 주기 없이 Network 환경이 변화되면 바로 적용되도록 바꾸었다. 또한, Hop 수 외에도 Bandwidth, Delay, Load, MTU 등을 추가적으로 계산하여 Link State 역시 활용하는 방식이다.
• Exterior(EGP)
  나뉘어진 AS 간의 통신을 지원하기 위한 방법이다.
  • BGP(Border Gateway Protocol)
    서로 다른 AS를 연결하는 Protocol로 TCP에 기반하며, IGP와 같이 연동하여 전체 네트워크를 구성할 수도 있고, 자체적으로 정의한 Interior BGP를 활용하여 BGP만으로 네트워크를 구성하는 것도 가능하다. 따라서, BGP는 iBGP(interior BGP), eBGP(exterior BGP)로 나눌 수 있다. BGP는 여타 IGP들과는 다르게 AS간의 Routing을 중계하기 때문에 Routing Table의 크기가 매우 크고, 이에 대한 처리에 특화되어있다. 하지만, 대게 BGP라고 하면 eBGP를 의미한다. 특이하게 BGP는 기존의 Link State나 Hop 수에 기반하지 않고 Attribute(Hop, Bandwidth, ACL, Weight 등)라는 것을 별도로 활용한다. Dynamic Routing 방식이지만, 각 Link에 대한 정보는 앞에서 언급한 Attribute를 이용하여 수동으로 설정해주어야 한다. 하지만, BGP는 Broken Gateway Protocol이라는 별명이 있을 정도로 현재 많은 문제를 야기하고 있다. BGP Table의 크기가 102.4만 개를 초과할 시에 일부 Router의 Memory가 부족해지는 현상이 발생할 수 있다. 현재 해당 크기에 도달 시점을 2023년 말 정도로 예측하고 있다. 또한, 이렇게 커진 Table의 크기로 인해 Convergence Time도 굉장히 많이 소모하고 있다.(완전 수렴까지 15분 소요)

Reference

• Thumbnail : Photo by Nick Seagrave on Unsplash