라우터가 패킷을 전달하기 위한 최단 경로 찾기
인터넷은 여러 네트워크가 라우터를 통해 연결된 형태로 이루어져 있다.
패킷이 전달되는 경로의 비용(Metric)을 최소화하여 최단 경로를 찾아내는 것을 라우팅이라고 한다.
인터넷은 다양한 조직의 자율 네트워크로 구성되어있다.
네트워크는 너무 크고 분산되어 있으므로, 모든 라우터의 테이블을 단일 프로토콜로 관리하기 어렵다는 문제가 있다.
이를 해결하기 위해 각각의 네트워크와 라우터들을 하나의 단일 관리 그룹으로 묶어서 관리한다.
이것을 자율 시스템(AS)이라고 부른다.
자율 시스템 내에서 라우팅은 내부와 외부 라우팅으로 구분되어 있다.
내부 라우팅은 각 자율 시스템(R1, R4) 내부에서의 경로를 선택하고,
외부 라우팅은 자율 시스템 간의 경로를 연결한다. (R2와 R3 간의 연결)
RIP (Routing Information Protocol)
각 링크를 동일하게 취급하며, 목적지까지의 홉 수(Hop Count)를 기반으로 경로를 선택한다.
예를들어, 10개의 라우터를 통과하면 비용은 10이 된다.
이와 같은 방식은 Bellman-Ford 알고리즘을 기반으로 작동하는 거리 벡터 라우팅을 사용한다.
거리 벡터 라우팅에서 라우터는 주기적으로 자신이 알고 있는 정보를 이웃에게 공유한다.
공유는 인접한 이웃 라우터에만 이루어지고, 일정한 시간 간격으로 정보를 업데이트한다.
이 때, 거리 벡터 라우팅 테이블에서 각 엔트리는 특정 목적지와 해당 목적지까지의 홉 수를 나타낸다.
RIP 메시지를 받았다면 각 목적지에 대해 홉 수를 1 증가시키고
목적지를 기존 라우팅 테이블과 비교하여 없으면 추가, 있으면 아래 규칙에 따라 처리한다.
- 홉 수가 더 적으면 기존 엔트리를 대체.
- 홉 수가 같으면 그대로 유지.
- 홉 수가 많으면 무시.
라우팅 테이블 업데이트 예시 - 초기 라우팅 테이블
라우터는 네트워크에 추가되면 설정 파일을 통해 초기 라우팅 테이블을 생성한다.
이후, 각 네트워크에서 인접 라우터 정보를 포함한 초기 테이블을 설정한다.
최종 라우팅 테이블
각 라우터가 네트워크 정보를 수집 및 교환한 후, 모든 네트워크와 최적 경로 정보를 포함하여 최종 라우팅 테이블이 완성된다.
RIP 메시지 형식
- Command: 요청(1) 또는 응답(2) 명령을 지정.
- Version: RIP 프로토콜 버전.
- Family: TCP/IP의 경우 값은 2로 설정.
- Network Address: 목적지 네트워크 주소.
- Distance: 광고하는 라우터로부터 목적지 네트워크까지의 홉 수.
요청(Request)은 특정 목적지 정보 요청과 모든 경로 정보 요청 두 가지가 있다.
라우터가 네트워크에 추가되거나 일부 타임아웃된 항목이 있을 때 전송한다.
응답(Response)은 요청에 대한 응답과, 요청받지 않았음에도 주기적으로 전송되는 응답 두 가지가 있다.
요청받은 것에 대한 응답은 요청된 목적지 네트워크에 대한 정보를 갖고있고,
요청받지 않은 응답은 전체 라우팅 테이블 정보를 갖고있다.
RIP 응답 메시지 예
여러 네트워크 주소와 해당 홉 수가 나열되어 있다. message 부분이 홉 숫자다.
RIP 타이머
RIP는 주기적으로 라우팅 정보를 교환하기 때문에 다양한 타이머가 있다.
타이머는 라우팅 테이블을 관리하는 곳에 포함되어서
라우팅 루프를 방지하거나 오래된 정보를 제거 및 네트워크 관리를 하고 있다.
- Periodic Timer:
- 정기적인 메시지 전송을 제어.
- 25~35초 사이의 랜덤 주기로 알림.
- Expiration Timer:
- 라우팅 정보의 유효 기간 제어.
- 180초 내에 업데이트가 없으면 경로를 만료로 간주, 홉 수를 16으로 설정(무효 경로).
- Garbage Collection Timer:
- 만료된 경로를 120초 동안 광고한 후 테이블에서 삭제.
RIP의 문제점
RIP는 네트워크 변화가 인터넷 전체로 전파되는 데 시간이 오래 걸린다.
예를 들어 Net1에서 변화가 발생하면 라우터 R1이 30초마다 주기적으로 업데이트를 전송하며, 이를 R2가 수신한다.
이 때 각 단계마다 평균 15초가 소요되므로, 네트워크의 변화가 완전히 전파되기까지 많은 시간이 걸린다.
또한, 네트워크에서 장애가 발생하면 모든 라우터의 라우팅 테이블이 한동안 불안정해질 수 있다.
이 과정에서 패킷이 여러 라우터 간에 무한 루프를 형성할 수 있다.
예를 들어 Net1이 장애를 겪으면
각 라우터는 Net1 경로의 홉 수를 반복적으로 업데이트하면서 라우팅 루프를 형성할 수 있다.
문제 해결 방법
(1) Triggered Update
변화가 발생하면 즉시 업데이트 메시지를 전송하여 빠른 안정화를 유도한다.
(2) Split Horizon
경로 정보를 광고한 방향으로 다시 보내지 않음으로써 루프를 방지한다.
ex) A가 Net1의 경로를 Net2로 보냈다면, Net2는 Net1 경로 정보를 다시 A로 보내지 않음.
(3) Poison Reverse
원천 경로로 홉 수를 16으로 설정(무한값)하여 경로를 비활성화시킨다.
ex) Net1 경로가 비활성화되면, A는 Net1의 홉 수를 16으로 설정하여 Net2로 보냄.
RIP Version 2
이것은 RIP Version 1의 한계를 극복하기 위해 설계됐다.
기존에 0으로 채워진 필드들을 새로운 필드로 대체하여 기능을 개선한다.
RIP와 메시지 형식이 조금 달라졌다.
- Route Tag: 자율 시스템 번호와 같은 정보를 포함.
- Subnet Mask: 서브넷 마스크 정보를 전달.
- Next-hop Address: 다음 홉의 주소를 표시.
또한 인증 기능이 추가되어 비인가된 광고를 방지할 수 있다.
Family 필드는 FFFF₁₆ 값을 사용하며 16바이트 크기의 인증 데이터를 갖고 있다.
UDP 데이터그램에 캡슐화하여 UDP에서 RIP에 할당된 포트 번호 520을 사용한다.
OSPF(Open Shortest Path First)
관리자가 링크별 비용을 설정하며, OSPF는 목적지까지의 총 비용을 계산해 최적 경로를 찾는다.
OSPF는 하나의 자율 시스템(AS) 내부에서 사용되는 프로토콜이다.
AS를 여러 개의 영역(Area)으로 나누어 효율적이고 빠르게 라우팅을 처리하는데
여기에서 영역(Areas)은 네트워크, 호스트, 라우터로 구성된 집합을 말한다.
하나의 AS 내에 여러 영역으로 나눌 수 있으며, 영역 내부의 모든 네트워크는 연결되어야 한다.
영역 내의 라우터는 멀티캐스트를 사용해서 라우팅 정보를 공유한다.
위 그림을 보면
특정 영역의 정보를 요약하여 다른 영역으로 전달하는 Area Border Router,
AS 내의 모든 영역을 연결하고 있는 백본(Backbone)으로 구성되어 있다.
여기에서 Area 0은 주 영역으로 기능하며 백본 라우터로 구성된다.
백본 라우터는 Area Border Router가 될 수 있다.
관리자는 라우팅 경로에 대해 "메트릭"이라는 비용을 할당할 수 있다.
메트릭(metric)은 경로의 비용, 우선 순위를 나타내며 네트워크 경로를 선택하는 데 사용되는 기준 값이다.
OSPF는 각 라우팅 경로의 비용(cost)을 계산하여 최적의 경로를 결정한다.
또한 OSPF는 링크 상태 라우팅(Link State Routing)을 사용하여 영역 내 라우팅 테이블을 업데이트한다.
라우터는 자신과 이웃에 대한 정보를 다른 모든 라우터와 공유(Flooding)한다.
변화가 발생했을 때만 정보를 공유하여, 이를 통해 Distance Vector 라우팅 방식의 비효율성을 극복하고 있다.
OSPF의 링크 타입
OSPF의 링크 유형 및 작동 방식에는 4가지 타입이 있다.
Point-to-Point Link
각 라우터는 링크 반대편에 단일 이웃만 가지는 상태이다.
이 경우는 두 라우터 간의 직접 연결에 사용된다.
R1 ─── R2
Transient Link
여러 라우터가 연결된 네트워크다.
모든 라우터를 상호 연결하는 비현실적 표현 대신, 지정된 라우터(Designated Router)를 통해 네트워크를 단순화한다.
예를 들어 이더넷과 같은 네트워크에서 여러 라우터가 연결된 형태가 있다.
DR
│
┌─────┴─────┐
│ │
R1 R2
│ │
R3 R4
DR(Designated Router)은 라우터들 간의 트래픽을 효율적으로 관리하고
R1, R2, R3, R4는 같은 네트워크에 속한 라우터들이다.
여기에서 Designated Router는 LAN 내 라우터를 대표하는 지정 라우터를 말한다.
각 라우터는 지정 라우터와만 이웃 관계를 유지하고, 이웃 관계 수를 줄이는 것으로 효율성을 높인다.
지정 라우터와 다른 노드 간에는 메트릭이 정의되지 않는다. (지정 라우터가 네트워크를 대표하기 때문)
Stub Link
단일 라우터에만 연결된 네트워크를 말한다.
Transient Network의 case중 하나라고 볼 수도 있다.
R1 ─── N1
Virtual Link
두 라우터 간의 직접 링크가 끊어졌을 때, 대체 경로로 가상 링크 생성한다.
예를 들어 관리자가 두 라우터를 연결하는 긴 경로를 생성하여 문제를 해결할 수 있다.
R1 ── (Area 0) ── R2 ── (Virtual Link) ── R3
OSPF의 전반적인 작동 과정
OSPF는 링크 상태 라우팅 프로토콜로
네트워크 내 모든 라우터가 동일한 링크 상태 데이터베이스(Link State Database, LSDB)를 공유한다.
라우터는 자신의 네트워크 상태와 연결 정보를 Link State Advertisements (LSAs)로 광고하고
모든 라우터들은 LSAs를 받아서 LSDB를 생성한다.
이 때 Link State Advertisements (LSAs)란
각 라우터가 이웃 및 링크 상태 정보를 공유하기 위해 사용하는 데이터를 말한다.
LSAs는 네트워크 내 모든 라우터에 전파되어 라우팅 테이블을 구성한다.
LSA에는 여러 type이 있다.
Router Link
라우터의 링크 상태를 나타낸다.
해당 라우터에 연결된 모든 링크와, 링크의 양쪽 끝에 있는 이웃에 대한 정보를 갖고 있다.
ex) Transient Network, Point-to-Point 링크, Stub Network, Virtual Link 정보를 갖고 있다.
Network Link
네트워크의 링크 상태를 나타낸다.
지정된 라우터(Designated Router)가 네트워크 링크 정보를 광고한다.
ex) LAN 네트워크에서 5개의 라우터가 연결된 상태를 나타냄.
Summary Link to Network
영역 간의 요약된 네트워크 정보를 제공한다.
경계 라우터(Area Border Router)가 여러 영역의 라우팅 정보를 요약하여 전달한다.
ex) R1이 Area 1에 Area 0 네트워크 정보를 제공
Summary Link to AS Boundary Router
자율 시스템 경계 라우터(AS Boundary Router)로 가는 경로 정보를 제공한다.
AS 외부로 패킷을 보내기 위해 필요한 정보를 포함한다.
ex) R2가 Area 2에 AS Boundary Router로 가는 경로를 제공
External Link
자율 시스템(AS) 외부 네트워크의 가용성을 나타낸다.
AS 경계 라우터가 외부 네트워크 정보를 내부로 전파하면, 내부 라우터가 외부 네트워크에 접근할 수 있도록 경로를 제공한다.
ex) Area 0에서 AS 경계 라우터를 통해 외부 네트워크 정보가 flooding.
이제
모든 라우터가 Router Link LSA와 Network Link LSA를 받아서 LSDB를 생성했으면
각 라우터는 LSDB를 바탕으로 Dijkstra 알고리즘을 통해 최단 경로를 계산한다.
Dijkstra 알고리즘
https://guhonga.tistory.com/140
Shortest Paths - Bellman Ford, Dijkstra’s algorithm
MST와 Shortest Paths의 차이 https://guhonga.tistory.com/139 Minimum Spanning Tree (MST) 소개 - Kruskal, Prim’s algorithmMST 소개 및 특징Spanning Tree란, cycle을 갖지 않고 그래프 내의 모든 정점이 연결된 트리를 말한다.
guhonga.tistory.com
간단하게 소개하자면
단일 소스에서 모든 목적지까지의 최단 경로를 계산하는 알고리즘이다.
시작 노드를 트리의 루트로 설정하고 비용 0을 할당하면
루트 노드에서 인접 노드를 확인하고 누적 비용을 계산해서 임시 노드로 추가한다.
임시 노드 중 누적 비용이 가장 작은 노드를 선택하여 영구 노드로 설정하고
모든 노드가 영구 노드가 될 때까지 이 과정을 반복한다.
이렇게
LSDB를 바탕으로 Dijkstra 알고리즘을 통해 최단 경로를 계산했으면
계산된 결과를 바탕으로 라우팅 테이블을 생성한다.
Routing Table
각 라우터는 최단 경로 트리(SPT)를 사용하여 라우팅 테이블을 생성한다.
영역 내 네트워크에 도달하는 비용을 표시하고
외부 네트워크에 도달하기 위해 요약 링크(Summary Link) 및 외부 링크(External Link)를 사용한다.
OSPF 패킷 Type들
Version: OSPF의 버전.
Type: 패킷 유형 지정. (Hello, Database Description 등).
Source Router IP Address: 송신 라우터의 IP.
Authentication: 메시지 인증 정보. (비밀번호 또는 인증 해시 값)
등등 OSPF 패킷은 여러가지 필드로 구성되어 있는데
각각의 패킷 유형에는 이와 같은 필드들이 어떻게 사용될지를 나타내는 방식이 있다.
(1) Hello Packet ( Type: 1 )
인접 라우터와 관계를 설정하고 이웃의 접근 가능성을 테스트한다.
같은 영역에 있는지 Area ID, 라우터의 IP 주소를 포함하는 이웃이 있는지를 Source Router IP Address 필드들을 통해 확인한다.
(2) Database Description Packet ( Type: 2 )
라우터가 시스템에 처음 연결되거나 오류 후 재연결 시 사용한다.
링크 상태 데이터베이스의 개요를 제공한다.
(3) Link State Request Packet ( Type: 3 )
특정 링크 또는 라우트에 대한 정보를 요청한다.
(4) Link State Update Packet ( Type: 4 )
링크 상태 정보를 광고하여 네트워크를 업데이트한다.
(5) Link State Acknowledgment Packet ( Type: 5 )
모든 링크 상태 업데이트 패킷의 수신을 확인한다.
BGP (Border Gateway Protocol)
BGP는 inter-AS 라우팅 프로토콜로, 대규모 네트워크에서 자율 시스템(AS) 간 데이터를 교환하는 데 사용된다.
경로 선택 시 단순히 거리(홉 수)를 기준으로 하지 않고 경로 정책과 속성을 활용하여 최적 경로를 선택한다.
링크 상태나 거리 벡터 라우팅은 외부 라우팅에 적합하지 않기 때문에 BGP는 Path Vector Routing 방식을 사용한다.
아래는 Path Vector Routing Table의 예시다.
테이블은 목적지 네트워크, 다음 라우터, 경로(AS 목록)으로 구성되어 있다.
위 테이블을 보면 N01 네트워크는 R01을 통해 이동하며, 경로는 AS14 → AS3 → AS67
Path Vector Messages는 AS 내부에서 네트워크의 도달 가능성을 이웃 AS에 알려준다.
수신한 경로가 정책에 부합하는지 확인하고 검증 후, 라우팅 테이블을 업데이트하고 이웃 라우터로 메시지 전달한다.
BGP에서 사용되는 주요 메시지 유형은 다음과 같다.
- Open: 이웃 관계 형성을 위한 메시지.
- Update: 경로를 추가하거나 제거할 때 사용.
- Keepalive: 이웃 라우터 간 연결 유지.
- Notification: 오류가 발생하거나 연결이 종료될 때 알림.
(TCP 포트 179를 사용한다.)
이것은 여러 AS 간 경로 및 라우터를 통한 데이터 흐름(패킷)을 나타낸 것이다.
라우터는 관리자가 설정한 정책에 따라 경로를 선택하는데
특정 경로가 정책에 맞지 않으면 무시할 수 있다.
홉 수나 메트릭 대신 관리자가 정의한 조건을 기준으로 경로를 결정한다.
BGP 경로 속성
BGP 경로 속성은
모든 BGP 라우터가 반드시 인식해야 하는 Well-Known Attributes (필수 속성)과
필수는 아니고, 선택적으로 사용되는 Optional Attributes (선택 속성)이 있다.
필수 속성
ORIGIN: 경로가 어떻게 생성되었는지 표시.
AS_PATH: 경로를 거쳐간 AS 목록.
NEXT_HOP: 패킷이 도달해야 할 다음 라우터의 IP 주소.
선택 속성
전이 속성: 다른 라우터에 전달됨.
비전이 속성: 수신 라우터에서만 사용되고 다른 라우터로 전달되지 않음.