컴퓨터 네트워크

Computer network - Routing

김윤재 2025. 12. 28. 14:37

IP 주소가 너무 많기에 이게 수십 억개 IP주소 테이블까지 확장 가능할 수 있다..

이를 어떻게 해결할 것인가.

현재까지의 가정

모든 라우터는 동일하다. → 같은 역할, 같은 정보 공유
네트워크는 납작하다. → 계층이 없는 하나의 거대한 네트워크
현실에서는 아니다..

현실:

라우터마다 역할 다름
ISP / 기업 / 백본 등 계층 존재
모든 라우터가 모든 IP를 알 수 없음

해결 방법

수십억 개의 IP 주소 테이블 - 메모리 저장 불가, 트래픽 폭발, 계산량 과다

→ Scalable Routing

네트워크를 계층(level) 으로 나눔
각 기관(AS) 내부에서는:
- 내부 라우팅 프로토콜 사용 (OSPF, RIP 등)
기관 간(계층 간)에서는:
- 내부 구조를 숨기고 요약된 정보만 교환

구체적인 방안으로는 여러개의 IP주소를 하나의 prefix로 묶는다.

→ CIDR, IP address agrregation

인터넷이 Scalable하게 라우팅을 구현하는 법 - AS

1. Internet approach to scalable routing

인터넷은 “독립된 기간 단위(AS)”로 나누어 라우팅

AS란 !

하나의 기관/ 조직이 관리하는 라우터 집합 - 일반 공유기는 통신사의 라우터집합에 들어가있는가?

→ 통신사(ISP), 대학교 네트워크, 대기업, 클라우드 사업자

AS는 추가로 AS 번호(ASN)을 가진다

2. Instra-AS vs Inter-AS

Intra-AS

같은 AS내부
동일한 라우팅 프로토콜 사용
목표 :
- 빠른 수렴
- 최단 경로
- 성능 중심

예시: OSPF, RIP, EIGRP, IS-IS

OSPF, RIP는 나중에 다시

EIGRP

Distance Vector 기반 (개선형)
과거 Cisco 전용
지금은 RFC 공개
Cisco 환경에서 주로 사용

IS - iS

ISO 표준
OSPF와 거의 동일한 개념
대형 ISP에서 많이 사용

Inter-AS

AS와 AS 사이
경계 라우터(게이트웨이)가 담당
목표:
- 정책
- 사업 관계
- 안정성

사용 프로토콜 : BGP

3. Interconnected ASes

포워딩 테이블은 intra-AS와 inter-AS 라우팅의 결과를 같이 반영한다.

내부 목적지
- intra-AS 라우팅 만으로 결정
- AS내 최단 경로 사용
외부 목적지
- 어떤 AS로 나갈 것인가 → inter-AS(BGP)
- 정한 출구 라우터까지 내부에서 어떻게 갈 것인가 → intra-AS

→ 포워딩 테이블 : 외부 목적지 prefix를 바탕으로 어느 출구 게이트웨이로 보낼지, 그리고 그 게이트웨이까지의 내부 경로를 알려준다.

RIP

Distance Vector 기반
30초마다 Distance Vector 교환→ 변화가 없어도 계속 트래픽 발생(30초마다 무조건 교환해야하니까)
→ 장애 발생 시 수렴 느림(최대 30초 기다림)
→ 이웃 라우터에게 내가 아는 모든 목적지 + 거리 광고 (주기적 광고)
Distance metric: hop 수ex) hops (max = 15) → 16홉 = 무한대 → 네트워크 크기 제한
→ 경로 품질은 거쳐가는 라우터 개수(홉 수)로만 = 대역폭, 지연, 혼잡은 보지 않음
Advertisement 크기 제한→ 대규모 네트워크 불가
→ 한번에 최대 25개 목적지만 보낼 수 있음(더 크다면 쪼개서 보내야함..)
루프 방지: Poison Reverse→ 결국 16에 도달해야 못가는 경로인 걸 알고 시간 낭비를 하게됨→ A,B가 있을 때 A가 B에게 C에 대한 정보를 줬다. → 그러나 C가 다운됨 → 이 때 A가 C에 가야한다. 그러나 A는 C가 다운된 걸 몰라 이를 본인이 정보가 있지만 안 가지기에 B에 물어봄 (여기서 poison reverse)발생 → B가 A에게 본인이 저장한 정보가 아닌 무한대를 알려줌.
→ 한계는 결국 직전에 이뤄지는 상황만 이렇다. 라우팅테이블은 목적지, nexthop만 알기에 이를 2단계 거치면 알 수 없게 되어 한계를 가짐
→ 여기서 Poison Reverse는 이 루프를 방지하기 위해
→ 서로 계속 잘못된 정보 교환하는 것 = count-to-infinity문제
UDP 사용
→ 신뢰성 X, 순서 보장 X, 단순함 중시

RIP는 구현은 쉽지만 느리고 확장성이 없다 이로 인해 대규모 네트워크에선 불가

OSPF

모든 라우터가 네트워크 지도를 공유하고 각자 최단경로를 계산하자

open→ 표준 프로토콜
→ 누구나 구현이 가능하다…
→ 특정 회사 소유가 아님
Link-State-flooding→ 모든 라우터가 전체 토폴로지 보유
토폴로지란 - 네트워크의 지도와 같은 느낌으로 라우터들이 LSA를 보내면 이를 LSDB를 만든다. 이것은 토폴로지와 같은 것 이는 공유됨
→ 각 라우터가 본인의 이웃과 링크 비용을 AS전체에 flood
다양한 비용 metric→ 빠른 링크 = 낮은 비용, 느린 링크 = 높은 비용
→ RIP는 홉수만 봤음 but OSPF는 대역폭, delay같은 요소도 본다
다익스트라 사용→ 포워딩 테이블 생성
→ 각 라우터가 자기 기준 최단경로 트리 계산
보안→ 악성 라우터 차단
→ 인증 없는 라우팅 정보 X
Link-State기반

OSPF는 구현이 복잡하고 오버헤드 크다는 점이 있지만 빠른 수렴과 정확한 경로로 대규모 네트워크가 가능하기에 현업 표준으로 사용중이다.

OSPF에서 정보흐름

모든 라우터가 LSA 생성→ 본인 라우터ID, 연결된 이웃 라웉, 각 링크의 코스트, 링크 상태
→ 목적지 목록이 아닌 링크 상태 공유
→ LSA란 각 라우터가 만들어서 네트워크에 뿌리는 공지
LSA를 flooding (AS 전체에 전달)
모든 라우터가 동일한 링크 상태 DB 보유
각자 Dijkstra 실행
포워딩 테이블 생성

Hierarchical OSPF - OSPF도 scalable해야한다

계층이 필요한 이유

모든 LSA를 AS전체에 flood

만약 AS가 커지면 LSA 폭발, CPU, 메모리 부담 증가

→ OSPF는 scalable하지 않다..

해결 방안

2계층 구조로 가자

Local routers (Internal routers)
- 자기 area 내부 정보만 안다
- LSA도 area 내부에서만 flood
- 외부 목적지는 area border router로 전달
Area Border Router(ABR)
- 여러 area에 연결
- 역할:
  - area간 트래픽 중계
  - 요양된 정보 전달
Backbone (Area 0)
- 모든 area 연결의 중심
- area 간 트래픽은 무조건 backbone을 경유한다..
Boundary Router(ASBR)
- 다른 AS와 연결
- BGP와 OSPF를 연결하는 지점

HIerarchical OSPF의 효과로 LSA 범위를 제한하고 계산량 감소 및 대규모 AS가 가능하게 하였다.

결론

인터넷은 AS 단위로 계층적 라우팅
intra-AS: 성능 중심
inter-AS: 정책 중심
외부 목적지는 BGP + 내부 라우팅 조합
포워딩 테이블은 두 라우팅 결과의 합

Inter - AS Routing: BGP

BGP (Border Gateway Protocol)

ex) 충남대 ↔ KT, KT ↔ SK브로드밴드 등 기관 사이의 라우팅

eBGP: 외부 라우터와 subnet reachability information 획득
iBGP: AS 내부 라우터들에게 reachability information 전달
경로 설정
- “good” routes to other networks based on reachability information and policy - 정보와 정책에 기반하여 다른 네트워크에 연결
BGP session: BGP router는 TCP로 연결된다.
- 목적지에 대한 경로 정보 광고
- BGP is a “path vector” protocol
ex) AS3 gateway 3a 광고 → AS2 게이트웨이 2c
→AS3과 ip 주소

BGP path

BGP path: prefix + attributes

prefix: IP주소 (CIDR)
속성
- AS-PATH: AS 리스트
- Next-Hop: 다음 AS로 향하는 라우터 주소

정책 기반 라우팅

정책
- accept/decline path (e.g., never route through AS Y).
- advertise path to other other neighboring ASes

BGP 요약

BGP는 distance vector→ AS-PATH에 자기 AS가 있다면 버림 → 루프 방지
→ distance vector인데 루프가 안 생기는 이유
BGP path = prefix + attributes
prefix = IP 주소 블록
AS-PATH = 지나가는 AS 리스트
NEXT-HOP = 실제로 보내야 할 다음 라우터
BGP는 정책 기반 라우팅
accept/decline + advertise 정책이 핵심
최단 경로 X, 사업·정책 O
AS 간(inter-AS) 라우팅 전용

핵심 포인트 정리 (이해 체크)

✔ prefix를 보고 어디로 갈지 결정하는 건 누구?

→ BGP

✔ BGP는 “어디까지” 책임지나?

→ AS 경계까지 (출구 선택)

✔ AS 내부에서 그 출구까지 가는 길은 누가 찾나?

→ OSPF

✔ 최종 목적지까지의 전체 경로를 한 번에 계산하나?

→ 아님

→ AS 단위로 나눠서 계산

BGP messages

BGP 메시지는 피어간(이웃) TCP연결을 바탕으로 교환한다.

→ 안전성 보장, 순서 보장, 재전송 필요 → 경로정보는 유실되면 안됨.

메시지 종류

OPEN 메시지
- TCP 연결 후
- BGP 세션을 시작하는 메시지(내 AS 번호)

→ 서로의 AS 번호 확인 및 정책상 허용된 이웃인지 확인(경로는 아직 안 보냄)

UPDATE 메시지
- 새 경로 광고
- 기존 경로 철회
- Prefix, attributes(AS-PATH, NEXT-HOP)가 들어감.
KEEPALIVE 메시지
- 업데이트가 없을 때
- TCP/BGP 세션 유지
특징
- 아주 작음
- 주기적 전송 (60초)
역할

→ KEEPALIVE, UPDATE가 일정 시간 안 오면 이웃이 죽었다 판단

NOTIFICATION 메시지
- 에러 보고
- 보낸 즉시 BGP 세션 종료
예시
- 잘못된 AS번호
- 잘못된 메시지 포맷
- 정책 위반
역할

전체 흐름

TCP 연결
OPEN ↔ OPEN
KEEPALIVE
UPDATE (경로 광고/철회) → 새로운 prefix, 더 좋은 경로, 링크/AS 다운일 때 일어남.
(중간중간 KEEPALIVE)
에러 발생 시 NOTIFICATION → 종료

BGP는 TCP 위에서

OPEN으로 관계 맺고,

UPDATE로 prefix+경로를 알리며,

KEEPALIVE로 살아있음을 확인하고,

NOTIFICATION으로 에러 시 종료한다.

1d는 단순한 예시 라우터
X는 AS3에 있는 prefix
AS1 내부 어느 라우터에서든 X로 패킷이 시작될 수 있음
BGP는 출구(1c)를 정하고
OSPF는 “내가 지금 있는 라우터에서 그 출구까지 어떻게 가나”를 정함

BGP 경로 선택 방법

큰 weight 값의 경로 - 라우터 내부에서만 쓰고 이 경로를 쓰고싶다라는 로컬 설정
→ 트래픽 강제로 보내고 싶을 때, 테스트/ 운영 편의용
큰 local preference value attribute: policy decision→ AS내부(iBGP) 전체에 공유
→ AS 전체의 정책 결정 - 우리 AS에서는 이 출구를 선호한다… 이런거
shortest AS-PATH→ 내부 라이터개수, 지원과 대역폭은 안본다… 오직 AS 수
→ 거쳐가는 AS 개수 가장 적은 경로 = 짧은 경로 but 최우선은 아님
closest NEXT-HOP router: hot potato routing→ 내 AS내 트래픽 운반 비용 줄음, ISP 입장에선 중요한 것
→ 여기서 가장 가까운 거 찾을 때 OSPF사용
→ 여러 경로가 남아 있다면 본인 AS내부에서 가장 가까운 출구선택
MED(multi-exit discriminator) 값이 낮은 경로→ 같은 이웃 AS사이에서만 비교
→ 상대 as가 제안하는 선호 출구(본인 as로 들어올 땐 이쪽으로 와달라..)

BGP는

(1) 로컬 강제 →

(2) AS 정책 →

(3) AS 경로 길이 →

(4) 내부 비용 최소 →

(5) 상대방 제안

순으로 우선순위를 정해 경로 설정